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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references