Linear Array For Efficient Execution Of Partitioned Matrix Algorithms

Jaime H. Moreno; Tomas Lang

doi:10.1117/12.962376

6 December 1989 Linear Array For Efficient Execution Of Partitioned Matrix Algorithms

Jaime H. Moreno, Tomas Lang

Proceedings Volume 1154, Real-Time Signal Processing XII; (1989) https://doi.org/10.1117/12.962376
Event: 33rd Annual Technical Symposium, 1989, San Diego, United States

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.

Citation Download Citation

Jaime H. Moreno and Tomas Lang "Linear Array For Efficient Execution Of Partitioned Matrix Algorithms", Proc. SPIE 1154, Real-Time Signal Processing XII, (6 December 1989); https://doi.org/10.1117/12.962376

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available