Pipelines (for software people)

Pipelining is a very important concept in hardware design, you would be hard-pressed to find any large hardware project that doesn’t have pipelines everywhere, especially if performance is a goal. It is also a central concept in Spade, to the point where explicit pipelining is listed as the second key feature we advertise on the website.

Pipelining doesn’t have a clear analogy in software, so to explain it we will have to start thinking about the hardware we are describing when writing Spade.

Running Example: Is a Point in a Circle?

Let’s start off with an example. Say we want to determine if a point $(𝑝_{𝑥}, 𝑝_{𝑦})$ is inside a circle centered at $(𝑐_{𝑥}, 𝑐_{𝑦})$ with radius $𝑟$ . We can do that by computing the distance from the point to the center and checking if it is smaller than the radius:

\sqrt{{(𝑝_{𝑥} - 𝑐_{𝑥})}^{2} + {(𝑝_{𝑦} - 𝑐_{𝑦})}^{2}} < 𝑟

Since the square root is an expensive computation to perform in hardware, we can square both sides and end up with

{(𝑝_{𝑥} - 𝑐_{𝑥})}^{2} + {(𝑝_{𝑦} - 𝑐_{𝑦})}^{2} < 𝑟^{2}

First Hardware Implementation

In Spade, we can write that as

fnFunctions together with entityEntities together with fn and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fn, entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). point_in_circle(
    px: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    py: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    cx: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    cy: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    r: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits
) -> boolType used to represent 1 bit values {
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. dx = px - cx;
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. dy = py - cy;

    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. distance = dx * dx + dy * dy;
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. r_squared = sext(r * r);

    distance < r_squared
}

The hardware described by this code looks like this:

And this works! It will compute the result we want. However, now we reluctantly have to acknowledge that the real world exists and that this hardware while correct isn’t going to give us great throughput. The problem is that each one of our sub-circuits here are going to take some time to compute their results, each transistor that they end up being built from need some time to toggle between values, so every time we feed in a new input, we have to wait some time before the output becomes ready. On human time scales this is insignificant of course, but at the multi-MHz frequencies we want to run our circuits at, it becomes a limiting factor.

This latency is unavoidable, we can’t do much to get the result of a single computation out of the circuit more quickly than the time it takes to compute the sub-results. However, if we are computing the result of several independent inputs in sequence, we are leaving performance on the table. To see why, Let’s look at what this circuit does over time:

This figure shows which result is being valid and computed in each sub-circuit. The values ( $1$ , $2$ ) are not actual values, but the index of subsequent inputs. When a sub-circuit is computing, it is represented by a horizontal line, and when a result is invalid (a mix of two values), it is represented by dashed areas.

As you can see, we feed in the first values at time 0. The - operator takes some time to compute its result, and when that is done the * operator can start computing its result. In turn, when it is done + can compute its result, until a value is produced at the output.

When that value has been computed and read, we can feed in a second value, and here we see something else interesting in the final few rows of the diagram. The $𝑟^{2}$ computation is much faster than the distance computation, so it starts feeding its output to the > which is now computing the difference between the first set of points and the second radius, a state which persists until the new distance is computed and the actual result is returned.

If you stare at this graph long enough, you may realize that this circuit isn’t using its hardware resources very efficiently. First, only the - operator and $𝑟^{2}$ computation are doing anything, next only the * operator is active, next only the + operator, and so on.

In theory, we could start feeding new values into the circuit as soon as the first stage of the computation is done, as long as we read the result at the right time. As written, this would be difficult, the latency of the operators is a simplification, there is actually a latency for each individual bit being computed, and we will not be able to avoid issues like the final comparison mixing different values, since its latency is shorter than the other branches. If we can deal with these issues however, we will end up with a circuit where we can complete more computations per second without using more hardware resources.

Manual Pipelining

Pipelining is the solution to these issues. In pipelining, we strategically place registers between computations. Graphically, we want to create the following circuit:

Recall from the blinky chapter that a register holds on to its value until a clock signal tells it to replace it with a new value, so what this will allow us to do is to compute all the results before the first line of registers, tick the clock which will start computing the second batch of results, at which point we can safely feed the next batch of inputs to the first stage, and so on.

