BCS302 · AKTU past paper

Computer Organization and Architecture 2022-23 question paper

The complete AKTU 2022-23 exam paper for Computer Organization and Architecture (BCS302), all 25 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 marksInstruction types, formats, instruction cyHideAnswer
List the steps involved in an instruction cycle.
The instruction cycle has these steps, repeated for every instruction:

Fetch: the instruction is read from the memory location given by PC into the instruction register, and PC is increased.

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

Read the effective address: if the address is indirect, the operand address is read from memory.

Execute: the operation is done, for example an ALU operation, a data transfer or a branch.

Store the result: the result goes to a register or to memory.

Interrupt check: the CPU checks for a pending interrupt, then starts the next cycle.
22 marksRegister, bus and memory transferHideAnswer
How memory read and write operations are performed in computer system?
Memory is connected to the CPU through the address register (AR), the data register (DR) and the control signals.

For a read, the CPU puts the address of the required word in AR and activates the read signal. The memory places the word on the data lines, and it is loaded into DR.

$Read:\ DR \leftarrow M[AR]$

For a write, the CPU puts the address in AR and the data in DR, and activates the write signal. The memory stores the word at that address.

$Write:\ M[AR] \leftarrow DR$

Each operation takes one memory cycle.
Memory is connected to the CPU through the address register (AR), the data register (DR) and the control signals.

For a read, the CPU puts the address of the required word in AR and activates the read signal. The memory places the word on the data lines, and it is loaded into DR.

$$Read:\ DR \leftarrow M[AR]$$

For a write, the CPU puts the address in AR and the data in DR, and activates the write signal. The memory stores the word at that address.

$$Write:\ M[AR] \leftarrow DR$$

Each operation takes one memory cycle.
32 marksRegister, bus and memory transferHideAnswer
Define bus and memory transfer?
A bus is a set of common wires that carries information between the units of a computer. A bus transfer moves the content of one register to another register over this common path, and it is written as $R2 \leftarrow R1$ .

A memory transfer is the movement of data between the CPU and the memory. A read brings a word from memory into a register, written $DR \leftarrow M[AR]$ . A write stores a register's content into memory, written $M[AR] \leftarrow DR$ . Here AR holds the address and DR holds the data.
A bus is a set of common wires that carries information between the units of a computer. A bus transfer moves the content of one register to another register over this common path, and it is written as $R2 \leftarrow R1$.

A memory transfer is the movement of data between the CPU and the memory. A read brings a word from memory into a register, written $DR \leftarrow M[AR]$. A write stores a register's content into memory, written $M[AR] \leftarrow DR$. Here AR holds the address and DR holds the data.
42 marksNumericalCache memoriesHideAnswer
Define HIT and MISS ratio in memory with an example.
The hit ratio is the fraction of CPU memory references that are found in the cache. The miss ratio is the fraction that are not found, so

$\text{hit ratio} + \text{miss ratio} = 1$

For example, suppose the CPU makes 200 references and 180 are found in the cache. Then the hit ratio is $180/200 = 0.9$ and the miss ratio is $20/200 = 0.1$ . On a miss, the block must be fetched from the slower main memory.
The hit ratio is the fraction of CPU memory references that are found in the cache. The miss ratio is the fraction that are not found, so

$$\text{hit ratio} + \text{miss ratio} = 1$$

For example, suppose the CPU makes 200 references and 180 are found in the cache. Then the hit ratio is $180/200 = 0.9$ and the miss ratio is $20/200 = 0.1$. On a miss, the block must be fetched from the slower main memory.
52 marksInstruction types, formats, instruction cyHideAnswer
Define instruction cycle.
The instruction cycle is the complete set of steps the CPU takes to process one instruction. It begins with fetching the instruction from memory, and goes on with decoding it, reading the operands, executing the operation, and storing the result. The CPU then repeats the cycle for the next instruction, whose address is in the program counter. A computer keeps running instruction cycles as long as it is working a program.

62 marksProgram Control, Reduced Instruction Set CAnswer

Differentiate between RISC and CISC.

RISC uses a small set of simple, fixed-length instructions, each done in about one clock cycle. CISC uses a large set of complex, variable-length instructions that may take many cycles.

Point	RISC	CISC
Instructions	Few, simple	Many, complex
Memory access	LOAD and STORE only	Many instructions
Registers	Many	Few
Control	Hardwired	Microprogrammed
Pipelining	Easy	Hard
Code size	Larger	Smaller
Example	ARM, MIPS	x86

72 markssemiconductor RAM memories, 2D & 2 1/2D meAnswer

List the difference between static RAM and dynamic RAM.

Both are semiconductor RAM, but they differ in how a bit is stored and in cost.

Static RAM	Dynamic RAM
Uses flip-flops to store bits	Uses a capacitor and a transistor
No refresh needed	Must be refreshed regularly
Fast access	Slower access
Costly, less bits per chip	Cheap, more bits per chip
Used for cache	Used for main memory

Because of these differences, a computer uses a little SRAM for speed and a large amount of DRAM for capacity.

82 marksVirtual memoryHideAnswer
Define Virtual memory.
Virtual memory is a technique that gives a program the feeling of a very large main memory, bigger than the real RAM. The program uses virtual addresses. The system keeps the active parts in main memory and the rest on the disk, and it moves parts in and out as needed. The address translation is done by hardware, using a page table, so the programmer does not need to manage it.
92 marksPeripheral devices, I/O interface, I/O porHideAnswer
List down the functions performed by an Input/Output unit.
The main functions of an Input/Output unit are:

Interfacing the CPU and memory with the I/O devices through the system bus.

Selecting the correct device by decoding the address.

Converting data between the different formats and signal levels of the device and the CPU (for example parallel and serial).

Matching the speed of the fast CPU to the slow devices, by buffering data.

Giving the CPU control and status information, such as ready, busy and error.

Detecting errors and sending an interrupt when the device needs service.
102 marksModes of Data TransferHideAnswer
Why does the DMA get priority over CPU when both request memory transfer?
The DMA controller gets priority over the CPU for the memory bus because an I/O device cannot wait. A device such as a disk delivers data at a fixed speed. If its word is not moved at once, the next word overwrites it and data is lost.

The CPU, on the other hand, can be delayed for a cycle without any harm. It only runs a little slower. Hence the memory cycle goes to the DMA controller first, which also keeps the high speed device working at full rate.
1110 marksFunctional units of digital system and theHideAnswer
Explain functional units of computer system in detail.
A computer is a system made of five functional units. They are the input unit, the memory unit, the arithmetic and logic unit, the control unit and the output unit. The ALU and control unit together are called the central processing unit (CPU). Each unit does a clear job, and they work together under the control of a stored program.

Input unit

The input unit takes data and instructions from the user and converts them into binary form that the computer can use. Keyboard, mouse, scanner and microphone are examples. The data is placed in memory or sent to a register of the CPU. Input is usually read one character or one word at a time.

Memory unit

The memory stores programs and data. It has two levels. The main (primary) memory, made of semiconductor RAM, is fast and holds the programs now being run. It is directly used by the CPU. The secondary memory, such as a hard disk or SSD, is larger and cheaper but slower. It keeps programs and data permanently. Each word of main memory has an address, and the CPU can reach any word by giving its address.

Arithmetic and logic unit (ALU)

The ALU does the arithmetic operations such as add, subtract, multiply and divide. It also does logic operations such as AND, OR, NOT and comparison. The operands come from registers. The result goes back to a register. A set of flag bits records things like zero, carry and overflow.

Control unit

The control unit is the brain of the computer. It reads each instruction from memory, decodes it, and sends the right timing and control signals to the other units. It tells memory when to read or write, tells the ALU what to do, and tells the input and output devices when to transfer data. It does not process data itself. The program counter (PC) holds the address of the next instruction, and the instruction register (IR) holds the present one.

Output unit

The output unit shows the results to the user in a form that people can understand. Monitor, printer and speakers are examples. It receives the binary results from the memory or CPU and converts them.

Interconnection

The units are joined by the system bus, which has an address bus, a data bus and a control bus. Data goes from the input unit to memory, then through the ALU, then back to memory and out through the output unit. The control unit directs the whole flow.

Working in short

