Browse Prior Art Database

DECOUPLING THE DIMENSIONS OF A SYSTEM OF AFFINE RECURRENCE EQUATIONS

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

Publishing Venue

Software Patent Institute

Related People

Yoav Yaacoby: AUTHOR [+4]

Abstract

Most work on the problem of synthesizing a systolic array from a system of recurrence equations is restricted to systems of uniform recurrence equations. In this paper, this restriction is relaxed to include systems of afline recurrence equations. A system of uniform recurrence equations typically can be embedded in spacetime so that the distance between a variable and a dependent variable does not depend on the problem size. Systems of affine recurrence equations which are not uniform, do not enjoy this property. A method in another paper has been presented for converting a system of affine recurrence equations to an equivalent system of recurrence equations that is uniform, except for points near the boundaries of its index sets. In this paper a procedure is presented for decoupling the dimensions of the system of affine recurrence equations, thereby simplifying the conversion to an equivalent system that is uniform (except for points near the boundaries). Key Words: affine recurrence equation, concurrent computation, data dependence, decoupling, par-allel computation, processor array, systolic array, uniform recurrence equation.

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

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

DECOUPLING THE DIMENSIONS OF A SYSTEM OF AFFINE RECURRENCE EQUATIONS

Yoav Yaacoby Department of Electrical & Computer Engineering University of California Santa Barbara, CA Peter R. Cappellol Department of Computer Science University of California Santa Barbara, CA 93106

April 20, 1988

'This material is based upon work supported by the Office of Naval Research under contract nos. N00014-84-K-0664 and N00014-85-K-0553.

Abstract

Most work on the problem of synthesizing a systolic array from a system of recurrence equations is restricted to systems of uniform recurrence equations. In this paper, this restriction is relaxed to include systems of afline recurrence equations. A system of uniform recurrence equations typically can be embedded in spacetime so that the distance between a variable and a dependent variable does not depend on the problem size. Systems of affine recurrence equations which are not uniform, do not enjoy this property. A method in another paper has been presented for converting a system of affine recurrence equations to an equivalent system of recurrence equations that is uniform, except for points near the boundaries of its index sets. In this paper a procedure is presented for decoupling the dimensions of the system of affine recurrence equations, thereby simplifying the conversion to an equivalent system that is uniform (except for points near the boundaries).

Key Words: affine recurrence equation, concurrent computation, data dependence, decoupling, par-allel computation, processor array, systolic array, uniform recurrence equation.

I INTRODUCTION

An important property of any VLSI system is physical regularity. Systolic arrays [14,131 and wave-front arrays [15] have an iterative form of physical regularity. Array architecture is suited to VLSI technology; replicating a processing element reduces design cost, and neighbor communication be-tween processing elements reduces operation cost. Leiserson, Rose, and Saxe 117,16) show how to convert a finite network without zero-delay cycles to an equivalent network that functions systoli-cally (see also [271). Melhem and Rheinboldt 119) give a mathematical model for the verification of systolic networks.

A system of uniform recurrence equations, as defined by Karp, Miller, and Winograd [11,121, maps especially well onto a systolic/wavefront array. This is noted explicitly by Chen and Mead
[4), and Quinton [25), for example. Linearly mapping a system of recurrence equation's index sets into spacetime, has been pursued by Cappello and Steiglitz 11,2,31. Fortes et al. 19) survey seventeen methodologies for the design of systolic arrays. Systematic translation from either a program fragment or a system of uniform recurrence equations to systolic/wavefront arrays has been studied by Moldovan 12211211, Quinton [251, Winkler and Miranker [201,

University of California at Santa Barbara Page 1 Dec 31, 1988

Page 2...