Automatic Inversion GeneratesDivide-and-Conquer Parallel ProgramsKazutaka Morita Akimasa Morihata Kiminori Matsuzaki Zhenjiang Hu Masato TakeichiGraduate School of Information Science and Technology, Univ ersity of Tokyo{kazutaka,morihata,kmatsu}@ipl.t.u-tokyo.ac.jp {hu,takeichi}@mist.i.u-tokyo.ac.jpAbstractDivide-and-conquer algorithms are suitable for modern parallelmachines, tending to have large amounts of inherent parallelismand working well with caches and deep memory hierarchies.Among others, list homomorphisms are a class of recursive func-tions on lists, which match very well with the divide-and-conquerparadigm. Ho wever, direct programming with list homomorphismsis a challenge for many programmers. In this paper, we proposeand implement a novel system that can automatically derive cost-optimal list homomorphisms from a pair of sequential programs,based on the third homomorphism theorem. Our idea is to reduceextraction of list homomorphisms to derivation of weak right in-verses. We sho w that a weak right inverse always exists and canbe automatically generated from a wide class of sequential pro-grams. We demonstrate our system with several nontrivial exam-ples, including the maximum prefix sum problem, the prefix sumcomputation, the maximum segment sum problem, and the line-of-sight problem. The experimental results show practical efficiencyof our automatic parallelization algorithm and good speedups ofthe generated parallel programs.Categories and Subject Descriptors D.1.2 [Programming Tech-niques]: Automatic Programming; D.1.3 [Programming Tech-niques]: Concurrent Programming—Parallel programmingGeneral Terms Algorithms, Design, LanguagesKeyw ords Divide-and-conquer parallelism, Inversion, Programtransformation, Third homomorphism theorem1. IntroductionDivide-and-conquer algorithms solve problems by breaking themup into smaller subproblems, recursively solving the subproblems,and then combining the results to generate a solution to the originalproblem. They match very well for modern parallel machines,tending to have large amounts of inherent parallelism and workingwell with caches and deep memory hierarchies [28]. Among others,list homomorphisms are a class of recursive functions on lists,which match very well with the divide-and-conquer paradigm [9,11, 24, 27, 30]. Function h is said to be a list homomorphism, ifPermission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. To copy otherwise, to republish, to post on servers or to redis tributeto lists, requires prior specific permission and/or a fee.PLDI’07June 11–13, 2007, San Diego, California, USA.Copyrightc 2007 ACM 978-1-59593-633-2/07/0006. . . $5.00there is an associated operator  such that for any list x and list yh (x ++ y)=h(x)  h(y)where ++ is the list concatenation. When function h is defined asthe equation above, the computation of h on a longer list, which is aconcatenation of two shorter ones, can be carried out by computingh on each piece in parallel and then combining the results. Forinstance, the function that sums up the elements in a list can bedescribed as a list homomorphismsum (x ++ y)=sum(x)+sum(y) .List homomorphisms are attractive in parallel programming forseveral reasons. First, being a class of natural recursive functions onlists, they enjoy many nice algebraic properties, among which, thethree well-kno wn homomorphism lemmas form the basis of the for-mal de velopment of parallel programs [9, 19,21,22]. Secondly, andvery importantly, they are useful to solve really practical problems.For example, many algorithms executed on Google’s clusters are onMapReduce [24], and most of them, such as distributed grep, countof URL access frequency, and inverting index, are certainly noth-ing but list homomorphisms. Moreover, homomorphisms (catamor-phisms) are suitable for developing robust parallel programs, andare considered to be a primitive parallel loop structure in the de-sign of the new parallel programming language Fortress in Sun Mi-crosystems [30].Despite these appealing advantages of list homomorphisms inparallel programming, a challenge remains for a programmer to usethem to solve their problems, particularly when the problems area bit complicated. Consider the maximum prefix sum problem [6],which is to compute the maximum sum of all the prefix sublists. Forinstance, supposing mps is the function that solves the problem, wehavemps [1, −1, 2] = 0 ↑ 1 ↑ (1 + (−1)) ↑ (1 + (−1) + 2)=2where ↑ is an infix operator returning the bigger of two numbers.It is not straightforward to obtain a parallel program by finding anoperator  such thatmps (x ++ y)=mps(x)  mps( y).It is, however, easy to obtain two sequential programs. We maycompute the maximum prefix sum either by scanning the list fromleft to right asmps (x ++[b]) = mps(x) ↑ (sum(x)+b)or by scanning the list from right to left asmps ([a]++ y)=0↑ (a + mps(y)).These two sequential programs are specialized ones of list homo-morphisms: In the former program y is specialized to a list with146a single element b, and in the latter program x is specialized to alist with a single element a, This ease of sequential programmingsuggests us to look into possibilities of obtaining list homomor-phisms from sequential programs. Noticing that not every sequen-tial program can be parallelized, that is, not all functions can bedescribed as list homomorphisms (in fact mps cannot be a list ho-momorphism), it is important to clarify under what condition listhomomorphisms exist and can be automatically derived.Interestingly, in the context of list homomorphisms, there is afamous theorem, called the third homomorphism theorem,whichsays thatif two sequential programs in some specific form exist insolving a problem, then there must exist a list homomor-phism that solves the pr oblem too.This theorem suggests a new parallel programming paradigm, thatis, developing a parallel program with a list homomorphism froma pair of sequential ones. Although this theorem gives a necessaryand sufficient condition for the existence of list homomorphisms, itmentions nothing of how to construct them. In fact, it remains openwhether there is a general and automatic way to extract an efficientlist homomorphism from two sequential