並列プログラムの候補生成と適合性検査による並列化

情報処理学会 Web Site

書誌事項

タイトル別名
  • ヘイレツ プログラム ノ コウホ セイセイ ト テキゴウセイ ケンサ ニ ヨル ヘイレツカ
  • Program Parallelization by Candidate Generation and Conformity Testing

この論文をさがす

抄録

近年，並列計算のための環境は身近になってきている．しかし，効率の良い並列プログラムの構築は逐次プログラムの構築に比べてはるかに難しい．そのため，逐次プログラムをもとにして自動的に並列プログラムを得る自動並列化の手法が求められている．プログラムの並列化に関連して，関数プログラミングの分野では第三準同型定理という定理が知られている．第三準同型定理は，配列からある値を計算する問題に対し，その配列の要素を右から順に走査するプログラムと左から順に走査するプログラムの両方が存在すれば，その問題を分割統治法によって解く並列プログラムが存在する，ということを示している．第三準同型定理は並列プログラムの構成に有用であり，第三準同型定理に基づいた自動並列化手法もいくつか提案されている．本論文では第三準同型定理に基づいた新たな自動並列化手法を提案する．提案手法では，逐次プログラムを元に並列プログラムの候補を生成し，それらの中から正しい並列プログラムとなっているものを選択する．さらに，我々は提案手法に基づいた自動並列化器を試作した．我々の並列化器は，算術演算と条件式によって定義された再帰関数から，その再帰関数を計算する並列プログラムを自動的に生成することができる．本論文では我々の自動並列化手法の概要について述べた後，我々の実装と実験結果について報告する．

Recently, it has been easy to access parallel computation environments. However, efficient parallel programs are much harder to develop than sequential ones. Therefore, automatic parallelization methods, which generate parallel programs from sequential ones, are called for. The third homomorphism theorem is a folk theorem in the functional programming community. The theorem states that for a problem to compute a value from an array, there exists a divide-and-conquer parallel algorithm to solve the problem if and only if the problem can be solved by both of two programs that respectively scan the array in leftward and rightward manners. The theorem is useful for developing parallel programs, and automatic parallelization methods have been proposed on it. In this paper, we propose a new automatic parallelization method. We generate candidates of parallel programs, and choose one that satisfies the requirement of parallel programs. We implemented our idea as an automatic parallelization system, which can parallelize recursive functions defined by arithmetic and conditional expressions.

収録刊行物

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