Performance estimation of program partitions on multi-core platforms, 2016 26th International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS)

The exploration of different design configurations of dynamic dataflow programs executed on many-core or multi-core platforms is, in general, a very difficult task. Determining a close-to-optimal partitioning, scheduling and buffer dimensioning configuration, when associated with a performance optimization function, belongs to the class of NP-complete problems. In order to explore the space of feasible solutions with efficient heuristics looking for solutions of good quality, it is important to be able to evaluate the design points in terms of the performance optimization function with sufficient precision without having to physically execute the program on the platform. This paper presents a performance estimation approach and an associated SW tool capable of exploring, with a high level of accuracy, the space of feasible solutions by using only a limited set of measurements from the physical processing platform. Moreover, the estimation model allows an identification of possible improvements that can be applied to different configurations. The results reported validate the accuracy of the methodology using examples of dataflow implementations of dynamic video codec designs for two different classes of platforms: Transport Triggered Architecture and Intel platforms.

High-Precision Performance Estimation for the Design Space Exploration of Dynamic Dataflow Programs

Endri Bezati, Simone Casale Brunet, Marco Mattavelli, Malgorzata Maria Michalska

The implementation and optimization of dynamic dataflow programs on multi/many-core platforms require solving a very difficult problem: how to partition and schedule the processing elements and dimension their interconnecting buffers according to given optimization functions in terms of throughput, memory usage, and energy consumption. This problem is NP-hard even for two cores. Thus, finding a close-to-optimal solution consists of exploring the design space by appropriate heuristics identifying those design points that maximize or minimize the desired (multiple) objective functions subject to a set of constraints. In general, exploring the design space efficiently is a challenging task due to the massive number of admissible design points. Efficient estimation methodologies are necessary to support an effective search of the design space by reducing to a minimum the cost and the number of measurements on the physical platform. This paper presents a new methodology that provides high-precision estimations of dynamic dataflow programs performances on multi/many-core platforms for any set of design configurations. The estimations rely on the execution trace post-processing obtained by a single execution of the program. The paper describes the estimation methodology, implementation tools, and the information that is obtained from many/multi-core dataflow executions and used to drive the optimization heuristics.

2018

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

Efficient Dynamic Optimisation Heuristics for Dataflow Pipelines

Endri Bezati, Simone Casale Brunet, Marco Mattavelli

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.

IEEE2018

High-level synthesis of dataflow programs for heterogeneous platforms

Endri Bezati

EPFL2015