文献

J-GLOBAL ID：201702287911120553   整理番号：17A1346185

計算機連結成分のための適応並列アルゴリズム【Powered by NICT】

An Adaptive Parallel Algorithm for Computing Connected Components

著者 (5件)： Jain Chirag (Georgia Institute of Technology, Atlanta, GA) ,  Flick Patrick (Georgia Institute of Technology, Atlanta, GA) ,  Pan Tony (Georgia Institute of Technology, Atlanta, GA) ,  Green Oded (Georgia Institute of Technology, Atlanta, GA) ,  Aluru Srinivas (Georgia Institute of Technology, Atlanta, GA)
資料名： IEEE Transactions on Parallel and Distributed Systems  (IEEE Transactions on Parallel and Distributed Systems)
巻： 28  号： 9  ページ： 2428-2439  発行年： 2017年 
JST資料番号： T0882A  ISSN： 1045-9219  CODEN： ITDSEO  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： Shiloach VishkinのPRAMアプローチに基づく無向グラフ内の連結成分を計算するための効率的な分散メモリ並列アルゴリズムを提案した。通信量を削減できるだけでなく,アルゴリズムを負荷バランスさせる複数の最適化技法を論じた。並列グラフ連結性アルゴリズムの効率は,基礎となるグラフトポロジーに依存することを指摘した。特に短径グラフ成分の,並列幅優先探索(B FS)法は良好な性能を提供することを観察した。しかし,並列B FSを走る大きな直径成分または多数の小成分を計算するための効率的ではない。この挑戦に取り組むために,筆者らは次数分布を計算することによりネットワークの型を予測する迅速かつ最適ハイブリッド経路を追跡するためにアルゴリズムを可能にする発見的方法を採用した。メタゲノミクス,ウェブクロール,社会的グラフと道路ネットワークを含む領域からの多様なトポロジーを持つ大規模グラフを用いて,ハイブリッド実装は効率的であり,グラフタイプの各々に対してスケーラブルであることを示した。提案アプローチでは,50以上の十億端部を持つメタゲノムグラフのためのクレイ社XC30の32Kコアを用いた215秒の実行時間を達成した。以前の最新手法と比較した場合,24×までの性能改善が見られた。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *並列アルゴリズム ,  発見的方法 ,  *アルゴリズム ,  無向グラフ ,  負荷分散 ,  分散メモリ ,  道路網 ,  最適化手法 ,  位相幾何学 ,  連結性
準シソーラス用語： 実行時間 ,  次数分布 ,  幅優先探索 ,  通信量 ,  *連結成分 , 【Automatic Indexing@JST】

分類 (2件)： ディジタル計算機方式一般  (JC02010O) ,  計算機網  (JC03000K)

タイトルに関連する用語 (4件)： 計算機 ,  連結成分 ,  適応 ,  並列アルゴリズム