Hierarchical algorithm partitioning at system level for an improved utilization of memory structures

The object of algorithm design in context with a hierarchically structured memory system is a reduction of access cycles to higher memory levels by an increase of data reuse from levels closer to execution units. The object o f our approach is to systematically construct an algorithm coding, starting from a weak single assignment form, so that parameters of the algorithm co de (number and type of partitions, scheduling orders) can be directly mappe d on parameters of the architecture (number of memory levels, size of the m emories, input/output access behavior) and vice versa. Target architectures are processors with from one up to a few execution units and with a hierar chically structured memory system. The approach is based on methods derived from the realm of array synthesis and consists of a recursively defined al gorithm partitioning. An approach to a quantitative determination of data r euse in recursively partitioned algorithms is given.