Synthesis of Parallel Software from Heterogeneous Dataflow Models
Abstract
Dataflow process networks (DPNs) are intrinsically data-driven, i.e., node actions are not synchronized among each other and may fire whenever sufficient input operands arrived at a node. While the general model of computation (MoC) of DPNs does not impose further restrictions, many different subclasses of DPNs representing different dataflow MoCs have been considered over time. These classes mainly differ in the kinds of behaviors of the processes. A DPN may be heterogeneous in that different processes in the network belong to different classes of DPNs. A heterogeneous DPN can therefore be effectively used to model and to implement different components of a system with different kinds of processes and, therefore, different dataflow MoCs. This paper presents a model-based design based on different dataflow MoCs including their heterogeneous combinations. In particular, it covers the automatic software synthesis of systems from DPN models. The main objective is to validate, evaluate and compare the artifacts exhibited by different dataflow MoCs at the implementation level of systems under the supervision of a common design tool. Moreover, this work also offers an efficient synthesis method that targets and exploits heterogeneity in DPNs by generating implementations based on the kinds of behaviors of the processes. The proposed synthesis method provides a tool chain including different specialized code generators for specific dataflow MoCs, and a runtime system that finally maps models using a combination of different dataflow MoCs on cross-vendor target hardware.
References
[1]
Bai Y. Model-based design of embedded systems by desynchronization. PhD thesis, Department of Computer Science, University of Kaiserslautern, Germany, 2016. PhD.
[2]
Bai Y, Rafique O and Schneider K. A model-based design flow for asynchronous implementations from synchronous specifications. In: Design, automation and test in Europe (DATE). Grenoble, France, 2021. IEEE Computer Society, pp. 862–7.
[3]
Bai Y, Schneider K, Bhardwaj N, Katti B and Shazadi T. From clock-driven to data-driven models. In: Formal methods and models for codesign. Lausanne, Switzerland, 2014. IEEE Computer Society, pp. 32–41.
[4]
Benveniste A, Caillaud B, and Le Guernic P Baeten JCM and Mauw S From synchrony to asynchrony Concurrency theory (CONCUR) 1999 Eindhoven Springer 162-177
[5]
Benveniste A, Caspi P, Edwards S, Halbwachs N, Le Guernic P, and de Simone R The synchronous languages twelve years later Proc IEEE 2003 91 1 64-83
[6]
Berry G and Gonthier G The Esterel synchronous programming language: design, semantics, implementation Sci Comput Program 1992 19 2 87-152
[7]
Bhattacharyya SS, Eker J, Janneck JW, Lucarz C, Mattavelli M, and Raulet M Overview of the MPEG reconfigurable video coding framework J Signal Process Syst 2011 63 2 251-263
[8]
Boutellier J, Wu J, Huttunen H, and Bhattacharyya SS PRUNE: dynamic and decidable dataflow for signal processing on heterogeneous platforms IEEE Trans Signal Process 2018 66 3 654-665
[9]
Brooks CX, Lee EA, and Tripakis S Givargis T and Donlin A Exploring models of computation with Ptolemy II International conference on hardware/software codesign and system synthesis (CODES+ISSS) 2010 Scottsdale ACM 331-332
[10]
Buck JT. Scheduling dynamic dataflow graphs with bounded memory using the token flow model. PhD thesis, University of California, Berkeley, California, USA, 1993. PhD.
[11]
Dennis JB Robinet B First version of a data-flow procedure language Programming symposium 1974 Paris Springer 362-376
[12]
Didier K, Potop-Butucaru D, Iooss G, Cohen A, Souyris J, Baufreton P, and Graillat A Correct-by-construction parallelization of hard real-time avionics applications on off-the-shelf predictable hardware ACM Trans Archit Code Optim 2019 16 3 24:1-24:27
[13]
Eker J and Janneck JW. CAL language report. ERL Technical Memo UCB/ERL M03/48, EECS Department, University of California at Berkeley, Berkeley, California, USA, 2003.
[14]
Eker J, Janneck JW, Lee EA, Liu J, Liu X, Ludvig J, Neuendorffer S, Sachs S, and Xiong Y Taming heterogeneity—the Ptolemy approach Proc IEEE 2003 91 1 127-144
[15]
Engels M, Bilsen G, Lauwereins R and Peperstraete J. Cyclo-static dataflow. In: International conference on acoustics, speech and signal processing (ICASSP). Detroit, Michigan, USA, 1995. IEEE Computer Society, pp. 3255–8.
[16]
Falk J, Haubelt C, Teich J, and Zebelein C SysteMoC: a data-flow programming language for codesign 2017 Netherlands Springer 59-97
[17]
Faustini AA Nielsen M and Schmidt EM An operational semantics for pure data flow International colloquium on automata 1982 Århus Springer 212-224
[18]
Geilen M and Basten T Degano P Requirements on the execution of Kahn process networks European symposium on programming (ESOP) 2003 Warsaw Springer 319-334
[19]
Girault A. A survey of automatic distribution method for synchronous programs. In: Synchronous languages, applications, and programming (SLAP). Edinburgh, Scotland, UK, 2005, pp. 1–20. (unpublished workshop proceedings)
[20]
Haubelt C, Falk J, Keinert J, Schlichter T, Streubühr M, Deyhle A, Hadert A, and Teich J A SystemC-based design methodology for digital signal processing systems EURASIP J Embed Syst 2007 2007 1 15-15
[21]
Kahn G and MacQueen DB. Coroutines and networks of parallel processes. In: Gilchrist B, editor, Information processing. North-Holland, 1977; pp. 993–8.
[22]
Kahn G Rosenfeld JL The semantics of a simple language for parallel programming Information processing 1974 Stockholm North-Holland 471-475
[23]
Karp RM and Miller RE Properties of a model for parallel computations: determinacy, termination, queueing SIAM J Appl Math (SIAP) 1966 14 6 1390-1411
[24]
Kuhn T, Forster T, Braun T and Gotzhein R. FERAL—framework for simulator coupling on requirements and architecture level. In: Formal methods and models for codesign. Portland, OR, USA, 2013; pp. 11–22. IEEE Computer Society.
[25]
Lee JH, Nigania N, Kim H, Patel K and Kim H. OpenCL performance evaluation on modern multicore CPUs. Sci Programm. 2015; pp. 859491:1–859491:20
[26]
Lee EA and Messerschmitt DG Synchronous data flow Proc IEEE 1987 75 9 1235-1245
[27]
Lee EA and Parks T Dataflow process networks Proc IEEE 1995 83 5 773-801
[28]
Lund W, Kanur S, Ersfolk J, Tsiopoulos L, Lilius J, Haldin J and Falk U. Execution of dataflow process networks on OpenCL platforms. In: Euromicro international conference on parallel, distributed, and network-based processing. Turku, Finland, 2015; pp. 618–25. IEEE Computer Society.
[29]
Parks TM. Bounded scheduling of process networks. PhD thesis, Princeton University, 1995. PhD.
[30]
Parks TM, Pino JL and Lee EA. A comparison of synchronous and cyclo-static dataflow. In: Asilomar conference on signals, systems and computers. Washington, District of Columbia, USA, 1995; pp. 204–210. IEEE Computer Society.
[31]
Potop-Butucaru D, Caillaud B, and Benveniste A Concurrency in synchronous systems Formal Methods Syst Design (FMSD) 2006 28 2 111-130
[32]
Rafique O and Schneider K. A model-based synthesis framework for the execution of dynamic dataflow actors. In: International conference on internet of things embedded systems and communications. Hammamet, Tunisia, 2018. IEEE Computer Society.
[33]
Rafique O and Schneider K. Employing OpenCL as a standard hardware abstraction in a distributed embedded system: a case study. In: Conference on cyber-physical systems and internet-of-things. Budva, Montenegro, 2020; pp. 1–7. IEEE Computer Society.
[34]
Rafique O and Schneider K. Evaluating OpenCL as a standard hardware abstraction for a model-based synthesis framework: a case study. In: International conference on model driven engineering and software development. Prague, Czech Republic, 2019.
[35]
Rafique O and Schneider K. Integrating Kahn process networks as a model of computation in an extendable model-based design framework. In: International conference on model driven engineering and software development. SCITEPRESS, 2021.
[36]
Rafique O and Schneider K. SHeD: a framework for automatic software synthesis of heterogeneous dataflow process networks. In: Euromicro conference on digital system design (DSD), Portoroz̆, Slovenia, 2020. IEEE Computer Society.
[37]
Rafique O, Gesell M, and Schneider K Corporaal H and Stuijk S Generating hardware specific code at different abstraction levels using Averest International workshop on software and compilers for embedded systems (SCOPES) 2013 Sankt Goar ACM 90-92
[38]
Rafique O, Bai Y, Schneider K and Yan G. Efficient implementation of heterogeneous dataflow models using synchronous IO patterns. In: Euromicro conference on digital system design (DSD). Palermo, Sicily, Italy, 2021; pp. 82–9. IEEE Computer Society.
[39]
Rafique O, Bai Y, Schneider K and Yan G. Synthesis of heterogeneous dataflow models from synchronous specifications. In: Computers, software, and applications conference (COMPSAC). Virtual Conference, 2021. IEEE Computer Society.
[40]
Rafique O, Gesell M and Schneider K. Learning various aspects of a distributed real-time automotive embedded system. In: Marwedel P, Jackson J and Ricks K (eds) Workshop on embedded and cyber-physical systems education (WESE), Montreal, Canada, 2013. ACM.
[41]
Rafique O, Schneider K. Automatic software synthesis of static and dynamic dataflow process networks. In: International workshop on interplay of model-driven and component-based software engineering. Munich, Germany; 2019.
[42]
Sander I, Jantsch A, and Attarzadeh-Niaki S-H Ha S and Teich J ForSyDe: system design using a functional language and models of computation Handbook of hardware/software codesign, chapter 4 2017 Berlin Springer
[43]
Schneider K. The synchronous programming language Quartz. Internal Report 375, Department of Computer Science, University of Kaiserslautern, Kaiserslautern, Germany, 2009.
[44]
Schor L, Bacivarov I, Rai D, Yang H, Kang S-H, and Thiele L Jerraya A, Carloni L, Mooney V, and Rabbah R Scenario-based design flow for mapping streaming applications onto on-chip many-core systems Compilers, architecture, and synthesis for embedded systems (CASES) 2012 Tampere ACM 71-80
[45]
Schor L, Tretter A, Scherer T and Thiele L. Exploiting the parallelism of heterogeneous systems using dataflow graphs on top of OpenCL. In: IEEE symposium on embedded systems for real-time multimedia. IEEE Computer Society, 2013; pp. 41–50.
[46]
Shen J, Fang J, Sips H, and Varbanescu AL An application-centric evaluation of OpenCL on multi-core CPUs Parallel Comput 2013 39 12 834-850
[47]
Stone JE, Gohara D, and Shi G OpenCL: a parallel programming standard for heterogeneous computing systems Comput Sci Eng 2010 12 3 66-73
[48]
Stuijk S, Geilen M, Theelen BD, and Basten T Carro L and Pimentel AD Scenario-aware dataflow: modeling, analysis and implementation of dynamic applications International conference on embedded computer systems: architectures, modeling, and simulation (SAMOS) 2011 Samos IEEE Computer Society 404-411
[49]
Stuijk S, Geilen M and Basten T. SDF3: SDF for free. In: Application of concurrency to system design (ACSD). Turku, Finland, 2006; pp. 276–8. IEEE Computer Society.
[50]
Tarjan R Depth first search and linear graph algorithms SIAM J Comput (SICOMP) 1972 1 2 146-160
Recommendations
Dataflow Graph Partitioning for Area-Efficient High-Level Synthesis with Systems Perspective
Area efficiency in datapath synthesis is a widely accepted goal of high-level synthesis. Applications represented by their dataflow graphs are synthesized using resource sharing principles to reduce the area. However, existing resource sharing ...
Hardware and software synthesis of heterogeneous systems from dataflow programs
Special issue on ESL Design MethodologyThe new generation of multicore processors and reconfigurable hardware platforms provides a dramatic increase of the available parallelism and processing capabilities. However, one obstacle for exploiting all the promises of such platforms is deeply ...
A comparison of synchronous and cycle-static dataflow
ASILOMAR '95: Proceedings of the 29th Asilomar Conference on Signals, Systems and Computers (2-Volume Set)We compare synchronous dataflow (SDF) and cyclo-static dataflow (CSDF), which are each special cases of a model of computation we call dataflow process networks. In SDF actors have static firing rules: they consume and produce a fixed number of data ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s) 2022.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 26 April 2022
Accepted: 21 March 2022
Received: 02 October 2021
Author Tags
Qualifiers
- Research-article
Funding Sources
- Technische Universität Kaiserslautern (3142)
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Jan 2025