CU-BCA-SEM-IV-Computer System Architecture-Second Draft

Figure 3.5: MIMD architecture diagram 3.6 SUMMARY  Flynn’s classification scheme is based on identifying two orthogonal streams in a computer. These are the instruction and the data streams. The instruction stream is defined as the sequence of instructions performed by the computer.  The original Von Neumann Architecture that does not employ any kind of parallelism. The sequential processor takes data from a single address in memory and performs a single instruction on the data. All single processor systems are SISD.  A single instruction is executed on multiple different data streams. These instructions can be performed sequentially, taking advantage of pipelining, or in parallel using multiple processors. Modern GPUs, containing Vector processors and array processors, are commonly SIMD systems.  Multiple autonomous processors perform operations on difference pieces of data, either independently or as part of shared memory space.  The classification helped in categorizing architectures that were available and those that have been introduced later. For example, the introduction of the SIMD and MIMD machine models in the classification must have inspired architects to introduce these new machine models.  A very important aspect that is lacking in Flynn’s classification is the issue of machine performance. Although the classification gives the impression that machines in the SIMD and the MIMD are superior to their SISD and MISD counterparts, it gives no information on the relative performance of SIMD and MIMD machines. 51 CU IDOL SELF LEARNING MATERIAL (SLM)

3.7 KEYWORDS  SISD: (single instruction stream, single data stream) is a computer architecture in which a single unicore processor executes a single instruction stream, to operate on data stored in a single memory.  SIMD: is short for Single Instruction/Multiple Data, while the term SIMD operations refer to a computing method that enables processing of multiple data with a single instruction. In contrast, the conventional sequential approach using one instruction to process each individual data is called scalar operations.  MIMD: (Multiple Instruction stream Multiple Data stream) the instruction execution architecture of a CPU that can process two or more independent sets of instructions simultaneously on two or more sets of data. CPUs with multiple cores are examples of MIMD architecture, each core performing SIMD processing.  MISD: (multiple instruction, single data) is a type of parallel computing architecture where many functional units perform different operations on the same data.  Modern GPUs: A Graphics Processing Unit (GPU) is a chip or electronic circuit capable of rendering graphics for display on an electronic device. 3.8 LEARNING ACTIVITY 1. Discuss Flynn’s classification. ___________________________________________________________________________ ______________________________________________________________ 2. Conduct a seminar on MIMD. ___________________________________________________________________________ _______________________________________________________________ 3.9 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Define Observations on Flynn’s Classification? 2. Expand SISD? 3. What is SIMD? 4. Expand MISD? 5. List the common usage of MIMD? 52 CU IDOL SELF LEARNING MATERIAL (SLM)

Long Questions 1. Explain Flynn’s Classification. 2. List and explain the Single-instruction single-data streams. 3. Explain Multiple-instruction multiple-data streams? 4. Draw and explain Multiple-instruction single-data streams? 5. Explain Single-instruction multiple-data streams? B. Multiple Choice Questions 1. How MIPS are defined as? a. IPS * 10^-6 b. IPS * 10^-9 c. IPS * 1/10^-6 d. IPS * 1/10^-9 2. Which of the following is not type of Flynn's classification of computer? a. SISD b. SIBD c. MISD d. MIMD 3. Which Flynn's classification is IBM 701, IBM 1620 and IBM 7090 are model of? a. SISD b. SIMD c. MISD d. MIMD 4. What is the technique of decomposing a sequential tasks into sub-tasks with each sub- task being executed in a special dedicated stage that operate concurrently with each other? a. DMA b. Pipelining c. Vector Processing d. Interconnection network 5. Which of the following is not a type of pipeline processor? 53 CU IDOL SELF LEARNING MATERIAL (SLM)

a. Arithmetic pipeline b. Instruction pipeline c. Processor pipeline d. Vector pipeline Answers 1-a, 2-b, 3-a, 4-b, 5-d 3.10 REFERENCES References Book  Flynn, Michael J. (September 1972). \"Some Computer Organizations and Their Effectiveness\" (PDF). IEEE Transactions on Computers. C-21 (9): 948–960. doi:10.1109/TC.1972.5009071.  Quinn, Michael J. Chapter 2: Parallel Architectures, Parallel Programming in C with MPI and OpenMP. Boston: McGraw Hill, 2004. ISBN 0-07-282256-2  Ibaroudene, Djaffer. Chapter 1: Motivation and History, Parallel Processing. St. Mary's University, San Antonio, TX. Spring 2008. Textbook References  Null, Linda; Lobur, Julia (2006). The Essentials of Computer Organization and Architecture. 468: Jones and Bartlett.  Spector, A.; Gifford, D. (September 1984). \"The space shuttle primary computer system\". Communications of the ACM. 27 (9): 872–900. doi:10.1145/358234.358246.  Michael J. Flynn, Kevin W. Rudd. Parallel Architectures. CRC Press, 1996. Website  https://edurev.in/studytube/Flynn-s-Classification-Parallelism--Computer- Scien/022d5a88-f5da-4c5b-9f2c-4547f2566e84_t  https://careericons.com/computer-aptitude-quiz/parallel-computing/discussed-1226/  https://tutorialsinhand.com/tutorials/computer-organization-and-architecture-coa- tutorial/flynns-classification-of-computers/flynns-classification-of-computers.aspx 54 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT–4:REGISTER TRANSFER AND MICRO OPERATIONS STRUCTURE 4.0 Learning Objectives 4.1 Introduction 4.2Register Transfer Language 4.3 Data movement among Registers and Memory 4.4 Summary 4.5 Keywords 4.6 Learning Activity 4.7 Unit End Questions 4.8 References 4.0 LEARNING OBJECTIVES After studying this unit, you will be able to:  Describe the Register Transfer Language.  Explain about Bus.  Illustrate the Memory Transfer. 4.1 INTRODUCTION Describing every operation in words can specify the sequence of micro-operations in a computer. But this method is avoided because it is a lengthy procedure. So we use certain symbols to describe the sequence of transfers between registers and micro-operations associated with the transfers. Symbols are an easy way to represent the micro-operation sequences in registers and the control functions that initiate them, in a lucid & concise form. This symbolic notation is called a register transfer language. This language is used for listing micro-operation sequences among the registers of digital computer system. It also acts as a facilitator in the designing process. We designate computer registers by capital letters to denote the function of the register. For example, the register that holds an address for the memory unit is usually called a memory address register, represented by MAR. Other examples are PC (for program counter), IR (for instruction register) and R1 (for processor register). We show the individual flip-flops in an 55 CU IDOL SELF LEARNING MATERIAL (SLM)

n-bit register by giving numbers them in sequence from 0 through n - 1, starting from 0 in the right most position and increasing the numbers toward the left. A 16-bit register is divided into two halves. Low byte (Bits 0 through 7) is assigned the symbol L and high byte (Bits 8 through 15) is assigned the symbol H. The name of a 16-bit register is PC. The symbol PC(L). 4.2 REGISTER TRANSFER LANGUAGE Describing every operation in words can specify the sequence of micro-operations in a computer. But this method is avoided because it is a lengthy procedure. So we use certain symbols to describe the sequence of transfers between registers and micro-operations associated with the transfers. Symbols are an easy way to represent the micro-operation sequences in registers and the control functions that initiate them, in a lucid & concise form. This symbolic notation is called a register transfer language. This language is used for listing micro-operation sequences among the registers of digital computer system. It also acts as a facilitator in the designing process. We designate computer registers by capital letters to denote the function of the register. For example, the register that holds an address for the memory unit is usually called a memory address register, represented by MAR. Other examples are PC (for program counter), IR (for instruction register) and R1 (for processor register). We show the individual flip-flops in an n-bit register by giving numbers them in sequence from 0 through n - 1, starting from 0 in the right most position and increasing the numbers toward the left. A 16-bit register is divided into two halves. Low byte (Bits 0 through 7) is assigned the symbol L and high byte (Bits 8 through 15) is assigned the symbol H. The name of a 16-bit register is PC. The symbol PC (L) Represents the low order byte and PC (H) designates the high order byte. The statement R2 ← R1 refers the transfer of the content of register R1 into register R2. It should be noted that the content of the source register R1 does not change after the transfer. In real applications, the transfer occurs only under a predetermined control condition. This can be shown by means of an “if-then” statement If P=1 then R2 ← R1 Where P is a control signal generated in the control section of the system. For convenience we separate the control variables from the register transfer operation by specifying a control function. A control function is a Boolean variable that is equal to 1 or 0. The control function is written as follows P: R2 ← R1 BUS 56 CU IDOL SELF LEARNING MATERIAL (SLM)

