不規則アクセスを伴うループの並列化コンパイル技法　－Inspector/Executorアルゴリズムの高速化－

• 窪田, 昌史

• 三吉, 郁夫

• 大野, 和彦

• 森, 眞一郎

• 中島, 浩

• 富田, 眞治

書誌事項

タイトル別名

• A Parallelizing Compiler Technique for Loops with lrregular Accesses -New Algorithms to Improve the Performance of the Inspector/Executor-
• 並列化コンパイラ

抄録

本稿では、分散メモリ型の並列計算機に射するSPMDコード生成技法について述べる、インデックス配列による間接アクセスが存在するループを並列化すると、不規則なアクセスパターンを生ずる。従来inspectorとexecutorというコードを生成する手法が提案されてきたが、inspectorにおいて全対全のプロセッサ間通信が必要であり、適用できるコードの範囲にも制限がある。これらの問題を解決するために、逆インデックス法と全検査法という2つのinspectorのアルゴリズムを提案する、さらに、それらの手法の有効性を高並列計算機AP1000上で評価した。その結果、部分ピボッティング付きLU分解のプログラムでは、Inspector／Executor戦略を用いない場含に比べ、逆インデックス配列法で42倍、全検査法で11倍まで実行時間が高速化された。また、不規則疎行列とベクトルの積を求めるプログラムで、従来のinspectorアルゴリズムと逆インデックス法とを比較すると、1．6倍に実行時間の高速化が達成された。

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 35 (4), 532-541, 1994-04-15

  一般社団法人情報処理学会

キーワード

• 特集：並列処理

詳細情報

• CRID: 1050564287841206912
• NII論文ID: 110002722689
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00014253/
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles