階層構造をもつマルチプロセッサにおける階層データ分割分析法

• Item type: SIG Technical Reports(1)
• 公開日: 1994-10-27
• タイトル: 階層構造をもつマルチプロセッサにおける階層データ分割分析法
• タイトル / 言語: en
• タイトル: A Hierarchical data Partitioning Method for Hierarchical Memory Compilation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 慶應義塾大学計算機科学専攻
• 著者所属: 慶應義塾大学計算機科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Keio University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Keio University
• 著者名: 李, 暁傑; 原田, 賢一
• 著者名(英): Xiaojie, Li; Ken-Ichi, Harada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 分散共有メモリ型並列計算機におけるプログラムの実行効率を向上させるための課題の1つに、データの分割と配置の問題（分割配置）がある。その結果によって、実行対象となるプログラムの並列性、通信オーバヘッド、および負荷分散が影響される。科学技術計算のプログラムに対するデータの分割配置には、データのアクセスパターンを記述するために、一般にステンシル構造(stencil structure)が用いられ、その構造にもとづく方法が多く提案されている。本論文は、ステンシル構造をもとに、階層メモリをもつ分散メモリ型マシンを対象として、メモリアクセスに要するプロセッサ間の通信量を定式化し、通信量を最小にするデータの分割配置法を提案するものである。具体的には、与えられたステンシル構造に対し、アクセスベクトルと呼ぶ概念を導入することによって、その構造が表すデータアクセスに必要な通信量を定式化する。その定式化に基づき、通信量が最小になるようにループの繰返し空間の最適分割を求め、分割されたデータ領域を、ループにおけるデータアクセスの性質に従って、ローカルメモリ＋リモートメモリ、さらにはキャッシュメモリ＋ローカルメモリ＋リモートメモリの各層に配置する。最後に複数のループに対する簡易分割配置法を示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: An important problem facing numerous research projects on parallelizing compilers for hierarchical memory machines is that of automatically determining a suitable data partition for a program. A stencil structure can be used for representing a data access pattern, we use stencils to evaluate the communication weight across each memory level, and develop a data partitioning scheme which generates data partitions for an extended sequentially iterated parallel loop to minimize interprocessor communication in hierarchical memory machines. Given a discretion stencil, a vector notation is chosen to quantify communication across a global data set. Communication parameters are used to generate a loop iteration partition that minimize interprocessor communication. Under the given loop partition, the data partition that maximizes local access is obtained by shifting the loop part up by several rows (lines). Furthermore, among the data part this partitioning scheme automatically identifies the exclusive read-write data set, and move these data into the cache to reduce the data traffic for ensuring memory coherence. For reducing conflict among different optimal partitions, a cooperated partitioning method is proposed.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 情報処理学会研究報告計算機アーキテクチャ（ARC）; 巻 1994, 号 91(1994-ARC-108), p. 1-8, 発行日 1994-10-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会