
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.
numerical analysis
numerical analysis
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 149 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 0.1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
