LOOP PARALLELIZATION ALGORITHMS - FROM PARALLELISM EXTRACTION TO CODE

In this paper, we survey loop parallelization algorithms, analyzing th e dependence representations they use, the loop transformations they g enerate, the code generation schemes they require, and their ability t o incorporate various optimizing criteria such as maximal parallelism detection, permutable loop detection, minimization of synchronizations , easiness of code generation, etc. We complete the discussion by pres enting new results related to code generation and loop fusion for a pa rticular class of multidimensional schedules called shifted linear sch edules. We demonstrate that algorithms based on such schedules lead to simple codes. (C) 1998 Elsevier Science B.V. All rights resented.