الفهرس 
AcknowledgementOnly 14 pages are availabe for public view
 |  | from | 133 |  |  |
| | | from | 133 | | |
Abstract
’This thesis is concerned with the synthesis of systolic
for a class of uniform recurrence equations. Equations in class have the features that one variable is computed using tative and associative operators and the other variables propagating variables. By exploiting these features,arrays with high performance or optimized area are
5 i z e d .
The thesis is divided into two parts. In the first part, a ily of systolic arrays for the matrix multiplication
aic=rithm are synthesized. The arrays exploit the available 1/0 iaz-a4width. They are optimal in storage and time. The computation time decreases as the 1/0 bandwidth increases whereas the number of processing elements (PEs) are of the same order.
In the second part, we present several previous approaches
design methodology of systolic arrays. The transformation matrix technique, found in the literature, is adopted for :acing these approaches in a unified framework so that
approaches are related in a formal way.
The adopted technique is extended to improve the ===putation time or solve large size algorithms. One (or more) dependence vector, of the algorithm’s dependence matrix, is
7 ;
--t into two or more dependence vectors. This split extends
e dimension of the dependence matrix and consequently the -.mension of the index space. Valid transformation matrices are,
found. These matrices map the extended dependence matrix =nto multidimensional systolic arrays. Conditions of correctness ire given to characterize the validity of the transformation -.at-rices. Also, an algorithm is provided to derive such systolic arrays. With respect to computation time, the derived systolic ;trays outperform their 1-D counterpart that of the same order :n space complexity. Also, we derive smaller size arrays that are able to solve larger size algorithms.