|
 ABSTRACT
A set equations in the quantities ai(p), where i = 1, 2, · · ·, m and p ranges over a set R of lattice points in n-space, is called a system of uniform recurrence equations if the following property holds: If p and q are in R and w is an integer n-vector, then ai(p) depends directly on aj(p - w) if and only if ai(q) depends directly on aj(q - w). Finite-difference approximations to systems of partial differential equations typically lead to such recurrence equations. The structure of such a system is specified by a dependence graph G having m vertices, in which the directed edges are labeled with integer n-vectors. For certain choices of the set R, necessary and sufficient conditions on G are given for the existence of a schedule to compute all the quantities ai(p) explicitly from their defining equations. Properties of such schedules, such as the degree to which computation can proceed “in parallel,” are characterized. These characterizations depend on a certain iterative decomposition of a dependence graph into subgraphs. Analogous results concerning implicit schedules are also given.
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
|
BERGE, C. The Theory of Graphs and It8 Applications. Wiley, New York, 1962.
|
| |
2
|
DANTZm, G. B. Linear Programming and Extensions. Princeton U. Press, Princeton, N, J., 1963.
|
| |
3
|
GOMORY, R. E. On the relation between integer and noninteger solutions to linear programs. Proc, Nat. Acad. Sci. 58, 2 (Feb. 1965), 260--265.
|
| |
4
|
GOOD, I .J . Normal recurring decimals. J. London Math. Soc. Zl (1946), 167-169.
|
| |
5
|
JEENEL, J. Programs as a tool for research in systems organization. IBM J. 2, 2 (April 1958), 105--122.
|
| |
6
|
KaRP R. M., AND MILLER, R.E. Properties of a model for parallel computations: determinacy, termination, queueing. SIAM J. Appl. Math. iS, 6 (Nov. 1966), 1390-1411.
|
| |
7
|
THOMAS, J.M. Orderly differential systems. Duke MaTh. J. 7 (Dec. 1940), 249-290.
|
CITED BY 89
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Patrice Quinton , Tanguy Risset, Structured scheduling of recurrence equations: theory and practice, Embedded processor design challenges: systems, architectures, modeling, and simulation-SAMOS, Springer-Verlag New York, Inc., New York, NY, 2002
|
|
|
|
|
|
|
|
|
|
|
|
Stephan Balev , Patrice Quinton , Sanjay Rajopadhye , Tanguy Risset, Linear programming models for scheduling systems of affine recurrence equations—a comparative study, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.250-258, June 28-July 02, 1998, Puerto Vallarta, Mexico
|
|
|
|
|
|
|
|
|
|
|
|
Pierrick Gachet , Christophe Mauras , Patrice Quinton , Yannick Saouter, Alpha du centaur: a prototype environment for the design of parallel regular alorithms, Proceedings of the 3rd international conference on Supercomputing, p.235-243, June 05-09, 1989, Crete, Greece
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
M. V. Marathe , H. B. Hunt, III , R. E. Stearns , V. Radhakrishnan, Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.468-477, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Francisco Almeida , Rumen Andonov , Daniel Gonzalez , Luz M. Moreno , Vincent Poirriez , Casiano Rodriguez, Optimal tiling for the RNA base pairing problem, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
Jürgen Teich , Lothar Thiele, Exact partitioning of affine dependence algorithms, Embedded processor design challenges: systems, architectures, modeling, and simulation-SAMOS, Springer-Verlag New York, Inc., New York, NY, 2002
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Marcus Bednara , Frank Hannig , Jürgen Teich, Generation of distributed loop control, Embedded processor design challenges: systems, architectures, modeling, and simulation-SAMOS, Springer-Verlag New York, Inc., New York, NY, 2002
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Youcef Bouchebaba , Bruno Girodias , Gabriela Nicolescu , El Mostapha Aboulhamid , Bruno Lavigueur , Pierre Paulin, MPSoC memory optimization using program transformation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.4, p.43-es, September 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Clémentin Tayou Djamegni , Patrice Quinton , Sanjay Rajopadhye , Tanguy Risset , Maurice Tchuenté, A reindexing based approach towards mapping of DAG with affine schedules onto parallel embedded systems, Journal of Parallel and Distributed Computing, v.69 n.1, p.1-11, January, 2009
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.2