文献

J-GLOBAL ID：200902205932153621   整理番号：09A0595005

Cell Broadband Engineプロセッサでの全点対間最短路問題の解法

A Solution of the All-Pairs Shortest Paths Problem on the Cell Broadband Engine Processor

著者 (2件)： MATSUMOTO Kazuya (Univ. Aizu, Aizuwakamatsu-shi, JPN) ,  SEDUKHIN Stanislav G. (Univ. Aizu, Aizuwakamatsu-shi, JPN)
資料名： IEICE Transactions on Information and Systems (Institute of Electronics, Information and Communication Engineers)  (IEICE Transactions on Information and Systems (Institute of Electronics, Information and Communication Engineers))
巻： E92-D  号： 6  ページ： 1225-1231  発行年： 2009年06月01日 
JST資料番号： L1371A  ISSN： 0916-8532  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 全点対間最短路(APSP)問題は三入れ子型ループ問題により解くことができるグラフ問題である。Cell Broadband Engine (Cell/B.E.)は,高い単一精度の浮動小数点性能を提供するヘテロジニアスマルチコアプロセッサである。本稿ではCell/B.E.での全点対間最短路問題の解法を提示する。Cell/B.E.の性能を最大化するために,APSP問題に対するブロック化アルゴリズムが用いられる。ブロック化アルゴリズムはレジスタのデータの再利用を可能にし,そして,メモリ階層を利用する。Cell/B.E.でのAPSP問題の効果的実装に対する幾つかの最適化技法も述べる。Cell/B.E.は1つのSPEを用いることにより8.45 Gflop/sの性能を,また,6つのSPEを用いることにより50.6 Gflop/sの性能をそれぞれ達成する。(翻訳著者抄録)

シソーラス用語： *最短路問題 ,  グラフ理論 ,  *マイクロプロセッサ ,  ヘテロコンピュータシステム ,  計算機アルゴリズム ,  SIMD ,  記憶階層
準シソーラス用語： *全点対間最短路問題 ,  *マルチコアプロセッサ ,  Floyd Warshallアルゴリズム

分類 (2件)： グラフ理論基礎  (IA02020S) ,  ディジタル計算機方式一般  (JC02010O)

引用文献 (23件)：

• BONDHUGULA, U. Hardware/software integration for FPGA-based all-pairs shortest-paths. Proc. 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, April 2006. 2006, 152-164
• FINK, E. A survey of sequential and systolic algorithms for the algebraic path problem. 1992
• FLOYD, R. W. Algorithm 97 : Shortest path. Commun. ACM. 1962, 5, 6, 345
• GAEKE, B. R. Memory-intensive benchmarks : IRAM vs. cache-based machines. Int'l Parallel and Distributed Processing Symposium, April 2002. 2002, 30-36
• GRIEM, G. Transitive closure on the imagine stream processor. Proc. Fifth Workshop on Media and Stream Processors (MSP-5), 2003. 2003

タイトルに関連する用語 (4件)： プロセッサ ,  点 ,  最短路問題 ,  解法