Search

Irregular computation by a High Performance Fortran compiler is accomplished effectively using a method in which a set of compiler directives invoke a user specified mapping procedure. Graph connectivity, spatial distribution of array elements and computational load are explained by program arrays. Another method is a conservative irregular loop compilation method in which previously calculated information, from inspectors, can be reused by the complier.

This paper proposes a simple yet efficient algorithm to distribute loads evenly on multiprocessor computers with hypercube interconnection networks. This algorithm was developed based upon the well-known dimension exchange method. However, the error accumulation suffered by other algorithms based on the dimension exchange method is avoided by exploiting the notion of regular distributions, which are commonly deployed for data distributions in parallel programming. This algorithm achieves a perfect load balance over P processors with an error of 1 and the worst-case time complexity of O(M log2P), where M is the maximum number of tasks initially assigned to each processor. Furthermore, perfect load balance is achieved over subcubes as well—once a hypercube is balanced, if the cube is decomposed into two subcubes by the lowest bit of node addresses, then the difference between the numbers of the total tasks of these subcubes is at most 1. [ABSTRACT FROM AUTHOR]