不規則アクセスを伴うループの並列化コンパイル技法 -Inspector/Executorアルゴリズムの高速化-  [in Japanese] A Parallelizing Compiler Technique for Loops with lrregular Accesses -New Algorithms to Improve the Performance of the Inspector/Executor-  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

本稿では、分散メモリ型の並列計算機に射するSPMDコード生成技法について述べる、インデックス配列による間接アクセスが存在するループを並列化すると、不規則なアクセスパターンを生ずる。従来inspectorとexecutorというコードを生成する手法が提案されてきたが、inspectorにおいて全対全のプロセッサ間通信が必要であり、適用できるコードの範囲にも制限がある。これらの問題を解決するために、逆インデックス法と全検査法という2つのinspectorのアルゴリズムを提案する、さらに、それらの手法の有効性を高並列計算機AP1000上で評価した。その結果、部分ピボッティング付きLU分解のプログラムでは、Inspector/Executor戦略を用いない場含に比べ、逆インデックス配列法で42倍、全検査法で11倍まで実行時間が高速化された。また、不規則疎行列とベクトルの積を求めるプログラムで、従来のinspectorアルゴリズムと逆インデックス法とを比較すると、1.6倍に実行時間の高速化が達成された。

ln this paper, we focus on parallelizing compiler techniques which generate SPMD codes for distributed memory computers. Parallelization of loops with indirect accesses with index arrays causes irregular access patterns. For such codes, a technique to generate inspector/executor code has been proposed. In this technique, however, the inspector must perform all-to-all global communications. Furthermore, codes, to which this method is applicabIe, are restricted. In order to resolve these drawbacks, we propose two inspector algorithms, inverse index method and exhaust inspection method. We evaluated the effectiveness of these methods on the highly parallel computer AP 1000. For the LU decomposition program with partial pivoting, the inverse index and exhaust inspection methods improve the performance 42 and 11 times respectively, as compared with the code without the Inspector/Executor strategy. As for the comparison of the inverse index method with the conventional one, it is proved that the code with the former is 1.6 times as fast as with the latter, in the case of the irregular sparse matrix-vector multiply.

Journal

  • IPSJ Journal

    IPSJ Journal 35(4), 532-541, 1994-04-15

    Information Processing Society of Japan (IPSJ)

References:  5

Cited by:  3

Codes

  • NII Article ID (NAID)
    110002722689
  • NII NACSIS-CAT ID (NCID)
    AN00116647
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7764
  • Data Source
    CJP  CJPref  NII-ELS  IPSJ 
Page Top