著者

安井 雄一郎 藤澤 克樹 笹島 啓史 後藤 和茂

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:04534514)

巻号頁・発行日

vol.54, pp.58-83, 2011

参考文献数

20

被引用文献数

1 1

---

最短路問題はネットワーク上の経路探索などの多くの応用を持ち,また他の最適化問題の子問題として用いられることも多く,適用範囲の広い組合せ最適化問題である.そのため最短路問題を高速に解くことの重要性は非常に大きくなってきている.最短路問題に対する解法としてはダイクストラ法などの安定的かつ効率的な高速アルゴリズムが存在するが,実問題は非常に大規模になるためさらなる高速化が不可欠である.そこで本論文では大規模最短路問題に対し,計算機のメモリ階層構造を考慮しつつ汎用的かつ効率的に高速化を行うための実装方法を示す.さらに論文中では計算機のメモリ階層構造における律速箇所の特定を行うための汎用的な解析方法を示し,高速化の有用性を検証していく.本手法により実装されたバイナリ・ヒープを適用したダイクストラ法は,実行性能,安定性,メモリ要求量などを他の実装と比較すると総合的に最も優れているといえる.また本実装を用いた大規模最短路問題に対するオンライン・ソルバーについても説明を行う.

著者

遠藤 敏夫 松岡 聡 橋爪 信明 長坂 真路 後藤 和茂

出版者

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

雑誌

情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.87, pp.43-48, 2006-07-31

参考文献数

8

被引用文献数

5

---

TSUBAMEスーパーコンピュータは,655ノード10480 Opteron coreと360枚の ClearSpeed SIMDアクセラレータボードを備えるヘテロ型の大規模クラスタシステムである.TSUBAMEはLinpackベンチマークで38.18TFlopsを記録し,この結果により2006年6月のTop500ランキングに7位としてランクされた.しかしその測定にはOpteronのみが使われ,アクセラレータは用いられていない.本論文は汎用CPUとアクセラレータによる不均一な環境においてLinpack 性能を得る上での課題について論じ,解決法を述べる.16ノード256 CPU coreを用いた予備実験では,アクセラレータ8枚を加えたときに8.2 %,16枚を加えたときに19%の性能向上が観測された.The TSUBAME supercomputer is a heterogeneous large-scale cluster system, which is equipped with 10480 Opteron CPU cores on 655 nodes and 360 ClearSpeed SIMD accelerator boards. The TSUBAME system has achieved 38.18TFlops with Linpack benchmark and is ranked 7th in the Top500 supercomputer ranking in June 2006, even though the measurement is done without any accelerator boards. This paper discusses issues to obtain high Linpack performance on heterogeneous systems with general purpose processors and accelerators, and describes solutions. Through preliminary experiments with 256 CPU cores on sixteen nodes, we observed +8.2% speed-up when eight accelerators are added, and +19% with sixteen accelerators.