UNIT – 2

Unit-02/Lecture-01

Control Unit Organization

·         Hardwired control unit

·          Micro and nano programmed control unit

·         Control Memory

·          Address Sequencing

·         Micro Instruction formats

·         Micro program sequencer

·         Microprogramming

Arithmetic and Logic Unit

·       Arithmetic Processor

·       Addition

·        Subtraction

·       Multiplication and division

·        Floating point and decimal arithmetic and arithmetic units

·       Design of arithmetic unit.

        Hardwired control unit

·            In the hardware implementation the control unit is essentially a combinational circuit or sequential circuit. The key inputs are instruction register, the clock flags & control bus signals. Each of these individual bits typically has some meaning.  

·           The other inputs are not directly useful to control unit.

·           The control unit makes use of op-code perform different action for different instruction.

·           This function can be performed by a decoder which takes & encoding inputs & produces single output.

·           The clock portion of the control unit issues a representative sequence of pulses.

·           For each instruction, the control unit causes the CPU to execute a sequence of steps correctly. In reality, there must be control signals to assert lines on various digital components to make things happen.

·           For example, when we perform an Add instruction in assembly language, we assume the addition takes place because the control signals for the ALU are set to "add" and the result is put into the AC. The ALU has various control lines that determine which operation to perform.

·           The question we need to answer is, "How do these control lines actually become asserted?"

·           We can take one of two approaches to ensure control lines are set properly. The first approach is to physically connect all of the control lines to the actual machine instructions. The instructions are divided up into fields, and different bits in the instruction are combined through various digital logic components to drive the control lines. This is called hardwired control, and is illustrated in figure

Fig: Hardwired Control Organization

·         The steps required for performing an arithmetic or logical operation, for fetching a word from memory, or for storing a word in memory.

·         The  control  unit is  implemented  using  hardware  (for  example:  NAND gates, flip-flops, and counters).We need a special digital circuit that uses , as inputs, the bits from the Opcode field in our instructions, bits from the flag (or status) register, signals from the bus, and signals from the clock. It should produce, as outputs, the control signals to drive the various components in the computer.

·          The advantage of hardwired control is that is very fast. The disadvantage is that the instruction set and the control logic are directly tied together by special circuits that are complex and difficult to design or modify. If someone designs a hardwired computer and later decides to extend the instruction set, the physical components in the computer must be changed. This is prohibitively expensive, because not only must new chips be fabricated but also the old ones must be located and replaced.

·         Performed sequentially changing from one step to another.

·         In the past, hardwired control unit is very difficult to design hence its engineering cost is very high. Presently, the emphasis of computer design is the performance therefore hardwired design is the choice.  Also the CAD tools for logic design have improved to the point that a complex design can be mostly automated. Therefore almost all processors of today use hardwired control unit.

·         Starting with a behavioral description of the control unit, the state diagram of micro-operations is constructed.  Most states are simply driven by clock and only transition to the next state.  Some states branch to different states depends on conditions such as testing conditional codes or decoding the instruction. 

·          CISC also can be implemented by using hardwired control:

In the above sense, the micro programmed control is not always necessary to implement CISC machines. Hardwired control also can be used for implementing sophisticated CISC machines. The bases of this opinion are as follows:

1.    The same field configuration (state assignment) can be used for both of these two types of    control. This is clear because of the above identification.

Fig: Control unit with decoded input

Unit-02/Lecture-02

Micro programmed control unit

·                          Microprogramming is a second alternative for designing control unit of digital computer (uses software for control).

·                           A control unit whose binary control variables are stored in memory is called a micro programmed control unit. The control variables at any given time can be represented by a string of 1's and 0's called a control word (which can be programmed to perform various operations on the component of the system). Each word in control memory contains within it a microinstruction. The microinstruction specifies one or more microoperatiotins for the system. A sequence of microinstructions constitutes a micro program.

·                          A more advanced development known as dynamic microprogramming permits a micro program to be loaded initially from an auxiliary memory such as a magnetic disk. Control units that use dynamic microprogramming employ a writable control memory; this type of memory can be used for writing (to change the micro program) but is used mostly for reading.

·                          The general configuration of a micro programmed control unit is demonstrated in the block diagram of Figure. The control memory is assumed to be a ROM, within which all control information is permanently stored.

Fig: Micro programmed Control Organization

·          The main advantages of the micro programmed control are the fact that once the hardware configuration is established; there should be no need for further hardware or wiring changes. If we want to establish are different control sequence for the system, all we need to do is specify different set microinstructions for control memory. The hardware configuration should not be changed for different operations; the only thing that must be changed is the micro program residing in control memory.

·          All microroutines corresponding to the machine instructions are stored in the control store.

·          The control unit generates the sequence of control signals for a certain machine instruction by reading from the control store the CWs of the micro routine corresponding to the respective instruction.

·          In micro programmed control unit , the logic of the control unit is specified by a micro program. A Micro program consists of a sequence of instructions in a microprogramming language. These are very instructions that specify microoperations.

·         A microprogrammed control unit is a relatively simple logic circuit that is capable of:

 (1) Sequencing through microinstructions

 (2) Generating control signals to execute each microinstruction.

·         The concept of microprogram is similar to computer program. In computer program the complete instructions of the program is stored in main memory and during execution it fetches the instructions from main memory one after another.

·         The sequence of instruction fetch is controlled by program counter (PC).

·         Microprogram are stored in microprogram memory and the execution is controlled by microprogram counter (PC ) .

