Computer Organization and Architecture 2020-21 question paper

Computer architecture means the attributes of a computer that are visible to the programmer. It includes the instruction set, the data formats, the addressing modes, the registers and the I/O methods. It decides what the machine can do.

Computer organization means how these features are actually built in hardware. It deals with control signals, the interfaces between units, the memory technology and the data paths. It decides how the machine does it.

For example, a multiply instruction is architecture. Whether it is done by a separate multiplier circuit or by repeated addition is organization.

Bus arbitration is the process of deciding which device becomes the bus master when several devices ask for the shared bus at the same time. Only one master can use the bus at a time.

Two types of bus arbitration exist.

• Centralized arbitration: a single arbiter or the CPU grants the bus. It has the daisy chaining method, the polling method and the independent request (parallel) method.
• Distributed arbitration: there is no central arbiter. Every device has its own arbitration logic, and the devices decide by themselves using a priority code placed on the bus.

Biasing means adding a fixed constant, called the bias, to the true exponent before storing it. The stored value is then always a positive (unsigned) number, so no sign bit is needed for the exponent. It also lets us compare two floating point numbers using plain integer comparison.

In IEEE 754 single precision the bias is 127, so $E = e + 127$. In double precision the bias is 1023. For example, a true exponent of $-3$ is stored as $-3 + 127 = 124$, and a true exponent of $5$ is stored as $132$.

The restoring method is a way of dividing two binary numbers by repeated subtraction and shifting. Register $A$ starts at 0, $Q$ holds the dividend and $M$ holds the divisor.

In each of $n$ cycles, we shift $A$ and $Q$ left by one bit. Then we subtract $M$ from $A$. If the result is negative, the subtraction was too large. So we set $Q_0 = 0$ and add $M$ back to $A$, which restores the old value. If the result is not negative, we set $Q_0 = 1$.

After $n$ cycles, $Q$ holds the quotient and $A$ holds the remainder. For example, $7 \div 3$ gives quotient $2$ and remainder $1$.

A micro operation is a small, basic operation done on data stored in registers in one clock pulse. Examples are shifting a register, adding two registers, or loading one register from another, written as $R1 \leftarrow R2 + R3$.

Microcode is the set of microinstructions stored in the control memory of a microprogrammed control unit. Each microinstruction holds the control signals for some micro operations. A group of microinstructions makes a microprogram, which carries out one machine instruction. Microcode sits between the hardware and the machine language.

RISC means Reduced Instruction Set Computer. It is a design in which the CPU uses a small set of simple instructions, and each one is executed in a single clock cycle.

Main features:

• Fixed-length instructions and a few addressing modes.
• Only LOAD and STORE instructions touch memory. All other work is done on registers.
• A large register file, often with register windows.
• A hardwired control unit, which is fast.
• Pipelining works well, since the instructions are simple.

RISC needs more instructions for a job, but each is quick. Examples are ARM, MIPS and SPARC.

Hit ratio is the fraction of memory accesses that find the needed data in the cache.

$$\text{Hit ratio } H = \frac{\text{number of hits}}{\text{total number of accesses}}$$

For example, if the CPU makes 1000 accesses and 950 are found in the cache, then $H = 950/1000 = 0.95$. The miss ratio is $1 - H = 0.05$. A higher hit ratio gives a lower average access time, because fewer accesses go to the slow main memory.

A page fault is an event that occurs when a program refers to a page that is not present in main memory. The page table entry of that page has its valid bit as 0, so the hardware raises a trap to the operating system. The operating system then loads the page from disk into a free frame (removing another page if needed), updates the page table, and restarts the instruction. A page fault costs a lot of time, because a disk access is very slow compared to a memory access.

Cycle stealing is a DMA mode in which the DMA controller takes control of the memory bus for just one memory cycle at a time to move one word. It then gives the bus back to the CPU.

The controller "steals" a cycle from the CPU, so the CPU is delayed by only one cycle per word. The CPU and the DMA transfer therefore share the bus alternately. The transfer is slower than burst mode, but the CPU is never blocked for long. This suits slow or medium speed devices.

