Computer Organization and Architecture 2019-20 question paper

Computer architecture describes the attributes of a computer that a programmer can see and use. These are the instruction set, the number of bits used for data, the addressing modes, the registers and the way input and output is handled. It answers the question "what does the machine do?".

For example, whether a processor has a multiply instruction is an architectural decision. How that instruction is built with gates and circuits is not part of architecture. That is the job of computer organization. The same architecture can therefore be built with different organizations, as in the Intel x86 family over many years.

A computer has five basic functional units: the input unit, the memory unit, the arithmetic and logic unit (ALU), the control unit, and the output unit. The ALU and the control unit together form the CPU.

Input devices bring data and programs into memory. The control unit fetches each instruction from memory and sends signals to the other units. The ALU performs arithmetic and logic operations. Results go back to memory and then to the output unit, such as a monitor or printer.

To subtract a smaller number from a larger one with 2's complement, we add the 2's complement of the smaller number to the larger number. The final carry out is thrown away.

The 2's complement of $101011$ is found by inverting every bit, which gives $010100$, and then adding 1:

$$010100 + 1 = 010101$$

Now add this to the larger number:

$$111001 + 010101 = 1,001110$$

The extra carry bit $1$ on the left is discarded. Therefore the answer is $001110$, which is $14$. Check: $57 - 43 = 14$.

A multiplexer (MUX) is a selector. It has many data inputs, a few select lines and one output. The select lines decide which one input is passed to the output. A 4-to-1 MUX has 4 inputs and 2 select lines. It is used to choose one source among many, for example in a bus system.

A decoder does the opposite job. It takes an n-bit binary code and activates exactly one of its $2^n$ output lines. A 3-to-8 decoder has 3 inputs and 8 outputs. It is used to select one register, one memory chip or one device from an address.

RISC (Reduced Instruction Set Computer) uses a small set of simple instructions. CISC (Complex Instruction Set Computer) uses many powerful, complex instructions.

A microinstruction is one word stored in the control memory. It holds the control signals for one step. There are two main types.

• Horizontal microinstruction: each control signal has its own bit. The word is long, but many signals can be active together, so it is fast.
• Vertical microinstruction: the bits are encoded into small fields. A decoder gives the signals. The word is short, but decoding makes it slower.

Some books also mention a third type, the nanoinstruction, used in a two-level control store.

SRAM (static RAM) stores each bit in a flip-flop made of about six transistors. It keeps the data as long as power is on and needs no refresh. It is fast but costly and takes more space, so it is used for cache memory.

DRAM (dynamic RAM) stores each bit as charge on a tiny capacitor with one transistor. The charge leaks, so every row must be refreshed within a few milliseconds. DRAM is slower, cheaper and denser, so it is used for main memory.

In 2D organization the cells form one array of rows and columns. A single decoder takes all $n$ address bits and drives one of $2^n$ word lines, so a whole word is selected at once. The decoder becomes very large for big memories.

In 2 1/2D organization the address is split into a row part and a column part. Two small decoders (row and column) select the cell, so each needs only about $2^{n/2}$ outputs. The total decoder size is much smaller, which makes it cheaper and the usual choice in real chips.

An I/O control method is the way the CPU manages data transfer between itself and an input/output device. It decides who starts the transfer and who moves the data.

There are three main methods:

• Programmed I/O: the CPU runs a program that checks the device status again and again and moves each word itself.
• Interrupt-initiated I/O: the device sends an interrupt signal when it is ready, so the CPU can do other work meanwhile.
• Direct Memory Access (DMA): a DMA controller moves blocks of data between the device and memory without the CPU handling each word.

Bus arbitration is the method used to decide which device gets control of a shared bus when two or more devices want it at the same time. Only one device, called the bus master, can drive the bus at any moment.

The arbiter looks at all the requests. It then grants the bus to one device according to a rule such as fixed priority or rotating priority. When the master finishes its transfer, it releases the bus and the arbiter grants it to the next requester. This prevents two devices from sending data together and corrupting it.

In infix notation the operator is written between its two operands, as in $A + B$. In reverse Polish notation (RPN), also called postfix, the operator comes after its operands, as in $A,B,+$. RPN needs no brackets because the order of operators is fixed by their position. This is why stack machines use it.

A computer can evaluate a postfix string in one left-to-right scan, without looking back or worrying about priorities. This makes the compiler's work simple and the hardware fast. Humans find infix easier to read, so the compiler converts infix to postfix before generating code.

To convert, we follow the normal precedence rules. Multiplication and division are done before addition and subtraction. Operators of equal rank are done from left to right. Brackets are done first.

(i) $AB+CD+E*F$

There are three products and two additions. The products are done first, so we write each of them in postfix form.

$$AB \rightarrow AB$$

$$CD \rightarrow CD$$

$$EF \rightarrow EF$$

The expression is now (AB*) + (CD*) + (EF*). The additions go from left to right. The first addition joins the first two products.

