Instruction Timing

Learning Outcomes

• Practice interpreting waveforms in timing diagrams.
• Given an instruction, identify the critical path through the single-cycle datapath.
• Approximate instruction timing based on the five phases of instruction execution.

🎥 Lecture Video

How should we time our single-cycle datapath? How should we set the clock frequency? In this section, we develop an approximation of instruction timing using the five steps to a RISC-V instruction.

见 #sec-five-steps

Timing Diagram for add

First, let’s consider the delays in our beloved add instruction. Review the add datapath in #anim-datapath-add-full.

The `add` datapath, updated from an [earlier section](/notes/cs61c/datapath/r-type/#sec-datapath-r-type)'s simple `add`-only datapath. Use the menu bar to trace through the animation or access the [original Google slides](https://docs.google.com/presentation/d/10ORU8oWu4rSY7J6uSWl_6OxrJLVLt9EQ/edit?usp=sharing).

#fig-timing-add shows the waveforms for executing an add x1 x2 x3 instruction at address 0x100, followed by add x6 x7 x9 at address 0x104.

Timing diagram for add. Only relevant signal waveforms are shown.

Critical path delay by instruction

Different instructions use different components of the datapath. We now update our definition of critical path to consider the path between clocked element inputs and outputs that matter for the given instruction. For example, accessing DMEM does not matter for an add, whereas setting up the RegFile data to write back does not matter for sw.

Show Answer for `add`

B. There are two “loops” that we consider:³

• The PC update loop, measured from the PC output to the PC input: $t_{\texttt{clk-to-q}} + t_{\texttt{Add}} + t_{\texttt{mux}} + t_{\texttt{setup}}$
• The loop through the ALU, measured from the PC output to the RegFile input: $t_{\texttt{clk-to-q}} + t_{\texttt{IMEM}} + t_{\texttt{Reg}} + t_{\texttt{mux}} + t_{\texttt{ALU}} + t_{\texttt{mux}} + t_{\texttt{setup}}$

$$\begin{aligned} \text{Critical path delay} =& t_{\texttt{clk-to-q}} \\ & + \max \{ t_{\texttt{Add}} + t_{\texttt{mux}}, t_{\texttt{IMEM}} + t_{\texttt{Reg}} + t_{\texttt{mux}} + t_{\texttt{ALU}} + t_{\texttt{mux}} \} \\ & + t_{\texttt{setup}} \\ =& t_{\texttt{clk-to-q}} + t_{\texttt{IMEM}} + t_{\texttt{Reg}} + t_{\texttt{mux}} + t_{\texttt{ALU}} + t_{\texttt{mux}} + t_{\texttt{setup}} \\ =&t_{\texttt{clk-to-q}} + t_{\texttt{IMEM}} + t_{\texttt{RegFile}} + 2 \cdot t_{\texttt{mux}} + t_{\texttt{ALU}} + t_{\texttt{Setup}} \end{aligned}$$

The critical path uses the longer loop through the ALU.

The `beq` datapath, updated from an [earlier section](/notes/cs61c/datapath/b-type/#sec-datapath-b-type)'s simpler datapath. Use the menu bar to trace through the animation or access the [original Google slides](https://docs.google.com/presentation/d/1iI-seGm2A7lSpHoGKM81b67utfyINT1H/edit?usp=sharing).

Show Answer for `beq`

E. Something else.

We leave this derivation to you. Note you may need to make new placeholder delays for control logic…!

The `lw` datapath, updated from an [earlier section](/notes/cs61c/datapath/load-store/#sec-datapath-load-store)'s simpler datapath. Use the menu bar to trace through the animation or access the [original Google slides](https://docs.google.com/presentation/d/1QV6naVOhLr3PVoKszzY-ipUCigknXs3D/edit?usp=sharing).

Show Answer for `lw`

C. Load uses hardware in all five phases of the datapath. We still consider the two “loops” through the datapath³:

• The PC update loop, still measured from the PC output to the PC input.
• The much longer loop, measured from the PC output through the ALU and DMEM, to the RegFile input. We now consider additional hardware for loads:
  • Instruction Decode: The immediate generation block sets imm concurrently with the RegFile retrieving the source register value R[rs1]. We denote this delay as the larger of the two, $\max\{t_{\texttt{RegFile}}, t_{\texttt{Imm}}\}$.
  • Execute: The ALU output computes the memory address, so we incur $t_{\texttt{ALU}}$.
  • Memory: The DMEM read now matters, so we incur DMEM read time, $t_{\texttt{DMEM}}$.

$$\begin{aligned} \text{Critical path delay} =& t_{\texttt{clk-to-q}} \\ & + \max \{ t_{\texttt{add}} + t_{\texttt{mux}}, \\ & t_{\texttt{IMEM}} + t_{\texttt{Imm}} + t_{\texttt{mux}} + t_{\texttt{ALU}} + t_{\texttt{DMEM}} + t_{\texttt{mux}}, \\ & t_{\texttt{IMEM}} + t_{\texttt{RegFile}} + t_{\texttt{mux}} + t_{\texttt{ALU}} + t_{\texttt{DMEM}} + t_{\texttt{mux}} \} \\ & + t_{\texttt{setup}} \\ =& t_{\texttt{clk-to-q}} + t_{\texttt{IMEM}} + \max\{t_{\texttt{RegFile}}, t_{\texttt{Imm}}\} + t_{\texttt{ALU}} + 2 \cdot t_{\texttt{mux}} + t_{\texttt{DMEM}} + t_{\texttt{setup}} \end{aligned}$$

The single-cycle datapath clock is slow

To determine the clock frequency for the single-cycle datapath, we compute delays of each instruction’s critical path, then set the clock period as the worst-case delay incurred over all instructions.

To put some numbers to our earlier analysis, we will simplify our time estimates with #tab-timing-steps, which assumes that the timing of each of the five steps to a RISC-V instruction are dominated by the major functional hardware units.

We can then produce the simplified timing diagram in #fig-timing-phases for an instruction that uses all phases—like our lw instruction from earlier. We can additionally construct #tab-timing-instructions, which shows the time required for various instruction formats.

Approximate timing diagram for the five steps to a RISC-V instruction in the single-cycle-datapath.

While #tab-timing-instructions above shows the shortest time to complete each instruction, we note that the single-cycle datapath, like all synchronous digital systems, shares a single clock.

We further note that each instruction’s critical path often involves accessing major hardware units in sequence. In other words, for most of each clock period, much of our hardware is idle and not computing additional data!

We address these performance issues and more in our pipelined datapath design up next. Stay tuned!

Footnotes

1. These processes take a comparable amount of time, though which is longer depends on the specific technology. In #fig-timing-add, the adder happens to complete faster than the IMEM memory fetch. ↩

2. Note that the waveform represent bundles of wires with a hexadecimal value (contrast this with the clock’s binary high-low signal). The PC output pc bundle of wires update at the same time, because flip-flops are wired in parallel. By contrast, the pc+4 output does not stabilize simultaneously. Because the adder cascades single-bit adders in series, the least significant bits stabilize sooner than the more significant bits. In timing diagrams, we always show the transition to the correct value. For pc+4, this occurs after the propagation delay of the most significant bit. ↩

3. In #fig-timing-add, the control logic decoding of the instruction happens to complete faster than the RegFile register read. We will assume this precedence in later analysis. ↩ ↩² ↩³

4. There are two multiplexers controlled with ASel and BSel, respectively. Both propagation delays occur concurrently, so we only count for one mux’s propagation delay. ↩