·         Microprogram consists of microinstructions which are nothing but the strings of 0’s and 1’s . In a particular instance ,we read the contents of one location of microprogram memory , which is nothing but a microinstruction . Each output line ( data line )  of microprogram memory corresponds to one control signal. If the  contents of the memory cell is ) , it indicates that the signal is to generated and if the contents of memory cell is 1 , it indicates that generate that control signal at that instant of time.

·           First let me define the different terminologies that are related to microprogrammed control unit.

ü  Control Word (CW) :

—           Control word is defined as a word whose individual bits represent the various control signal. Therefore each of the control steps in the control sequence of an instruction defines a unique combination of 0s and 1s in the CW.

—           A sequence of control words ( CWs ) corresponding to the control sequence of a machine instruction constitutes the microprogram for that instruction.

—           The individual control words in this microprogram are referred to as microinstructions.

—           The microprograms corresponding to the instruction set of a computer are stored ina aspecial memory which will be referred to as the microprogram memory. The control words related to an instruction are stored in microprogram memory.

—           The control unit can generate the control signals for any instruction by sequencially reading the CWs of the corresponding microprogram from the microprogram memory.

·          To read the control word sequentially from the microprogram memory a microprogram counter (PC ) is needed.

·          The basic organization of a microprogrammed control unit is shown in the figure.

Fig: Micro programmed Control

·          The “starting address generator “  block is responsible for loading the starting address of the microprogram into the PC everytime a new instruction is loaded in the IR.

·          The PC is then automatically incremented the clock, and it reads the successive microinstruction from memory . Each microinstruction basically provides the required control signal at that time step. The microprogram counter ensures that the control signal will be delivered to the various parts of the CPU in correct sequence.

·          We have some instructions whose execution depends on the status of condition codes and status flag , as for example , the branch instruction. During branch instruction execution it is required to take the decision between the alternative action.

·          To handle such type of instructions with microprogrammed control , the design of control unit is based on the concept of  conditional branching  in the microprogram. For that it is required to include some conditional branch microinstructions.

·          In conditional microinstructions , it is required to specify the address of the microprogram memory to which the control must direct. It is known as branch address. Apart from branch address , these microinstructions can specify which of the states flags ,  condition codes , or possibly , bits of the instruction register should be checked as a condition for branching to take place.

·          To support microprogram branching, the organization of control unit should be modified to accommodate the branching decision. To generate the branch address, it is required to know the status of the condition codes and status flag.

·          To generate the starting address, we need the instruction which is present in IR. But for branch address generation we have to check the content of condition codes and status flag.

·          In microprogrammed controlled control unit, a common microprogram is used to fetch the instruction. This microprogram is stored in a specific location and execution of each instruction start from that memory location.

Unit-02/Lecture-03

Nano programmed control unit

·           It is an extension of micro- programmed control unit.

·           An alternate strategy to generate control signals.

·           Having the concept of a secondary control memory.

·           A microinstruction is in primary control-store memory, it then has the control signals generated for each microinstruction using a secondary control store memory.

·           The output word from the secondary memory is called nano instruction.

·           The microprogram counter contains The address of the next microinstruction to be executed.

·           The micro-programmed memory contains all the microinstructions.

·           Each machine level instruction is interpreted by one or more microinstructions.

·           If there are n machine-level instructions and each instruction is interpreted by m microinstructions, the size of the microprogram ROM is n. m lines.

·           The microinstruction register holds the bits of the current microinstruction. If this is P bitswide, the total size of the microprogram memory in bits is n.m.p.

·           This structure requires a lot of fast microinstruction storage. For example, if there are 512machine-level instructions, and each instruction is interpreted by four 200-bit microinstructions, the size of the ROM is 512 x 4 x200 = 409,600 bits (51,200 bytes)

·           Nanoprogramming reduces the number of control bits require to interpret an instruction set.

·           In, most microprogrammed processors, an instruction fetched from memory is interpreted by a micro program stored in a single control memory CM. In some microprogrammed processors, the micro instructions are not directly used by the decoder to generate control signals.

·             They use secondcontrol memory called a nano control memory (nCM).So they are two levels of control memories, a higher level control memories is known asmicro control memory ( µ CM) and lower level control memories is known as nano control memory (nCM). The µCM stores micro instructions whereas nCM stores nano instructions.

·            2 LEVELS  OF CONTROL MEMORY

—     Microcontrolled memory- higher level

—     Nanocontrol memory(Nanoinstructions)-lower level

Fig: Two Level control store organization for nano programming

Fig. Nano Programmed control unit Organization

·         Advantages of nano programming

1.       Reduces total size of required memory In two level control design technique, the total control memory size S2 can be calculated as

S2= Hm x Wm+ Hn x Wn

Where Hm represents the number

Wm represents the size of word in

Hn represents the number of word

Wn represents the size of word in the low level Memory

Usually, the microprograms are vertically organized so Hm is large and Wm is small. In nanoprogramming .we have a highly parallel horizontal organization, which makes Wn large and Hn is small. This gives the compatible size for single level control unit as S1= Hm x Wn which is quiet larger than S2. the reduced sizeof control memory reduces the total chip area.

2.       Greater design flexibility Because of two level memories organization more design flexibility existsbetween instructions and hardware.

·         Disadvantage of nano programming

The main disadvantage of the two level memory approaches is the loss of speed due to the extra memory access required for nano control memory.

Unit-02/Lecture-04

Micro-operation.