Now, using the register syntax we have seen already, we could write this as:

entityEntities together with fnFunctions together with entity and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fnFunctions together with entity and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure)., entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. point_in_circle(
    clk: clockType used to represent clock signals.,
    px: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    py: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    cx: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    cy: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    r: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
) -> boolType used to represent 1 bit values {
    reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)) are used for state registers both inside and outside pipelines. which are used to separate stages. dx = px - cx;
    reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)) are used for state registers both inside and outside pipelines. which are used to separate stages. dy = py - cy;

    reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)) are used for state registers both inside and outside pipelines. which are used to separate stages. distance = dx*dx + dy*dy;

    reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)) are used for state registers both inside and outside pipelines. which are used to separate stages. r_squared = sext(r*r);
    reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)) are used for state registers both inside and outside pipelines. which are used to separate stages. r_squared_s2 = r_squared;
    reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)) are used for state registers both inside and outside pipelines. which are used to separate stages. r_squared_s3 = r_squared_s2;

    distance < r_squared_s3
}

But this has a number of issues. First, and perhaps most obvious is the manual registered copies of r_squared. If we end up refactoring this code to add or remove registers or computations, we have to remember to also update these in order to keep things synchronized ¹.

The second, less obvious issue is that this change affects the output of the circuit. If we feed in values at clock cycle 0, the corresponding results will not show up until 3 clock cycles later, since there are 3 registers between the input and output. If you simply instantiated this pipeline without considering this, you would get strange results indeed, and again, if someone refactors this inner pipeline, everyone else who instantiates it would have to know to adjust their code to account for these changes.

Pipelining in Spade

Spade solves these issues by having a pipelining construct built into the language. The pipelined version of our running example looks like this:

pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline.(3) point_in_circle(
    clk: clockType used to represent clock signals.,
    px: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    py: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    cx: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    cy: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits,
    r: int<16>Type used to represent signed integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits
) -> boolType used to represent 1 bit values {
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. dx = px - cx;
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. dy = py - cy;
reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg; which are used to separate stages.) are used for state registers both inside and outside pipelines.
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. dx_squared = dx * dx;
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. dy_squared = dy * dy;
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. r_squared = sext(r*r);
reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg; which are used to separate stages.) are used for state registers both inside and outside pipelines.
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. distance = dx_squared + dy_squared;
reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg; which are used to separate stages.) are used for state registers both inside and outside pipelines.
    distance < r_squared
}

The reg keywords here are not the same as those we have seen before and are actually referred to as pipeline stage markers. They take the variables defined above them, create registers for each of them which future references to those variables will refer to. This decouples the description of the pipelining from the computation. If you realize you want to add, move, or remove stages, you can simply move these reg statements around.

The fn that our initial example used has also been replaced by pipeline(3). The 3 here is the latency of the pipeline, which lets both readers of the code, and the compiler know its latency without having to read the body of the pipeline. When you instantiate pipelines, you do so with inst(3), which means that if the pipeline latency changes in the future, you have to go back and make sure that the instantiating code doesn’t need updating.

With this change in place, we can look at a new timing diagram similar to that which we saw before:

This diagram has a lot going on, so it is best to look at a vertical slice. Focus on the time step when the inputs are set to the fourth value. When this happens, the - circuit starts computing its result for those values. Meanwhile, the first register stage now contains the third value, and the squared computations operate on these values. The second reg stage computes the distance result for the second set of inputs, and finally, the comparison is made on the first input value.

Normally, pipeline diagrams like these only show what is in the individual stages, since the computations are easy to infer from that, so a much simplified version of this diagram looks like this:

Performance: Throughput and Latency

It is worth taking some time to discuss the performance of pipelines. In software, “performance” is a relatively easy concept to grasp, a program that is performant completes its tasks quickly. In a loop, a more performant function will finish more computations in a given time than a less performant function.

However, in hardware, this is not necessarily the case, and pipelining is a very good example of this. What we did with pipelining was allow starting one computation before the previous one finished. This means that we can shove more computations through the circuit in any given time, which is called the throughput.

