TY - GEN
T1 - Optimal processor-time tradeoffs on massively parallel memory-based architectures
AU - Alnuweiri, Hussein M.
AU - Prasanna Kumar, V. K.
PY - 1990
Y1 - 1990
N2 - Processor-time-optimal algorithms are presented for several image and graph problems on a parallel architecture that combines an orthogonally accessed memory with a linear array structure. The organization has p processors and a memory of size Θ(n2) locations. The number of processors p can vary over a wide range while providing processor-time-optimal algorithms for sorting and for several problems from graph theory, computational geometry, and image analysis. Sorting and geometric problems can be solved in O((n2/p) log n + n) time, which is optimal for p in the range [1, n log n]. Graph and image problems can be solved in O(n2/p + n1/2) time, which is optimal for p in the range [1, n3/2]. The algorithms implemented on the proposed architecture have processor-time products superior to those of the mesh and pyramid computer algorithms.
AB - Processor-time-optimal algorithms are presented for several image and graph problems on a parallel architecture that combines an orthogonally accessed memory with a linear array structure. The organization has p processors and a memory of size Θ(n2) locations. The number of processors p can vary over a wide range while providing processor-time-optimal algorithms for sorting and for several problems from graph theory, computational geometry, and image analysis. Sorting and geometric problems can be solved in O((n2/p) log n + n) time, which is optimal for p in the range [1, n log n]. Graph and image problems can be solved in O(n2/p + n1/2) time, which is optimal for p in the range [1, n3/2]. The algorithms implemented on the proposed architecture have processor-time products superior to those of the mesh and pyramid computer algorithms.
UR - http://www.scopus.com/inward/record.url?scp=0025563960&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0025563960
SN - 0818620536
T3 - Proc 3 Symp Front Massively Parallel Comput Frontiers 90
SP - 278
EP - 281
BT - Proc 3 Symp Front Massively Parallel Comput Frontiers 90
PB - Publ by IEEE
T2 - Proceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90
Y2 - 8 October 1990 through 10 October 1990
ER -