Since a computer has many registers, paths must be provided to transfer information from one register toanother. If separate lines are used between each register and all other registers, number of wires will beexcessive in the system. A more efficient scheme for transferring information between registers in amultiple-register configuration is a common bus system. A bus structure consists of a set of common lines,one for each bit of a register, through which binary information is transferred one at a time. Control signalsdetermine which register is selected by the bus during each particular register transfer. A common bus system can be constructed using multiplexers. These multiplexers select the source registerwhose binary information is then placed on the bus. A bus system will multiplex registers of a bit each toproduce an n-line common bus. The number of multiplexers required to construct the bus is equal to n,where n is the number of bits in each register. The size of each multiplexer must be k × 1 since itmultiplexes k data lines. A bus system can be constructed with ‘three-state gates’ instead of multiplexers. Athree-state gate is a digital circuit that shows three states. Two of the states are equivalent to logic 1 and 0.The third state is a high impedance state. The high-impedance state behaves like an open circuit, whichmeans that the output is disconnected and does not have a logic significance. The one most commonly usedin the design of a bus system is the buffer gate. The graphic symbol of a three state buffer gate is shown in the figure given below. The control inputdetermines the output. Figure 4.1: The graphic symbol of a three state buffer gate The construction of a bus system for four registers is shown in the figure in on the next page. 57 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 4.2: The construction of a bus system for four registers The function table of the above bus system is Register collected S1 S0 A 00 B 01 C 10 D 11 The construction of a bus system with three state table buffers is shown in the following figure. 58 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 4.3: The construction of a bus system with three state table buffers Memory Transfer A read operation implies transfer of information to the outside environment from a memory word, whereas storage of information into the memory is defined as write operation. Symbolizing a memory word by the letter M, it is selected by the memory address during the transfer which is a specification for transfer operations. The address is specified by enclosing it in square brackets following the letter M. For example, the read operation for the transfer of a memory unit M from an address register AR to another data register DR can be illustrated as Read: DR ←M [AR] Micro Operation A micro-operation is an elementary operation which is performed on the data stored in registers. We can classify the micro-operations into four categories. 1. Register transfer: transfer binary information from one register to another. 2. Arithmetic: perform arithmetic operations on numeric data stored in registers. 3. Logic: perform bit manipulation operation on non-numeric data stored in registers. 4. Shift: perform shift operations on data stored in registers. These micro-operations, transfer information from one register to another. It should be noted that the information does not 59 CU IDOL SELF LEARNING MATERIAL (SLM)

change during this micro-operation. A register transferred micro-operation may be designed as R1 ← R2 This implies that transfer the content of register R2 to register R1. Since we expect the register transfer to occur in a pre-determined control condition, the destination register should have a parallel load capability. A common internal data bus of the processor is used for connecting various registers. In general, the size of this data bus should be equal to the number of bits in a general register. There are some transfers who do not take place through the internal data bus, but through the system bus. These transfers are related to memory and input/output modules. Also the input/output operation is treated as a separate activity where normally a program and therefore instructions are executed. Memory transfer is considered as the most important transfer for instruction execution because it takes place at least once for every instruction. Memory transfer can be achieved via a system bus. Since, the main memory is a random access memory; therefore address of the location which is to be used is to be supplied. This address is supplied by the CPU on the address bus. There are two memory transfer operations: Read and Write. Memory Read 1. Put memory address in the memory address register (MAR). 2. Read the data of the location. Generally this is achieved by putting the data in MAR on address busalong with a memory read control signal on the control bus. The resultant of memory read is put intothe data bus which in turn stores the read data in the data register (DR). This whole operation can beshown as DR←M [MAR] Memory Write 1. Put the desired memory address in memory address register (MAR) and the data to be written in thedata register (DR). 2. Write the data into the location: MAR puts the address on address bus and DR puts the data on databus to be written into the memory location addressed by MAR. M [MAR] ← DR Usually, a memory read or writes operation requires more clock cycles than a register transfer operation. Arithmetic Micro-Operations These micro-operations perform some basic arithmetic operations on the numeric data stored in theregisters. These basic operations may be addition, subtraction, incrementing a number, decrementing anumber and arithmetic shift operation. An ‘add’ micro-operation can be specified as 60 CU IDOL SELF LEARNING MATERIAL (SLM)

R3 ← R1 + R2 It implies: add the contents of registers R1 and R2 and store the sum in register R3.The add operation mentioned above requires three registers along with the addition circuit in the ALU.Subtraction, is implemented through complement and addition operation as R3 ← R1 – R2 is implemented as R3 ← R1 + (2’s complement of R2) R3 ← R1 + (1’s complement of R2 + 1) R3 ← R1 + R2 + 1 An increment operation can be symbolized as R1 ← R1 + 1 While a decrement operation can be symbolized as R1 ← R1 – 1 We can implement increment and decrement operations by using a combinational circuit or binary up/down counters. In most of the computers multiplication and division are implemented using add/subtract and shift micro-operations. If a digital system has implemented division and multiplication by means of combinational circuits then we can call these as the micro-operations for that system. An arithmetic circuit is normally implemented using parallel adder circuits. Each of the multiplexers (MUX) of the given circuit has two select inputs. This 4-bit circuit takes input of two 4-bit data values and a carry-in-bit and outputs the four resultant data bits and a carry-out-bit. With the different input values we can obtain various micro- operations. Equivalent micro-operation Micro-operation name R ← R1 + R2 Add R ← R1 + R2 +1 Add with carry R ← R1 + R2 Subtract with borrow R ← R1 + 2’s Subtract R ← R1 Transfer R ←R1 + 1 Increment R ← R1 – 1 Decrement Logic Micro-Operations These operations are performed on the binary data stored in the register. For a logic micro- operation each bit of a register is treated as a separate variable. For example, if R1 and R2 are 8 bits registers and 61 CU IDOL SELF LEARNING MATERIAL (SLM)

R1 contains 10010011 and R2 contains 01010101 R1 AND R2 00010001 Some of the common logic micro-operations are AND, OR, NOT or complements. Exclusive OR, NOR, NAND. We can have four possible combinations of input of two variables. These are 00, 01, 10 and 11. Now, for all these 4 input combination we can have 24 = 16 output combinations of a function. This implies that for two variables we can have 16 logical operations. Some Application of Logic Micro operations Selective Set This operation sets to 1, the bits in register A, where there are corresponding 1’s in register B. For example 1010 A before 1101 B (logic operand) 1111 A after It is clear that the OR micro-operation can be used to selectively set the bits of a register. Selective Compliment This operation compliment bits in A where there are corresponding 1’s in B. Obviously the bit positions that have 0’s in B are not affected by this operation. For example 1100 A before 1010 B (logic operand) 0110 A after Hence the exclusive OR micro-operation can be used to selectively complement bits of a register. Selective Clear The selective clear operation clears to 0, the bits a only where there are corresponding 1’s is B. Following example clarifies this. 1100 A before 1010 B (logic operand) 0100 A after Hence the logic micro-operation corresponding to this is. A←B ^ B 62 CU IDOL SELF LEARNING MATERIAL (SLM)

