From Concurrent Multi-clock Programs to Deterministic Asynchronous Implementations

• Autorzy: Potop-Butucaru D. , Sorel Y. , Simone R. de , Talpin J.-P.
• Języki publikacji: EN

Abstrakty

EN

We propose a generalmethod to characterize and synthesize correctness-preserving asynchronous wrappers for synchronous processes on a globally asynchronous locally synchronous (GALS) architecture. While a synchronous process may rely on the absence of a signal to trigger a reaction, sensing absence in an asynchronous environment may be unfeasible due to uncontrolled communication latencies. A simple and common solution is to systematically encode and send absence notifications, but it is unduly expensive at run-time. Instead, our approach is based on the theory of weakly endochronous systems, which defines the largest sub-class of synchronous systems where (possibly concurrent) asynchronous evaluation is faithful to the original (synchronous) specification. Our method considers synchronous processes or modules that are specified by synchronization constraints expressed in a high-level multi-clock synchronous reactive formalism. The algorithm uses a compact representation of the abstract synchronization configurations of the analyzed process and determines a minimal set of synchronization patterns generating by union all its possible reactions. A specification is weakly endochronous if and only if these generators do not need explicit absence information. In this case, the set of generators can directly be used to synthesize the concurrent asynchronous multi-rate wrapper of the process.

Słowa kluczowe

EN

endochrony; synchrony; multi-clock; asynchronous implementation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 108, nr 1/2
• Strony: 91--118
• Opis fizyczny: Bibliogr. 22 poz., tab.

Twórcy

autor

Potop-Butucaru D.

autor

Sorel Y.

autor

Simone R. de

autor

Talpin J.-P.

• INRIA Rocquencourt, Domaine de Voluceau, BP105, 78153 Le Chesnay Cedex, France,

Bibliografia

• [1] Amagbégnon, P., Besnard, L., Guernic, P. L.: Implementation of the data-flow synchronous language Signal, Proceedings PLDI'95, La Jolla, CA, USA, June 1995.
• [2] Benveniste, A., Caillaud, B., Guernic, P. L.: Compositionality in Dataflow Synchronous Languages: Specification and Distributed Code Generation, Information and Computation, 163, 2000, 125 - 171.
• [3] Benveniste, A., Caspi, P., Edwards, S. A., Halbwachs, N., Guernic, P. L., de Simone, R.: The Synchronous Languages 12 Years Later, Proceedings of the IEEE, 91(1), January 2003, 64-83.
• [4] Berry, G., Gonthier, G.: The Esterel synchronous programming language: Design, semantics, implementation, Science of Computer Programming, 19(2), 1992, 87-152.
• [5] Carloni, L., McMillan, K., Sangiovanni-Vincentelli, A.: Theory of Latency-Insensitive Design, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20(9), Sep 2001, 18.
• [6] Caspi, P., Girault, A., Pilaud, D.: Automatic Distribution of Reactive Systems for Asynchronous Networks of Processors, IEEE Transactions on Software Engineering, 25(3), May/June 1999, 416-427.
• [7] Chapiro, D. M.: Globally asynchronous, locally synchronous systems, Ph.D. Thesis, Stanford University, Department of Computer Science, 1984.
• [8] Cortadella, J., Kondratyev, A., Lavagno, L., Sotiriou, C.: Desynchronization: Synthesis of Asynchronous Circuits from Synchronous Specifications, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(10), October 2006, 1904-1921.
• [9] Dasgupta, S., Potop-Butucaru, D., Caillaud, B., Yakovlev, A.: Moving from Weakly Endochronous Systems to Delay-Insensitive Circuits, Electronic Notes in Theoretical Computer Science, 146(2), 2006, 81 - 103, Proceedings of the Second Workshop on Globally Asynchronous, Locally Synchronous Design (FMGALS 2005).
• [10] Grandpierre, T., Sorel, Y.: From Algorithm and Architecture Specification to Automatic Generation of Distributed Real-Time Executives: a Seamless Flow of Graphs Transformations, Proceedings of First ACM and IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE'03, Mont Saint-Michel, France, June 2003.
• [11] Guernic, P. L., Talpin, J.-P., Lann, J.-C. L.: Polychrony for system design, Journal for Circuits, Systems and Computers, April 2003, Special Issue on Application Specific Hardware Design.
• [12] Kahn, G.: The semantics of a simple language for parallel programming, Information Processing '74 (J. Rosenfeld, Ed.), North Holland, 1974.
• [13] Keller, R.: A fundamental theorem of asynchronous parallel computation, Lecture Notes in Computer Science, 24, 1975, 103-112.
• [14] Mazurkiewicz, A.: Concurrent Program Schemes and their Interpretations, Technical report, DAIMI, Arhus University, 1977.
• [15] Milner, R.: Communication and Concurrency, Prentice Hall, 1989.
• [16] Nebut, M.: Specification and Analysis of Synchronous Reactions, Formal Aspects of Computing, 16(3), august 2004, 263-291.
• [17] Potop-Butucaru, D., Caillaud, B.: Correct-by-construction asynchronous implementation of modular synchronous specifications, Proccedings ACSD'05, St. Malo, France, June 2005.
• [18] Potop-Butucaru, D., Caillaud, B., Benveniste, A.: Concurrency in synchronous systems, Formal Methods in System Design, 28(2),March 2006, 111-130.
• [19] Potop-Butucaru, D., de Simone, R., Sorel, Y.: Necessary and sufficient conditions for deterministic desynchronization, Proceedings EMSOFT'07, Vienna, Austria, 2007.
• [20] Potop-Butucaru, D., de Simone, R., Sorel, Y.: deterministic execution of synchronous programs in an asynchronous environment. A compositional necessary and sufficient condition, Research Report RR-6656, INRIA, 2008.
• [21] Singh, M., Theobald, M.: Generalized Latency-Insensitive Systems for Single-Clock and Multi-Clock Architectures, Proceedings DATE'04, Paris, France, 2004.
• [22] Vijayaraghavan, M., Arvind: Bounded Dataflow Networks and Latency-Insensitive Circuits, Proceedings Memocode'09, Nice, France, 2009.