BCS302 · AKTU past paper

Computer Organization and Architecture 2023-24 question paper

The complete AKTU 2023-24 exam paper for Computer Organization and Architecture (BCS302), all 22 questions with solved model answers written to the mark scheme.

Past Papers2025-26 2024-25 2023-24 2022-23 2021-22 2020-21 2019-20

Tap a question to open its answer.

12 marksbuses, bus architecture, types of buses anHideAnswer
What are the different types of Buses used in computer architecture?
A computer has three types of buses.

Address bus: it carries the address of the memory location or I/O device that the CPU wants to reach. It is one way, from the CPU to the memory and devices. Its width decides the memory size.

Data bus: it carries the actual data between the CPU, memory and I/O. It is two way. Its width decides how many bits move at a time.

Control bus: it carries control signals such as read, write, clock, interrupt request and bus grant. It manages the use of the other two buses.
22 marksMultiplicationHideAnswer
Name the different types of multipliers.
A multiplier is the circuit or method that multiplies two binary numbers. The main types are:

Shift-and-add (sequential) multiplier: it adds the multiplicand to a partial product once for each 1 bit of the multiplier, and shifts after each step.

Booth multiplier: it works on signed 2's complement numbers and skips strings of 0s and 1s.

Array multiplier: it uses a grid of AND gates and adders to make the product in one pass.

Wallace tree multiplier: it adds the partial products with a tree of carry-save adders, which is faster.
32 marksInstruction types, formats, instruction cyHideAnswer
What are the different phases of an instruction cycle?
An instruction cycle has these phases:

Fetch: the instruction is read from the memory address held in PC, and PC is incremented.

Decode: the control unit finds out the operation from the opcode.

Operand fetch: the effective address is found, and the operand is read from memory or a register.

Execute: the ALU or another unit does the operation.

Write back (store): the result is saved in a register or memory.

After this, the CPU may check for an interrupt, and then repeat the cycle for the next instruction.
42 marksHardwire and micro programmed controlHideAnswer
How does control unit of a computer works?
The control unit is the part of the CPU that directs all other parts. It does not process data itself.

It first fetches the instruction from memory using the address in the program counter, and places it in the instruction register. It then decodes the opcode to learn what is to be done. Using the decoded instruction and the clock timing signals, it produces control signals. These open the right data paths, select the ALU function, and give read or write commands to memory and I/O. It also watches status flags and interrupt requests. It may be hardwired (logic gates) or microprogrammed (control memory).
52 marksBasic concept and hierarchyHideAnswer
Write a short note on locality of reference.
Locality of reference means that a program tends to use a small part of its memory addresses again and again over a short time. It has two forms. Temporal locality means that an item used now is likely to be used again soon, as in a loop. Spatial locality means that items near the one just used are likely to be used next, as in an array or in straight-line code. Caches use this idea to keep the active data close to the CPU.
62 markssemiconductor RAM memories, 2D & 2 1/2D meHideAnswer
Define 2 1/2 D memory organization.
In 2 1/2D memory organization, the cells are placed in a two-dimensional array of rows and columns. The address is split into two halves. A row decoder selects one row, and a column decoder selects one column. The cell at the crossing is accessed. Two small decoders of about $2^{n/2}$ outputs each are used, instead of one big decoder of $2^n$ outputs. This reduces the cost and area of the memory chip.
In 2 1/2D memory organization, the cells are placed in a two-dimensional array of rows and columns. The address is split into two halves. A row decoder selects one row, and a column decoder selects one column. The cell at the crossing is accessed. Two small decoders of about $2^{n/2}$ outputs each are used, instead of one big decoder of $2^n$ outputs. This reduces the cost and area of the memory chip.
72 marksSerial CommunicationHideAnswer
In what way synchronous and asynchronous serial modes of data transfer differ?
In the synchronous serial mode, the sender and receiver share a common clock, and data bits are sent continuously in blocks (frames) without start and stop bits for each character. It is fast, but needs clock or synchronising characters.

In the asynchronous serial mode, there is no common clock. Each character is framed by a start bit and one or two stop bits, so the receiver can synchronise on every character. It is simple and cheap but has extra bits as overhead, so it is slower. A keyboard link is an example.
87 marksbuses, bus architecture, types of buses anHideAnswer
What is meant by the term BUS arbitration? Why is it needed? How can bus arbitration be implemented in Daisy chaining scheme?
Bus arbitration is the method of deciding which device may use a shared bus when more than one device requests it at the same time. The device that gets the bus is called the bus master. The unit that decides is the arbiter. The arbiter can be the CPU, or a special bus controller.

Why it is needed

A bus is a shared resource, and only one device can send data on it at a time. If two devices sent together, the signals would mix and the data would be wrong. Several devices, such as the CPU, DMA controllers and I/O processors, can all become bus masters. So a rule is needed to give the bus to one of them and to make others wait. Arbitration also gives the important devices a higher priority and stops any device from using the bus for ever.

Daisy chaining scheme

In this scheme, all the devices are connected in series. The devices share one common bus request line. The bus grant line passes from the arbiter through each device in turn, and it goes from one device to the next one.

Arbiter --grant--> [Dev 1] --grant--> [Dev 2] --grant--> [Dev 3] ^ | | | +------ common bus request line (wired OR) -------------+

The working is as follows.

Any device that needs the bus puts a signal on the common bus request line. The line is the OR of all requests.

The arbiter sees the request and sends the grant signal to the first device in the chain.

If this device did not request the bus, it passes the grant signal on to the next device.

The first device that did request the bus keeps the grant signal and does not pass it on. It becomes the bus master and also sets a busy line, so that the others know the bus is in use.

When the master finishes, it removes the busy signal. The arbiter then looks at the request line again.

The priority of a device depends only on its position in the chain. The device nearest to the arbiter has the highest priority, and the last one has the lowest.

Advantages and disadvantages

It is simple and needs very few wires, and a new device is easy to add at the end. But the priority is fixed by position, and a device at the end may starve if the earlier ones request often. The grant signal has to pass through every device, so the delay grows with the chain length. If one device in the chain fails, the devices after it cannot get the bus.

97 marksNumericalMultiplicationAnswer

Show the multiplication process using Booth's algorithm when the following numbers are multiplied: (-12) * (-18).

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

$M = -12 = 110100 \qquad -M = +12 = 001100 \qquad Q = -18 = 101110$

$A$ and $Q_{-1}$ start at 0. In each cycle we read the pair $Q_0Q_{-1}$ . The pair $10$ means $A = A - M$ . The pair $01$ means $A = A + M$ . The pairs $00$ and $11$ mean no operation. Then $A$ , $Q$ and $Q_{-1}$ shift one place right with the sign bit of $A$ copied (arithmetic shift right, ASR). There are 6 cycles.

