
Structured Parallel Programming with TreesStructured Parallel Programming with Trees 木を用いた構造化並列プログラミング 
"/佐藤, 重幸/"佐藤, 重幸 ,
"/サトウ, シゲユキ/"サトウ, シゲユキ ,
"/Sato, Shigeyuki/"Sato, Shigeyuki
pp.1

143 , 20150325 , The University of ElectroCommunications
Description
Highlevel abstractions for parallel programming are still immature. Computations on complicated data structures such as pointer structures are considered as irregular algorithms. General graph structures, which irregular algorithms generally deal with, are difficult to divide and conquer. Because the divideandconquer paradigm is essential for load balancing in parallel algorithms and a key to parallel programming, general graphs are reasonably difficult. However, trees lead to divideandconquer computations by definition and are sufficiently general and powerful as a tool of programming. We therefore deal with abstractions of treebased computations. Our study has started from Matsuzaki’s work on tree skeletons. We have improved the usability of tree skeletons by enriching their implementation aspect. Specifically, we have dealt with two issues. We first have implemented the loose coupling between skeletons and data structures and developed a flexible tree skeleton library. We secondly have implemented a parallelizer that transforms sequential recursive functions in C into parallel programs that use tree skeletons implicitly. This parallelizer hides the complicated API of tree skeletons and makes programmers to use tree skeletons with no burden. Unfortunately, the practicality of tree skeletons, however, has not been improved. On the basis of the observations from the practice of tree skeletons, we deal with two application domains: program analysis and neighborhood computation. In the domain of program analysis, compilers treat input programs as controlflow graphs (CFGs) and perform analysis on CFGs. Program analysis is therefore difficult to divide and conquer. To resolve this problem, we have developed divideandconquer methods for program analysis in a syntaxdirected manner on the basis of Rosen’s highlevel approach. Specifically, we have dealt with dataflow analysis based on Tarjan’s formalization and valuegraph construction based on a functional formalization. In the domain of neighborhood computations, a primary issue is locality. A naive parallel neighborhood computation without locality enhancement causes a lot of cache misses. The divideandconquer paradigm is known to be useful also for locality enhancement. We therefore have applied algebraic formalizations and a treesegmenting technique derived from tree skeletons to the locality enhancement of neighborhood computations.
FullText
http://ir.lib.uec.ac.jp/infolib/user_contents/9000000788/9000000788.pdf