Pipeline Synthesis and Optimization from Branched Feedback Dataflow Programs

Endri Bezati, Simone Casale Brunet, Marco Mattavelli, Anatoly Prihozhy
SPRINGER, 2020
Article

Résumé

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.

Official source

https://infoscience.epfl.ch/record/278882?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Endri Bezati, Simone Casale Brunet, Marco Mattavelli, Anatoly Prihozhy
SPRINGER, 2020
Article

Résumé

Official source

https://infoscience.epfl.ch/record/278882?ln=fr

À propos de ce résultat

Concepts associés (14)

Concepts associés

Chargement

Publications associées (9)

Publications associées

Chargement

High-level synthesis of dataflow programs for heterogeneous platforms

Endri Bezati

The growing complexity of digital signal processing applications implemented in programmable logic and embedded processors make a compelling case the use of high-level methodologies for their design and implementation. Past research has shown that for complex systems, raising the level of abstraction does not necessarily come at a cost in terms of performance or resource requirements. As a matter of fact, high-level synthesis tools supporting such a high abstraction often rival and on occasion improve low-level design. In spite of these successes, high-level synthesis still relies on programs being written with the target and often the synthesis process, in mind. In other words, imperative languages such as C or C++, most used languages for high-level synthesis, are either modified or a constrained subset is used to make parallelism explicit. In addition, a proper behavioral description that permits the unification for hardware and software design is still an elusive goal for heterogeneous platforms. A promising behavioral description capable of expressing both sequential and parallel application is RVC-CAL. RVC-CAL is a dataflow programming language that permits design abstraction, modularity, and portability. The objective of this thesis is to provide a high-level synthesis solution for RVC-CAL dataflow programs and provide an RVC-CAL design flow for heterogeneous platforms. The main contributions of this thesis are: a high-level synthesis infrastructure that supports the full specification of RVC-CAL, an action selection strategy for supporting parallel read and writes of list of tokens in hardware synthesis, a dynamic fine-grain profiling for synthesized dataflow programs, an iterative design space exploration framework that permits the performance estimation, analysis, and optimization of heterogeneous platforms, and finally a clock gating strategy that reduces the dynamic power consumption. Experimental results on all stages of the provided design flow, demonstrate the capabilities of the tools for high-level synthesis, software hardware Co-Design, design space exploration, and power optimization for reconfigurable hardware. Consequently, this work proves the viability of complex systems design and implementation using dataflow programming, not only for system-level simulation but real heterogeneous implementations.

EPFL2015

Chargement

Nowadays, the general trend towards to minimally invasive interventions is present in all the medical domains. For the surgical intervertebral spinal disc cutting or removal domain, it is particularly a necessity because the manual methods currently employed are tedious, time consuming and taxing on the hands of the practitioner. In that context, new devices that are small enough to pass through a small opening in the skin or through a small portal are required. A detailed analysis of current cutting methods that are or could be used for disc and disc nucleus removal provided that ultrasonics technology should be investigated as a possible solution. The study of ultrasonics technology to fulfil the overall cutting function needed for spinal annulus and nucleus disc material removal is based on a design methodology that breaks down the overall cutting function in many partial functions. The applied design methodology consists in drawing a complete catalogue of solutions for each partial function. Based on a predetermined choice of criteria for each partial function, the evaluation and the classification of each solution allows determination of the best solutions for each partial function. A new ultrasonic transducer designed device composed of a piezoelectric stack for the source of energy and movement, a transmission partial function with rods or discs, an amplification partial function with exponential horns and the cutting partial function solutions is detailed. Existing analytical methods for the design of ultrasonic transducers are mostly based on quarter wavelength segments used to build the transducer. The modeling of that transducers with a finite element method (FEM) avoids building the prototypes and constitutes progress. Analytical models different from the quarter wavelength approach have already been developed and are very useful when used in an optimization process. Furthermore, when the geometry of the analyzed model is not straightforward, a FEM optimization approach to solve that kind of problems can be a valid solution too. Some existing optimization algorithms and other already developed pseudo-gradient methods applied to optimize the analytical models of the ultrasonic transducers are not valid for numerical optimizations where the computing time is a key factor. This leads to the development a new genetic algorithm (GA) optimization methods. One advantage being that the number of parameters to be optimized does not change the complexity of the algorithm unlike other algorithms. Three GAs with improvements done on different parts are discussed, implemented and tested. One GA is chosen to optimize the transducer model with numerical methods. As the main drawback with FE optimizations is the amount of computation time spent for each simulation, this creates a need to develop numerical 2D models that can be quickly simulated but with accurate results. Ultrasonic transducer prototypes are also built and measured. As the prototype has to be used for the cutting or the removal of spinal disc material, the cutting effect of the prototypes has been tested and evaluated.

EPFL2009

Chargement

Pipeline Synthesis and Optimization of FPGA-based Video Processing Applications with CAL

Ab Al Hadi Bin Ab Rahman, Marco Mattavelli, Anatoly Prihozhy

This paper describes a pipeline synthesis and optimization technique that increases data throughput of FPGA-based system using minimum pipeline resources. The technique is applied on \CAL dataflow language, and designed based on relations, matrices and graphs. First, the initial As-Soon-As-Possible (ASAP) and As-Late-As-Possible (ALAP) schedules, and the corresponding mobility of operators are generated. From this, operator coloring technique is used on conflict and nonconflict directed graphs using recursive functions and explicit stack mechanisms. For each feasible number of pipeline stages, a pipeline schedule with minimum total register width is taken as an optimal coloring, which is then automatically transformed to a description in \CAL. The generated pipelined \CAL descriptions are finally synthesized to HDL for FPGA implementation. Experimental results of three video processing applications demonstrate up to 3.9x higher throughput for pipelined compared to non-pipelined implementations, and average total pipeline register width reduction of up to 39.6% and 49.9% between the optimal, and ASAP and ALAP pipeline schedules respectively.

Hindawi Publishing Corporation2011

Chargement

High-level synthesis of dataflow programs for heterogeneous platforms

Endri Bezati

EPFL2015

EPFL2009