文献

J-GLOBAL ID：201802219473725267   整理番号：18A0443443

作業規則性をもつ並列非同期分散メモリ最大独立集合アルゴリズム【Powered by NICT】

Parallel Asynchronous Distributed-Memory Maximal Independent Set Algorithm with Work Ordering

著者 (3件)： Kanewala Thejaka ,  Zalewski Marcin ,  Lumsdaine Andrew
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： HiPC  ページ： 52-61  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 最大独立集合(MIS)グラフ問題は,コンピュータビジョン,情報理論,分子生物学,プロセススケジューリングなどの多くの応用で生じる。グラフデータの大規模が必要計算とメモリ資源を提供する費用対効果の高いアプローチとして分散メモリハードウエアの利用を示唆した。既存の分散メモリ並列MISアルゴリズムは同期通信に依存し,部分グラフ計算のような技術を用いた。本論文では,アルゴリズム実行中に形成された仮想有向非循環グラフ(DAG)に依存する非同期分散メモリ並列グラフアルゴリズムを提案した。規則化生じる仕事による計算を節減する二種類のアルゴリズムを導入した。第一のアルゴリズムは,計算の手間を省くための大域的秩序化適用し,第二のアルゴリズムは同期オーバヘッドを最小化するためのスレッドレベルでの局所的秩序化を適用した。は提案したアルゴリズムの性能を比較するためにベースラインとしてLubyのアルゴリズム変異体の二つの異なる実装を使用(1)バーテックス中心Luby AおよびLuby B実装,および(2)CombBLAS線形代数Lubyの実現。結果は,提案したアルゴリズムがLubyアルゴリズムの実装,特に分散実行におけるよりも優れていることを示した。低直径グラフのための大域的秩序化を適用するアルゴリズムが他のアルゴリズムよりも良好なスケールと高直径グラフのためのオリジナルの非同期アルゴリズムとスレッドレベル秩序化アルゴリズムはより優れた性能を示した。Copyright 2018 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *分散メモリ ,  コンピュータビジョン ,  通信 ,  規則度 ,  分子生物学 ,  *アルゴリズム ,  *記憶装置 ,  線形代数 ,  基準線 ,  情報理論 ,  ハードウェア ,  部分グラフ
準シソーラス用語： オーバヘッド ,  グラフアルゴリズム ,  DAG【グラフ】 , 【Automatic Indexing@JST】

分類 (1件)： パターン認識  (JE07000S)

タイトルに関連する用語 (5件)： 規則性 ,  非同期 ,  分散メモリ ,  集合 ,  アルゴリズム