文献

J-GLOBAL ID：201702266311527344   整理番号：17A1398670

グラフ分割のメモリ局所性を利用したによるグラフ解析の高速化【Powered by NICT】

Accelerating Graph Analytics by Utilising the Memory Locality of Graph Partitioning

著者 (3件)： Sun Jiawen ,  Vandierendonck Hans ,  Nikolopoulos Dimitrios S.
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： ICPP  ページ： 181-190  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文では,大規模共有メモリシステム上でのグラフ構造分析のメモリ局所性を改善するかを検討した。頂点のすべてのエッジは同じ分配に配置されているグラフ分割はメモリ局所性を改善することを示す。しかし,そのようなグラフ分割による性能向上を実現するいくつかの課題を提起し,グラフアルゴリズムと優先データ構造の分類を再考する必要である。が,中程度の密度フロンティアの概念,ビットマップ表現のための十分に高密度であるが,インデックスグラフレイアウトから恩恵を受ける型フロンティアを導入した。三種類フロンティアの,各フロンティア型に最適化した三グラフレイアウトスキームを用いて,使用する型決定する自律的エッジ横断アルゴリズムを設計した。前方対後方グラフ横断の識別は,この決定に折畳まれ,プログラマにより特異的である長い必要がない。Ligraから誘導されたNUMAを意識したグラフ分析フレームワークにおいて我々の手法を実装し,Ligra上で最大4.34倍と2.93倍までポリマ以上の高速化を実証した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *局所性 ,  *図式解法 ,  *グラフ ,  最適化 ,  *高速化 ,  プログラマ ,  データ構造 ,  *記憶装置 ,  アルゴリズム
準シソーラス用語： NUMA ,  高密度 ,  ビットマップ ,  グラフアルゴリズム ,  グラフ構造 ,  *グラフ分割 , 【Automatic Indexing@JST】

分類 (2件)： グラフ理論基礎  (IA02020S) ,  代数学  (AB02000R)

タイトルに関連する用語 (4件)： グラフ分割 ,  局所性 ,  グラフ解析 ,  高速化