A vector interrupt is an interrupt in which the interrupting device itself supplies the address, or a vector number, of its service routine. The CPU uses this vector to look up the starting address of the routine in the interrupt vector table.

So the CPU does not have to poll all devices to find the source. This makes the response fast. For example, in the 8086 each interrupt type number n points to the table entry at address $4n$. Daisy chain priority hardware is often used to send the vector from the highest priority device.

(i) Bus system using multiplexers

There are four registers A, B, C and D, each of 4 bits. The bus is also 4 bits wide. We need one 4-to-1 multiplexer for each bit, so four multiplexers are used. Bit 0 of every register goes to MUX 0, bit 1 goes to MUX 1, and so on. Two select lines $S_1S_0$ are common to all the multiplexers. They choose which register is placed on the bus.

 A3..A0   B3..B0   C3..C0   D3..D0
   |        |        |        |
   v        v        v        v
+------------------------------------+
| MUX 3 | MUX 2 | MUX 1 | MUX 0      | <- S1 S0
+------------------------------------+
        |   4-bit common bus   |
        v                      v
   (loaded into any register by its LOAD input)

The select value 00 chooses A, 01 chooses B, 10 chooses C and 11 chooses D. The bus output is then loaded into a destination register by enabling its load input at a clock pulse. For example, with $S_1S_0 = 10$ and the load input of A enabled, the transfer $A \leftarrow C$ takes place at the next clock edge. The same bus can be used for any transfer between the four registers, but only one transfer can happen in one clock pulse.

(ii) Evaluating X = A + B * [C * D + E * (F + G)]

In a stack computer, every arithmetic instruction takes its operands from the top of the stack, so it needs no address. First we write the expression in reverse Polish notation. The conversion is checked with a program.

$$ABCDEFG++*+$$

Then we scan it from left to right. A letter becomes a PUSH instruction. An operator becomes one instruction without an operand. The program is:

The program needs 14 instructions. The last instruction stores the result at location X.

As a check, let $A=1, B=2, C=3, D=4, E=5, F=6, G=7$. The stack program computes $CD = 12$, $F+G = 13$, $E13 = 65$, then $12 + 65 = 77$, then $B * 77 = 154$, and finally $A + 154 = 155$. The direct calculation of the expression also gives 155, so the program is correct.

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.

The instruction cycle is the set of steps the CPU repeats to run each instruction of a program. It starts when the machine is powered on and stops only when a halt instruction is run or power is lost.

Flowchart

        +------------------+
        |  START (PC set)  |
        +--------+---------+
                 v
        +------------------+
        | FETCH: AR <- PC  |
        | IR <- M[AR]      |
        | PC <- PC + 1     |
        +--------+---------+
                 v
        +------------------+
        | DECODE opcode,   |
        | read mode bit I  |
        +--------+---------+
                 v
          < indirect? >--yes--> AR <- M[AR]
                 | no                 |
                 +<-------------------+
                 v
        +------------------+
        |     EXECUTE      |
        +--------+---------+
                 v
          < interrupt? >--yes--> save PC, go to ISR
                 | no
                 +---------> back to FETCH

Explanation

The cycle has four main phases.

Fetch. The address in the program counter (PC) goes to the address register (AR). The memory word at that address is read into the instruction register (IR). Then PC is increased by one so that it points to the next instruction. This is written as follows.

$$AR \leftarrow PC$$

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

Decode. The control unit looks at the opcode bits of IR and finds which operation is needed. A decoder turns the three opcode bits into one of eight lines. The mode bit I tells whether the operand address is direct or indirect.

Read the effective address. If the instruction is indirect, the address field only points to a memory word that holds the real operand address. So the CPU reads that word:

$$AR \leftarrow M[AR]$$

For a direct instruction, nothing more is needed here.

Execute. The operation is carried out. A memory-reference instruction such as ADD reads the operand into the data register DR and adds it to the accumulator AC. A register-reference instruction such as CLA clears AC. A branch instruction loads a new address into PC. An input-output instruction moves data to or from a device.

