Modular static scheduling of synchronous data-flow networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Modular static scheduling of synchronous data-flow networks: an efficient symbolic representation

Full text

Pdf (552 KB)

Source

International Conference on Compilers, Architecture and Synthesis for Embedded Systems archive
Proceedings of the seventh ACM international conference on Embedded software table of contents

Grenoble, France

SESSION: Implementation issues table of contents

Pages 215-224

Year of Publication: 2009

ISBN:978-1-60558-627-4

Authors

Marc Pouzet	LRI, Univ. Paris-Sud 11, Orsay, France
Pascal Raymond	VERIMAG-CNRS, Grenoble, France

Sponsors

ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 12, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629335.1629365 What is a DOI?

ABSTRACT

This paper addresses the question of producing modular sequential imperative code from synchronous data-flow networks. Precisely, given a system with several input and output flows, how to decompose it into a minimal number of sub-systems executed atomically and statically scheduled without restricting possible feedback loops between input and output?

Though this question has been identified by Raymond in the early years of Lustre, it has almost been left aside until the recent work of Lublinerman, Szegedy and Tripakis. The problem is proven to be intractable, in the sense that it belongs to the family of optimization problems where the corresponding decision problem -- there exists a solution with size c -- is NP-complete. Then, the authors derive an iterative algorithm looking for solutions for c = 1, 2, ... where each step is encoded as a SAT problem.

Despite the apparent intractability of the problem, our experience is that real programs do not exhibit such a complexity. Based on earlier work by Raymond, this paper presents a new symbolic encoding of the problem in terms of input/output relations. This encoding simplifies the problem, in the sense that it rejects solutions, while keeping all the optimal ones. It allows, in polynomial time, (1) to identify nodes for which several schedules are feasible and thus are possible sources of combinational explosion; (2) to obtain solutions which in some cases are already optimal; (3) otherwise, to get a non trivial lower bound for c to start an iterative combinational search.

The solution applies to a large class of block-diagram formalisms based on atomic computations and a delay operator, ranging from synchronous languages such as Lustre or Scade to modeling tools such as Simulink.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Benveniste, P. LeGuernic, and Ch. Jacquemot. Synchronous programming with events and relations: the SIGNAL language and its semantics. Science of Computer Programming, 16:103--149, 1991.
	2	Albert Benveniste, Paul Le Guernic, and Pascal Aubry. Compositionality in dataflow synchronous languages: Specification & code generation. Technical Report R3310, INRIA, November 1997.
	3	Darek Biernacki, Jean-Louis Colaco, Gregoire Hamon, and Marc Pouzet. Clock-directed Modular Code Generation of Synchronous Data-flow Languages. In ACM International Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES), Tucson, Arizona, June 2008. Extended version of [4].
	4	Darek Biernacki, Jean-Louis Colaco, and Marc Pouzet. Clock-directed Modular Compilation from Synchronous Block-diagrams. In Workshop on Automatic Program Generation for Embedded Systems (APGES), Salzburg, Austria, october 2007. Embedded System Week.
	5	M. R. Garey and D. S. Johnson. Computers and Intractability - A guide to the Theory of NP-completeness. Freeman, New-York, 1979.
	6	Georges Gonthier. Semantiques et modeles d'execution des langages reactifs synchrones. PhD thesis, Universite Paris VI, Paris, 1988.
	7	N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. The synchronous dataflow programming language lustre. Proceedings of the IEEE, 79(9):1305--1320, September 1991.
	8	N. Halbwachs, P. Raymond, and C. Ratel. Generating efficient code from data-flow programs. In Third International Symposium on Programming Language Implementation and Logic Programming, Passau (Germany), August 1991.
	9	Gilles Kahn. The semantics of a simple language for parallel programming. In IFIP 74 Congress. North Holland, Amsterdam, 1974.
	10	E. A. Lee and D. G. Messerschmitt. Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans. on Computers, 36(2), 1987.
	11	R. Lublinerman, C. Szegedy, and S. Tripakis. Modular Code Generation from Synchronous Block Diagrams -- Modularity vs. Code Size. In ACM Principles of Programming Languages (POPL), 2009.
	12	R. Lublinerman and S. Tripakis. Modularity vs. reusability: Code generation from synchronous block diagrams. In Design, Automation and Test in Europe (DATE'08), 2008.
	13	Pascal Raymond. Compilation separee de programmes lustre. Technical report, Projet SPECTRE, IMAG, juillet 1988. url="http://www-verimag.imag.fr/SYNCHRONE/publis/spectre-L5.pdf".