An efficient uniform run-time scheme for mixed regularirregular applications

Almost all applications containing indirect array address-ing (irregular accesses) have a substantial number of direct array accesses (regular accesses) too. A conspicuous per-centage of these direct array accesses usually require inter-processor communication for the applications to run on a distributed memory multicomputer. This study highlights how lack of a uniform representation and lack of a uniform scheme to generate communication structures and parallel code for regular and irregular accesses in a mixed regular-irregular application prevent sophisticated optimizations. F-urthermore, we also show that code generated for regular accesses using compile-time schemes are not alzvays compat-ible to code generated for irregular accesses using run-time schemes. In our opinion, existing schemes handling mixed regular-irregular applications either incur unnecessary pre-processing costs or fail to perform the best communication optimization. This study presents a uniform scheme to han-dle both regular and irregular accesses in a mixed regular-irregular application. While this allows for sophisticated communication optimizations such as message coalescing, message aggregation to be made across regular and irregu-lar accesses, the preprocessing costs incurred are likely to be minimum. Experimental comparisons for various bench-marks on a 16-processor IBM SP-2 show that our scheme is feasible and better than existing schemes.