research-article

Properties of a Model for Parallel Computations: : Determinacy, Termination, Queueing

Authors:

Richard M. Karp,

Rayamond E. MillerAuthors Info & Claims

SIAM Journal on Applied Mathematics, Volume 14, Issue 6

Pages 1390 - 1411

https://doi.org/10.1137/0114108

Published: 01 November 1966 Publication History

Abstract

This paper gives a graph-theoretic model for the description and analysis of parallel computations. Within the model, computation steps correspond to nodes of a graph, and dependency between computation steps is represented by branches with which queues of data are associated. First, it is shown that each such computation graphGrepresents a unique computation, determined independently of operation times. Next, methods of determining whether such a computation terminates and of finding the number of performances of each computation step are developed. The maximal strongly connected subgraphs of G and the loops within these subgraphs play aooutnal role in this analysis. For example, use is made of the result that either every computation step within a strongly connected snbgroph of G is performed an infinite number of times, or none is. Finally, necessary and sufficient conditions for the lengths of data queues to remain bounded are derived.

References

[1]

W. S. Dorn, N. C. Hsu, T. J. Rivlin, Some mathematical aspects of parallel computation, RC-647, IBM Research Center, Yorktown Heights, New York, 1962

Google Scholar

[2]

G. Estrin, B. Bussell, R. Turn, J. Bibb, Parallel processing in a restructurable computer system, IEEE Trans. Electronic Computers, EC-12 (1963), 747–755

Crossref

Google Scholar

[3]

L. R. Ford, Jr., D. R. Fulkerson, Flows in networks, Princeton University Press, Princeton, N.J., 1962xii+194

Google Scholar

[4]

J. Holland, A universal computer capable of executing an arbitrary number of subprograms simultaneously, Proc. Eastern Joint Computer Conference, 1959, 108–113

Google Scholar

[5]

R. M. Karp, R. E. Miller, Properties of a model for parallel computations: determinacy, termination, queueing, RC-1285, IBM Research Center, Yorktown Heights, New York, 1964

Google Scholar

[6]

D. W. Slotnick, C. Borck, R. C. Mcreynolds, The SOLOMON computer, Proc. Eastern Joint Computer Conference, 1962, 97–107

Google Scholar

[7]

E. G. Wagner, An approach to modular computers, I: Spider automata and embedded automata, RC-1107, IBM Research Center, Yorktown Heights, New York, 1964

Google Scholar

Cited By

View all

Lin ZGancher JParno B(2024)FlowCert: Translation Validation for Asynchronous Dataflow via Dynamic Fractional PermissionsProceedings of the ACM on Programming Languages10.1145/36897298:OOPSLA2(499-526)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689729
Rinaldi Fwunder jAzevedo de Amorim AMuller S(2024)Pipelines and Beyond: Graph Types for ADTs with FuturesProceedings of the ACM on Programming Languages10.1145/36328598:POPL(482-511)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632859
Bugayenko YLipanin M(2023)An Algorithm for Partial Elimination of Jumps in an Object-Oriented Dataflow LanguageProceedings of the 2023 7th International Conference on Computer Science and Artificial Intelligence10.1145/3638584.3638679(152-164)Online publication date: 8-Dec-2023
https://dl.acm.org/doi/10.1145/3638584.3638679
Show More Cited By

Index Terms

Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing

Index terms have been assigned to the content through auto-classification.

Recommendations

Scheduling Parallel Computations

A model for parallel computations is given as a directed graph in which nodes represent elementary operations, and branches, data channels. The problem considered is the determination of an admissible schedule for such a computation; i.e. for each node ...
Predicting Performance of Parallel Computations

An accurate and computationally efficient method for predicting the performance of a class of parallel computations running on concurrent systems is described. A parallel computation is modeled as a task system with precedence relationships expressed as ...
A GRAPH MODEL FOR PARALLEL COMPUTATIONS

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Applied Mathematics

SIAM Journal on Applied Mathematics Volume 14, Issue 6

Nov 1966

297 pages

ISSN:0036-1399

DOI:10.1137/smjmap.1966.14.issue-6

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 November 1966

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 22 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lin ZGancher JParno B(2024)FlowCert: Translation Validation for Asynchronous Dataflow via Dynamic Fractional PermissionsProceedings of the ACM on Programming Languages10.1145/36897298:OOPSLA2(499-526)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689729
Rinaldi Fwunder jAzevedo de Amorim AMuller S(2024)Pipelines and Beyond: Graph Types for ADTs with FuturesProceedings of the ACM on Programming Languages10.1145/36328598:POPL(482-511)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632859
Bugayenko YLipanin M(2023)An Algorithm for Partial Elimination of Jumps in an Object-Oriented Dataflow LanguageProceedings of the 2023 7th International Conference on Computer Science and Artificial Intelligence10.1145/3638584.3638679(152-164)Online publication date: 8-Dec-2023
https://dl.acm.org/doi/10.1145/3638584.3638679
Bhagyanath AKercher NSchneider KZhu Qvon Hanxleden RStephen EBrandt J(2023)Allocation and Scheduling of Dataflow Graphs on Hybrid Dataflow/von Neumann ArchitecturesProceedings of the 21st ACM-IEEE International Conference on Formal Methods and Models for System Design10.1145/3610579.3611079(59-70)Online publication date: 21-Sep-2023
https://dl.acm.org/doi/10.1145/3610579.3611079
Schneider KBhagyanath A(2023)Consistency Constraints for Mapping Dataflow Graphs to Hybrid Dataflow/von Neumann ArchitecturesACM Transactions on Embedded Computing Systems10.1145/360786922:5(1-25)Online publication date: 26-Sep-2023
https://dl.acm.org/doi/10.1145/3607869
Wang DLou JJin NMascarenhas EMahapatra RKinzer SGhodrati SYazdanbakhsh AEsmaeilzadeh HKim NSolihin YHeinrich M(2023)MESA: Microarchitecture Extensions for Spatial Architecture GenerationProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589084(1-14)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589084
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
Muller S(2022)Static prediction of parallel computation graphsProceedings of the ACM on Programming Languages10.1145/34987086:POPL(1-31)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498708
Rafique OSchneider K(2022)Synthesis of Parallel Software from Heterogeneous Dataflow ModelsSN Computer Science10.1007/s42979-022-01102-33:3Online publication date: 26-Apr-2022
https://dl.acm.org/doi/10.1007/s42979-022-01102-3
Schneider KArun-Kumar SMery DSaha IZhang L(2021)Translating structured sequential programs to dataflow graphsProceedings of the 19th ACM-IEEE International Conference on Formal Methods and Models for System Design10.1145/3487212.3487343(66-77)Online publication date: 20-Nov-2021
https://dl.acm.org/doi/10.1145/3487212.3487343
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Scheduling Parallel Computations

Predicting Performance of Parallel Computations

A GRAPH MODEL FOR PARALLEL COMPUTATIONS

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations