MODULE- 2- LECTURE 2

ALU- SIGNED ADDITION/SUBTRACTION

ALU INPUTS AND OUTPUTS
 Performs arithmetic and logical operations on
data.

 Other elements of the computer system(control

unit, registers, memory, I/O) brings data into ALU
for process and take the results back out.

 Operands for ALU presented in registers and

also results stored in registers

ALU also sets flag values in registers as the

result of operation
Example: overflow=1 if result of
computation exceeds length of register

Control signals control the operation of ALU and

data movement in and out of ALU
INTEGER REPRESENTATION
 Three systems are used to positive and negative
represent numbers
-Sign-magnitude
-1’s complement
-2’s complement

 In all three systems,

*Left most bit is 0 for positive and 1 for negative numbers
 Positive values are same for all systems

 In sign& magnitude, negative values represent by changing

MSB b3 from 0 to 1

1’s complement, negative values represent by complement

each bit of corresponding positive number

2’s complement obtain by adding 1 to 1’s complement of

number.

 drawback: +0 and -0 has distinct representation in sign and

magnitude and 1’s complement

2’s complement system leads to most efficient way to carry

out addition and subtraction
Addition and subtraction of signed integer

The rules governing addition and subtraction of n-bit signed numbers using the 2’scomplement
representation system may be stated as follows:

To add two numbers, add their n-bit representations, ignoring the carry-out bit from the most significant
bit (MSB) position. The sum will be the algebraically correct value in 2’s-complement representation if the
actual result is in the range -2n-1 through +2n-1-1

To subtract two numbers X and Y , to perform X − Y , form the 2’s-complement of Y , then add it to X
using the add rule. Again, the result will be the algebraically correct value in 2’s-complement representation
if the actual result is in the range -2n-1 through +2n-1-1
Addition and subtraction using 2’s complement
Overflow in integer arithmetic

 When the actual result of an arithmetic operation is outside the representable

range, an arithmetic overflow has occurred.

When adding unsigned numbers, a carry-out of 1 from the most significant bit
position indicates that an overflow has occurred.

If two numbers are added, and they are both positive or both negative, then
overflow occurs if and only if the result has the opposite sign.
MODULE- 2- LECTURE 3

MULTIPLICATION
REPRESENTATION OF NUMBER

 Binary representation of 41.6875 is 101001.1011

 Therefore any real number can be converted to binary number system

 There are two schemes to represent real number :

 Fixed-point representation

 Floating-point representation
FIXED-POINT REPRESENTATION

 Binary representation of 41.6875 is 101001.1011

 To store this number, we have to store two information,

-- the part before decimal point and
-- the part after decimal point.

 This is known as fixed-point representation where the position of decimal point is fixed
and number of bits before and after decimal point are also predefined.

 If we use 16 bits before decimal point and 8 bits after decimal point, in signed magnitude
form, the range is  216  1 to  216  1 and the precision is 2 8

One bit is required for sign information, so the total size of the number is 25 bits

 ( 1(sign) + 16(before decimal point) + 8(after decimal point)).

FLOATING-POINT REPRESENTATION

 In this representation, numbers are represented by a mantissa comprising the significant digits
and an exponent part of Radix R. The format is:

Mantissa  R exp onent

 Numbers are often normalized, such that the decimal point is placed to the right of the first non
zero digit.

 For example, the decimal number,

5236 is equivalent to 5.236  10 3

 To store this number in floating point representation, we store 5236 in mantissa part and 3 in
exponent part
IEEE standard floating point format:

 IEEE has proposed two standard for representing floating-point number:

-Single precision
-l Double precision

Single Precision: Double Precision:

64 bits
32 bits
S E’ M
S E’ M
S: sign bit: 0 denoted + and 1 denotes -
S: sign bit: 0 denoted + and 1 denotes - E: 11-bit excess -1023 exponent
E: 8-bit excess -127 exponent M: 52-bit mantissa
M: 23-bit mantissa

E ' 127
 1.M  2 E '1023
 1.M  2
 Arithmetic operations with Floating point numbers are more complicated
than arithmetic operations with fixed point numbers

 Execution takes longer and requires more complex hardware

Many computers and all electronic calculators have built in capability of

floating point arithmetic operations

 Computers do not have hardware for floating point computations

MULTIPLICATION- UNSIGNED
 Multiplication is a complex operation as compared to addition and
subtraction

 It can perform in hardware or software.

 Several algorithms are used in various computers.

 First we see the simpler problem of multiplying two unsigned integers,

Process involves generation of partial products, one for each digit in the
Multiplier and each successive partial product is shifted one position to the
left.

 When the multiplier bit is 0, the partial product is 0. When the multiplier is 1,
the partial product is the multiplicand

 Final product is produced by summing the partial products.

 The multiplication of two n-bit binary integers results in a product of upto 2n

