階層構造型マルチプロセッサに対するプログラムの最適並列化技法

本研究では,操作型プログラムを対象として,階層構造型のメモリをもつマルチプロセッサ,すなわち分散共有メモリマシンおよび分散メモリマシンに対するデータの最適配置法およびデータ転送の最適化手法を開発し,その効果を実験によって評価した.まず,多重ループにおける配列へのアクセスをパターンとして簡潔に表現するために,ステンシル構造とよぶ概念を導入し,ステンシル構造を用いてメモリアクセスに要するプロセッサ間のデータ通信量を定式化した.その定式化をもとに通信量を最小にするためのデータの分割法を示した.最適分割のあと,各プロセッサについて,ループにおけるデータアクセスの特徴によって,分割されたデータ領域をキャッシュメモリ,ローカルメモリ,またはリモートメモリの各層に配置するための方法を提案した.この方法を用いた場合と用いない場合とについて,ワークステーション上でのシミュレーション,および分散共有メモリ型のマシンASPIRE上でのプログラム実行の実験から,本手法の有効性が確かめられた.最適なデータ分割配置に続いて,分散メモリマシンを対象に個々のプロセッサ上での冗長なデータ転送をデータフロー解析によって検出するためのアルゴリズムを考えた.他のプロセッサのメモリ中にある配列要素への参照が起ったとき,その値がそれ以前の実行によってすでに得られていることが保証できれば,データ転送を避けることができる.この点に着目して,プロセッサと,そのプロセッサにとって値が再利用できる部分配列の対を未知数としたデータフロー方程式を作り,区間解析によってその解を求める方法を提案した.この解析結果を利用した場合の効果についても,分散並列マシンAP1000上でのプログラム実行によって確認した.

本研究では,操作型プログラムを対象として,階層構造型のメモリをもつマルチプロセッサ,すなわち分散共有メモリマシンおよび分散メモリマシンに対するデータの最適配置法およびデータ転送の最適化手法を開発し,その効果を実験によって評価した.まず,多重ループにおける配列へのアクセスをパターンとして簡潔に表現するために,ステンシル構造とよぶ概念を導入し,ステンシル構造を用いてメモリアクセスに要するプロセッサ間のデータ通信量を定式化した.その定式化をもとに通信量を最小にするためのデータの分割法を示した.最適分割のあと,各プロセッサについて,ループにおけるデータアクセスの特徴によって,分割されたデータ領域をキャッシュメモリ,ローカルメモリ,またはリモートメモリの各層に配置するための方法を提案した.この方法を用いた場合と用いない場合とについて,ワークステーション上でのシミュレーション,および分散共有メモリ型のマシンASPIRE上でのプログラム実行の実験から,本手法の有効性が確かめられた.最適なデータ分割配置に続いて,分散メモリマシンを対象に個々のプロセッサ上での冗長なデータ転送をデータフロー解析によって検出するためのアルゴリズムを考えた.他のプロセッサのメモリ中にある配列要素への参照が起ったとき,その値がそれ以前の実行によってすでに得られていることが保証できれば,データ転送を避けることができる.この点に着目して,プロセッサと,そのプロセッサにとって値が再利用できる部分配列の対を未知数としたデータフロー方程式を作り,区間解析によってその解を求める方法を提案した.この解析結果を利用した場合の効果についても,分散並列マシンAP1000上でのプログラム実行によって確認した.