Report Number: CS-TR-70-185
Institution: Stanford University, Department of Computer Science
Title: Graph program simulation
Author: Nelson, Edward C.
Date: October 1970
Abstract: This reports the simulation of a parallel processing system
based on a directed graph representation of parallel
computations. The graph representation is based on the model
developed by Duane Adams in which programs are written as
directed graphs whose nodes represent operations and whose
edges represent data flow. The first part of the report
describes a simulator which interprets these graph programs.
The second part describes the use of the simulator in a
hypothetical environment which has an unlimited number of
processors and an unlimited amount of memory. Three programs,
a trapezoidal quadrature, a sort and a matrix multiplication,
were used to study the effect of varying the relative speed
of primitive operations on computation time with problem
size. The system was able to achieve a high degree of
parallelism. For example, the simulator multiplied two n by n
matrices in a simulated time proportional to n.