Multi-threaded code generation from Signal program to OpenMP

Abstract

The use of multi-core processors will become a trend in safety critical systems. For safe execution of multithreaded code, automatic code generation from formal specification is a desirable method. Signal, a synchronous language dedicated for the functional description of safety critical systems, provides soundness semantics for deterministic concurrency. Although sequential code generation of Signal has been implemented in Polychrony compiler, deterministic multi-threaded code generation strategy is still far from mature. Moreover, existing code generation methods use certain multi-thread library, which limits the cross platform executions. OpenMP is an application program interface (API) standard for parallel programming, supported by several mainstream compilers from different platforms. This paper presents a methodology translating Signal program to OpenMP-based multi-threaded C code. First, the intermediate representation of the core syntax of Signal using synchronous guarded actions is defined. Then, according to the compositional semantics of Signal equations, the Signal program is synthesized to dependency graph (DG). After parallel tasks are extracted from dependency graph, the Signal program can be finally translated into OpenMP-based C code which can be executed on multiple platforms.

Keywords

multi-thread / synchronous language / Signal / code generation / OpenMP

References

[1] IEEE POSIX standardization authority. http://standards.ieee.org/regauth/posix/

[2] Microsoft windows threads. http://msdn.microsoft.com/

[3] MPI: A message-passing interface standard version 3.0. http://www.mpi-forum.org/docs/mpi-3.0/mpi30-report.pdf

[4] The OpenMP API specification for parallel programming. http://openmp.org/wp/

[5] Intel thread building blocks. http://www.threadingbuildingblocks.org/

[6] Lee E A. The problem with threads. Computer, 2006, 39(5): 33−42

[7] Benveniste A,Berry G. The synchronous approach to reactive and realtime systems. Proceedings of the IEEE, 1991, 79(9): 1270−1282

[8] Benveniste A, Caspi P, Edwards S A, Halbwachs N, Le Guernic P, De Simone R. . The synchronous languages 12 years later. Proceedings of the IEEE, 2003, 91(1): 64−83

[9] Berry G, Gonthier G. The esterel synchronous programming language: design, semantics, implementation. Science of Computer Programming, 1992, 19(2): 87−152

[10] Halbwachs N, Caspi P, Raymond P, Pilaud D. The synchronous data flow programming language lustre. Proceedings of the IEEE, 1991, 79(9): 1305−1320

[11] Le Guernic P, Gautier T, Le Borgne M, Le Maire C. . Programming realtime applications with signal. Proceedings of the IEEE, 1991, 79(9): 1321−1336

[12] Le Guernic P, Talpin J P, Le Lann J C. Polychrony for system design. Journal of Circuits, Systems, and Computers, 2003, 12(3): 261−303

[13] Potop-Butucaru D, Caillaud B, Benveniste A. Concurrency in synchronous systems. Formal Methods in System Design, 2006, 28(2): 111−130

[14] Besnard L, Gautier T, Talpin J P. Code generation strategies in the polychrony environment. http://hal.inria.fr/docs/00/37/24/12/PDF/RR-6894.pdf

[15] Besnard L, Gautier T, Le Guernic P, Talpin J P. Compilation of polychromous data flow equations. In: Synthesis of Embedded Software, 1−40. Springer, 2010

[16] Talpin J P, Ouy J, Gautier T, Besnard L, Le Guernic P. Compositional design of isochronous systems. Science of Computer Programming, 2012, 77(2): 113−128

[17] Benveniste A, Caillaud B, Le Guernic P. Compositionality in dataflow synchronous languages: specification and distributed code generation. Information and Computation, 2000, 163(1): 125−171

[18] Jose B A, Shukla S K, Patel H D, Talpin J P. On the deterministic multithreaded software synthesis from polychronous specifications. In: Proceedings of the 6th ACM/IEEE International Conference on Formal Methods and Models for Co-Design. 2008, 129−138

[19] Maffeïs O, Le Guernic P. Combining dependability with architectural adaptability by means of the signal language. In: Static Analysis, 99−110. Springer, 1993

[20] Potop-Butucaru D, Sorel Y, Simone d R, Talpin J P. From concurrent multi-clock programs to deterministic asynchronous implementations. Fundamenta Informaticae, 2011, 108(1): 91−118

[21] Papailiopoulou V, Potop-Butucaru D, Sorel Y, Simone d R, Besnard L, Talpin J. From design-time concurrency to effective implementation parallelism: The multi-clock reactive case. In: Proceedings of the 2011 Electronic System Level Synthesis Conference. 2011, 1−6

[22] Baudisch D, Brandt J, Schneider K. Multithreaded code from synchronous programs: extracting independent threads for openmp. In: Proceedings of the 2010 Conference on Design, Automation, and Test in Europe. 2010, 949−952

[23] Besnard L, Gautier T, Le Guernic P. Signal v4-Inria version: reference manual, 2008

[24] Gamatie A. Designing embedded systems with the signal programming language. Springer, 2010

[25] RT-builder, geensys.

[26] Polychrony. http://www.irisa.fr/espresso/Polychrony/

RIGHTS & PERMISSIONS

2013 Higher Education Press and Springer-Verlag Berlin Heidelberg