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

IPSJ Web Site 1 Citations

Bibliographic Information

Other Title
  • アクセス ケイサンリョウ アタラシイ ヘイレツ ケイサンリョウ ノ ワクグミ ノ テイアン
  • Access Complexity: A New Framework for Complexity of Parallel Computation

Search this article

Abstract

近年の計算機ハードウェアの進化により，既存の計算量理論ではアルゴリズムの解析に十分とはいえない局面が多くなってきている．計算機のメモリ階層は深化し，RAM モデルと現実とは著しく乖離している．また，クラスタや大規模分散計算など，各計算機間の通信遅延やその違いを無視できない並列環境が一般的になっているが，現状の並列計算コストモデルは，通信遅延の差異を考慮しないものや特定のネットワークトポロジに特化したものしか存在しない．我々は，単一計算機内のメモリ階層から計算機間のネットワーク遅延の差異までを統一的に記述できる計算量モデル，「アクセス計算量モデル」を提案した．このモデルは，計算のコストの本質は演算ではなく通信にこそ存在するという立場をとる．このモデルは十分簡潔なものであり，並列アルゴリズムの計算量を解析的に求めることができることを，いくつかのアルゴリズムで実証することができた．また，bitonic sort アルゴリズムの実計算機上での実行と比較することで，このモデルの妥当性を示すことができた．

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.

Journal

Citations (1)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top