article

Free access

Legality and Other Properties of Graph Models of Computations

Authors:

G. EstrinAuthors Info & Claims

Journal of the ACM (JACM), Volume 17, Issue 3

Pages 543 - 554

https://doi.org/10.1145/321592.321605

Published: 01 July 1970 Publication History

Abstract

Directed graphs having logical control associated with each vertex have been introduced as models of computational tasks for automatic assignment and sequencing on parallel processor systems. A brief review of their properties is given. A procedure to test the “legality” of graphs in this class is described, and leads to algorithms for counting the number of all possible executions (AND-type subgraphs), and for evaluating the probability of ever reaching a given vertex in the graph. Numerical results are given for some example graphs.

References

[1]

CALINGAER% P. System performance evaluation: survey and appraisal. Comm. ACM 10, 1 (Jan. 1967), 12-18.

[2]

ESTaIN, G., HOPKINS, D., COGGAN, B., AND CROCKER, S.D. SNUPER COMPUTER--a computer in instrumentation automaton. Proc. AFIPS 1967 Spring Joint Comput. Conf., Vol. 30, pp. 645-656 (Thompson Books, Washington, D. C.).

[3]

CONTI, C. J., GIBSON, D. H., ANn FITKOWSKY, S.H. Structural aspects of the System/ 360 Model 85. IBM Syst. J. 7, 1 (1968), 2--14.

[4]

ScnEaa, A.L. An anMysis of time-shared computer systems. Ph.D. diss., Dep. of Elec. Eng., MIT, Cambridge, Mass., June 1965.

[5]

ELMAGnP~BY, S. An algebra for the analysis of generalized activity networks. Manage. Sci. 10 (April 1964), 494-514.

[6]

ESTRIN, G., AND TURN, 1~. Automatic assignment of computations in a variable structure computer system. IEEE Trans. EC-12 (Dec. 1963), 756-773.

[7]

RUSSELL E.C. Automatic assignment of computational tasks in a variable structure computer. Rep. 63-45, Dep. of Eng., U. of California, Los Angeles, Calif., 1963.

[8]

MARTIN D .F . The automatic assignment and sequencing of computations on parallel processor systems. Ph.D. diss. in Eng., U. of California, Los Angeles, Calif., 1963.

[9]

MARTIN D. ~F., AND ESTRIN, G. Experiments on models of computations and systems. IEEE Trans. EC-16 (Feb. 1967), 59-69.

[10]

MARTIN D. F., AND ESTRIN, G. Models of computational systems--cyclic to acyclic graph transformations. Trans. IEEE EC-16 (Feb. 1967), 70-79.

[11]

MARTIN, D. F., AND ESTRIN, G. Models of computations and systems---evaluation of vertex probabilities in graph models of computations. J. ACM 14 (April 1967), 281-299.

[12]

MARTIN D. F., AND ESTRIN, G. Path length computations on graph models of computations. IEEE Trans. EC-18 (June 1969), 530-536.

[13]

BAER, J. Graph models of computations in computer systems. Ph.D. diss., Dep. of Eng., U. of California, Los Angeles, Calif., 1968.

[14]

BOVET, D.P. Memory allocation in computer systems. Ph.D. diss., Dep. of Eng., U. of California, Los Angeles, Calif., 1968.

[15]

RUSSELL, E.C. Automatic program analysis. Ph.D. diss., Dep. of Eng., U. of California, Los Angeles, Calif., 1969.

[16]

RODRIG~EZ, J. A graph model for parallel computations. Sc.D. diss., Dep. of Elec. Eng., MIT, Cambridge, Mass., Sept. 1967.

[17]

REITER, R. Scheduling parallel computations. J. ACM 15, 4 (Oct. 1968), 590-599.

[18]

PROSSER, R. T. Applications of Boolean matrices to the analysis of flow diagrams. Proc. 1959 Eastern Joint Comput. Conf., Vol. 16, pp. 133-138.

[19]

KARP, R.M. A note on the application of graph theory to digital computer programming. Inform. Contr. 3 (June 1960), 179-190.

[20]

MARIMONT, R.B. A new method of checking the consistency of precedence matrices. J. ACM 6, 2 (April 1959), 164-171.

[21]

COOPER, D.C. Some transformations and standard forms of graphs, with applications to computer programs. In Machine Intelligence, Vol. 2, Dale, E., and Michie, D. (Eds.), American Elsevier Publishing Co., Inc., New York, 1968, pp. 21-32.

