文献

J-GLOBAL ID：202102279510695541   整理番号：21A3276053

マルチコアシステムにおけるグラフ再順序付けによる負荷バランシング【JST・京大機械翻訳】

Workload Balancing via Graph Reordering on Multicore Systems

著者 (2件)： Chen YuAng (The Chinese University of Hong Kong, Shenzhen, Guangdong, China) ,  Chung Yeh-Ching (The Chinese University of Hong Kong, Shenzhen, Guangdong, China)
資料名： IEEE Transactions on Parallel and Distributed Systems  (IEEE Transactions on Parallel and Distributed Systems)
巻： 33  号： 5  ページ： 1231-1245  発行年： 2022年 
JST資料番号： T0882A  ISSN： 1045-9219  CODEN： ITDSEO  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 共有メモリマルチコアシステムにおいて,グラフの固有不規則データ構造は貧弱なキャッシュ利用につながり,従ってグラフ解析の性能を低下させる。問題に取り組むために,先行研究は,キャッシュ局所性の最適化に焦点を当てた様々な軽量再順序付け法を提案した。しかし,キャッシュ局所性と作業負荷バランスの間には妥協がある。並列グラフ処理の有効性を低下させる,根底にあるマルチコアシステムのための作業負荷不均衡の問題について,ほとんど洞察が払われていない。本研究では,頂点の濃度によって発生する不均衡を定量化するための測定法を提案した。これに触発されて,マルチコアシステムのキャッシュ階層構造を利用する軽量再順序付け法であるキャッシュアウェアリオーダー(Corder)を提示した。共有メモリレベルでは,Corderはマルチコア間の計算負荷の分布さえ促進する。プライベートキャッシュレベルでは,Corderは局所頂点次数にさらなる精密化を適用することによりキャッシュ効率を促進する。種々のグラフアプリケーションとデータセットについて,C次の包括的性能評価を行った。実験結果は,Corderが,2.59×2.59の高速化と,平均1.45×1.45の高速化をもたらし,既存の軽量再順序付け法よりも著しく優れていることを示した。順序によって送られる性能ブーストの根本原因を同定するために,マルチコア活動を,スレッド挙動,キャッシュ効率,およびメモリ利用の観点から調査した。統計解析は,不均衡なスレッド実行時間の問題が,全体のグラフ処理時間を決定する際に他の因子を支配することを証明した。さらに,Corderはクロスプラットフォームスケーラビリティと再順序付けオーバヘッドにおいて顕著な利点を達成した。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 記憶装置 ,  最適化 ,  加工時間 ,  図式解法 ,  *キャッシュメモリ ,  応用プログラム ,  局所性 ,  高速化 ,  共有メモリ ,  スレッド
準シソーラス用語： 実行時間 ,  オーバヘッド ,  計算負荷 ,  *順序づけ ,  *マルチコアプロセッサ , 【Automatic Indexing@JST】

分類 (5件)： 図形・画像処理一般  (JE04010I) ,  記憶方式  (JC02040V) ,  符号理論  (ND02030R) ,  パターン認識  (JE07000S) ,  自然語処理  (JE06000L)

タイトルに関連する用語 (3件)： グラフ ,  順序付け ,  負荷バランシング