Unified Interprocedural Parallelism Detection

Abstract

In this paper. we outline a new way of detecting parallelism interprocedurally within a program. Our method goes beyond mere dependence testing, to embrace methods of removing dependences as well, namely privatization, induction recognition and reduction recognition. This method is based on a combination of techniques: a "universal" form for representing memory accesses within a section of code (the Lineal memory Access Descriptor), a technique for classifying memory locations based on the accesses made to them by the code (Memory Classification Analysis), and a dependence test (the Access Region Test). The analysis done with Linear Memory Access Descriptors is based on an intersection operation, for which we present an algorithm. Linear Memory Access Descriptors are independent of any declarations that may exist in a program, so they are subroutine- and language-independent. This makes them ideal for use in interprocedural analysis. Our experiments indicate that this test is highly effective for parallelizing loops containing very complex subscript expressions.