Mask Operation The mask operation is similar to the selective clear operation except that the bits of a are cleared only where there are corresponding 0’s in B. It can be seen by the following example 1010 A before 1100 B (logic operation) 1000 A after masking The two right most bits of A are cleared because the corresponding bits of B are 0’s. The two right most bits are left unchanged due to the corresponding bits of B (i.e. 1). The mask operation is more convenient to use than the selective clear because most computers provide an AND instruction, and few provide an introduction that executes the micro operation is an AND micro operation. Insert Operation This operation is used to insert a new value into a group of bits. This can be done by first masking the bits and then ORing them with the required value. For example suppose that an A register contains 8 bits, 01101010. To replace the four unwanted bits. 0110 1010 A before 0000 1111 B (mask) 0000 1010 A after masking And then insert the new value 0000 1010 A before 1001 0000 B (insert) 1001 1010 A after insertion Insert operation is an OR microoperation Shift Micro-Operation Shift microoperation can be used for serial transfer of data. They are used generally with the arithmetic, logic, and other data-processing operations. The contents of a register can be shifted to the left or the right. During a shift-right operation the serial input transfers a bit into the leftmost position. The serial input transfers a bit into the rightmost position during a shift- left operation. There are three types of shifts, logical, circular and arithmetic. 1. Logical shift A logical shift operation transfers 0 through the serial input. We use the symbols shl and shr for logical shift left and shift right micro operations, e.g. R1 ← shl R1 63 CU IDOL SELF LEARNING MATERIAL (SLM)

R2 ← shr R2 are the two micro operations that specify a 1-bit shift left of the content of register R1 and a 1- bit shift right of the content of register R2. 2. Circular shift The circular shift is also known as rotate operation. It circulates the bits of the register around the two ends and there is no loss of information. This is accomplished by connecting the serial output of the shift register to its serial input. We use the symbols cil and cir for the circular shift left and circular shift right. E.g. suppose Q1 register contains 01101101 then after cir operation, it contains 0110110 and after cil operation it will contain 11011010. 3. Arithmetic shift An arithmetic shift microoperation shifts a signed binary number to the left or right. The effect of an arithmetic shift left operation is to multiply the binary number by 2. Similarly an arithmetic shift right divides the number by 2. Because the sign of the number must remain the same arithmetic shift-right must leave the sign bit unchanged, when it is multiplied or divided by 2. The left most bit in a register holds the sign bit, and the remaining bits hold the number. The sign bit is 0 for positive and 1 for negative. Negative numbers are in 2’s complement form. Following figure shows a typical register of n bits. Sign bit Arithmetic shift right Bit Rn-1 in the left most position holds the sign bit. Rn-2 is the most significant bit of the number and R0 is the least significant bit. The arithmetic shift-right leaves the sign bit unchanged and shifts the number (including the sign bits) to the right. Thus Rn-1 remains the same; Rn-2 receives the bit from Rn-1, and so on for other bits in the register. 4.3 DATA MOVEMENT AMONG REGISTERS AND MEMORY Data movement instructions move data from one place, called the source operand, to another place, called the destination operand. Data movement instructions can be grouped into loads, stores, moves, and immediate loads. Load instructions move data from memory to registers. Store instructions move data from registers to memory. Move instructions move data from one register to another. Immediate load instructions move constants, including addresses, to registers. 64 CU IDOL SELF LEARNING MATERIAL (SLM)

Basic Instructions MOVE MOV R1 R2, MOV R1 500, MOV R1 X LOAD Memory to Regi. LD I 500, LD R1 R2, LD R1 X STORE Regi to Memory STA EXCHANGE XCHG R1, R2 INPUTIN Get Data from Input Device OUTPUT OUT For Give Data to Device PUSH Memory Use as Stack Insert POP Delete from Top Load Instructions Load instructions move data from memory to registers. INSTRUCTION OPERATION Lb Rd, Addr Load Byte Sign Extended Lbu Rd, Addr Load Byte Zero Extended Lh Rd, Addr Load Half word Sign Extended Lhu Rd, Addr Load Half word Zero Extended Lw Rd, Addr Load Word L.D Fd, Addr Load Double L.S Fd, Addr Load Float Store Instructions Store instructions move data from registers to memory. INSTRUCTION OPERATION Sb Rs, Addr Store Byte Sh Rs, Addr Store Half word Sw Rs, Addr Store Word S.D Fs, Addr Store Double S.S Fs, Addr Store Float Move Instructions Move instructions move data from one register to another. INSTRUCTION OPERATION 65 CU IDOL SELF LEARNING MATERIAL (SLM)

Mfc0 Rd, Cs Load From Control Register Mfc1 Rd, Fs Load From Floating Point Register Move Rd, Rs Move Integer Data Move.D Fd, Fs Move Double Move.S Fd, Fs Move Float Mtc0 Rs, Cd Store To Control Register Mtc1 Rs, Fd Store To Floating Point Register Immediate Load Instructions Immediate load instructions move constants to registers. INSTRUCTION OPERATION La Rd, Label Load Address Li Rd, Const Load Immediate Li.D Fd, Const Load Double Immediate Li.S Fd, Const Load Float Immediate 4.4 SUMMARY  Since a computer has many registers, paths must be provided to transfer information from one register to another. If separate lines are used between each register and all other registers, number of wires will be excessive in the system.  A common bus system can be constructed using multiplexers. These multiplexers select the source register whose binary information is then placed on the bus.  A read operation implies transfer of information to the outside environment from a memory word, whereas storage of information into the memory is defined as write operation.  These micro-operations perform some basic arithmetic operations on the numeric data stored in the registers. These basic operations may be addition, subtraction, incrementing a number, decrementing a number and arithmetic shift operation. An ‘add’ micro-operation can be specified as: R3 ← R1 + R2.  Shift microoperation can be used for serial transfer of data. They are used generally with the arithmetic, logic, and other data-processing operations. The contents of a register can be shifted to the left or the right. During a shift-right operation the serial input transfers a bit into the leftmost position. 66 CU IDOL SELF LEARNING MATERIAL (SLM)

 A logical shift operation transfers 0 through the serial input. We use the symbols shl and shr for logical shift left and shift right micro operations, e.g. R1 ← shl R1 R2 ← shr R2. 4.5 KEYWORDS  BUS - In computer architecture, a bus is a communication system that transfers data between components inside a computer, or between computers.  Memory Transfer - The address register (AR) is used to select a memory address, and the data register (DR) is used to send and receive data. Both these registers are connected to the internal bus. DR is a bridge between the internal BUS and the memory data BUS.  Micro Operation - In computer central processing units, micro-operations (also known as a micro-ops or μops, historically also as micro-actions) are detailed low- level instructions used in some designs to implement complex machine instructions (sometimes termed macro-instructions in this context).  Insert Operation - This operation is used to insert a new value into a group of bits. This can be done by first masking the bits and then ORing them with the required value.  Circular Shift - The circular shift is also known as rotate operation. It circulates the bits of the register around the two ends and there is no loss of information. This is accomplished by connecting the serial output of the shift register to its serial input. 4.6 LEARNING ACTIVITY 1. Discuss the topic on register transfer language ___________________________________________________________________________ _____________________________________________________________________ 2. Conduct a seminar on data movement among registers and memory ___________________________________________________________________________ _____________________________________________________________________ 4.7 UNIT END QUESTIONS A. Descriptive Questions 67 Short Questions 1. What register transfer language? 2. What is memory transfer? CU IDOL SELF LEARNING MATERIAL (SLM)

