|
 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/&pgr; where &pgr; is a parameter dependent upon the cycles in the graph. Thus, the computation cannot proceed at a rate exceeding 1/&pgr;. For &ggr; ≥ &pgr;, the class of all periodic admissible schedules with period &ggr; is characterized by the solution space of a certain system of linear inequalities. In particular, then, the maximum computation rate of 1/&pgr; is attainable under a periodic admissible schedule with period &pgr;. 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
ESTRIN, G., BUSSELL, B., TURN, R., AND BIBB, J. Parallel processing in a restructurable computer system. IEEE Trans. EC-12 (1963), 747-755.
|
| |
2
|
DORN, W. S., Hsu, N. C., AND IIVLIN, T .J . Some mathematieM aspects of parallel computation. RC-647, IBM tesearch Center, Yorktown Heights, N. Y., 1962.
|
 |
3
|
|
| |
4
|
|
| |
5
|
KARP, R. M., AND MILLER, R.E. Properties of a model for parallel computations: Determinacy, termination, queueing. SIAM J. Appl. Malh. 14 (1966), 1390-1411.
|
| |
6
|
BERGE, C., AND GHOUILa-HOUaI, A. Programming, Games and Transporlation Nelworks. Wiley, New York, 1965.
|
| |
7
|
DANTZIG, G. B., BLATTNER, W. O., AND }AO, M.R. Finding a cycle in a graph with minimum cost to time ratio with application to a ship routing problem. Tech. Rep. 66-1, Operations Res. House, Stanford U., Stanford, Calif., Nov. 1966.
|
| |
8
|
|
CITED BY 34
|
|
|
|
|
Wolfgang Backes , Uwe Schwiegelshohn , Lothar Thiele, Analysis of free schedule in periodic graphs, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.333-342, June 29-July 01, 1992, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B. Mesman , M. Strik , A. H. Timmer , J. L. van Meerbergen , J. A. G. Jess, A constraint driven approach to loop pipelining and register binding, Proceedings of the conference on Design, automation and test in Europe, p.377-383, February 23-26, 1998, Le Palais des Congrés de Paris, France
|
|
|
|
|
|
R. Govindarajan , Erik R. Altman , Guang R. Gao, Minimizing register requirements under resource-constrained rate-optimal software pipelining, Proceedings of the 27th annual international symposium on Microarchitecture, p.85-94, November 30-December 02, 1994, San Jose, California, United States
|
|
|
Bart Mesman , Marino T. J. Strik , Adwin H. Timmer , Jef L. van Meerbergen , Jochen A. G. Jess, Constraint analysis for DSP code generation, Proceedings of the 10th international symposium on System synthesis, p.33-40, September 17-19, 1997, Antwerp, Belgium
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.4