More Web Proxy on the site http://driver.im/

research-article

A type system for the automatic distribution of higher-order synchronous dataflow programs

Authors:

Gwenaël Delaval,

Marc PouzetAuthors Info & Claims

LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems

Pages 101 - 110

https://doi.org/10.1145/1375657.1375672

Published: 12 June 2008 Publication History

Abstract

We address the design of distributed systems with synchronous dataflow programming languages. As modular design entails handling both architectural and functional modularity, our first contribution is to extend an existing synchronous dataflow programming language with primitives allowing the description of a distributed architecture and the localization of some expressions onto some processors. We also present a distributed semantics to formalize the distributed execution of synchronous programs. Our second contribution is to provide a type system, in order to infer the localization of non-annotated values by means of type inference and to ensure, at compilation time, the consistency of the distribution. Our third contribution is to provide a type-directed projection operation to obtain automatically, from a centralized typed program, the local program to be executed by each computing resource. The type system as well as the automatic distribution mechanism has been fully implemented in the compiler of an existing synchronous data-flow programming language.

References

[1]

Lucid synchrone v3. www.lri.fr/~pouzet/lucid-synchrone.

[2]

Architecture analysis & design language (AADL). SAE Standard (AS5506), Nov. 2004.

[3]

P. Aubry and P. Le Guernic. On the desynchronization of synchronous applications. In 11th International Conference on Systems Engineering, ICSE'96, Las Vegas, USA, June 1996.

[4]

H. E. Bal, J. G. Steiner, and A. S. Tanenbaum. Programming languages for distributed computing systems. ACM Computing Surveys, 21(3):261--322, 1989.

Digital Library

[5]

A. Benveniste, P. Caspi, S. Edwards, N. Halbwachs, P. L. Guernic, and R. de Simone. The synchronous languages twelve years later. Proc. of the IEEE, Special issue on embedded systems, 91(1):64--83, Jan. 2003.

[6]

B. Caillaud, P. Caspi, A. Girault, and C. Jard. Distributing automata for asynchronous networks of processors. European Journal of Automated Systems, 31(3):503--524, 1997.

[7]

P. Caspi, A. Curic, A. Maignan, C. Sofronis, S. Tripakis, and P. Niebert. From Simulink to Scade/Lustre to TTA: A layered approach for distributed embedded applications. In International Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES'03, San Diego, USA, June 2003. ACM.

Digital Library

[8]

P. Caspi, A. Girault, and D. Pilaud. Automatic distribution of reactive systems for asynchronous networks of processors. IEEE Trans. on Software Engineering, 25(3):416--427, May 1999.

Digital Library

[9]

