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.