research-article

A low-overhead dedicated execution support for stream applications on shared-memory cmp

Authors:

Stéphane Louise,

Vincent DavidAuthors Info & Claims

EMSOFT '12: Proceedings of the tenth ACM international conference on Embedded software

Pages 143 - 152

https://doi.org/10.1145/2380356.2380383

Published: 07 October 2012 Publication History

Abstract

The ever-growing number of cores in Chip Multi-Processors (CMP) brings a renewed interest in stream programming to solve the programmability issues raised by massively parallel architectures. Stream programming languages are flourishing (StreaMIT, Brook, ∑C, etc.). Nonetheless, their execution support have not yet received enough attention, in particular regarding the new generation of many-cores.

In embedded software, a lightweight solution can be implemented as a specialized library, but a dedicated micro-kernel offers a more flexible solution. We propose to explore the latter way with a Logical Vector Time based execution model, for CMP architectures with on-chip shared memory.

References

[1]

A. Amar, P. Boulet, and P. Dumont. Projection of the Array-OL specification language onto the Kahn Process Network computation model. Technical Report RR-5515, LIFL, USTL, Mar 2005.

Digital Library

[2]

S. Amarasinghe, M. I. Gordon, M. Karczmarek, J. Lin, D. Maze, R. M. Rabbah, and W. Thies. Language and compiler design for streaming applications. International Journl of Parallel Programming, 33(2/3), Jun 2005.

Digital Library

[3]

I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fatahalian, M. Houston, and P. Hanrahan. Brook for gpus: stream computing on graphics hardware. ACM Trans. Graph., 23:777--786, August 2004.

Digital Library

[4]

J. T. Buck and E. A. Lee. Scheduling dynamic dataow graphs with bounded memory using the token ow model. Technical report, 1993.

Digital Library

[5]

L. Cudennec and R. Sirdey. Parallelism reduction based on pattern substitution in dataow oriented programming languages. In Proceedings of the 12th International Conference on Computational Science, ICCS'12, Omaha, Nebraska, USA, 2012. To Appear.

[6]

B. A. Davey and H. A. Priestley. Introduction to lattices and order. Cambridge University Press, New York, NY, 2002.

[7]

P. Dumont and P. Boulet. Another multidimensional synchronous dataow: Simulating Array-OL in Ptolemy II. Technical Report RR-5516, LIFL, USTL, Mar 2005.

[8]

C. J. Fidge. Partial orders for parallel debugging. In Proceedings of the 1988 ACM SIGPLAN and SIGOPS Workshop on Parallel and Distributed Debugging, pages 183--194, 1988.

Digital Library

[9]

C. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. In Proceedings of the 11th Australian Computer Science Conference, pages 56--66, 1988.

[10]

R. L. G. Bilsen, M. Engels and J. A. Peperstraete. Cyclo-static data flow. IEEE Transactions on Signal Processing, 44(2):397--408, 1996.

Digital Library

[11]

M. I. Gordon, W. Thies, M. Karczmarek, J. Lin, A. S. Meli, A. A. Lamb, C. Leger, J. Wong, H. Hoffmann, D. Maze, and S. Amarasinghe. A stream compiler for communication-exposed architectures. SIGOPS Oper. Syst. Rev., 36(5):291--303, Oct. 2002.

Digital Library

[12]

T. Goubier, R. Sirdey, S. Louise, and V. David. ∑C: A programming model and language for embedded manycores. In Y. Xiang, A. Cuzzocrea, M. Hobbs, and W. Zhou, editors, ICA3PP (1), volume 7016 of Lecture Notes in Computer Science, pages 385--394. Springer, 2011.

Digital Library

[13]

M. Habib, M. Huchard, and L. Nourine. Embedding partially ordered sets into chain-products. In Proceedings of the 1995 International Symposium on Knowledge Retrieval, Use, and Storage for Efficiency, Santa Cruz, CA, 1995. University of California.

[14]

M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(2):124--149, 1991.

Digital Library

[15]

G. Kahn. The semantics of a simple language for parallel programming. In J. L. Rosenfeld, editor, Information processing, pages 471--475, Stockholm, Sweden, Aug 1974. North Holland, Amsterdam.

