文献

J-GLOBAL ID：201802221135199794   整理番号：18A1486162

動的エッジトリミングによる単一サーバ上での幅優先グラフ探索の加速【JST・京大機械翻訳】

Accelerating breadth-first graph search on a single server by dynamic edge trimming

著者 (5件)： Zhang Guangyan (Department of Computer Science and Technology, Tsinghua University, Beijing, China) ,  Cheng Shuhan (Department of Computer Science and Technology, Tsinghua University, Beijing, China) ,  Shu Jiwu (Department of Computer Science and Technology, Tsinghua University, Beijing, China) ,  Hu Qingda (Department of Computer Science and Technology, Tsinghua University, Beijing, China) ,  Zheng Weimin (Department of Computer Science and Technology, Tsinghua University, Beijing, China)
資料名： Journal of Parallel and Distributed Computing  (Journal of Parallel and Distributed Computing)
巻： 120  ページ： 383-394  発行年： 2018年 
JST資料番号： D0613B  ISSN： 0743-7315  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 第一グラフ探索(a.k.a.,BFS)は,複雑で頻繁なメモリアクセスを持つ典型的なメモリ内計算モデルの一つである。既存の単一サーバグラフコンピューティングシステムは,性能最適化のためのBFSのアクセスパターンを利用することができない。したがって,それらを処理するための大量の計算資源を浪費するだけでなく,大きなグラフのより長い有用なデータ要素にアクセスすることにより,多くの余分なメモリ待ち時間に悩まされる。本論文では,大規模グラフ上での反復中のアクセスパターンの活用により,単一サーバ上での第一グラフ探索を加速する新しい手法であるFastBFSを提案した。最初に,FastBFSは,高価なデータ前処理なしで,逐次メモリおよび/またはディスクアクセスの高い帯域幅を得るために,エッジ中心グラフ処理モデルを用いた。第二に,動的および非同期トリミング機構により,FastBFSは,計算と並行して,無用エッジを除去することにより,大きいグラフのサイズを効率的に低減することができる。第3に,FastBFSは効率的にI/Oストリームをスケジュールし,追加のディスクが利用できればより大きな並列性を達成できる。EPFLにより開発されたXストリームシステムを修正することにより,FastBFSを実装した。著者らの実験結果は,FastBFSが,XストリームおよびGraaphChiと比較して,計算速度においてそれぞれ7.9×および10.4×までのスピードアップを達成できることを示した。追加のディスクによって,性能をさらに改良することができた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 計算機システム ,  円板 ,  計算 ,  *グラフ ,  *トリミング ,  記憶装置 ,  最適化 ,  帯域幅 ,  計算機処理速度 ,  計算モデル ,  待ち時間
準シソーラス用語： 計算資源 ,  アクセスパターン ,  性能最適化 ,  メモリアクセス , 【Automatic Indexing@JST】

著者キーワード (4件)： グラフコンピューティング ,  メモリ内コンピューティング ,  I/O最適化 ,  BFS

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： エッジ ,  サーバ ,  グラフ ,  探索 ,  加速