Abstract
Affine space-time mappings have been extensively studied for systolic array design and parallelizing compilation. However, there are practical important cases that require other types of transformations. This paper considers so-called modular mappings described by linear transformations modulo a constant vector. Sufficient conditions for these mappings to be one-to-one are investigated for rectangular domains of arbitrary dimensions. It is shown that a sufficient condition for a modular mapping to be one-to-one is that its (n x n) coefficient -matrix T has entries tii = k1 and tij = 0 for i > j where > is a total order on {1, 2,. ., n), n = domain dimension. These conditions are strengthened and extended for particular types of rectangular domains and a.ffine transformations modulo a coinstant vector. The results of this paper can be used to identify a space of valid modular mappings of specific algorithms into time and space. They are illustrated by examples which include Cannon's matrix multiplication algorithm.
Date of this Version
June 1994