Dataflow Programming for Systems Design Space Exploration for Multicore Platforms

Nowadays processing systems are asked to support increasing complex and demanding high-performance applications, especially in the signal processing and video processing domains. The design of these systems are becoming extremely challenging because of several factors. Among them the most relevant are: The advent of the parallel era The sequential general purpose processor era during which performance increased more than two-fold every year, is definitely over. There has been no further increase in leading edge processor performance for over five years now and all projects aimed at breaking the 4 GHz barrier have been canceled by the major processor manufacturers. So as to continue increasing the computing power of computer systems, manufacturers have to use several slower processing cores, while trying to minimize the power consumption. Sequential reference softwares are no longer adapted Up to now, sequential software have proven to be the winning approaches for exploiting the potential of each new generation of sequential processors. But the advent of the new parallel era changes the way systems are implemented and sequential reference software used as specification base are no longer appropriate starting points for designing complex systems. The increasing demanding functionality and performance In parallel with miniaturization and the necessity to handle severely resource-constrained implementation platforms, the functionality and complexity of large classes of systems continue to increase making them from many respects comparable to ordinary desktop personal computers. A mixture of different types of timing and quality constraints make overall system architecture design, resource allocation and scheduling more important and challenging topics than ever before. Additionally, the market asks companies to build efficient systems while using the minimum of resources as fast as possible. Due to the level of complexity reached by high-demanding digital systems, it is no longer reasonable to handle such systems at low levels of abstraction (e.g. VHDL/Verilog or C/C++). A solution to the problem is to higher the level of abstraction at which the design of such systems is performed. But for raising the level of abstraction, the need for portable parallelism is primordial so as to be able to implement all kind of systems on a wide range of target platforms. Thus, enabling portable parallelism should be a primordial requirement for the development of this level of abstraction and the associated methodology and tools. However, creating a new abstraction layer may incur in the risk of loosing contact with implementation details and accuracy necessary for achieving efficient implementations. This work focuses on tackling such problem by using the CAL data flow language as main abstraction at the basis of the design process. The attempt of solving such challenging problem consists in building an environment for enabling high level design space exploration of complex parallel application for seamless implementation on heterogeneous platforms using CAL. It includes the extraction of metrics (static analysis and profiling) with the intention to use them as a basis for partitioning and scheduling heuristics aiming at finding the most efficient partitions. It also implies developing methodologies for guiding designers in the optimization of the high level specifications. Finally, a holistic approach has been defined in form of a complete design flow starting from CAL specifications down to implementations. Where traditional approaches are faced to traverse, at each iteration of the design flow, all the levels of abstraction for testing a design solution, the use of CAL as an abstraction layer enables designers to separate clearly three domains of concerns that are made orthogonal: functionality, partitioning and implementation. The separation of these domains of concerns eases the design space exploration and leads to an increase in productivity in the design of complex systems. This work leads to the creation of several new design tools: (1) profiling tools which extracts metrics from CAL programs and (2) exploration tools which include partitioning and scheduling heuristics and performance evaluation. These tools have been implemented with the aim of guiding designers in the high level design space exploration of systems in order to achieve efficient implementation. A systematic methodology has been also elaborated and has been tested successfully on a real world applications. Thanks to the metrics extracted from the CAL program, the design bottlenecks of a MPEG-4 SP video decoder have been identified and removed at a high level of abstraction, leading to improvements up to 7 times faster implementation.

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

A virtual model for simulation and design of architectures in MPEG-4 audio and multimedia context

Giorgio Zoia

