文献

J-GLOBAL ID：202002227303141865   整理番号：20A1504326

大規模重み付きグラフ上のParaPLL高速並列最短経路距離クエリー【JST・京大機械翻訳】

ParaPLL Fast Parallel Shortest-path Distance Query on Large-scale Weighted Graphs

著者 (6件)： Qiu Kun (School of Computer Science, Fudan University, Shanghai, China) ,  Zhu Yuanyang (School of Computer Science, Fudan University, Shanghai, China) ,  Yuan Jing (School of Computer Science, Fudan University, Shanghai, China) ,  Zhao Jin (School of Computer Science, Fudan University, Shanghai, China) ,  Wang Xin (School of Computer Science, Fudan University, Shanghai, China) ,  Wolf Tilman (Department of Electrical and Computer Engineering, University of Massachusetts Amherst, Amherst, Massachusetts)
資料名： ACM Proceedings  (ACM Proceedings)
号： ICPP 2018  ページ： 1-10  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 加重グラフにおける頂点間の最短経路距離の決定は,コンテキスト意識探索や経路選択のような広範囲の分野にとって重要な問題である。最短経路距離を問うための多くの効率的方法が提案されているが,それらは,強いタスク依存性のため,マルチコアCPUやコンピュータクラスタのような並列アーキテクチャにはあまり適していない。本論文では,大規模加重グラフ上の高速最短経路距離クエリのための新しい並列フレンドリーフレームワークであるParaPLLを提案した。パラPLLは,共有メモリとメッセージパッシングパラダイムをそれぞれ用いてノード内とノード間の並列性を利用する。また,タスク割当と同期ポリシーを設計し,最先端のソリューションと比較して,ParaPLLが顕著な高速化に達することを可能にする。さらに,パラPLLの正当性も証明した。知る限りでは,ParaPLLは,大規模加重グラフ上の最短経路距離クエリを加速するために,剪定されたランドマークラベリングを利用する最初の並列フレームワークである。この評価結果は,パラPLLが12コアコンピュータを用いた重み付き0.3M-頂点グラフ上の対応するシリアルバージョンよりも9.46倍速いことを示した。また,6ノードコンピュータクラスタ上のパラPLLは,単一ノード実装に対して最大5.6の高速化を達成できる。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 経路選定 ,  高速化 ,  *共有メモリ
準シソーラス用語： コンピュータクラスタ ,  タスク割当 ,  メッセージパッシング ,  *クエリー ,  マルチコアプロセッサ ,  並列アーキテクチャ ,  *最短経路 , 【Automatic Indexing@JST】

著者キーワード (3件)： MPI ,  大規模グラフ ,  最短経路距離質問

分類 (2件)： グラフ理論基礎  (IA02020S) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (4件)： 大規模 ,  グラフ ,  最短経路 ,  クエリー