計算機科学 理解への道

 ここでは大学生及び社会人の方を対象とした並列計算への理解のための知識を参考文献を引用しながら紹介していきます。
------------------------------------------------------------------------------
小柳義夫、「ハイパフォーマンスコンピューティングによる計算科学の歴史・現状・展望」、応用物理、80 (2011) 557.

 

◆ 3.2 動作周波数の高速化

 通常のCPU(Central Processing Unit)は、クロックと呼ばれる矩形信号に同期して動作する。1秒間のクロック回数を動作周波数と呼び、Hz(ヘルツ)という単位で表す。ENIACは5 kHz で動作したが、現在の最高速のクロックは 5 GHz 程度である。1クロックで行う処理はCPUによって違うので単純に比較はできないが、約60年間でクロックは106 倍向上した。これが性能向上の大きな要因である。しかし数兆(1012)倍の向上にはまだ106倍以上足りない。最近では動作周波数の高速化は頭打ちであり、電力消費を減らすために、むしろ1〜2 GHz 程度の低い周波数で動くプロセッサも多い。

 

3.3 命令レベル並列化

 現在のコンピュータの基本となっているフォン・ノイマン・アーキテクチャでは、一つずつ命令を読み出して逐次的に実行することになっている。しかし、現在のプロセッサは複数の命令を並列に実行する。このような並列処理を命令レベル並列化という。もちろん、逐次的に実行したのと論理的に同一の結果を出すようにハードウェアで制御されている。これにはいくつかの技術がある。

 

(1) スーパスカラ

 後述するベクトルプロセッサに対して、汎用のプロセッサをスカラプロセッサと呼ぶ。スーパスカラとは、1クロックに複数の命令を発行する技術である。逐次的に実行したのと同一の結果を出すようにするためには、同時に実行できる命令の数に制限がつく。この制限のため、1クロック当たりの実行命令数は余り増やすことができないことが示されている。

 

(2) パイプライン

 パイプラインとは流れ作業のことをいう。コンピュータでは、高速化のためにいろいろなレベルでパイプラインが用いられている。特に、実行に複数クロックを要する処理の命令を、クロックごとに1個または複数個発行し、流れ作業により多数の処理を少ないクロックで行う技術を演算パイプラインと呼ぶ。ただし、逐次的に実行したのと同一の結果を出すように制御する必要がある。実際にはスーパスカラと併用される。

 

(3) VLIW(Very Long Instruction Word)

 特殊な命令の形式で、一つの命令が多くのフィールドから成り、1命令で複数の処理を起動する技術である。スーパスカラと似ているが、VLIWでは、逐次的に実行したのと同一の結果を出すように保証するのはコンパイラであり、スーパスカラのようにハードウェアで制御するのではない。Intel の Itanium プロセッサで用いられている IA 64 命令セットはVLIWである。

 

(4) マルチスレッディング

 一続きの演算処理をスレッド(Thread)という。単一のCPUで、複数のスレッドを同時実行することにより、見かけの資源を増やす技術をマルチスレッディングという。特に、データ待ちの間に他の処理が実行できれば、メモリレイテンシを隠蔽する効果がある。資源の競合もあり、またスレッドを切り替えるには若干のオーバヘッドが必要なので、複数のスレッドを同時実行しても性能がスレッド数倍になるとは限らない。


◆ 3.6 複数演算器の同時実行
 科学技術計算では多数の浮動小数の演算が実行される。このため現在のプロセッサには多数の浮動小数演算器が設置されて並列に動作する。これは命令レベル並列化の一種であるが、ここでまとめて議論する。

(1) 浮動小数演算器
 フォン・ノイマン・アーキテクチャでは、演算器は1台だけ存在することになっているが、現代のプロセッサでは多くの演算器、特に浮動小数演算器が装備されている。浮動小数加減算と乗算がそれぞれ1個ずつ実行できる浮動小数演算器をMAD(Multiply and Add)と呼ぶが、多くの汎用プロセッサにはMADが1組ないし2組用意されている。すなわち同時に最大4回の浮動小数演算を実行することができる。

(2) グラフィック・コントローラ
 最近のプロセッサには、グラフィックスや科学技術計算のためにSIMDの演算器が設置され、それを動かす拡張命令が備えられている。代表的なものはインテル社のSSE(Streaming SIMD Extension)であり、4個の 32bit ないし 64bit 浮動小数データの集合に対し同一の命令を(a + b とか a * b + c とか)を実行する。さまざまな拡張がなされている。AMD社のプロセッサにも実装されている。IBM社はこれと類似しているVMX(Vector Multimedia Extension)をPowerPCなどに実装している。ベクトル命令とも呼ばれるが、後に述べるベクトルプロセッサとは、類似点もあるが、異なる点も多い。

(3) GPU
 GPU(Graphics Processing Unit)は、PCにおいてグラフィックス処理を専用に行うチップであり、グラフィック・コントローラから発展した。グラフィックスのためには多くの浮動小数演算を実行する必要があり、GPUには多数の(例えば512)演算器が用意されている。最近では科学技術計算に特化したGPUが登場し、GPGPU(General Purpose GPU)という矛盾した呼び名がつけられている。上述の2010年11月発表のTop 500リストのトップ4台中3台はTianhe-1Aを含めGPGPUを用いて高い性能を実現している。

(4) ベクトルプロセッサ
 ベクトル処理とは、パイプラインの一種で、多数のデータに対する同一の演算を、パイプライン処理により高速に実行する技術である。IBMのSenzigらによって提案されたが、Cray-1(1977)において初めて大規模に実用化した。Cray-1ではベクトル演算器は2台であったが、その後、多数のベクトル演算器を並列に動作させるベクトルコンピューターがスーパーコンピューターの主流である時代を迎えた。しかし、汎用プロセッサの高性能化に伴いスカラプロセッサの超並列機が首位を取って代わった。

◆ 3.7 メモリシステムの高速化
 かつては、コンピューターの性能を決めていたのは演算器の性能であった。しかし、今では演算器よりもメモリシステムの性能が重要である。いくら演算器が速くても、演算の対象であるデータが高速に供給されなければ演算を行うことができないからである。半導体技術の進歩によりメモリも高速化されてきたが、演算器の高速化には追いついていない。

 

(1) バンド幅

 メモリの性能としては、バンド幅とレイテンシが重要である。バンド幅とはメモリとCPUとの間の最大通信速度である。バンド幅と演算速度の比をBF比という。すなわち1浮動小数演算に対して何バイトのデータの供給が可能かという数字である。筑波大学のcp-pacsや海洋研究開発機構の地球シミュレータ(当初)では4 Byte/Flop、すなわち1演算に対して(64 bit のデータで)0.5語が供給可能であった。かなり小さいようにみえるが、QCDの計算にはほぼ十分であった。現在ではこの数字は下がりつつあり、例えば次世代の「京」コンピュータでは0.5 Byte/Flopえある。バンド幅を制約しているのはCPUチップのピン数である。半導体技術の進歩によりチップのトランジスタ数は増えたが、ピン数はほとんど増えない。特にマルチコア・プロセッサでは深刻である。8個のコアを載せてもピン数を8倍にすることはできず、BF比は必然的に低下する。

 

(2) メモリレイテンシ
 メモリレイテンシも主記憶容量の増大とともに増加の傾向にある。しかし、以下に示す技術によりレイテンシについては隠蔽する可能性がある。ただしバンド幅の制約は隠蔽することができない。

 

(3) キャッシュメモリ

 コンピュータにおいて演算器の性能がメモリの性能に追いつかないため、小容量の高速メモリをCPUと主記憶の間に置き、両者の性能差を埋めるために用いる。これをキャッシュメモリ(Cache Memory)と呼ぶ。通常、キャッシュメモリはプログラムから制御せず、一定のアルゴリズムにより、主記憶のある一部分のコピーを保持する。キャッシュはアドレスの上位の何 bit かを共有し、連続するアドレスをもつ一定の長さ(キャシュラインという)を単位に制限され、キャシュラインを単位に主記憶とデータをやり取りする。

 CPUがデータを要求したとき、データがキャシュに依存する割合をキャッシュヒット率という。ヒット率が高ければデータを取り出す時間が短縮される。ヒット率が高くなるのは、プログラムに時間的な局所性が存在する場合である。時間的な局所性とは、一度アクセス(読み出しまたは書き出し)したデータが直後に何度もアクセスされることである。その場合、演算はキャッシュ上のデータに対して行うので、主記憶へのアクセスが減少する。空間的な局所性とは、アドレスに近いデータに引き続いてアクセスすることである。キャッシュ上のデータが有効利用されるからである。

 現在では、キャッシュを3段層程度に設置することが多い。L1(レベル1キャッシュ)は、CPUのすぐそばにあり、1クロックでデータにアクセスできるほど高速であるが、容量は少ない。L2はその次、L3は大容量だがアクセスには何クロックかが掛かる。マルチコア・プロセッサでは、L1とL2はコアごとに装備され、L3は複数のコアで共有するのが典型的である。ヒット率はレベルごとに定義される。

 

(2) プリフェッチ

 キャッシュメモリはプログラムから制御できないのが原則であるが、演算に必要なデータがあらかじめキャッシュにコピーされていれば演算を高速に実行することができる。例えば、ダミーのレジスタにロードする命令により、キャッシュにデータが転送される。うまくいけばメモリレイテンシを隠蔽できるが、もしキャッシュがあふれると無駄になり、主記憶のバンド幅を浪費する危険もある。

 

(3) プリロード

 演算に必要なデータを演算より前にCPUのレジスタにコピーしておく技術。これによりメモリレイテンシを隠蔽することができる。ただし、レジスタ数が多くないと十分隠蔽できない。筆者が関係したCP-PACSのSliding-window技術や、Itanium系のプロセッサでも用いられいるIA64アーキテクチャのRotate命令などがこれにあたる。

 

(4) プログラムから制御できるキャッシュ

 上述のようにキャッシュメモリへのデータの出し入れは一定のアルゴリズムに基づいて自動的に制御され、ユーザーが介入することはできない。しかし、ユーザーはどのデータが再利用されるかを知っているわけであるから、もしキャッシュへのデータの出し入れをユーザーからコントロールできればキャッシュを有効に利用し、メインメモリへのアクセスを減少させることができる。そのような機能をもつCPUもある。例えば、SX-9にはADB(Addressable Data Buffer)が、「京」コンピュータのCPUにはセクタ・キャッシュが用意され、プログラムのディレクティブにより制御することができる。

 

◆ 3.8 並列化技術

 前に述べた命令レベル並列性なども講義の並列化技術であるが、ここでは複数のプロセッサを並列化する技術について述べる。数兆倍の性能向上のかなりは並列化によって達成された。

 並列性は、大きく分けて「共有メモリ並列」と「分散メモリj並列」に分類される。対称型マルチプロセッサと分散共有マルチプロセッサが共有メモリ並列で、どのプロセッサからも主記憶の任意のアドレスにアクセスできる。

 マルチコア・プロセッサでは、多くの場合、チップ上のCPU間では共有メモリとして動作する。複数のチップで共有メモリを実現できる機能をもつものである。

 

(1) 対称型マルチプロセッサ

 複数のCPUに対し、ただ1個の主記憶がシステム中に存在し、主記憶の任意のアドレスに全てのCPUから同一時間でアクセスできるような並列コンピュータを対称型マルチプロセッサ(Symmetric Multi-Processor: SMP)という。各CPUにはキャッシュが存在するが、通常はキャッシュ・コヒーレントになるような仕掛けが用意されている。

 対称型マルチプロセッサでは、全てのプロセッサに対して主記憶が入口を持たなければならないので、あまり多くのプロセッサ数には対応できない。

 

(2) 分散共有マルチプロセッサ

 各CPUは固有の主記憶をもっているが、他のCPUからもネットワーク経由でアクセスできるような並列コンピュータを分散共有(Distributed Shared Memory : DSM)マルチプロセッサという。主記憶は分散しているが、アドレスは共有だからである。ただし、CPUから自分の主記憶へはネットワーク経由なので時間が掛かる。その意味でNUMA(Non-Uniform Memory Access)と呼ばれることもある。これに対しSMPをUMA(Uniform Memory Access)と呼ぶ。キャッシュ・コヒーレントな分散共有マルチプロセッサをcc-NUMAと呼ぶ。現在では、SMPといっても完全に同一の時間でアクセスできるわけではないので、SMPとDSMとの区別は曖昧になりつつある。

 どちらの場合も、並列処理はCPUど同数のスレッドを立ち上げて記述する。OpenMPが用いられることも多い。

 

(3) 分散メモリ並列コンピュータ

 CPUと主記憶をもつコンピュータを多数、何らかの相互結合ネットワークで結合した並列コンピュータのことである。CPUは自分の主記憶しかアクセスできないので、他のCPUの主記憶のデータにアクセスするときは、通信ライブラリを用い相互結合ネットワークを経由してメッセージをやりとりする。通信ライブラリとしては、現在ではMPI(Message Passing Interface)が標準的に用いられている。

 

(4) 混合型並列コンピュータ

 現在の多くの並列コンピュータは、SMPまたはDSMのマルチプロセッサをノードとして、ノード間を相互結合ネットワークで結合したシステムである。これを混合型並列コンピュータという。プログラミングスタイルとしては、ノード内ではOpenMPでプログラムし、これをMPIで結合するのが普通である。もちろん、ノード内の各CPUを独立させて、それらの間をMPIで通信する手法もある。どちらが有利かはアプリケーションの性質、ノードの構築などに依存する。

 

3.9 並列言語

 並列コンピュータに並列処理を行わせるには、並列性を何らかの形でプログラムに記述し、それをコンパイラがオブジェクト・コードに変換する必要がある。並列性を記述できるプログラミング言語を並列言語と呼ぶ。既存のプログラミング言語とミドルウェア(例えばMPI)を組み合わせて記述する場合もあるが、これも広い意味で並列言語と呼ばれる。1970年代から多くの研究がおこなわれてきたが、ここでは概観を示す。

 

(1) 並列言語の種類

 並列言語には、大別して明示的言語と非明示的言語がある。

(a)明示的言語とは、プログラマが並列性を直接にプログラムとして記述する。並列処理を細かく制御でき、うまくいけば高い性能を実現できることは長所であるが、プログラムは書きにくく、生産性は低い。FortranまたはC言語でMPIを用いるのがその典型である。

(b)非明示的言語とは、プログラマは逐次的処理としてプログラムを記述するが、コンパイラがそこから並列性を抽出して並列に動くオブジェクト・コードを出力する。プログラムは書きやすいが、意図した並列性がコンパイラに認識されないこともあり、高い性能を実現することは容易ではない。実際には、何かの補助情報をコンパイラに教える必要がある。

 

(2) 並列言語の成立

(a) 自動並列化

 従来の逐次型言語で書いたプログラムを、コンパイラが分析して並列性を抽出し、並列に実行する方式。これが実現できて、しかも高い並列計算効率を達成できればそれに越したことはない。ベクトルコンピュータではある程度これを実現できたが、一般的な並列処理では困難であり、そこから並列言語の研究が始まった。並列性の抽出についてはその後も研究が進んでいる。

(b) 新並列言語

 従来の逐次的な言語とは別に、並列処理を記述するために作った新しい言語、例えば Hoare が提唱した CSP(Communicationg Sequential Processes)に基づいて、Transputer というプロセッサのたえに1980年代に開発された言語 Occam はその一例である。従来の言語との整合性を考慮する必要がないので、並列性を自由に表現できることが最大の長所であるが、逐次的言語で書かれたプログラム資産の並列化には困難が伴う。

(c) 拡張言語方式

 従来の言語に並列性を記述する新しい構文を導入する方式、例えば、Fortran 90 で導入された配列演算は配列性の記述であり、ベクトルコンピュータにおいて容易にベクトル化が可能である。プログラム資産の並列化は全くの新言語よりは容易であるが、新しい構文が古いコンパイラ(例えば Fortran 77)で動かないことは欠点である。

(d) ディレクティブの追加

 従来の言語に、ディレクティブを付加し、並列性を記述する方式。完全な自動並列化は困難なので、ディレクティブによってユーザーの知っている情報をコンパイラに教えることによって並列性を見つけやすくする。HPF(High Performance Fortran)や OpenMP はその典型である。また、ベクトルコンピュータの自動ベクトル化コンパイラもこの形で指示を書くことができた。コメントと同じ形をしているので、従来のコンパイラでコンパイルすると無視されて逐次的に実行することができ、移植が容易である。実際には、いくつかの関数やプロシージャが付加されるので、逐次的に実行するには何らかの対応が必要である。

(e) 関数の付加

 従来の言語に関数やプロシージャを付加して並列性を記述する方式。Fortran や C言語の上で MPI のライブラリを用いてプロセッサ間通信を記述することにより、並列性処理を記述するのが典型である。ベクトルプロセッサの初期に関数でベクトル処理を記述したが、これもその一例である。

 

