Software pipelining

In computer science, software pipelining is a technique used to optimize loops, in a manner that parallels hardware pipelining. Software pipelining is a type of out-of-order execution, except that the reordering is done by a compiler (or in the case of hand written assembly code, by the programmer) instead of the processor. Some computer architectures have explicit support for software pipelining, notably Intel's IA-64 architecture.
It is important to distinguish "software pipelining", which is a target code technique for overlapping loop iterations, from "modulo scheduling", the currently most effective known compiler technique for generating software pipelined loops.
Software pipelining has been known to assembly language programmers of machines with instruction-level parallelism since such architectures existed. Effective compiler generation of such code dates to the invention of modulo scheduling by Rau and Glaeser.
Lam showed that special hardware is unnecessary for effective modulo scheduling. Her technique, "modulo variable expansion" is widely used in practice.
Gao et al. formulated optimal software pipelining in integer linear programming, culminating in validation of advanced heuristics in an evaluation paper. This paper has a
good set of references on the topic.
Example.
Consider the following loop:
 for i = 1 to bignumber
 A(i)
 B(i)
 C(i)
 end
In this example, let codice_1, codice_2, codice_3 be instructions, each operating on data codice_4, that are dependent on each other. In other words, codice_1 must complete before codice_2 can start. For example, codice_7 could load data from memory into a register, codice_8 could perform some arithmetic operation on the data, and codice_9 could store the data back into memory. However, let there be no dependence between operations for different values of codice_4. In other words, codice_11 can begin before codice_12 finishes.
Without software pipelining, the operations execute in the following sequence:
 A(1) B(1) C(1) A(2) B(2) C(2) A(3) B(3) C(3) ...
Assume that each instruction takes 3 clock cycles to complete (ignore for the moment the cost of the looping control flow). Also assume (as is the case on most modern systems) that an instruction can be dispatched every cycle, as long as it has no dependencies on an instruction that is already executing. In the "unpipelined" case, each iteration thus takes 9 cycles to complete: 3 clock cycles for codice_12, 3 clock cycles for codice_14, and 3 clock cycles for codice_15.
Now consider the following sequence of instructions "with software pipelining":
 A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ...
It can be easily verified that an instruction can be dispatched "each" cycle, which means that the same 3 iterations can be executed in a total of 9 cycles, giving an average of 3 cycles per iteration.
Implementation.
Software pipelining is often used in combination with loop unrolling, and this combination of techniques is often a far better optimization than loop unrolling alone. In the example above, we could write the code as follows (assume for the moment that codice_16 is divisible by 3):
 for i = 1 to (bignumber - 2) step 3
 A(i)
 A(i+1)
 A(i+2)
 B(i)
 B(i+1)
 B(i+2)
 C(i)
 C(i+1)
 C(i+2)
 end
Of course, matters are complicated if (as is usually the case) we can't guarantee that the total number of iterations will be divisible by the number of iterations we unroll. See the article on loop unrolling for more on solutions to this problem, but note that software pipelining prevents the use of Duff's device.
In the general case, loop unrolling may not be the best way to implement software pipelining. Consider a loop containing instructions with a high latency. For example, the following code:
 for i = 1 to bignumber
 A(i) ; 3 cycle latency
 B(i) ; 3
 C(i) ; 12(perhaps a floating point operation)
 D(i) ; 3
 E(i) ; 3
 F(i) ; 3
 end
would require 12 iterations of the loop to be unrolled to avoid the bottleneck of instruction codice_9. This means that the code of the loop would increase by a factor of 12 (which not only affects memory usage, but can also affect cache performance, "see code bloat"). Even worse, the prologue (code before the loop for handling the case of codice_16 not divisible by 12) will likely be even larger than the code for the loop, and very probably inefficient because software pipelining cannot be used in this code (at least not without a significant amount of further code bloat). Furthermore, if codice_16 is expected to be moderate in size compared to the number of iterations unrolled (say 10-20), then the execution will spend most of its time in this inefficient prologue code, rendering the software pipelining optimization ineffectual.
By contrast, here is the software pipelining for our example (the "prologue" and "epilogue" will be explained later):
 prologue
 for i = 1 to (bignumber - 6)
 A(i+6)
 B(i+5)
 C(i+4)
 D(i+2) ; note that we skip i+3
 E(i+1)
 F(i)
 end
 epilogue