However, if we look at the time it takes to finish any individual computation, called latency, pipelining had no effect. We still have to wait for the value we are interested in to flow through the whole circuit before we can get the result. In fact, pipelining may even have a slight negative impact on throughput because the latency becomes limited by the slowest stage, since we can only tick the clock once all the stages have finished their computation.

A real world example of mixing up throughput and latency is the saying that “a product manager is someone who thinks two women can give birth to a baby in 4.5 months”. This is of course not true. If you need a baby right now, there is nothing you can do to speed up that process, you have to wait the 9 months. It is the inherent latency of the “computation”. However, if you are an especially unethical product manager who wants to maximize the “number of babies produced per year” metric, you can certainly use more women, the throughput is higher.

Whether latency or throughput is important depends on your application. If you are streaming data through your circuit, you are most often interested in throughput, with latency being a secondary concern. If you need the result of one computation in order to start the next one, you are instead much more concerned with latency.

Performance: Where to put Pipeline Stages

Another important discussion for performance is when and where to use pipelining and when and where to place the register stages. In the previous example, we assumed that each computation takes the same amount of time, but in practice, multipliers are a lot slower than additions and comparisons. The maximum frequency we can run a pipeline at is determined by the slowest stage, so putting stages between fast computations will not have any impact on throughput, but will harm latency. For example, consider a circuit which computes:

(𝑎 + 𝑏 + 𝑐) * 𝑑

which we can write as: ²

pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline.(3) some_computation(
    clk: clockType used to represent clock signals.,
    a: uint<8>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits, b: uint<8>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits, c: uint<8>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits, d: uint<8>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits
) -> uint<16>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits {
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. s1 = a +.Add two values, producing a value of the same size while wrapping ifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it. the result overflows. This is unlike + where the addition results in one more bit than the input type, guaranteeing no overflows. b;
reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg; which are used to separate stages.) are used for state registers both inside and outside pipelines.
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. s2 = s1 +.Add two values, producing a value of the same size while wrapping ifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it. the result overflows. This is unlike + where the addition results in one more bit than the input type, guaranteeing no overflows. c;
reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg; which are used to separate stages.) are used for state registers both inside and outside pipelines.
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. result = s2 * d;
reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg; which are used to separate stages.) are used for state registers both inside and outside pipelines.
    result
}

and which, assuming that multipliers are twice as slow as adders would have the following pipelining diagram:

Since the additions are twice as fast as the multipliers, we can combine them all into one stage like this:

pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline.(2) some_computation(
    clk: clockType used to represent clock signals.,
    a: uint<8>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits, b: uint<8>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits, c: uint<8>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits, d: uint<8>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits
) -> uint<16>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits {
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. s1 = a +.Add two values, producing a value of the same size while wrapping ifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it. the result overflows. This is unlike + where the addition results in one more bit than the input type, guaranteeing no overflows. b;
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. s2 = s1 +.Add two values, producing a value of the same size while wrapping ifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it. the result overflows. This is unlike + where the addition results in one more bit than the input type, guaranteeing no overflows. c;
reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg; which are used to separate stages.) are used for state registers both inside and outside pipelines.
    letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. result = s2 * d;
reg;reg; is used in a pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. to separate stages. When you refer to a variable defined above a reg; statement below a reg; statement you refer to a registered version of the original value. Registers defined with an explicit clockType used to represent clock signals. (reg(clk)reg(clk) is used to define registers which maintain the state of your circuit.
All registers have a clockType used to represent clock signals. (clk), a name and a new value after the = which is given as a function of the current value. Registers can also have a reset(Defines the reset value of a register as (trigger: value). When trigger ist rue, the reset is synchronously reset to valuetrigger: value) wich means that the reset is synchronously set to value when trigger is true.
In pipelines, you can also define registers with reg; which are used to separate stages.) are used for state registers both inside and outside pipelines.
    result
}

which results in this timing diagram:

This allows us to run the circuit at the same frequency, still limited by the multipliers, but it has a lower latency now since we removed one pipeline stage. Notice how this timing diagram “finishes” three clock cycles earlier than the last one.