$$AB*;CD*;+$$

The second addition joins this result with the third product.

$$AB*;CD*;+;EF*;+$$

Therefore the RPN is $ABCD+EF*+$.

(ii) $A[B+CD+E]/F*(G+H)$**

The question has a printed typing error in the middle ("CCD"). We take the intended expression as $A[B+CD+E]/F(G+H)$.

Inside the square bracket, the product is done first, so $CD$ becomes $CD$. Then the two additions go from left to right.

$$B+CD+E \rightarrow B,CD,+,E,+$$

Call this bracket $X$. The brackets $(G+H)$ become $GH+$. The remaining expression is $AX/F(GH+)$. Multiplication and division have the same rank, so they go from left to right. First comes $A*X$, then the division by $F$, then the product with $GH+$.

$$AX \rightarrow A,X,$$

$$AX*/F \rightarrow AX*,F,/$$

$$AXF/(GH+) \rightarrow AXF/,GH+,$$

Putting $X = BCD*+E+$ back, we get the final answer.

$$ABCD*+E+F/GH+$$

I checked both results with a small stack-based conversion program, and they match.

A quick check of part (ii) also works. Take $A=2, B=1, C=2, D=3, E=4, F=2, G=5, H=1$. The infix value is $2*(1+6+4)/26 = 66$. Scanning $2,1,2,3,,+,4,+,,2,/,5,1,+,$ with a stack also leaves 66.

Let us check part (i) with numbers. Take $A=2, B=3, C=4, D=5, E=6, F=7$. The infix value is $23 + 45 + 67 = 6 + 20 + 42 = 68$. Now evaluate $2345*+67*+$ with a stack.

$$\text{push }2,3 \rightarrow \text{multiply} \rightarrow 6$$

$$\text{push }4,5 \rightarrow \text{multiply} \rightarrow 20 \rightarrow \text{add} \rightarrow 26$$

$$\text{push }6,7 \rightarrow \text{multiply} \rightarrow 42 \rightarrow \text{add} \rightarrow 68$$

Both methods give 68, so the conversion is correct. The same idea gives zero-address instructions in a stack computer.

To verify an RPN string by hand, scan from left to right. Push each operand on a stack. When an operator comes, pop two operands, apply the operator and push the result back. At the end one value remains, which is the value of the expression.

A ripple carry adder is slow because each full adder waits for the carry of the stage before it. For $n$ bits, the delay grows with $n$. A carry look-ahead adder (CLA) removes this wait. It calculates every carry directly from the inputs, at the same time.

For each bit position $i$ we define two signals. The generate signal $G_i = A_i B_i$ says that this stage makes a carry on its own. The propagate signal $P_i = A_i \oplus B_i$ says that this stage passes an incoming carry forward. The sum and the next carry are then:

$$S_i = P_i \oplus C_i$$

$$C_{i+1} = G_i + P_i C_i$$

If we keep replacing the earlier carry in this equation, every carry depends only on $G$, $P$ and $C_0$:

$$C_1 = G_0 + P_0 C_0$$

$$C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0$$

$$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$$

$$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$$

Each of these is a two-level AND-OR circuit. So all four carries appear after the same two gate delays, no matter which bit it is. The 4-bit CLA is built from these parts: four half-adder style gates that make $P_i$ and $G_i$, one look-ahead logic block that holds the four equations above, and four XOR gates that make the sums.

 A3B3  A2B2  A1B1  A0B0
  |     |     |     |
 [P,G] [P,G] [P,G] [P,G]   (AND gate gives G, XOR gives P)
  |     |     |     |
 +-----------------------+
 |  look-ahead carry     |<-- C0
 |  logic (C1, C2, C3,C4)|--> C4
 +-----------------------+
  |C3   |C2   |C1   |C0
 [XOR] [XOR] [XOR] [XOR]    (S = P xor C)
  |     |     |     |
  S3    S2    S1    S0

Example. Add $A = 1011$ and $B = 0110$ with $C_0 = 0$. The bitwise values, from bit 0 to bit 3, are:

Using the look-ahead equations with $C_0 = 0$:

$$C_1 = G_0 + P_0 C_0 = 0$$

$$C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0 = 1$$

$$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0 = 0 + 1 + 0 + 0 = 1$$

$$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + \dots = 0 + 0 + 1 + 0 + 0 = 1$$

The sum bits are $S_i = P_i \oplus C_i$. This gives $S_0 = 1 \oplus 0 = 1$, $S_1 = 0 \oplus 0 = 0$, $S_2 = 1 \oplus 1 = 0$ and $S_3 = 1 \oplus 1 = 0$. With the final carry $C_4 = 1$, the result is $10001$. Therefore $11 + 6 = 17$, which matches.

