Distributed Implementation Of A Parallel Tree And Graph Computation Framework

Treestructure,suchasthebinarytreeorthegeneraltree,isanimportantdatastruc-ture, which is frequently used to represent hierarchical data structure like mathematicalexpression or structured documents (for example, XML documents). Even though treestructures are widely used in serial program programs, its irregular and imbalancedfeature makes it difcult to develop efcient parallel programs on tree computations.Although there is a lot of research on tree parallelization, it is still a known challengeto provide an efcient divide-and-conquer parallel algorithm on trees to distributedsystems with good load balance.On the other hand, large networks or graphs are prevailing in many areas, such asbiology, physics, chemistry, communication and social network. The computationalcomplexity of such large datasets has exhausted the limits of a single computer, whichdemands parallelization of graph problems on parallel systems. Thus the approachesofusingMapReduce-likeframeworkstohandlelargegraphsarebeingactivelystudied.However, many graph optimization problems, such as the Maximum Weighted Inde-pendent Set problem, are NP-hard. For large input graphs, these problems are hard tobe computed even using MapReduce-like frameworks that are deployed on large com-puter clusters, because such graph computations are often exponential in the size ofthe input graphs. Fortunately, many studies have shown that many NP-hard problemsposed in monadic second-order logic can be solved in polynomial time using dynamicprogramming techniques on input graphs with bounded treewidth. Many problems ongraph can be solved via tree decomposition using bottom-up dynamic recursive algo-rithms.In this paper, we studied the related work on tree parallelization and graph paral- lelization. By extending the Third Homomorphism Theorem and the zipper structure,we proposed a tree parallelization framework which is suitable for distributed systemsand can be applied to the MapReduce model. As the tree decomposition of a graph istree structure in the data structure view, we proposed an approach to transform bottom-up dynamic programming algorithms on tree decomposition to parallel algorithms onzipper. Based on the tree parallelization framework and the tree decomposition tech-nique, we proposed a distributed graph parallelization framework, which provides ef-fcient parallelization to the graph optimization problems.Our main contributions in this paper are as follows:1. WeextendTheThirdHomomorphismTheoremandthezipperstructureandgivea recursive approach for balanced tree partition. Based on such techniques, wepropose a tree parallelization framework which is suitable for distributed sys-tems.2. Based on the tree parallelization framework, we design a distributed graph par-allelization framework by combing the tree decomposition technique.3. We design user-friendly abstractions and interfaces for our tree and graph paral-lelization frameworks.4. We propose a systematic framework for algorithm transformation. It transformsuser-defned algorithms to parallel algorithms automatically, and it will generateparallel programs based on the target environment.