Cycle	Q0 Q-1	Operation	A	Q	Q-1
Start	-	initial	000000	101110	0
1	0 0	no change, ASR	000000	010111	0
2	1 0	A = A - M, ASR	000110	001011	1
3	1 1	no change, ASR	000011	000101	1
4	1 1	no change, ASR	000001	100010	1
5	0 1	A = A + M, ASR	111010	110001	0
6	1 0	A = A - M, ASR	000011	011000	1

The product is in $AQ$ joined:

$AQ = 000011011000$

The leading bit is 0, so the product is positive. Its value is:

$2^7 + 2^6 + 2^4 + 2^3 = 128 + 64 + 16 + 8 = 216$

Therefore $(-12) \times (-18) = +216$ .

Check: $12 \times 18 = 216$ , and two negative numbers give a positive product, so the answer is correct. Booth's algorithm gave the correct sign without any separate sign handling, because it works on 2's complement numbers directly. Cycles 1, 3 and 4 needed no addition or subtraction, so the multiplier $101110$ was handled with only three arithmetic operations instead of four.

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

$$M = -12 = 110100 \qquad -M = +12 = 001100 \qquad Q = -18 = 101110$$

$A$ and $Q_{-1}$ start at 0. In each cycle we read the pair $Q_0Q_{-1}$. The pair $10$ means $A = A - M$. The pair $01$ means $A = A + M$. The pairs $00$ and $11$ mean no operation. Then $A$, $Q$ and $Q_{-1}$ shift one place right with the sign bit of $A$ copied (arithmetic shift right, ASR). There are 6 cycles.

Cycle	Q0 Q-1	Operation	A	Q	Q-1
Start	-	initial	000000	101110	0
1	0 0	no change, ASR	000000	010111	0
2	1 0	A = A - M, ASR	000110	001011	1
3	1 1	no change, ASR	000011	000101	1
4	1 1	no change, ASR	000001	100010	1
5	0 1	A = A + M, ASR	111010	110001	0
6	1 0	A = A - M, ASR	000011	011000	1

The product is in $AQ$ joined:

$$AQ = 000011011000$$

The leading bit is 0, so the product is positive. Its value is:

$$2^7 + 2^6 + 2^4 + 2^3 = 128 + 64 + 16 + 8 = 216$$

Therefore $(-12) \times (-18) = +216$.

Check: $12 \times 18 = 216$, and two negative numbers give a positive product, so the answer is correct. Booth's algorithm gave the correct sign without any separate sign handling, because it works on 2's complement numbers directly. Cycles 1, 3 and 4 needed no addition or subtraction, so the multiplier $101110$ was handled with only three arithmetic operations instead of four.

107 marksProgram Control, Reduced Instruction Set CHideAnswer
What is pipelining? What are the different stages of pipelining? Explain in detail.
Pipelining is a technique to overlap the execution of many instructions. The work of one instruction is divided into stages, with separate hardware for each stage. When one instruction moves to the next stage, a new one enters the first stage. It is like an assembly line in a factory, where every worker does one small job, and all work at the same time.

Stages of an instruction pipeline

A common pipeline has five stages.

Instruction fetch (IF): the instruction is read from memory using the address in the program counter.

Instruction decode (ID): the opcode is decoded, and the source registers are read.

Execute (EX): the ALU does the operation, or calculates the address of a memory operand.

Memory access (MEM): a load reads data from memory, and a store writes data to memory.

Write back (WB): the result is written in the destination register.

In the timing diagram, each row is an instruction and each column is a clock cycle. Instruction 2 starts one cycle after instruction 1. After the pipeline fills in cycle 5, one instruction completes in every clock cycle.

Performance

For $k$ stages, $n$ instructions and a stage time $t_p$ :

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

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

The speedup is then:

$S = \frac{nk}{k + n - 1}$

For large $n$ the speedup is close to $k$ . For example, 100 instructions in a 5-stage pipeline give $500/104 \approx 4.81$ .

Hazards. The pipeline cannot always run at full speed.

A structural hazard happens when two instructions need the same hardware in the same cycle, such as one memory port for both fetch and data.

A data hazard happens when an instruction needs a result that an earlier instruction has not yet written. It is reduced by forwarding the result directly and by stalling.

A control hazard happens at a branch, when the next instruction is not known. It is reduced by branch prediction and by delayed branches.

Advantages and limits. Pipelining gives higher throughput and better use of the hardware. It does not reduce the time of a single instruction, and hazards and unequal stage times reduce the gain. RISC designs have simple, equal-length instructions, so they pipeline very well.
Pipelining is a technique to overlap the execution of many instructions. The work of one instruction is divided into stages, with separate hardware for each stage. When one instruction moves to the next stage, a new one enters the first stage. It is like an assembly line in a factory, where every worker does one small job, and all work at the same time.

Stages of an instruction pipeline

A common pipeline has five stages.

Instruction fetch (IF): the instruction is read from memory using the address in the program counter.

Instruction decode (ID): the opcode is decoded, and the source registers are read.

Execute (EX): the ALU does the operation, or calculates the address of a memory operand.

Memory access (MEM): a load reads data from memory, and a store writes data to memory.

Write back (WB): the result is written in the destination register.

In the timing diagram, each row is an instruction and each column is a clock cycle. Instruction 2 starts one cycle after instruction 1. After the pipeline fills in cycle 5, one instruction completes in every clock cycle.

Performance

For $k$ stages, $n$ instructions and a stage time $t_p$:

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

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

The speedup is then:

$$S = \frac{nk}{k + n - 1}$$

For large $n$ the speedup is close to $k$. For example, 100 instructions in a 5-stage pipeline give $500/104 \approx 4.81$.

Hazards. The pipeline cannot always run at full speed.

A structural hazard happens when two instructions need the same hardware in the same cycle, such as one memory port for both fetch and data.

A data hazard happens when an instruction needs a result that an earlier instruction has not yet written. It is reduced by forwarding the result directly and by stalling.

A control hazard happens at a branch, when the next instruction is not known. It is reduced by branch prediction and by delayed branches.

Advantages and limits. Pipelining gives higher throughput and better use of the hardware. It does not reduce the time of a single instruction, and hazards and unequal stage times reduce the gain. RISC designs have simple, equal-length instructions, so they pipeline very well.

117 marksAuxiliary memoriesAnswer

Give classification of memory based on the method of access. Also discuss construction and working of magnetic disk and various components of disk access time.

Classification by method of access

Type	How data is reached	Example
Random access	any location in the same time, using its address	RAM, ROM, cache
Sequential access	data is reached in order, passing all earlier data	magnetic tape
Direct (semi-random) access	the head goes to the nearby area directly, then reads in order	magnetic disk
Associative access	a word is found by its content, not by its address	cache tag memory, CAM

Construction of a magnetic disk

A magnetic disk has one or more platters made of aluminium or glass, coated with magnetic material. They are fixed on a spindle which rotates at a constant speed, such as 7200 rpm. Each surface is divided into concentric circles called tracks. Each track is divided into sectors, and a sector is the smallest unit that can be read or written (often 512 bytes). The tracks at the same position on all surfaces form a cylinder. A read/write head is placed over each surface, and all heads are fixed on one arm assembly that moves together. A disk controller drives the arm and moves data.

Working

To write, the head sends a current through its coil, which magnetizes a tiny spot on the surface in one of two directions, standing for 1 and 0. To read, the moving magnetized spots induce a small current in the head, which is sensed as bits. To reach a sector, the arm moves the heads to the right cylinder. Then the disk turns until the sector is under the head. Then the data is transferred.

Components of disk access time

$T_{access} = T_{seek} + T_{rotation} + T_{transfer} + T_{controller}$

Seek time is the time to move the head to the required track. It is the largest part, a few milliseconds.
Rotational latency is the time for the needed sector to come under the head. On average it is half a rotation, $\frac{60}{2 \times \text{rpm}}$ seconds. For 7200 rpm it is $60/(2 \times 7200) = 4.17$ ms.
Transfer time is the time to read the sector bytes, equal to the data size divided by the transfer rate.
Controller overhead is the small time used by the disk controller for commands and checks.

Classification by method of access

Type	How data is reached	Example
Random access	any location in the same time, using its address	RAM, ROM, cache
Sequential access	data is reached in order, passing all earlier data	magnetic tape
Direct (semi-random) access	the head goes to the nearby area directly, then reads in order	magnetic disk
Associative access	a word is found by its content, not by its address	cache tag memory, CAM

Construction of a magnetic disk

Working

Components of disk access time

$$T_{access} = T_{seek} + T_{rotation} + T_{transfer} + T_{controller}$$

Seek time is the time to move the head to the required track. It is the largest part, a few milliseconds.
Rotational latency is the time for the needed sector to come under the head. On average it is half a rotation, $\frac{60}{2 \times \text{rpm}}$ seconds. For 7200 rpm it is $60/(2 \times 7200) = 4.17$ ms.
Transfer time is the time to read the sector bytes, equal to the data size divided by the transfer rate.
Controller overhead is the small time used by the disk controller for commands and checks.

127 marksModes of Data TransferAnswer

What are the basic differences between interrupt initiated I/O and programmed I/O? Explain in detail.

Programmed I/O and interrupt-initiated I/O are two ways in which the CPU controls the transfer of data to and from an I/O device. They differ mostly in how the CPU learns that the device is ready.

Programmed I/O

The CPU runs a program that tests the status flag of the device again and again in a loop. This is called polling. When the flag shows "ready", the CPU transfers one word between the device and a CPU register. Then it goes back to polling for the next word.

The CPU does nothing useful while it waits. It is therefore tied up for the entire time the device takes. The method needs little hardware and is easy to program. It is used when the system has a single job or when the device is very fast.

Interrupt-initiated I/O

Here the CPU starts the device and then goes on with other work. When the device is ready, its interface sends an interrupt request. The CPU completes its current instruction, saves the return address and the flags, and jumps to the interrupt service routine. The routine moves one word, and the CPU returns to the interrupted program.

The CPU is not kept waiting, so it is used well when devices are slow. The cost is the time spent in saving and restoring the state for each interrupt, and the extra hardware for interrupt handling and priority.

Differences

Point	Programmed I/O	Interrupt-initiated I/O
Who finds that the device is ready	CPU, by polling the flag	Device, by an interrupt signal
CPU use	Wasted in busy waiting	Free for other work meanwhile
Response time	Depends on the polling loop	Fast, as the interrupt is served at once
Hardware	Simple	Needs interrupt logic and priority
Overhead per word	Test of the flag	Saving and restoring state
Software	Simple loop	Needs a service routine
Efficiency	Poor for slow devices	Good for slow and medium devices
Typical use	Small embedded systems	Keyboard, mouse, timer

Summary

Programmed I/O is simple but wasteful, because the CPU stays in a loop. Interrupt-initiated I/O uses the CPU much better because the device calls the CPU when needed. Neither is suited to moving big blocks of data at high speed. For that, DMA is used, since in both of these methods the CPU must handle every word.

137 marksProcessor organization, general registers HideAnswer
What do you mean by processor organization? Explain various types of processor organization with suitable example.
Processor organization is the way the registers, ALU and control unit inside a CPU are arranged and connected. It decides where operands are kept while an instruction works on them. Three types are common.

Single accumulator organization

One special register, the accumulator (AC), holds one operand and also receives the result. The instruction has one address field for the other operand. For example, ADD X means $AC \leftarrow AC + M[X]$ . To compute $Z = X + Y$ the program is LOAD X, ADD Y, STORE Z. It is simple and cheap, but every result passes through AC, so many load and store instructions are needed. Early machines such as the IBM 701 used it.

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

General register organization

A group of registers R1 to R7 can each hold data. Two multiplexers select the two source registers for the ALU, and a decoder selects the destination register. For example, ADD R1, R2, R3 means $R1 \leftarrow R2 + R3$ . Data stays in the CPU, so fewer memory accesses are needed and the program is fast. Instructions are longer as they carry register numbers. ARM and RISC-V processors use this type. The program for $Z = X + Y$ is LOAD R1, X, LOAD R2, Y, ADD R3, R1, R2 and STORE R3, Z.

Stack organization

The CPU works with a LIFO stack, and the operations use the top items. Most instructions are zero-address. For example, ADD pops two items and pushes their sum. The program for $Z = X + Y$ is PUSH X, PUSH Y, ADD and POP Z. It suits expressions in reverse Polish notation, and the instructions are very short. But random access to the middle of the stack is not possible. The Burroughs B5500 used it.

Comparison

Point Accumulator General register Stack
Address fields one two or three zero
Speed slow fast medium
Instruction size short long very short
Example IBM 701 ARM, RISC-V Burroughs B5500

Most modern processors use the general register organization along with some stack support for subroutine calls.
Processor organization is the way the registers, ALU and control unit inside a CPU are arranged and connected. It decides where operands are kept while an instruction works on them. Three types are common.

