TY - GEN
T1 - Parallel convexity algorithms for digitized images on a linear array of processors
AU - Alnuweiri, Hussein M.
AU - Prasanna Kumar, V. K.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1990.
PY - 1990
Y1 - 1990
N2 - Efficient implementation of global computations on a, linear array of processors is complicated due to the small communication bandwidth and the large communication diameter of the array. This paper presents efficient parallel techniques for partitioning, movement, and reduction of data on linear arrays. Also, efficient data structures are used to enable fast sequential access of query points within each processor. This combination of serial and parallel techniques is used to derive an optimal parallel algorithm for computing the convex hull of each connected region in an n × n image. The algorithm takes O(n2/p) time on a linear array with p processors, where 1 ≤ p ≤ n/logn. This result is processor-time optimal since an optimal sequential algorithm takes O(n2) to solve the problem. Thus, a linear array with n/log n processors can solve the above problem in O(nlogn) time. In comparison, a two dimensional mesh-connected array of processors can solve this problem in O(n) time using n2 processors. The processor-time product for the mesh is 0(n3), which is not optimal.
AB - Efficient implementation of global computations on a, linear array of processors is complicated due to the small communication bandwidth and the large communication diameter of the array. This paper presents efficient parallel techniques for partitioning, movement, and reduction of data on linear arrays. Also, efficient data structures are used to enable fast sequential access of query points within each processor. This combination of serial and parallel techniques is used to derive an optimal parallel algorithm for computing the convex hull of each connected region in an n × n image. The algorithm takes O(n2/p) time on a linear array with p processors, where 1 ≤ p ≤ n/logn. This result is processor-time optimal since an optimal sequential algorithm takes O(n2) to solve the problem. Thus, a linear array with n/log n processors can solve the above problem in O(nlogn) time. In comparison, a two dimensional mesh-connected array of processors can solve this problem in O(n) time using n2 processors. The processor-time product for the mesh is 0(n3), which is not optimal.
UR - http://www.scopus.com/inward/record.url?scp=85031809173&partnerID=8YFLogxK
U2 - 10.1007/3-540-52921-7_89
DO - 10.1007/3-540-52921-7_89
M3 - Conference contribution
AN - SCOPUS:85031809173
SN - 9783540529217
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 397
EP - 406
BT - Algorithms - International Symposium SlGAL 1990, Proceedings
A2 - lbaraki, Toshihide
A2 - Nishizeki, Takao
A2 - Imai, Hiroshi
A2 - Asano, Tetsuo
PB - Springer Verlag
T2 - 1st SIGAL International Symposium on Algorithms, 1990
Y2 - 16 August 1990 through 18 August 1990
ER -