Interrupt check. After the execute phase, the CPU checks if an interrupt request has come. If yes, it saves the contents of PC (the return address), and starts the interrupt service routine. When the routine finishes, the return address is restored, and the program goes on. If no interrupt is pending, control goes back to the fetch phase for the next instruction.

All these steps are timed by the sequence counter, which generates the pulses T0, T1, T2 and so on. At the end of each instruction the counter is cleared, so the next fetch starts again at T0.

A worked example. Suppose PC holds 300 and the word at address 300 is the instruction ADD 500, with the mode bit I equal to 0. In the fetch phase, AR gets 300, IR gets the word from location 300, and PC becomes 301. In the decode phase, the decoder finds that it is an ADD, and the address field gives 500. As the instruction is direct, there is no indirect read. In the execute phase, the word at address 500 is read into DR, and AC is replaced by $AC + DR$. The sequence counter is cleared, and the next instruction at 301 is fetched.

Why the cycle matters. Every program, however large, runs only by repeating this loop. The speed of a computer in a large part depends on how fast the loop runs. Pipelining overlaps the loops of different instructions to make it faster.

A RAM is built from a large array of storage cells. The way the cells are arranged and addressed decides the size of the decoder and the cost of the chip. The two common arrangements are 2D and 2 1/2D.

2D organization

In 2D organization the cells are arranged as a two-dimensional array of words. Each row is one word, and each word has its own word line. A single decoder takes all $n$ address bits and activates exactly one of the $2^n$ word lines. All bits of that word are then read or written through the bit lines.

 Address (n bits) --> [ n to 2^n decoder ]
                        | word line 0 ---> [ word 0 ]
                        | word line 1 ---> [ word 1 ]
                        | ...
                        | word line 2^n-1 > [ word 2^n-1 ]
                                               |  |  |
                                         bit lines to R/W circuit

The decoder is a big circuit. For a $64\text{K} \times 1$ memory, $n = 16$, so the decoder has $2^{16} = 65536$ output lines and 65536 AND gates. This is costly and slow, and it takes a large area. So 2D organization suits only small memories.

2 1/2D organization

Here the cells are arranged in a square-like array of rows and columns, and the address is split into two halves. A row decoder takes the upper half and selects one row. A column decoder takes the lower half and selects one column through a multiplexer (or a column selector). The cell at the crossing of the chosen row and column is read or written.

 Row address (n/2) --> [ row decoder ] --> row lines
                                              |
                                   +------------------+
                                   |   cell array     |
                                   |  (rows x cols)   |
                                   +------------------+
                                              |
 Col address (n/2) --> [ column decoder / mux ] --> data bit

For the same $64\text{K} \times 1$ memory, the cells form a $256 \times 256$ array. The row decoder has 8 inputs and 256 outputs, and the column decoder also has 256 outputs. The total number of decoder outputs is

$$256 + 256 = 512$$

compared with 65536 in the 2D scheme. The saving is large. The name "2 1/2D" is used because the structure is more than a plain 2D array but not a full 3D one.

Comparison

The 2 1/2D scheme is also easy to refresh, because DRAM can refresh a whole row in one step. This is why modern memory chips use it.

In short, the 2D scheme is easy to understand but wastes area on the decoder, and the 2 1/2D scheme saves that area by splitting the address, which is why large memory chips follow it.

A DMA controller is the hardware unit that transfers data between an I/O device and main memory without the CPU, by taking over the system buses. A typical controller (such as the Intel 8237) has the following block structure.

Main blocks

• Address register: it holds the memory address of the word to be moved. It is incremented after each transfer.
• Word count register: it holds the number of words left. It is decremented after each transfer. When it reaches zero, the transfer is over.
• Control register: it holds the mode and the direction of transfer (read from memory or write to memory), and the transfer type such as burst or cycle stealing.
• Data buffer (data bus buffer): it holds the word for a moment and connects the controller to the data bus.
• Address and control logic: it drives the memory read and write lines, and the address bus when the controller is the bus master.
• Status register: it records when the count has reached zero and which channel was served.
• DMA select and register select: these inputs let the CPU address the controller itself, when the CPU programs its registers.

