An Efficient Allocation Strategy for Mapping Affine Recurrences into Space and Time Optimal Regular Processor Arrays

This paper adresses the problem of efficient mappings of nested loops, and more generally of systems of affine recurrence equations, into regular arrays. The presented technique is based on the transformation of an initial systolic mapping. By studying the processor element (PE) activity, a nearly space-optimal mapping is designed by serializing the computations of several initial PEs into a single one. A new approach of this technique is presented. It allows to map into regular arrays which may be nonplanar. Moreover, the solutions can be linearly time-optimal since this technique does not affect the initial schedule. The methodology is illustrated by the LL T Cholesky factorization. 1 Introduction Distributed memory multiprocessors are attractive to their scalability, flexibility and performance but suffer from a lack of efficient methods for mapping algorithms into such parallel architectures. A large number of algorithms in signal and data processing applications can be..