3. What is micro operation? 4. What is shift micro operation? 5. What are the types of shift micro operation? Long Questions 1. Describeregister transfer language. 2. Explain data movement among registers and memory. 3. Explain the construction of a bus system with diagram. 4. Explain memory transfer system. 5. Explain MAR and the MDR. B. Multiple Choice Questions 1. What does CPU has built-in ability to execute a particular set of machine instructions, called as a. Instruction set b. Registers c. Sequence set d. User instructions 2. What is the length of a register is called? a. Word limit b. Word size c. Register limit d. Register size 3. What holds the contents of the accessed memory word? a. MAR b. MBR c. PC d. IR 4. Which of the following is a data transfer instruction? 68 a. STA 16-bit address b. ADD A, B c. MUL C, D d. RET CU IDOL SELF LEARNING MATERIAL (SLM)

5. What is correct instruction if you want the control to go to the location 2000h? a. MOV 2000h b. MOV A, 2000h c. JMP 2000h d. RET 2000h Answers 1-a, 2-b, 3-b, 4-a, 5-c. 4.8 REFERENCES References  ABBATTISTA, F., DELL'AQUILA, C., PIZZUTILO, S., AND TANGORRA, F. 2000. An object oriented simulator of computer microarchitectures. In Proceedings of the IASTED International Conference on Modelling and Simulation (Pittsburgh, PA, May).  AGREN, O. 1999. Teaching computer concepts using virtual machines. SIGCSE Bull. 31, 2, 84-85.  KERRIDGE, J., AND WILLIS, N. 1980. A simulator for teaching computer architecture. SIGCSE Bull. 12, 2, 65-71. Textbooks  SKRIEN, D., AND HOSACK, J. 1991. A multilevel simulator at the register transfer level for use in an introductory machine organization class. SIGCSE Bull. 23, 1, 347- 351.  SKRIEN, D. 1994. CPU Sim: A computer simulator for use in an introductory computer organization class. J. Comput. Higher Education 6, 1, 3-13.  TANENBAUM, A. 1999. Structured Computer Organization. 4th ed., Prentice Hall, Upper Saddle River, NJ. Website  https://www.javatpoint.com  https://www.geeksforgeeks.org  https://www.computerscience.gcse.guru 69 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT –5:MICRO OPERATIONS STRUCTURE 5.0 Learning Objectives 5.1 Introduction 5.2 Micro-operations 5.3 Types of Micro-operations 5.3.1 Register Transfer Micro-operations 5.3.2 Arithmetic Micro-operations 5.3.3 Logic Micro-operations 5.3.4 Shift Micro-operations 5.4 Logic Operations 5.5Shift operations 5.6 Arithmetic and Shift operations. 5.7 Summary 5.8 Keywords 5.9 Learning Activity 5.10Unit End Questions 5.11 References 5.0 LEARNING OBJECTIVES After studying this unit, you will be able to:  Describe the Micro-operations.  Explain types of micro-operations.  Illustrate about Logic Operations. 5.1 INTRODUCTION In computer central processing units, micro-operations (also known as micro-ops) are the functional or atomic, operations of a processor. These are low level instructions used in some designs to implement complex machine instructions. They generally perform operations on 70 CU IDOL SELF LEARNING MATERIAL (SLM)

data stored in one or more registers. They transfer data between registers or between external buses of the CPU, also performs arithmetic and logical operations on registers. In executing a program, operation of a computer consists of a sequence of instruction cycles, with one machine instruction per cycle. Each instruction cycle is made up of a number of smaller units – Fetch, Indirect, Execute and Interrupt cycles. Each of these cycles involves series of steps, each of which involves the processor registers. These steps are referred as micro-operations. If CPU wants to perform any operation, suppose execution of only one instruction or even break it down one particular execution phase (like fetch instruction, write back, decode, operand fetch etc.). CPU cannot perform one operation in one single step; it performs these operations in multiple small- small steps. These small-small steps of operations are called micro-operations. Definition-“The operations executed on values stored in registers are called as micro- operations.” CPU can perform operations on some values (operands), and these values are stored in memory (registers). Operations made by the CPU to fetch these values and execute the instruction are micro- operations. “To execute an instruction or program CPU perform various operations step by step and these instructions are commanded by the control unit of the CPU. Control unit generate command and rest of the system follow these commands to fetch the instruction. Whenever one type of command is generated by your control unit then a particular small operation is performed and that operation is micro-operation.” 5.2 MICRO-OPERATIONS A micro-operation is an elementary operation performed normally during one clock pulse. On the information stored in one or more registers. The result of the operation may replace the previous content of a register or is transferred to a new register or a memory location. A digital system performs a sequence of micro-operations on data stored in registers or memory. The specific sequence of micro-operations performed is predetermined for an instruction. Thus, an instruction is a binary code specifying a definite sequence of micro- operations to perform a specific function. For example, a C program instruction sum = sum + 7, will first be converted to equivalent assembly program  Move data from memory location “sum” to register R1 (LOAD R1, sum).  Add an immediate operand to register (R1) and store the results in R1 (ADD R1, 7).  Store data from register R1 to memory location “sum” (STORE sum, R1). 71 CU IDOL SELF LEARNING MATERIAL (SLM)

Thus, several machine instructions may be needed (this will vary from machine to machine) to execute a simple C statement. But, how will each of these machine statements be executed with the help of micro-operations? Let us try to elaborate the execution steps.  Fetch the instructions i. Pass the address of Program Counter (PC) to Memory Address Register (MAR). ii. Issue the memory read operation to fetch instruction in the Buffer Register for data, such as M (BR). iii. Increment Program Counter to refer to next instruction in sequence and bring instruction to Instruction Register (IR).  Execute the instruction i. Decode the instruction to ascertain operation. ii. As one of the operands is already available in R1 register and the second operand is an immediate operand so fetch operand step is not required. The immediate operand is available in the address part of the instruction. iii. Perform the ALU based addition with R1 and buffer register, store the result in R1. Thus, we may have to execute the instruction in several steps. For the subsequent discussion, for simplicity, let us assume that each micro-operation can be completed in one clock period, although some micro-operations require memory read/write that may take more time. Let us first discuss the type of micro-operations. The most common micro-operations performed in a digital computer can be classified into four categories. a. Register transfer micro-operations: simply transfer binary information from one register to another. b. Arithmetic micro-operations: perform simple arithmetic operations on numeric data stored in registers. c. Logic micro-operations: perform bit manipulation (logic) operations on nonnumeric data stored in registers. d. Shift micro-operations registers: perform shift operations on data stored in registers. 5.3 TYPES OF MICRO-OPERATIONS We all know computer system is very useful thing in today’s era and if I tell about architecture of this great invention it has various components and it has very complex hardware implemented perfectly. So today this post is all about micro operationsused by hardware of computer system and it is also considered in architecture of computer system. 72 CU IDOL SELF LEARNING MATERIAL (SLM)