bits in length.
MULTIPLIER ARCHITECTURE

 we can perform a running addition on the

partial products rather than waiting until the
end.

 Eliminates the need for storage of all the

partial products; fewer registers are needed.

Save some time on the generation of partial

products

 For each 1 on the multiplier, an add and a shift

operation are required; but for each 0, only a
shift is required
MULTILPLICATION OPERATION STEPS
 The multiplier and multiplicand are loaded into two registers
(Q and M).

Multiplicand
Multiplier
 A register, is also needed and is initially set to 0.

 1-bit C register, initialized to 0, holds a potential carry bit

resulting from addition.

 Bit 0 of multiplier operand (Q0 of Q register is checked)

 If bit Q0 is 1, then multiplicand are added to A register and

results are stored here.

 All bits of C, A,and Q registers are shifted to right one bit, so

that C bit goes into An-1, A0 goes into Qn-1 and Q0 is lost

 If bit 0, no addition operation only shift operations is carried

out.

This process is repeated for each bit of the original multiplier.

Resulting 2n-bit product is contained in the A and Q registers

FLOWCHART FOR UNSIGNED MULTIPLICATION
MODULE- 2- LECTURE 4

SIGNED MULTIPLICATION
BOOTH’S ALGORITHM
 Algorithm used for signed number multiplication is called Booth’s algorithm
which generates 2n-bit product .

 Treats both positive and negative numbers uniformly.

SIGNED MULTILPLICATION OPERATION STEPS
Initially set A and Q-1 = 0

 N bit adder
-N bit adder add two inputs, A register and M(multiplicand)

-For addition, A= A+M

Add’/sub =0,Cin=0, multiplicand directly applied as input to n bit adder and add with A register

-For subtraction, A= A-M

Add’/sub =1,Cin=1, multiplicand is complemented and applied as input to n bit adder and finally 2’s
complement of multiplicand is added to A register

 Shift, add and subtract control logic : scans Q0 and Q-1 bits one at a time
-If (Q0 and Q-1 =1-1 or 0-0 ), shift operations occur from (A to Q-1) registers, no add/subtract(Enable=0)

-If (Q0 and Q-1 =0-1), addition operation , A=A+M (Add/subtract enable=1)

-If (Q0 and Q-1 =1-0), subtraction operation , A=A-M (Add/subtract enable=1)

-After addtion and subtraction, right shift occurs from Left most bit of A(An-1) and also it keeps An-1 bit
in A register.

- It is also known as arithmetic shift, since it preserves the sign bit.

EXAMPLES FOR BOOTH’S ALGORITHM
Both Positive
Multiplicand=7 QO Q-1 Add’/sub Add/sub shift
Multiplier=3
enable
0 0 X 0 1
0 1 0 1 (A+M) 1
1 0 1 1 (A-M) 1
1 1 X 0 1

Booth’s algorithm (3X7)=21

Booth’s algorithm (5X-4)=-20

FLOWCHART FOR SIGNED MULTIPLICATION
ASSIGNMENT

Compute -5 x -4 using Booth’s algorithm

MODULE- 2- LECTURE 5

ARRAY MULTIPLIER
ARRAY MULTIPLIER

ARRAY IMPLEEMNTATION FOR UNSIGNED OPERANDS

Binary multiplication of unsigned operands can be implemented in logic array.

Main component in each cell is a full adder, FA.

AND gate in each cell determines whether a multiplicand bit, mj , is added to the incoming partial-
product bit, based on the value of the multiplier bit, qi =0 ≤ i ≤ 3,

if qi=1 ,adds the multiplicand (appropriately shifted) to the incoming partial product, PPi, to generate the
outgoing partial product, PP(i + 1),.

If qi = 0, PPi is passed vertically downward unchanged.

Multiplicand shifted left per row in diagonally

Row by row addition in array circuit differ from manual addition (column by column )

Critical path and performance is identified by two gate delays from the inputs to the outputs of a full-
adder block, FA.

 Total of 6(n − 1) − 1 gate delays, including the initial AND gate delay in all cells, for an n × n array.
MODULE- 2- LECTURE 6

RESTORING AND NON-RESTORING DIVISION

DIVISION

Examine bits of dividend from left to right,

13 00001101 Quotient
until set of bits represents number >= 11
divisor, referred to as divisor able divide the
number. Divisor 1011 10010011 Dividend
143
1011
Until this condition occurs 0’s placed in
quotient from left to right. When condition Partial Remainder1 001110
satisfied place 1’s in quotient and diviosr
subtract from dividend 101 1

Result is reffered to as partial remainder

Partial Remainder 2 001 1 11
1 0 1 1
Repeat the steps until all bits of dividend
are brought down and result is less than 4
divisor.
Remainder 1 0 0

Each repetiton cycle, additional bits from

dividend are brought down to partial
remainder
HARDWARE TO IMPLEMENT BINARY DIVISION

