Optimization of the background memory utilization by partitioning

The skilful utilization of the memory structure of a processor and of its background memory may crucially affect the system performance. We propose a restructuring of for-loop programs by hierarchical partitioning, which improves the properties of the algorithm with respect to the memory utilization. We consider the problem for regularly connected processor arrays (where single processors are a special case) and for a memory structure which is subdivided into a local foreground memory (register) and a background memory with up to three levels (cache, RAM, mass storage). The extension of the lifetime of a variable on an inner memory level, i.e. the reduction of the number of read accesses to the more outer memory levels, is the object of the proposed method