並列処理に適した配列範囲記述子quadの提案と評価

摘要

プログラマに対して共有メモリを提供するプログラミング言語を，計算機クラスタなどの分散メモリ環境に実現する手段として，コンパイラによって共有メモリへのアクセス情報を収集して，読み出しアクセス前までに，データを消費するプロセッサのメモリ領域にそのデータを移動させる方法が考えられる．この方法は，データアクセス範囲を適切に表現し，それに基づいて移動すべきデータを特定することで，データ転送を必要最小限に抑えることが可能である．本論文では，コンパイラ内部でアクセス情報を表現するための配列範囲記述子quadを提案する．quadは，並列プログラムの実行中に発生するアクセス・パターンを簡潔に表現できる特長を持つ．コンパイラは，依存関係にあるデータを適切に移動させるため，まず書き込みアクセスおよび読み出しアクセスを表現するquad間の積演算により転送すべき配列範囲を求め，対応する通信コードを生成する．本論文では，複数の並列応用プログラムを用いて，実行中にネットワークを介して転送されたデータ転送量，および記述子間の演算コストを基にquadの有効性を評価した．その結果，quadは並列プログラムで出現する典型的なアクセス・パターンを簡潔に表現することができ，従来の配列範囲記述子BRS1に比べて記述子間の演算コストを，BRS2に比べてデータ転送量を大幅に軽減できることを示した．One of the approaches to implement programming languages which provide shared memory for programmers on distributed memory environment is communication code generation, in which a producer sends appropriate data to the consumer. In this approach, the optimal use of network can be achieved by precisely identifying the necessary data to be transferred. This requires a compiler represents the exact range of accessed arrays. In this paper, we proposed a new array section descriptor, called quad, which can concisely represent array sections that are accessed in executing parallel programs. To identify data to be transferred, the compiler generates quads that represent written array section and read array section, and then generates codes for intersection operation between those quads. At runtime, according to the results of the intersection operation, the generated communication code sends the data to satisfy the dependency. For evaluation, we executed several parallel application programs using the quad and a coventional array section descriptor, and measured the amount of data transferred and the computational cost of the operations between descriptors. The results showed that the quad represents various access patterns typically observed in parallel programs efficiently, and can be more efficiently calculated when compared against an existing descriptor BRS1, and reduces the amount of data transferred when compared against BRS2.