Loop partitioning refers to this stage of the parallelisation process which deals with the formation of groups of loop iterations that can be executed in parallel; using a scheduling scheme, these groups are assigned to processors. Partitioning and scheduling constitute a fundamental problem to be solved on parallel computers [13]; this is generally termed as mapping. When mapping loop nests, it is essential to minimise overheads, such as load imbalance, communication, etc., thus increasing performance. Traditionally, researchers have been inclined towards run-time mapping schemes, on the basis that information not available at compile-time may permit a more balanced distribution of the workload [4], [9], [10], [15]. However, the latter may be achieved at the expense of additional overheads; furthermore, in the context of parallelising compilers, where a number of decisions are taken at compile-time, postponing the mapping phase until run-time may seriously affect the applicability of program restructuring transformations.
In this paper we describe a scheme for compile-time partitioning of loop nests comprising two inner nested loops both of which have bounds linearly dependent on the index of the outermost parallel loop. The main target is the minimisation of load imbalance, however, an attempt is also made to avoid options that may increase other sources of overhead. Load imbalance is estimated using symbolic analysis techniques for enumerating loop iterations; they are briefly introduced in section 2. Based on these, section 3 provides a description of the partitioning scheme, while preliminary experimental results on a virtual shared memory parallel computer demonstrate the efficiency of the method over other compile-time schemes.