文献

J-GLOBAL ID：201702219486491916   整理番号：17A1360014

グラフ分割ライブラリMETISとリストスケジューリングを応用した負荷分散の改善

著者 (3件)： 西川直樹 (大阪大 大学院情報科学研究科) ,  置田真生 (大阪大 大学院情報科学研究科) ,  萩原兼一 (大阪大 大学院情報科学研究科)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2017  号： HPC-161  ページ： Vol.2017-HPC-161,No.6,1-8 (WEB ONLY)  発行年： 2017年09月12日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： プログラムを並列化するとき,計算の割当にグラフを用いる手法がある。計算を規定するグラフを分割し,部分グラフをそれぞれ1つの実行ユニットに割り当てる。グラフの頂点および切断辺はそれぞれ計算および通信に対応するため,部分グラフの頂点の重みの和が均衡し,かつ切断辺の重みの和が少ない分割が望ましい。このような分割を得る手法としてMETISが広く使われている。しかし,METIS k-way partitioningを利用してグラフを分割すると,頂点の重みの均衡化に失敗する場合がある。この結果に従って計算を割り当てると,負荷の不均衡により性能が低下する。そこで本研究では,負荷の均衡という制約下で通信を削減する割当手法を提案する。具体的には,k-way partitioningを用いてグラフを粗粒化し,リストスケジューリングを応用して実行ユニットに割り当てる。提案手法を適用した結果,k-way partitioningのみを用いた場合と比較して最大4.2倍の速度向上を達成した。(著者抄録)

シソーラス用語： *並列化 ,  分割 ,  *スケジューリング ,  計算機アルゴリズム ,  *負荷分散 ,  コード生成 ,  システムインタフェイス ,  グラフ ,  高速化 ,  生体シミュレーション
準シソーラス用語： グラフ分割 ,  スケジューリングアルゴリズム ,  MPI【インタフェイス】

分類 (1件)： 計算機システム開発  (JD02010R)

引用文献 (13件)：

• Tanaka, M. and Tatebe, O.: Workflow Scheduling to Minimize Data Movement using Multi-constraint Graph Partitioning, Proceedings of the 12th IEEE/ACM International Symposium on Culster, Cloud and Grid Computing (CCGrid 2012), pp. 65-72 (online), DOI: 10.1109/CCGrid.2012.134 (2012).
• 藤森俊匡,塩川浩昭,鬼塚 真:分散グラフ処理におけるグラフ分割の最適化,情報処理学会論文誌:データベース (TOD72),Vol. 9, No. 4, pp. 46-56 (2016).
• 永持 仁:グラフの最小分割問題に対するアルゴリズム,電子情報通信学会論文誌 D,Vol. J86-D1, No. 2, pp. 53-68 (2003).
• Okuyama, T., Okita, M., Abe, T., Asai, Y., Kitano, H., Nomura, T. and Hagihara, K.: Accelerating ODE-based Simulation of General and Heterogeneous Biophysical Models using a GPU, IEEE Transactions on Parallel and Distributed Systems, Vol. 25, No. 8, pp. 1966-1975 (2014).
• PhysioDesigner.org: About Physiological Hierarchy ML (PHML), http://physiodesigner.org/phml/index.html (accessed on 2017-2-13).

タイトルに関連する用語 (6件)： グラフ分割 ,  ライブラリ ,  リスト ,  スケジューリング ,  応用 ,  負荷分散