Title :
Optimal hot spot allocation on meshes for large-scale data-parallel algorithms
Author :
Lee, Soo-Young ; Chen, Chung-Ming
Author_Institution :
Sch. of Electr. Eng., Cornell Univ., Ithaca, NY, USA
fDate :
8/1/1995 12:00:00 AM
Abstract :
Hot spots are notorious for degrading the performance of a parallel algorithm. We attempt to minimize the hot-spot access time for a class of problems, namely, Large-Scale Data-Parallel (LSDP) algorithms, on a 2D mesh. An LSDP algorithm has rich data parallelism but without exclusive task and data partitioning. Our approach is to allocate the hot spots at the optimal locations such that the hot-spot access time is minimized. Also, we have designed scheduling algorithms which control hot spot access sequences to achieve the minimal access time. Both uniform and nonuniform hot spots have been considered in this study. We have analytically derived the optimal allocations for wrapped-around and non-wrapped-around square meshes. The theoretical results have been verified by parallelizing the EM algorithm for 3D PET image reconstruction on the Intel iPSC/860
Keywords :
image reconstruction; medical image processing; mesh generation; optimisation; parallel algorithms; positron emission tomography; processor scheduling; scheduling; 3D PET image reconstruction; Intel iPSC/860; data parallelism; exclusive data partitioning; exclusive task partitioning; hot spot allocation; large-scale data-parallel algorithms; meshes; nonwrapped-around square meshes; optimal hot spot allocation; positron emission tomography; scheduling algorithms; wrapped-around square meshes; Computational modeling; Computer Society; Degradation; Delay; Large-scale systems; Parallel algorithms; Parallel processing; Partitioning algorithms; Positron emission tomography; Scheduling algorithm;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