Signals with the CPU and the device

The DMA request line (DRQ) comes from the device and tells the controller that the device wants a transfer. The controller sends a bus request (HOLD) to the CPU. The CPU answers with a bus grant (HLDA) after finishing the present bus cycle. The controller then sends a DMA acknowledge (DACK) to the device. After the block is done, the controller sends an interrupt to the CPU.

Working

When the CPU is the bus master, the controller acts like an I/O interface. The CPU programs it by writing the start address, word count and mode into the registers. The control signals of the CPU (read and write) select the register through the register select input.

Once programmed, the controller waits for DRQ. On DRQ it asks for the bus. When the bus is granted, it places its address register on the address bus and issues the memory and I/O control signals together. The word goes straight from the device to memory or from memory to the device, over the data bus, without entering the CPU.

Then the address register goes up by one and the word count goes down by one. If the count is not zero and the device still requests, the cycle repeats. When the count is zero, the controller gives the bus back and raises an interrupt.

A controller with several channels can serve several devices. Each channel has its own address and count registers. A priority circuit decides which channel is served first when two request at the same time.

Why it is useful

The CPU is involved only at the start and the end of a block. High speed devices like disks can therefore move data at nearly the full memory speed.

The effective address (EA) is the memory address from which the operand is finally taken. It depends on the addressing mode. Here the instruction is at location 400 and its address field is at location 401, with value 500. The processor register R1 holds 200.

While the instruction is being fetched, the program counter (PC) moves on. The opcode is read from 400 and the address field from 401. So when the instruction is executed, PC holds the address of the next instruction.

$$PC = 401 + 1 = 402$$

We now go through each mode.

(i) Direct addressing

In direct mode the address field is itself the effective address. There is no calculation.

$$EA = 500$$

The operand is the word stored at memory location 500.

(ii) Immediate addressing

In immediate mode the address field is not an address at all. It is the operand. So the operand is the number 500 and no effective address exists. The processor does not go to memory for the operand, which makes this mode the fastest of all memory-type modes. We may say that the value used is found at location 401, the address field itself.

(iii) Relative addressing

In relative mode the address field is added to the content of the program counter. The PC already holds the address of the next instruction, which is 402.

$$EA = PC + 500$$

$$EA = 402 + 500 = 902$$

The operand is at location 902. This mode is used in branch instructions, because a jump is described as a distance from the present position.

(iv) Register indirect addressing

In register indirect mode the register named in the instruction holds the address of the operand. Here that register is R1.

$$EA = (R1) = 200$$

The operand is at location 200. The value 500 in the address field is not used in this mode.

(v) Indexed addressing with R1 as index register

In indexed mode the content of the index register is added to the address field.

$$EA = 500 + (R1)$$

$$EA = 500 + 200 = 700$$

The operand is at location 700. This mode is used to reach elements of an array. The address field gives the start of the array, and the index register selects one element.

Summary

Therefore the five modes give five different results from the same instruction, which shows why the addressing mode matters. One small point: if the question wants the PC value as 401 instead of 402, the relative result would be 901. The standard rule is that the PC is incremented after the fetch, so 902 is the accepted answer.

Processor organization means the way the registers, the ALU and the control unit inside the CPU are arranged and connected, and how the instructions use them to hold and process data. The CPU must fetch instructions, fetch operands, process them and store results. So it needs storage for temporary values. How that storage is arranged gives the type of organization.

Based on this, three types of processor organization are used.

(a) Single accumulator organization

All the operations use one special register called the accumulator (AC). One operand is always in AC and the result is also stored back in AC. The instruction has just one address field, for the second operand in memory. For example, ADD X means $AC \leftarrow AC + M[X]$.

  Memory ---> [ ALU ] ---> [ AC ] ---+
                 ^                   |
                 +-------------------+

This organization is simple and cheap and needs short instructions. But every result must pass through AC, so the program has many load and store instructions, and it is slow. Early computers such as the IBM 701 used it.

(b) General register organization