J.-L. Colaço, A. Girault, G. Hamon, and M. Pouzet. Towards a Higher-order Synchronous Data-flow Language. In ACM Fourth International Conference on Embedded Software (EMSOFT'04), Pisa, Italy, september 2004.

Digital Library

[10]

F. Jondral. Software-defined radio -- basics and evolution to cognitive radio. EURASIP Journal on Wireless Communications and Networking, 3:275--283, 2005.

Digital Library

[11]

G. Kahn. The semantics of a simple language for parallel programming. In J. L. Rosenfeld, editor, Information Processing '74: Proceedings of the IFIP Congress, pages 471--475, New York, NY, 1974. North-Holland.

[12]

B. Liblit and A. Aiken. Type systems for distributed data structures. In POPL '00: Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 199--213, New York, NY, USA, 2000. ACM Press.

Digital Library

[13]

N. Liogkas, B. MacIntyre, E. D. Mynatt, Y. Smaragdakis, E. Tilevich, and S. Voida. Automatic partitioning: A promising approach to prototyping ubiquitous computing applications. IEEE Pervasive Computing, 2004.

Digital Library

[14]

O. Maffeïs. Ordonnancements de graphes de flots synchrones ; Application à la mise en æuvre de Signal. Phd thesis, University of Rennes I, Rennes, France, Jan. 1993.

[15]

J. Mitola. The software radio architecture. IEEE Communications Magazine, 33(5):26--38, May 1995.

Digital Library

[16]

M. Neubauer and P. Thiemann. From sequential programs to multi-tier applications by program transformation. In POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 221--232, New York, NY, USA, 2005. ACM Press.

Digital Library

[17]

P. Sewell, J. J. Leifer, K. Wansbrough, F. Z. Nardelli, M. Allen- Williams, P. Habouzit, and V. Vafeiadis. Acute: High-level programming language design for distributed computation. In Proceedings of ICFP 2005: International Conference on Functional Programming (Tallinn), Sept. 2005.

Digital Library

[18]

Y. Sorel. SynDEx: System-level cad software for optimizing distributed real-time embedded systems. Journal ERCIM News, 59:68--69, Oct. 2004.

[19]

J.-P. Talpin and P. Jouvelot. Polymorphic type, region and effect inference. Journal of Functional Programming, 2(3), 1992.

[20]

M. Ward and H. Zedan. Slicing as a program transformation. ACM Transactions on Programming Languages and Systems (TOPLAS), 29(2):7, 2007.

Digital Library

Cited By

Salvaneschi GWeisenburger P(2024)Bridging Between Active Objects: Multitier Programming for Distributed, Concurrent SystemsActive Object Languages: Current Research Trends10.1007/978-3-031-51060-1_4(92-122)Online publication date: 29-Jan-2024
https://doi.org/10.1007/978-3-031-51060-1_4
Weisenburger PWirth JSalvaneschi G(2020)A Survey of Multitier ProgrammingACM Computing Surveys10.1145/339749553:4(1-35)Online publication date: 26-Sep-2020
https://dl.acm.org/doi/10.1145/3397495
Delaval G(2019)Modular Distribution and Application to Discrete Controller SynthesisElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2008.01.003238:1(3-19)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.entcs.2008.01.003
Show More Cited By

Index Terms

A type system for the automatic distribution of higher-order synchronous dataflow programs
1. Computing methodologies
  1. Distributed computing methodologies
    1. Distributed programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages
        Distributed programming languages
        Parallel programming languages

Recommendations

A type system for the automatic distribution of higher-order synchronous dataflow programs
LCTES '08

We address the design of distributed systems with synchronous dataflow programming languages. As modular design entails handling both architectural and functional modularity, our first contribution is to extend an existing synchronous dataflow ...
Towards a higher-order synchronous data-flow language
EMSOFT '04: Proceedings of the 4th ACM international conference on Embedded software

The paper introduces a higher-order synchronous data-flow language in which communication channels may themselves transport programs. This provides a mean to dynamically reconfigure data-flow processes. The language comes as a natural and strict ...
Developing a monadic type checker for an object-oriented language: an experience report
SLE 2019: Proceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering

Functional programming languages are well-suited for developing compilers, and compilers for functional languages are often themselves written in a functional language. Functional abstractions, such as monads, allow abstracting away some of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems

June 2008

180 pages

ISBN:9781605581040

DOI:10.1145/1375657

General Chair:
Krisztián Flautner
ARM Limited, UK
,
Program Chair:
John Regehr
University of Utah, USA

ACM SIGPLAN Notices Volume 43, Issue 7
LCTES '08
July 2008
167 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1379023
Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES08

Sponsor:

LCTES08: ACM SIGPLAN/SIGBED 2008 Conference on Languages, Compilers, and Tools for Embedded Systems

June 12 - 13, 2008

AZ, Tucson, USA

Acceptance Rates

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
286
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)2

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Salvaneschi GWeisenburger P(2024)Bridging Between Active Objects: Multitier Programming for Distributed, Concurrent SystemsActive Object Languages: Current Research Trends10.1007/978-3-031-51060-1_4(92-122)Online publication date: 29-Jan-2024
https://doi.org/10.1007/978-3-031-51060-1_4
Weisenburger PWirth JSalvaneschi G(2020)A Survey of Multitier ProgrammingACM Computing Surveys10.1145/339749553:4(1-35)Online publication date: 26-Sep-2020
https://dl.acm.org/doi/10.1145/3397495
Delaval G(2019)Modular Distribution and Application to Discrete Controller SynthesisElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2008.01.003238:1(3-19)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.entcs.2008.01.003
Giese HHenkler SHirsch M(2018)A multi-paradigm approach supporting the modular execution of reconfigurable hybrid systemsSimulation10.1177/003754971036682487:9(775-808)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1177/0037549710366824
Phothilimthana PSchuldt MBodik R(2016)Compiling a gesture recognition application for a low-power spatial architectureACM SIGPLAN Notices10.1145/2980930.290796251:5(102-112)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2980930.2907962
Phothilimthana PSchuldt MBodik RKuo TWhalley D(2016)Compiling a gesture recognition application for a low-power spatial architectureProceedings of the 17th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools, and Theory for Embedded Systems10.1145/2907950.2907962(102-112)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2907950.2907962
Phothilimthana PJelvis TShah RTotla NChasins SBodik R(2014)ChlorophyllACM SIGPLAN Notices10.1145/2666356.259433949:6(396-407)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2666356.2594339
Phothilimthana PJelvis TShah RTotla NChasins SBodik RO'Boyle MPingali K(2014)ChlorophyllProceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2594291.2594339(396-407)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2594291.2594339
Lê NGuatto ACohen APop A(2013)Correct and Efficient Bounded FIFO QueuesProceedings of the 2013 25th International Symposium on Computer Architecture and High Performance Computing10.1109/SBAC-PAD.2013.8(144-151)Online publication date: 23-Oct-2013
https://dl.acm.org/doi/10.1109/SBAC-PAD.2013.8
Cohen AGérard LPouzet MJerraya ACarloni LMaraninchi FRegehr J(2012)Programming parallelism with futures in lustreProceedings of the tenth ACM international conference on Embedded software10.1145/2380356.2380394(197-206)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2380356.2380394
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents