ハイエンドコンピューティング技術に関する調査研究� ―　高性能プラットフォーム技術を中心とする　―

今後の有力な並列システムである分散共有メモリシステムと、OpenMPを用いた並列プログラミングの実際と問題点、今後の課題について述べる。

1．分散共有メモリシステムとOpenMP
　DSM（分散共有メモリシステム）システムとは、物理的に分散配置されたメモリを共有メモリとして構成したシステムであり、論理的にはすべてのアドレス空間を通常のロード、ストア命令でアクセスできる。ただし、物理的には分散配置されているので、図1に示すように、自プロセッサに直接接続されたメモリへのアクセスは高速だが、他のプロセッサに接続されたメモリへのアクセスは低速となる。このようなマシンとしては、スタンフォード大学で研究されたDASH［1］や、商用機としてはSGIのOriginシリーズ［2］、NECのCenju-4［3］などがある。

このようなDSMシステム上の並列プログラミングインタフェースとしては、OpenMP［4］が有望と目されている。OpenMPは、共有メモリシステム向けの並列化インタフェースであり、主に、ループの各繰り返しや計算処理のまとまりを単位として、これらを別々のプロセッサで実行させることをユーザが明示的に指示することにより並列化を行うことができる。たとえば、ループの並列化の例では以下のように、ループを

で囲むことにより、各繰り返しを並列実行することをコンパイラに伝える。

　ここで注意すべきは、OpenMPの並列化は、計算処理のプロセッサへの振り分けが主眼であり、データを分散メモリ上にどのように配置するかについては、何もユーザが記述する術がない点である。図1に示すとおり、ある計算処理とそれに用いられるデータが同じプロセッサとメモリにあれば高速処理ができるが、これらを全く考慮しなければ、大半の計算処理でのメモリアクセスがネットワーク経由となり効率低下を招く[5]。このための制御（Affinity制御と呼ばれる）をコンパイラ、ユーザでどのように分担するか、またその際の言語インタフェースはどうすべきかが重要である。データ階層を対象とするコンパイラの最適化については、文献[6]によくまとまっている。
　DSMシステムでは、一般にデータの（物理的）分散メモリ上への配置は、ページ単位に行われる。このことが2つの困難な問題を発生させる。1つは、データのマッピングがページ単位にしか行えないことであり、2つ目はこれと関連するが、キャッシュのFalse Sharingという問題である。
　一つ目のページ単位のマッピングという問題は、Fortranプログラムにデータ配置の連続性を仮定したものが多いという問題と関連がある。たとえば、A（100,100）という倍精度（8バイト）の2次元配列をマッピングすることを考えてみる。Fortranでは1次元目（列）方向が連続に配置されるデータレイアウトになる。ページが仮に4KBだとすると、倍精度データが512要素。これは、配列Aが5列と少しということになる。4プロセッサの実行では、2次元目で分割し、25列ずつをプロセッサに割り付けると効率が良いが、ページ単位の分割では、これができない。境界部分では、どちらかのプロセッサメモリに両方のプロセッサがアクセスするデータがページとして配置されることになる（図2参照）。これを防ぐためには、データ境界部分について、余分な未使用領域を確保し、データの分割サイズとページサイズを合致させることが考えられる。ただし、この場合には論理空間上のデータの連続性が損なわれるため、メモリの連続性を仮定したプログラムは不正動作をすることになる。また、プログラムの並列化の都合で、1次元目で分割したいこともありうるが、これもデータの連続性を保ったまま分割することはできない。

　2つ目の問題、False Sharingは、キャッシュの一貫性制御の単位であるキャッシュラインを、複数のプロセッサで同時に利用することにより発生する。キャッシュラインは、32バイトや64バイトなどの単位で管理されるが、この1ラインの中に複数プロセッサがアクセスするデータの境界が来ると、双方の処理で、たとえデータの受け渡しをする必要がなくとも、キャッシュライン単位でデータの一貫性制御を行うために、双方でデータを更新するたびに、他方が保持するキャッシュデータを消し合うことになる。数値計算では、問題の境界部分の処理を目的として、Nの計算領域のために、N+1のデータ領域を確保することが良くある。このような場合にもFalse Sharingが発生することになる(図3参照)。

2．MPIとOpenMPの比較
　DSMシステム上の並列化インタフェースとしては、多くのマシンがMPI（Message Passing Interface）[7]もサポートしている。MPICH[8]でも、lfshmemというロックフリーの同期機構を用いた実装がフリーソフトとして提供されている。OSやMPIの実装にも依存するが、MPIはSPMD（Single Program Multiple Data Stream）の形式で並列実行が実現されるため、各プロセッサには、プロセスまたはスレッドの上で同一のプログラムがロードされ実行される。各プロセッサが用いるデータは基本的にプロセッサローカルなものだけであるため、それぞれの利用するデータを別ページとして、プロセッサに直接接続されたメモリに貼り付けることが容易である。プロセッサ間のデータの共有は、すべてMPIライブラリを介して行われるため、Affinity制御の問題や複数プロセッサによる同一データ（キャッシュライン）参照の問題はすべてライブラリの中に分離することができる。
　一方で、MPIはもともと分散メモリマシン用に開発されたインタフェースであり、OpenMPで必要となる計算処理の分割だけでなく、対象データの分割、プロセッサ間のデータ転送、同期などをすべてユーザが明示的に記述する必要がある。それだけプログラミングは複雑になりユーザの負担は飛躍的に増大する。また、分散メモリで動作可能なMPIプログラムをDSMシステムで動作させることは、DSMに余計なHWコストをかけて共有メモリを構築する意味が薄れてしまう。

3．DSM上のAffinity制御
　そこで、DSM上でOpenMPプログラムを動作させ、さらにAffinity制御を行う方法がいろいろと検討されている。代表的な手法が、First Touch Methodと明示的マッピング指定である。これらは、SGIのOriginシステム[9]や、Compaqのシステム[10]で実装されている。
　First Touch Methodとは、データをメモリ上に確保する際に、実際にデータがアクセスされるまでは、ページの登録だけをしておいて、物理メモリにはunmappedの状態にしておく。そして、最初のアクセスに最も適した形でページを配置する（アクセスしたプロセッサのメモリにページを貼り付ける）方法である。たとえば、下記のプログラムを考える。

（例2）First Touch MethodによるAffinity制御

!$OMP DO
　　DO I=1,N　　　　　　　！Aの初期化ループ
　　　A(I)=0.0D0
　　ENDDO

　　・・・

!$OMP DO
　　DO I=1,N
　　・・・　=　A(I) ＋　・・・　　　！A(I)を用いた計算処理
　　ENDDO
　・・・

　最初に配列A(I)の初期化処理が行われ、あとの計算主要部にてA(I)がアクセスされる。この場合、計算処理における複数プロセッサからのA(I)のアクセスパターンが初期化部のそれと同一であれば、初期化時点で、A(I)をアクセスしたプロセッサのメモリに対応するデータをマッピングすれば、計算主要部におけるAffinityを得ることができる。一般的に、この制御はシステムにより自動的に行うことができるため、ユーザは特に何も指定する必要がない。さらに、計算途中でマッピングを変更できる機能を持つシステムもある。Compaqでは、MIGRATE_NEXT_TOUCHという機構により、データマッピングを一旦白紙に戻し、後続のループ処理にAffinityを取る形でデータを再構成することができる。
　データの明示的分散配置指定は、HPF（High Performance Fortran）[11]と同様の方法でユーザが陽にデータマッピングを与える方法である。ただし、ページ単位のマッピング（データ配置の連続性を保証する場合）には、厳密にユーザの指定通りに配置されるわけではなく、ページ境界を考えて、できる範囲でのマッピングとなる。データの連続性を保証しなくて良い場合には、メモリ上のデータの詰め替えや非利用エリアでページを埋めるなどして、厳密なユーザ指定に従うこともできる。
　参考までに、SGIシステムでサポートされているAffinity制御のためのOpenMPの拡張仕様を説明する[9]。

!$SGI DISTRIBUTE
　　配列に明示的マッピング指示を与える。ただしデータの論理空間上の連続性を保持して配置する。
!$SGI DISTRIBUTE_RESHAPE
　　配列に明示的マッピング指示を与える。ただし、データの連続性は保持しない。データ配置の連続性を仮定した
　　プログラムでは結果不正を起こす可能性がある。
!$SGI DYNAMIC
　　配列データのマッピングを変更する可能性があることを指示する。
!$SGI REDISTRIBUTE
　　実行途中で、データのマッピングを変更する。
!$SGI PAGE_PLACE
　　HPFでいうところのGEN_BLOCKに相当。配列を任意の数の部分に分割し、それぞれの分割片の先頭アドレス、
　　サイズ、割り付けるべきプロセッサ番号を与え、その分割片を明示的にプロセッサメモリにマッピングする。
!$SGI AFFINITY(idx)=data(array(expr))
　　DOループに対する指示であり、ループ空間の計算マッピングに合わせて、指定した配列をマッピングすることを指定。

　参考文献[9]には、上記指示を用いた種々の最適化例が掲載されているので、興味のある方は参照されたい。

4．擬似SPMDプログラミングによる高速化
　Houston大学のBarbara Chapmanらは、ここまでで述べたAffinity制御によりある程度の高速化は可能だが、16プロセッサ以上の並列実行では、さらなる最適化が必要だと主張している[12]。もっとも確実にAffinity制御を実現する方法は、実は先にも述べた通り、MPIによるプログラミングである。データのプロセッサ間での共有は通信部分に隠蔽できる。この考え方をOpenMPプログラミングに適用する。SPMDモデルにおけるそれぞれのローカルデータ領域は、OpenMPのPrivate変数（スレッドごとに独立に確保される変数）を用いて表現できる。そして、通信バッファ領域としてShared変数を確保しておき、プロセッサ間でのデータの共有をバッファエリアとローカルデータ領域のデータ移送部分に隠蔽するのである。図4に擬似SPMDプログラミングの概要を示す。上の図は通常のOpenMPプログラミングであり、Sharedデータを全プロセッサがアクセスする。それに比べ、下図では、プロセッサごとにPrivate領域を確保し、計算処理では、これだけを用いる。必要に応じて、HPFでいうところのSHADOW領域と同様の袖領域も確保される。Sharedデータは、通信バッファ領域だけであり、プロセッサ間のデータのやりとりは、この領域へのアクセスに押し込めることができる。
　彼女たちは、本手法をOrigin2000上で、Jacobi反復などのテストコードを用いて評価し、単なるFirst Touch手法による方法に比べて明示的データマッピングを行った方が高速だが、8プロセッサ程度で高速化が飽和する。これに比べ、擬似SPMDコーディングを行えば、32プロセッサまでスケーラブルな性能向上が得られることを示している（データ等は、文献[12]に併記したURLより参照可能）。
　このプログラミングテクニックは有効であるが、プログラミングが大変である。共有メモリでの容易な並列化を狙って標準化が進められたOpenMPであるにもかかわらず、MPIと同じ程度複雑なプログラミングが要求される。プログラムによっては、MPIを用いればトップダウンに手続き処理単位のマクロなレベルで並列化できる場合があるが、OpenMPでは、それぞれのDOループについてボトムアップの並列化対応も必要になるので、こちらがより大変になるケースもある。何らかの言語処理系の支援によって、このSPMDコーディングを容易にする方策が必須である。HPFコンパイラは、逐次コードにデータマッピング指示を加えたものをSPMDコードに自動変換するシステムであるので、ここで蓄積された技術が活かせるのではと期待している。

5．言語インタフェース標準化の動向と関連研究
　OpenMPは共有メモリ用のデファクト標準を目指して作られた言語であり、シンプルできれいな言語インタフェースである。これに、DSM向けのデータマッピング指定機能を付加するかどうかがOpenMPのARB（Architecture Review Board）などで議論されている。DSMという特定のクラスの計算システムだけのために機能付加を行って、言語の簡潔さを損なうことは避けたい。かといって、DSMシステムのベンダがそれぞれ独自の指示行を追加していくと、言語のPortabilityが損なわれる。昨年末から、Barbara ChapmanらはHPFの基本機能からOpenMPに付加すべきデータマッピング指示を整理して、OpenMP拡張仕様案をとりまとめる作業に着手している。また、前節でも述べた通り、DSMではプロセッサ間で境界データをやりとりする処理が性能ボトルネックとなるケースが多い。日本でHPFの拡張機能としてとりまとめられたHPF/JA[13]にSHADOW通信の明示的最適化機能が含まれるが、これがOpenMPでは有効だという議論もなされている。
　この他には、日立で、自動データレイアウト機能を用いた、最適First Touchコードを自動挿入する手法が研究されている[14]。手続き間解析が必須であり、またコンパイル時の静的な情報だけでは難しいケースもあるが、面白い試みだと思う。
　また、RWCPの佐藤らのグループが、Omni-OpenMPという処理系を開発し、フリーソフトとして公開している[15]。共有メモリマシンや、クラスタに実装されたソフトウェアDSM上でもかなり良い性能を達成している。