A program is first loaded into memory through the input unit. The control unit fetches an instruction, decodes it and fetches the operands. The ALU does the work and the result is stored or displayed. This fetch, decode and execute cycle repeats until the program ends.
1210 marksNumericalIEEE Standard for Floating Point NumbersHideAnswer
Explain IEEE-754 standard for floating point representation. Express (314.175)10 in all the IEEE-754 models.
IEEE 754 is the standard format for real numbers in almost every computer. A number is stored as $(-1)^s \times 1.f \times 2^{e}$ in three fields: the sign bit $s$ (0 for positive, 1 for negative), the biased exponent $E = e + \text{bias}$ , and the fraction $f$ . The leading 1 is implied and not stored.

Model Total bits Sign Exponent Fraction Bias
Single precision 32 1 8 23 127
Double precision 64 1 11 52 1023

The bias keeps the stored exponent positive, so numbers can be compared like integers. The all-0 and all-1 exponent patterns are kept for special values.

Exponent Fraction Meaning
all 0 0 zero
all 0 not 0 denormal number
all 1 0 infinity
all 1 not 0 NaN (not a number)

Normal numbers use the stored exponents 1 to 254 in single precision and 1 to 2046 in double precision. Rounding to the nearest value is the default way to fit a long fraction into the fraction field, and it keeps the error below half of the last bit.

Representing 314.175

The number is positive, so $s = 0$ . The integer part is $314 = 100111010_2$ . For the fraction, we double $0.175$ again and again and note the digits:

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

So the number is $100111010.0010110011\ldots_2$ . Move the point 8 places left to normalise:

$314.175 = 1.001110100010110011\ldots_2 \times 2^{8}$

The true exponent is $e = 8$ . The fraction starts with $00111010$ (from the integer part) and then continues with the digits of $0.175$ .

Single precision. The stored exponent is:

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

The fraction takes 23 bits. The bits after the 23rd are $0110\ldots$ , which are less than half, so we round down. Therefore:

Sign Exponent Fraction
0 10000111 00111010001011001100110

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

Double precision. The stored exponent is:

$E = 8 + 1023 = 1031 = 10000000111_2$

The fraction takes 52 bits. The bits after the 52nd are $1100\ldots$ , which is more than half, so the last bit is rounded up. Therefore:

Sign Exponent Fraction
0 10000000111 0011101000101100110011001100110011001100110011001101

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

Neither answer is exact, because $0.175$ has a repeating binary fraction. The error is about $10^{-5}$ in single precision and about $10^{-14}$ in double precision. To check the single answer, decode it: $E = 135$ gives $e = 8$ , and the value is $1.00111010001011001100110_2 \times 2^8 \approx 314.17499$ .
IEEE 754 is the standard format for real numbers in almost every computer. A number is stored as $(-1)^s \times 1.f \times 2^{e}$ in three fields: the sign bit $s$ (0 for positive, 1 for negative), the biased exponent $E = e + \text{bias}$, and the fraction $f$. The leading 1 is implied and not stored.

Model Total bits Sign Exponent Fraction Bias
Single precision 32 1 8 23 127
Double precision 64 1 11 52 1023

The bias keeps the stored exponent positive, so numbers can be compared like integers. The all-0 and all-1 exponent patterns are kept for special values.

Exponent Fraction Meaning
all 0 0 zero
all 0 not 0 denormal number
all 1 0 infinity
all 1 not 0 NaN (not a number)

Normal numbers use the stored exponents 1 to 254 in single precision and 1 to 2046 in double precision. Rounding to the nearest value is the default way to fit a long fraction into the fraction field, and it keeps the error below half of the last bit.

Representing 314.175

The number is positive, so $s = 0$. The integer part is $314 = 100111010_2$. For the fraction, we double $0.175$ again and again and note the digits:

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

So the number is $100111010.0010110011\ldots_2$. Move the point 8 places left to normalise:

$$314.175 = 1.001110100010110011\ldots_2 \times 2^{8}$$

The true exponent is $e = 8$. The fraction starts with $00111010$ (from the integer part) and then continues with the digits of $0.175$.

Single precision. The stored exponent is:

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

The fraction takes 23 bits. The bits after the 23rd are $0110\ldots$, which are less than half, so we round down. Therefore:

Sign Exponent Fraction
0 10000111 00111010001011001100110

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

Double precision. The stored exponent is:

$$E = 8 + 1023 = 1031 = 10000000111_2$$

The fraction takes 52 bits. The bits after the 52nd are $1100\ldots$, which is more than half, so the last bit is rounded up. Therefore:

Sign Exponent Fraction
0 10000000111 0011101000101100110011001100110011001100110011001101

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

Neither answer is exact, because $0.175$ has a repeating binary fraction. The error is about $10^{-5}$ in single precision and about $10^{-14}$ in double precision. To check the single answer, decode it: $E = 135$ gives $e = 8$, and the value is $1.00111010001011001100110_2 \times 2^8 \approx 314.17499$.
1310 marksProgram Control, Reduced Instruction Set CHideAnswer
Explain the concept of pipelining and also explain types of pipelining.
Pipelining is a technique in which the work of an instruction is broken into stages, and many instructions are processed at the same time, each in a different stage. Think of a laundry with a washer, a dryer and an iron. While one load is in the dryer, the next load is already in the washer. In the same way, a new instruction enters the pipeline in every clock cycle.

The space-time diagram shows the stages (space) on one axis and the clock cycles (time) on the other. After the first few cycles, the pipeline is full, and one instruction finishes in every cycle.

Speedup. For $k$ stages, $n$ tasks and a clock time $t_p$ :

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

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

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

For a very large $n$ , the speedup comes close to $k$ . For example, for $k = 4$ and $n = 100$ , the speedup is $400/103 \approx 3.88$ .

Types of pipelining

Arithmetic pipeline: the stages of an arithmetic operation are overlapped. For floating point addition, the stages are compare exponents, align mantissas, add mantissas and normalize the result. It is used in vector processors and in floating point units.

Instruction pipeline: the instruction cycle is split into stages like fetch, decode, operand fetch, execute and write back. A new instruction is fetched while the earlier ones are in later stages.

Processor pipeline: a stream of data passes through a series of processors, each doing a part of the job. This is less common.

Linear and non-linear pipelines: in a linear pipeline, data flows from the first stage to the last in one direction. A non-linear pipeline has feedback or feed-forward paths, so a stage may be used more than once.

Static and dynamic pipelines: a static pipeline does one type of function at a time. A dynamic one can do different functions at different times.

Unifunction and multifunction pipelines: the first does a fixed function, the second can be set to do several.

Hazards. A pipeline may stall because of three kinds of hazards. A structural hazard is when two stages need the same resource. A data hazard is when an instruction needs a result that is not ready. A control hazard comes from branches. They are solved by stalling, forwarding data and predicting branches.

Advantage. Pipelining raises the throughput without making any single instruction faster. The cost is extra registers between the stages and more complex control.

Example of an instruction pipeline. With four stages (fetch, decode, execute, write back), the first instruction finishes after 4 cycles. After that, one instruction finishes in each cycle. So 10 instructions need $4 + 10 - 1 = 13$ cycles, while without pipelining they need $10 \times 4 = 40$ cycles.
Pipelining is a technique in which the work of an instruction is broken into stages, and many instructions are processed at the same time, each in a different stage. Think of a laundry with a washer, a dryer and an iron. While one load is in the dryer, the next load is already in the washer. In the same way, a new instruction enters the pipeline in every clock cycle.

The space-time diagram shows the stages (space) on one axis and the clock cycles (time) on the other. After the first few cycles, the pipeline is full, and one instruction finishes in every cycle.

Speedup. For $k$ stages, $n$ tasks and a clock time $t_p$:

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

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

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

For a very large $n$, the speedup comes close to $k$. For example, for $k = 4$ and $n = 100$, the speedup is $400/103 \approx 3.88$.

Types of pipelining

Arithmetic pipeline: the stages of an arithmetic operation are overlapped. For floating point addition, the stages are compare exponents, align mantissas, add mantissas and normalize the result. It is used in vector processors and in floating point units.

Instruction pipeline: the instruction cycle is split into stages like fetch, decode, operand fetch, execute and write back. A new instruction is fetched while the earlier ones are in later stages.

Processor pipeline: a stream of data passes through a series of processors, each doing a part of the job. This is less common.

Linear and non-linear pipelines: in a linear pipeline, data flows from the first stage to the last in one direction. A non-linear pipeline has feedback or feed-forward paths, so a stage may be used more than once.

Static and dynamic pipelines: a static pipeline does one type of function at a time. A dynamic one can do different functions at different times.