Hardware consists of n+1 binary adder, shift,

add and control logic and registers A,Q and B.

Divisior and dividend are loaded into register B

and Q.

Register A initially set to Zero

Division operation is carried out

After division operation is complete, n bit

quotient stored in register Q and remainder in
Register A
RESTORING DIVISION
n= 4 Count =n =n-1
Q (Dividend)=1010; B(Divisor)=0011
Decimal 10 Decimal 3
A=00000 B= 00011 -B=11101

A
 Shift A and Q left one binary position

 Subtract B(divisor) from A and place

result back in A (A=A- B= A+(-B))
A

 If sign bit of A is 1, Set Q0 =0 and

restore A.
No Restore 00010

If sign bit A is 0, set Q0=1

1
 Repeat the steps n times
3
FLOWCHART FOR RESTORING DIVISION OPERATION
NON RESTORING DIVISION

After subtraction operation in restoring algorithm,

- If sign bit of A is 1, Set Q0 =0 and restore A.

- If sign bit A is 0, set Q0=1

After subtraction operation in Non restoring algorithm,

-If sign bit of A is 1, shift A and Q left one position and add divisor to A,
Set Q0 =0.

-If sign bit of A is 0, shift A and Q left one position and subtract divisor from A, Set Q0 =1

Repeat steps 1 and 2 for n times

Q (Dividend)=1010; B(Divisor)=0011 B= 00011 -B=11101
CPU PERFORMANCE
PERFORMANCE

 Performance is an important attribute of a computer.

If a pc is working with high speed normally we will compare that with other PC by
speed ,cost and operation etc.

 Computer user expects to reduce the start and execution time of process.

 Execution time is also referred to as response time.

Reduction in response time increases the throughput.

Throughput is total amount of workdone in a given time.

 Performance of computer is based on throughput so it is reciprocal to execution

time.
RELATIVE PERFORMANCE

 Relate performance and execution time for Computer X.

PerformanceX= 1/execution time X

 Example:

- If Computer system named as A and B,

performance A> performance B

1/Execution timeA > 1/Execution timeB

Execution time B > Execution time A

 Hence, the execution time on B is longer than A. Therefore you say A is faster than Y

Performance A ExecutiontimeB
 n
PerfromanceB Executiontime A
EXAMPLES

 If computer A runs a program in 15 seconds and computer B runs the same

program in 30 seconds, how much faster is A than B?
MEASURING PERFORMANCE

Time is the measure of computer performance

Time can defined in different ways depending on what we count.

CPU execution time or CPU time, is the time the CPU spends computing for this task and does not
include time spent waiting for I/O or running other programs.

 CPU time can be further divided into

-user CPU time,
-system CPU time.

 the CPU time spent in the program, called user CPU time

CPU time spent in the operating system performing tasks on behalf of the program, called
System CPU time

 CPU performance is refer to as user CPU time

COMPUTER CLOCKS

 All computers are constructed in such a way that events in hardware synchronized using
clocks

 The discrete time intervals called clock cycles or clock periods

 The clock cycle time is the amount of time for one clock period to elapse

 clock cycle time in seconds is the inverse of clock rate (in HZ)

 For example if a computer have a clock cycle time of 5 ns then the clock rate will be 200
MHz.
CPU PERFORMANCE AND ITS FACTORS

 CPU execution time is measured in terms of clock cycles. It is measured as

clock cycles per second.

 Simple formula relate most basic metrics (clock cycles and clock cycles time)

CPU execution time for program = CPU clock cycles for a program x clock
cycle time

or CPU execution time =CPU clock cycles /clock rate

 Hence, hardware designer can improve the performance by reducing number

of clock cycles for program and increase the clock cycle time
INSTRUCTION PERFORMANCE
CPU execution time must depend on number of instructions in a program.

 CPU clock cycles = (instruction for a program) x (average clock cycle/instruction)

CPU clock cycles = instruction count x CPI

CPI (clock cycles per instruction) is average number of clock cycles required for each instruction
takes to execute

CPI = CPU clock cycles/ instruction count

 Performance equation in terms of instruction count, CPI and clock cycle time:

CPU execution time: Instruction count x CPI x clock cycle time

CPU execution time: Instruction count x CPI / clock rate

 Therefore these formulas have three key factors that affect CPU performance and it will be useful to
compare different implementations
OTHER PERFORMANCE MEASURES

Alternative to time is MIPS(million instructions per second)

 A measurement of program execution speed based on the number of millions of

instructions.

MIPS= Instruction count/Execution time X10^6

 MIPS is inversely proportional to execution time. Hence faster computers have higher
MIPS rating

 Relation between three factors MIPS, Clock rate and CPI

Instructioncount Clockrate
MIPS  
Instructioncount  CPI CPI  10 6
 10 6

Clockrate
THANK YOU