Toward scalable algorithms for orthogonal shared-memory parallel computers

Isaac D. Scherson, Ashish Mehra, Jennifer L. Rexford

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The problem of developing scalable and near-optimal algorithms for orthogonal shared-memory multiprocessing systems with a multidimensional access (MDA) memory array is considered. An orthogonal shared-memory system consists of 2n processors and 2m memory modules accessed in any one of m possible access modes. Data stored in memory modules are available to processors under a mapping rule that allows conflict-free data reads and writes for any given access mode. Scalable algorithms are presented for two well-known computational problems, namely, matrix multiplication and the fast Fourier transform (FFT). A complete analysis of the algorithms based on computational time and the access modes needed is also presented. The algorithms scale very well onto higher dimensional MDA architectures but are not always optimal. This reveals a tradeoff between the scalability of an algorithm and its optimality in the MDA computational model.

Original languageEnglish (US)
Title of host publicationProc 3 Symp Front Massively Parallel Comput Frontiers 90
PublisherPubl by IEEE
Pages12-21
Number of pages10
ISBN (Print)0818620536
StatePublished - Dec 1 1990
EventProceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90 - College Park, MD, USA
Duration: Oct 8 1990Oct 10 1990

Other

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

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Toward scalable algorithms for orthogonal shared-memory parallel computers'. Together they form a unique fingerprint.

  • Cite this

    Scherson, I. D., Mehra, A., & Rexford, J. L. (1990). Toward scalable algorithms for orthogonal shared-memory parallel computers. In Proc 3 Symp Front Massively Parallel Comput Frontiers 90 (pp. 12-21). Publ by IEEE.