文献

J-GLOBAL ID：201502203904816084   整理番号：15A0772771

部分的にバリア除去された負荷不均衡並列アプリケーションの確率論的解析

PROBABILISTIC ANALYSIS OF LOAD-IMBALANCED PARALLEL APPLICATIONS WITH PARTIALLY ELIMINATED BARRIERS

著者 (4件)： YONEZAWA Naoki (Teikyo Heisei Univ.) ,  KATOU Ken’ichi (Kanagawa Univ.) ,  KINO Issei (Kanagawa Univ.) ,  WADA Koichi (Univ. Tsukuba)
資料名： Journal of the Operations Research Society of Japan  (Journal of the Operations Research Society of Japan)
巻： 58  号： 2  ページ： 149-164  発行年： 2015年04月 
JST資料番号： G0402A  ISSN： 0453-4514  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 以前の研究において,バリア同期のオーバーヘッドを減らすべく,バリア同期を除去するアルゴリズムを提案しその有効性を実験的に評価した。その結果,アルゴリズムは負荷均衡プログラムよりも負荷不均衡プログラムに対して一層有効であることを発見した。しかし,負荷均衡の度合いを定量的に議論しなかった。本論文では,並列プログラムの挙動をモデル化した。提案モデルでは,並列プログラムに含まれる局面の実行時間をランダム変数として表現する。負荷均衡の度合いがアルゴリズムの性能にどう影響するかを調べるために,ランダム変数が追従する確率分布の変動係数(CV)を変化させた。モデルを用いて,4つの典型的依存性パターンを持つ並列プログラムの実行時間を評価した。結果に基づき,理論的結果は実験の結果と一致することを確認した。(翻訳著者抄録)

シソーラス用語： 情報技術 ,  *確率論 ,  応用プログラム ,  *並列処理 ,  *負荷分散 ,  計算機アルゴリズム ,  依存性 ,  *プログラム実行 ,  確率分布 ,  シミュレーション ,  モンテカルロ法 ,  コンパイラ ,  同期 ,  モデリング ,  モンテカルロシミュレーション ,  並列アプリケーション
準シソーラス用語： バリア同期 ,  確率論的解析 ,  実行時間 ,  負荷均衡

分類 (2件)： 計算機システム開発  (JD02010R) ,  数値計算  (JE02000J)

引用文献 (8件)：

• [1] S. Dwarkadas, A.L. Cox, and W. Zwaenepoel: An Integrated Compile-Time/Run-Time Software Distributed Shared Memory System. In Proceedings of International Conference on Architectural Support for Programming Languages and Operating Systems (1996), 186-197.
• [2] D. Lenoski, J. Laudon, K. Gharachorloo, W.-D. Weber, A. Gupta, J. Hennessy, M. Horowitz, and M.S. Lam: The Stanford DASH Multiprocessor. Computer, 25 (1992), 63-79.
• [3] J. Sun and G.D. Peterson: An Effective Execution Time Approximation Method for Parallel Computing. IEEE Trans. Parallel Distrib. Syst., 23 (2012), 2024-2032.
• [4] C.-W. Tseng: Compiler Optimizations for Eliminating Barrier Synchronization. In Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (1995), 144-155.
• [5] N. Yonezawa I. Kino and K. Wada: Probabilistic analysis of time reduction by eliminating barriers in parallel programmes. International Journal of Communication Networks and Distributed Systems, 6 (2011), 404-419.

タイトルに関連する用語 (4件)： バリア ,  均衡 ,  並列アプリケーション ,  確率論的解析