Single accumulator organization

One special register, the accumulator (AC), holds one operand and also receives the result. The instruction has one address field for the other operand. For example, ADD X means $AC \leftarrow AC + M[X]$. To compute $Z = X + Y$ the program is LOAD X, ADD Y, STORE Z. It is simple and cheap, but every result passes through AC, so many load and store instructions are needed. Early machines such as the IBM 701 used it.

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

General register organization

A group of registers R1 to R7 can each hold data. Two multiplexers select the two source registers for the ALU, and a decoder selects the destination register. For example, ADD R1, R2, R3 means $R1 \leftarrow R2 + R3$. Data stays in the CPU, so fewer memory accesses are needed and the program is fast. Instructions are longer as they carry register numbers. ARM and RISC-V processors use this type. The program for $Z = X + Y$ is LOAD R1, X, LOAD R2, Y, ADD R3, R1, R2 and STORE R3, Z.

Stack organization

The CPU works with a LIFO stack, and the operations use the top items. Most instructions are zero-address. For example, ADD pops two items and pushes their sum. The program for $Z = X + Y$ is PUSH X, PUSH Y, ADD and POP Z. It suits expressions in reverse Polish notation, and the instructions are very short. But random access to the middle of the stack is not possible. The Burroughs B5500 used it.

Comparison

Point Accumulator General register Stack
Address fields one two or three zero
Speed slow fast medium
Instruction size short long very short
Example IBM 701 ARM, RISC-V Burroughs B5500

Most modern processors use the general register organization along with some stack support for subroutine calls.

Point	Accumulator	General register	Stack
Address fields	one	two or three	zero
Speed	slow	fast	medium
Instruction size	short	long	very short
Example	IBM 701	ARM, RISC-V	Burroughs B5500

Point	Accumulator	General register	Stack
Address fields	one	two or three	zero
Speed	slow	fast	medium
Instruction size	short	long	very short
Example	IBM 701	ARM, RISC-V	Burroughs B5500

147 marksProcessor organization, general registers Answer

Differentiate between Memory stack and register stack.

A stack is a LIFO structure. It can be built in two ways: as a set of CPU registers (register stack), or in a portion of main memory (memory stack). In both, a stack pointer (SP) points to the top item.

Register stack

It is a small group of CPU registers, for example 64 words, organized as a stack. SP is a 6-bit register. Two flip-flops, FULL and EMPTY, signal the end conditions. The push and pop are

$\text{PUSH: } SP \leftarrow SP + 1,\ M[SP] \leftarrow DR$

$\text{POP: } DR \leftarrow M[SP],\ SP \leftarrow SP - 1$

The test for full or empty is done by checking whether SP has wrapped round to 0.

Memory stack

A part of the main memory is reserved for the stack. SP is a register holding a memory address. It usually starts at a high address and moves down as items are pushed. The push and pop are

$\text{PUSH: } SP \leftarrow SP - 1,\ M[SP] \leftarrow DR$

$\text{POP: } DR \leftarrow M[SP],\ SP \leftarrow SP + 1$

To find overflow and underflow, SP is compared with the upper and lower limit addresses of the stack area.

Differences

Point	Register stack	Memory stack
Location	Registers inside the CPU	A reserved area of main memory
Speed	Very fast, no memory access	Slower, each push or pop is a memory access
Size	Small and fixed by hardware	Large and can be changed by software
Cost	Costly, as registers are expensive	Cheap, memory is cheap
Overflow check	FULL and EMPTY flip-flops	SP compared with limit addresses
Direction of growth	Usually towards higher addresses	Usually towards lower addresses
Typical use	Expression evaluation in a small processor	Subroutine calls, interrupts, local data

Because main memory is cheap and big, general purpose computers use the memory stack. A register stack is used only where speed matters and a very small stack is enough, for example in a small embedded processor or for a stack of intermediate results.

Register stack

It is a small group of CPU registers, for example 64 words, organized as a stack. SP is a 6-bit register. Two flip-flops, FULL and EMPTY, signal the end conditions. The push and pop are

$$\text{PUSH: } SP \leftarrow SP + 1,\ M[SP] \leftarrow DR$$

$$\text{POP: } DR \leftarrow M[SP],\ SP \leftarrow SP - 1$$

The test for full or empty is done by checking whether SP has wrapped round to 0.

Memory stack

A part of the main memory is reserved for the stack. SP is a register holding a memory address. It usually starts at a high address and moves down as items are pushed. The push and pop are

$$\text{PUSH: } SP \leftarrow SP - 1,\ M[SP] \leftarrow DR$$

$$\text{POP: } DR \leftarrow M[SP],\ SP \leftarrow SP + 1$$

To find overflow and underflow, SP is compared with the upper and lower limit addresses of the stack area.

Differences

Point	Register stack	Memory stack
Location	Registers inside the CPU	A reserved area of main memory
Speed	Very fast, no memory access	Slower, each push or pop is a memory access
Size	Small and fixed by hardware	Large and can be changed by software
Cost	Costly, as registers are expensive	Cheap, memory is cheap
Overflow check	FULL and EMPTY flip-flops	SP compared with limit addresses
Direction of growth	Usually towards higher addresses	Usually towards lower addresses
Typical use	Expression evaluation in a small processor	Subroutine calls, interrupts, local data

157 marksLook ahead carries addersHideAnswer
Explain in detail the principle of carry look ahead adder and design 4-bit CLA adder.
A ripple carry adder is slow, because each stage waits for the carry of the stage before it. A carry look-ahead adder (CLA) finds all the carries at the same time, directly from the inputs.

For each bit $i$ we define two signals. The generate signal $G_i = A_iB_i$ means this stage makes a carry on its own. The propagate signal $P_i = A_i \oplus B_i$ means this stage passes an incoming carry on. Then:

$S_i = P_i \oplus C_i \qquad C_{i+1} = G_i + P_iC_i$

Replacing each carry by the equation of the stage before gives the carries of a 4-bit adder in terms of $G$ , $P$ and $C_0$ only:

$C_1 = G_0 + P_0C_0$

$C_2 = G_1 + P_1G_0 + P_1P_0C_0$

$C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$

$C_4 = G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0$

Each carry is a two-level AND-OR circuit. So all four carries are ready after the same two gate delays.

Design of the 4-bit CLA. The circuit has three layers. The first layer has an AND gate and an XOR gate for each bit. They give $G_i$ and $P_i$ . The second layer is the look-ahead logic that makes $C_1$ to $C_4$ from the four equations above. The third layer has four XOR gates that give $S_i = P_i \oplus C_i$ .

