All questions of Computer Architecture & Organisation (CAO) for Computer Science Engineering (CSE) Exam

Matching of computer terms:

(A) DMA I/O (1) High speed RAM
(B) Cache (2) Disk
(C) Interrupt I/O (3) Printer
(D) Condition Code Register (4) ALU

Explanation:

DMA I/O: Direct Memory Access (DMA) is a method of transferring data from the computer's memory to a device without involving the CPU. It is used to transfer large amounts of data at high speeds. Therefore, DMA I/O is associated with high-speed RAM.

Cache: Cache is a small amount of memory that is used to store frequently used data. It is used to speed up the access to data that is located in main memory. Therefore, cache is associated with disk.

Interrupt I/O: Interrupt I/O is a method of input/output in which a device sends a signal to the CPU to request its attention. The CPU then interrupts its current task and services the request. Therefore, Interrupt I/O is associated with printers.

Condition Code Register: The Condition Code Register (CCR) is a register that contains information about the status of the last arithmetic or logical operation performed by the CPU. It is used to determine the outcome of the operation. Therefore, the CCR is associated with the Arithmetic Logic Unit (ALU).

Hence, the correct matching of computer terms is:

A-2 B-1 C-3 D-4

Understanding the Pipelined Execution
In a 4-stage pipelined processor, we have the following stages: Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), and Writeback (WB). Each stage takes 1 clock cycle, except for MUL and DIV, which take 3 cycles.
Instruction Breakdown
1. ADD R5, R0, R1
- Takes 1 cycle in IF, ID, EX, and 1 cycle in WB (Total: 4 cycles).
2. MUL R6, R2, R5
- Takes 1 cycle in IF, ID, 3 cycles in EX, and 1 cycle in WB (Total: 6 cycles).
3. SUB R5, R3, R6
- Takes 1 cycle in IF, ID, EX, and 1 cycle in WB (Total: 4 cycles).
4. DIV R6, R5, R4
- Takes 1 cycle in IF, ID, 3 cycles in EX, and 1 cycle in WB (Total: 6 cycles).
5. STORE R6, X
- Takes 1 cycle in IF, ID, EX, and 1 cycle in WB (Total: 4 cycles).
Pipelining and Clock Cycles
- The pipeline can overlap the execution of instructions.
- Each instruction progresses through the stages simultaneously, and the total cycles will be determined by the longest EX stage.
Cycle Calculation
- The critical path is defined by the longest operation, which is MUL (6 cycles) and DIV (6 cycles).
- Thus, the total number of clock cycles required to complete all instructions is determined by the longest EX stages, plus the time taken for the first instruction to complete its WB stage.
Total Clock Cycle Count
- The total clock cycles required:
- 1 (IF for ADD) + 1 (ID for ADD) + 1 (EX for ADD) + 1 (WB for ADD)
- + 1 (IF for MUL, overlaps with ID for ADD)
- + 1 (ID for MUL) + 3 (EX for MUL) + 1 (WB for MUL)
- + 1 (IF for SUB, overlaps with ID for MUL)
- + 1 (ID for SUB) + 1 (EX for SUB) + 1 (WB for SUB)
- + 1 (IF for DIV, overlaps with ID for SUB)
- + 1 (ID for DIV) + 3 (EX for DIV) + 1 (WB for DIV)
- + 1 (IF for STORE, overlaps with ID for DIV)
- + 1 (ID for STORE) + 1 (EX for STORE) + 1 (WB for STORE)
The total comes up to 12 cycles.
Thus, the correct answer is 12 cycles (option b).

Pipelined Processor and Hazards

In a pipelined processor, instructions are divided into multiple stages and executed concurrently. This allows for improved performance by overlapping the execution of multiple instructions. However, this concurrent execution can introduce hazards, which are situations that prevent instructions from executing as intended. There are three types of hazards: data hazards, control hazards, and structural hazards.

I. Bypassing can handle all RAW hazards
Explanation:
- RAW (Read After Write) hazard occurs when a instruction depends on the result of a previous instruction that has not yet completed. This can lead to incorrect results if not handled properly.
- Bypassing, also known as forwarding, is a technique that allows data to be directly transferred from one stage of the pipeline to another without going through registers. It can help to resolve RAW hazards by providing the required data to instructions that need it.
- However, bypassing cannot handle all RAW hazards. There are situations where bypassing is not possible, such as when there are multiple dependent instructions in the pipeline or when the required data is not available in the pipeline.
- Therefore, the statement I is NOT true.

II. Register renaming can eliminate all register carried WAR hazards
Explanation:
- WAR (Write After Read) hazard occurs when a instruction writes to a register that is later read by another instruction before the write operation completes. This can lead to incorrect results if not handled properly.
- Register renaming is a technique that assigns multiple physical registers to the same logical register, allowing instructions to write to and read from different physical registers. This eliminates WAR hazards by ensuring that the read operation gets the correct value from the renamed register.
- However, there are situations where register renaming cannot eliminate WAR hazards, such as when there are dependencies between instructions that cannot be resolved by renaming registers.
- Therefore, the statement II is NOT true.

III. Control hazard penalties can be eliminated by dynamic branch prediction
Explanation:
- Control hazards occur when the control flow of the program is altered due to branches, jumps, or other control transfer instructions. This can lead to pipeline stalls and reduced performance.
- Dynamic branch prediction is a technique that predicts the outcome of branch instructions based on the behavior of previous branches. It allows the pipeline to continue executing instructions speculatively based on the predicted outcome.
- While dynamic branch prediction can significantly reduce the penalties associated with control hazards, it cannot eliminate them entirely. There are cases where the prediction may be incorrect, leading to incorrect execution and the need to flush the pipeline.
- Therefore, the statement III is NOT true.

Conclusion
- In summary, the correct answer is option 'B' because statements II and III are NOT true in a pipelined processor. Bypassing cannot handle all RAW hazards, and register renaming cannot eliminate all register carried WAR hazards. Similarly, while dynamic branch prediction can reduce control hazard penalties, it cannot eliminate them entirely.

Main Memory and Cache Structure
In a computer system, the organization of memory is crucial for performance. The main memory consists of blocks, and in this scenario, it has 2 cm blocks. The cache, which is faster and smaller, contains 2c blocks.
Cache Mapping Scheme
The cache employs a set associative mapping scheme with 2 blocks per set. This means that the cache can hold multiple blocks from the main memory in each set, allowing for more flexibility and faster access.
Understanding Block Mapping
To determine where a block from main memory maps in the cache, we can use the formula for set indexing. The formula typically involves the total number of cache blocks and the number of sets. Here’s how to analyze it:
- Total cache blocks: 2c
- Number of sets: Since there are 2 blocks per set, the number of sets in the cache = (2c) / 2 = c.
Now, to find out which set a block k from main memory maps to:
- Mapping formula: Block k will map to a set in the cache based on the modulo operation with the number of sets.
Calculating the Set Index
Since we have c sets, the formula to find the set for block k is:
- Set index = k mod c
This is because c is the number of sets in the cache, and using modulo c will provide the correct set index for the block.
Conclusion
Thus, the correct answer to where block k of the main memory maps in the cache is option b) (k mod c) of the cache. Understanding this mapping is crucial for optimizing cache performance in computer systems.