Here a set of registers, say R1 to R7, is available. Any of them can hold an operand or a result. A multiplexer chooses two source registers for the ALU inputs, a decoder chooses the destination register, and the ALU result goes back to the register file. The control word has the fields for source 1, source 2, destination and the ALU operation. An example instruction is ADD R1, R2, R3, which means $R1 \leftarrow R2 + R3$.

  R1 R2 R3 ... R7
   |  |  |      |
  [MUX A]   [MUX B]
      \       /
       [ ALU ]  <- operation select
          |
   (to registers via decoder)

This organization is fast, because the data stays inside the CPU and fewer memory accesses are needed. Instructions are longer, since they hold two or three register numbers. Most modern CPUs, such as the ARM and RISC-V, use it.

(c) Stack organization

Here the CPU has a stack (LIFO) in memory or in registers, and the operations work on the top of the stack. Most instructions are zero-address. For example, ADD pops two values, adds them and pushes the result. Other instructions are PUSH X and POP X.

This is very good for evaluating expressions written in reverse Polish notation, and it gives very short instructions. It is also used for subroutine calls. However, random access to items in the middle of the stack is hard. Burroughs B5500 used it.

Comparison

In short, the choice depends on cost, speed and the program length that the designer wants.

We use 6-bit registers, because $-19$ needs 6 bits in 2's complement. The numbers are:

$$M = +20 = 010100 \qquad -M = 101100 \qquad Q = -19 = 101101$$

$A$ starts at $000000$ and $Q_{-1}$ starts at 0. In each cycle we read the pair $Q_0 Q_{-1}$. The pair $10$ means subtract $M$ from $A$. The pair $01$ means add $M$ to $A$. The pairs $00$ and $11$ mean no operation. After that, $A$, $Q$ and $Q_{-1}$ are shifted one place right, and the sign bit of $A$ is copied (arithmetic shift right, ASR). The process runs for 6 cycles, one for each bit of the multiplier.

The product is in the joined register $AQ$:

$$AQ = 111010000100$$

The leftmost bit is 1, so the answer is negative. To find its size, take the 2's complement:

$$\overline{111010000100} + 1 = 000101111011 + 1 = 000101111100 = 380$$

Therefore $(+20) \times (-19) = -380$.

The result is correct because $20 \times 19 = 380$, and the signs differ. Booth's method gave the right sign automatically, and we did not need to treat the sign separately. This is the main strength of the algorithm. It works directly on numbers in 2's complement form. It also skips over strings of 0s and 1s in the multiplier, so it uses fewer additions when the multiplier has long runs of equal bits.

In this example the multiplier $101101$ has no long runs, so only the pair $11$ in cycle 4 causes a skip.

The table can be understood in another way. The pairs of bits turn the multiplier into the signed digits $-1, +1, 0, -1, +1, -1$ (from the leftmost bit down). So the multiplier is worth:

$$-32 + 16 + 0 - 4 + 2 - 1 = -19$$

Each digit decides whether we subtract $M$, add $M$, or do nothing at that bit position. Adding up the shifted copies gives $20 \times (-19) = -380$.

IEEE 754 is the standard way to store real numbers in a computer. A number is written in the form $(-1)^s \times 1.f \times 2^{e}$ and stored in three fields: a sign bit $s$, a biased exponent $E$, and a fraction $f$ (also called the mantissa). The leading 1 is implied, so it is not stored.

The stored exponent is $E = e + \text{bias}$. The bias lets the exponent field hold negative powers of 2 without its own sign. Single precision covers magnitudes from about $1.2 \times 10^{-38}$ to $3.4 \times 10^{38}$. The all-0 and all-1 exponent patterns are kept for zero, denormal numbers, infinity and NaN.

Representing -1460.125

The number is negative, so the sign bit is $1$. Convert the magnitude to binary. The integer part is $1460 = 10110110100_2$. The fraction is exact, since $0.125 = 0.001_2$. So:

$$1460.125 = 10110110100.001_2$$

Move the binary point 10 places left to normalise:

$$1460.125 = 1.0110110100001_2 \times 2^{10}$$

The fraction is $0110110100001$, and the true exponent is $e = 10$.