Speed. Making $P$ and $G$ takes one gate delay, the look-ahead block takes two, and the last XOR takes one. The total is about 4 gate delays for any $n$ that fits in one block. A 4-bit ripple adder needs about 8. The cost is more gates, and the AND-OR gates need more inputs as $n$ grows, so large adders use several 4-bit CLA blocks joined in groups.

(i) Timing diagram of the instruction cycle

The CPU repeats the instruction cycle for every instruction. It has a fetch phase, a decode phase, an execute phase, and an interrupt check when needed. A timing diagram shows which register transfer happens at which clock pulse.

The fetch part takes three clock pulses (T0 to T2). The decode part takes one more (T3). The execute part follows. The register transfers are given below.

$$T_0:; AR \leftarrow PC$$

$$T_1:; IR \leftarrow M[AR],; PC \leftarrow PC + 1$$

$$T_2:; D_0,\dots,D_7 \leftarrow \text{decode } IR(12\text{-}14),; AR \leftarrow IR(0\text{-}11),; I \leftarrow IR(15)$$

At T0 the address of the next instruction goes from the program counter (PC) to the address register (AR). At T1 the instruction is read from memory into the instruction register (IR), and PC moves on to the next address. At T2 the opcode is decoded and the address field is saved in AR. The mode bit I tells if the address is direct or indirect.

In the next clock pulse, if the instruction is indirect, the effective address is read as $AR \leftarrow M[AR]$ at T3. Then the execute phase starts with the timing signals T4, T5, T6 and so on. For example, for an ADD instruction the steps are:

$$T_4:; DR \leftarrow M[AR]$$

$$T_5:; AC \leftarrow AC + DR,; SC \leftarrow 0$$

Setting the sequence counter SC to zero at the end starts the next fetch at T0. The sequence counter (SC) is the small counter that produces the timing signals T0, T1, T2 and so on.

(ii) Subroutine

A subroutine is a group of instructions that does one job and can be used many times from different places in a program. It saves memory because the code is written once. The main program uses a CALL instruction to run it. The CALL stores the return address, which is the address of the next instruction, usually on the stack. Then it loads the subroutine address into PC. At the end, a RETURN instruction pops the saved address back into PC. The main program then continues from where it left off.

$$SP \leftarrow SP - 1,; M[SP] \leftarrow PC,; PC \leftarrow \text{subroutine address}$$

Because the return address is on a stack, subroutines can call other subroutines, and even themselves (recursion).

Interrupt and sub cycles. Before each fetch, the CPU also checks if an interrupt is pending. If the interrupt flip-flop is set, the CPU saves the return address, usually in memory location 0, and jumps to the interrupt service routine. So the full cycle is fetch, decode, read the effective address if indirect, execute, and then the interrupt check. Each of these is a sub cycle, and each is driven by the timing signals from the sequence counter.

Why the timing diagram matters. It shows exactly in which clock pulse each register is loaded. The control unit uses these timing signals together with the decoded opcode to produce the control signals. Memory reads and writes also fit inside these pulses, so the whole machine stays in step with one clock.

Virtual memory is a technique that lets a program use an address space larger than the real main memory. The programmer writes addresses in a big virtual (logical) address space. The hardware and the operating system keep only the needed parts in main memory and the rest on disk. The program feels that a large, continuous memory is available.

It is useful for three reasons. A program bigger than RAM can still run. Many programs can stay in memory together. The programmer need not care where the program is loaded.

How paging helps

In paging, the virtual address space is cut into equal fixed-size blocks called pages. The main memory is cut into blocks of the same size called frames. Any page can be placed in any free frame. So there is no external fragmentation, and finding space is easy. Only the pages in use are brought into memory, and this is called demand paging.

Address translation

A virtual address has two parts: the page number and the offset inside the page. A table called the page table is kept in main memory. It has one entry per page. Each entry holds the frame number, a valid (present) bit, a modified bit and protection bits. The page number selects the entry. If the valid bit is 1, the frame number is joined with the offset to form the physical address.

Virtual address        Page table            Physical address
+-----------+--------+                      +-----------+--------+
| page no.  | offset |                      | frame no. | offset |
+-----------+--------+                      +-----------+--------+
      |         |         +-------------+        ^           ^
      +-------->+-------->| valid|frame |--------+           |
                |         +-------------+                    |
                +--------------------------------------------+

For example, take a page size of 4 KB, so the offset has 12 bits. In a 32-bit virtual address the page number has 20 bits. The virtual address $\text{0x00003ABC}$ has page number 3 and offset $\text{0xABC}$. If page 3 sits in frame 7, then the physical address is $\text{0x00007ABC}$.

Page fault

If the valid bit is 0, the page is not in memory and a page fault occurs. The operating system finds the page on disk and picks a free frame. If no frame is free, it removes a victim page using a replacement rule such as FIFO or LRU. A modified victim is first written back to disk. The new page is loaded, the page table is updated and the instruction is restarted.

Speeding up with a TLB