Unifunction and multifunction pipelines: the first does a fixed function, the second can be set to do several.

Hazards. A pipeline may stall because of three kinds of hazards. A structural hazard is when two stages need the same resource. A data hazard is when an instruction needs a result that is not ready. A control hazard comes from branches. They are solved by stalling, forwarding data and predicting branches.

Advantage. Pipelining raises the throughput without making any single instruction faster. The cost is extra registers between the stages and more complex control.

Example of an instruction pipeline. With four stages (fetch, decode, execute, write back), the first instruction finishes after 4 cycles. After that, one instruction finishes in each cycle. So 10 instructions need $4 + 10 - 1 = 13$ cycles, while without pipelining they need $10 \times 4 = 40$ cycles.
1410 marksNumericalCache memoriesHideAnswer
Consider a cache consisting of 256 blocks of 16 words each for a total of 4096 words and assume that the main memory is addressable by a 16 bits address and it consists of 4K blocks. How many bits are there in each of TAG, SET, WORD field for 2-way set associative technique?
The cache has 256 blocks of 16 words each, so it holds $256 \times 16 = 4096$ words. Main memory is addressed by 16 bits, so it has $2^{16} = 65536$ words. With 16 words per block, main memory has $65536/16 = 4096$ blocks, which matches the 4K blocks given.

In set-associative mapping, the cache blocks are grouped into sets. A memory block maps to one set, and it can sit in any block of that set. The address is divided into tag, set and word fields.

Word field

A block has 16 words, so the word field must select one of 16 words:

$\text{word} = \log_2 16 = 4 \text{ bits}$

Set field

The cache is 2-way, so each set has 2 blocks. The number of sets is

$\text{sets} = \frac{256}{2} = 128$

so the set field has

$\log_2 128 = 7 \text{ bits}$

Tag field

The tag is what remains of the 16-bit address:

$\text{tag} = 16 - 7 - 4 = 5 \text{ bits}$

The address format is

Tag Set Word
5 bits 7 bits 4 bits

Therefore the fields are TAG = 5 bits, SET = 7 bits and WORD = 4 bits.

Check

The tag and set bits together give the block number of main memory: $5 + 7 = 12$ bits, and $2^{12} = 4096$ blocks, which agrees with the given size. Each set receives $4096/128 = 32$ memory blocks, and the 5-bit tag tells which of those 32 blocks sits in a cache block. The set has only 2 places, so at most 2 of those 32 blocks can be present at one time.

Working

When the CPU gives an address, the set field picks one set. The tags of both blocks of that set are compared with the tag of the address at the same time. If one of them matches and its valid bit is 1, it is a hit, and the word field selects the word. If neither matches, it is a miss. The block is fetched from main memory into the set, replacing one of the two blocks by the LRU or FIFO rule.

Comparison with other mappings

For the same cache, direct mapping would use 256 lines, giving tag $= 16 - 8 - 4 = 4$ bits, line 8 bits and word 4 bits. Fully associative mapping would use a tag of $16 - 4 = 12$ bits and no set field. The 2-way scheme lies between the two. Going from direct to 2-way, the tag grows by one bit and the set field shrinks by one bit, because the number of sets halves.

A short example shows the use of the fields. Take a memory block whose 12-bit block number has tag 10110 and set field 0000101 (which is 5). This block can go only to set 5 of the cache, in either of its two blocks. Any block with the same last 7 bits, such as one with tag $00001$ , also competes for set 5. The two together can stay in the cache, which would be impossible in direct mapping.

The 2-way scheme needs only two comparators, and it still removes many conflicts.
The cache has 256 blocks of 16 words each, so it holds $256 \times 16 = 4096$ words. Main memory is addressed by 16 bits, so it has $2^{16} = 65536$ words. With 16 words per block, main memory has $65536/16 = 4096$ blocks, which matches the 4K blocks given.

In set-associative mapping, the cache blocks are grouped into sets. A memory block maps to one set, and it can sit in any block of that set. The address is divided into tag, set and word fields.

Word field

A block has 16 words, so the word field must select one of 16 words:

$$\text{word} = \log_2 16 = 4 \text{ bits}$$

Set field

The cache is 2-way, so each set has 2 blocks. The number of sets is

$$\text{sets} = \frac{256}{2} = 128$$

so the set field has

$$\log_2 128 = 7 \text{ bits}$$

Tag field

The tag is what remains of the 16-bit address:

$$\text{tag} = 16 - 7 - 4 = 5 \text{ bits}$$

The address format is

Tag Set Word
5 bits 7 bits 4 bits

Therefore the fields are TAG = 5 bits, SET = 7 bits and WORD = 4 bits.

Check

The tag and set bits together give the block number of main memory: $5 + 7 = 12$ bits, and $2^{12} = 4096$ blocks, which agrees with the given size. Each set receives $4096/128 = 32$ memory blocks, and the 5-bit tag tells which of those 32 blocks sits in a cache block. The set has only 2 places, so at most 2 of those 32 blocks can be present at one time.

Working

When the CPU gives an address, the set field picks one set. The tags of both blocks of that set are compared with the tag of the address at the same time. If one of them matches and its valid bit is 1, it is a hit, and the word field selects the word. If neither matches, it is a miss. The block is fetched from main memory into the set, replacing one of the two blocks by the LRU or FIFO rule.

Comparison with other mappings

For the same cache, direct mapping would use 256 lines, giving tag $= 16 - 8 - 4 = 4$ bits, line 8 bits and word 4 bits. Fully associative mapping would use a tag of $16 - 4 = 12$ bits and no set field. The 2-way scheme lies between the two. Going from direct to 2-way, the tag grows by one bit and the set field shrinks by one bit, because the number of sets halves.

A short example shows the use of the fields. Take a memory block whose 12-bit block number has tag 10110 and set field 0000101 (which is 5). This block can go only to set 5 of the cache, in either of its two blocks. Any block with the same last 7 bits, such as one with tag $00001$, also competes for set 5. The two together can stay in the cache, which would be impossible in direct mapping.

The 2-way scheme needs only two comparators, and it still removes many conflicts.

Model	Total bits	Sign	Exponent	Fraction	Bias
Single precision	32	1	8	23	127
Double precision	64	1	11	52	1023

Exponent	Fraction	Meaning
all 0	0	zero
all 0	not 0	denormal number
all 1	0	infinity
all 1	not 0	NaN (not a number)

Sign	Exponent	Fraction
0	10000111	00111010001011001100110

Sign	Exponent	Fraction
0	10000000111	0011101000101100110011001100110011001100110011001101

Model	Total bits	Sign	Exponent	Fraction	Bias
Single precision	32	1	8	23	127
Double precision	64	1	11	52	1023

Exponent	Fraction	Meaning
all 0	0	zero
all 0	not 0	denormal number
all 1	0	infinity
all 1	not 0	NaN (not a number)

Sign	Exponent	Fraction
0	10000111	00111010001011001100110

Sign	Exponent	Fraction
0	10000000111	0011101000101100110011001100110011001100110011001101

Tag	Set	Word
5 bits	7 bits	4 bits

Tag	Set	Word
5 bits	7 bits	4 bits

1510 marksInterruptsAnswer

Define interrupt. Also discuss different types of interrupt.

Definition

An interrupt is a signal sent to the CPU by hardware or software that asks the CPU to stop its current program temporarily and run a special routine, the interrupt service routine (ISR). After the ISR, the CPU returns to the interrupted program from the same place. The CPU saves the program counter and the flags before it jumps, and restores them afterwards.

Interrupts remove the need for the CPU to wait for slow devices. The CPU can do useful work and is called only when something needs attention.

The CPU checks for an interrupt at the end of each instruction cycle. If one is pending and interrupts are enabled, it runs the interrupt cycle.

Types of interrupts

Interrupts are grouped in several ways.

Hardware interrupts come from external devices through the interrupt pins of the CPU.

Maskable interrupts can be enabled or disabled by the program, using flags such as IF. Keyboard and disk interrupts are examples. The CPU ignores them when they are masked.
Non-maskable interrupts (NMI) cannot be disabled. They signal very serious events such as power failure or a memory parity error, and have the highest priority.

Software interrupts are caused by an instruction in the program, such as INT n in the 8086 or a system call. They are used by programs to ask the operating system for a service, for example to read a file.