Single precision. The stored exponent is:

$$E = 10 + 127 = 137 = 10001001_2$$

The fraction is padded with zeros to 23 bits. Therefore:

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

Double precision. The stored exponent is:

$$E = 10 + 1023 = 1033 = 10000001001_2$$

The fraction is padded with zeros to 52 bits. Therefore:

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

Special values. The reserved exponent patterns give the following meanings:

Check. To decode the single precision answer, read $E = 137$, so $e = 137 - 127 = 10$. The value is $-1.0110110100001_2 \times 2^{10}$. Shifting the point 10 places right gives $-10110110100.001_2$, which is $-1460.125$. So the encoding is correct.

Both representations are exact, because the number needs only 13 fraction bits. Double precision stores the same value but has a wider range and about 15 to 16 decimal digits of accuracy, against about 7 for single precision.

A microprogram sequencer is the circuit that decides the address of the next microinstruction to be read from the control memory. A microprogram control unit needs it because the microinstructions are not always run in a straight line. They may branch, call a micro-subroutine, or jump to the routine of a new machine instruction.

Block diagram parts

• Multiplexer (MUX): picks one of the possible sources for the next address.
• Branch logic (condition select): tests a status bit, for example zero or carry, chosen by the microinstruction. It decides if the branch is taken.
• Incrementer: adds one to the present address, for straight-line flow.
• Subroutine register (SBR): stores the return address for a micro-subroutine call.
• Control address register (CAR): holds the address that goes to the control memory.
• Control memory: holds the microinstructions. Its output goes to the pipeline register.
• Mapping logic: converts the opcode of the machine instruction into the starting address of its microroutine.

Working

The control memory reads the microinstruction at the address in CAR. This microinstruction has a micro-operation field, a condition select field, a branch control field and a branch address field. The micro-operation field goes out as control signals. The other fields go into the sequencer.

The sequencer then chooses the next address from one of these sources.

1. Next in sequence: if no branch is needed, the incrementer gives CAR plus one.
2. Branch address: if the tested condition is true, the address field of the microinstruction is loaded into CAR. If it is false, CAR is incremented.
3. Mapped address: at the end of the fetch routine, the mapping logic turns the opcode into the starting address of the right routine.
4. Subroutine call and return: for a call, the return address (CAR plus one) is saved in SBR and the branch address is loaded. For a return, SBR is loaded back into CAR.

The multiplexer selects among these by the select lines that come from the branch control field. Then CAR is loaded with the chosen address at the next clock pulse, and the cycle repeats.

Example. If the control memory has 128 words, CAR is 7 bits wide, since $2^7 = 128$. The branch address field is also 7 bits. A common micro-subroutine, for example the one that finds an indirect operand address, is written once and called by many routines, which saves control memory.

The sequencer keeps the control unit flexible, since the order of microinstructions can be changed without any change in the hardware.

Summary of the sequencer. In one line, the sequencer is the "next address" box of the control unit. It lets the microprogram do loops, tests and calls, in the same way that a branch instruction does it in a machine program.

Difference between hardwired and microprogrammed control

Components of the hardwired control unit

In a hardwired unit, a fixed circuit takes the instruction and the clock and produces the control signals.

• Instruction register (IR): holds the instruction being run. Its opcode bits go to the decoder.
• Instruction decoder: a decoder, for example 3 to 8, turns the opcode into one active line $D_0$ to $D_7$. Each line means one instruction.
• Timing unit: it has a clock, a sequence counter (SC) and a 4 to 16 decoder. It gives timing signals $T_0, T_1, T_2$ and so on, one per clock pulse, so each step gets its own time slot.
• Flag and condition inputs: the status flags such as zero, carry and overflow also go into the circuit, because some signals depend on them.
• Control logic gates (combinational circuit): AND, OR and NOT gates combine the decoder lines, the timing signals and the flags. The output is the set of control signals that go to the ALU, registers, buses and memory.
• Control signal outputs: these signals open the paths and tell the units what to do in that clock pulse.

For example, the signal to load AR from PC happens in the fetch step at $T_0$ of every instruction:

