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

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.

Given Information:
- Non-pipelined single cycle processor operates at 100 MHz.
- Synchronous pipelined processor has five stages with the following delays:
- Stage 1: 2.5 nsec
- Stage 2: 1.5 nsec
- Stage 3: 2 nsec
- Stage 4: 1.5 nsec
- Stage 5: 2.5 nsec
- Delay of the latches is 0.5 nsec.

Calculating Speedup:
The speedup of the pipelined processor can be calculated using the formula:
Speedup = Non-pipelined processor time / Pipelined processor time

Non-pipelined Processor Time:
The non-pipelined processor operates at 100 MHz, which means each instruction takes 1 / 100 MHz = 10 nsec to complete.

Pipelined Processor Time:
The pipelined processor has five stages with the following delays:
- Stage 1: 2.5 nsec
- Stage 2: 1.5 nsec
- Stage 3: 2 nsec
- Stage 4: 1.5 nsec
- Stage 5: 2.5 nsec

Additionally, there is a delay of 0.5 nsec for each latch.

To calculate the pipelined processor time, we need to consider the longest stage delay, which is 2.5 nsec for Stage 1. Therefore, the pipelined processor time is 2.5 nsec + 0.5 nsec = 3 nsec.

Speedup Calculation:
Speedup = Non-pipelined processor time / Pipelined processor time
= 10 nsec / 3 nsec
≈ 3.33

Therefore, the speedup of the pipeline processor for a large number of instructions is approximately 3.33.

Answer:
The correct answer is option C) 3.33.

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).

Explanation:

To determine the correct matching for the given pairs, let's understand the concepts of indirect addressing, immediate addressing, and auto decrement addressing.

Indirect Addressing:
In indirect addressing, the address of the operand is specified by a register or a memory location. It involves accessing the operand indirectly through an intermediate address. It is commonly used for accessing data structures like arrays and linked lists.

Immediate Addressing:
In immediate addressing, the operand itself is specified in the instruction. It means that the data to be operated on is directly given as a constant value in the instruction itself.

Auto Decrement Addressing:
In auto decrement addressing, the address of the operand is decremented automatically after each access. It is often used in stack operations where the top of the stack pointer is decremented after each pop operation.

Now, let's match the given pairs with their corresponding addressing modes:

X: Indirect addressing
Indirect addressing involves accessing the operand indirectly through an intermediate address. It is similar to accessing data structures like arrays and linked lists. Therefore, X matches with 2: Pointers.

Y: Immediate addressing
Immediate addressing means that the operand itself is specified in the instruction. It is directly given as a constant value in the instruction. Therefore, Y matches with 3: Constants.

Z: Auto decrement addressing
Auto decrement addressing involves automatically decrementing the address of the operand after each access. It is commonly used in stack operations. Therefore, Z matches with 1: Loops.

Correct matching:
X - 2
Y - 3
Z - 1

Therefore, the correct matching for the given pairs is option 'C':

X - 2
Y - 3
Z - 1

The correct answer is option 'D', which means that all of the given options are factors that determine the microinstruction length. Let's explore each of these factors in detail.

1. The maximum number of simultaneous microoperations that must be specified:
Microinstructions are used to control the operations of a microprogrammed control unit (MCU) within a CPU. These microinstructions typically specify a set of microoperations that need to be executed simultaneously during each machine cycle. The number of microoperations that must be specified in each microinstruction determines the length of the microinstruction. If there are a large number of simultaneous microoperations, the microinstruction length will be longer.

2. The way in which the control information is represented or encoded:
Control information in a microprogrammed control unit is represented using encoding schemes such as binary or one-hot encoding. The choice of encoding scheme affects the number of bits required to represent each control signal. The length of the microinstruction is determined by the total number of bits needed to represent all the control signals. Different encoding schemes may require different lengths of microinstructions.

3. The way in which the next microinstruction address is specified:
Microprograms are typically organized as a sequence of microinstructions stored in a control memory. The next microinstruction to be executed is determined by the address specified in the current microinstruction. The method used to specify the next microinstruction address can vary. It could be a direct address, an indirect address, or an address calculated based on some condition. The way in which the next microinstruction address is specified affects the number of bits required to represent the address, thereby impacting the microinstruction length.

In conclusion, the length of a microinstruction is determined by the maximum number of simultaneous microoperations that must be specified, the encoding scheme used for control information, and the method used to specify the next microinstruction address. All of these factors have an impact on the overall length of the microinstruction.