Thumbnail
Access Restriction
Subscribed

Author Heath, Lenwood S. ♦ Rosenberg, Arnold L. ♦ Smith, Bruce T.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1988
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The problem of realizing an idealized parallel architecture on a (possibly fault-laden) physical architecture is studied. Our formulation performs the mapping in the light of the algorithm that one wants to implement on the idealized architecture. A version of the mapping algorithm suggested by the DIOGENES methodology for designing fault-tolerant VLSI processor arrays is settled definitely. Two quality metrics for mappings are considered, the first embodying an idealized notion of average delay, which relates to power consumption, and the second being the length of the longest run of wire. For the average-delay measure, four algorithms that optimally assign the $\textit{m}$ vertices of the embedded graph to the $\textit{n}$ fault-free processors that have been fabricated are presented. The most general algorithm makes no assumptions about the structure of the array or the physical format of the processors; it runs in time $\textit{O}(\textit{m}$ · $(\textit{n}$ - $\textit{m})2).$ The other algorithms assume that the processors are laid out in such a way that interprocessor distances obey the triangle equality; they run in times ranging from time $\textit{O}(max{\textit{m},$ $\textit{n}$ - $\textit{m}}$ · log min {m, n - m}) for certain array structures, including linear arrays, to time $\textit{O}(max{\textit{m,$ n - m}) for a narrow class of array structures, including pyramid arrays. For the max-wire-run cost measure, it is shown that the problem of finding cost-optimal vertex-to-processor assignments is NP-complete. However, an algorithm is presented that yields, in time $\textit{O}(\textit{m}$ · (n - m)2), vertex-to-processor assignments that are within a factor of 3 of optimal (they are optimal when the input graph-embedding is outplanar). This algorithm can easily be converted to one that yields, in time $\textit{O}(\textit{m}$ · (n - m)3), vertex-to-processor assignments that are within a factor of 2 of optimal. Finally, an algorithm that yields optimal assignments when the interprocessor distances obey the triangle equality is presented; this algorithm operates in time $\textit{O}(\textit{m}$ · (n - m) · $log(\textit{m}$ · (n - m)) · log $\textit{M}),$ where $\textit{M}$ is the largest interprocessor distance.
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 1988-06-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 35
Issue Number 3
Page Count 32
Starting Page 603
Ending Page 634


Open content in new tab

   Open content in new tab
Source: ACM Digital Library