Exceptions (internal interrupts or traps) are raised by the CPU itself when it finds an unusual condition during an instruction. Examples are divide by zero, overflow, an illegal opcode, a page fault and a protection violation. They are synchronous, meaning that they happen at a fixed point of the program.

Interrupts are also classified by the way the service routine is found.

Vectored interrupts: the device sends a vector number, so the CPU jumps to the correct routine directly. This is fast.
Non-vectored interrupts: the CPU jumps to one fixed address, and the routine has to poll the devices to find the cause. This is slower.

Priority

When many interrupts come together, priority decides the order. Hardware priority is made by a daisy chain or a priority encoder. Software priority is made by polling. The NMI and the exceptions usually rank above ordinary device interrupts.

Difference between external and internal interrupts

Point	External (hardware)	Internal (exception, software)
Source	I/O devices and timers	CPU or program
Timing	Asynchronous, at any time	Synchronous, at a known instruction
Examples	Keyboard, NMI, timer	Divide by zero, INT n, page fault

An interrupt is thus the means by which a computer responds quickly to events in the outside world and to errors in the program itself.

1610 marksProcessor organization, general registers HideAnswer
Explain about stack organization used in processors. What do you understand by register stack?
A stack is a storage structure in which items are inserted and removed only at one end, called the top of the stack. The last item put in is the first one taken out. This is the last-in, first-out (LIFO) rule. A processor keeps a register called the stack pointer (SP) that always holds the address of the top item.

Two operations work on a stack. PUSH inserts a new item on the top, and POP removes the top item. The stack can be built inside the CPU as a set of registers, or as a part of main memory.

Uses of stack in processors

Evaluation of arithmetic expressions in reverse Polish notation, using zero-address instructions.

Saving the return address and the local data when a subroutine is called, so that nested and recursive calls work.

Saving the state of the processor when an interrupt occurs.

For example, to compute $(A+B)*C$ the stack machine runs PUSH A, PUSH B, ADD, PUSH C, MUL. Each operator takes the top two items and leaves the result on the top. No address is given for the operators.

Register stack

A register stack is a small group of registers organized as a stack. Take a stack of 64 words. The stack pointer SP has 6 bits and holds the address of the top. Two flip-flops, FULL and EMPTY, show whether the stack is full or empty. DR is the data register that holds the word to be pushed or the word that is popped.

At the start, $SP = 0$ , $EMPTY = 1$ and $FULL = 0$ . A push is done by

$SP \leftarrow SP + 1$

$M[SP] \leftarrow DR$

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

After the push of the 63rd item, SP is 63. One more push makes SP wrap round to 0, which sets FULL. A pop is done by

$DR \leftarrow M[SP]$

$SP \leftarrow SP - 1$

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

A push when FULL is set, or a pop when EMPTY is set, is an error and is not allowed. Register stacks are very fast, as no memory access is needed, but they are small.

Memory stack

The same idea works with part of main memory. Then SP points to a memory word. The stack grows toward lower addresses. A push does $SP \leftarrow SP - 1$ and $M[SP] \leftarrow DR$ . A pop does $DR \leftarrow M[SP]$ and $SP \leftarrow SP + 1$ . This stack can be large, but each access is slower.

In short, a register stack is a fast hardware stack made of registers, with FULL and EMPTY flags to guard its limits.
A stack is a storage structure in which items are inserted and removed only at one end, called the top of the stack. The last item put in is the first one taken out. This is the last-in, first-out (LIFO) rule. A processor keeps a register called the stack pointer (SP) that always holds the address of the top item.

Two operations work on a stack. PUSH inserts a new item on the top, and POP removes the top item. The stack can be built inside the CPU as a set of registers, or as a part of main memory.

Uses of stack in processors

Evaluation of arithmetic expressions in reverse Polish notation, using zero-address instructions.

Saving the return address and the local data when a subroutine is called, so that nested and recursive calls work.

Saving the state of the processor when an interrupt occurs.

For example, to compute $(A+B)*C$ the stack machine runs PUSH A, PUSH B, ADD, PUSH C, MUL. Each operator takes the top two items and leaves the result on the top. No address is given for the operators.

Register stack

A register stack is a small group of registers organized as a stack. Take a stack of 64 words. The stack pointer SP has 6 bits and holds the address of the top. Two flip-flops, FULL and EMPTY, show whether the stack is full or empty. DR is the data register that holds the word to be pushed or the word that is popped.

At the start, $SP = 0$, $EMPTY = 1$ and $FULL = 0$. A push is done by

$$SP \leftarrow SP + 1$$

$$M[SP] \leftarrow DR$$

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

After the push of the 63rd item, SP is 63. One more push makes SP wrap round to 0, which sets FULL. A pop is done by

$$DR \leftarrow M[SP]$$

$$SP \leftarrow SP - 1$$

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

A push when FULL is set, or a pop when EMPTY is set, is an error and is not allowed. Register stacks are very fast, as no memory access is needed, but they are small.

Memory stack

The same idea works with part of main memory. Then SP points to a memory word. The stack grows toward lower addresses. A push does $SP \leftarrow SP - 1$ and $M[SP] \leftarrow DR$. A pop does $DR \leftarrow M[SP]$ and $SP \leftarrow SP + 1$. This stack can be large, but each access is slower.

In short, a register stack is a fast hardware stack made of registers, with FULL and EMPTY flags to guard its limits.
1710 marksNumericalProcessor organization, general registers HideAnswer
What is an effective address? How it is calculated in different types of addressing modes? Explain.
The effective address (EA) is the actual memory address of the operand. An instruction has an opcode and an address field. In some modes the address field is already the address, but in others it has to be changed by adding a register, or by reading memory, before the true address is known. The addressing mode tells the CPU how to do this. The EA is found by the CPU at execution time.

Calculation in the common modes

In direct addressing the address field gives the address, so

$EA = A$

In indirect addressing, the address field gives the location of a word that holds the address, so

$EA = M[A]$

In register indirect addressing, a register holds the address, so

$EA = (R)$

In relative addressing, the address field is added to the program counter, so

$EA = PC + A$

In indexed addressing, the address field is added to an index register, so

$EA = A + (XR)$

In base register addressing, an offset is added to a base register, so

$EA = (BR) + A$

In immediate addressing there is no effective address, as the operand is in the instruction. In register addressing, the operand is in the register, so no memory address is needed either. In autoincrement mode, EA is the register's value, and then the register is increased.

Worked example

Take an instruction located at 200, with the address field 500 at location 201. Let the register $R = 400$ , the index register $XR = 100$ , and $M[500] = 800$ . After the fetch, $PC = 202$ .

$\text{Direct: } EA = 500$

$\text{Indirect: } EA = M[500] = 800$

$\text{Register indirect: } EA = 400$

$\text{Relative: } EA = 202 + 500 = 702$

$\text{Indexed: } EA = 500 + 100 = 600$

Therefore the same instruction reads from five different locations, depending on the mode.

Mode EA Memory accesses for the operand
Direct A 1
Indirect M[A] 2
Register indirect (R) 1
Relative PC + A 1
Indexed A + (XR) 1
Immediate none 0
Register none 0

A note on the mode with autoincrement: it is useful when a loop reads one array element after another. The register points to the element, the instruction uses it, and the register moves on to the next element by itself. This saves a separate add instruction each time.

Direct addressing is simple. Indirect addressing gives a bigger address range and allows pointers, but it is slow. Indexed and relative modes help with arrays and branches. The right mode makes the program shorter and flexible.
The effective address (EA) is the actual memory address of the operand. An instruction has an opcode and an address field. In some modes the address field is already the address, but in others it has to be changed by adding a register, or by reading memory, before the true address is known. The addressing mode tells the CPU how to do this. The EA is found by the CPU at execution time.

Calculation in the common modes

In direct addressing the address field gives the address, so

$$EA = A$$

In indirect addressing, the address field gives the location of a word that holds the address, so

$$EA = M[A]$$

In register indirect addressing, a register holds the address, so

$$EA = (R)$$

In relative addressing, the address field is added to the program counter, so

$$EA = PC + A$$

In indexed addressing, the address field is added to an index register, so

$$EA = A + (XR)$$

In base register addressing, an offset is added to a base register, so

$$EA = (BR) + A$$

In immediate addressing there is no effective address, as the operand is in the instruction. In register addressing, the operand is in the register, so no memory address is needed either. In autoincrement mode, EA is the register's value, and then the register is increased.

Worked example

