不規則アクセスを伴うループの並列化コンパイル技法 : Inspector/Executorアルゴリズムの高速化
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,分散メモリ型の並列計算機に対するSPMDコード生成技法について述べる.インデックス配列による間接アクセスが存在するループを並列化すると,不規則なアクセスパターンを生ずる.従来inspectorとexecutorというコードを生成する手法が提案されてきたが,inspectorにおいて全対全のプロセッサ間通信が必要であり,適用できるコードの範囲にも制限がある.これらの問題を解決するために,逆インデックス法と全検査法という2つのinspectorのアルゴリズムを提案する.さらに,それらの手法の有効性を高並列計算機AP1000上で評価した.その結果,部分ピボッティング付きLU分解のプログラムでは,Inspector/Executor戦略を用いない場合に比べ,逆インデックス配列法で42倍,全検査法で11倍まで実行時間が高速化された.また,不規則疎行列とベクトルの積を求めるプロラグラムで,従来のinspectorアルゴリズムと逆インデックス法とを比較すると,1.6倍に実行時間の高速化が達成された.
- 社団法人情報処理学会の論文
- 1994-04-15
著者
-
富田 眞治
京都大学工学部情報工学科
-
窪田 昌史
広島市立大学情報科学部
-
窪田 昌史
京都大学工学部情報工学教室
-
森 眞一郎
京都大学工学部情報工学教室
-
中島 浩
京都大学工学部情報工学教室
-
三吉 郁夫
京都大学工学部
-
大野 和彦
京都大学工学部
-
中島 浩
京都大学工学部
-
富田 眞治
京都大学工学部情報工学教室
-
富田 眞治
京都大学工学部
-
三吉 郁夫
京都大学工学部:現在 富士通株式会社
-
森 眞一郎
京都大学工学部
関連論文
- 自動車ドライバ挙動解析のための光学式モーションキャプチャの開発と評価(感性情報処理とマルチメディア技術および一般)
- 自動車運転者の挙動計測のためのGPS同期モーションキャプチャシステム(画像処理・インタフェース,ITS情報処理,一般)
- インタラクティブ・スーパーコンピューティング環境の実現に向けて
- 並列可視化処理向けFPGA搭載PCIカードへのボリュームレンダリングの予備実装(応用2, FRGAとその応用及び一般)
- 並列ボリュームレンダリング・アクセラレータVisAの開発とその予備実装(高速データ通信と実装)
- 並列ボリュームレンダリング・アクセラレータVisAの開発とその予備実装(高速データ通信と実装,FPGA応用及び一般)
- 操作の連続性を考慮した手術シミュレータの高速化手法(HPC-8 : アプリケーションII)
- インタラクティブシミュレーションにおける遠隔操作フレームワークの実装(HPC-6 : 開発・実行環境)
- パス情報を用いた分岐フィルタ機構(プロセッサアーキテクチャ)
- スラック予測を用いたクラスタ型スーパースカラ・プロセッサ向け命令ステアリング(ARC-4:スケジューリング,2006年並列/分散/強調処理に関する『高知』サマー・ワークショップ(SWoPP 高知2006))
- セル投影型並列ボリュームレンダリングのEarly Ray Terminationによる高速化(並列計算)
- 中規模コモディティクラスタ向け相互結合網Three Quadsの提案(ネットワーク,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- 中規模コモディティクラスタ向け相互結合網Three Quadsの提案(ネットワーク, 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- DVIによる超高速単方向リンクを用いた並列ボリュームレンダリング(FPGAとその応用及び一般)
- DVIによる超高速単方向リンクを用いた並列ボリュームレンダリング
- 大規模パイプラインステージ統合 : CPU内部からチップセットまで(一般セッションE Funny Architecture I)
- 並列事前実行における再利用バッファの高速化(一般セッションC 設計と実装)
- 公開鍵暗号を用いてプログラムの保護を行うプロセッサの提案(プロセッサアーキテクチャ)
- ディジットシリアル浮動小数点演算器を用いた高精度FFT回路の設計検討(一般セッションC 設計と実装)
- MPIプログラムの自律チェックポインティング方式の実現(HPC-3 : スケジューリング)
- 構造化プログラムに対する静的単一代入形式の生成アルゴリズム
- 動的リンクライブラリを用いた実行時最適化の評価
- 2000-HPC-82-21 Javaクラスファイルの実行時ループ最適化手法
- 2000-HPC-82-18 ウェーブフロント型計算における性能予測モデルの構築
- 実行時情報を用いた性能最適化手法
- 並列化コンパイラTINPARにおける自動データ分割決定手法
- 非均質環境向け並列化コンパイラhetero-TINPER : 動的負荷分散方式の改良
- 並列化コンパイラTINPARによる非均質計算環境向けコード生成手法
- 並列化コンパイラTINPARにおける重複プロセッサ間通信の削減手法
- 並列化コンパイラTINPARにおける自動データ分割部の実現
- 不規則問題に対する並列化コンパイル手法
- 並列化コンパイラTINPARにおけるスカラ変数処理
- 不規則アクセスを伴うループの並列化コンパイル技法 : Inspector/Executorアルゴリズムの高速化
- 並列可視化処理向けFPGA搭載PCIカードへのボリュームレンダリングの予備実装(応用2, FRGAとその応用及び一般)
- 並列可視化処理向けFPGA搭載PCIカードへのボリュームレンダリングの予備実装(応用2, FRGAとその応用及び一般)
- 配列整合解析に基づく自動データ分割手法
- 小容量RAMを用いたオペランド・バイパスの複雑さの低減手法(プロセッサアーキテクチャ)
- グローバル分岐履歴を用いたスラック予測器(ARC-2 : プロセッサアーキテクチャII)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- アクセラレータを用いたルジャンドル変換の高速化
- タイルドディスプレイを用いた高精細ボリュームレンダリングシステムの実装
- HPC向けVMスケジューラの改良の提案
- 汎用グラフィクスカードを用いた並列ボリュームレンダリングシステム(並列処理応用)
- 情報科学・工学, 私はこう考える : これからのアーキテクチャ, 私はこう考える
- 自動車運転者の挙動計測のためのGPS同期モーションキャプチャシステム
- DVIによる超高速単方向リンクを用いた並列ボリュームレンダリング(FPGAとその応用及び一般)
- DVIによる超高速単方向リンクを用いた並列ボリュームレンダリング(FPGAとその応用及び一般)
- DVIによる超高速単方向リンクを用いた並列ボリュームレンダリング(FPGAとその応用及び一般)
- DVIによる超高速単方向リンクを用いた並列ボリュームレンダリング
- 静的解析による並列論理型言語KL1のメッセージ通信最適化
- 並列論理型言語処理系KLICにおける通信の高速化
- 並列論理型言語KL1の最適化手法
- 並列論理型言語KL1の最適化手法
- PIM/mフロントエンド・プロセッサの速度性能評価
- 分散環境における構造体管理
- PSI-IIの性能評価 : If_Then_Else,Neck_Cut
- HPC向けVMスケジューラの改良の提案
- 参照の空間局所性を最大化するボリューム・レンダリング・アルゴリズムの改良(並列処理応用)
- フロントエンド実行によるプリロードの提案(ARC-2 : プロセッサアーキテクチャII)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- フロントエンド実行(マルチスレッド実行とプロセッサアーキテクチャ)
- 計算機アーキテクチャの昨日、今日、明日
- HPCへの期待 : アーキテクチャの立場から
- 並列計算機の現状と将来
- Pascalマシンとチューニングによる高速化
- 1.5MLIPS40ビット推論プロセッサ
- スタック領域が不要な深さ優先順コピー型ゴミ集め方式
- 並列ボリュームレンダリング・アクセラレータVisAの開発とその予備実装(高速データ通信と実装,FPGA応用及び一般)
- 並列ボリュームレンダリング・アクセラレータVisAの開発とその予備実装(高速データ通信と実装,FPGA応用及び一般)
- 故障に対してユーザ側の耐性を高めるデジタル家電アーキテクチャ(Inventive and Creative Architecture特別セッションII)
- ALU Cascadingを行う動的命令スケジューラ(集積回路とアーキテクチャの協創-プロセッサ,メモリ,システムLSI及び一般-)
- ALU Cascadingを行う動的命令スケジューラ(低消費電力化技術(2),集積回路とアーキテクチャの協創-プロセッサ,メモリ,システムLSI及び一般-)
- 超並列プロトタイプ計算機JUMP-1の構想
- 第100回計算機アーキテクチャ研究会招待講演報告
- 動的負荷分散機能を備えたセル投影型並列ボリュームレンダリングシステムの実装
- 収束過程の可視化によるアルゴリズム設計支援 : インタラクティブシミュレーションの高速化
- 汎用GPUを用いた大規模可視化クラスタの構築
- メッセージ交換型並列計算機のための並列化コンパイラTINPAR
- 並列化コンパイラTINPARにおける専用通信ライブラリの実装と性能評価
- メッセージ交換型並列計算機のための並列化コンパイラTINPAR : 最適化手法と性能評価
- メッセージ交換型並列計算機のための並列化コンパイラ
- プログラム並列化におけるデータ分割支援システム
- 並列ボリュームレンダリングにおける投機的描画に関する考察(ARC-8: 応用システム, 2005年並列/分散/協調処理に関する『武雄』サマー・ワークショップ(SWoPP武雄2005)-研究会・連続同時開催-)
- 汎用グラフィクスカード上での簡易シミュレーションと可視化(CPSY-6 並列分散プラットホーム)(2004年並列/分散/協調処理に関する「青森」サマーワークショップ(SWoPP青森2004))
- 特集「並列処理」の編集にあたって (並列処理)
- 視角制限ピクセル並列処理によるボリューム・レンダリング向きの超高速専用計算機のアーキテクチャ
- ピクセル並列処理によるボリューム・レンダリング向きの超高速専用計算機アーキテクチャー
- ピクセル並列処理によるボリューム・レンダリング向きの超高速専用計算機アーキテクチャ
- ボリュームレンダリング専用並列計算機ReVolver/C40の試作
- セルフ・クリーンアップ型ライトバック・キャッシュの提案
- ディレクトリ型キャッシュコヒーレンスプロトコルの性能評価
- 細粒度プロセッサ間通信をサポートする高機能キャッシュ・システム
- シミュレーティド・アニーリングによる静的タスク配置へのヒューリスティクスの適用とその評価
- ボリュームレンダリング専用並列計算機ReVolverのアーキテクチャ
- スタック変数の導入による並列論理型言語KL1の高速実行
- 並列単層配線を改良する新しい手法の提案
- 汎用CAMを用いた区間再利用プロセッサシミュレータの高速化(CPSY-3 性能評価)(2004年並列/分散/協調処理に関する「青森」サマーワークショップ(SWoPP青森2004))
- 2次キャッシュを用いた再利用および並列事前実行機構における高速化手法(高速化手法)
- 並列自動配線アルゴリズムAmon
- 並列事前実行機構における主記憶値テストの高速化(プロセッサアーキテクチャ)
- 静的解析による並列論理型言語の実行最適化
- ボリュームグラフィクスを支える要素技術