文献

J-GLOBAL ID：200902239075302198   整理番号：09A0792582

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

Program Parallelization by Candidate Generation and Conformity Testing

著者 (4件)： 森畑明昌 (東大 大学院情報理工学系研究科) ,  松崎公紀 (東大 大学院情報理工学系研究科) ,  HU Zhenjiang (国立情報学研) ,  武市正人 (東大 大学院情報理工学系研究科)
資料名： 情報処理学会論文誌トランザクション(CD-ROM)  (情報処理学会論文誌 Computer Vision and Applications(CD-ROM))
巻： 2008  号： 2  ページ： VOL.2NO.2,132-143  発行年： 2009年04月15日 
JST資料番号： L7379A  ISSN： 1882-7772  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *並列処理 ,  計算機プログラム ,  *プログラム検査 ,  両立性 ,  分割統治法 ,  帰納的関数 ,  *自動プログラミング ,  実装設計 ,  評価試験 ,  *並列化
準シソーラス用語： *並列プログラム ,  適合性検査 ,  適合性 ,  *自動並列化 ,  算術演算 ,  再帰関数

分類 (2件)： ディジタル計算機方式一般  (JC02010O) ,  計算機システム開発  (JD02010R)

引用文献 (22件)：

• Bentley, J.: Programming Pearls, ACM, New York, NY, USA (1986).
• Bird, R. S.: An Introduction to the Theory of Lists, Logic of Programming and Calculi of Discrete Design, NATO ASI Series F, Vol.36, pp. 3-42, Springer (1987).
• Callahan, D.: Recognizing and Parallelizing Bounded Recurrences, Languages and Compilers for Parallel Computing, 4th International Workshop, Santa Clara, California, USA, August 7-9, 1991, Proceedings, Lecture Notes in Computer Science, Vol.589, pp. 169-185, Springer (1992).
• Chin, W.-N.: Towards an automated tupling strategy, Proc. ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM’93, Copenhagen, Denmark, June 14-16, pp. 119-132, ACM (1993).
• Collins, G. E.: Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Automata Theory and Formal Languages, 2nd GI Conference, Kaiserslautern, May 20-23, 1975, Lecture Notes in Computer Science, Vol.33, pp. 134-183, Springer (1975).

タイトルに関連する用語 (4件)： 並列プログラム ,  適合性 ,  検査 ,  並列化