On the parallel complexity of loops

AbstractMany methods have been proposed to parallelize loops for different scenarios using various syntax and/or semantics analysis techniques. An interesting fundamental question is whether one can build a “general” compiler which is able to produce an efficient parallel algorithm for every instance of a nested loop. We give a theoretical analysis using the PRAM complexity theory and present some positive and negative results