Access Restriction

Author Reiter, Raymond
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1968
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract 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 determine a sequence of times at which the node initiates its operation. These times must be such that each node, upon initiation, is assured of having the necessary data upon which to operate. Necessary and sufficient conditions that a schedule be admissible are given. The computation rate of a given admissible schedule is defined and is shown to have a limiting value 1/π where π is a parameter dependent upon the cycles in the graph. Thus, the computation cannot proceed at a rate exceeding 1/π. For γ ≥ π, the class of all periodic admissible schedules with period γ is characterized by the solution space of a certain system of linear inequalities. In particular, then, the maximum computation rate of 1/π is attainable under a periodic admissible schedule with period π. A class of all-integer admissible schedules is given. Finally, an algorithm is given for the determination of the number of initiations of each node in the graph defining a parallel computation.An example for a system of difference equations is given in detail.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1968-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 15
Issue Number 4
Page Count 10
Starting Page 590
Ending Page 599

Open content in new tab

   Open content in new tab
Source: ACM Digital Library