Synthesis and Optimization of Pipelines for HW Implementations of Dataflow Programs

This paper introduces a new methodology for pipeline synthesis with applications to data flow high-level system design. The pipeline synthesis is applied to dataflow programs whose operators are translated into graphs and dependencies relations that are then processed for the pipeline architecture optimization. For each pipeline-stage time, a minimal number of pipeline stages are first determined and then an optimal assignment of operators to stages is generated with the objective of minimizing the total pipeline register size. The obtained "optimal" pipeline schedule is automatically transformed back into a dataflow program that can be synthesized to efficient hardware implementations. Two new pipeline scheduling: "least cost search branch and bound" and a heuristic technique have been developed. The first algorithm yields global optimum solutions for middle size designs, whereas the second one generates close-to-optimal solutions for large designs. Experimental results on FPGA designs show that the total pipeline register size gain in a range up to 4.68x can be achieved. The new algorithms overcome the known downward and upward direction dataflow graph traversal algorithms concerning the amount of pipeline register size by up to 100% on average.