Share Email Print

Proceedings Paper

Linear Array For Efficient Execution Of Partitioned Matrix Algorithms
Author(s): Jaime H. Moreno; Tomas Lang
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

We propose a class-specific linear array suitable for partitioned execution of matrix algorithms, which achieves high efficiency, exploits pipelining within cells in a simple manner, has off cells communication rate lower than computation rate, and has a small storage per cell (whose size is independent of the size of problems). This array is well suited to use the MMG method, a data-dependency graph-based mapping technique. The MMG method has capabilities to realize fixed-size data and partitioned problems as algorithm-specific arrays, and to map algorithms onto class-specific arrays. The array proposed here uses the mapping capabilities of the method, which combine coalescing and cut-and-pile as partition strategies. Mapping is illustrated using the LU-decomposition algorithm; results obtained from mapping other algorithms are also indicated. Performance estimates of the mappings show that, for example, LU-decomposition of a 2000 by 2000 matrix computed in a linear array with 100-cells, two operation units per cell in a 4-stage pipeline, and 50 [nsec] clock period (i.e., 4000 [Mflops]), achieves 87% efficiency (3480 [Mflops]). This performance is obtained while requiring communication among cells of only 5 [Mwords/sec] and peak external I/O bandwidth for the entire array also of 5 [Mwords/sec]. Moreover, for a problem of this size, the use of cut-and-pile leads to storage requirements of only 8000 words per memory module.

Paper Details

Date Published: 6 December 1989
PDF: 16 pages
Proc. SPIE 1154, Real-Time Signal Processing XII, (6 December 1989); doi: 10.1117/12.962376
Show Author Affiliations
Jaime H. Moreno, University of California Los Angeles (United States)
Tomas Lang, University of California Los Angeles (United States)

Published in SPIE Proceedings Vol. 1154:
Real-Time Signal Processing XII
J. P. Letellier, Editor(s)

© SPIE. Terms of Use
Back to Top