Pipeline Synthesis and Optimization from Branched Feedback Dataflow Programs
- PDF / 1,215,071 Bytes
- 9 Pages / 595.276 x 790.866 pts Page_size
- 83 Downloads / 223 Views
Pipeline Synthesis and Optimization from Branched Feedback Dataflow Programs Anatoly Prihozhy 1
&
Simone Casale-Brunet 2 & Endri Bezati 3 & Marco Mattavelli 2
Received: 18 April 2019 / Revised: 3 June 2020 / Accepted: 11 June 2020 # Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Large dataflow designs are a result of behavioral specification of modern complex digital systems and/or a result of unfolding and transforming looped and branched programs. Since deep-submicron silicon technology provides large amounts of available resources, pipelining optimization without (or with minimal) resource sharing can give significant advantages in performance. High-level synthesis of CAL-programs is particularly popular in computation intensive applications (e.g., image and video processing, cryptography, wireless communication, etc.) where feedback actors with data flows at input and output ports represent loop-like behavior. In this work, we propose techniques for transforming, analysis, speculatively pipelining and optimizing large branched feedback dataflow programs. We develop an accurate algorithm and introduce fast dynamic and mixed static / dynamic heuristics that firstly minimize the number of pipeline stages for a given pipeline-stage time-period, and secondly minimize the overall pipeline registers size by means of appropriate assignment of feedbacks and instructions to pipeline stages. We also propose a genetic algorithm for tuning the heuristics for a particular design. The experimental results show the algorithms we propose give quickly solutions that are very close to accurate solutions and overcomes the earlier developed algorithms regarding computing time and pipeline parameters. Keywords Dataflow . Feedback . Branching . Pipeline . High level synthesis . Optimization
1 Introduction Pipelining is a certain type of transformation of a digital system behavioral specification into a set of partitions that represent pipeline stages and execute in time-sliced fashion on the input data flow [1–5]. Pipelining increases the operating frequency and throughput of data-intensive digital systems with long critical paths. The optimization of pipeline implementations is a hardcombinatorial problem in general case, and its exhaustive solution is not feasible in acceptable CPU time. For early silicon technologies, pipeline architectures intensively explored the sharing of computational resources Most of the known optimization algorithms generate pipelines executing several clock cycles per * Anatoly Prihozhy [email protected] 1
Computer and System Software Dpt, Belarusian National Technical University, Minsk, Belarus
2
EPFL SCI STI MM, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
3
EPFL IC IINFCOM VLSC, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
stage cycle and solve the problem of how to share functional units among operators and to share pipeline registers among variables. Works [6–9] propose techniques that optimize highly parallelized pipeline
Data Loading...