(3) 共有メモリ並列コンピュータ用の並列言語

(a) スレッド並列処理

 スレッドはプログラムの実行単位で、一つのプロセスには複数のスレッドが属し、主記憶を共有する。単一のCPUで複数のスレッドを実行させると時分割によって見かけ上、並列に走るが、速度が増えるわけではない。しかし複数のCPUでCPUと同数のスレッドを実行させることにより、並列処理を行うことができる。これをスレッド並列処理という。スレッドの生成や消滅は対応するシステム関数を呼ぶことによって記述できるが、煩雑で生産性が上がらない。

(b) OpenMP

 OpenMP はディレクティブを用いた。オープンでポータブルな共有メモリ並列処理記述用のAPI(Application Program Interface)であり、多くのベンダのFortran, C, C++に使用可能である。いくつかのライブラリ関数や実行時関数も用いる。コンパイラはこれをスレッドの制御に翻訳して実行する。Fortran用の仕様は1997年に、C/C++用の仕様は2002年に制定された。1980年代の並列ベクトルコンピュータ全盛時代に、マクロタスキングやマイクロタスキングが広く用いられたが、OpenMP はこれを一般化したものとみることもできる。

 

(4) 分散メモリ並列コンピュータ用の並列言語やミドルウェア

(a) PVM

 ネットワークで結合されたPCやワークステーション(「クラスタ」と呼ばれる)を並列コンピュータとして動作させるためのソフトウェアがPVM(Parallel Virtual Machine)である。PVMは米国のORNL(Oak Ride National Laboratory)で1989年から開発が始められた。大学、研究所、企業の研究者が共同で開発し、ソフトウェアを世界中に無料で公開した。当時は並列コンピュータ・ベンダごとに通信ライブラリが異なり、プログラムに互換性がなかったが、PVMはクラスタに限らず、分散メモリ並列コンピュータの標準通信ライブラリ・インターフェイスの役割も果たした。この機能は MPI に引き継がれたが、PVMは、異機種間の接続、プロセスの起動や停止など初期の MPI のもっていなかった機能をもっていた。しかしこれらの機能を取り入れたMPI2が実用化した現在ではPVMの存在理由はなくなった。

(b) MPI

 さらに進んで分散メモリ並列コンピュータのための共通通信インターフェイスを定めようという動きが1992年に起こり、MPI Forum という研究者による自発的な組織が作られた。2年間の努力の結果、プログラミング言語に依存しない通信インタフェース MPI 1.0が1994年に公表され、 Fortran, C, C++に実装された。直ちにこれが分散メモリ並列処理のための事実上の標準となった。さらに機能を強化したMPI2.0は1996年に完成した。現在MPI3の制定が進んでいる。

(c) HPF

 Fortran 90 を拡張して、ディレクティブによる並列言語を作ろうとする動きが、1991年にアルパカーキで開かれたSupercomputing '91国際会議で起こり、直ちにHPFF(High Performance Fortran Forum)という大学、研究所、企業の研究者の自発的組織が結成された。最初の規格HPF 1.0は1993年に制定された。この活動はMPIの規格制定の活動とほぼ同時期であることは注目される。1997年にはさらに拡張したHPF 2.0が制定された。日本の地球シミュレータ(横浜、海洋開発研究機構、2002年完成)では標準言語とされたが、残ながら世界的に普及しているとはいえない。

(d) PGAS

 現在では、MPI を含む Fortran またはCでプログラムするのが最も一般的であるが、通信機能を全て明示的に記述する必要があり、プログラムの生産性は高くない。最近注目されているがの、PGAS(Partitioned Global Address Space)というプログラミング・モデルである。これは分散メモリに統一的な線形アドレスを割る付けて、各プロセッサはその一部を所有しているというモデルである。PGASは、Unified Parallel C, Co-arry Fortran, Titanium, Fortress, Chapel, X 10などの新しい言語の基礎となっているモデルである。筑波大学を中心に開発が進められているXcalableMPも基本的にPGASのコンセプトに基づいている。

 

今後、並列処理を普及するためには、柔軟性があり、同時に、使いやすい並列言語の実現が極めて重要である。
------------------------------------------------------------------------------


QRコード
携帯用QRコード
アクセス数
ページビュー数
[無料でホームページを作成] [通報・削除依頼]