Optimal processor-time tradeoffs on massively parallel memory-based architectures

Hussein M. Alnuweiri*, V. K. Prasanna Kumar

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationProc 3 Symp Front Massively Parallel Comput Frontiers 90
PublisherPubl by IEEE
Pages278-281
Number of pages4
ISBN (Print)0818620536
Publication statusPublished - 1990
Externally publishedYes
EventProceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90 - College Park, MD, USA
Duration: 8 Oct 199010 Oct 1990

Publication series

NameProc 3 Symp Front Massively Parallel Comput Frontiers 90

Conference

ConferenceProceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90
CityCollege Park, MD, USA
Period8/10/9010/10/90

Fingerprint

Dive into the research topics of 'Optimal processor-time tradeoffs on massively parallel memory-based architectures'. Together they form a unique fingerprint.

Cite this