Efficient Loop Scheduling and Pipelining for Applications with Non-Uniform Loops

Using parallel processing systems to compute scientific applications is one of the most common solutions for achieving more efficient computing performance. In some applications such as fluid mechanics, structural analysis, solid state simulations, the dependencies across iterations (loop-carried dependencies) of the computation of array elements may be constants (uniform) or functions of array indices (non-uniform). Traditional scheduling can efficiently generate an optimized schedule for applications with any uniform dependencies. However, non-uniform dependencies of array elements in those applications may cause the scheduler to produce an inefficient result. This paper presents a new scheduling methodology for both uniform and non-uniform dependency loops, considering a limited number of target processors. A loop pipelining technique, called rotation scheduling, is used as the basis for our algorithm to overlap operations in the loops, taking into account the various forms of loop-..