Reading the page table costs one extra memory access for every reference. A small, fast cache of recent translations, called the translation lookaside buffer (TLB), avoids most of these extra accesses.

Merits and limits

Paging gives a large virtual space, easy memory sharing and protection, and good memory use. Its costs are the space taken by page tables and the time lost when page faults are frequent. Too many faults cause thrashing, where the system spends more time moving pages than doing useful work.

Direct Memory Access (DMA) is a method in which an I/O device transfers a block of data directly to or from main memory without passing each word through the CPU. A special hardware unit called the DMA controller takes charge of the memory buses for the duration of the transfer. This is much faster than programmed or interrupt-driven I/O, because the CPU does not execute instructions for every word.

How the DMA controller is organised

The controller has an address register, a word count register, a control register and a data buffer. It also has request and grant lines to the CPU and the device.

The address register holds the memory location of the next word. The word count register holds the number of words still to move. The control register holds the direction (read or write) and the mode of transfer.

How a transfer takes place

First, the CPU initialises the controller. It writes the starting memory address into the address register, the number of words into the word count register, and the direction into the control register. After this the CPU carries on with other work.

When the device is ready, it raises a DMA request to the controller. The controller then sends a bus request (HOLD) to the CPU. The CPU finishes its current bus cycle, floats its address, data and control buses to the high impedance state, and replies with a bus grant (HLDA).

Now the controller owns the buses. It puts the address from its address register on the address bus. It then activates the memory read or write signal and the DMA acknowledge to the device. The word moves directly between the device and memory.

After each word the controller increments the address register and decrements the word count register. This repeats until the count becomes zero.

When the count reaches zero, the controller releases the buses by removing the bus request. It also sends an interrupt to the CPU to say that the whole block has been transferred. The CPU then resumes normal control of the buses.

Modes of DMA transfer

In burst (block) mode, the controller keeps the bus until the whole block is moved. In cycle stealing mode, it takes the bus for one word at a time and gives it back, so the CPU is slowed only slightly. In transparent mode, it uses the bus only when the CPU is not using it.

Advantages

DMA gives a high transfer rate and frees the CPU from word-by-word work. It is the best method for fast devices like disks. Its cost is the extra hardware of the controller.

A small example

Suppose a disk must write 512 words into memory starting at address 2000. The CPU loads 2000 into the address register and 512 into the word count register, sets the direction to "write to memory", and starts the controller. The CPU then runs another program. The controller moves all 512 words, one after another, and finally interrupts the CPU. The CPU spent time only on the set-up and on the final interrupt, not on 512 separate transfers.

The addressing mode tells the CPU how to find the operand of an instruction from the address field. An instruction has an opcode and an address field. The mode decides whether the address field itself is the operand, or a memory address, or a register number. The final address of the operand in memory is called the effective address (EA).

Main addressing modes

In the implied mode, the operand is fixed by the opcode. For example, "complement accumulator" works on AC without any address field. Stack instructions such as ADD also use this mode.

In the immediate mode, the address field contains the operand itself. No memory access is needed to get it, so it is fast. It is used for constants. For example, ADD #5 adds the number 5.

In the register mode, the operand is inside a CPU register named in the instruction. For example, ADD R1 uses the value in R1. It is very fast and needs few bits.

In the register indirect mode, the register holds the memory address of the operand. So $EA = (R1)$. This is useful for pointers.

In the autoincrement or autodecrement mode, the register works as in register indirect, but its value is increased (or decreased) automatically after (or before) the access. It is used to walk through an array.

In the direct mode, the address field is the effective address. So $EA = A$. One memory access reaches the operand.

In the indirect mode, the address field gives the location where the real address is stored. So $EA = M[A]$. It needs two memory accesses and allows pointers.

In the relative mode, the address field is added to the program counter. So $EA = PC + A$. It is used for branches and makes code position independent.

In the indexed mode, the address field is added to an index register. So $EA = A + (XR)$. It is used to access array elements.

In the base register mode, a base register holds the starting address of a block, and the address field is an offset from it. So $EA = (BR) + A$. It is used to move programs in memory.

Example

Take an instruction at address 200 whose address field (at 201) is 500. Let $R1 = 400$ and $XR = 100$. The PC has already moved to 202 after fetching.

The table shows that the same address field gives different operands in different modes. Modes make a program shorter, more flexible and easier to relocate, at the cost of more complex hardware and extra memory accesses for some modes.

A stack is a list of data items in which an item is added or removed only at one end, called the top. It works on the last-in, first-out (LIFO) rule. A register called the stack pointer (SP) always holds the address of the top item. Adding an item is a PUSH and removing one is a POP. Stack organization is used for subroutine calls, interrupts and expression evaluation.

(i) Register stack

