Browse Prior Art Database

MATHEMATICAL REPRESENTATION FOR VLSI ARRAYS

IP.com Disclosure Number: IPCOM000152078D
Original Publication Date: 1980-Sep-30
Included in the Prior Art Database: 2007-Apr-24
Document File: 34 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Wieser, Uri: AUTHOR [+3]

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. 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...