The operation of computer is executing a program consists of sequence of instruction cycle. Each instruction cycle is made up off no of smaller units, one subdivision that we found convenient is fetch, indirect execute and interrupt with only fetch and execute cycle always occurring. Each of the smaller cycle involves series of steps, each of which involve processor register. Fig depicts the relationship among the various concepts

Fig. Constituent element of program execution

Fetch cycle: It causes an instruction to be fetched form memory. Fetch cycle actually consist of three steps and four micro operations.

·         t1: MAR à (PC)

·         t2: MBR àMemory

o   PC àPC+1

·         t3: IR à(MBR) 

·         The notion (t1, t2, t3) represent successive time units.

Indirect cycle: once an instruction is fetch, the next step is to fetch source operand.

·         t1: MAR ← (IR (address))

·         t2: MBR ←Memory

·         t3: IR(address) à(MBR(address)

Interrupt cycle: At the completion of execution cycle a test is made to determine weather any enabled interrupts have occur if so the interrupt cycle occurs.

·         t1: MBR à (PC)

·         t2: MARàsave address

o   PC àRoutine address

·         t3: Memory à(MBR)

Execute cycle: The fetch indirect and interrupt cycle are simple and predictable. Each involve fix sequence of micro operation. This is not true of the execute cycle for a machine with N different upcodes, there are N different sequence of micro operation that can occur. Consider ADD instruction.

ADD R1,X

This adds the content of location X to register R1.

·         t1: MAR à (IR address)

·         t2: MBR àMemory

·         t3: R1 à(R1)+(MBR)

The two basic tasks performed by micro programmed control unit are as follows:

- Micro instruction sequencing:- Get then next micro instruction from the control memory.

- Micro instruction execution:- Generates the control signals needed to execute the micro instruction.

Microinstruction sequencing:

Based on the current micro operation, condition flags and content of instruction register, control memory address must be generated for next micro instruction. A wide variety of techniques have been used. We can group them into three general categories based on the format of address information in the micro instruction:

- Two address field.

- Single address field.

- Variable format.

Fig. Branch control logic, two address fields

Microinstruction Format

Microinstructions are a symbolic representation of bit patterns.  In this way, they are similar to assembly code.  In both cases, the use of mnemonics makes the creation of bit patterns much easier.

Microinstructions

1.                                have fixed fields

2.                                use mnemonic identifiers to represent bit patterns, and

3.                                Are very close to hardware usually, every field represents a group of control signals.

The microinstruction format consists of 128 bits and these bits are broken down into 30 functional fields , each of these fields consists of one or  more bits and they are grouped into five major categories:

 1) Control of board

 2) 8847 floating- point and integer processor or chip

 3) 8832 registered ALU

 4) 8818 microsequencer

 5) WCS data field.

     Control operations in the microinstruction include:

  - Selecting condition codes for sequencer control . The first bit of field 1 indicates whether the condition flag is to be set to 1 or 0,and the remaining  4 bits indicate which flag is to be set.

  - Sending an I/O request to the PC/AT.

  - Enabling local data memory read/write operations.

  - Determining the unit driving the system Y bus. One of the four devices attached to the bus is selected.

Each microinstruction is a 36-bit word whose bits drive the control lines of the CPU. The basic microinstruction format is given here:

xxxxxxxxx|xxx|xxxxxxxx|xxxxxxxxx|xxx|xxxx

Next Addr|JJJ|SSFFEEII|HOTCLSPMM|WRF|B

         |MAA|LR01NNNN| POPVPCDA|REE|Bus

         |PMM|LA  ABVC| CSP   RR|IAT|

         |CNZ|81    A |         |TDC|

         |   |        |         |E H|

                ^^                   ^^^^

                00 AND               0000 MDR

                01 OR                0001 PC

                10 NOT               0010 MBR

                11 ADD               0011 MBRU

                                     0100 SP

                                     0101 LV

                                     0110 CPP

                                     0111 TOS

                                     1000 OPC

In the descriptions below, bit numbering begins at the left with the most significant bit.

Next Addr Control Bits (bits 1-9)

This field contains the address of the next microinstruction. It is copied to the MPC register during the execution of the current microinstruction. The value in the MPC may be altered by the jump control bits described next.

Jump Control Bits (bits 10-12)

The jump control bits control branching within the microprogram.

JMPC (bit 10)

If this bit is set, the current value of the MBR register is bit-wise ORed with the 8 low-order bits of the MPC (which came from the next address field described above). Often, the next address field is set to zero when JMPC is set to one. In that case, the value in the MBR register is the address of the next microinstruction. For example, when executing a machine language program, the opcode of an instruction is the address of the block of code within the microprogram that executes that instruction. The microprogram performs a JMPC to this address when the opcode is loaded into the MBR.

JAMN (bit 11)

If this bit is set, the value of the N register is ORed with the high order bit of the MPC register. Typically, the high order bit of the value in the next address field is zero. In that case, JAMN allows a conditional jump when the value generated by the ALU is negative. If the high order bit of the next address is already one, then the value of the JAMN bit is irrelevant.

JAMZ (bit 12)

If this bit is set, the value of the Z register is ORed with the high order bit of the MPC register. Typically, the high order bit of the value in the next address field is zero. In that case, JAMZ allows a conditional jump when the value generated by the ALU is zero. If the high order bit of the next address is already one, then the value of the JAMZ bit is irrelevant.

Note: Any combination of the JMPC, JAMN, and JAMZ bits may be set at the same time.

ALU/Shifter Control Bits (bits 13-20)