[16]

A. D. Kshemkalyani and M. Singhal. Distributed Computing: Principles, Algorithms and Systems. Cambridge University Press, Baltimore, MD, 2011.

Digital Library

[17]

E. A. Lee. Finite state machines and modal models in Ptolemy II. Technical Report UCB/EECS-2009-151, EECS Department, University of California, Berkeley, Nov 2009.

[18]

E. A. Lee and T. Parks. Dataow process networks. In Proceedings of the IEEE, pages 773--799, 1995.

[19]

F. Mattern. Virtual time and global states of distributed systems. In Proceedings of the International Workshop on Parallel and Distributed Algorithms, pages 215--226, 1988.

[20]

P. Oliveira Castro, S. Louise, and D. Barthou. Reducing memory requirements of stream programs by graph transformations. In Proc. of the Int. Conf. of High Perf. Computing and Sim. (HPCS), pages 171--180, 2010.

[21]

Ø. Ore. Theory of graphs, volume 38. American Mathematical Society Colloquium Publications, Providence, RI, 1962.

[22]

D. Parker, G. J. Popek, G. Rudisin, A. Stoughton, B. J. Walker, E. Walton, J. M. Chow, D. Edwards, S. Kiser, and C. Kline. Detection of mutual inconsistency in distributed systems. IEEE Trans. Software Ingineering, 9:240--247, 1983.

Digital Library

[23]

M. Singhal. A heuristically-aided algorithm for mutual exclusion in distributed systems. IEEE Trans. on Computers, 38(5), 1989.

Digital Library

[24]

W. Thies, M. Karczmarek, and S. Amarasinghe. Streamit: A language for streaming applications. In R. Horspool, editor, Compiler Construction, volume 2304 of Lecture Notes in Computer Science, pages 49--84. Springer Berlin / Heidelberg, 2002. 10.1007/3-540-45937-5 14.

Digital Library

[25]

W. T. Trotter. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore, MD, 1992.

[26]

P. A. S. Ward. An offline algorithm for dimension-bound analysis. In Proceedings of the 1999 International Conference on Parallel Processing. IEEE Computer Society, 1999.

Digital Library

[27]

J. Yañez and J. Montero. A poset dimension algorithm. Journal of Algorithms, 30(1):185--208, 1999.

Digital Library

[28]

M. Yannakakis. The complexity of the partial order dimension problem. Journal on Algebraic and Discrete Methods, 3(3):351--358, 1982.

[29]

X. D. Zhang, Q. J. Li, R. Rabbah, and S. Amarasinghe. A lightweight streaming layer for multicore execution. In Workshop on Design, Architecture and Simulation of Chip Multi-Processors, Chicago, IL, Dec 2007.

Cited By

Gonnord LHenrio LMorel LRadanne G(2023)A Survey on Parallelism and DeterminismACM Computing Surveys10.1145/356452955:10(1-28)Online publication date: 2-Feb-2023
https://dl.acm.org/doi/10.1145/3564529
Cudennec LGoubier T(2015)A Short Overview of Executing Chemical Reactions over the C and C Dataflow Programming ModelsProcedia Computer Science10.1016/j.procs.2015.05.34951:C(1413-1422)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.procs.2015.05.349
Louise SDubrulle PGoubier T(2014)A Model of Computation for Real-Time Applications on Embedded ManycoresProceedings of the 2014 IEEE 8th International Symposium on Embedded Multicore/Manycore SoCs10.1109/MCSoC.2014.54(333-340)Online publication date: 23-Sep-2014
https://dl.acm.org/doi/10.1109/MCSoC.2014.54
Show More Cited By

Index Terms

A low-overhead dedicated execution support for stream applications on shared-memory cmp
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Process synchronization
        Scheduling

Recommendations

Synergistic execution of stream programs on multicores with accelerators
LCTES '09: Proceedings of the 2009 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

The StreamIt programming model has been proposed to exploit parallelism in streaming applications on general purpose multicore architectures. The StreamIt graphs describe task, data and pipeline parallelism which can be exploited on accelerators such as ...
Synergistic execution of stream programs on multicores with accelerators
LCTES '09