Here the stack is a set of CPU registers. Suppose it has 64 words, so SP is a 6-bit register. A word is moved through the data register DR. Two flip-flops, FULL and EMPTY, show the state of the stack.

   +----------+
 63|          |
   |   ...    |
  3|   C      |  <- SP = 3, top is C
  2|   B      |
  1|   A      |
  0|          |
   +----------+

Initially $SP = 0$, $EMPTY = 1$ and $FULL = 0$. The PUSH operation is

$$SP \leftarrow SP + 1$$

$$M[SP] \leftarrow DR$$

$$\text{if } SP = 0 \text{ then } FULL \leftarrow 1,\ EMPTY \leftarrow 0$$

SP becomes 0 again only after the last location (63) is filled, because the 6-bit counter wraps around. The POP operation is

$$DR \leftarrow M[SP]$$

$$SP \leftarrow SP - 1$$

$$\text{if } SP = 0 \text{ then } EMPTY \leftarrow 1,\ FULL \leftarrow 0$$

A push is not allowed when FULL is 1, and a pop is not allowed when EMPTY is 1. A register stack is very fast, but its size is small and fixed.

(ii) Memory stack

Here a part of main memory is used as the stack. Three segments exist in memory: the program, the data and the stack. The program counter points to the program, an address register points to the data, and SP points to the top of the stack. The stack usually grows towards lower addresses. Suppose SP starts at 4001 and the stack uses the addresses 4000 down to 3000. The PUSH operation is

$$SP \leftarrow SP - 1$$

$$M[SP] \leftarrow DR$$

The POP operation is

$$DR \leftarrow M[SP]$$

$$SP \leftarrow SP + 1$$

Here the limits are checked by comparing SP with the two end addresses. The stack can be large and the size can be changed, but every push and pop needs a memory access, so it is slower than a register stack.

Example of memory stack use

Start with $SP = 4001$. Push the values 10 and then 20. After the first push SP is 4000 and M[4000] holds 10. After the second push SP is 3999 and M[3999] holds 20. A pop now returns 20, the last item pushed, and SP goes back to 4000. This shows the LIFO rule.

Difference in short

Both kinds help to evaluate expressions written in reverse Polish notation. Operands are pushed. An operator pops two values and pushes the result. No address field is needed, so the instructions are zero-address instructions.

IEEE 754 single precision uses 32 bits: 1 sign bit, 8 exponent bits (bias 127) and 23 fraction bits. A normalised number is written as $(-1)^s \times 1.f \times 2^{e}$. The stored exponent is $E = e + 127$. The leading 1 is not stored, because every normalised number starts with 1, so keeping it would waste a bit.

The bias 127 is added so that the exponent field is always a positive number. This lets two floating point numbers be compared like plain integers. The exponent patterns $00000000$ and $11111111$ are kept for zero, denormal numbers, infinity and NaN (not a number). So normal numbers use stored exponents from 1 to 254.

The method has three parts. First, convert the number to binary. Second, normalise it to the form $1.f \times 2^e$. Third, find $E = e + 127$ and write the sign, exponent and fraction in order.

(i) 65.175

The number is positive, so the sign bit is $0$. Convert the integer and fraction parts separately. The integer part is $65 = 1000001_2$. For the fraction, multiply by 2 again and again and note the integer parts:

$$0.175 = 0.001011,0011,0011\ldots_2$$

The first digits come from $0.175 \times 2 = 0.35$ (digit 0), $0.35 \times 2 = 0.7$ (digit 0), $0.7 \times 2 = 1.4$ (digit 1), then $0.4 \times 2 = 0.8$ (digit 0), and so on. The pattern $0011$ repeats forever, so the fraction never ends.

So the number is $1000001.001011001100\ldots_2$. Move the binary point 6 places left to normalise:

$$65.175 = 1.000001001011001100\ldots_2 \times 2^{6}$$

The stored exponent is:

$$E = 6 + 127 = 133 = 10000101_2$$

The fraction needs 23 bits. We take the digits after the leading 1 and round the last bit, because the next digits are $1001\ldots$, which is more than half. The fraction is $00000100101100110011010$. Therefore:

In hexadecimal this is $\text{0x4282599A}$.

(ii) -307.1875

The number is negative, so the sign bit is $1$. The integer part is $307 = 100110011_2$. The fraction is exact:

$$0.1875 = 0.0011_2$$

So the number is $100110011.0011_2$. Move the point 8 places left:

$$307.1875 = 1.001100110011_2 \times 2^{8}$$

The stored exponent is:

$$E = 8 + 127 = 135 = 10000111_2$$

The fraction is $001100110011$ followed by 11 zeros to fill 23 bits. Therefore:

In hexadecimal this is $\text{0xC3999800}$.

To check, decode the second answer: $-1.001100110011_2 \times 2^{8} = -1.1999\ldots \times 256 = -307.1875$. The first answer is the nearest 32-bit value to $65.175$, so it has a tiny rounding error of the order of $10^{-6}$. This is normal, because $0.175$ cannot be written exactly in binary.