In system design using modular approach having components and join these components to make a system, components could be registers, multiplexers, decoders, adders etc. Micro operations are the basic operations that can be performed by system on data stored in registers. Each microoperation describes a simple operation performed on data in one or more registers. Micro operations are used by processors to complete their tasks to transfer data from one place to another. If we take this more specific then microoperation could be for transfer data from register to register, between registers and external bus, or accomplish a simple ALU operation.  Register Transfer Micro-operations: Transfer binary information from one register to another.  Arithmetic Micro-operations: Perform arithmetic operation on numeric data stored in registers.  Logical Micro-operations: Perform bit manipulation operations on data stored in registers.  Shift Micro-operations: Perform shift operations on data stored in registers. Register Transfer Micro-operation doesn’t change the information content when the binary information moves from source register to destination register. Other three types of micro-operations change the information change the information content during the transfer. 5.3.1 Register Transfer Micro-Operations These micro-operations, as the name suggests transfer information from one register to another. The information does not change during these micro-operations. A register transfer micro-operation may be designed as. R1← R2. The ← symbol implies that the contents of register R2 are transferred to register R1. R2 here is a source register while R1 is a destination register. We will use this notation throughout this section. Please note the following important points about register transfer micro-operations.  For a register transfer micro-operation there must be a path for data transfer from the output of the source register to the input of destination register.  In addition, the destination register should have a parallel load capability, as we expect the register transfer to occur in a predetermined control condition. We will discuss more about the control unit in Unit 4 of this block.  A common path for connecting various registers is through a common internal data bus of the processor. In general the size of this data bus should be equal to the number of bits in a general register. 73 CU IDOL SELF LEARNING MATERIAL (SLM)

The convention used to represent the micro-operations is 1. Computer register names are designated by capital letters (sometimes followed by numerals) to denote its function. For example, R1, R2 (General Purpose Registers), AR (Address Register), IR (Instruction Register) etc. 2. The individual bits within a register are numbered from 0 (rightmost bit) to n-1 (leftmost bit) as shown in Figure 5.1). Common ways of drawing the block diagram of a computer register are shown below. The name of the 16-bit register is IR (Instruction Register) which is partitioned into two subfields in Figure 5.1). Bits 0 through 7 are assigned the symbol L (for low byte) and bits 8 through 15 are assigned the symbol H (for high byte). The symbol PC (L) refers to the low-order byte and PC (H) refers to high-order byte. Figure 5.1: Register formats 3. Information transfer from one register to another is designated in symbolic notation by a replacement operator. For example, the statement R2 ← R1 denotes a transfer of all bits from the source register R1 to the destination register R2 during one clock pulse and the destination register has a parallel load capacity. However, the contents of register R1 remain unchanged after the register transfer micro-operation. More than one transfer can be shown using a comma operator. 4. If the transfer is to occur only under a predetermined control condition, then this condition can be specified as a control function. For example, if P is a control function then P is a Boolean variable that can have a value of 0 or 1. It is terminated by a colon (:) and placed in front of the actual transfer statement. The operation specified in the statement takes place only when P = 1. Consider the statements If (P = 1) then (R2 ← R1) P: R2 ← R1, Where P is a control function that can be either 0 or 1. 74 CU IDOL SELF LEARNING MATERIAL (SLM)

5. All micro-operations written on a single line are to be executed at the sametime provided the statements or a group of statements to be implementedtogether are free of conflict. A conflict occurs if two different contents arebeing transferred to a single register at the same time. For example, thestatement: new line X: R1 ←R2, R1←R3 represents a conflict because bothR2 and R3 are trying to transfer their contents to R1 at the same time. 6. A clock is not included explicitly in any statements discussed above. However,it is assumed that all transfers occur during the clock edge transitionimmediately following the period when the control function is 1. All statementsimply a hardware construction for implementing the micro-operation statementas shown below:Implementation of controlled data transfer from R2 to R1 only when T = 1 T:R1 ←R2. Bus and Memory Transfers Quite often a digital computer has many registers, and rather than connectingwires between all registers to transfer information between them, a common bus isused. Bus is a path (consists of a group of wires) one for each bit of a register, overwhich information is transferred, from any of several sources to any of severaldestinations. From a register to Bus: BUS ← R. The transfer from bus to register can beexpressed symbolically as: R1 ← BUS, The content of the selected register is placed on the BUS and the content ofthe bus is loaded into register R1 by activating its load control input. Memory Transfer The transfer of information from memory to outside environment i.e., I/OInterface is called a read operation. The transfer of new information to be stored inmemory is called a write operation. These kinds of transfers are achieved via asystem bus. It is necessary to supply the address of the memory location formemory transfer operations. Memory Read The memory unit receives the address from a register, called the memory address register designated by MAR. The data is transferred to another register, called the data register designated by DR. The read operation can be stated as:Read: DR ← [MAR]. Memory Write The memory write operation transfers the content of a data register to a memory word M selected by the address. Assume that the data of register R1 is to be written to the memory at the address provided in MAR. The write operation can be stated as: Write: [MAR] ← R1 please note, it means that the location pointed by MAR will be written. 75 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.2: Memory transfer 5.3.2 Arithmetic Micro-Operations These micro-operations perform simple arithmetic operations on numeric data stored in registers. The basic arithmetic micro-operations are addition, subtraction, increment, decrement, and shift. Addition micro-operation is specified as R3 ←R1 +R2 It means that the contents of register R1 are added to the contents of register R2 and the sum is transferred to register R3. This operation requires three registers to hold data along with the Binary Adder circuit in the ALU. Binary adder is a digital circuit that generates the arithmetic sum of two binary numbers of any lengths and is constructed with full-adder circuits connected in cascade. An n-bit binary adder requires n full- adders. Add micro-operation, in accumulator machine, can be performed as AC ←AC + DR Subtraction is most often implemented in machines through complement and adds operations. It is specified as R3 ←R1 − R2 R3 ←R1 + (2’s complement of R2) R3 ←R1 + (1’s complement of R2 + 1) R3 ←R1 + R2 + 1 (The bar on top of R2 implies 1’s complement of R2 which is bitwise complement) Adding 1 to the 1’s complement produces the 2’s complement. Adding the contents of R1 to the 2’s complement of R2 is equivalent to subtracting the contents of R2 from R1 and storing the result in R3. We will describe the basic circuit required for these micro-operations in the next unit. The increment micro-operation adds one to a number in a register. This operation is designated as R1 ← R1 + 1 76 CU IDOL SELF LEARNING MATERIAL (SLM)

This can be implemented in hardware by using a binary-up counter. The decrement micro- operation subtracts one from a number in a register. This operation is designated as R1 ← R1 – 1 This can be implemented using binary-down counter. What about the multiply and division operations? Are not they micro- operation? In most of the older computers multiply and divisions were implemented using add/subtract and shift micro-operation. If a digital system has implemented division and multiplication by means of combinational circuits, then we can call these as the micro-operations for that system. 5.3.3 Logic Micro-Operations Logic operations are basically binary operations, which are performed on the string of bits stored in the registers. For a logic micro-operation each bit of a register is treated as a variable. A logic micro-operation: R1 ← R1. R2 specifies AND operation to be performed on the contents of R1 and R2 and store the results in R1. For example, if R1 and R2 are 8 bits registers and R1 contains 10010011 and R2 contains 01010101 Then R1 will contain 00010001 after AND operation. Some of the common logic micro-operations are AND, OR, NOT or Complement, Exclusive OR, NOR, and NAND. In many computers only four: AND, OR, XOR (exclusive OR) and complement micro-operations are implemented. Let us now discuss how these four micro-operations can be used in implementing some of the important applications of manipulation of bits of a word, such as, changing some bit values or deleting a group of bits. We are assuming that the result of logic micro-operations go back to Register R1 and R2 contains the second operand. Let us select 1100 as 4 bit data for register R1, and 1001 data for register R2. If we see the bit combinations of R2, and R1, they represent the truth table entries (read from right to left and bottom to top) 00, 01, 10 and 11. Thus, the resultant of the logical operation on them will indicate which logic micro-operation is needed to be performed for that data manipulation. The following table gives details on some of these operations. R1 1100 R2 1001 Operation Name Operation Example and Explanation Selective Set Sets bits of R1 R1 = 1100 R2 = 1001 77 CU IDOL SELF LEARNING MATERIAL (SLM)

1101 Selective Clear Clear bits in R1 R1 = 1100 R2 = 1001 0100 Selective Complement Complement bits in R1 R1 = 1100 R2 = 1001 0001 Mask Operation Clear bit in R1 R1 = 1100 R2 = 1001 1000 Table 5.1: Logic micro operations 1 5.3.4 Shift Micro-Operations Shift is a useful operation, which can be used for serial transfer of data. Shift operations can also be used along with other (arithmetic, logic, etc.) operations. For example, for implementing a multiply operation arithmetic micro- operation (addition) can be used along with shift operation. The shift operation may result in shifting the contents of a register to the left or right. In a shift left operation a bit of data is input at the right most flip-flop while in shift right a bit of data is input at the left most flipflop. In both the cases a bit of data enters the shift register. Depending on what bit enters the register and where the shift out bit goes, the shifts are classified in three types. These are  Logical  Arithmetic and  Circular In logical shift the data entering by serial input to left most or right most flip-flop (depending on right or left shift operations respectively) is a 0. If we connect the serial output of a shift register to its serial input then we encounter a circular shift. In circular shift left or circular shift right information is not lost, but is circulated. In arithmetic shift a signed binary number is shifted to the left or to the right. Thus, an arithmetic shift-left causes a number to be multiplied by 2; on the other hand a shift-right causes a division by 2. But as in division or multiplication by 2 the sign of a number should not be changed; therefore, arithmetic shift must leave the sign bit unchanged. Let us summarize micro-operations using the table 5.2. 78 CU IDOL SELF LEARNING MATERIAL (SLM)

Micro-operations Examples Register transfer R1 ← R2 Arithmetic micro-operation [MAR] ← R1 (Register to memory) ADD R1 ←R1 + R2; Subtract R1 ←R1 + R2; Logical micro-operation AND; OR; NOT; XOR; COMPLEMENT. Shift micro-operations Left or Right Shift ←Logical; Arithmetic, Circular. Table 5.2: Micro-operations 2 5.4 LOGIC OPERATIONS A logical operation is a special symbol or word that connects two or more phrases of information. It is most often used to test whether a certain relationship between the phrases is true or false. In computing, logical operations are necessary because they model the way that information flows through electrical circuits, such as those inside a CPU. These types of operations are called Boolean operations. The elements in a circuit which behave according to Boolean logic are called logic gates. Fundamental Logic Operations The following seven logic operations take inputs that are either true (1) or false (0) and produce a single output value that is also true or false. Most of these operations can take more than two inputs, except for the NOT operation which takes only one input. Below are examples using only one or two inputs, which is what usually happens inside a computer. The operations are listed below. Click a link for an operation to learn more. AND The AND logic operation returns true only if either of its inputs are true. If either of the inputs is false, the output is also false. In computer programming, the AND operation is usually written as && (two ampersands). In Boolean algebra, the AND operation of two inputs A and B can be written as AB. Below is the truth table for an AND operation, and the circuit diagram of an AND logic gate. 79 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.3: AND Operation truth table and circuit diagram OR The OR logic operation returns true if either of its inputs are true. If all inputs are false, the output is also false. In computer programming, the OR operation is usually written as || (two vertical bars). In Boolean algebra, the OR value of two inputs A and B can be written as A+B. Note: Do not mistake the OR operation for arithmetic addition, even though they both use the \"+\" symbol. They are distinct operations. Below is the truth table for an OR operation, and the circuit diagram of an OR logic gate. 80 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.4: OR Operation truth table and circuit diagram NOT The NOT logic operation returns true if its input is false, and false if its input is true. In computer programming, the NOT operation is usually written as! (An exclamation mark). In Boolean algebra, the NOT value of an input A can be written as A̅ (A with an over score). Below is the truth table for a NOT operation, and the circuit diagram of a NOT logic gate. Figure 5.5: OR Operation truth table and circuit diagram NAND The NAND logic operation (which stands for \"NOT AND\") returns true if its inputs are false, and false if either of its inputs is true. Tip: NAND Flash is a type of flash memory based on NAND logic gates. In Boolean algebra, the NAND value of two inputs A and B can be written as (AB with an overscore). NAND has the distinction of being one of two \"universal\" logic gates because any other logic operation can be created using only NAND gates. (The other universal logic gate is NOR.) Below is the truth table for a NAND operation, and the circuit diagram of a NAND logic gate. 81 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.6: OR Operation truth table and circuit diagram NOR The NOR logic operation (which stands for \"NOT OR\") returns true if its inputs are false, and false if either of its inputs is true. Tip: NOR Flash is a type of flash memory based on NOR logic gates. In Boolean algebra, the NOR value of two inputs A and B can be written as (A+B with an overscore). NOR has the distinction of being one of two \"universal\" logic gates, because any other logic operation can be created using only NOR gates. (The other universal logic gate is NAND.) Below is the truth table for a NOR operation, and the circuit diagram of a NOR logic gate. 82 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.7: OR Operation truth table and circuit diagram XOR The XOR logic operation (which stands for \"Exclusive OR\" returns true if either of its inputs differ, and false if they are all the same. In other words, if its inputs are a combination of true and false, the output of XOR is true. If its inputs are all true or all false, the output of XOR is false. In Boolean algebra, the XOR value of two inputs A and B can be written as A⊕B (the XOR symbol, ⊕, resembles a plus sign inside a circle). Below is the truth table for an XOR operation, and its circuit diagram. 83 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.8: OR Operation truth table and circuit diagram XNOR The XNOR logic operation (which stands for \"Exclusive NOT OR\" returns true if either of its inputs are the same, and false if either of them differ. In other words, if its inputs are a combination of true and false, the output of XNOR is false. If its inputs are all true or all false, the output of XNOR is true. In Boolean algebra, the XNOR value of two inputs A and B can be written as (the XOR symbol, ⊕, resembles a plus sign inside a circle with line over everything). Below is the truth table for an XNOR operation, and its circuit diagram. 84 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.9: OR Operation truth table and circuit diagram 5.5 ARITHMETIC OPERATIONS Binary Addition In Binary Arithmetic 0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 0 with a carry of 1. This can be given in the form of a table which is called as TRUTH TABLE. Adding 2 Binary digits without considering the carry from the addition of the adjacent less significant digits is called Half-Addition. G E SC 0 0 00 0 1 10 1 0 10 1 1 01 G: Augend; E: Addend; S: Sum; C: Resulting Carry. The Electronic device that performs the Half-Addition is called as Half-Adder. 85 CU IDOL SELF LEARNING MATERIAL (SLM)

The block diagram of a Half-Adder is shown in Fig. 5.10 Figure 5.10: Block diagram of a Half-Adder i. Full Addition In the computers, the Augend and the Addend are mostly stored in separate General- Purpose Registers and the ALU performs their addition. The result will be stored in any one of the 2 registers. In small computers, each Register will be of 8 Bits and addition of two 8-bit numbers can be performed in them. Medium size computers have 16-bit registers, big size computers 32-bit registers and Supercomputers 64-bit Registers. When two 8 bit or 16 bit or 32 bit or 64-bit Binary numbers are added, the addition of the least significant bits will be a Half-Addition. In the case of the subsequent digits, the carry from the previous addition has also to be added along with the two digits. This addition is called FULL-ADDITION. The Truth- Table for full addition is shown in Table. G E PSE 0 0 000 0 0 110 0 1 010 0 1 101 1 0 010 1 0 101 1 1 001 1 1 111 G: Augend; E: Addend; P: Previous Carry; S: Sum; C: Resulting Carry. 86 CU IDOL SELF LEARNING MATERIAL (SLM)

The Electronic device that performs full-addition is called FULL-ADDER. The Block- Diagram of a Full-Adder is shown in Fig. 5.11. Figure 5.11: Full adder The addition of 2 Binary Numbers with two or more digits is illustrated in the example below. Example: Perform the addition of the Binary numbers 1011 and 1010. Decimal value Augend 1011 11 Addend 1010 10 Sum 10101 21 ii. Adder Circuits One type of Adder Circuit will contain as many Adders as the number of bits in the (size of the) General Purpose Registers. One of them will be a Half-Adder and the rest Full- Adders. The Half-Adder is to add the least significant digits and the others for adding the other digits. Such an Adder is called a RIPPLE CARRY ADDER or PARALLEL ADDER. The block diagram of a 4 Bit Ripple Carr Adder is given in Fig. 5.12. Note that the Carry from each stage is taken to the next stage for adding and the ‘Final Carry’ is taken as the most significant bit in the Sum. Figure 5.12: Ripple Carry Adder 87 CU IDOL SELF LEARNING MATERIAL (SLM)

iii. Serial Adder Circuit This consists of only one Adder which will be a Full-Adder. The Augend and the Addend are each stored in a separate Register. The Binary Data in these Registers are simultaneously shifted Bit by Bit to the Right by a clock pulse. The shifted bits are added by the Full-Adder and the Sum bit is transferred to a Register. The circuit includes a CAREY FLIP-FLOP and a CYCLE COUNTER. The carry Flip-Flop takes out the Carry from the Adder and feeds back to it so that it will be added with the bits of the next higher order from the Augend and the Addend. The Carry Flip-Flop is initialized (made to 0) initially (i.e.) while adding the least significant bits. The Cycle Counter will be initialized at the start of the operation. After each clock-pulse (i.e.) after each addition, it will be incremented by 1. After the count in it becomes equal to the number of bits in any one of the registers, the Add Operation will be terminated. Figure 5.13: Serial Adder Binary Subtraction There are 2 methods of performing subtraction of a Binary number from another Binary number, namely i. Direct subtraction, and ii. Subtraction by complementary addition. Direct Subtraction In this: 1 – 1 = 0; 1 – 0 = 1; 0 – 0 = 0; 0 – 1 = 1 with a borrow of 1. This way of sub-tracting a Binary digit from another without considering the previous borrow, if any, is called Half Subtraction. The Truth Table for Half Subtraction is given in the Table below. 88 CU IDOL SELF LEARNING MATERIAL (SLM)

MT D = M-T B 00 0 0 01 1 1 10 1 0 11 0 0 M: Minuend; T: Subtrahend; D: Difference; B: Resulting Borrow. The Electronic device that performs Half-Subtraction is called Half-Sub-tractor. The Block diagram of a Half-Sub-tractor is given in Fig. 5.14. Figure 5.14: Half Subtractor If the Minuend and the Subtrahend are of two or more digits, the subtraction of the least significant digit of the subtrahend from that of the minuend is half-subtraction. For the subtraction of the higher order digits the borrow resulting from the previous operation has to be taken into account. Such a subtraction is called Full-Subtraction. The Truth Table for the Full-Subtraction is given in Table below. MT W DB 00 0 00 00 1 11 01 0 11 01 1 01 10 0 10 89 CU IDOL SELF LEARNING MATERIAL (SLM)

10 1 00 11 0 00 11 1 11 M: Minuend; T: Subtrahend; W: Previous Borrow; D: Difference; B: Resulting Borrow. The Electronic Device that is designed to perform Full-Subtraction is called FULL- SUBTRACTOR. Example: Figure 5.15: Full Subtractor Subtract 1010 from 1111: Decimal Value Solution: Minuend 1111 15 Subtrahend 1010 10 Difference 0101 05 In the present-day computers, the method of direct subtraction is not adopted; the method of subtraction by complementing is used instead. The principle of subtraction by complementing can be illustrated in example 5.3 Subtract (46)10 from (87)10 by complementing method. Solution: Minuend = 87. Subtrahend = 46. Complement of the Subtrahend = (99 — 46) = 53. 90 CU IDOL SELF LEARNING MATERIAL (SLM)

Add the minuend and the complement of the subtrahend 87 + 53 = It is found that the result has an extra digit (i.e.) while the Minuend and the Subtrahend are of 2 digits, the results is of 3 digits. The extra digit (i.e.) the most significant digit in the result is called END AROUND CARRY (EAC). This is removed and added to the least significant bit in the result itself to get the actual difference. In the above case, the magnitude of the Subtrahend is less than that of the Minuend. Example 5.1 describes a case where the magnitude of the Subtrahend is greater than that of the Minuend. Example 5.1: Subtract (75) from (54) by method of complementing. Solution: Minuend = 54. Subtrahend = 75. Complement of Subtrahend = (99 — 75) = 24. Adding minuend and complement of the subtrahend the result is 54 + 24 = 78. There is no EAC in the result. So the actual difference will be got by complementing the result as follows and prefixing a negative sign to it. Complement of the result (99 — 78) = 21. Prefixing a — sign, the difference = —21. The same procedure as the above is followed when subtraction by complementing is done with the Minuend and the Subtrahend in the Binary form except that they are stored in The SIGN- Magnitude form. Sign Magnitude Representation of Numbers While storing numbers in the Memory and in the General Purpose Registers, to indicate whether it is a positive or negative number, the Most Significant Bit of the number is used as the sign bit. If this bit is 1, the number is negative; else (i.e.) if it is 0, it is positive. For example, if the contents of an Eight-Bit Register is: 1 0 1 0 0 0 0 1 the number stored is -33. If it is: 0 0 1 0 0 0 0 1, the number is 33. 91 CU IDOL SELF LEARNING MATERIAL (SLM)

Different Methods of Complementing There are 3 methods of complementing a Binary number, namely:  l’s Complementing  2’s Complementing, and  Characteristic method The l’s Complement of a Binary number is obtained by replacing the ls in it by O’s and O’s by ls. Example: Find the l’s complement of 1 0 1 0 1 0 0 1. Binary Subtraction by 1’s Complementing The procedure for subtraction of a Binary number from another Binary number will be as follows:  Store both the Minuend and the Subtrahend in the Sign-Magnitude form.  Get the l’s complement of the Subtrahend, including its sign bit.  Add the l’s complement of the Subtrahend with the Minuend.  Check the result to find whether there is an EAC in it. If there is, remove it and add it to the Least Significant Digit of the result, to give the actual difference.  If there is no EAC, ls complement the result, to get the actual difference. Example: Show how 5 is subtracted from 7, in Binary form, by l’s complementing method.\\ Example: Show how 7 is subtracted from 5 in the Binary form using l’s complement method. 92 CU IDOL SELF LEARNING MATERIAL (SLM)

Subtraction Circuit For complementing a Binary digit, a device called INVERTOR or NOT-Gate is used Figure 5.16: Invertor The circuit for Subtraction by l’s complement method will have as many Full-Adders as the number of bits in the register including the sign bit. A Full-Adder is used even for the least significant bits since EAC, if any, has to be added with them. Investors are used one for each digit to complement the digits of the subtrahend. The complemented digits of the subtrahend are added with the corresponding bits of the Minuend by the Full-Adders (refer Fig. 5.17). 93 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.17: Binary subtractor Subtraction by 2’s Complementing The 2’s complement of a Binary number is obtained as follows: i. Write its l’s complement; and ii. Add 1 to its Least Significant Bit. Example: Write down the 2’s complement of the Binary number 1010. Alternate Method for 2’s Complementing: There is another method of getting the 2’s complement of a Binary number. The method is: “Scan the Binary number from right to left and complement all the bits appearing after the first ‘1’ bit”. The below example illustrates this method. Example: Give the 2’s complement of the Binary number 10 101010. Solution: 94 CU IDOL SELF LEARNING MATERIAL (SLM)