Knowing when and where to insert pipeline stages is in some ways a bit of an art, and in some ways a mechanical process. When you compile your Spade code, the tool will statically evaluate the computation time of all your sub-circuits and tell you where the path that limits your frequency is. Using that information, you can add a pipeline stage through that part to break it up into two clock cycles, increasing the clock cycle latency but reducing the total computation time since the clock can now run faster. Then you can simply repeat this process until you reach your performance target, or when it is no longer possible to split computations into smaller sub-computations. Since Spade separates computation from pipeline staging, you can do this iteratively. It is often possible to simply write the non-pipelined circuit first, simulate it to verify correctness, then start adding pipeline stages for performance.

However, even with the tooling that can tell you the paths that limit your performance, it is useful to know roughly how fast individual circuits are. Multipliers being slower than adders, for example, and this is something that only comes with practice.

More Pipelining

The pipelining system has a few more bells and whistles that are useful to know about, but now that you know what pipelines are and why you would want to use them, you should be able to follow the Pipelines for Hardware People chapter to read about them.

An Anecdote About Spectre and Meltdown
If you remember the spectre and meltdown processor vulnerabilities, they are interesting case studies of pipelines, throughput, and latency.
In a processor, our primary goal is throughput: we want to execute as many instructions per second as possible. To do so, high performance processors are almost always pipelined. While the processor is computing the result of one instruction, it is fetching the next one, and writing the result of the previous one (in practice, processor pipelines are much more fine grained, but for the example this is enough). However, what happens if we have a jump instruction that depends on the result of the previous instruction? For example, in the following code:
  add r1, r2, r3
  jump_if_zero r1, skip
  insn1
skip:
  insn2
should we start fetching insn1 or insn2 after the jump? The simple answer is that we don’t know, so we’ll pause (usually called “stall”) the pipeline until we know the result of the add. In essence, that means that the throughput of our processor is limited by the latency of each executed instruction.
However, this leaves performance on the table, and in a high performance processor, this is not acceptable. What processor designers realized is that there is often a pattern to jump instructions. For example, a jump back to the start of a loop is going to be taken once per iteration, and only skipped once the loop is finished. What modern processors do is to use this fact and speculatively start executing the most likely branch before knowing if it is going to be taken or not. This is fine as long as it is possible to roll back all effects of that decision if it turns out to be wrong.
In practice, processors usually don’t roll back, instead they keep a queue of “speculated” results, and those results are only committed to memory once it is known if they should have been executed or not.
However, spectre and meltdown are side channel attacks, the primary results are correctly rolled back, but other parts of the processors are affected in a measurable way. To see why, consider this code:
  load r1, <address we are not allowed to access>
  jump_if_zero r1, skip
  load r2, <address we are allowed to access>
skip:
  insn2
In a processor with a deep pipeline³ the processor would start executing the first load instruction of an unreachable address. This is supposed to tell the operating system that something fishy is going on and that the process should fault.
However, before that happens, a few more instructions are put in the pipeline. First, the jump_if_zero instruction, and then the load r2 instruction. In a very deep pipeline, the processor will need time to fully evaluate the jump, start working on load r2 and send the request to the memory controller before the fault for the first load is emitted at the end of the pipeline.
This is fine, right? The invalid load will be be aborted, so the subsequent instructions will not be committed and the system can move on. Unfortunately, modern processors also have a cache, so so while the r1 value was never updated with the value we are not allowed to see, the load r2 would only have been executed if the illegal data was 0.
Now, after executing this program <address we are allowed to access> will be in the cache if and only if the data was 0. We can easily measure if a value is in the cache by loading it and seeing if it takes a few clock cycles, or a few hundred clock cycles, and thereby find out if the value was 0 even if we can’t read the value directly.
Naturally, this is a very simplified hand-wavy example, the actual spectre and meltdown vulnerabilities are more complex, but the basic principle is the same. Processor designers found a way to increase the throughput of a pipelined latency limited system, but failed to notice that it interacting with the cache allowed a smart attacker to extract data.

This is actually how pipelines in most HDLs are handled a lot of the time. ↩︎
Using the wrapping add operator +. for sake of simplicity. ↩︎
Many stages, for some definition of many ↩︎