__ Page 1 of 34 __
**MATHEMATICAL REPRESENTATION ****FOR ****VLSI ARRAYS **

**by **

**URI WEISER **

**and **

**ALAN ****L. DAVIS**

UUCS **- ****80 ****- ****111 **

**Department of Computer Science **

University of Utah

Salt **Lake ****City, Utah 84112 **

**SEPTEMBER 1980 **

**This work was supported under the Data Driven Research Project grant**

provided by Burroughs Corporation.

__ [This page contains 1 picture or other non-text object] __
__ Page 2 of 34 __
__ [This page contains 1 picture or other non-text object] __
__ Page 3 of 34 __
**Table ****of ****Contents **

1 **INTRODUCTION**

**2 ****MATHEMATICAL PRESENTATION ****OF ****SEQUENCES **

2.1 **THE D OPERATOR**

**3 ****ONE DIMENSIONAL ARRAYS **

3 . 1 MATRIX-VECTOR MULTIPLICATION

**3.2 ****SOLVING TRIANGULAR LINEAR SYSTEMS **

4 **TWO DIMENSIONAL ARRAYS **

**4.1 ****BAND MATRIX MULTIPLICATION **

4.1.1 **G e n e r a l ****approach **

4.1.2 **C o n s t r u c t i o n of ****the ****n e t w o r k . **

4.2 **SOLVING A SET OF ****TRIANGULAR ****LINEAR SYSTEMS **

**4.2.1 ****CASE ****1: ****A X **= **Y, ****w h e r e A ****is ****a ****triangular ****band ****m a t r i x , ****and ****X ****and Y ****are full ****m a t r i c e s **

4.2.2 **CASE **2: A **X **= **Y **, **w h e r e A, X and ****Y ****are all ****band ****m a t r i c e s **

**5 ****CONCLUSIONS **

I. **Number ****of ****multiplications ****in Matrix: ****Multiplication **

__ [This page contains 1 picture or other non-text object] __
__ Page 4 of 34 __
__ [This page contains 1 picture or other non-text object] __
__ Page 5 of 34 __
List of Figures

Figure 1: Two steps Transformation

Figure 2: The delay element leq. (111.

Figure 3: The system z=F(x,y)

Figure **4: **row feeding of full matrix B

Figure 5: Multiplication of a band matrix by a vector [eq. (411.

Figure 6: Matrix-vector multiplication network [eq. (711.

Figure 7: **The **basic block P

Figure 8: Matrix-vector multiplication network using the basic block P

Ceq. (711.

Figure **9: **Triangular linear system network [eq. (lo)].

Figure 10: Triangular linear system network using the basic block P [eq.

Cl0)I.

Figure 11: Triangular linear system network using the basic block P Ceq.

**(1311. **

Figure 12: Band matr i.2 mu1 tiplication

Figure **13: **Wavefront C and **D[~I **

Figure 14: Orientation of **1 **and *2. *

Figure 15: Tne stream of data of the partial results of Y

Figure 16: Band matrix multiplication, output Y i n colunns Ceq. (17)l. Figure **17: **Band matrix multiplication, producing the output Y in colunns

Ceq. (2011.

Figure 18: Solution for a set of simultaneous equations, when **A **is a triangular band matrix and X and Y are full matrices leg. (2311%

Figure 19: Solution for a set of simultaneous equations, when **A, **X and Y are band matrices, using the basic block P [eq. (27)l.

Figure 20: Processor array for solving a set of triangular linear systems, when A, X and Y are band matrices, using the basic block P [eq. (3011.

Figure 21: Number of multiplications needed to calculate the set **Q **

__ [This page contains 1 picture or other non-text object] __
__ Page 6 of 34 __
__ [This page contains 1 picture or other non-text object] __
__ Page 7 of 34 __
**1 ****INTRODUCTION **

This paper introduces a methodology for mapping algorithmic description into a concurrent implementation on silicon. This...