Research in multimedia for consumer electronics is dominated by the problem of incredibly short times-to-market, that means fast complexity estimations and fast design of new architectures. On one side more and more sophisticated and flexible applications are rapidly developed, on the other side the exponential growth in IC computational power seems to be hardly capable to keep pace with requirements for real-time applications, since their complexity is exponentially growing as well. The processor's performance, often slowed down by bottlenecks in memories and buses, is further reduced by the time wasted in communication among the several application layers. From this problem comes the conception of integrated development frameworks for simulation and design. Tools for simulation and analysis of architectures have appeared from academic and industrial research laboratories above all in the last decade. Many of them are conceived to provide low-level exact simulation of the supported devices, at the price of heavy slowdowns in simulation times and huge sizes of traced data reports. Some others, in the last years, introduced some degrees of approximation in simulations, in order to speed up execution time and to increase the flexibility of the tools to support multi-processors. The resulting more or less abstract models are anyway not suitable to analyze real multimedia-oriented applications, where programs are usually available in some languages including dedicated libraries and meaningful results are only those measured in function of time. On another level, tools for hardware/software codesign or for block-based system design provide more useful results, but to be effective they must rely on rigid cores that may allow only a few degrees of reconfigurability; some very recent tools are conceived to design complex systems by modeling blocks through a high level description language. Conversely, the virtual model and related tool proposed in this dissertation have their roots in an approach to the analysis of complexity that aims to be, as far as possible, platform independent. The method is based on the concepts of abstract classes of operations and simulation in function of the performance time. The work described in this dissertation finds its application field in the world of multimedia, more precisely in multimedia-oriented Audio applications. Media applications are commonly programmed by imperative or object-oriented languages, which are composed by many different statements, operators and above all standard libraries. A careful profiling of typical applications permits to detect fundamental operations and functions and to define a virtual instruction set, grouping more or less similar operators and breaking functions into basic building blocks. The resulting virtual instruction set does not correspond to any actual one but it has as property to be easily mapped on a large number of existing ones. The simulation of an architecture requires then the availability of measures, benchmarks or estimations of at least one member of each abstract class. The number of classes, i.e. the complexity vector, can be adapted in length and detail to the needed degree of precision and to the available set of actual measures and/or benchmarks. The input to the simulation is described by a high-level standardized programming language, the new MPEG-4 Structured Audio Orchestra Language (SAOL); in principle, it may also be the case that the application does not need any translation, if it is already available in this format. Moreover, simulation through a high-level language permits to trace the behavior of the target architecture in function of the internal time of the application itself, result that is fundamental when the related workload is highly variable as in downloadable and/or interactive scenarios. In such cases complexity has always been considered a guess. The new virtual model for analyses of complexity led to two main practical results: the proposed method of simulation has been used to define complexity levels for Structured Audio in the MPEG-4 Standard, and consequently the platform independent analyzer has become the MPEG-4 reference software for MPEG-4 SA Conformance test. a virtual instruction set has been conceived that has permitted the implementation of an efficient Structured Audio decoder, SAINT, based on a virtual interpreted DSP core. The flexibility of the SAINT virtual DSP approach has permitted a fast porting of its execution engine on a superscalar VLIW DSP, making it one of the building blocks of the ThreeDSPACE system, a framework for advanced rendering of 3-D Audio scenes based on MPEG-4 descriptions. The complete tool for simulation of architectures, including a cache simulator, has shown promising results, achieving estimations of the execution time of SAINT with an approximation of the 10% in the mean for a general purpose processor, and of the 20% for a very complex superscalar VLIW processor. Estimated programs have sometimes dynamic excursions of a factor 10 in their complexity along the time axis. In general, the experimental results can be considered in line with those of the most recent, state-of-the-art simulators presented in literature. A limitation of the language adopted to model the applications is that its generality is limited to onedimensional floating-point computation; the most relevant advantage is that simulation in function of the performance time is straightforward and provides the time-dependent results that are fundamental for the optimization of real-time applications. With the tool developed in this PhD work, complex programs can be quickly modeled thanks to SA specific libraries and also quickly analyzed; moreover, the tool can be easily extended to become a tool for automatic generation and configuration of the main building blocks of a system running the application, or the class of applications, under consideration. The proposed model is finally intended as an alternative approach to coordinate two sides; a principal goal of this work was to conceive and specify a systematic analysis method that can be useful to both the software programmer and to the hardware system engineer. The former can benefit of a reconfigurable and dedicated highlevel software tool able to profile programs in a simple and platform independent manner and to easily simulate, with some margins of error, the behavior of a specific platform, existing or virtual; the latter can exploit complexity estimations in an abstract format, with the possibility to study the target application in its several aspects (operations, memory usage, data flows among the different program blocks) and the potentiality to extend these results to an automatic generation of high-level system architectures.

EPFL2001

High Level Extraction of SoC Architectural Information from Generic C Algorithmic Descriptions

Marco Mattavelli, Massimo Ravasi

The complexity of nowadays, algorithms in terms of number of lines of codes and cross-relations among processing algorithms that are activated by specific input signals, goes far beyond what the designer can reasonably grasp from the “pencil & paper” analysis of the (software) specifications. Moreover, depending on the implementation goal different measures and metrics are required at different steps of the implementation methodology or design flow of SoC. The process of extracting the desired measures needs to be supported by appropriate automatic tools, since code rewriting, at each design stage, may result resource consuming and error prone. This paper presents an integrated tool for automatic analysis capable of producing complexity results based on rich and customizable metrics. The tool is based on a C virtual machine that allows extracting from any C program execution the operations and data-flow information, according to the defined metrics. The tool capabilities include the simulation of virtual memory architectures.