  We propose a methodology for automatic generation of divide-and-conquer
parallel implementations of sequential nested loops. We focus on a class of
loops that traverse read-only multidimensional collections (lists or arrays)
and compute a function over these collections. Our approach is modular, in
that, the inner loop nest is abstracted away to produce a simpler loop nest for
parallelization. Then, the summarized version of the loop nest is parallelized.
The main challenge addressed by this paper is that to perform the code
transformations necessary in each step, the loop nest may have to be augmented
(automatically) with extra computation to make possible the abstraction and/or
the parallelization tasks. We present theoretical results to justify the
correctness of our modular approach, and algorithmic solutions for automation.
Experimental results demonstrate that our approach can parallelize highly
non-trivial loop nests efficiently.