Before getting to the prologue and epilogue, which handle iterations at the beginning and end of the loop, let's verify that this code does the same thing as the original for iterations in the middle of the loop. Specifically, consider iteration 7 in the original loop. The first iteration of the pipelined loop will be the first iteration that includes an instruction from iteration 7 of the original loop. The sequence of instructions is:
However, unlike the original loop, the pipelined version avoids the bottleneck at instruction codice_9. Note that there are 12 instructions between codice_28 and the dependent instruction codice_29, which means that the latency cycles of instruction codice_28 are used for other instructions instead of being wasted.
The prologue and epilogue handle iterations at the beginning and end of the loop. Here is a possible prologue for our example above:
 ; loop prologue (arranged on lines for clarity)
 A(1)
 A(2), B(1)
 A(3), B(2), C(1)
 A(4), B(3), C(2) ; cannot start D(1) yet
 A(5), B(4), C(3), D(1)
 A(6), B(5), C(4), D(2), E(1)
Each line above corresponds to an iteration of the main pipelined loop, but without the instructions for iterations that have not yet begun. Similarly, the epilogue progressively removes instructions for iterations that have completed:
 ; loop epilogue (arranged on lines for clarity)
 B(bignumber), C(bignumber-1), D(bignumber-3), E(bignumber-4), F(bignumber-5)
 C(bignumber), D(bignumber-2), E(bignumber-3), F(bignumber-4)
 D(bignumber-1), E(bignumber-2), F(bignumber-3)
 D(bignumber), E(bignumber-1), F(bignumber-2)
 E(bignumber), F(bignumber-1)
 F(bignumber)
Difficulties of implementation.
The requirement of a prologue and epilogue is one of the major difficulties of implementing software pipelining. Note that the prologue in this example is 18 instructions, 3 times as large as the loop itself. The epilogue would also be 18 instructions. In other words, the prologue and epilogue together are "6 times as large as the loop itself". While still better than attempting loop unrolling for this example, software pipelining requires a trade-off between speed and memory usage. Keep in mind, also, that if the code bloat is too large, it will affect speed anyway via a decrease in cache performance.
A further difficulty is that on many architectures, most instructions use a register as an argument, and that the specific register to use must be hard-coded into the instruction. In other words, on many architectures, it is impossible to code such an instruction as "multiply the contents of register codice_31 and register codice_32 and put the result in register codice_33", where codice_31, codice_32, and codice_33 are numbers taken from other registers or memory. This has often been cited as a reason that software pipelining cannot be effectively implemented on conventional architectures.
In fact, Monica Lam presents an elegant solution to this problem in her thesis, "A Systolic Array Optimizing Compiler" (1989) (). She calls it "modulo variable expansion". The trick is to replicate the body of the loop after it has been scheduled, allowing different registers to be used for different values of the same variable when they have to be live at the same time. For the simplest possible example, let's suppose that codice_1 and codice_2 can be issued in parallel and that the latency of the former is 2 cycles. The pipelined body could then be:
 A(i+2); B(i)
Register allocation of this loop body runs into the problem that the result of codice_39 must stay live for two iterations. Using the same register for the result of codice_39 and the input of codice_2 will result in incorrect results.
However, if we replicate the scheduled loop body, the problem is solved:
 A(i+2); B(i)
 A(i+3); B(i+1)
Now a separate register can be allocated to the results of codice_39 and codice_43. To be more concrete:
 r1 = A(i+2); B(i) = r1
 r2 = A(i+3); B(i+1) = r2
 i = i + 2 // Just to be clear
On the assumption that each instruction bundle reads its input registers before writing its output registers, this code is correct. At the start of the replicated loop body, codice_44 holds the value of codice_39 from the previous replicated loop iteration. Since codice_4 has been incremented by 2 in the meantime, this is actually the value of codice_1 in this replicated loop iteration.
Of course, code replication increases code size and cache pressure just as the prologue and epilogue do. Nevertheless, for loops with large trip counts on architectures with enough instruction level parallelism, the technique easily performs well enough to be worth any increase in code size.
IA-64 implementation.
Intel's IA-64 architecture provides an example of an architecture designed with the difficulties of software pipelining in mind. Some of the architectural support for software pipelining includes: