article

Free access

Resource requirements of dataflow programs

Authors:

ArvindAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 16, Issue 2

Pages 141 - 150

https://doi.org/10.1145/633625.52417

Published: 17 May 1988 Publication History

Abstract

Parallel execution of programs requires more resources and more complex resource management than sequential execution. If concurrent tasks can be spawned dynamically, programs may require an inordinate amount of resources when the potential parallelism in the program is much greater than the amount of parallelism the machine can exploit. We describe loop bounding, a technique for dynamically controlling the amount of parallelism exposed in dataflow programs. The effectiveness of the technique in reducing token storage requirements is supported by experimental data in the form of parallelism profiles and waiting-token profiles. Comparisons are made throughout with more conventional approaches to parallel computing.

References

[1]

Arvind and David E. Culler. Dataflow Architectures, pages 225-253. Volume 1, Annual Reviews Inc., Palo Alto, CA, 1986. Reprinted in Dataflow and Reduction Architectures, S. S. Thakkar, IEEE Computer Society Press, 1987.

Digital Library

[2]

Arvind and David E. Culler. Managing Resources in a Parallel Machine. In Proceedings of IFZP TC-10 Working Conference on Fifth Generation Computer Architecture, Manchester, England, North-Holland Publishing Company, July 15-18 1985.

Digital Library

[3]

Arvind, David E. Culler, and Gino K. Maa. Parallelism in Dataflow Programs. Technical Report Computation Structures Group Memo 279, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, December 1987.

[4]

Arvind and Kattamuri Ekanadham. Future Scientific Programming on Parallel Machines. In Proceedings of the International Conference on Supercomputing (ICS), Athens, Greece, June 8-12 1987. To appear in the Journal of Parallel and Distributed Computing.

Digital Library

[5]

Arvind and K. P. Gostelow. The U-Interpreter. COM- PUTER, 15(2), Feburary 1982.

[6]

Arvind and Robert A. Iannucci. Two Fundamental Issues in Multiprocessing. In Proceedings of DFVLR - Conference 1957 on Parallel Processing in Science and Engineering, Bonn-Bad Godesberg, W. Germany, June 25-29 1987.

Digital Library

[7]

Arvind, R. S. Nikhil, and K. K. Pingali. Id Nouveau Reference Manual, Part II: Semantics. Technical Report, Computation Structures Group, MIT Lab. for Computer Science, 545 Technology Square, Cambridge, MA 02139, April 1987.

[8]

Arvind and Rishiyur S. Nikhil. Executing a Program on the MIT Tagged-Token Dataflow Architecture. In Pruceedings of the PARLE Conference, Eindhoven, The Netherlands. (LNCS Volume Z59), Springer-Verlag, June 15-19 19S7. To appear in IEEE Transactions on Computers.

Digital Library

[9]

G. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein. Register Allocation via Coloring. Computer Languages, 6:47-57, 1981.

Digital Library

[10]

David E. Culler. Eflectiue Dataflow Execution of Scientific Programs. PhD thesis, Dept. of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, August 1988 (expected).

[11]

David E. Culler. Resource Management for the Tagged- Token Dataflaw Architecture. Technical Report TR-332, Massachusetts Institute for Technology, Laboratory for Computer Science, January 1985.

Digital Library

[12]

A. Gottlieb, B. D. Lubachevsky, and L. Rudolph. Coordinating Large Numbers of Processors. ACM Transactions on Programming Languages and Systems, 4(I), January 1982.

[13]

Robert H. Jr. Halstead. Implementation of Multilisp: Lisp on a Multiprocessor. In Proceedings of the ACM Symposium on Lisp and Functional Languages, August 1984.

Digital Library

[14]

D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe. Dependence Graphs and Compiler Optimizations. In Proceeding of A CM Symposium on Principles of Progmmming Languages, January 1981.

Digital Library

[15]

Rishiyur Sivaswami Nikhil. Id Nouveau Reference Manual, Part I: Syntar. Technical Report, Computation Structures Group, MIT Lab. for Computer Science, 545 Technology Square, Cambridge, MA 02139, April 1987.

[16]

G. F. Pfister and et al. The IBM Research Parallel Processor Prototype (RP3). In Proceedings of the 1985 ICPP, August 1985.

[17]

C. A. Ruggiero. Throttle Mechanisms for the Manchester Dataflow Machine. PhD thesis, University of Manchester, Manchester Ml3 9PL, England, July 1987.

Digital Library

[18]