These bits determine the operations performed by the arithmetic logic unit and the shift register.

SLL8 (bit 13)

If set, the value generated by the ALU will be shifted left 8 bits by the shifter with zero fill (a logic shift).

SRA1 (bit 14)

If set, the value generated by the ALU will be shifted right one bit with sign extension (arithmetic shift). Sign extension means that the high order bit prior to the shift will be copied into the vacated high order bit following the shift right.

Note: SLL8 and SRA1 should not both be set at the same time (it would make no sense). In the simulator, if both are set at the same time then the left logic shift will be performed first and the arithmetic right shift applied to the result.

F0, F1 (bits 15-16)

Determines the operation performed by the ALU:

00 => AND
01 => OR
10 => NOT B
11 = > ADD

ENA (bit 17)

If set, the A input to the ALU is enabled. Otherwise the A input is disabled; effectively setting the A input to zero.

ENB (bit 18)

If set, the B input to the ALU is enabled. Otherwise the B input is disabled; effectively setting the B input to zero.

INVA (bit 19)

If set, the value of the A input is bit-wise inverted.

Note: Clearing ENA and setting INVA has the effect of setting every bit in the A input to one which is the two's complement representation of -1.

INC (bit 20)

If this bit is set and the ALU function is ADD the output of the ALU will be A+B+1. If the ALU function is anything other than ADD then setting this bit has no effect.

C-Bus Control Bits (bits 21-29)

These nine bits determine which register(s) receive data from the C bus during the execution of a microinstruction. Any number of these bits may be set in any given microinstruction. The bits (listed in order) correspond to the H, OPC, TOS, CPP, LV, SP, PC, MDR, and MAR registers. If a given bit is set then the corresponding register is loaded from the C-bus; otherwise it is not.

Memory Access Control Bits (bits 30-32)

These bits control memory reads and writes.

WRITE (bit 30)

If set, the value stored in the four-byte MDR register is written to the word address stored in the MAR register. The byte address is four times the word address stored in the MAR register. The write operation is complete at the end of the next instruction.

READ (bit 31)

If set, the MDR register is loaded with the four-byte value found at the word address stored in the MAR register. The byte address is four times the word address stored in the MAR register. The read operation is complete at the end of the next instruction.

FETCH (bit 32)

If set, the MBR register is loaded with the byte value found at the address in the PC register. The fetch operation is complete at the end of the next instruction.

Note: It would make no sense to set both the WRITE and READ bits at the same time. If this is done, the simulator performs the READ operation.

Note: A fetch operation may occur simultaneously with a READ or WRITE operation. In effect, we are simulating access to cache memory in which the data and instructions are located in two separate caches.

B-Bus Control Bits (bits 33-36)

These four bits serve as input to a 4 to 16 decoder and select which register's value is gated to the B bus:

0 => MDR
1 => PC
2 => MBR (with sign extension)
3 => MBR (with zero fill)
4 => SP
5 => LV
6 => CPP
7 => TOS
8 => OPC
9-15 =>none

A multiplexer is provided that serves as destination for both address field plus instruction register based on the address selection input the multiplexer transmits the op-code or one of the two address to the control address register (CAR). CAR is subsequently decoded to produce the next micro instruction address.

Fig: Branch Control logic single address field

Unit-02/Lecture-05

Micro instruction execution:

The effect of execution of micro instruction is to generate control signal. Some of these signals control points internal to the processor. The remaining signal goes to the external control bus.

Fig. Control unit organization

The sequencing logic module generates a address of next micro instruction using as inputs instruction register flags, CAR (for implementing), control buffer register. The module is driven by clock that determines the timing of micro instruction cycle. The control logic module generates the control signal as a function of some of the bits in micro instruction.

Difference between Hardwired Control and Micro programmed Control

Unit-02/Lecture-06

   Arithmetic and Logic Unit

·      The ALU is the core of the computer - it performs arithmetic and logic operations on data that not only realize the goals of various applications (e.g., scientific and engineering programs), but also manipulate addresses (e.g., pointer arithmetic).

ALU is responsible to perform the operation in the computer.

The basic operations are implemented in hardware level. ALU is having collection of two types of operations:

·      Arithmetic operations

·      Logical operations

·         Consider an ALU having 4 arithmetic operations and 4 logical operations.

·         To identify any one of these four logical operations or four arithmetic operations, two control lines are needed. Also to identify the any one of these two groups- arithmetic or logical, another control line is needed. So, with the help of three control lines, any one of these eight operations can be identified.

·         Consider an ALU is having four arithmetic operations. Addition, subtraction, multiplication and division. Also consider that the ALU is having four logical operations: OR, AND, NOT & EX-OR.

·         We need three control lines to identify any one of these operations. The input combination of these control lines are shown below:

Control line  is used to identify the group: logical or arithmetic, i.e.

: Arithmetic operation: logical operation.

Control lines  and  are used to identify any one of the four operations in a group. One possible combination is given here.

·         A  decode is used is used to decode the instruction. The block diagram of the ALU is shown in the figure.

The ALU has got two input registers named as A and B and one output storage register, named as C. If performs the operation as:

·         The input data are stored in A and B, and according to the operation specified in the control lines, the ALU perform the operation and put the result in register C.

·         As for example, if the contents of controls lines are, 000, then the operation decoder enables the addition operation and in terms it activates the adder circuit and the addition operation is performed on the data that are available in storage register A and B. After the completion of the operation, the result is stored in register C.

·         We should have some hardware implementations for basic operations. These basic operations can be used to implement some complicated operations which are not feasible to implement directly in hardware.

