### The physical mapping problem for parallel architecturesThe physical mapping problem for parallel architectures

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

Source: ACM Digital Library