# MATHEMATICAL REPRESENTATION FOR VLSI ARRAYS

Original Publication Date: 1980-Sep-30

Included in the Prior Art Database: 2007-Apr-24

## Publishing Venue

Software Patent Institute

## Related People

Wieser, Uri: AUTHOR [+2]

## Abstract

by URI WEISER and ALAN L. DAVIS UUCS 80 111 Department of Computer Science University of UtahSalt Lake City, Utah 84112 SEPTEMBER 1980 This work was supported under the Data Driven Research Project grant provided by Burroughs Corporation. 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 List of Figures Figure 1: Two steps TransformationFigure 2: The delay element leq. (111.

**This text was extracted from a PDF file.**

**At least one non-text object (such as an image or picture) has been suppressed.**

**This is the abbreviated version, containing approximately 9% of the total text.**

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

**by **

**URI WEISER **

**and **

**ALAN ****L. DAVISUUCS **

**-**

**80**

**-**

**111**

**Department of Computer Science University of UtahSalt **

**Lake**

**City, Utah 84112**

**SEPTEMBER 1980 **

**This work was supported under the Data Driven Research Project grantprovided 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...