The numbers are two 8-bit unsigned integers, $10110011 = 179$ and $11010101 = 213$. Booth's algorithm works on signed numbers. So we first add a 0 on the left of each number. That makes them 9-bit non-negative numbers with the same value. The product then needs 18 bits.

The multiplicand is $M = 010110011$ and the multiplier is $Q = 011010101$. We also need $-M$, found by taking the 2's complement of $M$:

$$-M = 101001101$$

Registers $A$ (9 bits) and $Q_{-1}$ start at 0. In each cycle we look at the pair $Q_0 Q_{-1}$. If it is $10$, we do $A = A - M$. If it is $01$, we do $A = A + M$. If it is $00$ or $11$, we do nothing. Then we shift $A$, $Q$ and $Q_{-1}$ one place right, keeping the sign bit of $A$ (arithmetic shift right, ASR). We repeat this 9 times.

After 9 cycles, the product is held in $A$ and $Q$ joined together:

$$AQ = 001001010,011101111$$

This is the 18-bit number $001001010011101111_2$. Its value is:

$$2^{15} + 2^{12} + 2^{10} + 2^{7} + 2^{6} + 2^{5} + 2^{3} + 2^{2} + 2^{1} + 2^{0} = 38127$$

Therefore $10110011 \times 11010101 = 38127$. Check: $179 \times 213 = 38127$, so the working is correct.

The reason Booth's method helps here is that runs of 1s in the multiplier are handled by one subtraction at the start of the run and one addition after its end. The multiplier $011010101$ has many isolated 1s, so there are many operations. Even so, the answer is correct for every pattern.

Parallelism

Parallelism means doing more than one job at the same time. It is used to make a computer faster. It can be at the instruction level (pipelining), at the processor level (many CPUs), or at the data level (vector and array processors). A simple example is a kitchen where one person chops, one cooks and one serves at the same time.

Pipelining

Pipelining is a method where the work of one instruction is split into stages, and many instructions are in different stages at the same time. Each stage has its own hardware. Like a car assembly line, a new instruction enters the pipeline in every clock cycle, while older ones move forward.

A simple instruction pipeline has these stages:

• IF: instruction fetch.
• ID: instruction decode and register read.
• EX: execute in the ALU.
• MEM: memory access.
• WB: write back the result.

The diagram shows that in clock cycle 5 five different instructions are being worked on, one in each stage. Without pipelining, the next instruction would have to wait until the whole of the earlier one finishes.

Speedup. Let $k$ be the number of stages, $n$ the number of instructions and $t_p$ the clock time of one stage. Then:

$$T_{pipelined} = (k + n - 1),t_p$$

$$T_{non\text{-}pipelined} = n,k,t_p$$

$$S = \frac{n,k,t_p}{(k + n - 1),t_p} = \frac{nk}{k + n - 1}$$

When $n$ is very large, the speedup tends to $k$. So a five-stage pipeline can be at most about five times faster.

Problems. Pipelines lose speed because of hazards:

• Structural hazard: two stages need the same hardware at once.
• Data hazard: an instruction needs a result that an earlier one has not produced yet.
• Control hazard: a branch changes the flow, so the fetched instructions may be wrong.

These are handled by stalls, forwarding (bypassing) and branch prediction.

Difference. Parallelism is the wider idea of many things happening together. Pipelining is one way to get it, using overlapped stages inside one processor. Pipelining does not shorten the time of one instruction, but it raises the throughput, that is, the number of instructions finished per second.

Example. Take a five-stage pipeline and 100 instructions, with the same clock time for every stage. Then the speedup is:

$$S = \frac{nk}{k + n - 1} = \frac{100 \times 5}{5 + 100 - 1} = \frac{500}{104} \approx 4.81$$

This is close to the ideal value of 5.

Types of parallelism in short. Instruction-level parallelism overlaps instructions inside one CPU, for example pipelining and superscalar issue. Thread-level parallelism runs different threads on different cores. Data-level parallelism applies one operation on many data items together, as in vector processors and GPUs. A real computer today often uses all three.

Where pipelining is used. Besides the instruction pipeline, there are arithmetic pipelines, for example for floating point addition, which split the work into stages such as exponent compare, align, add and normalize.

In a microprogrammed control unit the control signals are not made by logic gates. They are stored as words, called microinstructions, in a special memory. A set of microinstructions that carries out one machine instruction is a microprogram or routine.

Main components

• Control memory: a fast ROM that holds all the microprograms. One word is one microinstruction.
• Control address register (CAR): holds the address of the next microinstruction to read.
• Control data register (CDR) or pipeline register: holds the microinstruction just read, so the next address can be prepared while this one is used.
• Next address generator (sequencer): works out the next value for CAR. It can increment CAR, load a branch address, load an address from the opcode, or return from a subroutine.
• Decoders and control outputs: the fields of the microinstruction go out as control signals to the ALU, registers and memory.

