データ局所性で不規則アプリケーションを治療

Carlo del Mundo

データの局所性は、並列プログラムにおけるエネルギー効率と性能において重要な役割を果たしている。局所性が豊富なデータ並列アルゴリズムにおいては、ユーザ・プログラム可能なローカル·キャッシュを持ったアーキテクチャ用にマップし最適化することは比較的簡単な作業だ。しかし、そのような幅優先探索（BFS）のような不規則なアルゴリズムには、局所性を利用することは些細な仕事ではなくなる。

デラウェア大学の電気および計算機工学部門の教授であるGuang Gaoは、BFSのような不規則アルゴリズムにおける局所性のマッピンや活用の研究を行っている。「BFS問題に関するエネルギー効率の課題の研究は２、３しかありません。ですので、ローカルストレージを持ったアーキテクチャ上でのBFSのエネルギー効率の解析を行うにはさらなる研究が必要です。」とGaoは指摘する。

BFSにおいては、データの局所性は2つの方法のいずれかで利用されている。：内部またはループ間での局所性だ。ループ間とは隣接するループ間のループ本体内での局所性を指す。ループ間では
異なループ内におけるループの反復回数間の局所性を指す。両方の内部およびループ間の局所性を利用することは、プログラマは細粒度の並列をサポートするモデルを活用すると仮定して、比較的簡単だ。

典型的な不規則アルゴリズムへのアプローチは、OpenMPのように伝統的な粗粒度実行モデルの下ではうまく動かない。動機の例としてBFSを使用して、Gaoのチームは細粒度データフロー実行モデルであるCodeletを使用して、データの局所性を利用している。

Codeletモデルでは、計算の単位はcodeletと呼ばれています。各codeletは中断することなく実行可能な連続的なコードの一部です（例えば、同期化は必要ありません）。データ依存は、Codelet graphと呼ばれる直接グラフを通してcodelet間で指定される。実行時に、ランタイムがその依存性に応じてcodeletをスケジュールするのだ。

Codeletモデルは、抽象的並列マシンモデルのコンテキストで実行される。マシンは、インターコネクト・ネットワークを介して大量の演算ノードが接続された構成である。各ノードはCUとSUの2種類のタイプのコアで構成されたメニーコア・チップを搭載している。この不均一性は、異なるパ性能とエネルギーのプロファイルを提供している。弱いコアを必要とするCodeletは、エネルギーを節約するために、コアのタイプのひとつににスケジュールすることができる。逆に、ヘビーデューティーな計算を必要とするCodeletは、より強力なコアにスケジュールすることができるのだ。

Codeletような細粒度データフロー実行モデルを活用することで、Gaoと彼のチームは、従来の粗粒度のOpenMPモデルに比べて7％までメモリアクセスするための運動エネルギーを向上させることができきる。