·         These are several logic gates exists in digital logic circuit. These logic gates can be used to implement the logical operation. Some of the common logic gates are mentioned here.

·       AND gate: The output is high if both the 0-inputs are high.

·       OR gate: The output is high if any one of the inputs is high.

·       EX-OR gate: The output is high if either of the input is high.

·           If we want to construct a circuit which will perform the AND operation on two 4-bit number, the implementation of the 4-bit AND operation is shown in the figure.

·                        An arithmetic-logic unit (ALU) is the part of a computer processor (CPU) that carries out arithmetic and logic operations on the operands in computer instruction words. In some processors, the ALU is divided into two units, an arithmetic unit (AU) and a logic unit (LU). Some processors contain more than one AU - for example, one for fixed-point operations and another for floating-point operations. (In personal computers floating point operations are sometimes done by a floating point unit on a separate chip called a numeric coprocessor).

·                        The ALU has direct input and output access to the processor controller, main memory (random access memory or RAM in a personal computer), and input/output devices. Inputs and outputs flow along an electronic path that is called a bus.

·          Performs arithmetic and logic operations on data.

·          Everything that we think of as “computing”.

·          Everything else in the computer is there to service this unit.

·          All ALUs handle integers.

·          Some may handle floating point (real) numbers.

·          May be separate FPU (math co-processor).

·          FPU may be on separate chip (486DX +)

Fig. A symbolic representation of an ALU and its input and output signals (indicated by arrows pointing into or out of the ALU, respectively)

·         An ALU performs basic arithmetic and logic operations. Examples of arithmetic operations are addition, subtraction, multiplication, and division. Examples of logic operations are comparisons of values such as NOT, AND, and OR.

·         All information in a computer is stored and manipulated in the form of binary numbers, i.e. 0 and 1. Transistor switches are used to manipulate binary numbers, since there are only two possible states of a switch: open or closed. An open transistor, through which there is no current, represents a 0. A closed transistor, through which there is a current, represents a 1. Operations can be accomplished by connecting multiple transistors. One transistor can be used to control a second one, in effect turning the transistor switch on or off depending on the state of the second transistor. This is referred to as a gate, because the arrangement can be used to allow or stop a current.

·         The simplest type of operation is a NOT gate. This uses only a single transistor. It uses a single input and produces a single output, which is always the opposite of the input. The figure below shows the logic of the NOT gate.

Fig: NOT gate

·         Other gates consist of multiple transistors and use two inputs. The OR gate results in a 1 if either the first or the second input is a 1. The OR gate only results in a 0 if both inputs are 0. The figure below shows the logic of the OR gate.

How an OR gate processes binary data

·         The AND gate results in a 1 only if both the first and second input are 1s. The figure below shows the logic of the AND gate.

·         The XOR gate results in a 0 if both the inputs are 0 or if both are 1. Otherwise, the result is a 1. The figure below shows the logic of the XOR gate.

Arithmetic processors

They are the core part of system to perform vector execution instructed by control vector processor. Usually, an array processor is formed by a collection of N arithmetic-logic units and a collection of M memory units by means of networks.

Characteristics of this machine

The characteristics of this machine are as follows:

INDEX[i]

ACC[k]   <- k^th processor

This refers to the k^th arithmetic processor, not the k^th register within a CPU chip. Here, we are talking about multi-processor, not uni-processor.

Unit-02/Lecture-07

Addition

·           Notice how the carry moves up the word, the same as in decimal arithmetic. The simplest form of adder is known as a ripple carry adder. Arithmetic circuits are usually formed from two simple types of blocks: the half adder and the full adder. The half adder takes in two inputs and generates two outputs: the modulo two sum of the input bits, and the carry.

Fig. Half-Adder Logic Circuit

·           Binary adder is used to add two binary numbers.

·           In general, the adder circuit needs two binary inputs and two binary outputs. The input variables designate the augends and addend bits; The output variables produce the sum and carry.

·           The binary addition operation of single bit is shown in the truth table

The simplified sum of products expressions are

The circuit implementation is

This circuit can not handle the carry input, so it is termed as half adder.

·      A full adder is a combinational circuit that forms the arithmetic sum of three bits. It consists of three inputs and two outputs.

·      Two of the input variables, denoted by x and y, represent the two bits to be added. The third input Z, represents the carry from the previous lower position.

Fig. Full-Adder Logic Circuit

The two outputs are designated by the symbols S for sum and C for carry.

The truth table of the full adder is given in the table.

The simplified expression for S and C are

We may rearrange these two expressions as follows:

The circuit diagram full adder is shown in the figure.

This single bit full adder block is used to make n-bit full adder.

To demonstrate the binary addition of four bit numbers, let us consider a specific example.

Consider two binary numbers

         A=1 0 0 1        B= 0 0 1 1

To get the four bit adder, we have to use 4 full adder block. The carry output the lower bit is used as a carry input to the next higher bit.

Subtraction

·           We could build a completely separate component, a 32-bit subtractor, once we work out how to build a 1-bit subtractor.

·           Fortunately, we can simplify things a bit.

·           According to the rules of maths: 3-2=3+(-2).

·           If we could negate one of the inputs, we could use the existing 32-bit full adder.

·           We have already seen two algorithms to negate a twos complement binary integer.

·           One of them works as follows: invert every bit in the number, then add 1.

·           Putting all of the above together, we can say:

                                          A - B = A + (-B) = A + ~B + 1