Take an instruction located at 200, with the address field 500 at location 201. Let the register $R = 400$, the index register $XR = 100$, and $M[500] = 800$. After the fetch, $PC = 202$.

$$\text{Direct: } EA = 500$$

$$\text{Indirect: } EA = M[500] = 800$$

$$\text{Register indirect: } EA = 400$$

$$\text{Relative: } EA = 202 + 500 = 702$$

$$\text{Indexed: } EA = 500 + 100 = 600$$

Therefore the same instruction reads from five different locations, depending on the mode.

Mode EA Memory accesses for the operand
Direct A 1
Indirect M[A] 2
Register indirect (R) 1
Relative PC + A 1
Indexed A + (XR) 1
Immediate none 0
Register none 0

A note on the mode with autoincrement: it is useful when a loop reads one array element after another. The register points to the element, the instruction uses it, and the register moves on to the next element by itself. This saves a separate add instruction each time.

Direct addressing is simple. Indirect addressing gives a bigger address range and allows pointers, but it is slow. Indexed and relative modes help with arrays and branches. The right mode makes the program shorter and flexible.
1810 marksNumericalLook ahead carries addersHideAnswer
Describe the derivation procedure of look ahead carry adder by an example with the help of block diagram.
Deriving the carry equations

A full adder adds the bits $A_i$ and $B_i$ and the carry $C_i$ . Its carry out is:

$C_{i+1} = A_iB_i + (A_i \oplus B_i)C_i$

We give the two parts names. The generate term $G_i = A_iB_i$ means that the stage creates a carry by itself. The propagate term $P_i = A_i \oplus B_i$ means that the stage passes the carry on. The equations become:

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

Now we replace each carry by the equation of the stage before it, one at a time.

$C_1 = G_0 + P_0C_0$

$C_2 = G_1 + P_1C_1 = G_1 + P_1G_0 + P_1P_0C_0$

$C_3 = G_2 + P_2C_2 = 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$

After the substitution, no carry depends on another carry. Each one depends only on $G$ , $P$ and $C_0$ , so all can be built as two-level AND-OR circuits and are ready at the same time.

Block diagram

A3 B3 A2 B2 A1 B1 A0 B0 | | | | | | | | [ P/G ] [ P/G ] [ P/G ] [ P/G ] P = A xor B, G = A.B | | | | | | | | | +----+--+----+--+----+--+--> look-ahead carry unit | | | | (C1, C2, C3, C4 from | | | | all P, G and C0) [XOR] [XOR] [XOR] [XOR] <--- C3, C2, C1, C0 | | | | S3 S2 S1 S0 C4 = carry out

Example. Add $A = 0111$ and $B = 0011$ with $C_0 = 1$ .

Bit i A B G = AB P = A xor B
0 1 1 1 0
1 1 1 1 0
2 1 0 0 1
3 0 0 0 0

The look-ahead equations give:

$C_1 = G_0 + P_0C_0 = 1 + 0 = 1$

$C_2 = G_1 + P_1G_0 + P_1P_0C_0 = 1 + 0 + 0 = 1$

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

$C_4 = G_3 + P_3G_2 + \dots = 0$

The sums are $S_i = P_i \oplus C_i$ , so $S_0 = 0 \oplus 1 = 1$ , $S_1 = 0 \oplus 1 = 1$ , $S_2 = 1 \oplus 1 = 0$ and $S_3 = 0 \oplus 1 = 1$ . The result is $S_3S_2S_1S_0 = 1011$ with carry out $0$ . Therefore $7 + 3 + 1 = 11 = 1011_2$ .
Deriving the carry equations

A full adder adds the bits $A_i$ and $B_i$ and the carry $C_i$. Its carry out is:

$$C_{i+1} = A_iB_i + (A_i \oplus B_i)C_i$$

We give the two parts names. The generate term $G_i = A_iB_i$ means that the stage creates a carry by itself. The propagate term $P_i = A_i \oplus B_i$ means that the stage passes the carry on. The equations become:

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

Now we replace each carry by the equation of the stage before it, one at a time.

$$C_1 = G_0 + P_0C_0$$

$$C_2 = G_1 + P_1C_1 = G_1 + P_1G_0 + P_1P_0C_0$$

$$C_3 = G_2 + P_2C_2 = 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$$

After the substitution, no carry depends on another carry. Each one depends only on $G$, $P$ and $C_0$, so all can be built as two-level AND-OR circuits and are ready at the same time.

Block diagram

A3 B3 A2 B2 A1 B1 A0 B0 | | | | | | | | [ P/G ] [ P/G ] [ P/G ] [ P/G ] P = A xor B, G = A.B | | | | | | | | | +----+--+----+--+----+--+--> look-ahead carry unit | | | | (C1, C2, C3, C4 from | | | | all P, G and C0) [XOR] [XOR] [XOR] [XOR] <--- C3, C2, C1, C0 | | | | S3 S2 S1 S0 C4 = carry out

Example. Add $A = 0111$ and $B = 0011$ with $C_0 = 1$.

Bit i A B G = AB P = A xor B
0 1 1 1 0
1 1 1 1 0
2 1 0 0 1
3 0 0 0 0

The look-ahead equations give:

$$C_1 = G_0 + P_0C_0 = 1 + 0 = 1$$

$$C_2 = G_1 + P_1G_0 + P_1P_0C_0 = 1 + 0 + 0 = 1$$

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

$$C_4 = G_3 + P_3G_2 + \dots = 0$$

The sums are $S_i = P_i \oplus C_i$, so $S_0 = 0 \oplus 1 = 1$, $S_1 = 0 \oplus 1 = 1$, $S_2 = 1 \oplus 1 = 0$ and $S_3 = 0 \oplus 1 = 1$. The result is $S_3S_2S_1S_0 = 1011$ with carry out $0$. Therefore $7 + 3 + 1 = 11 = 1011_2$.
1910 marksNumericalMultiplicationHideAnswer
Show the systematic multiplication process of (-15) x (-16) using Booth's Algorithm.
Both numbers need 5 bits in 2's complement. The numbers are:

$M = -15 = 10001 \qquad -M = +15 = 01111 \qquad Q = -16 = 10000$

$A$ starts at $00000$ and $Q_{-1}$ at 0. In every cycle we look at 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. After that, $A$ , $Q$ and $Q_{-1}$ shift one place right together, and the sign bit of $A$ is copied (arithmetic shift right, ASR). The loop runs 5 times, once for each bit of the multiplier. After the 5 cycles, the 10-bit product is ready, because two 5-bit numbers give a result of at most 10 bits.

Cycle Q0 Q-1 Operation A Q Q-1
Start - initial 00000 10000 0
1 0 0 no change, ASR 00000 01000 0
2 0 0 no change, ASR 00000 00100 0
3 0 0 no change, ASR 00000 00010 0
4 0 0 no change, ASR 00000 00001 0
5 1 0 A = A - M, ASR 00111 10000 1

The product is in $AQ$ joined:

$AQ = 0011110000$

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

$2^7 + 2^6 + 2^5 + 2^4 = 128 + 64 + 32 + 16 = 240$

Therefore $(-15) \times (-16) = +240$ .

This example is short because the multiplier $-16 = 10000$ has four zeros in a row at the right. In the first four cycles the pair is $00$ , so only shifts happen. In cycle 5, the pair is $10$ , since the lowest 1 has reached $Q_0$ while $Q_{-1}$ is 0. So $M$ is subtracted. Subtracting $M = -15$ means adding $+15$ , which gives $A = 01111$ . After the last shift, this becomes $00111$ .

The multiplier is worth a single signed digit $-1$ at bit position 4, that is $-16$ . So the product is $(-15) \times (-16) = +240$ , with the factor $2^4$ coming from the shifts. The sign comes out positive on its own, with no separate sign logic. Every cycle of the table works on 2's complement numbers directly, so negative multiplicands and multipliers need no special treatment, unlike sign-magnitude multiplication. If the multiplier is read as $-16$ , only one subtraction is needed, so Booth's method is very efficient for such numbers. The check is $15 \times 16 = 240$ and the two negative signs give a positive result, so the answer is correct.
Both numbers need 5 bits in 2's complement. The numbers are:

$$M = -15 = 10001 \qquad -M = +15 = 01111 \qquad Q = -16 = 10000$$

