Browse Prior Art Database

REMOVING ALGORITHM IRREGULARITIES IN THE DESIGN OF ARRAYS FOR MATRIX COMPUTATIONS

IP.com Disclosure Number: IPCOM000128350D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 42K

Publishing Venue

Software Patent Institute

Related People

Jaime H. Moreno: AUTHOR [+4]

Abstract

We address some irregularities in matrix algorithms, as part of a systematic design methodology for arrays of processing elements (PEs) that we are researching. We propose a procedure to reduce the number of nodes in the fully-parallel dependence graph of matrix algorithms. We identify some irregularities which complicate such reduction of nodes and propose transformations to the dependence graph to remove them. The graphs obtained from such transformations are suitable for further transformations aimed towards regular algorithms or for direct implementation as arrays of PEs. The irregularities considered are bi-directional broadcasting and non-regular interconnection pattern between levels of the dependence graph. We use LU-decomposition, without and with pivoting, as examples of application of our transformations. The methodology results in triangular arrays for this computation, with better utilization than square arrays formerly proposed for it.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

REMOVING ALGORITHM IRREGULARITIES IN THE DESIGN OF ARRAYS FOR MATRIX COMPUTATIONS

Jaime H. Moreno Tomas Lang August 1987 CSD-870040 _~.- _~.

Removing Algorithm Irregularities in the Design-of Arrays for Matrix Computations Jaime H. Moreno, Tomas Lang Computer Science Department University of California, Los Angeles

Report No. CSD-870040* August 1987 'This research has been supported in part by the Office of Naval Research, Contract N00014-83-K-0493 "Specifications and Design Methodologies for High-Speed Fault-Tolerant Algorithms and Structures for VLSI."

Abstract

We address some irregularities in matrix algorithms, as part of a systematic design methodology for arrays of processing elements (PEs) that we are researching. We propose a procedure to reduce the number of nodes in the fully-parallel dependence graph of matrix algorithms. We identify some irregularities which complicate such reduction of nodes and propose transformations to the dependence graph to remove them. The graphs obtained from such transformations are suitable for further transformations aimed towards regular algorithms or for direct implementation as arrays of PEs. The irregularities considered are bi-directional broadcasting and non-regular interconnection pattern between levels of the dependence graph. We use LU-decomposition, without and with pivoting, as examples of application of our transformations. The methodology results in triangular arrays for this computation, with better utilization than square arrays formerly proposed for it.

1 Introduction

?Matrix computations are the basis for many applications in science and engineering. Examples exist in image and signal processing, pattern recognition, control systems, among others. The evolution in VLSI technology is making possible the cost-effective implementation of many matrix algorithms as a collection of regularly connected processing elements (PEs).

An important problem in the design of arrays of PEs for a given algorithm is the methodology used to derive the structure and interconnection of those arrays. Standard structures (systolic arrays (1J) have been used for these implementations, but they might be non-optimal for a partic-ular algorithm. Some transformational methodologies have been proposed (2J, which either restrict the form of the algorithm (i.e., a recurrence equation) or are unable to incorporate certain imple-mentation restrictions, such as number of I/O pads, limited data broadcasting, or lower bound on efficiency.

We are researching a general and systematic design methodology for matrix algorithms, with the capability to handle and relate features of the algorithm and the implementation in a unified manner [3J. We have applied a preliminary version of this methodology to the algorithms for matrix multiplication and LU-decomposition [4J. This methodology is based on the dependence graph of the algorithms and provides mechan...