·           Inverting every bit is easy: we can use a NOT gate for each bit in B.

·           But now we need to do A + ~B + 1. How can we do this?

·            We are going to use a very clever trick.

·           Set the initial carry-in to 1 instead of 0, thus adding an extra 1 to the sum.

·           And instead of using NOT gates, we will use XOR gates.

·           The subtraction operation can be implemented with the help of binary adder circuit, because

·           We know that 2’s complement representation of a number is treated as a negative number of the given number.

·           We can get the 2’s complements of a given number by complementing each bit and adding 1 to it.

·           The circuit for subtracting A-B consist of an added with inverter placed between each data input B and the corresponding input of the full adder. The input carry  must be equal to 1 when performing subtraction.

·           The operation thus performed becomes A, plus the 1’s complement of B, plus 1. This is equal to A plus 2’s complement of B.

·           With this principle, a single circuit can be used for both addition and subtraction. The 4 bit adder subtractor circuit is shown in the figure. It has got one mode (M) selection input line, which will determine the operation,

If  , then  A+B

If   then 

                                   1’s complement of

4-bit adder subtractor.

The operation of OR gate:

A B 0 0 0 0 1 1 1 0 1 1 1 0

                                   

if 

if  

Unit-02/Lecture-08

Division

·           More complex than multiplication to implement (for computers as well as humans!).

·           Some processors designed for embedded applications or digital signal processing lack a divide instruction.

• Basically inverse of add and shift: shift and subtract.

• Similar to long division taught in grade school.

·            More complex than multiplication

·         Negative numbers are really bad.

·         Based on long division.

·         Division is a similar operation to multiplication, especially when implemented using a procedure similar to the algorithm shown in Figure 3.18a. For example, consider the pencil-and-paper method for dividing the byte 10010011 by the nybble 1011.

Flowchart for Unsigned Binary Division

The governing equation is as follows:

Dividend = Quotient · Divisor + Remainder

1. Unsigned Division. The unsigned division algorithm that is similar to Booth's algorithm is shown in , with an example shown in Figure. The ALU schematic shows in diagram. The analysis of the algorithm and circuit is very similar to the preceding discussion of Booth's algorithm.

(a)

(b)

(c)

Fig. Division of 32-bit Boolean number representations: (a) algorithm, (b) example using division of the unsigned integer 7 by the unsigned integer 3, and (c) schematic diagram of ALU circuitry

2.Signed Divisiion. With signed division, we negate the quotient if the signs of the divisor and dividend disagree. The remainder and the divident must have the same signs. The governing equation is as follows:

Remainder = Divident - (Quotient · Divisor) ,

and the following four cases apply:

We present the preceding division algorithm, revised for signed numbers, as shown in Figure . Four examples, corresponding to each of the four preceding sign permutations, are given in Figure.

(a)

(b)

(c)

Fig: Division of 32-bit Boolean number representations: (a) algorithm, and (b,c) examples using division of +7 or -7 by the integer +3 or -3

3. Divisiion in MIPS. MIPS supports multiplication and division using existing hardware, primarily the ALU and shifter. MIPS needs one extra hardware component - a 64-bit register able to support sll and sra instructions. The upper (high) 32 bits of the register contains the remainder resulting from division. This is moved into a register in the MIPS register stack (e.g., $t0) by the mfhi command. The lower 32 bits of the 64-bit register contains the quotient resulting from division. This is moved into a register in the MIPS register stack by the mflo command.

In MIPS assembly language code, signed division is supported by the div instruction and unsigned division, by the divu instruction. MIPS hardware does not check for division by zero. Thus, divide-by-zero exception must be detected and handled in system software. A similar comment holds for overflow or underflow resulting from division.

Figure illustrates the MIPS ALU that supports integer arithmetic operations (+,-,x,/).

Figure MIPS ALU supporting the integer arithmetic operations (+,-,x,/)

Unit-02/Lecture-09

Multiplication

°         Complex

°         Work out partial product for each digit

°         Take care with place value (column)

°         Add partial produc

Unsigned Binary Multiplication

Execution of Example

Flowchart for Unsigned Binary Multiplication

Booth's multiplication algorithm

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. Booth's algorithm is of interest in the study of computer architecture.

A typical implementation

Booth's algorithm can be implemented by repeatedly adding (with ordinary unsigned binary addition) one of two predetermined values A and S to a product P, then performing a rightward arithmetic shift on P. Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in m and r.

1. Determine the values of A and S, and the initial value of P. All of these numbers should have a length equal to (x + y + 1).
1. A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y + 1) bits with zeros.
2. S: Fill the most significant bits with the value of (−m) in two's complement notation. Fill the remaining (y + 1) bits with zeros.
3. P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill the least significant (rightmost) bit with a zero.
2. Determine the two least significant (rightmost) bits of P.
1. If they are 01, find the value of P + A. Ignore any overflow.
2. If they are 10, find the value of P + S. Ignore any overflow.
3. If they are 00, do nothing. Use P directly in the next step.
4. If they are 11, do nothing. Use P directly in the next step.
3. Arithmetically shift the value obtained in the 2nd step by a single place to the right. Let P now equal this new value.
4. Repeat steps 2 and 3 until they have been done y times.
5. Drop the least significant (rightmost) bit from P. This is the product of m and r.

Example

Find 3 × (−4), with m = 3 and r = −4, and x = 4 and y = 4:

• m = 0011, -m = 1101, r = 1100
• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0