Cited By

Никищенков СNikishchenkov S(2005)Диагностическая модель реконфигурируемых систем на основе информационно-логических схем процессовВестник Самарского государственного технического университета. Серия Физико-математические наукиVestnik Samarskogo Gosudarstvennogo Tekhnicheskogo Universiteta. Seriya "Fiziko-Matematicheskie Nauki"10.14498/vsgtu34534(119-127)Online publication date: 2005
https://doi.org/10.14498/vsgtu345
Naqvi WIbrahim M(2005)REFLEX active database model: Application of petri-netsDatabase and Expert Systems Applications10.1007/3-540-57234-1_21(233-240)Online publication date: 27-May-2005
https://doi.org/10.1007/3-540-57234-1_21
Moalla MPulou JSifakis J(2005)Synchronized petri nets : A model for the description of non-autonomous sytemsMathematical Foundations of Computer Science 197810.1007/3-540-08921-7_85(374-384)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08921-7_85
Show More Cited By

Index Terms

Legality and Other Properties of Graph Models of Computations
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Graph Bipartition with Hereditary Properties
On the sensitivity complexity of bipartite graph properties

Sensitivity complexity, introduced by Cook, Dwork, and Reischuk (1982, 1986) in [2,3], is an important complexity measure of Boolean functions. Turan (1984) [7] initiated the study of sensitivity complexity for graph properties. He conjectured that for ...
Quasi-randomness of graph balanced cut properties

Quasi-random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi-randomness of graphs. Let k ≥ 2 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 17, Issue 3

July 1970

173 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321592

Issue’s Table of Contents

Copyright © 1970 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1970

Published in JACM Volume 17, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
403
Total Downloads

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

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Никищенков СNikishchenkov S(2005)Диагностическая модель реконфигурируемых систем на основе информационно-логических схем процессовВестник Самарского государственного технического университета. Серия Физико-математические наукиVestnik Samarskogo Gosudarstvennogo Tekhnicheskogo Universiteta. Seriya "Fiziko-Matematicheskie Nauki"10.14498/vsgtu34534(119-127)Online publication date: 2005
https://doi.org/10.14498/vsgtu345
Naqvi WIbrahim M(2005)REFLEX active database model: Application of petri-netsDatabase and Expert Systems Applications10.1007/3-540-57234-1_21(233-240)Online publication date: 27-May-2005
https://doi.org/10.1007/3-540-57234-1_21
Moalla MPulou JSifakis J(2005)Synchronized petri nets : A model for the description of non-autonomous sytemsMathematical Foundations of Computer Science 197810.1007/3-540-08921-7_85(374-384)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08921-7_85
Uzgalis R(2005)A short history of computer system modeling and measurements at the University of California, Los AngelesRechnerstrukturen und Betriebsprogrammierung10.1007/3-540-06815-5_135(138-163)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-06815-5_135
Lee KLu ILin H(1994)PM-Net: a software project management representation modelInformation and Software Technology10.1016/0950-5849(94)90085-X36:5(295-308)Online publication date: May-1994
https://doi.org/10.1016/0950-5849(94)90085-X
Ghodsi Kant (1991)Well-formed generalized task graphsProceedings of the 1991 Third IEEE Symposium on Parallel and Distributed Processing10.1109/SPDP.1991.218221(344-351)Online publication date: 2-Dec-1991
https://dl.acm.org/doi/10.1109/SPDP.1991.218221
Zedan H(1990)Key references in distributed computer systems 1959–1989Distributed Computer Systems10.1016/B978-0-408-02938-4.50016-4(193-295)Online publication date: 1990
https://doi.org/10.1016/B978-0-408-02938-4.50016-4
Cohen ALevy L(1978)Structured flowcharts for multiprocessingComputer Languages10.1016/0096-0551(78)90040-13:4(209-226)Online publication date: 1-Jan-1978
https://dl.acm.org/doi/10.1016/0096-0551%2878%2990040-1
Unger B(1977)A Computer Resource Allocation Model with Some Measured and Simulation ResultsIEEE Transactions on Computers10.1109/TC.1977.167481326:3(243-259)Online publication date: 1-Mar-1977
https://dl.acm.org/doi/10.1109/TC.1977.1674813
Bowie W(1976)Applications of graph theory in computer systemsInternational Journal of Computer & Information Sciences10.1007/BF009910695:1(9-31)Online publication date: Mar-1976
https://doi.org/10.1007/BF00991069
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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents