- Authors:
- J. E. Rodrigues,
- Jorge E Rodriguez Bezos
This report presents a computational model called program graphs which makes possible a precise description of parallel computations of arbitrary complexity on non-structured data. In the model, the computation steps are represented by the nodes of a directed graph whose links represent the elements of storage and transmission of data and/or control information. The activation of computation represented by a node depends only on the control information residing in each of the links incident into and out of the node. At any given time any number of nodes may be active, and there are no assumptions in the model regarding either the length of time required to perform the computation represented by a node or the length of time required to transmit data or control information from one node to another. Data dependent decisions are incorporated in the model in a novel way which makes a sharp distinction between the local sequencing requirements arising form the data dependency of the computation steps and the global sequencing requirements determined by the logical structure for the algorithm.
Cited By
- Dongarra J, Haidar A, Kurzak J, Luszczek P, Tomov S and YarKhan A (2014). Model-Driven One-Sided Factorizations on Multicore Accelerated Systems, Supercomputing Frontiers and Innovations: an International Journal, 1:1, (85-115), Online publication date: 6-Apr-2014.
- Postow B, Regan K and Smith C (2019). UPSILON: Universal Programming System with Incomplete Lazy Object Notation, Fundamenta Informaticae, 50:3-4, (325-359), Online publication date: 1-Aug-2002.
- Postow B, Regan K and Smith C (2019). UPSILON, Fundamenta Informaticae, 50:3, (325-359), Online publication date: 1-Mar-2002.
- Dennis J and Misunas D A preliminary architecture for a basic data-flow processor 25 years of the international symposia on Computer architecture (selected papers), (125-131)
- Grafe V, Davidson G, Hoch J and Holmes V (1989). The Epsilon dataflow processor, ACM SIGARCH Computer Architecture News, 17:3, (36-45), Online publication date: 1-Jun-1989.
- Grafe V, Davidson G, Hoch J and Holmes V The Epsilon dataflow processor Proceedings of the 16th annual international symposium on Computer architecture, (36-45)
- Herath J, Yamaguchi Y, Saito N and Yuba T (2019). Dataflow Computing Models, Languages, and Machines for Intelligence Computations, IEEE Transactions on Software Engineering, 14:12, (1805-1828), Online publication date: 1-Dec-1988.
- Hancu and Smith K DVPP: a VLSI dynamic-graph ensemble machine Proceedings of the 2nd international conference on Supercomputing, (90-100)
- Mendelson B and Silberman G Mapping data flow programs on a VLSI array of processors Proceedings of the 14th annual international symposium on Computer architecture, (72-80)
- Kaplan I (1987). Programming the Loral LDF 100 dataflow machine, ACM SIGPLAN Notices, 22:5, (47-57), Online publication date: 1-May-1987.
- Hong Y, Payne T and Ferguson L Graph allocation in static dataflow systems Proceedings of the 13th annual international symposium on Computer architecture, (55-64)
- Hong Y, Payne T and Ferguson L (1986). Graph allocation in static dataflow systems, ACM SIGARCH Computer Architecture News, 14:2, (55-64), Online publication date: 1-May-1986.
- Gurd J, Kirkham C and Watson I (1985). The Manchester prototype dataflow computer, Communications of the ACM, 28:1, (34-52), Online publication date: 2-Jan-1985.
- Gostelow K and Thomas R (1980). Performance of a Simulated Dataflow Computer, IEEE Transactions on Computers, 29:10, (905-919), Online publication date: 1-Oct-1980.
- Davis A The architecture and system method of DDM1 Proceedings of the 5th annual symposium on Computer architecture, (210-215)
- Arvind , Gostelow K and Plouffe W Indeterminacy, monitors, and dataflow Proceedings of the sixth ACM symposium on Operating systems principles, (159-169)
- Arvind , Gostelow K and Plouffe W (1977). Indeterminacy, monitors, and dataflow, ACM SIGOPS Operating Systems Review, 11:5, (159-169), Online publication date: 1-Nov-1977.
- Anderson J and Browne J Graph models of computer systems Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, (166-178)
- Barta B (1975). PACOL, ACM SIGPLAN Notices, 10:3, (44-53), Online publication date: 1-Mar-1975.
- Dennis J and Misunas D A preliminary architecture for a basic data-flow processor Proceedings of the 2nd annual symposium on Computer architecture, (126-132)
- Barta B PACOL Proceedings of the conference on Programming languages and compilers for parallel and vector machines, (44-53)
- Dennis J and Misunas D (1974). A preliminary architecture for a basic data-flow processor, ACM SIGARCH Computer Architecture News, 3:4, (126-132), Online publication date: 1-Dec-1974.
- Knott G (1974). A proposal for certain process management and intercommunication primitives, ACM SIGOPS Operating Systems Review, 8:4, (7-44), Online publication date: 1-Oct-1974.
- Dennis J and Misunas D A computer architecture for highly parallel signal processing Proceedings of the 1974 annual ACM conference - Volume 2, (402-409)
- Dennis J Bibliography Record of the Project MAC conference on concurrent systems and parallel computation, (183-199)
Recommendations
Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing
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 ...
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 ...