A3B3 A2B2 A1B1 A0B0 | | | | [AND,XOR] x4 -> G3..G0, P3..P0 | | | | +--------------------------+ | look-ahead carry logic |<-- C0 | C1 C2 C3 C4 | +--------------------------+ |C3 |C2 |C1 |C0 [XOR] [XOR] [XOR] [XOR] S3 S2 S1 S0

The delay is about 4 gate delays in total (one for $P,G$ , two for the carries, one for the XOR). A 4-bit ripple carry adder needs about 8. The price is more gates, and wider AND-OR gates for longer words. So big adders use 4-bit CLA blocks joined together.
A ripple carry adder is slow, because each stage waits for the carry of the stage before it. A carry look-ahead adder (CLA) finds all the carries at the same time, directly from the inputs.

For each bit $i$ we define two signals. The generate signal $G_i = A_iB_i$ means this stage makes a carry on its own. The propagate signal $P_i = A_i \oplus B_i$ means this stage passes an incoming carry on. Then:

$$S_i = P_i \oplus C_i \qquad C_{i+1} = G_i + P_iC_i$$

Replacing each carry by the equation of the stage before gives the carries of a 4-bit adder in terms of $G$, $P$ and $C_0$ only:

$$C_1 = G_0 + P_0C_0$$

$$C_2 = G_1 + P_1G_0 + P_1P_0C_0$$

$$C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$$

$$C_4 = G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0$$

Each carry is a two-level AND-OR circuit. So all four carries are ready after the same two gate delays.

Design of the 4-bit CLA. The circuit has three layers. The first layer has an AND gate and an XOR gate for each bit. They give $G_i$ and $P_i$. The second layer is the look-ahead logic that makes $C_1$ to $C_4$ from the four equations above. The third layer has four XOR gates that give $S_i = P_i \oplus C_i$.

A3B3 A2B2 A1B1 A0B0 | | | | [AND,XOR] x4 -> G3..G0, P3..P0 | | | | +--------------------------+ | look-ahead carry logic |<-- C0 | C1 C2 C3 C4 | +--------------------------+ |C3 |C2 |C1 |C0 [XOR] [XOR] [XOR] [XOR] S3 S2 S1 S0

The delay is about 4 gate delays in total (one for $P,G$, two for the carries, one for the XOR). A 4-bit ripple carry adder needs about 8. The price is more gates, and wider AND-OR gates for longer words. So big adders use 4-bit CLA blocks joined together.
167 marksNumericalIEEE Standard for Floating Point NumbersHideAnswer
Represent the following decimal number in IEEE standard floating-point format in a single precision method (32 bit) representation method. (i) (85.125)10 (ii) (-307.1875)10
IEEE 754 single precision uses 32 bits: 1 sign bit, 8 exponent bits with bias 127, and 23 fraction bits. A number is stored as $(-1)^s \times 1.f \times 2^{e}$ , with the stored exponent $E = e + 127$ . The leading 1 is implied, so it is not stored.

The method has three parts. First, convert the number to binary. Second, normalise it to the form $1.f \times 2^e$ by moving the binary point. Third, add the bias to $e$ and write the sign, exponent and fraction in order. The bias of 127 makes the stored exponent a positive number even for small values.

(i) 85.125

The number is positive, so $s = 0$ . The integer part is $85 = 1010101_2$ , and the fraction is exact, since $0.125 = 0.001_2$ . So:

$85.125 = 1010101.001_2 = 1.010101001_2 \times 2^{6}$

The stored exponent is:

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

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

Sign Exponent Fraction
0 10000101 01010100100000000000000

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

(ii) -307.1875

The number is negative, so $s = 1$ . The integer part is $307 = 100110011_2$ and $0.1875 = 0.0011_2$ . So:

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

The stored exponent is:

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

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

Sign Exponent Fraction
1 10000111 00110011001100000000000

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

Both numbers have short binary fractions, so both are stored exactly with no rounding error.

To check the first answer, decode it: $E = 133$ gives $e = 6$ . The value is $1.010101001_2 \times 2^6 = 1010101.001_2 = 85 + 0.125 = 85.125$ . The second answer decodes in the same way to $-(256 + 32 + 16 + 2 + 1) - 0.1875 = -307.1875$ , which matches.
IEEE 754 single precision uses 32 bits: 1 sign bit, 8 exponent bits with bias 127, and 23 fraction bits. A number is stored as $(-1)^s \times 1.f \times 2^{e}$, with the stored exponent $E = e + 127$. The leading 1 is implied, so it is not stored.

The method has three parts. First, convert the number to binary. Second, normalise it to the form $1.f \times 2^e$ by moving the binary point. Third, add the bias to $e$ and write the sign, exponent and fraction in order. The bias of 127 makes the stored exponent a positive number even for small values.

(i) 85.125

The number is positive, so $s = 0$. The integer part is $85 = 1010101_2$, and the fraction is exact, since $0.125 = 0.001_2$. So:

$$85.125 = 1010101.001_2 = 1.010101001_2 \times 2^{6}$$

The stored exponent is:

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

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

Sign Exponent Fraction
0 10000101 01010100100000000000000

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

(ii) -307.1875

The number is negative, so $s = 1$. The integer part is $307 = 100110011_2$ and $0.1875 = 0.0011_2$. So:

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

The stored exponent is:

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

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

Sign Exponent Fraction
1 10000111 00110011001100000000000

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

Both numbers have short binary fractions, so both are stored exactly with no rounding error.

To check the first answer, decode it: $E = 133$ gives $e = 6$. The value is $1.010101001_2 \times 2^6 = 1010101.001_2 = 85 + 0.125 = 85.125$. The second answer decodes in the same way to $-(256 + 32 + 16 + 2 + 1) - 0.1875 = -307.1875$, which matches.
177 marksInstruction types, formats, instruction cyHideAnswer
Explain the different cycles of an instruction execution.
An instruction passes through a few cycles, called sub cycles, before it is finished. The CPU repeats them for each instruction.

Fetch cycle. The address in PC goes to the address register, and the instruction is read from memory into IR. Then PC is incremented.

$AR \leftarrow PC$

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

Decode cycle. The control unit decodes the opcode in IR. It also finds out the addressing mode from the mode bit. This tells how the operand is to be found.

Indirect cycle. If the address is indirect, the effective address is read from memory:

$AR \leftarrow M[AR]$

For direct addressing this cycle is skipped.

Execute cycle. The operation named by the opcode is carried out. A memory-reference instruction reads the operand and uses it. A register-reference instruction works on registers only. An input-output instruction moves data to or from a device. A branch instruction loads a new value in PC.