Format of a microinstruction. It usually has three parts. The first is the micro-operation field, which gives the control signals. The second is the condition field, which selects a status bit to test. The third is the branch address field, which gives the next address when the condition is true.

Working

First, the opcode of the machine instruction in IR is mapped to the starting address of its microprogram. This address is loaded in CAR. Then the microinstruction at that address is read from the control memory into CDR. Its micro-operation field is sent out as control signals, so the hardware does that step. At the same time the sequencer finds the next address. If there is no branch, CAR is increased by one. If the condition is true, the branch address is loaded. This repeats until the last microinstruction, which sends the control back to the fetch routine for the next instruction.

Control memory sizes. For example, if the control memory has 128 words, CAR needs 7 bits, because $2^7 = 128$.

Advantages. The design is regular and easy to change. New instructions can be added by writing new microprograms, so it is flexible.

Disadvantage. It is slower than a hardwired unit, because each step needs a memory read.

Address sequencing. The sequencer has to choose the next address in four common ways. It can increment CAR for straight-line code. It can branch to an address given in the microinstruction, conditionally or not. It can map the opcode bits to a starting address, which happens at the end of the fetch routine. And it can call and return from a micro-subroutine, using a small register to save the return address. A multiplexer in the sequencer picks one of these sources.

Mapping example. If the opcode is 4 bits and each routine can have up to 4 microinstructions, the starting address can be formed as 0, opcode, 00. So opcode 0011 maps to address 0001100, which is 12. This keeps the mapping hardware very simple.

Horizontal and vertical forms. The micro-operation field may be coded one bit per signal (horizontal) or in encoded groups (vertical). This choice trades speed for control memory size.

A cache is much smaller than main memory, so the system must decide which memory block goes to which cache line. This rule is the mapping technique. There are three kinds.

Direct mapping

Each main memory block can go to exactly one cache line, given by $\text{line} = \text{block number} \bmod \text{number of lines}$. The address is split into tag, line (index) and word fields. The line field picks the cache line, and the tag is compared with the stored tag to check for a hit. For example, with a 16-bit address, 4-word blocks and 256 cache lines, the fields are tag 6, line 8 and word 2 bits.

Merits: it is simple, cheap, fast, and needs only one comparator. No replacement rule is needed. Demerits: two blocks that map to the same line keep throwing each other out, even if other lines are empty. The hit ratio can fall badly.

Associative (fully associative) mapping

A block can be placed in any cache line. The address has only a tag and a word field. In the same example the tag is 14 bits and the word is 2 bits. The tag is compared with all stored tags at the same time, using associative (content addressable) memory.

Merits: it is the most flexible. Conflict misses do not occur, and the hit ratio is the highest. Demerits: it needs one comparator per line, so the hardware is costly and slower. A replacement algorithm such as LRU or FIFO is needed.

Set-associative mapping

The cache lines are grouped into sets. A block maps to one particular set, but it can go to any line inside that set. With $k$ lines per set it is called $k$-way. In the example, a 4-way cache has $256/4 = 64$ sets, so the fields are tag 8, set 6 and word 2 bits. Only the $k$ tags of one set are compared.

Merits: it is a good middle path. It removes most conflict misses and needs only $k$ comparators. Demerits: it needs more hardware than direct mapping, and a replacement rule is still required inside each set.

Comparison

A good mapping keeps useful blocks together and avoids needless replacement. It also keeps the tag comparison cheap, because the cache must answer in one or two clock cycles.

Direct mapping is the special case of 1-way set associative, and associative mapping is the case where one set holds all the lines.

In practice, most modern processors use set-associative caches with 2, 4 or 8 ways, because this gives a hit ratio close to full associativity at a much lower hardware cost.

The chip stores $4096 \times 8$ bits, that is 4096 words of 8 bits each, or 4 KB.

Pins needed

Since $2^{12} = 4096$, the chip needs 12 address lines. It needs 8 data lines, which are bidirectional. There are 2 enable (chip select) lines and 1 read/write control line. These make

$$12 + 8 + 2 + 1 = 23$$

signal pins. Two more pins are needed for the power supply and ground, so the package has 25 pins in all.

Block diagram and labels

                 +----------------------+
  Address  12 -->|                      |
                 |    RAM 4096 x 8      |<--> Data (8)
  CS1 ---------->|                      |
  CS2 ---------->|                      |
  R/W ---------->|                      |
                 +----------------------+
                   Vcc, GND (power pins)

Inputs are the 12 address lines, the two enables CS1 and CS2, and the read/write line R/W. The 8 data lines are both input and output. The chip works only when both enables are active. Then R/W = 1 reads a word onto the data lines, and R/W = 0 writes the data lines into the addressed word. If the chip is not enabled, the data lines are in the high impedance state.

Inside the chip

The 12 address bits go to an internal decoder. The decoder selects one of the 4096 words in the cell array. The selected 8 cells are connected to the data lines through tri-state buffers. These buffers are on only when the chip is enabled, so many chips can share one data bus without clashing.

The total size follows from the pins:

$$2^{12} \times 8 = 4096 \times 8 = 32768 \text{ bits}$$

Two enable lines are given so that a larger memory can be built easily. One enable can come from the high address bits through a decoder, and the other can come from a control signal such as the memory-request line. For instance, if the chip is placed at the start of the address space, its address range is $\text{0x000}$ to $\text{0xFFF}$.

The same rule gives the pin count for any RAM chip. Address pins equal $\log_2$ of the number of words, data pins equal the word width, and a few control pins are added. A larger chip such as $8192 \times 8$ would need one more address pin, so 13, while its data pins would stay at 8.

Main feature of RAM

In a random-access memory, every location can be reached in the same time, whatever its position in the memory. The time does not depend on the address used. A RAM can be both read and written, and it is volatile, so it loses its data when power is switched off.

In a computer, the CPU must address both memory locations and I/O device registers. There are two ways to do this.

Isolated I/O keeps a separate address space for I/O. The CPU uses special instructions (IN and OUT) and a control signal such as IO/M to tell whether the address belongs to memory or to an I/O port.

Memory mapped I/O gives the I/O registers addresses from the same space as memory. The CPU uses the ordinary load and store instructions to talk to devices. No separate control signal is needed.

Difference between the two

Advantages of isolated I/O

• The whole memory address space is free for memory.
• I/O instructions stand out clearly in the program, so the code is easy to read.
• Port address decoding is simple because the number of ports is small.

Disadvantages of isolated I/O

• Only a few instructions (IN and OUT) can work with I/O, and they usually move data only through the accumulator.
• Extra control signals and extra instructions make the CPU more complex.
• Arithmetic or logic on device data cannot be done directly.

Advantages of memory mapped I/O

• All memory instructions work on I/O registers, so one can add, compare, shift or test bits of a device register directly.
• No special instructions or control pins are needed, so the CPU design is simpler.
• Many more I/O devices can be addressed.

Disadvantages of memory mapped I/O

• Device addresses take away a part of the memory space. This matters for a small address space.
• Address decoding is more complex, because the full address must be decoded for each device.
• It is harder to spot I/O operations in a program, since they look like normal memory accesses.

Which one to choose

A small processor with a limited address space and few devices often prefers isolated I/O, so that no memory addresses are lost. A modern processor with a large address space (32 or 64 bits) prefers memory mapped I/O, because the lost addresses hardly matter and the programming is far more flexible.

(i) Design of a typical I/O interface

An I/O interface is the hardware between the CPU buses and an I/O device. Devices differ from the CPU in speed, data format and signal levels. The interface hides these differences.

 CPU buses                 Interface                Device
+----------+     +-----------------------+     +----------+
| Data bus |<--->| Data register/buffer  |<--->|  data    |
| Address  |---->| Address decoder       |     |          |
| Control  |<--->| Control, status regs  |<--->| control  |
| (RD, WR) |     | Timing and control    |     | and      |
| Interrupt|<----| Interrupt logic       |     | status   |
+----------+     +-----------------------+     +----------+

The main blocks are these:

• Address decoder: it checks the address on the address bus and selects the interface when its own address is seen.
• Data register (buffer): it holds the word being moved. It lets the fast CPU and the slow device work at different speeds.
• Control register: the CPU writes commands here, such as start, stop or the direction of transfer.
• Status register: it holds flags like ready, busy and error, which the CPU can read.
• Timing and control logic: it makes the read and write signals and the handshake signals for the device.
• Interrupt logic: it raises an interrupt request when the device needs service.

The CPU reads and writes these registers like memory locations (memory mapped) or through IN and OUT instructions (isolated). The interface also converts data between parallel form (CPU) and serial form (some devices) and changes voltage levels where needed.

(ii) Interrupts and how they are handled

An interrupt is a signal that makes the CPU stop the program it is running, serve an urgent event, and then come back. It lets the CPU avoid waiting for slow devices.

When an interrupt request arrives, the CPU does the following.

First, it completes the instruction it is executing. Then it checks whether interrupts are enabled. If they are, it sends an interrupt acknowledge.

Next, it saves the return address (the program counter) and the status flags on the stack. Further interrupts are usually disabled for a moment.

Then it finds the address of the service routine. In a vectored interrupt, the device supplies a vector number that points to the routine. In a non-vectored interrupt, the CPU jumps to one fixed address, and the routine polls the devices to find the source.

The interrupt service routine (ISR) runs next. It serves the device, for example by reading the data register. It ends with a return-from-interrupt instruction.

Finally, the CPU pops the saved flags and the program counter and carries on with the interrupted program as if nothing had happened.

If several devices interrupt together, priority decides which one is served first. Priority can be set by software polling or by hardware such as a daisy chain or a priority encoder.