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

• Item type: Trans(1)
• 公開日: 2009-03-23
• タイトル: 並列プログラムの候補生成と適合性検査による並列化
• タイトル / 言語: en
• タイトル: Program Parallelization by Candidate Generation and Conformity Testing
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: 国立情報学研究所
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者名: 森畑, 明昌; 松崎, 公紀; 胡, 振江; 武市, 正人
• 著者名(英): Akimasa, Morihata; Kiminori, Matsuzaki; Zhenjiang, Hu; Masato, Takeichi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，並列計算のための環境は身近になってきている．しかし，効率の良い並列プログラムの構築は逐次プログラムの構築に比べてはるかに難しい．そのため，逐次プログラムをもとにして自動的に並列プログラムを得る自動並列化の手法が求められている．プログラムの並列化に関連して，関数プログラミングの分野では第三準同型定理という定理が知られている．第三準同型定理は，配列からある値を計算する問題に対し，その配列の要素を右から順に走査するプログラムと左から順に走査するプログラムの両方が存在すれば，その問題を分割統治法によって解く並列プログラムが存在する，ということを示している．第三準同型定理は並列プログラムの構成に有用であり，第三準同型定理に基づいた自動並列化手法もいくつか提案されている．本論文では第三準同型定理に基づいた新たな自動並列化手法を提案する．提案手法では，逐次プログラムを元に並列プログラムの候補を生成し，それらの中から正しい並列プログラムとなっているものを選択する．さらに，我々は提案手法に基づいた自動並列化器を試作した．我々の並列化器は，算術演算と条件式によって定義された再帰関数から，その再帰関数を計算する並列プログラムを自動的に生成することができる．本論文では我々の自動並列化手法の概要について述べた後，我々の実装と実験結果について報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 2, 号 2, p. 132-143, 発行日 2009-03-23
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会