• Perform the loop four times :
1. P = 0000 1100 0. The last two bits are 00.
• P = 0000 0110 0. Arithmetic right shift.
2. P = 0000 0110 0. The last two bits are 00.
• P = 0000 0011 0. Arithmetic right shift.
3. P = 0000 0011 0. The last two bits are 10.
• P = 1101 0011 0. P = P + S.
• P = 1110 1001 1. Arithmetic right shift.
4. P = 1110 1001 1. The last two bits are 11.
• P = 1111 0100 1. Arithmetic right shift.

• The product is 1111 0100, which is −12.

The above mentioned technique is inadequate when the multiplicand is most negative number that can be represented (e.g. if the multiplicand has 4 bits then this value is −8). One possible correction to this problem is to add one more bit to the left of A, S and P. This then follows the implementation described above, with modifications in determining the bits of A and S; e.g., the value of m, originally assigned to the first x bits of A, will be assigned to the first x+1 bits of A. Below, we demonstrate the improved technique by multiplying −8 by 2 using 4 bits for the multiplicand and the multiplier:

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0

• Perform the loop four times :
1. P = 0 0000 0010 0. The last two bits are 00.
• P = 0 0000 0001 0. Right shift.
2. P = 0 0000 0001 0. The last two bits are 10.
• P = 0 1000 0001 0. P = P + S.
• P = 0 0100 0000 1. Right shift.
3. P = 0 0100 0000 1. The last two bits are 01.
• P = 1 1100 0000 1. P = P + A.
• P = 1 1110 0000 0. Right shift.
4. P = 1 1110 0000 0. The last two bits are 00.
• P = 1 1111 0000 0. Right shift.

• The product is 11110000 (after discarding the first and the last bit) which is −16

Fig: Flow chart of Booths algorithm

Unit-02/Lecture10

Floating Point Arithmetic

Floating point (FP) representations of decimal numbers are essential to scientific computation using scientific notation. The standard for floating point representation is the IEEE 754 Standard. In a computer, there is a tradeoff between range and precision - given a fixed number of binary digits (bits), precision can vary inversely with range. In this section, we overview decimal to FP conversion, MIPS FP instructions, and how registers are used for FP computations.

We have seen that an n-bit register can represent unsigned integers in the range 0 to 2ⁿ-1, as well as signed integers in the range -2^n-1 to -2^n-1-1. However, there are very large numbers (e.g., 3.15576 · 10²³), very small numbers (e.g., 10^-25), rational numbers with repeated digits (e.g., 2/3 = 0.666666...), irrationals such as 2^1/2, and transcendental numbers such as e = 2.718..., all of which need to be represented in computers for scientific computation to be supported.

We call the manipulation of these types of numbers floating point arithmetic because the decimal point is not fixed (as for integers). In C, such variables are declared as the float datatype.

3.4.1. Scientific Notation and FP Representation

Scientific notation has the following configuration:

and can be in normalized form (mantissa has exactly one digit to the left of the decimal point, e.g., 2.3425 · 10^-19) or non-normalized form. Binary scientiic notation has the folowing configuration, which corresponds to the decimal forms:

Assume that we have the following normal format for scientific notation in Boolean numbers:

+1.xxxxxxx₂ · w^yyyyy₂ ,

where "xxxxxxx" denotes the significand and "yyyyy" denotes the exponent and we assume that the number has sign S. This implies the following 32-bit representation for FP numbers:

which can represent decimal numbers ranging from -2.0 · 10^-38 to 2.0 · 10³⁸.

3.4.2 Overflow and Underflow

In FP, overflow and underflow are slightly different than in integer numbers. FP overflow (underflow) refers to the positive (negative) exponent being too large for the number of bits alloted to it. This problem can be somewhat ameliorated by the use of double precision, whose format is shown as follows:

Here, two 32-bit words are combined to support an 11-bit signed exponent and a 52-bit significand. This representation is declared in C using the double datatype, and can support numbers with exponents ranging from -308₁₀ to 308₁₀. The primary advantage is greater precision in the mantissa.

The following chart illustrates specific types of overflow and underflow encountered in standard FP representation:

FP Arithmetic

Applying mathematical operations to real numbers implies that some error will occur due to the floating point representation. This is due to the fact that FP addition and subtraction are not associative, because the FP representation is only an approximation to a real number.

Example 1. Using decimal numbers for clarity, let x = -1.5 · 10³⁸, y = 1.5 · 10³⁸, and z = 1.0. With floating point representation, we have:

x + (y + z) = -1.5 · 10³⁸ + (1.5 · 10³⁸ + 1.0) = 0.0

and

(x + y) + z = (-1.5 · 10³⁸ + 1.5 · 10³⁸) + 1.0 = 1.0

The difference occurs because the value 1.0 cannot be distinguished in the significand of 1.5 · 10³⁸ due to insufficient precision (number of digits) of the significand in the FP representation of these numbers (IEEE 754 assumed).

The preceding example leads to several implementational issues in FP arithmetic. Firstly, rounding occurs when performing math on real numbers, due to lack of sufficient precision. For example, when multiplying two N-bit numbers, a 2N-bit product results. Since only the upper N bits of the 2N bit product are retained, the lower N bits are truncated. This is also called rounding toward zero.

Another type of rounding is called rounding to infinity. Here, if rounding toward +infinity, then we always round up. For example, 2.001 is rounded up to 3, -2.001 is rounded up to 2. Conversely, if rounding toward -infinity, then we always round down. For example, 1.999 is rounded down to 1, -1.999 is rounded down to -2. There is a more familiar technique, for example, where 3.7 is rounded to 4, and 3.1 is rounded to 3. In this case, we resolve rounding from n.5 to the nearest even number, e.g., 3.5 is rounded to 4, and -2.5 is rounded to 2.

