自動並列化コンパイラにおける性能指向型統合的並列化・コード最適化技術に関する研究

面向性能的自动并行编译器集成并行化与代码优化技术研究

• 批准号: 11780223
• 负责人: 中西 恒夫
• 金额: $ 1.47万
• 依托单位: Nara Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1999
• 资助国家: 日本
• 起止时间: 1999 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-11780223/
• 关键词: 自動並列化コンパイラ; データフロー解析; 単調データフローモデル; 区間演算; 剰余類; 遺伝的アルゴリズム; プログラム分割; データ分割; 並列化; コード最適化; データ依存解析

今年度は,i)選択的データフロー解析適用技術の開発,ii)性能指向型統合的並列化/コード最適化処理適用アルゴリズムの開発,iii)プロファイリングに基づくプログラム実行時間予測技術の開発を行うことを計画し,以下の成果を得た.1.昨年度,選択的データフロー解析適用技術の手段として考案した剰余区間演算は情報処理学会論文誌に採録された.剰余区間演算は,従来浮動小数点の誤差解析等で用いられていた区間演算に法と剰余の概念を導入し,整数集合に対して代数演算および集合演算を定義した演算体系である.2.今年度の最大の業績は,剰余区間演算を単調データフローシステムに組み込み,変数ならびに式の値域を静的に解析するアルゴリズム,剰余区間伝播を考案したことである.単調データフローシステムを用いて値域解析を行うアルゴリズムはすでに発表されているが,これらのアルゴリズムはループのストライドが1より大きいケースでは解析の精度が落ちる.また,プログラム中の分岐条件式がX<Yのように簡単なものに限られた.剰余区間は整数の飛びが表現できるためループストライドが1より大きいケースに対処でき,また剰余区間伝播はX+Y<Zのような複雑な分岐条件式にも対処できる.配列添字式の値域解析に剰余区間伝播を適用することによりデータ依存解析や配列参照解析が行えるほか,並列処理以外の分野では,シリコンコンパイルにおいて重要なデータパス幅の解析にも剰余区間伝播を利用できる.さらに,剰余区間演算は演算の際に,実際の整数集合よりは大きな答えを出す演算誤差の問題があるが,剰余区間演算の誤差削減法の研究を昨年度に続けて行った.3.遺伝的アルゴリズムを用いてプログラム分割ならびにデータ分割配置の最適化を行った.分枝限定法では大きな問題が解けなかったが,遺伝的アルゴリズムを用いたところ,大きな問題の解が実用的な時間で得られた.

This year, we have planned to develop i) the development of selected technologies for data analysis,ii) the development of performance-oriented integration of parallelization/optimization processing for Android applications, and iii) the development of implementation time prediction technology for basic software programming, and the following results have been achieved. 1. Last year, Selected data analysis techniques and methods for the study of residual interval algorithms are recorded in the Journal of the Information Processing Society. 2. The biggest performance of this year is that of the interval algorithm, which is used to calculate the error of floating decimal points, and the concept of the interval algorithm and the residual algorithm is introduced, and the algebraic algorithm and the set algorithm are defined. The rest of the time. In the case of a simple adjustment, the range of the solution is determined by the range of the solution and the accuracy of the solution is reduced. In this case, X<Y is the condition of divergence in the first group. The remainder interval is an integer, and the remainder interval is an integer. In addition, the allocation of additional words in the field of analysis of residual interval transmission is applicable to the analysis of residual interval transmission, and the allocation of reference analysis is applicable to the analysis of residual interval transmission. In this paper, the problem of error reduction in residual interval algorithm is studied. 3. The optimization of the allocation of the residual interval algorithm is carried out. The branch and limit method is used to solve the problem of large number of problems, and the time of solution of large number of problems is obtained.

项目成果

中西恒夫: "剰余区間演算の定義とプログラム解析への応用"並列処理シンポジウムJSPP2000(採録). (2000)

Tsuneo Nakanishi：“余数间隔运算的定义及其在程序分析中的应用”并行处理研讨会 JSPP2000（已接受）。

山崎光倫: "周期性を有する配列参照パターンの解析手法について"情処研報. 99-MPS-26. 1-4 (1999)

Mitsunichi Yamazaki：“关于周期序列参考模式的分析方法”信息研究报告99-MPS-26（1999）。

中西恒夫: "A Combined Data and Program Partitioning Algorithm for Distributed Memory Mu*tiprocessor"情処論・数理モデル化と応用. 40,SIG9. 30-41 (1999)

Tsuneo Nakanishi：“分布式内存多处理器的组合数据和程序分区算法”信息处理理论，数学建模和应用 40，SIG9（1999）。

Noriko Soyama: "Reducing Error on Modulo Interval Arithmetic"Proc.of the 5th Asian Technology Conf.in Mathematics (ATCM). 482-491 (2000)

Noriko Soyama：“Reducing Error on Modulo Interval Arithmetic”Proc.of the 5th Asian Technology Conf.in Mathematics (ATCM)。

Tsuneo Nakanishi: "Modulo Interval Arithmetic and Its Application to Program Analysis"Trans.of Information Processing Society of Japan. (採録). (2001)

Tsuneo Nakanishi：“模区间算法及其在程序分析中的应用”，日本信息处理协会（已接受）。