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 language | English (US) |
---|---|
Title of host publication | Proc 3 Symp Front Massively Parallel Comput Frontiers 90 |
Publisher | Publ by IEEE |
Pages | 12-21 |
Number of pages | 10 |
ISBN (Print) | 0818620536 |
State | Published - Dec 1 1990 |
Event | Proceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90 - College Park, MD, USA Duration: Oct 8 1990 → Oct 10 1990 |
Other
Other | Proceedings of the 3rd Symposium on the Frontiers of Massively Parallel Computation - Frontiers '90 |
---|---|
City | College Park, MD, USA |
Period | 10/8/90 → 10/10/90 |
All Science Journal Classification (ASJC) codes
- Engineering(all)