OPTIMAL PROCESSOR-TIME TRADEOFFS ON MASSIVELY PARALLEL MEMORY-BASED ARCHITECTURES Conference Paper uri icon

abstract

  • 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.

name of conference

  • [1990 Proceedings] The Third Symposium on the Frontiers of Massively Parallel Computation

published proceedings

  • 3RD SYMPOSIUM ON THE FRONTIERS OF MASSIVELY PARALLEL COMPUTATION

author list (cited authors)

  • ALNUWEIRI, H. M., & KUMAR, V.

citation count

  • 0

complete list of authors

  • ALNUWEIRI, HM||KUMAR, VKP

publication date

  • January 1990