A second implementational issue in FP arithmetic is addition and subtraction of numbers that have nonzero significands and exponents. Unlike integer addition, we can't just add the significands. Instead, one must:

1. Denormalize the operands and shift one of the operands to make the exponents of both numbers equal (we denote the exponent by E).
2. Add or subtract the significands to get the resulting significand.
3. Normalize the resulting significand and change E to reflect any shifts incurred by normalization.

Points:

•What are needed to represent a floating-point decimal number?

•It needs three fields

•Sign

•Mantissa (the significant digits)

•Exponent to an implied base (scale factor)

“Normalized” – the decimal point is placed to the right of the first (nonzero) significant digit

•To represent the number in floating point format, first binary point is shifted to right of the first bit and the number is multiplied by the scaling factor to get the same value.

•The number is said to be Normalized form and is given as

Exponent

Think about this number (all digits are decimal): ±X1.X2X3X4X5X6X7×10±Y1Y2.It is possible to approximate this mantissa precision and scale factor range in a binary representation that occupies 32 bits: 24-bit mantissa (1 sign bit for signed number), 8-bit exponent.

Instead of the signed exponent, E, the value actually stored in the exponent field is an unsigned integer E’=E+127, so called excess-127 format.

Single Precision

101000)2=4010 ; 40-127=-87

Double Precision

Problem

1)Represent 1259.12510 in single precision and double precision formats

•Step 1 :Convert decimal number to binary format

1259(10)=10011101011(2)

Fractional Part

0.125 (10)=0.001

•Binary number = 10011101011+0.001

=10011101011.001

Step 2:Normalize the number 10011101011.001=1.0011101011001 x 210 Step3:Single precision format:

For a given number S=0,E=10 and M=0011101011001 Bias for single precision format is = 127 E’=E+127=10+127=137 (10)

Step 4:Double precision format:

For a given number S=0,E=10 and M=0011101011001 Bias for double precision format is = 1023 E’=E+1023=10+1023=1033 (10)

=10000001001 (2)

IEEE Standard

•For excess-127 format, 0 ≤ E’ ≤ 255. However, 0 and 255 are used to represent special value. So actually 1 ≤ E’ ≤ 254. That means -126 ≤ E ≤ 127.

•Single precision uses 32-bit. The value range is from 2-126 to 2+127.

•Double precision used 64-bit. The value range is from 2-1022 to 2+1023.

Normalization

•If a number is not normalized, it can always be put in normalized form by shifting the fraction and adjusting the exponent. As computations proceed, a number that does not fall in the representable range of normal numbers might be generated.

•In single precision, it requires an exponent less than -126 (underflow) or greater than +127 (overflow). Both are exceptions that need to be considered.

Special Values

•The end value 0 and 255 are used to represent special values.

•When E’=0 and M=0, the value exact 0 is represented. (±0)

•When E’=255 and M=0, the value ∞ is represented. (± ∞)

•When E’=0 and M≠0, de normal numbers are represented. The value is ±0.M´2-

126. (allow for Gradual underflow)

•When E’=255 and M≠0, Not a Number (NaN).

•NaN is the result of performing an invalid operation, such as 0/0 or square root of -1.

Exceptions

•A processor must set exception flags if any of the following occur in performing operations: underflow, overflow, divide by zero, inexact, invalid.

•When exception occurs, the results are set to special values.

Arithmetic Operations on Floating-Point Numbers

Add/Subtract rule

1.Choose the number with the smaller exponent and shift its mantissa right a number of steps equal to the difference in exponents.

2.Set the exponent of the result equal to the larger exponent.

3.Perform addition/subtraction on the mantissas and determine the sign of the result.

4.Normalize the resulting value, if necessary.

Subtraction of floating point numbers

•Similar process is used for subtraction

•Two mantissas are subtracted instead of addition

•Sign of greater mantissa is assigned to the result

Step 1: Compare the exponent for sign bit using 8bit subtractor Sign is sent to SWAP unit to decide on which number to be sent to SHIFTER unit.

Step2: The exponent of the result is determined in two way multiplexer depending on the sign bit from step1

Step3: Control logic determines whether mantissas are to be added or subtracted. Depending on sign of the operand. There are many combinations are possible here, that depends on sign bits, exponent values of the operand.

Step4: Normalization of the result depending on the leading zeros, and some special case like 1.xxxxx operands. Where result is 1x.xxx and X = -1, therefore will increase the exponent value.

Example

Add single precision floating point numbers A

and B, where A=44900000 H and B = 42A00000H. Solution

Step 1 :Represent numbers in single precision format A = 0 1000 1001 0010000….0

B = 0 1000 0101 0100000….0 Exponent for A = 1000 1001 =137

Therefore actual exponent = 137-127(Bias) =10 Exponent for B = 1000 0101 = 133

Therefore actual exponent = 133-127(Bias) = 6

With difference 4. Hence its mantissa is shifted right by 4 bits as shown below Step 2:Shift mantissa

Shifted mantissa of B = 0 0 0 0 0 1 0 0…0 Step 3: Add mantissa

Mantissa of A = 00100000…0

Mantissa of B = 00000100…0 Mantissa of result = 00100100…0

As both numbers are positive, sign of the result is positive Result =0100 0100 1001 0010 0…0

=44920000H