$$AR\text{ load} = R'T_0 + R'T_2 , D_7 I'$$

This kind of Boolean equation is written for each signal and then built with gates.

 IR --> [Decoder] --D0..D7--+
                            v
 Clock -> [SC] -> [T0..T15]-> [Control logic ] --> control signals
                            ^   [ gates       ]
 Flags ---------------------+

Because the signals come straight from gates, the unit works at the speed of the hardware. But the design must be done again if an instruction is added.

Which one to choose. A hardwired unit gives the highest speed, so it is the choice for RISC machines with a small and fixed set of instructions. A microprogrammed unit costs less to design and modify, so it suits CISC machines with hundreds of complex instructions. Many real processors use a mix: simple instructions are hardwired and rare, complex ones are microcoded.

Note on the sequence counter. When an instruction finishes, the sequence counter is cleared by a control signal. This makes the timing signals start again at $T_0$ for the next instruction. Without this reset the timing would run on into the wrong time slots.

The reference string has 20 page numbers and there are 4 frames. A page fault happens when the needed page is not in any frame.

FIFO removes the page that has been in memory the longest. The frames below are listed from the oldest to the newest page.

LRU removes the page that was used least recently. The frames below are listed from the least recently used to the most recently used.

Counting the faults in each column gives

$$\text{FIFO faults} = 14, \qquad \text{LRU faults} = 10$$

The first four faults in both are compulsory, because the frames are empty at the start. FIFO has 6 hits, so its hit ratio is $6/20 = 0.30$. LRU has 10 hits, so its hit ratio is $10/20 = 0.50$.

Therefore, with 4 frames, FIFO gives 14 page faults and LRU gives 10 page faults. LRU does better here because it keeps the pages 1, 2 and 3, which are used again and again. FIFO throws out a page just because it is old, even when it is still in use. For example, FIFO removes page 2 and page 1 early, and has to fetch them again.

LRU needs extra hardware or counters to track the last use, while FIFO needs only a simple queue. LRU is also free from Belady's anomaly, where more frames can give more faults under FIFO.

A larger number of frames normally lowers the page faults, so with 4 frames both algorithms do better than they would with 3 frames on the same string.

(i) Memory of 1024 x 8

Each chip stores 1024 words of 1 bit. A word of 8 bits needs 8 bits in parallel, so

$$\text{chips} = \frac{1024 \times 8}{1024 \times 1} = 8$$

The memory has 1024 words, so it needs 10 address lines because $2^{10} = 1024$. All 10 address lines are connected in parallel to every one of the 8 chips. Each chip gives one bit of the word, so the data pin of chip 0 is bit 0, that of chip 1 is bit 1, and so on up to bit 7. The read/write line and the chip select line are also common to all chips. All 8 chips work together as one 8-bit wide memory.

Connection diagram for part (i)

 A9..A0 (10 lines) ---+----+----+--- ... ---+  (to all 8 chips)
 R/W, CS -------------+----+----+--- ... ---+
                      |    |    |           |
                   [chip0][chip1][chip2] .. [chip7]
                      |    |    |           |
                     D0   D1   D2   ...    D7

Here the lines D0 to D7 form the 8-bit data bus of the memory. Because the address lines are shared, a single address selects the same cell position in all 8 chips. The 8 bits read from them together form one memory word. This is called widening the word length. When the memory must be made deeper (more words), more groups are added, and the extra high address lines select one group, as shown below.

(ii) Memory of 16 KB

Take 1 byte as 8 bits. Then 16 KB is $16 \times 1024 = 16384$ words of 8 bits, that is $16384 \times 8 = 131072$ bits. Each chip holds 1024 bits, so

$$\text{chips} = \frac{16384 \times 8}{1024 \times 1} = 128$$

So 128 chips are needed. They form 16 groups of 8 chips, and each group is a $1024 \times 8$ block like the one in part (i).

The memory has 16384 words, so it needs 14 address lines because $2^{14} = 16384$. The lower 10 lines go to all chips in parallel. The upper 4 lines go to a $4 \times 16$ decoder. Each decoder output enables one group of 8 chips. In this way only one group works at a time.