Interrupt cycle. After execution, the CPU checks if an interrupt is waiting. If so, it saves PC, and jumps to the interrupt service routine. If not, the cycle goes back to fetch.

The diagram shows these cycles in order and the way that execution goes back to fetch for the next instruction. The sequence counter times each cycle with the pulses T0, T1, T2 and so on. This is how every instruction of a program is run, one after another.

For example, in ADD 500, fetch brings the instruction in, decode finds the ADD, the indirect cycle is skipped, execute reads the word at 500 and adds it to AC, and the interrupt check follows.

Notes on the sub cycles. The fetch cycle is the same for all instructions, but the execute cycle is different for each. A register-reference instruction needs no memory read and finishes quickly, while a memory-reference instruction needs at least one memory access. Because of this, the number of clock pulses is not the same for each instruction. The control unit uses the sequence counter to track the pulse, and clears it at the end of the instruction.
An instruction passes through a few cycles, called sub cycles, before it is finished. The CPU repeats them for each instruction.

Fetch cycle. The address in PC goes to the address register, and the instruction is read from memory into IR. Then PC is incremented.

$$AR \leftarrow PC$$

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

Decode cycle. The control unit decodes the opcode in IR. It also finds out the addressing mode from the mode bit. This tells how the operand is to be found.

Indirect cycle. If the address is indirect, the effective address is read from memory:

$$AR \leftarrow M[AR]$$

For direct addressing this cycle is skipped.

Execute cycle. The operation named by the opcode is carried out. A memory-reference instruction reads the operand and uses it. A register-reference instruction works on registers only. An input-output instruction moves data to or from a device. A branch instruction loads a new value in PC.

Interrupt cycle. After execution, the CPU checks if an interrupt is waiting. If so, it saves PC, and jumps to the interrupt service routine. If not, the cycle goes back to fetch.

The diagram shows these cycles in order and the way that execution goes back to fetch for the next instruction. The sequence counter times each cycle with the pulses T0, T1, T2 and so on. This is how every instruction of a program is run, one after another.

For example, in ADD 500, fetch brings the instruction in, decode finds the ADD, the indirect cycle is skipped, execute reads the word at 500 and adds it to AC, and the interrupt check follows.

Notes on the sub cycles. The fetch cycle is the same for all instructions, but the execute cycle is different for each. A register-reference instruction needs no memory read and finishes quickly, while a memory-reference instruction needs at least one memory access. Because of this, the number of clock pulses is not the same for each instruction. The control unit uses the sequence counter to track the pulse, and clears it at the end of the instruction.
187 marksHardwire and micro programmed controlHideAnswer
Differentiate between hardwired and micro programmed control unit. Explain each component of hardwired control unit organization.
Hardwired versus microprogrammed control unit

Point Hardwired Microprogrammed
Control signals From logic gates From a control memory
Speed Fast Slower
Flexibility Low High
Design Complex, hard to modify Simple, easy to modify
Cost (large sets) High Low
Use RISC CISC

Components of the hardwired control unit

A hardwired unit produces the control signals with a fixed circuit. Its parts are as follows.

Instruction register (IR): it holds the instruction. The opcode part is sent to the decoder.

Instruction decoder: a decoder, for example 3 to 8, converts the opcode to one of the lines $D_0$ to $D_7$ . Each line stands for one instruction type.

Sequence counter (SC) and timing decoder: SC counts the clock pulses, and a 4 to 16 decoder produces the timing signals $T_0$ to $T_{15}$ . Each signal marks one step of the instruction. At the end, SC is cleared.

Flip-flops and flags: the mode bit I, the interrupt flip-flop R, and the status flags like zero and carry also affect the signals.

Control logic gates: a network of AND, OR and NOT gates combines the decoder outputs, the timing signals and the flags. For example, a load signal for AR is given by

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

Control outputs: these go to the registers, the ALU, the bus selectors and memory, and they decide what is done in each clock pulse.

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

The unit works at gate speed, but a change in the instruction set means a new circuit.

Explanation of the difference. In the hardwired unit, the signals are made by gates, so the speed is high but the circuit is fixed. In the microprogrammed unit, the signals are read from memory as microinstructions, so it is slow but easy to change. The first suits RISC, and the second suits CISC. A hardwired design needs a full redesign when a new instruction is added. A microprogrammed design needs only a new microroutine.
Hardwired versus microprogrammed control unit

Point Hardwired Microprogrammed
Control signals From logic gates From a control memory
Speed Fast Slower
Flexibility Low High
Design Complex, hard to modify Simple, easy to modify
Cost (large sets) High Low
Use RISC CISC

Components of the hardwired control unit

A hardwired unit produces the control signals with a fixed circuit. Its parts are as follows.

Instruction register (IR): it holds the instruction. The opcode part is sent to the decoder.

Instruction decoder: a decoder, for example 3 to 8, converts the opcode to one of the lines $D_0$ to $D_7$. Each line stands for one instruction type.

Sequence counter (SC) and timing decoder: SC counts the clock pulses, and a 4 to 16 decoder produces the timing signals $T_0$ to $T_{15}$. Each signal marks one step of the instruction. At the end, SC is cleared.

Flip-flops and flags: the mode bit I, the interrupt flip-flop R, and the status flags like zero and carry also affect the signals.

Control logic gates: a network of AND, OR and NOT gates combines the decoder outputs, the timing signals and the flags. For example, a load signal for AR is given by

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

Control outputs: these go to the registers, the ALU, the bus selectors and memory, and they decide what is done in each clock pulse.

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

The unit works at gate speed, but a change in the instruction set means a new circuit.

Explanation of the difference. In the hardwired unit, the signals are made by gates, so the speed is high but the circuit is fixed. In the microprogrammed unit, the signals are read from memory as microinstructions, so it is slow but easy to change. The first suits RISC, and the second suits CISC. A hardwired design needs a full redesign when a new instruction is added. A microprogrammed design needs only a new microroutine.
197 marksNumericalCache memoriesHideAnswer
Consider a cache (M1) and memory (M2) hierarchy with following characteristics: M1: 16K word, 50 ns Access time; M2: 1M word, 400 ns Access time. Assume 8-word cache blocks and set size 256 words with set associative mapping. (i) Show and explain the mapping between M2 and M1. (ii) Calculate the effective memory access time with cache hit ratio=0.95.
Cache M1 has 16K words and memory M2 has 1M words. Let a block have 8 words. A set has 256 words, so it holds $256/8 = 32$ blocks, and the cache is 32-way set associative.

(i) Mapping between M2 and M1

The sizes are

$\text{M1 blocks} = \frac{16384}{8} = 2048, \qquad \text{M1 sets} = \frac{16384}{256} = 64$

$\text{M2 blocks} = \frac{2^{20}}{8} = 131072$

M2 has 1M words, which is $2^{20}$ , so the address has 20 bits. The word field has $\log_2 8 = 3$ bits. The set field has $\log_2 64 = 6$ bits. The tag is

$20 - 6 - 3 = 11 \text{ bits}$

Tag Set Word
11 bits 6 bits 3 bits

The block number of M2, taken modulo 64, gives the set of M1. So blocks $0, 64, 128, \ldots$ of M2 go to set 0, blocks $1, 65, 129, \ldots$ go to set 1, and so on. Each set of M1 is shared by $131072/64 = 2048$ blocks of M2, which is $2^{11}$ , the number of different tags. Within the set, the block can be placed in any of the 32 places. The 11-bit tag stored with the block tells which of the 2048 blocks is present. To find a word, the set field picks the set. Then the 32 tags in that set are compared with the tag of the address in parallel.

M2 blocks (131072) M1 sets (64), 32 blocks each block 0, 64, 128 ... ----> Set 0 [ b ][ b ] ... [ b ] block 1, 65, 129 ... ----> Set 1 [ b ][ b ] ... [ b ] ... ... block 63, 127 ... ----> Set 63 [ b ][ b ] ... [ b ]

(ii) Effective memory access time

With hit ratio $h = 0.95$ , $t_1 = 50$ ns and $t_2 = 400$ ns, when the cache and memory are accessed in parallel on a miss,

$t_{eff} = h\,t_1 + (1-h)\,t_2 = 0.95 \times 50 + 0.05 \times 400 = 47.5 + 20 = 67.5 \text{ ns}$

Therefore the effective access time is 67.5 ns. If the memory is accessed only after the cache misses, the miss time is $50 + 400$ ns, and the time becomes $50 + 0.05 \times 400 = 70$ ns. Either way, it is close to the cache speed and much better than 400 ns.
Cache M1 has 16K words and memory M2 has 1M words. Let a block have 8 words. A set has 256 words, so it holds $256/8 = 32$ blocks, and the cache is 32-way set associative.

(i) Mapping between M2 and M1

The sizes are

$$\text{M1 blocks} = \frac{16384}{8} = 2048, \qquad \text{M1 sets} = \frac{16384}{256} = 64$$

$$\text{M2 blocks} = \frac{2^{20}}{8} = 131072$$

M2 has 1M words, which is $2^{20}$, so the address has 20 bits. The word field has $\log_2 8 = 3$ bits. The set field has $\log_2 64 = 6$ bits. The tag is

$$20 - 6 - 3 = 11 \text{ bits}$$

Tag Set Word
11 bits 6 bits 3 bits

The block number of M2, taken modulo 64, gives the set of M1. So blocks $0, 64, 128, \ldots$ of M2 go to set 0, blocks $1, 65, 129, \ldots$ go to set 1, and so on. Each set of M1 is shared by $131072/64 = 2048$ blocks of M2, which is $2^{11}$, the number of different tags. Within the set, the block can be placed in any of the 32 places. The 11-bit tag stored with the block tells which of the 2048 blocks is present. To find a word, the set field picks the set. Then the 32 tags in that set are compared with the tag of the address in parallel.

M2 blocks (131072) M1 sets (64), 32 blocks each block 0, 64, 128 ... ----> Set 0 [ b ][ b ] ... [ b ] block 1, 65, 129 ... ----> Set 1 [ b ][ b ] ... [ b ] ... ... block 63, 127 ... ----> Set 63 [ b ][ b ] ... [ b ]

(ii) Effective memory access time

With hit ratio $h = 0.95$, $t_1 = 50$ ns and $t_2 = 400$ ns, when the cache and memory are accessed in parallel on a miss,

$$t_{eff} = h,t_1 + (1-h),t_2 = 0.95 \times 50 + 0.05 \times 400 = 47.5 + 20 = 67.5 \text{ ns}$$

Therefore the effective access time is 67.5 ns. If the memory is accessed only after the cache misses, the miss time is $50 + 400$ ns, and the time becomes $50 + 0.05 \times 400 = 70$ ns. Either way, it is close to the cache speed and much better than 400 ns.
207 marksNumericalCache memoriesHideAnswer
Explain the direct mapping technique. Consider a digital computer has a memory unit of 64k*16 and cache memory of 1k words. The cache uses direct mapping with 4 block size of four words. (i) How many bits are there in the tag, block and word fields of the address format? (ii) How many blocks can the cache accommodate?
Direct mapping

In direct mapping, each block of main memory can be placed in only one fixed line of the cache. The line number is given by

$\text{line} = (\text{block number}) \bmod (\text{number of cache lines})$

The main memory address is divided into three fields: tag, index (block or line) and word. The word field selects a word inside the block. The block field selects the cache line. The tag is the remaining high bits. It is stored with each cache line. It tells which of the many memory blocks that share the line is now present.

On a memory reference, the line field selects the line. The stored tag is compared with the tag of the address. If they are equal and the valid bit is 1, it is a hit, and the word is taken. Otherwise it is a miss. The whole block is read from main memory into that line, and the old block is overwritten. No replacement algorithm is needed.

Merits: simple, cheap, and fast, as only one tag comparison is needed. Demerit: if two active blocks map to the same line, they replace each other again and again (thrashing), though other lines are free.

Numerical

Main memory is $64\text{K} \times 16$ , so the address has $\log_2 65536 = 16$ bits. The cache has 1K words, so the index has $\log_2 1024 = 10$ bits. A block has 4 words.

(i) The word field needs $\log_2 4 = 2$ bits. The cache has $1024/4 = 256$ lines, so the block field needs $\log_2 256 = 8$ bits. The tag is

$16 - 8 - 2 = 6 \text{ bits}$

Tag Block Word
6 bits 8 bits 2 bits

(ii) The number of blocks the cache can hold is

$\frac{1024}{4} = 256 \text{ blocks}$

Therefore the fields are tag 6 bits, block 8 bits and word 2 bits, and the cache can hold 256 blocks. The main memory has $65536/4 = 16384$ blocks, so every cache line is shared by 64 memory blocks.
Direct mapping

In direct mapping, each block of main memory can be placed in only one fixed line of the cache. The line number is given by

$$\text{line} = (\text{block number}) \bmod (\text{number of cache lines})$$

The main memory address is divided into three fields: tag, index (block or line) and word. The word field selects a word inside the block. The block field selects the cache line. The tag is the remaining high bits. It is stored with each cache line. It tells which of the many memory blocks that share the line is now present.