The StreamIt programming model has been proposed to exploit parallelism in streaming applications on general purpose multicore architectures. The StreamIt graphs describe task, data and pipeline parallelism which can be exploited on accelerators such as ...
Software Pipelined Execution of Stream Programs on GPUs
CGO '09: Proceedings of the 7th annual IEEE/ACM International Symposium on Code Generation and Optimization

The StreamIt programming model has been proposed to exploit parallelism in streaming applications on general purpose multi-core architectures. This model allows programmers to specify the structure of a program as a set of filters that act upon data, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EMSOFT '12: Proceedings of the tenth ACM international conference on Embedded software

October 2012

266 pages

ISBN:9781450314251

DOI:10.1145/2380356

General Chairs:
Ahmed Jerraya
CEA
,
Luca Carloni
Columbia University
,
Program Chairs:
Florence Maraninchi
Grenoble INP & VERIMAG
,
John Regehr
University of Utah

Copyright © 2012 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: 07 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESWEEK'12

Sponsor:

ESWEEK'12: Eighth Embedded System Week

October 7 - 12, 2012

Tampere, Finland

Acceptance Rates

Overall Acceptance Rate 60 of 203 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
140
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gonnord LHenrio LMorel LRadanne G(2023)A Survey on Parallelism and DeterminismACM Computing Surveys10.1145/356452955:10(1-28)Online publication date: 2-Feb-2023
https://dl.acm.org/doi/10.1145/3564529
Cudennec LGoubier T(2015)A Short Overview of Executing Chemical Reactions over the C and C Dataflow Programming ModelsProcedia Computer Science10.1016/j.procs.2015.05.34951:C(1413-1422)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.procs.2015.05.349
Louise SDubrulle PGoubier T(2014)A Model of Computation for Real-Time Applications on Embedded ManycoresProceedings of the 2014 IEEE 8th International Symposium on Embedded Multicore/Manycore SoCs10.1109/MCSoC.2014.54(333-340)Online publication date: 23-Sep-2014
https://dl.acm.org/doi/10.1109/MCSoC.2014.54
Do XLouise SCohen A(2014)Comparing the StreamIt and SC Languages for Manycore ProcessorsProceedings of the 2014 Fourth Workshop on Data-Flow Execution Models for Extreme Scale Computing10.1109/DFM.2014.13(17-25)Online publication date: 24-Aug-2014
https://dl.acm.org/doi/10.1109/DFM.2014.13
Nguyen DNguyen TDubrulle P(2014)Hierarchical Synchronization between Processes in a High-Performance Execution Support of Dataflow Process Networks on Many-Core ArchitecturesProceedings of the 2014 Eighth International Conference on Complex, Intelligent and Software Intensive Systems10.1109/CISIS.2014.62(439-444)Online publication date: 2-Jul-2014
https://dl.acm.org/doi/10.1109/CISIS.2014.62
Louise S(2013)A Formal Evaluation of Mean-Time Access Latencies for Interleaved On-chip Shared Banked-memory in ManycoresProceedings of the 2013 IEEE 7th International Symposium on Embedded Multicore/Manycore System-on-Chip10.1109/MCSoC.2013.16(19-24)Online publication date: 26-Sep-2013
https://dl.acm.org/doi/10.1109/MCSoC.2013.16
Dubrulle POhayon E(2013)A Dedicated Micro-Kernel to Combine Real-Time and Stream Applications on Embedded ManycoresProcedia Computer Science10.1016/j.procs.2013.05.33118(1634-1643)Online publication date: 2013
https://doi.org/10.1016/j.procs.2013.05.331
Aubry PBeaucamps PBlanc FBodin BCarpov SCudennec LDavid VDore PDubrulle PDinechin BGalea FGoubier THarrand MJones SLesage JLouise SChaisemartin NNguyen TRaynaud XSirdey R(2013)Extended Cyclostatic Dataflow Program Compilation and Execution for an Integrated Manycore ProcessorProcedia Computer Science10.1016/j.procs.2013.05.33018(1624-1633)Online publication date: 2013
https://doi.org/10.1016/j.procs.2013.05.330

View Options

Get Access

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