For instance, the address with A13 to A10 equal to 0101 enables group 5. That group holds the words from $5 \times 1024 = 5120$ to $5120 + 1023 = 6143$. The other 15 groups stay idle, and their data outputs are in the high impedance state. This allows all 16 groups to share the same 8 data lines.

In short, adding chips side by side widens the word, and adding chip groups with a decoder increases the number of words.

Asynchronous data transfer

In a digital system, two units such as the CPU and an I/O interface often have their own independent clocks. When data is moved between them without a common clock, the transfer is called asynchronous. The sender must tell the receiver when the data is valid, and the receiver must tell the sender that it has taken the data. This is done by extra control signals. The two main methods are strobe control and handshaking.

Strobe control

Here a single control line, the strobe, tells when the data is valid. It can be driven by the source or by the destination.

In source-initiated strobe, the source places the data on the data bus. After a short delay it activates the strobe. The destination uses the strobe to latch the data. The source then removes the strobe and, after a little more time, removes the data.

In destination-initiated strobe, the destination first activates the strobe to ask for data. The source then places data on the bus. The destination latches it and removes the strobe, after which the source removes the data.

Source-initiated strobe
 Data   ----<====valid====>----
 Strobe ______|‾‾‾‾‾‾‾‾‾|______

The drawback is that the source does not know whether the destination really got the data. In the destination-initiated case, the destination does not know whether the source has put valid data. There is no acknowledgement.

Handshaking

Handshaking solves this problem by using two control lines, one in each direction, so each unit knows what the other has done.

In source-initiated handshaking, the source puts data on the bus and activates the line "data valid". The destination sees it, accepts the data, and activates the line "data accepted". The source sees this and removes data valid. Then the destination removes data accepted. The source can now send new data. The sequence is as follows.

1. The source places data on the bus and enables data valid.
2. The destination accepts the data and enables data accepted.
3. The source disables data valid and removes the data.
4. The destination disables data accepted and is ready for the next transfer.

In destination-initiated handshaking, the two lines are "ready for data" (from the destination) and "data valid" (from the source). The destination first activates ready for data. The source then places data and activates data valid. The destination takes the data and removes ready for data. The source then removes data valid, and the next cycle can start.

Comparison

Handshaking is more reliable and is used in most real interfaces. A time-out circuit can be added to detect a unit that never answers.

Data transfer between the CPU, memory and I/O devices is done in three modes. They differ in how much work the CPU does and how fast the transfer is.

Programmed I/O

The CPU controls the whole transfer by a program. It checks the status flag of the device in a loop. When the flag shows ready, the CPU reads or writes the data register. After that it goes back to checking.

This is simple and needs little hardware. But the CPU is kept busy waiting. This is called busy waiting, and it wastes CPU time, especially when the device is slow.

Interrupt-initiated I/O

Here the CPU does not wait. The device sends an interrupt signal when it is ready. The CPU stops its program, saves its state, and runs the service routine that moves the data. Then it returns to the old program.

The CPU can therefore run other programs while the device is busy. The overhead is the time to save and restore the state for every word. So this mode is good for slow or medium speed devices such as keyboards, but not for large blocks of data.

Direct Memory Access (DMA)

The DMA controller moves blocks of data between the device and memory by itself. The CPU only sets up the start address and word count, and the controller interrupts the CPU at the end. Data goes straight over the system bus, so the CPU is free during the transfer.

DMA is the fastest mode and is used for disks, tapes and network cards. It needs extra hardware, and the controller and the CPU compete for the memory bus.

Comparison

A simple illustration

Think of a student waiting for a parcel. In programmed I/O, the student stands at the gate and keeps looking out. In interrupt-initiated I/O, the student studies and goes to the gate only when the doorbell rings. In DMA, a helper collects all the parcels and places them in the room, and tells the student only when the last one is in.

Choosing a mode

If the device is slow and the system is simple, programmed I/O is enough. If the CPU has other jobs to do, interrupts are better. If large amounts of data must move quickly, DMA is the best choice.