B4 Pipelined Processor
We have improved the NPC's instruction supply capacity by adding an icache. Although the area budget is very limited, adding icache has clearly improved the overall performance of the NPC. The remaining directions for optimization include improving data supply capacity and computational efficiency.
Evaluating the ideal performance gain of dcache
An effective method for improving data supply capacity is to add dcache. In the previous section, we already asked you to estimate the ideal performance gain of dcache using performance counters. After optimizing icache, the speedup brought by dcache under ideal conditions may change. Try reevaluating the ideal performance gain of dcache.
Evaluate the expected performance of dcache using cachesim
Try to improve your cachesim so that it can read mtrace, then evaluate the expected performance of a dcache of a certain size.
You should find that, within the remaining area budget, it is difficult to effectively improve the NPC's data supply capacity through dcache. Therefore, using the remaining area to improve computational efficiency is a more scientific decision. The current NPC is multi-cycle, which means it can execute one instruction only after several cycles. If we can increase the throughput of the NPC's instruction execution, we can improve its computational efficiency. As an instruction-level parallelism technique, pipelining can effectively improve the throughput of the NPC's instruction execution.
Evaluating the ideal gain in computational efficiency
We have not yet introduced the specific implementation of the pipeline, but you can already estimate the ideal gain of pipelining based on performance counters. Assuming that the NPC can execute one instruction per cycle except for memory access instructions, try to estimate the ideal speedup of the NPC under the current conditions of icache misses.
Evaluate performance gains from a system-wide perspective
This estimate may surprise you.
Remember the example of a 5,000x speedup from Amdahl's law? The performance gain brought by a technology by itself, and the performance gain brought by it in the full-system scenario, may be completely different. If you implement out-of-order execution and multiple issue, but the instruction supply and data supply cannot keep up, in a real chip they are just a pile of gate circuits that occupy area and consume power but do little to improve program execution performance.
Pipeline Basics
Factory Pipeline
The idea of pipelining also exists in our lives; the most common example is the pipeline in a factory. For example, a factory producing products needs to go through 5 processes: assembly, labeling, bagging, boxing, and external inspection. If we label these processes with 1~5, and use A, B, C...... to label different products, then the space-time diagram without pipelining is as follows:
----> Time
| Product
| +---+---+---+---+---+
V |A.1|A.2|A.3|A.4|A.5|
+---+---+---+---+---+
+---+---+---+---+---+
|B.1|B.2|B.3|B.4|B.5|
+---+---+---+---+---+
+---+---+---+---+---+
|C.1|C.2|C.3|C.4|C.5|
+---+---+---+---+---+
================================================================
----> Time
| Employee
| +---+ +---+ +---+
V |A.1| |B.1| |C.1|
+---+ +---+ +---+
+---+ +---+ +---+
|A.2| |B.2| |C.2|
+---+ +---+ +---+
+---+ +---+ +---+
|A.3| |B.3| |C.3|
+---+ +---+ +---+
+---+ +---+ +---+
|A.4| |B.4| |C.4|
+---+ +---+ +---+
+---+ +---+ +---+
|A.5| |B.5| |C.5|
+---+ +---+ +---+
The space-time diagram with pipelining is as follows:
----> Time
| Product
| +---+---+---+---+---+
V |A.1|A.2|A.3|A.4|A.5|
+---+---+---+---+---+
+---+---+---+---+---+
|B.1|B.2|B.3|B.4|B.5|
+---+---+---+---+---+
+---+---+---+---+---+
|C.1|C.2|C.3|C.4|C.5|
+---+---+---+---+---+
+---+---+---+---+---+
|D.1|D.2|D.3|D.4|D.5|
+---+---+---+---+---+
+---+---+---+---+---+
|E.1|E.2|E.3|E.4|E.5|
+---+---+---+---+---+
================================================================
----> Time
| Employee
| +---+---+---+---+---+
V |A.1|B.1|C.1|D.1|E.1|
+---+---+---+---+---+
+---+---+---+---+---+
|A.2|B.2|C.2|D.2|E.2|
+---+---+---+---+---+
+---+---+---+---+---+
|A.3|B.3|C.3|D.3|E.3|
+---+---+---+---+---+
+---+---+---+---+---+
|A.4|B.4|C.4|D.4|E.4|
+---+---+---+---+---+
+---+---+---+---+---+
|A.5|B.5|C.5|D.5|E.5|
+---+---+---+---+---+
As can be seen, in the pipelined approach, although the production time of each product has not been reduced, since every employee keeps working, they can continuously handle the same process of different products. As a result, the line completes one product per cycle, thereby increasing the throughput of the production line.
Instruction Pipeline
Analogous to the factory pipeline, a processor can also execute instructions in a pipelined manner. We divide the instruction execution process into several stages, let each component handle one stage, and keep these components working so that they can continuously handle the same stage of different instructions. As a result, overall, one instruction completes execution every cycle, thereby improving the processor's throughput.
When learning about buses, we already asked you to upgrade the NPC to a distributed-control multi-cycle processor. Multi-cycle processors already have the concept of stages, and their working process is very similar to the non-pipelined approach in the factory scenario above. Therefore, it is not difficult to understand how an instruction pipeline works.
We can perform a simple analysis and evaluation of the performance of several processors. Assume the processor's work is divided into 5 stages: instruction fetch, decode, execute, memory access, and write back; their logic delays are all 1ns, and we temporarily ignore the delays of instruction fetch and memory access.
- Single-cycle processor: There are no registers between stages, so the critical path is 5ns and the frequency is 200MHz. One instruction takes 1 cycle to execute, i.e., 5ns; 1 instruction is executed every 1 cycle, i.e.,
IPC = 1. - Multi-cycle processor: There are registers between stages, so the critical path is 1ns and the frequency is 1000MHz. One instruction takes 5 cycles to execute, i.e., 5ns; 1 instruction is executed every 5 cycles, i.e.,
IPC = 0.2. - Pipelined processor: There are registers between stages, so the critical path is 1ns and the frequency is 1000MHz. One instruction takes 5 cycles to execute, i.e., 5ns; 1 instruction is executed every 1 cycle, i.e.,
IPC = 1.
| Processor | Frequency | Instruction Execution Delay | IPC |
|---|---|---|---|
| Single cycle | 200MHz | 5ns | 1 |
| Multi-cycle | 1000MHz | 5ns | 0.2 |
| Pipeline | 1000MHz | 5ns | 1 |
As can be seen, although the instruction execution delay is still 5ns, the pipeline has the advantages of high frequency and high IPC. These advantages essentially come from instruction-level parallelism: every cycle, the pipelined processor is processing 5 different instructions.
Of course, the above data is only obtained from analysis under ideal conditions. If we consider memory access in the SoC, the IPC would be far lower; moreover, a pipelined processor cannot always execute 5 instructions every cycle, which we will analyze further below.
Longer pipelines
The above example only divides the pipeline into 5 stages. In fact, we can divide the pipeline into more stages, making the logic of each stage simpler, thereby improving the overall frequency of the processor. Such a pipeline is called a "superpipeline." For example, if the pipeline can be divided into 30 stages, according to the above estimate, the frequency could theoretically reach 6GHz.
However, current mainstream high-performance processors generally only divide the pipeline into about 15 stages. What factors do you think may make it inappropriate to divide the pipeline into too many stages?
Simple Implementation of the Pipeline
It is not difficult to implement a pipeline based on a handshake-based multi-cycle processor. For each stage's input in and output out, we only need to correctly process the following signals (bits refers to the payload that needs to be transferred between stages):
out.bits, generated by the current stageout.valid, generated by the current stage, usually also related toin.validin.ready, generated by the current stage, set to invalid when busy, and set to valid after the current instruction is processedout.ready, identical to the next stage'sin.readyin.bits, updated to the previous stage'sout.bitswhen both the current stage'sin.readyand the previous stage'sout.validare validin.valid, left as an exercise for you
Based on the above, we can package the processing of the last three signals into a function, and then use it to connect the stages:
def pipelineConnect[T <: Data, T2 <: Data](prevOut: DecoupledIO[T],
thisIn: DecoupledIO[T], thisOut: DecoupledIO[T2]) = {
prevOut.ready := thisIn.ready
thisIn.bits := RegEnable(prevOut.bits, prevOut.valid && thisIn.ready)
thisIn.valid := ???
}
pipelineConnect(ifu.io.out, idu.io.in, idu.io.out)
pipelineConnect(idu.io.out, exu.io.in, exu.io.out)
pipelineConnect(exu.io.out, lsu.io.in, lsu.io.out)
// ...
In particular, the IFU can fetch the next instruction immediately without waiting for the current instruction to finish executing. The RegEnable above plays the role of the "pipeline stage register" in traditional textbooks, but from the bus perspective we can also understand it as a buffer where the downstream module receives messages: after the upstream and downstream modules handshake successfully, the upstream module considers that the downstream module has successfully received the message, so it no longer stores the message; therefore, the downstream module needs to record the received message in the buffer to prevent message loss. As for the first three signals, since their specific logic is related to the behavior of the current stage, they need to be implemented in the module corresponding to the current stage.
In particular, there are situations in a pipelined processor where the current instruction cannot continue to execute, which are called "hazards." Hazards are mainly divided into 3 categories: structural hazards, data hazards, and control hazards. If hazards are ignored and execution is forced, the CPU state machine's transition result will be inconsistent with the ISA state machine, manifesting as instruction execution results that do not match their semantics. Therefore, in pipeline design, we need to detect hazards, and either eliminate them through hardware design, or wait in time until the hazards no longer occur. For the latter, this can be achieved by adding wait conditions to in.ready and out.valid.
Structural Hazard
A structural hazard refers to the case where different stages in the pipeline need to access the same component simultaneously, but the component cannot support simultaneous access by multiple stages. For example, in the instruction sequence shown in the figure below, at time T4, I1 is reading data in the LSU and I4 is fetching an instruction in the IFU; both need to read memory. At time T5, I1 is writing registers in the WBU and I4 is reading registers in the IDU; both need to access the register file.
T1 T2 T3 T4 T5 T6 T7 T8
+----+----+----+----+----+
I1: lw | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I2: add | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I3: sub | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I4: xor | IF | ID | EX | LS | WB |
+----+----+----+----+----+
Some structural hazards can be completely avoided through hardware design, so that they do not occur during CPU execution: we only need to design the hardware so that these components support simultaneous access by multiple stages. Specifically:
- For the register file, we only need to implement its read port and write port independently, letting the IDU access the register file through the read port and the WBU access the register file through the write port
- For memory, there are several solutions
- Separate the read port and write port like the register file, implementing a true dual-port memory
- Divide memory into instruction memory and data memory, which work independently
- Introduce a cache; if the cache hits, there is no need to access memory
Differences between textbooks and real systems
Most solutions in textbooks are based on some simplified assumptions, which are likely no longer valid in real processors, so they are not necessarily suitable for use in the OSOC ("One Student One Chip") scenario.
For example, SDRAM memory chips cannot separate the read port from the write port. Both the READ command and the WRITE command are passed to the SDRAM chips through the SDRAM memory bus. Dividing memory into instruction memory and data memory would put instructions and data in different address spaces, which violates the ISA specification's memory model of a unified address space for instructions and data. On the one hand, modern compilers cannot compile programs that adapt to the above scheme; on the other hand, even if programs are developed in assembly language, loading-program functions such as a bootloader cannot run correctly either.
In fact, OSOC places higher demands on everyone: learn to evaluate a scheme from the system-wide perspective. The simplified assumptions in textbooks can help everyone focus on learning the current knowledge point, but what you will face in the future are real projects; only by learning to relate the various factors in the system can you make reasonable and effective decisions in your future work.
There are also some structural hazards that cannot be completely avoided, for example:
- When the cache misses, the IFU and LSU still need to access memory at the same time
- The SDRAM controller's queue is full and cannot accept further requests
- The divider's calculation takes dozens of cycles, and another calculation cannot be started before the current one finishes
To deal with the above situations, a simple way is to wait: if the IFU and LSU access memory at the same time, let one wait for the other; wait until the SDRAM controller's queue has a free slot; wait until the divider finishes its current calculation. The good news is that the bus inherently has a waiting capability, so as long as the slave device, the downstream module, or the arbiter sets ready to invalid, the detection and handling of structural hazards can be reduced to the bus state machine, without needing to implement dedicated structural hazard detection and handling logic.
Who waits for whom?
While waiting, should the IFU wait for the LSU, or should the LSU wait for the IFU? Or are both options acceptable? Why?
Data Hazard
A data hazard refers to the case where instructions in different stages depend on the same register data, and at least one instruction writes to that register. For example, in the instruction sequence shown in the figure below, I1 writes to register a0, but the write is not completed until the end of time T5. Before that, I2 reads the old value of a0 at time T3, I3 reads the old value of a0 at time T4, I4 reads the old value of a0 at time T5, and I5 can only read the new value of a0 at time T6.
T1 T2 T3 T4 T5 T6 T7 T8 T9
+----+----+----+----+----+
I1: add a0,t0,s0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I2: sub a1,a0,t0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I3: and a2,a0,s0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I4: xor a3,a0,t1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I5: sll a4,a0,1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
The above data hazard is called a read-after-write (RAW) hazard. The characteristic of a RAW hazard is that one instruction needs to write a register, while another younger instruction needs to read that register. Obviously, if this data hazard is not handled, instructions I2, I3, and I4 will compute wrong results because they read the old value of a0, violating the semantics of instruction execution.
There are several ways to resolve the RAW hazard. From the software perspective, instructions are generated by the compiler, so one way is to let the compiler detect RAW hazards and insert empty instructions (nops) to wait for the instruction writing to the register to complete the write, as shown in the figure below:
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
+----+----+----+----+----+
I1: add a0,t0,s0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
nop | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
nop | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
nop | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I2: sub a1,a0,t0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I3: and a2,a0,s0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I4: xor a3,a0,t1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I5: sll a4,a0,1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
The essence of inserting empty instructions is still waiting, but in fact the compiler can do better: instead of waiting, it is better to execute some meaningful instructions. This can be achieved by letting the compiler perform instruction scheduling: the compiler can try to find instructions with no data dependencies and adjust their order without affecting program behavior. An example is as follows, where I6, I7, and I8 all have no data dependency with I1, so they can be scheduled to execute after I1:
I1: add a0,t0,s0 I1: add a0,t0,s0
I2: sub a1,a0,t0 I6: add t5,t4,t3
I3: and a2,a0,s0 I7: add s5,s4,s3
I4: xor a3,a0,t1 ---> I8: sub s6,t4,t2
I5: sll a4,a0,1 I2: sub a1,a0,t0
I6: add t5,t4,t3 I3: and a2,a0,s0
I7: add s5,s4,s3 I4: xor a3,a0,t1
I8: sub s6,t4,t2 I5: sll a4,a0,1
Compilers and out-of-order execution processors
If we delegate the compiler's instruction scheduling work to hardware, we obtain an out-of-order execution processor. Of course, to perform instruction scheduling in hardware, we need to add quite a few hardware modules. But fundamentally, both techniques aim to improve the efficiency of the processor's instruction execution.
However, for instruction scheduling, the compiler can only do its best and cannot always find suitable instructions. For example, a division instruction needs dozens of cycles to execute, and it is usually hard for the compiler to find that many suitable instructions. In such cases, if the compiler is to handle RAW hazards, it can still only insert empty instructions.
An even worse message is that some RAWs cannot be resolved by the compiler alone. Consider that the depended-on instruction is a load instruction; this kind of RAW hazard is called a load-use hazard:
T1 T2 T3 .... T? T? T? T? T? T? T?
+----+----+----+--------------+----+
I1: lw a0,t0,s0 | IF | ID | EX | LS | WB |
+----+----+----+--------------+----+
+----+----+----+----+----+
nop X ? | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I2: sub a1,a0,t0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
In fact, in a real SoC, software can almost never predict the latency of a memory access instruction when it is executed in the future:
- If the cache hits, the data may return after 3 cycles
- If the cache misses, SDRAM needs to be accessed, and the data may return after 30 cycles
- If it happens to coincide with SDRAM charging/refresh, the data may return after 30+? cycles
- If the CPU frequency is increased from 500MHz to 600MHz, the number of cycles required for the data to return increases
For this reason, almost all modern processors adopt the approach of detecting and handling RAW hazards in hardware. Since register write operations happen in the WBU, the register number to be written is also propagated along the pipeline to the WBU; that is, we can find, from each stage, which register the corresponding instruction will write. If the register that the instruction in the IDU wants to read is the same as the register that a later pipeline stage will write, a RAW hazard occurs:
def conflict(rs: UInt, rd: UInt) = (rs === rd)
def conflictWithStage[T <: Stage](rs1: UInt, rs2: UInt, stage: T) = {
conflict(rs1, stage.rd) || conflict(rs2, stage.rd)
}
val isRAW = conflictWithStage(IDU.rs1, IDU.rs2, EXU) ||
conflictWithStage(IDU.rs1, IDU.rs2, LSU) ||
conflictWithStage(IDU.rs1, IDU.rs2, WBU)
The pseudocode above is only a rough idea; in practice you also need to consider more issues: not all instructions need to write registers, not all stages are executing instructions, not all instructions need to read rs2 (e.g., U-type instructions), the value of the zero register is always 0, etc. How to write correct RAW detection code is left for you to think about.
After detecting a RAW hazard, the simplest way to handle it is still to wait: just set in.ready and out.valid to invalid. As can be seen, this hardware-based scheme for detecting and handling RAW hazards does not need to know in advance when the instruction execution ends, because the various waits during instruction execution are propagated into the pipeline through the bus handshake signals. Therefore, it is more applicable than the software scheme above.
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12
+----+----+----+----+----+
I1: add a0,t0,s0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+-------------------+----+----+----+
I2: sub a1,a0,t0 | IF | ID | EX | LS | WB |
+----+-------------------+----+----+----+
+-------------------+----+----+----+----+
I3: and a2,a0,s0 | IF | ID | EX | LS | WB |
+-------------------+----+----+----+----+
+----+----+----+----+----+
I4 xor a3,a0,t1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I5: sll a4,a0,1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
Control Hazard
A control hazard refers to the case where a jump instruction changes the order of instruction execution, causing the IFU to possibly fetch instructions that should not be executed. For example, in the instruction sequence shown in the figure below, which instruction the IFU should fetch at T4 can only be known after I3 computes the jump result at time T5.
T1 T2 T3 T4 T5 T6 T7 T8
+----+----+----+----+----+
I1: 100 add | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I2: 104 lw | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I3: 108 beq 200 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I4: ??? ??? | IF | ID | EX | LS | WB |
+----+----+----+----+----+
In addition to the branch instruction above, jal and jalr also cause similar problems. Suppose I3 in the figure above is a jump instruction. We expect to fetch the instruction at the jump target at time T4, and at time T4 the IDU happens to be decoding I3; in principle it should be able to catch up, but modern processors generally consider that it still cannot catch up, and therefore treat it as a control hazard.
Why do modern processors handle it this way?
In fact, some textbooks do handle control hazards in the way described above. What factors do you think make the above textbook scheme unadoptable in real processor designs?
Even exceptions thrown by the CPU can cause control hazards. When an exception is thrown, instruction fetch must immediately restart from the memory location pointed to by mtvec, but generally speaking, the processor cannot know, at the time of fetching, whether the execution of this instruction will throw an exception.
All the above problems arise because, at the instruction fetch stage, it is impossible to determine which instruction truly needs to be fetched next. If we choose to wait, we must wait until the previous instruction almost completes execution before knowing the true address of the next instruction. For example, a memory access instruction must wait until the memory access finishes and, through the bus's resp signal, confirm that no exception was thrown during the memory access. Obviously, this scheme would prevent the instruction pipeline from flowing, greatly reducing the processor's instruction execution throughput. If we choose not to wait, we may fetch some instructions that should not be executed; without further handling, the processor's state transition would be inconsistent with the ISA state machine, resulting in incorrect execution results.
To handle control hazards, modern processors usually adopt "speculative execution" technology. Speculative execution is essentially a prediction technique. Its basic idea is to try to speculate a choice while waiting; if the guess is right, it is equivalent to having made the correct choice in advance, thus saving the waiting overhead. Speculative execution specifically consists of three parts:
- Selection strategy - before obtaining the correct result, speculate a choice through a certain strategy
- Checking mechanism - when the correct result is obtained, check whether the previously speculated choice matches the correct result
- Error recovery - if the check finds a mismatch, roll back to the state at the time of the selection strategy, and make the correct choice based on the obtained correct result
For control hazards, the simplest speculative execution strategy is "always speculate that the next static instruction will be executed next." Consider the implementation of this strategy from the above three parts:
- Selection strategy - very simple: just let the IFU keep fetching the instruction at
PC + 4. - Checking mechanism - according to the semantics of instructions, only when executing branch and jump instructions, or when throwing exceptions, may the CPU change the execution flow; in all other cases, execution is sequential. Therefore, in the other cases, the speculated choice above is always correct and requires no additional check. Only when executing branch and jump instructions, or throwing exceptions, do we need to check whether the jump result matches the speculated choice, i.e., check whether the jump result is
PC + 4. - Error recovery - if the jump result above is found not to be
PC + 4, it means the previous speculation was wrong; the instructions fetched based on this speculation should not be executed and should be eliminated from the pipeline. This action is called "flushing"; at the same time, the IFU needs to fetch from the correct jump result.
The performance improvement brought by speculative execution is related to the accuracy of the speculation. If the accuracy is high, the IFU can fetch the correct instruction in advance with high probability, saving waiting overhead; if the accuracy is low, the IFU often fetches instructions that should not be executed, and these instructions are later flushed. During this period, the pipeline behaves as if no valid instruction were executed, reducing the throughput of instruction execution. Specifically:
- Since exceptions are low-probability events during processor execution, the vast majority of instructions do not throw exceptions when executed, so for exceptions, the accuracy of the above strategy is close to 100%
- The execution result of a branch instruction is either "taken" or "not taken"; the above strategy is equivalent to always predicting "not taken," so probabilistically, for branch instructions, the accuracy of the above strategy is close to 50%
- A jump instruction behaves as an unconditional jump to the target address, but there can be many possible target addresses; the probability of jumping exactly to
PC + 4is very low, so for jump instructions, the accuracy of the above strategy is close to 0%
According to the above analysis, speculative execution can correctly handle control hazards on the one hand; on the other hand, compared with passive waiting, speculative execution can also bring some performance improvement. However, for branch instructions and jump instructions, the above speculative execution scheme still has much room for improvement, which we will continue to discuss below.
There are also some details to note about the implementation of speculative execution:
- From the requirement's perspective, flushing is to restore the processor's state to the moment before the control hazard occurred; therefore, we can derive from the state-machine perspective how to handle the relevant implementation details. The state-machine perspective tells us that the processor's state is determined by sequential logic circuits, and the processor's state updates are controlled by control signals. Therefore, to achieve the effect of flushing, we only need to consider setting the relevant control signals to invalid. For example, by setting
validto invalid, the instructions being executed by most components can be flushed directly. - However, if components still contain some state that affects control signals, you need extra consideration, such as the state machine in the icache. In particular, issued AXI requests cannot be withdrawn, so you need to wait for the requests to complete.
- Speculative execution means that the currently executed operation may not be what is truly needed in the future; if the speculation is wrong, the related operations should be cancelled. But some operations are hard to cancel, including updating the register file, updating CSRs, writing memory, accessing peripherals, etc. Once the state of these modules changes, it is hard to restore the old state. Therefore, the state of these modules can only be updated after the speculation is confirmed to be correct.
Implement a simple pipelined processor
Handle the various hazards in the simplest way, so as to implement the most basic pipeline structure. After implementation, try running microbench to check whether your implementation is correct.
Hint:
- To make DiffTest work correctly, you may need to modify the signals passed to the simulation environment
- For now, you can ignore the implementation related to exception handling; we will implement it next
Nested speculative execution
Think about it: if you encounter consecutive branch instructions or jump instructions, can your design still work correctly?
For the implementation of exceptions in a pipelined processor, we also need to consider the following details:
- When an exception is thrown,
mepcneeds to be set to the PC value of the instruction where the exception occurred; this feature is called a "precise exception." If this property is not satisfied, then when returning from exception handling viamret, we cannot precisely return to the instruction where the exception occurred, making the state before and after the exception inconsistent. This may prevent system software from using the exception mechanism to implement certain key mechanisms of modern operating systems, such as process switching and demand paging. But in a pipelined processor, the IFU's PC keeps changing; by the time an instruction throws an exception during execution, the IFU's PC no longer matches this instruction. To obtain the PC that matches this instruction, we need to pass the corresponding PC downstream together with the instruction when the IFU fetches it. - An instruction may throw an exception during speculative execution, but if the speculation is wrong, the instruction should not actually be executed, and the exception thrown should not be handled. Therefore, the operations that need to update processor state during exception handling all need to wait until the speculation is confirmed to be correct before actually taking effect, including writing
mepcandmcause, jumping to the location indicated bymtvec, etc. - The update of
mcausedepends on the type of exception; in RISC-V processors, different exception numbers are generated by different components. The generated exception number also needs to be passed downstream along the pipeline, andmcausecan only be written after the speculation is confirmed to be correct.
| Exception Number | Exception Description | Component Where Exception First Occurred |
|---|---|---|
| 0 | Instruction address misaligned | IFU |
| 1 | Instruction access fault | IFU |
| 2 | Illegal Instruction | IDU |
| 3 | Breakpoint | IDU |
| 4 | Load address misaligned | LSU |
| 5 | Load access fault | LSU |
| 6 | Store/AMO address misaligned | LSU |
| 7 | Store/AMO access fault | LSU |
| 8 | Environment call from U-mode | IDU |
| 9 | Environment call from S-mode | IDU |
| 11 | Environment call from M-mode | IDU |
| 12 | Instruction page fault | IFU |
| 13 | Load page fault | LSU |
| 15 | Store/AMO page fault | LSU |
Implement a pipeline that supports exception handling
According to the above content, implement a pipeline that supports exception handling. After implementation, run some exception-handling-related tests to check whether your implementation is correct.
Multiple exceptions occur
In a pipelined processor, different stages execute different instructions, which means different stages may simultaneously produce different exceptions. For example, while the IFU finds an instruction address misalignment, the IDU finds an illegal instruction, and the LSU finds a load memory access error. How should this be handled?
Although we do not currently require you to implement all exceptions, you can still think about whether your design can correctly handle this situation.
Intel's superpipeline architecture
In the period before 2005, Intel once used superpipeline technology to pursue extreme clock speeds. In February 2004, Intel released a processor with the architecture codename Prescott, whose pipeline depth reached an unprecedented 31 stages; even at the then-90nm process node, its clock speed reached 3.8GHz. However, actual measurements found that, compared with the previous-generation 20-stage pipeline Northwood, this processor's performance did not improve much; instead, it became the hottest-running and most power-consuming single-core processor in x86 history. In fact, were it not for thermal and power issues, this processor's clock speed could have been even higher than 3.8GHz: a year before its release, Intel claimed this processor could reach up to 5GHz.
At the microarchitecture level, the execution efficiency of the 31-stage pipeline was also not satisfactory. On the one hand, the instructions in the pipeline were full of data hazards; many instructions could only wait in the pipeline due to RAW hazards. On the other hand, the cost of flushing the pipeline because of wrong speculation on branch instructions was very high. Suppose the processor computes whether a branch instruction is taken at stage 26; in the case of wrong speculation, all instructions fetched in the previous 25 cycles need to be flushed. In particular, Prescott is a multi-issue processor capable of 4 simple ALU operations per cycle; estimating it as 4-issue, then in the case of wrong speculation, 25 * 4 = 100 instructions need to be flushed! Although Prescott adopted some advanced technologies to improve speculation accuracy, according to actual measurement results, the performance of quite a few programs still declined because of the over-long pipeline.
Later, Intel abandoned this aggressive superpipeline technology route, and the pipeline depth of subsequent architectures is generally around 15 stages, at most not exceeding 20.
Testing and Verification of Pipelined Processors
The processing object of the pipeline is instructions, which means that different instruction sequences will have different effects on the pipeline's behavior. Therefore, the verification process of the pipeline should use instruction sequences as test inputs and cover as many different situations as possible. According to the behavior of instructions in the pipeline, they can be roughly divided into the following 10 types:
- Instructions whose computation can be completed by the ALU in one cycle, such as addition, subtraction, logic, and shift
- Control flow transfer instructions, divided into 3 types: conditional branches,
jal,jalr - Memory access instructions, divided into 2 types: load, store
- CSR instructions
ecall,mretfence.i
Just considering the combinations of the above 10 types of instructions in a traditional 5-stage pipeline already gives possibilities. In fact, we also need to consider the various hazards mentioned above: memory access may need to wait, there are data dependencies between instructions, control flow transfer instructions cause pipeline flushes...... In short, there are too many instruction sequences formed by combinations of different situations. Even developing an instruction generator makes it hard to guarantee coverage of all the above situations, and it is even harder to manually design that many test cases.
The correctness of the processor cannot be proven by traditional instruction test sets
If you are familiar with instruction test sets like riscv-tests, you need to understand that passing riscv-tests does not mean the pipelined NPC is correct. In fact, the number of test cases in riscv-tests is far below the roughly computed 100000 above, which already shows that there must be some instruction sequences that riscv-tests cannot cover. More fundamentally, riscv-tests tests the behavior of single instructions, while fully testing a pipelined processor requires traversing various instruction sequences. Therefore, if your pipelined NPC only passes traditional instruction test sets like riscv-tests, you should not be 100% confident in your NPC implementation.
Since manually designing test cases is difficult, let's find a way to leave it to tools! Recall the formal verification tool we used when verifying the cache: it can automatically help us find test cases that violate assert; if none are found, it proves the correctness of the design. If formal verification can be applied to the pipelined NPC, the tool can help us automatically find erroneous instruction sequences!
To use formal verification, we also need a REF and to write appropriate verification conditions (i.e., assert). For the REF, we need another implementation that can correctly execute instruction sequences. Since the formal verification tool we use can only verify at the RTL level, it is currently impossible to integrate instruction set emulators such as NEMU and Spike. However, we can consider the single-cycle NPC developed earlier: as another microarchitecture implementation of the RISC-V ISA, it can necessarily execute instruction sequences correctly.
As for the verification conditions, one idea is, like DiffTest, after the DUT and REF execute the same instructions, to check whether their GPR states are consistent. In C code, checking whether all GPRs are consistent is just a single memcmp() call, which is not expensive; but in formal verification, checking whether all GPRs are consistent is used as a constraint for "equation solving," which brings considerable overhead to the BMC solving process. For this reason, it is necessary to find a simpler comparison method.
Recalling the state machine model, the new state depends on the current state and the state transition. Therefore, besides directly comparing the new states, we can also compare from another angle: if the current states are consistent and the state transitions are also consistent, then the new states should also be consistent. Generally speaking, describing a state transition is much smaller than describing the state itself (i.e., the state space), so comparing whether the state transitions are consistent is usually a simpler comparison method. Taking the GPR state above as an example, although the GPR state space has bits, one RISC-V instruction writes at most one GPR. We only need to record which GPR this instruction updates to which value, and compare whether the DUT and REF records are consistent; there is no need to directly compare whether the 512-bit GPR state spaces are consistent, greatly simplifying the comparison overhead.
According to the above analysis, it is easy to write pseudocode for the verification top-level module. Here we use Chisel as pseudocode; if you develop in Verilog, you can still draw on the related ideas to write the verification top-level module.
class PipelineTest extends Module {
val io = IO(new Bundle {
val inst = Input(UInt(32.W))
val rdata = Input(UInt(XLEN.W))
})
val dut = Module(new PipelineNPC)
val ref = Module(new SingleCycleNPC)
dut.io.imem.inst := io.inst
dut.io.imem.valid := ...
dut.io.dmem.rdata := io.rdata
dut.io.dmem.valid := ...
// ...
ref.io.imem.inst := dut.io.wb.inst
// ...
when (dut.io.wb.valid) {
assert(dut.io.wb.rd === ref.io.wb.rd)
assert(dut.io.wb.res === ref.io.wb.res)
}
}
The pseudocode above only gives a rough framework; there are still many details that you need to pay attention to and fill in:
- To reduce the BMC solution space, the DUT only contains the pipeline itself, without the cache and various peripheral modules; but the memory access latency caused by cache misses can be implemented through handshake signals
- Instructions are one of the inputs of the verification top-level module, which means the BMC will traverse various instructions; under the action of the bound, the BMC will traverse various combinations of instructions in different cycles, i.e., it realizes the traversal of all instruction sequences of a given length.
- The generated instruction sequence will be fed into the DUT's IFU in order, but since an instruction needs to wait several cycles to complete execution in the pipelined NPC, while it takes only 1 cycle in the single-cycle NPC, synchronization between the DUT and REF is needed so that an instruction is fed into the REF only after the DUT finishes executing it. Therefore, the currently completed instruction needs to be obtained from the DUT's WBU.
- Besides comparing the written GPR number
rdand its valueres, the PC also needs to be compared, to check whether the control flow transfer is correct. However, we can choose to compare the new PC value, which can catch PC inconsistency errors one cycle earlier. - Some instructions do not write GPRs; for these instructions, there is no need to compare
rdandres. - For load instructions, their memory access results are also one of the pipeline's inputs, so they need to be reflected at the ports of the verification top-level module. To ensure the DUT and REF are in the same state after executing the same load instruction, we also need to ensure they read the same data.
- We do not specially compare the execution results of store instructions, for two main reasons:
- The write data and write address both come from GPRs; if they are wrong, then there must be an instruction older than the store instruction that wrote a wrong value to a GPR, which can be detected by the above mechanism.
- If the write data and write address are correct but the AXI write channel signals are wrong, this problem belongs to the AXI bus implementation domain, not the pipeline verification domain. In principle, checking AXI signals can also be added to the pipeline verification framework, but this would increase the BMC constraints and thus the solving overhead.
- The handshake signals of the IFU and LSU need to be handled correctly.
- We also do not specially compare CSR writes, because if the write to a CSR is implemented incorrectly, an extra instruction can be used to read that CSR's value into a GPR, exposing the wrong value, thereby reducing the comparison of CSR writes to the comparison of GPR writes.
- It is also necessary to make the GPRs and CSRs have the same initial state in both the DUT and REF, so the GPRs and CSRs need to be initialized. Note that this is only a requirement of formal verification; during simulation and tape-out, not all GPRs and CSRs need to be initialized.
- Since the instruction sequence is generated by the BMC, without any restrictions, the generated instruction sequence may contain illegal instructions. If the NPC does not support handling illegal instruction exceptions, the NPC's behavior when executing illegal instructions is undefined, which is unfavorable for comparing the execution results of instruction sequences. To solve this problem, one idea is to allow the BMC to generate only legal instructions. This can be done through the
assumestatement provided by both Chisel and SystemVerilog, which is used to express the preconditions of verification. For example, ifisIllegalindicates "the instruction decoding result is an illegal instruction," thenassume(!isIllegal)indicates taking "the instruction decoding result is not an illegal instruction" as a precondition of verification; at this point, the BMC will solve under this precondition, thus excluding illegal instructions from the instruction sequence. - The CSR register addresses in CSR instructions also need to be considered; similarly, the
assumestatement can be used to restrict the CSR register addresses in CSR instructions to the range of implemented CSRs. - Another thing to consider is unaligned memory access; without restrictions, the addresses computed in the generated memory access instructions may be unaligned. This problem can also be solved with the
assumestatement.
Switch to a more efficient model checking tool
On 2024/08/20 02:30:00, we modified the way the formal verification tool is invoked, replacing the call to the Z3 solver with a call to the BtorMC model checker, to improve the efficiency of formal verification. If you develop with Chisel, please refer to the content of the "Simple Example of Formal Verification" subsection in the cache section.
Test the pipeline implementation through formal verification
Although this is not mandatory, we strongly recommend that you test your pipeline through formal verification. However, you need to think carefully about how to write verification conditions such as assert and assume; if they are written improperly, they may cause false positives or false negatives: false positives can be discovered during debugging and the corresponding verification conditions fixed, but false negatives are hard to discover. Therefore, this task essentially also tests whether your understanding of the pipeline details is deep enough.
In addition, regarding the bound of BMC, you can choose an appropriate parameter so that the formal verification tool can traverse enough instruction sequences and cover various hazard combinations. Generally, the bound may need to reach more than 10, which requires the solving process to take several hours or even dozens of hours; but from the perspective of tool convenience, this is still very worthwhile, because even spending several days manually writing test cases may not produce test cases that cover some extreme situations. However, to quickly find some counterexamples, you can start testing from a small bound and then gradually test larger bounds.
Use formal verification to test more complex processors
A research team at the Institute of Software, Chinese Academy of Sciences, has developed a formal verification-based RISC-V processor testing framework; through it, they even found some very hidden bugs in the NutShell processor that can boot Linux. For details, refer to their nutshell-fv project. This case also reflects the advantages of formal verification technology. However, since the current NPC functionality has undergone many simplifications, to integrate into this testing framework, you may need to make some adjustments to both your code and the testing framework's code. If you are interested, you can read the README in the project to learn how to use it, and understand the details of the testing framework by reading the relevant code.
Making the Pipeline Flow
After implementing the simple pipelined processor, let's discuss how to improve the pipeline's efficiency.
Evaluate the performance of the simple pipeline
Before optimizing, you need to evaluate the performance of the simple pipeline above. Compared with the multi-cycle processor before implementing the pipeline, how much performance improvement did you find after implementing the pipeline? If you find the performance has instead regressed, we suggest you use performance counters to understand the reasons deeply.
The ideal situation of a pipeline is to complete the execution of one instruction every cycle, but in general the pipeline's throughput cannot reach the ideal situation, mainly for the following reasons:
- Insufficient instruction supply capacity; not enough instructions can be provided to the pipeline
- Insufficient data supply capacity; the execution of memory access instructions is stalled
- Insufficient computational efficiency; due to the existence of the above three hazards, the pipeline needs to be stalled
Locate the performance bottleneck
To improve the pipeline's efficiency, we first need to locate the performance bottleneck. Try adding more performance counters to the pipelined processor and analyze the current performance bottleneck from the various stalling causes.
Decide whether to adopt the following optimizations based on your design
The following introduces some possibly useful optimizations. Whether to adopt them in the RTL design depends on many factors, including your previous design, the analysis of the current performance counters, and the remaining available area. But we still require you to evaluate the expected performance gain of the corresponding technique before performing the RTL implementation; this is very important training for architectural design capability: you can choose not to implement a certain optimization technique, but you need to use data obtained from quantitative analysis to justify your decision.
However, the optimization corresponding to "reducing data hazard stalling" is an important knowledge point, and we treat it as a mandatory task.
In short, if you did the previous area optimization work well, now you have more opportunities to optimize.
Improving Instruction Supply Capacity
In the previous multi-cycle processor, assuming each instruction takes 5 cycles to execute, as long as the instruction supply capacity reaches 0.2 instructions/cycle, the multi-cycle processor's instruction consumption demand can be satisfied. But in a pipelined processor, the ideal instruction consumption demand rises to 1 instruction/cycle; if the instruction supply capacity cannot reach the corresponding level, the pipeline's advantages cannot be exploited. However, for the icache, a miss requires accessing memory, in which case the above instruction supply capacity definitely cannot be reached; therefore, we focus on the icache's instruction supply capacity on hits. Depending on the icache design, whether the icache needs to be optimized here will also lead to different decisions.
Specifically, if your icache can determine whether it hits within 1 cycle and return the instruction to the IFU on a hit, then the icache's instruction supply capacity is already close to 1 instruction/cycle, basically satisfying the pipelined processor's instruction consumption demand. In this case, you basically do not need to further improve the instruction supply capacity, but you may pay the price of a lower frequency, since the icache needs to complete quite a few operations in one cycle, which also prevents the pipeline from working at a higher frequency.
If your icache needs multiple cycles to return an instruction to the IFU even on a hit, then the icache's instruction supply capacity is at most 0.5 instructions/cycle, or even lower. Under such instruction supply capacity, the pipeline's performance will be significantly constrained. Assuming the icache needs 3 cycles to return an instruction to the IFU on a hit, the following instruction space-time diagram results. Since cache is pronounced the same as cash, some English literature also uses $ to refer to cache; the figure below, for simplicity, also uses I$ to refer to icache, replacing the previous IF, because at this time the time IF needs to wait is consistent with the icache access time:
T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13
+--------------+----+----+----+----+
I1 | I$ | ID | EX | LS | WB |
+--------------+----+----+----+----+
+--------------+----+----+----+----+
I2 | I$ | ID | EX | LS | WB |
+--------------+----+----+----+----+
+--------------+----+----+----+----+
I3 | I$ | ID | EX | LS | WB |
+--------------+----+----+----+----+
To improve the icache's instruction supply capacity, to some extent we also need to improve the icache's throughput. This demand is very similar to the "improving instruction execution throughput" mentioned above; naturally, we can also try to pipeline the icache accesses!
T1 T2 T3 T4 T5 T6 T7 T8 T9
+----+----+----+----+----+----+----+
I1 | I$1| I$2| I$3| ID | EX | LS | WB |
+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+
I2 | I$1| I$2| I$3| ID | EX | LS | WB |
+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+
I3 | I$1| I$2| I$3| ID | EX | LS | WB |
+----+----+----+----+----+----+----+
Estimate the performance gain of pipelining the icache
Try to roughly estimate the performance gain of pipelining the icache based on performance counters.
The figure above further divides the icache access into 3 stages and overlaps these 3 stages in time through pipeline technology, so that the icache's throughput on hits is close to 1 instruction/cycle. To implement the pipelined icache, you can design the above stages according to the state transition process of the icache on a hit. This is very similar to turning the processor into a pipeline, and is even simpler than the processor pipeline, because the icache's working process has no concept of control hazards. Of course, if the icache misses, the icache pipeline still needs to stall, and the memory access and icache update need to be controlled through a state machine. Since a miss causes an icache update, this may lead to problems similar to data hazards, so you need to consider how to handle the situation correctly; how to solve it specifically still depends on your implementation.
Implement pipelined icache
If your icache needs multiple cycles to return instructions to the IFU on a hit, try borrowing the idea of an instruction pipeline to pipeline the icache accesses, thereby improving its instruction supply capacity. After implementation, try to evaluate through performance counters and benchmarks whether the improvement in instruction supply capacity meets expectations.
Dividing the icache access into 3 stages above is only an example; you should decide how to divide the stages according to your specific design. If you previously implemented the pipeline with something like PipelineConnect(), you will find the icache pipelining is easy to implement: you only need to define the information to be transferred between stages, and you have already implemented close to 90% of the work.
After implementation, try comparing it with the previously estimated performance improvement to check whether your implementation meets expectations.
Reducing Data Hazard Stalling
In the simple pipeline above, we handle RAW data hazards by stalling and waiting. This approach requires waiting for the dependent register to be written with the new value before the stalled instruction can continue; obviously, such waiting reduces the pipeline's throughput.
One observation is that the new value of the dependent register is written in the WB stage, but in fact this value is computed as early as the EX stage and is passed along the pipeline to the LS stage and the WB stage. Therefore, we can consider taking the computed new value in advance from these stages for use by subsequent instructions, so that they can obtain the correct source operand and start executing without waiting for the dependent register to complete the update. This technique is called "forwarding" or "bypass."
T1 T2 T3 T4 T5 T6 T7 T8
+----+----+----+----+----+
I1: add a0,t0,s0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
| | |
V | |
+----+----+----+----+----+
I2: sub a1,a0,t0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
| |
V |
+----+----+----+----+----+
I3: and a2,a0,s0 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
|
V
+----+----+----+----+----+
I4 xor a3,a0,t1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
Estimate the ideal performance gain of forwarding
As can be seen, forwarding can well eliminate RAW stalling other than load-use hazards. As for the load-use hazard, because the load instruction needs to wait for the data to be read before forwarding, the pipeline still needs to be stalled before that.
Try to estimate the ideal performance improvement that forwarding can bring based on performance counters.
Let's first discuss the modifications forwarding makes to the data path. In the pipeline above, there are 3 forwarding sources, namely the EX stage, the LS stage, and the WB stage; they may all carry data that can be forwarded. But forwarding cannot be performed unconditionally; the forwarding source must satisfy the following conditions: it will write to a register, the register number to be written matches the dependent register number, and the data is already ready. The first two conditions are the same as the RAW hazard detection conditions mentioned above, so the RAW hazard detection logic can be reused; the last condition is related to the instruction's behavior. Most computational instructions can compute the result in the EX stage, so the result obtained in the EX stage can be forwarded to the ID stage; but a load instruction can only compute the memory access address in the EX stage, so it should not be forwarded in the EX stage, and in the LS stage it needs to wait for the handshake on the R channel of the bus before getting the returned data, so it should not be forwarded before that either.
Besides the data path changes, we also need to consider modifications to the control path. Previously in the simple pipelined processor, once a RAW hazard was detected, the pipeline was stalled. With forwarding, the conditions for stalling the pipeline change:
- If the ID stage does not detect a RAW hazard, there is no need to stall the pipeline, consistent with the simple pipeline above
- If the ID stage detects a RAW hazard and some stage satisfies the forwarding conditions, there is no need to stall the pipeline, and the forwarded data is used as the ID stage's output
- If the ID stage detects a RAW hazard but no stage satisfies the forwarding conditions, the pipeline needs to be stalled
In particular, if multiple instructions satisfy the forwarding conditions at the same time, careful consideration is needed. Consider the following instruction sequence:
T1 T2 T3 T4 T5 T6 T7 T8
+----+----+----+----+----+
I1: add a0, a0, a1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I2: add a0, a0, a1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I3: add a0, a0, a1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I4: add a0, a0, a1 | IF | ID | EX | LS | WB |
+----+----+----+----+----+
Assuming I1 does not depend on any instruction older than itself, I1's execution need not be stalled; for I2, it depends on I1's result, but through forwarding, I1's result in the EX stage can be forwarded at time T3 to I2 in the ID stage, so I2's execution need not be stalled either; for I3, at time T4, both I2 in the EX stage and I1 in the LS stage satisfy the forwarding conditions, but from the ISA state machine's perspective, instructions execute serially, so the a0 read by I3 should be the result of the most recent write to a0; therefore, the forwarding should be from I2 in the EX stage; similarly, for I4, at time T5, I3 in the EX stage, I2 in the LS stage, and I1 in the WB stage all satisfy the forwarding conditions, but from the ISA state machine's perspective, the forwarding should be from I3 in the EX stage. That is, when multiple instructions satisfy the forwarding conditions simultaneously, the youngest instruction should be selected for forwarding.
Implement forwarding
According to the above content, implement forwarding in the pipeline to eliminate most RAW hazards. After implementation, try comparing it with the previously estimated performance improvement to check whether your implementation meets expectations.
The forwarding scheme in textbooks
The forwarding scheme above forwards the calculation results of other stages to the ID stage, and then selects the correct operand to feed into the pipeline stage register; while most textbook forwarding schemes forward to the EX and LS stages, and then select the correct operand before computation.
Try comparing these two schemes. If you cannot figure it out, you can implement both schemes separately and compare them in terms of IPC, frequency, area, and other aspects.
Reducing Control Hazard Stalling
In the simple pipeline above, we use speculative execution to handle control hazards. Specifically, we speculate "the next static instruction is always executed next"; if the speculation is correct, the stalling caused by control hazards can be eliminated. But in fact, the above speculation is not always correct; in that case the pipeline needs to be flushed, wasting several cycles. To improve the pipeline's execution efficiency, one angle is to reduce the negative impact caused by flushing the pipeline.
Estimate the performance gain of optimizing control-hazard-related stalling
Try to roughly estimate the performance when all control-hazard-related stalling is completely eliminated, based on performance counters, thereby obtaining the ideal performance gain of the corresponding optimization technique.
To reduce the negative impact of flushing the pipeline on the processor's execution efficiency, the following two directions can be considered:
- Reduce the cost of a single pipeline flush. This requires computing the branch instruction's result as early as possible. Some textbooks introduce a scheme of computing the branch result in the ID stage, which can obviously improve the pipeline's IPC, but this scheme also needs to be comprehensively evaluated in terms of frequency and area.
- Reduce the number of pipeline flushes. This requires improving the speculation accuracy. According to the above analysis, the accuracy of "speculating that no exception occurs" is already close to 100%, so the main consideration is the speculation accuracy of branch and jump instructions.
The speculation accuracy of branch instructions is usually improved through "branch prediction" technology; the module that performs branch prediction is called a branch predictor. The execution result of a branch instruction is either "taken" or "not taken," so branch prediction only needs to predict one of the two choices; how exactly a prediction is given is called a branch prediction algorithm. Considering whether runtime information is referenced, branch prediction algorithms are divided into static prediction and dynamic prediction. Here we first introduce static prediction algorithms; we will introduce dynamic prediction algorithms in Stage A.
Experience the importance of branch predictors in modern processors
Try to count the proportion of branch instructions in the number of dynamic instructions, i.e., assuming on average every x instructions contains one branch instruction, find x.
Assume that in an ideal five-stage pipelined processor, the instruction supply capacity is 1 instruction/cycle, there are no structural hazards or data hazards, all memory access latencies are 0 cycles, jump instructions are always predicted correctly, but branch instructions may be mispredicted, and branch instructions compute the branch result in the EX stage. Based on the x obtained above, calculate the processor's IPC at different branch prediction accuracies: 100%, 99.5%, 99%, 95%, 90%, 80%.
Improve the above processor into a 15-stage out-of-order single-issue pipeline, where branch instructions compute the branch result at stage 13; keep the other assumptions unchanged and recalculate the processor's IPC at different branch prediction accuracies.
Continue to improve the processor into a 15-stage out-of-order quad-issue pipeline; keep the other assumptions unchanged and recalculate the processor's IPC at different branch prediction accuracies.
Static prediction only makes predictions based on the branch instruction itself. Since the branch instruction itself does not change during program execution, for a given branch instruction and a given static prediction algorithm, the prediction result is always the same. The "always speculate that the next static instruction is executed next" above, from the perspective of branch prediction technology, is "always not taken," a static prediction algorithm. Another static prediction algorithm is "always taken."
In fact, depending on the direction of the branch target, whether a branch instruction's result is taken is biased. This is actually related to loop behavior in programs: for example, when the branch target is forward (younger instruction), it may be a loop exit, so it is biased not to be taken; when the branch target is backward (older instruction), it may be re-entering the loop body, so it is biased to be taken. A static prediction algorithm exploiting this property is called BTFN (Backward Taken, Forward Not-taken): if the branch target is backward, predict taken; otherwise, predict not taken. When implementing, you only need to look at the sign bit of the B-type instruction's offset to obtain the prediction. In fact, the RISC-V manual also recommends compilers generate code in the BTFN pattern:
Software should also assume that backward branches will be predicted taken and
forward branches as not taken, at least the first time they are encountered.
An important metric for evaluating a branch prediction algorithm is prediction accuracy. Similar to the previous icache, for a given program, which branch instructions need to be executed and the execution result of each branch instruction are all fixed. As long as we obtain the program's itrace, we can quickly compute a branch prediction algorithm's accuracy, without needing RTL-level simulation. Furthermore, itrace already contains the complete instruction stream; the traces of non-branch instructions have no effect on the execution results of branch instructions. Therefore, what we truly need is only the trace of branch instructions, which we call btrace (branch trace).
According to the above analysis, we only need to implement a functional simulator of a branch predictor, which we call branchsim. branchsim receives btrace, predicts whether each branch instruction is taken according to the branch prediction algorithm, then compares with the execution results recorded in btrace, and computes the algorithm's prediction accuracy. As for btrace, we can generate it quickly through NEMU.
Implement branchsim
According to the above introduction, implement a simple branch prediction simulator branchsim, then evaluate the accuracy of the above static prediction algorithms, and estimate the performance gain brought by the prediction algorithm based on the prediction accuracy.
If you are interested in dynamic prediction algorithms, you can first study the relevant materials, then implement the corresponding algorithms in branchsim and evaluate their accuracy.
Like cachesim, branchsim can also serve as a REF for branch prediction performance. For example, the simple pipeline above adopts the static prediction algorithm of "always not taken," and the related performance counters should be completely consistent with the statistics given by branchsim.
After selecting a branch prediction algorithm with good performance through branchsim, we can consider how to implement a branch predictor in the processor. Generally speaking, the branch predictor's prediction result needs to be provided to the IFU: if taken is predicted, let the IFU fetch from the branch instruction's target; otherwise, let the IFU fetch from PC + 4. But in fact, we can only know whether an instruction is a branch instruction in the ID stage, and if it is, we can also only know its branch target in the ID stage. In the IF stage, we only have the PC value, and it is difficult to obtain the above information for branch prediction.
The way to solve the above problem is to maintain a table of the correspondence between PCs and branch targets; this table is called the BTB (Branch Target Buffer). The BTB can be viewed as a special cache indexed by the PC value. If it hits, it means the PC corresponds to a branch instruction, and the branch target can be read from it; if it misses, it means the instruction corresponding to the PC is not a branch instruction, and at this time it suffices to let the IFU fetch from PC + 4. In addition, the BTB needs to be filled and updated during processor execution; in principle, the BTB can be updated as early as when the branch instruction is decoded in the ID stage. Usually the number of BTB entries is limited; if no free entry is found during an update, according to the principle of locality, the old entry should be overwritten. In particular, when the processor is reset, all BTB entries are invalid, and the correct branch target cannot be read at this time. But since branch prediction is a speculative execution technique, a misprediction does not affect the correctness of the processor's program execution; once correct entries are written into the BTB, effective prediction can be performed.
tag target
+-------+----------+ Branch Target Buffer
+----+ +-------+----------+
| PC |---> +-------+----------+
+-+--+ +-------+----------+
| +-------+----------+
| | | branch predicted
| v | target +-----------+ next PC +-----+
| +----+ +------->| branch |---------->| IFU |
+--------->| == |-------------->| predictor | +-----+
+----+ is branch +-----------+
Implement a branch predictor
Since the information of different branches may replace each other in a limited-entry BTB, when performing branch prediction, the branch target of the branch instruction corresponding to the current PC is not always available. This situation will affect the branch prediction accuracy, so you need to add a BTB to branchsim to calibrate its prediction accuracy.
Specifically, first implement a simple BTB in RTL, with no restrictions on its organization; you can choose direct-mapped, fully associative, or set-associative according to your needs. You can also add new fields to the BTB as needed. After implementation, evaluate its area, choose an appropriate number of BTB entries based on the remaining area, then adjust branchsim according to this number of entries and re-evaluate the branch prediction algorithm's accuracy.
After re-evaluation, comprehensively consider all factors to decide how to implement the branch predictor. After implementation, compare the branch prediction accuracy of the RTL with the branch prediction accuracy computed by branchsim.
What is described above is the prediction of branch instructions. Jump instructions also require speculative execution. Jump instructions are all unconditional, but there are various jump results, so predicting jump instructions mainly means predicting their jump targets. Jump instructions are divided into direct jumps jal and indirect jumps jalr. For a given jal instruction, its jump target is determined, so as long as the jal instruction's jump target is recorded in the BTB, as long as the corresponding entry is not replaced, the next time this jal instruction is encountered, the instruction at the correct jump target can be fetched with 100% accuracy. As for the jalr instruction, its jump target is determined by the value of the source register when it executes, and it is difficult to predict successfully with static prediction algorithms alone; corresponding dynamic prediction algorithms need to be considered. For simplicity, the "always not taken" prediction algorithm can be used for jalr instructions for now.
Estimate the performance gain of correct speculative execution of jump instructions
Try to estimate, based on performance counters, the ideal performance gain when the speculation on jal instructions and jalr instructions is correct, respectively.
If you want to predict the jump targets of jal instructions, you can let jal instructions share the same BTB as branch instructions, or let jal instructions use a separate BTB of their own. The former saves area, but the entries of different instructions may overwrite each other, affecting prediction accuracy; the latter is the opposite. You can decide the design based on branchsim's evaluation.
Implement jump target prediction for jal instructions
According to the above scheme, implement jump target prediction for jal instructions.
Implement jump target prediction for the ret instruction
Generally speaking, the jump target of jalr instructions is hard to predict correctly, but as a special kind of jalr instruction, the ret instruction is relatively easy to predict correctly. If you are interested and have enough remaining area, you can consult the materials on the "Return Address Stack" and implement jump target prediction for the ret instruction in the processor.
Optimize the pipeline
According to the analyzed performance bottleneck, under the area constraint, try to invest the limited area resources into the most worthwhile optimization techniques to improve the processor's performance as much as possible.
Re-examine the processor's performance optimization
We can anticipate that when you finish this part, you will not feel very happy: either the available area is very tight and it is hard to add optimization techniques; or after adding optimization techniques, the processor frequency drops, offsetting the IPC improvement the technique brings; or after investing a lot of effort, you finally make both area and frequency look good, but find the IPC improvement is very small......
More importantly, you should vaguely feel a sense of helplessness: pipeline is the pinnacle of what computer organization textbooks teach, and is this all the performance it delivers? In fact, this illusion of a pinnacle comes from the textbooks' heavy weakening of instruction supply and data supply, making you mistakenly believe that computational efficiency is everything in processor design, and that out-of-order multi-issue is the ultimate pursuit of processor design.
In fact, this experience of yours precisely reflects the famous "memory wall" in the field of computer systems: the performance of memory seriously affects the realization of the CPU's performance. Theoretically, improving a multi-cycle processor into a pipelined processor should yield a performance gain close to 5 times, but in a system containing modern memory, the final performance is also closely related to the memory's performance. And Amdahl's law actually predicted your helplessness: if memory access cannot keep up, no matter how fast the CPU's computing power is, it is futile.
Therefore, you need to wake up from the illusion that "once you learn the pipeline, you have architectural design capability," realize the significance of performance counters, Amdahl's law, simulators, etc. for architectural design, learn to make reasonable trade-offs among area, frequency, and IPC, and even find a solution that performs well in all aspects. This is what a qualified architect needs.
And the above abilities cannot be obtained merely by translating the architecture diagrams in books into RTL code. If you only refer to the code in some books, forget about it. On the contrary, the reason we organize the lecture content in the current order is to help you wake up from the above illusion as early as possible, face the reality of the memory wall in an SoC, and then learn to scientifically explore reasonable processor optimization solutions step by step.
In terms of results, the processor you design may still be weak in performance, but if you have completed the training we set up, you have already trained real architectural design capability: you learn to analyze performance bottlenecks, to think of new solutions from them, to estimate their performance gains, to implement these solutions under various constraints, and to evaluate whether your implementation meets expectations...... These are much more important than merely being able to write a pipelined processor in RTL.
Therefore, you can also test whether you have architectural design capability in the following way: if you do not know what to do without reference books, or need to ask others to know the pros and cons of a scheme, then you do not have architectural design capability.
Handling fence.i
Finally, we also need extra handling for the execution of the fence.i instruction in the pipeline. Recall the semantics of fence.i: its behavior is to ensure that fetch operations after it can see the data modified by store instructions before it. We already guaranteed, when implementing the icache, through special handling of the icache, that subsequent fetch operations will not fetch stale instructions through the icache.
In a pipelined processor, stale instructions may exist in the pipeline. Consider the following example: suppose fence.i takes effect in the EX stage, but as instructions younger than fence.i, I3 and I4 have already been fetched and are in the pipeline; they may be stale. Continuing to execute them may cause the CPU state machine's transition result to be inconsistent with the ISA state machine, resulting in errors.
T1 T2 T3 T4 T5 T6 T7
+----+----+----+----+----+
I1: add | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+----+----+----+
I2: fence.i | IF | ID | EX | LS | WB |
+----+----+----+----+----+
+----+----+
I3: ??? may be stale | IF | ID |
+----+----+
+----+
I4: ??? may be stale | IF |
+----+
+----+----+----+----+----+
I5: sub | IF | ID | EX | LS | WB |
+----+----+----+----+----+
Design a counterexample
According to the above analysis, design a fence.i-related test case such that the test case runs correctly in the previous multi-cycle processor but fails in the pipelined processor.
The solution to the above problem is also simple: since the above instructions should not be executed, just flush them. When implementing, you can reuse the flushing logic for speculative execution errors.
Correctly implement fence.i in the pipeline
Flush the pipeline when executing fence.i, then re-run the above test case. If your implementation is correct, the test case will run successfully.
yyz