Geometrical tools to map systems of affine recurrence equations on regular arrays (Q1323382)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Geometrical tools to map systems of affine recurrence equations on regular arrays |
scientific article |
Statements
Geometrical tools to map systems of affine recurrence equations on regular arrays (English)
0 references
10 May 1994
0 references
We propose a method based on geometrical tools to map problems onto regular and synchronous processor arrays. The problems we consider are defined by systems of affine recurrence equations. From such a problem specification we extract the data dependencies in terms of two classes of vectors: the utilization vectors and the dependence vectors. We use these vectors to express constraints on the timing or the allocation functions. We differentiate two classes of constraints. The causal ones are intrinsic timing constraints induced by the system of equations defining the problem. A given choice of target architecture may impose new constraints on the timing or the allocation. We call them the architecture-related constraints. We use these constraints to determine first an affine timing function and next an allocation by projection. We finally illustrate the method with three examples: the matrix multiplication, the recursive convolution and the LL\(^ t\) Cholesky factorization.
0 references
regular arrays
0 references
synchronous processor arrays
0 references
affine recurrence equations
0 references
matrix multiplication
0 references
recursive convolution
0 references
LL\(^ t\) Cholesky factorization
0 references
0 references
0 references