アクセス計算量：新しい並列計算量の枠組みの提案

• Item type: Trans(1)
• 公開日: 2005-08-15
• タイトル: アクセス計算量：新しい並列計算量の枠組みの提案
• タイトル / 言語: en
• タイトル: Access Complexity: A New Framework for Complexity of Parallel Computation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: プログラミングモデル・ツール
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学新領域創成科学研究科
• 著者所属: 東京大学新領域創成科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Frontier Science the University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Frontier Science the University of Tokyo
• 著者名: 横山, 大作; 近山, 隆
• 著者名(英): Daisaku, Yokoyama; Takashi, Chikayama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年の計算機ハードウェアの進化により，既存の計算量理論ではアルゴリズムの解析に十分とはいえない局面が多くなってきている．計算機のメモリ階層は深化し，RAM モデルと現実とは著しく乖離している．また，クラスタや大規模分散計算など，各計算機間の通信遅延やその違いを無視できない並列環境が一般的になっているが，現状の並列計算コストモデルは，通信遅延の差異を考慮しないものや特定のネットワークトポロジに特化したものしか存在しない．我々は，単一計算機内のメモリ階層から計算機間のネットワーク遅延の差異までを統一的に記述できる計算量モデル，「アクセス計算量モデル」を提案した．このモデルは，計算のコストの本質は演算ではなく通信にこそ存在するという立場をとる．このモデルは十分簡潔なものであり，並列アルゴリズムの計算量を解析的に求めることができることを，いくつかのアルゴリズムで実証することができた．また，bitonic sort アルゴリズムの実計算機上での実行と比較することで，このモデルの妥当性を示すことができた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recent advances in computer hardware have been making existing computational complexity theory inappropriate for many cases. The random access memory (RAM) model was made unrealistic by large speed gap between the processing units and main memory systems. Distributed computing environments have obsoleted traditional models for parallel computation due to non-negligible diversity in communication delay. In this paper, we propose a new framework for computational complexity, named access complexity, in which the cost lies in data transfer rather than computation itself. The model tries to capture all levels of system hierarchy, from cache systems to globally distributed environments. It models these diverse access costs in a simple and uniform way. We apply the model to analyze some parallel algorithms, to show that the model can analyze well-known algorithms easily. We also show the appropriateness of the model, through comparing the predicted and the measured performance of bitonic sort algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 46, 号 SIG12(ACS11), p. 194-204, 発行日 2005-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会