Scanning the given number from right to left the first 1 bit that comes is next to the Least Significant Bit. Write down this 1 and the O’s to the right of it as they are and complement all the bits to its left: The result will be 01010110. Rules for Subtraction by 2’s Complementing The steps for Subtraction of a Binary number from another Binary number by 2’s comple-menting method are  2’s complement the subtrahend.  Add the 2’s complement of the Subtrahend with the Minuend.  Check the Sign Bit in the result.  If it is 0, the result will directly give the difference. (The magnitude of the Minuend will be greater than that of the Subtrahend in this case)  Else, if the Sign Bit is 1, 2’s complement the result to get the actual difference. Note: The Sign Bit is not to be complemented in 2’s complementing. Example: Assuming a 6 Bit configuration, inclusive of Sign Bit show how 14 is subtracted from 23 by 2’s complementing method. Example: Assuming a 6 Bit configuration, inclusive of the Sign Bit, show how 23 is subtracted from 15, by 2’s complementing method. 95 CU IDOL SELF LEARNING MATERIAL (SLM)

iii. Combined Adder Sub-Tractor Unit: In most of the present-day computers, the same unit is used to perform Addition and Sub­traction. The subtraction will be by 2’s complement method. Such a unit is called Combined Adder-Sub-tractor unit, (refer Fig. 5.18) Figure 5.18: Combined adder/subtractor The circuit contains 2 AND-GATES and an OR-GATE. An And-Gate is an Electronic device that can give an output only if there are minimum 2 inputs. An Or-Gate is an Electronic device which can give an output if there is even one input only. The Augend or the Minuend is stored in the register marked as X-Reg. The Addend or the Subtrahend is stored in the other register called as Y-Reg. If the operation is addition, an Add-Pulse is generated. On a clock pulse, the bits in the 2 registers will be shifted one by one to the right. The bits from the X-Register will be transferred to the Full-Adder. The bits from the Y-Register will go through the And-Gate-2 and the Or-Gate to the Full-Adder. The Result will go to the Result-Register. In case the operation is a subtraction, there will be a Subtract-Pulse, in which case the bits from Y-Register will be 2’s complemented and will be transferred through the And-Gate-1 96 CU IDOL SELF LEARNING MATERIAL (SLM)

and the Or-Gate to the Full-Adder. In both cases, the result will be available in the Result Register. The Carry flip-flop will function just as in a serial Adder circuit. Subtraction by the Characteristic Method This method is used in the computers that use a 6 Bit sign-magnitude method of storing the Integer numbers. In this method, both the Minuend and the Subtrahend are expressed in the CHARACTERISTIC form. The Characteristic form of a Binary Number is its Binary Expression; in excess of 32. For example, the Characteristic form of 17 is: 110001 which is 49(17 + 32). Similarly, -15 will be: 010001 which is 17(—15 + 32), in the Characteristic form. In this method of subtraction, there is no need to find which is the subtrahend or the negative number, since both the numbers are to be expressed in the Characteristic form. It will be found that, for a positive number, the magnitude bits are the same both in the Binary and the Characteristic forms. For the negative number, the magnitude bits in the Characteristic form will be the 2’s complement of the magnitude bits in the Binary form. In this method, the steps are:  Express both the minuend and the subtrahend in the characteristic form.  Add both of them in their characteristic form.  Check whether the sign bit is present in the result. If it is not present, the result itself gives the difference.  If the sign bit is present 2’s complement the result to get the actual difference. The below two examples illustrates these steps. Example: Illustrate how 15 can be subtracted from 28 in the characteristic method. Example: Illustrate how 15 can be subtracted from 28 in the characteristic method. 97 CU IDOL SELF LEARNING MATERIAL (SLM)

5.6 SHIFT OPERATIONS If is often necessary to align bits in a certain position in a word. The shift operations allow bits to be moved to the left or right in a word. There are three types of shift operations: logical, rotate and arithmetic. A logical shift moves bits to the left or right. The bits which 'fall off' the end of the word are discarded and the word is filled with 0's from the opposite end. A logical right shift of the 8 bit binary number 1000 1011 gives 0100 0101, as shown below. Shift instructions include a repeat value, which is the number of times the single bit shift operation is repeated. A rotate operation is a circular shift in which no bits are discarded. A rotate right of the 8 bit binary number 1000 1011 gives 1100 0101, as shown below. A right rotation by n bits of an n bit word returns the original word unchanged. A right rotation by n-1 bits is equivalent to a left rotation of 1 bit. The left rotation instruction is redundant because a left rotation of j bits is equivalent to a right rotation of n-j bits. On positive integers, a logical left shift is equivalent to multiplication by 2 and a logical right shift is equivalent to division by 2. The arithmetic shift extends this operation to negative 2's complement integers. An arithmetic right shift is similar to a logical right shift, except that the leftmost bits are filled with the sign bit of the original number instead of 0's. An arithmetic right shift of the 8 bit number 1000 1011 gives 1100 0101, as shown below: 98 CU IDOL SELF LEARNING MATERIAL (SLM)

Observe that in 8 bit 2's complement 1000 1011 equals decimal -117 and the result after the arithmetic right shift is 1100 0101, which equals decimal -59. The SAL shift instructions are: There are no Pascal operations equivalent to these shift operations. Shift operations may be combined with logical operations to extract and align bit fields. For example, the exponent of an IEEE floating point number, F, may be extracted as follows. And E, F, 0x7F800000 # mask the exponent field Srl E, E, 23 # shift exponent to the right Sub E, E, 127 # convert from biased-127 In this example, E and F are both words. Values in memory may be converted to hexadecimal using mask and shift operations. For example, the leftmost hexadecimal digit in a word, I, may be printed as follows. .data I: .word # the number to be printed T: .word # temporary to hold hex digit C: .byte # hex digit in ASCII .text __start: Get I # read a number And T, I, 0xF0000000 # mask leftmost hex digit Rol T, T, 4 # rotate to bits 0-3 Move C, T # truncate to byte Add C, C, '0' # convert to ASCII Ble C, '9', print # check for A-F Add C, C, 7 # convert A-F to ASCII Print: put C # print hex digit Done 99 CU IDOL SELF LEARNING MATERIAL (SLM)

By adding a loop which rotates I by 4 bits to the left on each iteration, an entire word may be printed in hexadecimal form. 5.7 SUMMARY  In computer central processing units, micro-operations (also known as micro-ops) are the functional or atomic, operations of a processor. These are low level instructions used in some designs to implement complex machine instructions.  These micro-operations, as the name suggests transfer information from one register to another. The information does not change during these micro-operations.  The transfer of information from memory to outside environment i.e., I/OInterface is called a read operation. The transfer of new information to be stored inmemory is called a write operation. These kinds of transfers are achieved via asystem bus. It is necessary to supply the address of the memory location formemory transfer operations.  Logic operations are basically binary operations, which are performed on the string of bits stored in the registers. For a logic micro-operation each bit of a register is treated as a variable.  Shift is a useful operation, which can be used for serial transfer of data. Shift operations can also be used along with other (arithmetic, logic, etc.) operations. For example, for implementing a multiply operation arithmetic micro- operation (addition) can be used along with shift operation. 5.8 KEYWORDS  Decoder - Decoder is a combinational circuit that has 'n' input lines and maximum of 2n output lines. One of these outputs will be active High based on the combination of inputs present, when the decoder is enabled. That means decoder detects a particular code.  Multiplexer is a combinational circuit that has maximum of 2n data inputs, 'n' selection lines and single output line. One of these data inputs will be connected to the output based on the values of selection lines. ... So, each combination will select only one data input. Multiplexer is also called as Mux.  Modular programming is the process of subdividing a computer program into separate sub-programs. A module is a separate software component. It can often be used in a variety of applications and functions with other components of the system 100 CU IDOL SELF LEARNING MATERIAL (SLM)