Kenneth R. Traub. A Compiler for the MIT Tagged-Token Dataflow Architecture. Technical Report LCS TR-370, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, August 1986. (Master's Thesis, Dept. of Electrical Engineering and Computer Science, MIT).

Digital Library

[19]

Michael J. Wolfe. Optimizing Supercompilers for Supercomputers. PhD thesis, University of Illinois at Urbana- Champaign, 1982.

Digital Library

Cited By

B. Khan MR. Khan AAlkahtani H(2022)Exploring the Approaches to Data Flow ComputingComputers, Materials & Continua10.32604/cmc.2022.02062371:2(2333-2346)Online publication date: 2022
https://doi.org/10.32604/cmc.2022.020623
Gobieski GLucia BBeckmann NBahar IHerlihy MWitchel ELebeck A(2019)Intelligence Beyond the EdgeProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304011(199-213)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304011
Josipović LGhosal RIenne PAnderson JBazargan K(2018)Dynamically Scheduled High-level SynthesisProceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3174243.3174264(127-136)Online publication date: 15-Feb-2018
https://dl.acm.org/doi/10.1145/3174243.3174264
Show More Cited By

Index Terms

Recommendations

Resource requirements of dataflow programs
ISCA '88: Proceedings of the 15th Annual International Symposium on Computer architecture

Parallel execution of programs requires more resources and more complex resource management than sequential execution. If concurrent tasks can be spawned dynamically, programs may require an inordinate amount of resources when the potential parallelism ...
Dataflow execution of sequential imperative programs on multicore architectures
MICRO-44: Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture

As multicore processors become the default, researchers are aggressively looking for program execution models that make it easier to use the available resources. Multithreaded programming models that rely on statically-parallel programs have gained ...
Assessing the benefits of fine-grain parallelism in dataflow programs
Supercomputing '88: Proceedings of the 1988 ACM/IEEE conference on Supercomputing

A method for assessing the benefits of fine-grain parallelism in “real” programs is presented. The method is based on parallelism profiles and speedup curves derived by executing dataflow graphs on an interpreter under progressively more realistic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 16, Issue 2

Special Issue: Proceedings of the 15th annual international symposium on Computer Architecture

May 1988

431 pages

ISSN:0163-5964

DOI:10.1145/633625

Issue’s Table of Contents

ISCA '88: Proceedings of the 15th Annual International Symposium on Computer architecture
June 1988
461 pages
ISBN:0818608617
Chairman:
H. J. Siegel
Purdue Univ., West Lafayette, IN

Copyright © 1988 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 May 1988

Published in SIGARCH Volume 16, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
820
Total Downloads

Downloads (Last 12 months)95
Downloads (Last 6 weeks)14

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

B. Khan MR. Khan AAlkahtani H(2022)Exploring the Approaches to Data Flow ComputingComputers, Materials & Continua10.32604/cmc.2022.02062371:2(2333-2346)Online publication date: 2022
https://doi.org/10.32604/cmc.2022.020623
Gobieski GLucia BBeckmann NBahar IHerlihy MWitchel ELebeck A(2019)Intelligence Beyond the EdgeProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304011(199-213)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304011
Josipović LGhosal RIenne PAnderson JBazargan K(2018)Dynamically Scheduled High-level SynthesisProceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3174243.3174264(127-136)Online publication date: 15-Feb-2018
https://dl.acm.org/doi/10.1145/3174243.3174264
Selim MRahman M(2014)Carrying on the legacy of imperative languages in the future parallel computing eraParallel Computing10.1016/j.parco.2014.02.00140:3-4(1-33)Online publication date: Mar-2014
https://doi.org/10.1016/j.parco.2014.02.001
Sbîrlea DSbîrlea AWheeler KSarkar V(2013)The Flexible Preconditions Model for Macro-Dataflow ExecutionProceedings of the 2013 Data-Flow Execution Models for Extreme Scale Computing10.1109/DFM.2013.13(51-58)Online publication date: 8-Sep-2013
https://dl.acm.org/doi/10.1109/DFM.2013.13
Arandi SEvripidou P(2010)Programming multi-core architectures using Data-Flow techniques2010 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation10.1109/ICSAMOS.2010.5642072(152-161)Online publication date: Jul-2010
https://doi.org/10.1109/ICSAMOS.2010.5642072
Gautier TRoch JWagner F(2007)Fine Grain Distributed Implementation of a Dataflow Language with Provable PerformancesProceedings of the 7th international conference on Computational Science, Part II10.1007/978-3-540-72586-2_87(593-600)Online publication date: 27-May-2007
https://dl.acm.org/doi/10.1007/978-3-540-72586-2_87
Cavalheiro GGaspary LCardozo MCordeiro O(2007)Anahy: A Programming Environment for Cluster ComputingHigh Performance Computing for Computational Science - VECPAR 200610.1007/978-3-540-71351-7_16(198-211)Online publication date: 2007
https://doi.org/10.1007/978-3-540-71351-7_16
Klitgård I(2006)Taking the pun by the hornsTargetTarget. International Journal of Translation Studies10.1075/target.17.1.05kli17:1(71-92)Online publication date: 23-Mar-2006
https://doi.org/10.1075/target.17.1.05kli
Traub K(2005)Multi-thread code generation for dataflow architectures from non-strict programsFunctional Programming Languages and Computer Architecture10.1007/3540543961_5(73-101)Online publication date: 6-Jul-2005
https://doi.org/10.1007/3540543961_5
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Issue’s Table of Contents