$A$ starts at $00000$ and $Q_{-1}$ at 0. In every cycle we look at 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. After that, $A$, $Q$ and $Q_{-1}$ shift one place right together, and the sign bit of $A$ is copied (arithmetic shift right, ASR). The loop runs 5 times, once for each bit of the multiplier. After the 5 cycles, the 10-bit product is ready, because two 5-bit numbers give a result of at most 10 bits.

Cycle Q0 Q-1 Operation A Q Q-1
Start - initial 00000 10000 0
1 0 0 no change, ASR 00000 01000 0
2 0 0 no change, ASR 00000 00100 0
3 0 0 no change, ASR 00000 00010 0
4 0 0 no change, ASR 00000 00001 0
5 1 0 A = A - M, ASR 00111 10000 1

The product is in $AQ$ joined:

$$AQ = 0011110000$$

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

$$2^7 + 2^6 + 2^5 + 2^4 = 128 + 64 + 32 + 16 = 240$$

Therefore $(-15) \times (-16) = +240$.

This example is short because the multiplier $-16 = 10000$ has four zeros in a row at the right. In the first four cycles the pair is $00$, so only shifts happen. In cycle 5, the pair is $10$, since the lowest 1 has reached $Q_0$ while $Q_{-1}$ is 0. So $M$ is subtracted. Subtracting $M = -15$ means adding $+15$, which gives $A = 01111$. After the last shift, this becomes $00111$.

The multiplier is worth a single signed digit $-1$ at bit position 4, that is $-16$. So the product is $(-15) \times (-16) = +240$, with the factor $2^4$ coming from the shifts. The sign comes out positive on its own, with no separate sign logic. Every cycle of the table works on 2's complement numbers directly, so negative multiplicands and multipliers need no special treatment, unlike sign-magnitude multiplication. If the multiplier is read as $-16$, only one subtraction is needed, so Booth's method is very efficient for such numbers. The check is $15 \times 16 = 240$ and the two negative signs give a positive result, so the answer is correct.

Mode	EA	Memory accesses for the operand
Direct	A	1
Indirect	M[A]	2
Register indirect	(R)	1
Relative	PC + A	1
Indexed	A + (XR)	1
Immediate	none	0
Register	none	0

Mode	EA	Memory accesses for the operand
Direct	A	1
Indirect	M[A]	2
Register indirect	(R)	1
Relative	PC + A	1
Indexed	A + (XR)	1
Immediate	none	0
Register	none	0

Bit i	A	B	G = AB	P = A xor B
0	1	1	1	0
1	1	1	1	0
2	1	0	0	1
3	0	0	0	0

Bit i	A	B	G = AB	P = A xor B
0	1	1	1	0
1	1	1	1	0
2	1	0	0	1
3	0	0	0	0

Cycle	Q0 Q-1	Operation	A	Q	Q-1
Start	-	initial	00000	10000	0
1	0 0	no change, ASR	00000	01000	0
2	0 0	no change, ASR	00000	00100	0
3	0 0	no change, ASR	00000	00010	0
4	0 0	no change, ASR	00000	00001	0
5	1 0	A = A - M, ASR	00111	10000	1

Cycle	Q0 Q-1	Operation	A	Q	Q-1
Start	-	initial	00000	10000	0
1	0 0	no change, ASR	00000	01000	0
2	0 0	no change, ASR	00000	00100	0
3	0 0	no change, ASR	00000	00010	0
4	0 0	no change, ASR	00000	00001	0
5	1 0	A = A - M, ASR	00111	10000	1

2010 marksNumericalInstruction types, formats, instruction cyAnswer

Write a program to evaluate the arithmetic statement. P = ((X - Y + Z) * (A ^ B))/( C ^ D * E) By using (i) Two address instructions (ii) One address instructions (iii) Zero address instructions

The statement is

$P = \frac{(X - Y + Z) \times (A ^ B)}{(C ^ D \times E)}$

Here the caret is taken as a binary operator, written POW. So $A ^ B$ is the instruction POW. The same order of evaluation is used in all three programs: first $(X - Y + Z)$ , then $A ^ B$ , then the product of both. Then $C ^ D$ , then multiply by $E$ , and last the division.

(i) Two-address instructions. The first operand is both a source and the destination.

Instruction	Meaning
MOV R1, X	R1 = X
SUB R1, Y	R1 = X - Y
ADD R1, Z	R1 = X - Y + Z
MOV R2, A	R2 = A
POW R2, B	R2 = A ^ B
MUL R1, R2	R1 = (X - Y + Z) * (A ^ B)
MOV R2, C	R2 = C
POW R2, D	R2 = C ^ D
MUL R2, E	R2 = C ^ D * E
DIV R1, R2	R1 = numerator / denominator
MOV P, R1	P = R1

(ii) One-address instructions. Every instruction uses the accumulator AC as the other operand, and T1 and T2 are temporary memory locations.

Instruction	Meaning
LOAD X	AC = X
SUB Y	AC = X - Y
ADD Z	AC = X - Y + Z
STORE T1	T1 = AC
LOAD A	AC = A
POW B	AC = A ^ B
MUL T1	AC = (A ^ B) * T1
STORE T1	T1 = numerator
LOAD C	AC = C
POW D	AC = C ^ D
MUL E	AC = C ^ D * E
STORE T2	T2 = denominator
LOAD T1	AC = numerator
DIV T2	AC = numerator / denominator
STORE P	P = AC

(iii) Zero-address instructions. These use a stack. PUSH puts a value on the stack. An operation takes the top two values, applies the operation, and pushes the result. For SUB and DIV, the lower element is the left operand. The expression in reverse Polish form is $X\,Y - Z + A\,B ^ \times C\,D ^ E \times /$ , and the program is:

Instruction	Stack after it (top on right)
PUSH X	X
PUSH Y	X, Y
SUB	X-Y
PUSH Z	X-Y, Z
ADD	X-Y+Z
PUSH A	X-Y+Z, A
PUSH B	X-Y+Z, A, B
POW	X-Y+Z, A^B
MUL	N (numerator)
PUSH C	N, C
PUSH D	N, C, D
POW	N, C^D
PUSH E	N, C^D, E
MUL	N, C^D*E
DIV	N / (C^D*E)
POP P	stack empty

The three programs use 11, 15 and 16 instructions. As the number of address fields drops, the program becomes longer, but each instruction becomes shorter.

The statement is

$$P = \frac{(X - Y + Z) \times (A ^ B)}{(C ^ D \times E)}$$

Here the caret is taken as a binary operator, written POW. So $A ^ B$ is the instruction POW. The same order of evaluation is used in all three programs: first $(X - Y + Z)$, then $A ^ B$, then the product of both. Then $C ^ D$, then multiply by $E$, and last the division.

(i) Two-address instructions. The first operand is both a source and the destination.

Instruction	Meaning
MOV R1, X	R1 = X
SUB R1, Y	R1 = X - Y
ADD R1, Z	R1 = X - Y + Z
MOV R2, A	R2 = A
POW R2, B	R2 = A ^ B
MUL R1, R2	R1 = (X - Y + Z) * (A ^ B)
MOV R2, C	R2 = C
POW R2, D	R2 = C ^ D
MUL R2, E	R2 = C ^ D * E
DIV R1, R2	R1 = numerator / denominator
MOV P, R1	P = R1

(ii) One-address instructions. Every instruction uses the accumulator AC as the other operand, and T1 and T2 are temporary memory locations.

Instruction	Meaning
LOAD X	AC = X
SUB Y	AC = X - Y
ADD Z	AC = X - Y + Z
STORE T1	T1 = AC
LOAD A	AC = A
POW B	AC = A ^ B
MUL T1	AC = (A ^ B) * T1
STORE T1	T1 = numerator
LOAD C	AC = C
POW D	AC = C ^ D
MUL E	AC = C ^ D * E
STORE T2	T2 = denominator
LOAD T1	AC = numerator
DIV T2	AC = numerator / denominator
STORE P	P = AC

(iii) Zero-address instructions. These use a stack. PUSH puts a value on the stack. An operation takes the top two values, applies the operation, and pushes the result. For SUB and DIV, the lower element is the left operand. The expression in reverse Polish form is $X,Y - Z + A,B ^ \times C,D ^ E \times /$, and the program is:

