Abstract
In this paper, we describe an automatic synthesis procedure that distributes synchronous programs on a set of desynchronized processing elements. Our distribution procedure consists of three steps: First, we translate the given synchronous program to synchronous guarded actions. Second, we analyze their data dependencies and represent them in a so-called action dependency graph (ADG). Third, the ADG is subsequently partitioned into of sub-graphs where cuts can be made horizontal (for a pipelined execution) or vertical (for a concurrent execution). Finally, we generate for each sub-graph a corresponding component and automatically synthesize a communication infrastructure between these components.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baudisch, D., Brandt, J., Schneider, K.: Multithreaded code from synchronous programs: Extracting independent threads for OpenMP. In: Design, Automation and Test in Europe (DATE), Dresden, Germany. EDA Consortium (2010)
Baudisch, D., Brandt, J., Schneider, K.: Multithreaded code from synchronous programs: Generating software pipelines for OpenMP. In: Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen (MBMV), Dresden, Germany (2010)
Benveniste, A., Caspi, P., Edwards, S., Halbwachs, N., Le Guernic, P., de Simone, R.: The synchronous languages twelve years later. Proceedings of the IEEE 91(1), 64–83 (2003)
Berry, G.: A hardware implementation of pure Esterel. Sadhana 17(1), 95–130 (1992)
Berry, G.: The foundations of Esterel. In: Plotkin, G., Stirling, C., Tofte, M. (eds.) Proof, Language and Interaction: Essays in Honour of Robin Milner, MIT Press, Cambridge (1998)
Berry, G.: The constructive semantics of pure Esterel (July 1999), http://www-sop.inria.fr/esterel.org/
Boldt, M., Traulsen, C., von Hanxleden, R.: Compilation and worst-case reaction time analysis for multithreaded Esterel processing. EURASIP Journal on Embedded Systems, Article ID 594129 (2008)
Brandt, J., Schneider, K.: Separate compilation for synchronous programs. In: Falk, H. (ed.) Software and Compilers for Embedded Systems (SCOPES). ACM International Conference Proceeding Series, vol. 320, pp. 1–10. ACM, New York (2009)
Brzozowski, J.A., Seger, C.-J.H.: Asynchronous Circuits. Springer, Heidelberg (1995)
Carloni, L.P.: The role of back-pressure in implementing latency-insensitive systems. Electronic Notes in Theoretical Computer Science (ENTCS) 146(2), 61–80 (2006)
Carloni, L.P., McMillan, K.L., Sangiovanni-Vincentelli, A.L.: Latency insensitive protocols. In: Halbwachs, N., Peled, D.A. (eds.) CAV 1999. LNCS, vol. 1633, pp. 123–133. Springer, Heidelberg (1999)
Carloni, L.P., McMillan, K.L., Sangiovanni-Vincentelli, A.L.: Theory of latency-insensitive design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 20(9), 1059–1076 (2001)
Carmona, J., Cortadella, J., Kishinevsky, M., Taubin, A.: Elastic circuits. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems 28(10), 1437–1455 (2009)
Caspi, P., Girault, A., Pilaud, D.: Automatic distribution of reactive systems for asynchronous networks of processors. IEEE Transactions on Software Engineering 25(3), 416–427 (1999)
Casu, M.R., Macchiarulo, L.: A new approach to latency insensitive design. In: Design Automation Conference (DAC), San Diego, CA, USA, pp. 576–581. ACM, New York (2004)
Chandy, K.M., Misra, J.: Parallel Program Design. Addison Wesley, Austin (1989)
Cortadella, J., Kishinevsky, M., Grundmann, B.: SELF: Specification and design of synchronous elastic circuits. In: International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, TAU (2006)
Cortadella, J., Kishinevsky, M., Grundmann, B.: Synthesis of synchronous elastic architectures. In: Design Automation Conference (DAC), San Francisco, CA, USA, pp. 657–662. ACM, New York (2006)
Dill, D.L.: The Murphi verification system. In: Alur, R., Henzinger, T.A. (eds.) CAV 1996. LNCS, vol. 1102, pp. 390–393. Springer, Heidelberg (1996)
Girault, A., Nicollin, X.: Clock-driven automatic distribution of Lustre programs. In: Alur, R., Lee, I. (eds.) EMSOFT 2003. LNCS, vol. 2855, pp. 206–222. Springer, Heidelberg (2003)
Halbwachs, N.: Synchronous programming of reactive systems. Kluwer, Dordrecht (1993)
Halbwachs, N.: A synchronous language at work: the story of Lustre. In: International Conference on Formal Methods and Models for Co-Design (MEMOCODE), Verona, Italy, pp. 3–11. IEEE Computer Society, Los Alamitos (2005)
Järvinen, H., Kurki-Suonio, R.: The DisCo language and temporal logic of actions. Technical Report 11, Tampere University of Technology, Software Systems Laboratory (1990)
Krstic, S., Cortadella, J., Kishinevsky, M., O’Leary, J.: Synchronous elastic networks. In: Gupta, A., Manolios, P. (eds.) Formal Methods in Computer-Aided Design (FMCAD), San Jose, California, USA, pp. 19–30. IEEE Computer Society Press, Los Alamitos (2006)
Lamport, L. The temporal logic of actions. Technical Report 79, Digital Equipment Cooperation (1991)
Logothetis, G., Schneider, K.: Exact high level WCET analysis of synchronous programs by symbolic state space exploration. In: Design, Automation and Test in Europe (DATE), Munich, Germany, pp. 10196–10203. IEEE Computer Society, Los Alamitos (2003)
Rocheteau, F., Halbwachs, N.: Pollux, a Lustr-based hardware design environment. In: Quinton, P., Robert, Y. (eds.) Conference on Algorithms and Parallel VLSI Architectures II, Chateau de Bonas (1991)
Schneider, K.: Embedding imperative synchronous languages in interactive theorem provers. In: Conference on Application of Concurrency to System Design (ACSD), Newcastle upon Tyne, UK, pp. 143–154. IEEE Computer Society, Los Alamitos (2001)
Schneider, K.: Proving the equivalence of microstep and macrostep semantics. In: Carreño, V.A., Muñoz, C.A., Tahar, S. (eds.) TPHOLs 2002. LNCS, vol. 2410, pp. 314–331. Springer, Heidelberg (2002)
Schneider, K.: The synchronous programming language Quartz. Internal Report 375, Department of Computer Science, University of Kaiserslautern, Kaiserslautern, Germany (2009)
Schneider, K., Brandt, J.: Performing causality analysis by bounded model checking. In: Conference on Application of Concurrency to System Design (ACSD), Xi’an, China, pp. 78–87. IEEE Computer Society, Los Alamitos (2008)
Schneider, K., Brandt, J., Schuele, T.: Causality analysis of synchronous programs with delayed actions. In: Compilers, Architecture, and Synthesis for Embedded Systems (CASES), Washington, DC, USA, pp. 179–189. ACM, New York (2004)
Schneider, K., Brandt, J., Schuele, T.: A verified compiler for synchronous programs with local declarations. Electronic Notes in Theoretical Computer Science (ENTCS) 153(4), 71–97 (2006)
Schneider, K., Brandt, J., Schuele, T., Tuerk, T.: Improving constructiveness in code generators. In: Synchronous Languages, Applications, and Programming (SLAP), Edinburgh, Scotland, UK, pp. 1–19 (2005)
Schneider, K., Brandt, J., Schuele, T., Tuerk, T.: Maximal causality analysis. In: Desel, J., Watanabe, Y. (eds.) Application of Concurrency to System Design (ACSD), St. Malo, France, pp. 106–115. IEEE Computer Society, Los Alamitos (2005)
Shiple, T.R.: Formal Analysis of Synchronous Circuits. PhD thesis, University of California at Berkeley, Berkeley, CA, USA (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 IFIP
About this paper
Cite this paper
Baudisch, D., Brandt, J., Schneider, K. (2010). Dependency-Driven Distribution of Synchronous Programs. In: Hinchey, M., et al. Distributed, Parallel and Biologically Inspired Systems. DIPES BICC 2010 2010. IFIP Advances in Information and Communication Technology, vol 329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15234-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-15234-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15233-7
Online ISBN: 978-3-642-15234-4
eBook Packages: Computer ScienceComputer Science (R0)