On a memory reference, the line field selects the line. The stored tag is compared with the tag of the address. If they are equal and the valid bit is 1, it is a hit, and the word is taken. Otherwise it is a miss. The whole block is read from main memory into that line, and the old block is overwritten. No replacement algorithm is needed.

Merits: simple, cheap, and fast, as only one tag comparison is needed. Demerit: if two active blocks map to the same line, they replace each other again and again (thrashing), though other lines are free.

Numerical

Main memory is $64\text{K} \times 16$, so the address has $\log_2 65536 = 16$ bits. The cache has 1K words, so the index has $\log_2 1024 = 10$ bits. A block has 4 words.

(i) The word field needs $\log_2 4 = 2$ bits. The cache has $1024/4 = 256$ lines, so the block field needs $\log_2 256 = 8$ bits. The tag is

$$16 - 8 - 2 = 6 \text{ bits}$$

Tag Block Word
6 bits 8 bits 2 bits

(ii) The number of blocks the cache can hold is

$$\frac{1024}{4} = 256 \text{ blocks}$$

Therefore the fields are tag 6 bits, block 8 bits and word 2 bits, and the cache can hold 256 blocks. The main memory has $65536/4 = 16384$ blocks, so every cache line is shared by 64 memory blocks.
217 marksSerial CommunicationHideAnswer
What do you mean by asynchronous data transfer? Explain strobe control and handshaking mechanism.
When two units use their own independent clocks, data moves between them by asynchronous transfer. The sender must show that the data is valid, and the receiver must show that it has taken it. The two methods are strobe control and handshaking.

Strobe control

A single control line, the strobe, tells when to transfer. In source-initiated strobe, the source puts data on the bus and then activates the strobe. The destination latches the data on the strobe. The source then removes the strobe and the data.

In destination-initiated strobe, the destination activates the strobe to ask for data. The source puts data on the bus. The destination latches it and removes the strobe, and the source removes the data.

Data ----<====valid====>---- Strobe ______|‾‾‾‾‾‾‾‾‾|______

The weakness is the lack of acknowledgement. The source does not know that the destination received the data, and the destination does not know that the data is really valid.

Handshaking

Handshaking uses two lines, one in each direction, so that every action gets a reply.

In source-initiated handshaking, the lines are data valid and data accepted. The sequence is:

The source puts data on the bus and enables data valid.

The destination takes the data and enables data accepted.

The source disables data valid and removes the data.

The destination disables data accepted. The system is ready for the next word.

In destination-initiated handshaking, the lines are ready for data and data valid. The destination first enables ready for data. The source places data and enables data valid. The destination latches the data and disables ready for data. Finally, the source disables data valid.

Comparison

Point Strobe Handshaking
Control lines One Two
Reply from the other unit None Yes
Reliability Lower Higher
Speed difference handled Poorly Well

A time-out circuit is often added with handshaking, to flag an error if a unit does not reply. Handshaking is used in most real interfaces, because it works safely for units of any speed.

Sign	Exponent	Fraction
0	10000101	01010100100000000000000

Sign	Exponent	Fraction
1	10000111	00110011001100000000000

Sign	Exponent	Fraction
0	10000101	01010100100000000000000

Sign	Exponent	Fraction
1	10000111	00110011001100000000000

Point	Hardwired	Microprogrammed
Control signals	From logic gates	From a control memory
Speed	Fast	Slower
Flexibility	Low	High
Design	Complex, hard to modify	Simple, easy to modify
Cost (large sets)	High	Low
Use	RISC	CISC

Point	Hardwired	Microprogrammed
Control signals	From logic gates	From a control memory
Speed	Fast	Slower
Flexibility	Low	High
Design	Complex, hard to modify	Simple, easy to modify
Cost (large sets)	High	Low
Use	RISC	CISC

Tag	Set	Word
11 bits	6 bits	3 bits

Tag	Set	Word
11 bits	6 bits	3 bits

Tag	Block	Word
6 bits	8 bits	2 bits

Tag	Block	Word
6 bits	8 bits	2 bits

Point	Strobe	Handshaking
Control lines	One	Two
Reply from the other unit	None	Yes
Reliability	Lower	Higher
Speed difference handled	Poorly	Well

227 marksModes of Data TransferAnswer

Explain the various modes of data transfer and discuss direct memory access mode in detail. Also explain how DMA is superior to other modes.

Modes of data transfer

There are three modes of data transfer between the CPU, memory and I/O devices.

Programmed I/O. The CPU runs a program that polls the status flag of the device. When the device is ready, the CPU moves one word. The CPU is busy waiting for the whole time, which wastes its power.

Interrupt-initiated I/O. The device interrupts the CPU when it is ready. The CPU saves its state, runs the service routine to move a word, and returns. The CPU is free between interrupts, but each word costs the time of an interrupt.

Direct memory access (DMA). A DMA controller moves a whole block between the device and memory, without involving the CPU in each word.

Direct memory access in detail

The CPU first loads the DMA controller with the starting memory address, the word count and the direction of the transfer, and then goes on with its work.

When the device is ready, it sends a DMA request to the controller. The controller sends a bus request to the CPU. The CPU completes the present cycle, puts its buses in the high impedance state, and sends back a bus grant. The controller now controls the buses. It places the memory address on the address bus, activates the read or write signal, and the word passes between the device and memory.

After each word, the address register increases by one and the word count decreases by one. The cycle is repeated until the count is zero. The controller then removes the bus request and interrupts the CPU to say that the block is finished.

DMA can work in burst mode, where the whole block is moved at one go. It can also work in cycle stealing mode, where one word is moved and the bus is given back to the CPU each time.

Why DMA is better than the other modes

Point	Programmed	Interrupt-initiated	DMA
CPU involvement	Every word	Every word	Start and end only
Speed of transfer	Slow	Medium	Fast
CPU waiting	Busy waits	Free, but with overhead	Free for the whole block
Best for	Simple tasks	Slow devices	Disks, bulk data

In programmed I/O the CPU is occupied by waiting. In interrupt-initiated I/O the CPU is not waiting, but it spends time saving and restoring state for each word, and the rate of transfer is limited by this. In DMA, the data goes straight to memory at the speed of the device and memory. The CPU only sets up the transfer and handles one interrupt at the end. Therefore DMA is the best choice for large blocks of data, and it gives the best use of the CPU. Its only costs are the extra hardware of the controller and some bus sharing.

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2025-26 paper 2024-25 paper 2022-23 paper 2021-22 paper 2020-21 paper 2019-20 paper