Instruction	Stack after it (top on right)
PUSH X	X
PUSH Y	X, Y
SUB	X-Y
PUSH Z	X-Y, Z
ADD	X-Y+Z
PUSH A	X-Y+Z, A
PUSH B	X-Y+Z, A, B
POW	X-Y+Z, A^B
MUL	N (numerator)
PUSH C	N, C
PUSH D	N, C, D
POW	N, C^D
PUSH E	N, C^D, E
MUL	N, C^D*E
DIV	N / (C^D*E)
POP P	stack empty

The three programs use 11, 15 and 16 instructions. As the number of address fields drops, the program becomes longer, but each instruction becomes shorter.

2110 marksHardwire and micro programmed controlAnswer

What are the differences between hardwired and micro-programmed control unit?

The control unit makes the signals that tell the other parts of the CPU what to do in each clock cycle. It can be built in two ways.

Point	Hardwired control unit	Microprogrammed control unit
Method	Fixed logic circuit of gates, decoders and counters	Microinstructions stored in a control memory
Speed	Fast	Slower, each step needs a memory read
Design	Complex and hard to change	Simple, regular, easy to change
Modification	Wiring must be changed	Only the microprogram is changed
Cost	High for large instruction sets	Lower for large instruction sets
Error fixing	Hard	Easy
Instruction set	Small, simple	Large, complex
Used in	RISC machines	CISC machines
Control memory	None	ROM or writable store
Examples	MIPS, ARM	IBM 360, VAX

Explanation. In the hardwired unit, the opcode is decoded and combined with the timing signals by logic gates. The gates give the control signals straight away, so it is very fast. But a change in even one instruction means a new circuit. Its design needs state tables and Boolean equations, so a big instruction set makes the design long and error-prone.

In the microprogrammed unit, each machine instruction has a small program of microinstructions in the control memory. The control address register selects the microinstruction, and its bits go out as control signals. The next address is found by the sequencer. To add or fix an instruction, one just writes or changes its microprogram. The price is the memory access in each step, which makes it slower.

Which is better. Neither is best everywhere. When speed matters most and the instruction set is small, as in RISC, the hardwired design is chosen. When the instruction set is large and flexibility matters, as in CISC, microprogrammed control is chosen. Some modern CPUs use a mix, with hardwired control for common simple instructions and microcode for rare complex ones.

Short example. Suppose the CPU must run an ADD. In the hardwired unit, the ADD line from the decoder and the timing pulse $T_4$ meet at an AND gate, and its output starts the add. In the microprogrammed unit, the opcode is mapped to the address of the ADD routine, the first microinstruction is read, and its bits start the same add. Both give the same result. The first does it with gates, and the second does it by reading words from memory.

Effect on the instruction set. Because microcode is cheap to change, early computers added many complex instructions, which led to the CISC style. When designers saw that simple instructions are used most, they moved to hardwired control with RISC.

The control unit makes the signals that tell the other parts of the CPU what to do in each clock cycle. It can be built in two ways.

Point	Hardwired control unit	Microprogrammed control unit
Method	Fixed logic circuit of gates, decoders and counters	Microinstructions stored in a control memory
Speed	Fast	Slower, each step needs a memory read
Design	Complex and hard to change	Simple, regular, easy to change
Modification	Wiring must be changed	Only the microprogram is changed
Cost	High for large instruction sets	Lower for large instruction sets
Error fixing	Hard	Easy
Instruction set	Small, simple	Large, complex
Used in	RISC machines	CISC machines
Control memory	None	ROM or writable store
Examples	MIPS, ARM	IBM 360, VAX

2210 marksBasic concept and hierarchyAnswer

Discuss the Memory Hierarchy in computer system with regard to Speed, Size and Cost.

A computer needs memory that is fast, large and cheap. No single technology gives all three, so memory is arranged as a hierarchy of levels. The fast, small and costly levels are near the CPU. The slow, large and cheap levels are far from the CPU.

The levels from top to bottom are the CPU registers, cache memory, main memory, secondary memory (magnetic disk, SSD) and tertiary memory (tape, optical disk).

Level	Typical access time	Typical size	Cost per bit
Registers	under 1 ns	hundreds of bytes	highest
Cache (SRAM)	1 to 10 ns	KB to few MB	very high
Main memory (DRAM)	50 to 100 ns	GB	moderate
Magnetic disk	5 to 10 ms	hundreds of GB to TB	low
Tape, optical	seconds	very large	lowest

Speed. Moving down the hierarchy, the access time increases. A disk is about a hundred thousand times slower than main memory.

Size. Moving down, the capacity increases by a large factor at each level.

Cost. Moving down, the cost per bit falls. Cache is costly per bit, so only a small amount is used.

Why it works

The hierarchy works because of the principle of locality of reference. Programs use the same data again soon (temporal locality) and use data near the data just used (spatial locality). So a small fast level can hold the data in use, and most accesses are served by it. When data is not found, a whole block is copied from the lower level to the upper level.

If the cache hit ratio is $h$ , the cache time is $t_c$ and the main memory time is $t_m$ , the average access time is

$t_{avg} = h\,t_c + (1-h)\,t_m$

For $h = 0.95$ , $t_c = 10$ ns and $t_m = 100$ ns, this is $0.95 \times 10 + 0.05 \times 100 = 14.5$ ns. This is near the speed of the cache, while the memory is as large as the main memory.

Data movement and the trade-off

The three requirements pull against each other. A fast memory needs costly technology, so it must be small. A large memory must use cheap technology, so it must be slow. The hierarchy solves this by placing a small amount of fast memory above a large amount of slow memory. The size of each level is about 100 to 1000 times that of the level above it. Each level holds a copy of the data of the level below that is likely to be used soon. A well chosen block size and a good replacement rule raise the hit ratio at every level.

Inclusion is another property. All data in the cache is also present in main memory, and all data in main memory is also present on the disk. So the lowest level always holds the complete set of data.

Result

The user gets a memory system with a speed close to the fastest level, a size equal to the largest level, and a cost near that of the cheapest level. Data moves between cache and main memory in blocks, and between main memory and disk in pages.

The levels from top to bottom are the CPU registers, cache memory, main memory, secondary memory (magnetic disk, SSD) and tertiary memory (tape, optical disk).

Level	Typical access time	Typical size	Cost per bit
Registers	under 1 ns	hundreds of bytes	highest
Cache (SRAM)	1 to 10 ns	KB to few MB	very high
Main memory (DRAM)	50 to 100 ns	GB	moderate
Magnetic disk	5 to 10 ms	hundreds of GB to TB	low
Tape, optical	seconds	very large	lowest

Speed. Moving down the hierarchy, the access time increases. A disk is about a hundred thousand times slower than main memory.

Size. Moving down, the capacity increases by a large factor at each level.

Cost. Moving down, the cost per bit falls. Cache is costly per bit, so only a small amount is used.

Why it works

If the cache hit ratio is $h$, the cache time is $t_c$ and the main memory time is $t_m$, the average access time is

$$t_{avg} = h,t_c + (1-h),t_m$$

For $h = 0.95$, $t_c = 10$ ns and $t_m = 100$ ns, this is $0.95 \times 10 + 0.05 \times 100 = 14.5$ ns. This is near the speed of the cache, while the memory is as large as the main memory.

Data movement and the trade-off

Result

2310 marksAuxiliary memoriesHideAnswer
Write a short notes on magnetic disk, magnetic tape and optical disk.
Magnetic disk

A magnetic disk is the main secondary storage of a computer. It has one or more circular platters coated with magnetic material. The platters spin at a fixed speed, such as 7200 rpm. Each surface is divided into concentric circles called tracks, and each track is divided into sectors, which are the smallest units read or written. A read/write head floats over each surface on an arm. The head magnetizes spots to write and senses them to read.

The disk is a direct access device. The head first moves to the right track, and then it waits for the sector. The access time is

$\text{access time} = \text{seek time} + \text{rotational latency} + \text{transfer time}$

The seek time is the time to move the arm to the track. Rotational latency is the wait for the sector to come under the head, on average half a rotation. At 7200 rpm one rotation takes $60/7200 = 8.33$ ms, so the average latency is about $4.17$ ms. Disks are cheap, large and non-volatile, but slow compared to memory.

Magnetic tape

A magnetic tape is a long plastic strip coated with magnetic material, wound on reels or in a cartridge. Data is written in tracks along the length of the tape. It is a sequential access device. To reach a record, the tape must be wound past all the records before it. So the access is slow, but once the right position is reached the data transfer is fast. Tape is very cheap per bit and holds a large amount of data. It is used for backup and archives. Its drawback is that random access is not possible.