6．まとめ
　DSMというシステムは、メモリを分散配置することで、スケーラブルに接続台数を増やせるHWを実現可能にしつつ、利用者には共有メモリビューを提供するという非常に野心的なシステムである。今後、さらに種々のベンダからDSMシステムが商用化されることが予想される。問題は、性能のスケーラビリティーが得られるかどうかであり、プログラミングインタフェース、コンパイラ最適化手法の両面からさらなる研究が期待される。
　ある意味で、DSM上のOpenMPというのは、機能要件として、元の共有メモリ上のインタフェースとMPIとの間に位置するものが要求される。この意味ではHPFの技術と共通するものが多い。HPFとの違いは、HPFが分散メモリを対象にすることで、通信最適化において、正常動作を保証するために、保守的な実装を強制されることがあるが、DSM上OpenMPの通信最適化は、最悪でも共有メモリ機能があるので、うまくやればOptimisticな最適化ができるかもしれない。一方で、OSのジョブスケジューリング機能やページ管理、ページマイグレーションPolicyなどと整合性をとった最適化が要求されるという点に難しさがある。今後、MPIやHPF、そしてOpenMPがそれぞれどのように進化していくのか、あるいは全く別のプログラミングパラダイムが現れるのか、非常に興味深いところである。

[1] Lenoski, D., et. al., The Stanford Dash Multiprocessor, IEEE Computer, 25(3), March 1992, pp. 63-79.

[2] J. Laudon and D. Lenoski, The SGI Origin ccNUMA Highly Scalable Server, SGI White Paper, March 1997.

[3] 細見他、並列計算機Cenju-4の分散共有メモリ機構，情処論文誌Vol.41 No.05-17, 2000年4月.

[4] OpenMP Architecture Review Board, OpenMP Fortran Application Program Interface, Version 2.0, November 2000. ( http://www.openmp.org/)

[5] T. Faulkner, Performance Implications of Process and Memory Placement using a Multi-Level Parallel Programming Model on the Cray Origin 2000., 1998, http://www.nas.nasa.gov/~faulkner/home.html.

[6] J. Anderson, Data and Computation Transformations for Multiprocessors , In Proc. Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '95), Santa Barbara, CA, July 19--21, 1995.
http://suif.stanford.edu/papers/anderson95/paper.html

[7] Message Passing Interface Forum 1994. MPI: A Message-Passing Interface Standard, The International Journal of Supercomputing Applications and High Performance Computing, Vol.8, No. 3/4, pp. 165-416.
http://www-unix.mcs.anl.gov/mpi/

[9] Silicon Graphics Inc., MIPSPro Fortran 90 Commands and Directives Reference Manual. Document number 007-3696-003. (http://techpubs.sgi.com/library/　から検索可能)

[10] J. Bircsak, et. al., Extendinf OpenMP for NUMA Machines, In SC2000, Dalls, Texas, November 2000.

[11] High Performance Fortran Forum. 1997. High Performance Fortran Language Specification. Version 2.0. Technical Report TR, Rice University, January 1997. http://www.crpc.rice.edu/HPFF/

[13] Japan Association of High Performance Fortran, 1999, HPF/JA Language Specification Version 1.0, RIST (English version is available at http://www.tokyo.rist.or.jp/jahpf/index-e.html).

[14] 廣岡孝志，太田寛，菊池純男，ファーストタッチ制御による分散共有メモリ向け自動データ分散方法，情処論文誌 Vol. 41 No.05 – 020, 2000年4月.

3.4.3 分散共有メモリ向け並列プログラミングインタフェースの動向

3.4.3　分散共有メモリ向け並列プログラミングインタフェースの動向