Efficient Dynamic Optimisation Heuristics for Dataflow Pipelines

摘要

Large dataflow designs appear as a result of functional specification of modern complex digital systems and/or a result of unfolding and behavioral transformation of looped and branched programs. Since deep-submicron silicon technology provides large amounts of available resources, pipelining optimization without resource sharing can give significant advantages in performance. In this work, we propose a novel pipeline optimization heuristic algorithm, which is named HADD. It is suitable for very large dataflow programs and makes use of efficient dynamic heuristics and a random search on the set of solutions. For a pipeline-stage time-period, it quickly minimizes the number of stages and successively finds the assignment of operators to stages with the objective of minimizing the overall pipeline registers size. The experimental results show that HADD gives solutions that are very close to accurate solutions with only 2% of the difference and overcomes by about 10% on average the best-known heuristic technique HT, which uses mixed static-dynamic heuristics on large designs. Moreover, HADD is c.a. 10 times faster on average against HT.