Optical disk

An optical disk stores data as tiny pits and flat areas (lands) along a spiral track. A laser beam is focused on the surface. The reflected light is different for a pit and a land, and a sensor reads this as 0 or 1. Common types are as follows.

Type Meaning Typical capacity
CD-ROM read only, factory made about 700 MB
CD-R, DVD-R write once 700 MB, 4.7 GB
CD-RW, DVD-RW can be erased and rewritten 700 MB, 4.7 GB
Blu-ray uses a blue laser 25 GB or more

Optical disks are cheap, easy to carry and last long, which is good for software and movies. They are slower than a magnetic disk.

All three are non-volatile, so data stays when power is off. Magnetic media can also be rewritten many times, but they can be damaged by strong magnetic fields, heat and dust.

Comparison

Point Magnetic disk Magnetic tape Optical disk
Access direct sequential direct
Speed fast slow medium
Use main storage backup distribution, archive

In a computer system, the disk is used as the main file store, the tape as an off-line backup, and the optical disk to carry and share software and media.
Magnetic disk

A magnetic disk is the main secondary storage of a computer. It has one or more circular platters coated with magnetic material. The platters spin at a fixed speed, such as 7200 rpm. Each surface is divided into concentric circles called tracks, and each track is divided into sectors, which are the smallest units read or written. A read/write head floats over each surface on an arm. The head magnetizes spots to write and senses them to read.

The disk is a direct access device. The head first moves to the right track, and then it waits for the sector. The access time is

$$\text{access time} = \text{seek time} + \text{rotational latency} + \text{transfer time}$$

The seek time is the time to move the arm to the track. Rotational latency is the wait for the sector to come under the head, on average half a rotation. At 7200 rpm one rotation takes $60/7200 = 8.33$ ms, so the average latency is about $4.17$ ms. Disks are cheap, large and non-volatile, but slow compared to memory.

Magnetic tape

A magnetic tape is a long plastic strip coated with magnetic material, wound on reels or in a cartridge. Data is written in tracks along the length of the tape. It is a sequential access device. To reach a record, the tape must be wound past all the records before it. So the access is slow, but once the right position is reached the data transfer is fast. Tape is very cheap per bit and holds a large amount of data. It is used for backup and archives. Its drawback is that random access is not possible.

Optical disk

An optical disk stores data as tiny pits and flat areas (lands) along a spiral track. A laser beam is focused on the surface. The reflected light is different for a pit and a land, and a sensor reads this as 0 or 1. Common types are as follows.

Type Meaning Typical capacity
CD-ROM read only, factory made about 700 MB
CD-R, DVD-R write once 700 MB, 4.7 GB
CD-RW, DVD-RW can be erased and rewritten 700 MB, 4.7 GB
Blu-ray uses a blue laser 25 GB or more

Optical disks are cheap, easy to carry and last long, which is good for software and movies. They are slower than a magnetic disk.

All three are non-volatile, so data stays when power is off. Magnetic media can also be rewritten many times, but they can be damaged by strong magnetic fields, heat and dust.

Comparison

Point Magnetic disk Magnetic tape Optical disk
Access direct sequential direct
Speed fast slow medium
Use main storage backup distribution, archive

In a computer system, the disk is used as the main file store, the tape as an off-line backup, and the optical disk to carry and share software and media.
2410 marksModes of Data TransferHideAnswer
With a neat schematic diagram, explain about DMA controller and its mode of data transfer.
A DMA controller is a hardware unit that lets I/O devices transfer data to or from memory directly, without the CPU moving each word. It takes control of the system buses from the CPU for the time of the transfer.

Schematic of the DMA controller

The controller has an address register for the memory address, a word count register for the number of words, and a control register for the direction and mode. It has a data buffer to connect to the data bus. It also has the lines DMA request and DMA acknowledge to the device, and bus request and bus grant to the CPU. A register select input lets the CPU read and write its registers.

Working of the transfer

The CPU first programs the controller with the starting address, the word count and the direction. The device then raises a DMA request. The controller asks the CPU for the bus. The CPU finishes the present bus cycle and grants the bus. The controller puts the address on the address bus, sends the read or write signals, and the word moves between the device and memory. The address is incremented and the count is decremented. When the count is zero, the controller releases the bus and interrupts the CPU.

Modes of data transfer in DMA

Burst mode (block mode). The controller keeps the bus until the whole block is transferred. The transfer is very fast. But the CPU cannot use the bus for the whole time and may be idle for long. This suits high speed devices such as disks.

Cycle stealing mode. The controller takes the bus for one word, then releases it. The CPU gets the bus in between. The transfer is slower, but the CPU is delayed only by one cycle for each word. This suits slow or medium speed devices.

Transparent mode (hidden mode). The controller uses the bus only in those cycles when the CPU is not using it, for example while the CPU is decoding an instruction. The CPU is never slowed. But the transfer can be delayed, and the circuit is more complex.

Direction of transfer

In a DMA read, data goes from memory to the device. In a DMA write, data goes from the device to memory. A third form, memory to memory transfer, is possible in some controllers.

Comparison of the modes

Mode Bus use by DMA Effect on CPU Speed
Burst Whole block together CPU waits for long Highest
Cycle stealing One word at a time Slight delay Medium
Transparent Only in free cycles No delay Lowest

Advantages

The main gains of DMA are higher speed and a free CPU. The cost is the extra hardware and the need to share the bus.
2510 marksPeripheral devices, I/O interface, I/O porHideAnswer
Discuss the design of a typical input or output interface.
An I/O interface is the hardware that joins an I/O device to the CPU buses. The CPU is fast and works with parallel words, while a device may be slow, serial and electromechanical. The interface makes the two work together.

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

Components of a typical interface

Address decoder. The interface has one or more addresses. The decoder looks at the address bus and the chip select signal. It enables the interface only when its own address is seen.

Data register (buffer). It holds the data word on its way between the bus and the device. Because of the buffer, the CPU can send data at its own speed and the device can take it at its own speed.

Control register. The CPU writes commands here. A command may start the device, set the mode, choose the direction or enable the interrupt.

Status register. It has flag bits such as ready, busy, overrun and error. The CPU reads them to know the condition of the device.

Timing and control logic. It makes the read, write and handshake signals in the right order for the device, so that data is exchanged safely.

Interrupt logic. When the device is ready or has an error, the logic raises an interrupt request to the CPU.

Operation

For an output, the CPU puts the address of the interface on the address bus and the data on the data bus, and gives a write signal. The interface latches the data in its data register and sends it to the device with the right handshake signals. It then sets a flag to say that the device has the data.

For an input, the device places the data in the data register and sets the ready flag. The CPU reads the status, sees the flag, and reads the data register. This read also clears the flag.

Other tasks

The interface may convert the data from parallel to serial form and back. It may also change the voltage levels, check parity for errors, and decode commands from the CPU.

A programmable interface chip, like the Intel 8255, lets software choose the mode of each port. In this way, one chip can be used with many devices.

Why the design is needed

Without an interface, the CPU would have to know the speed, voltage and timing of every device. With it, the CPU sees each device as a few simple registers, and the interface hides all the other details.

Type	Meaning	Typical capacity
CD-ROM	read only, factory made	about 700 MB
CD-R, DVD-R	write once	700 MB, 4.7 GB
CD-RW, DVD-RW	can be erased and rewritten	700 MB, 4.7 GB
Blu-ray	uses a blue laser	25 GB or more

Point	Magnetic disk	Magnetic tape	Optical disk
Access	direct	sequential	direct
Speed	fast	slow	medium
Use	main storage	backup	distribution, archive

Type	Meaning	Typical capacity
CD-ROM	read only, factory made	about 700 MB
CD-R, DVD-R	write once	700 MB, 4.7 GB
CD-RW, DVD-RW	can be erased and rewritten	700 MB, 4.7 GB
Blu-ray	uses a blue laser	25 GB or more

Point	Magnetic disk	Magnetic tape	Optical disk
Access	direct	sequential	direct
Speed	fast	slow	medium
Use	main storage	backup	distribution, archive

Mode	Bus use by DMA	Effect on CPU	Speed
Burst	Whole block together	CPU waits for long	Highest
Cycle stealing	One word at a time	Slight delay	Medium
Transparent	Only in free cycles	No delay	Lowest

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2025-26 paper 2024-25 paper 2023-24 paper 2021-22 paper 2020-21 paper 2019-20 paper