Access Restriction

Author Karp, Richard M. ♦ Miller, Raymond E. ♦ Winograd, Shmuel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1967
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A set equations in the quantities $\textit{ai}(\textit{p}),$ where $\textit{i}$ = 1, 2, · · ·, $\textit{m}$ and $\textit{p}$ ranges over a set $\textit{R}$ of lattice points in $\textit{n}-space,$ is called a system of uniform recurrence equations if the following property holds: If $\textit{p}$ and $\textit{q}$ are in $\textit{R}$ and $\textit{w}$ is an integer $\textit{n}-vector,$ then $\textit{ai}(\textit{p})$ depends directly on $\textit{aj}(\textit{p}$ - $\textit{w})$ if and only if $\textit{ai}(\textit{q})$ depends directly on $\textit{aj}(\textit{q}$ - $\textit{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 $\textit{m}$ vertices, in which the directed edges are labeled with integer $\textit{n}-vectors.$ For certain choices of the set $\textit{R},$ necessary and sufficient conditions on $\textit{G}$ are given for the existence of a schedule to compute all the quantities $\textit{ai}(\textit{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.
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 1967-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 14
Issue Number 3
Page Count 28
Starting Page 563
Ending Page 590

Open content in new tab

   Open content in new tab
Source: ACM Digital Library