Linux Parallel Processing HOWTO: はじめに

1. はじめに

並列処理とはプログラムの実行速度を上げる考えで、プログラムを同時に実行可能な複数の部分に分け、それぞれをプロセッサ上で動かします。プログラムを n 個のプロセッサに分けて実行すれば、1 つのプロセッサで動かすのに比べて n 倍速く実行できると考えられます。

これまで複数のプロセッサを持つシステムは、特注で設計した「並列コンピュータ」として世の中に存在していました。現状では、これに加えて Linux が SMP システム(「サーバ」として販売されていることが多い)を提供しています。これは 1 台のコンピュータで複数のプロセッサが 1 つのメモリとバスのインタフェースを共用しています。もちろんコンピュータを複数用意して (例えば Linux が動いている複数の PC を用意する)ネットワークでつないで並列処理クラスタを組むこともできます。Linux を使った並列演算の 3 番目の方法は、マルチメディア拡張命令(すなわち MMX)を使って、整数データのベクトルを並列に扱う方法です。最後は、専用に 搭載されている並列処理計算エンジンを利用するのに Linux システムをホストにしてしまう、という方法です。このドキュメントでは、これらすべてのアプローチを詳しく検討していくことにします。

1.1 何を並列処理に求めるのか？

複数のプロセッサは確かに多くの処理を高速にしますが、並列処理によって恩恵を受けないアプリケーションも多数存在します。一般的には並列処理で効果が出るのは下記の場合に限定されます。

アプリケーションが複数プロセッサを効率的に使用するよう並列化がほどこしてあること。ある面で、これはプログラムの一部分が独立して動作でき、かつその部分が独立したプロセッサで並列して動作するとみなすことにほかならない。ただし、並列で実行できることが特定のシステムではかえって処理速度が遅くなってしまう可能性があることもわかっている。例えば、1 つのプロセッサで実行に 4 秒かかるプログラムがあったとする。そのプログラムが、4 つのマシンでそれぞれ 1 秒で実行できたとしても、これらのマシンが協調して動作するのに 3 秒以上かかってしまえば、結局は処理速度が上がったことにはならない
実行したいと思っているアプリケーションが並列化されている(並列処理向きに手直ししてある)か、少なくとも並列処理で効果がでるように新たにアプリケーションに手をいれるつもりがあること
並列処理に関連する事柄についの研究に興味があるか、少なくとも理解する意志があること。システムで並列処理を使用することは必ずしも困難なことではないが、コンピュータの利用者の大半は並列処理に詳しくなく、今のところ「初めての並列処理」というような書籍も存在しない。この HOWTO は理解するきっかけとしては恰好のものだが、すべてを網羅しているわけではない

幸いなことに上記すべてが本当であっても、Linux を利用した並列処理はスーパーコンピュータ並のパフォーマンスで複雑な計算や巨大なデータセットを扱えます。何よりも、安価なハードウェア(既に所有しているような)で実現できるのが魅力です。さらに良いことには、並列に処理をするほど忙しくなければ、並列 Linux システムで他の処理も簡単に実行できます。

並列処理を望んでいるわけではないが、それなりにパフォーマンスの向上を達成したいと思っているなら、打つ手は他にまだあります。例えば、逐次実行するプログラムのパフォーマンスを上げるには、より高速なプロセッサへの換装やメモリの増設、ディスクを IDE から Fast Wide SCSI に交換する等の方法があります。この点に関心があるなら、セクション 6.2 に進んでください。そうでなければこのまま読み進めてください。

1.2 専門用語

並列処理はこれまで様々なシステムで行われてきていますが、コンピュータユーザの大部分にとって、まだそれほどなじみがあるわけではありません。そこで、いろいろな並列処理について論じる前に、よく使われる用語のいくつかを理解しておきましょう。

SIMD:

SIMD(Single Instruction stream, Multiple Data stream)は並列実行モデルの 1 つで、プロセッサすべてが同じ演算を同時に行う。しかし、それぞれのプロセッサは固有のデータしか扱えない。そもそもこのモデルは、配列の各要素に対して同様な演算するという、ベクトルや配列に関連した操作を得意とする。理由は、演算すべてがもともと同期していて、SIMD プロセッサ間のやりとりが簡単かつ効率良く実装しやすいからである

MIMD:

MIMD(Multiple Instruction stream, Multiple Data stream)は並列実行モデルの 1 つで、基本的にプロセッサそれぞれは独立して動作する。そもそもこのモデルは複数のプログラムを利用して、機能ベースで並列に実行することに長けている。例えば、あるプロセッサがデータベースの更新を行っている間、他のプロセッサは新たに入力された画像の表示を処理しているという具合に。このモデルは SIMD よりも自由度が高いが、悪夢のデバックが必要となる 競合状態に陥る可能性があり、プログラムが断続的に落ちる危険性がある。これはプロセッサが再実行を行うタイミングの問題で、他のプロセッサのタイミングとの関係によって生じる問題である

SPMD:

SPMD(Single Program, Multiple Data)は機能を限定した MIMD で、プロセッサすべてが同じプログラムを実行する。SIMD とは異なり、SPMD のコードを実行するプロセッサはプログラム中でそれぞれ異なった制御の流れをとる

通信帯域幅 (Communication Bandwidth):

通信系の帯域幅とは、転送がはじまってから単位時間当たりに転送できる最大のデータ量を表す。シリアル接続の帯域幅は ボー(baud) や ビット/秒 (b/s)で表すのが普通だが、これはバイト/秒 (B/s)のだいたい 1/10 から 1/8 に当たる。例えば 1200 ボーのモデムは、約 120 ビット/秒伝送し、155 M ビット/秒の ATM 回線は、モデムの 130,000 倍速く、17 M ビット/秒伝送できる。帯域が広ければ大きなブロックのデータを伝送することができ、プロセッサ間で効率良くデータがやり取りできる

通信遅延(Communication Latency):

通信系の遅延は、ある「もの」を伝送するのにかかる最小時間である。これには送受信にかかるソフトウェアのオーバーヘッドも含まれている。並列処理にとって遅延はとても重要であり、これが有効な最小の粒度を決定する。コード単位を実行している時間が短いほど、並列実行が高速になる。基本的に、コード単位を実行する時間がその実行結果を返す時間(例えば、遅延)より短ければ、プロセッサ上で返り値を必要とする連続したコードの実行は、並列実行より速くなるはずである。連続した処理の実行は、通信のオーバーヘッドを避ける必要がある

メッセージ通信(Message Passing):

メッセージ通信は、並列システム内でプロセッサ間でやりとりするモデルの 1 つである。普通はあるプロセッサ上のソフトウェアがメッセージを作成し、相互に接続しているネットワークを経由して送られる。送られたメッセージは受信され、メッセージの内容を実行する必要がある。メッセージを扱うオーバーヘッド(遅延)が大きいかもしれないが、通常はメッセージにどのくらい情報を含められるかについてはほとんど制限がない。したがって、メッセージ通信は広い帯域を生かしつつ、データを大きなブロックにすることにより、プロセッサ間でとても効率的にやりとりができる。しかし、メッセージ通信は時間がかかる処理なので、その必要性を最小限にしなければならない。並列処理プログラムのデータ構造は、広くプロセッサ間にまたがっているので、それぞれのプロセッサが参照するデータは、ローカルなメモリ上にある必要がある。この作業をデータ配置と言う

共有メモリ(Shared Memory):

共有メモリは、並列システムにおけるプロセッサ間のやりとりについてのモデルの 1 つである。Pentium をいくつか搭載しているような複数プロセッサマシンで Linux が動いている場合は、プロセッサは 1 つのメモリを物理的に共有している。したがってあるプロセッサが共有メモリに値を書き込むと他のどのプロセッサからも直接アクセスが可能になる。これとは別に 論理的に共有しているメモリを実装しているシステムもある。その各々のプロセッサは独自のメモリを持ち、ローカルでないメモリへの参照をプロセス間通信に適宜置き換える。普通どちらの共有メモリの実装をとっても、メッセージ通信よりも扱いやすい。物理的に共有されたメモリは広い帯域幅を使えるだけでなく、遅延も少ない。しかしそれは複数のプロセッサが同時にバスにアクセスしないようにした場合だけである。したがって、データ配置はやはりパフォーマンスに重大な影響を与え、キャッシュの効果等でどのデータ配置が最適なのかを判断するのは難しい

集合演算(Aggregate Functions):

メッセージ通信、共有メモリ両モデルとも、通信のきっかけは単独のプロセッサが引き金となる。それとは対照的に、生来の並列処理モデルである集約演算の通信では、各プロセッサが統合され、協調して動作する。そのような動作はバリア同期(barrier synchronization)と呼ばれている。個々のプロセッサは、統合されたプロセッサのそれぞれが処理上のある境界に達するまで待機する。プロセッサ毎にある境界に達したことを示す基準値を生成することで、通信機器はそれぞれのプロセッサに値を返すことが可能になる。そのプロセッサは、独自の演算で得られた値をすべて収集した結果を通信機器の返り値として返すことができる。それは例えば「どのプロセッサが解答を見つけたか？」という問への返答が返り値になる場合もあるし、それぞれのプロセッサからの値の合計が返り値になる場合もある。遅延が極めて少ない反面、プロセッサ毎の帯域幅も狭い傾向にある。元来、このモデルはデータ値を分散させるというよりも、並列実行を制御することを第一の目的としている場合が多い

集合通信(Collective Communication):

集合演算の別名で、集合演算を複数のメッセージ通信を使って実現する場合によく使われる

SMP:

SMP(Symmetric Multi-Processor)はオペレーティング・システムの概念で、対等に協調して動作するプロセッサの集合を表す。つまり、プロセッサそれぞれが処理の部分部分をうまい具合に処理しあう。普通、SMP は MIMD と共有メモリを組み合わせて実現する。IA32 を使ったシステムでは、SMP は MPS(the Intel MultiProcessor Specification)に準拠している。将来的には、「Slot 2」…を意味することになるかもしれない

SWAR:

SWAR(SIMD Within A Register)はレジスタを複数の整数領域に分割する考え方で、レジスタ長命令を使ってこれらの分割された領域で SIMD 並列演算を実行する。 k ビットのレジスタとデータパスと演算装置を持つマシンでは、通常のレジスタ処理は SIMD の並列処理で動くことが知られている。つまり k/n ビットの領域の値として n 個実行できる。このタイプの並列処理化は整数レジスタや整数命令を使って実行されるのが一般的だが、最近のハイエンドなマイクロプロセッサの多くは特殊な命令を追加して、マルチメディア関連処理のパフォーマンスを向上させている。Intel や AMD、Cyrix の MMX(MultiMedia eXtensions)がそれに当り、他にも Digital Alpha の MAX(MultimediA eXtensions)や Hewlett-Packard PA-RISC の MAX(Multimedia Acceleration eXtensions)、MIPS の MDMX (Digital Media eXtension "Mad Max" という)、Sun SPARC V9 の VIS (Visual Instruction Set)がある。MMX を採用しているベンダー 3 社を除いて、これらの命令セットすべては、似ていることは似ているが、それぞれ別個のものである

付加プロセッサ(コプロセッサ):

本来、付加プロセッサは特別な用途向けのコンピュータで、ホスト となるシステムに装着され、特殊な計算を高速に実行する。例えば、PC のビデオカードやオーディオカードの多くには付加プロセッサが載っており、それぞれに共通している画像処理やオーディオの DSP(Digital Signal Processing)処理を高速化する。またあちこちにアレイ・プロセッサ も存在する。こう呼ばれる理由は、アレイ状(配列状)に配置された付加プロセッサ上で、数学的演算を高速に実行するからである。現実的には、商用のスーパーコンピュータの多くはワークステーションというホストに付加プロセッサが載ったものである

RAID:

RAID(Redundant Array of Inexpensive Disks)は、ディスク入出力の帯域幅と信頼性を向上させる技術を指す。バリエーションがいくつもあるが、共通して鍵となる考え方が 2 つある。第 1 は、データブロックそれぞれは n+k 個のディスクドライブ群にストライプされており、それぞれのドライブはデータの 1/n だけ読み書きしなければいけない…ということを利用して、1 つのドライブに対して従来の n 倍の帯域幅を実現することである。第 2 は、データを冗長に書くことによって、ディスクドライブが 1 つ壊れてもデータを復旧できることである。これは重要なことで、冗長化していないと、n+k 個のディスクドライブのどれか 1 つでも駄目になった場合、ファイルシステムが完全に壊れてしまうことになる。RAID についての概要を知りたいならば、 http://www.adaptec.com/worldwide/product/prodtechindex.html?cat=%2fTechnology%2fRAID を、Linux システムの RAID がどのようなものがあるかを知りたければ、 http://linas.org/linux/raid.html を参照のこと。RAID 専用のハードウェアのサポートは別として、Linux はソフトウェアで RAID 0、1、4、 5 をサポートしており、複数のディスクを 1 台の Linux システムで扱える。詳細は、Software RAID mini-HOWTO や the Multi-Disk System Tuning mini-HOWTO を参照のこと。クラスタを組んだ複数のマシン上で複数のディスクドライブにまたがって RAID を組むことは、デフォルトではサポートされていない

【訳註：Multi-Disk System Tuning mini-HOWTO の日本語訳は http://www.linux.or.jp/JF/JFdocs/Multi-Disk-HOWTO.html です】

IA32:

IA32(Intel Architecture, 32-bit)は並列処理とは無関係だが、あるプロセッサの命令セットが Intel の 386 と互換性があるかについてふれている。基本的に、Intel の 286 以後の x86 プロセッサは、32 ビットのフラットなメモリモデルを持っていて、それが IA32 の特徴となっている。AMD と Cyrix も、IA32 互換のプロセッサを数多く製造している。Linux が主として IA32 プロセッサで発展し、商品市場が IA32 を中心として形成された理由は、 PowerPC や Alpha、PA-RISC、MIPS、SPARC 他のそれ以外のプロセッサと比べて利用しやすかった点にある。きたるべき IA64(64-bit with EPIC, Explicitly Parallel Instruction Computing)はきっとそううまくはいかないだろう。Merced と呼ばれる最初の IA64 プロセッサは 1999 年の時点では製造の見通しが立っていない。

【訳註：Merced はプロセッサのコア名となり、プロセッサ名としては、「Itanium」が正式名称となりました。製品版は 2001 年の中ごろになる予定です。既に第 2 世代コアの「McKinley」もアナウンスされていて、2001 年後半に登場する予定です。一方 AMD は、「ClawHammer」と呼ばれる 64 ビットチップを 2002 年後半に登場させる予定です】

市販の既成品:

多くの並列スーパーコンピュータ企業が消えていく中、並列計算システムの必要性から市販の既成品が論じられている。Windows に傾倒しているなら、市販の既成品で PC を使った並列処理技術を生かせるのは、SMP の Windows NT サーバと MMX を使った様々な Windows のアプリケーションということになるが、その考え方には何も得るところがない。市販の既成品に対する考え方の背景には、開発にかかる時間と費用の削減がある。したがって、便利かつ普通に入手できる市販の既成品は、少なくともサブシステムに対して商品市場戦略の恩恵をもたらしてくれる。ただ戦略が目指しているものとは違った技術が効果的に利用されることのなるのだが。大抵の場合、市販の既成品を用いた並列処理とはクラスタを指し、ノードを普通の PC で構成する。しかしネットワーク・インタフェースやソフトウェアは何かしらカスタマイズしてある…普通は Linux 上でフリーで利用できる(例えば、コピーレフトやパブリック・ドメイン)アプリケーションが動いているが、これは市販の既成品ではない

1.3 アルゴリズムの例

この HOWTO でこれから紹介していく様々な並列プログラミング手法を理解するには、例題を見ていくことが有効な手段です。どんな単純な並列アルゴリズムであったとしても、他の様々な並列プログラミングシステムのアプローチを明示してくれるアルゴリズムを選ぶことで、多少なりとも比較対照が楽になります。 M.J.Quinn 氏の著書である Parallel Computing Theory And Practice, second edition, McGraw Hill, New York, 1994 では、円周率を計算する並列アルゴリズムを挙げることで、いろいろな種類の並列スーパーコンピュータでのプログラミング環境(例えば nCUBE のメッセージ通信や Sequent の共有メモリ) を明らかにしています。この HOWTO では同じ基礎的なアルゴリズムを使っていきます。

そのアルゴリズムは、円周率の近似値を x 角形の領域を合計することで計算します。C のプログラムで素直に順次実行すると、アルゴリズムは下記のようになります。

#include <stdlib.h>;
#include <stdio.h>;

main(int argc, char **argv)
{
  register double width, sum;
  register int intervals, i;

  /* get the number of intervals */
  intervals = atoi(argv[1]);
  width = 1.0 / intervals;

  /* do the computation */
  sum = 0;
  for (i=0; i<intervals; ++i) {
    register double x = (i + 0.5) * width;
    sum += 4.0 / (1.0 + x * x);
  }
  sum *= width;

  printf("Estimation of pi is %f\n", sum);

  return(0);
}

しかしこの順次実行のアルゴリズムは、「極めて並列性を上げて」実行できます。領域は間隔単位に細分化され、プロセッサの数の分だけ間隔単位で割り当てた部分を独立に合計できます。ここではプロセッサ間の調整作業は必要ありません。ローカルでの合計が計算されれば、それを合計して総合計をだせばいいわけです。この段階ではプロセッサ間で何らかの調整と計算が発生します。最終的に、この総合計が円周率の近似値としてプロセッサの 1 つが値を出力します。

この HOWTO では、このアルゴリズムを表現した様々な並列処理の実装を提示することで、プログラミング手法の様々な相違を検討していきます。

1.4 このドキュメントの構成

このドキュメントの残りの部分は 5 つに分かれています。セクション 2 と 3、4、5 それぞれは、Linux を使って並列処理をサポートする 3 種の異なるハードウェアの構成にふれています。

セクション 2 では SMP Linux システムを論じる。このシステムは、共有メモリを使って MIMD をそのまま実行できるが、メッセージ通信も簡単に実装できる。Linux は最大で 16 個のプロセッサの設定をサポートしているが、SMP PC システムの大部分は 2 もしくは 4 個の独立したプロセッサを搭載している
セクション 3 ではネットワークに接続していて Linux が動作しているマシンで構成するクラスタについて論じる。クラスタとは並列処理システムで用いられ、MIMD の実行とメッセージ通信、もちろん論理的な共有メモリもサポートする。SIMD の実行をシミュレートしたり、集合演算通信もサポートしているが、これはネットワークの手法に依存している。クラスタ当たりのプロセッサの数は 2 から数千にまで及ぶが、数を制限する要因の第 1 はネットワークの取り回しである。1 つのクラスタに様々なタイプのマシンを組み込むことが可能である。例えば、DEC の Alpha と Pentium の Linux システムで構成されたネットワークを異機種クラスタと呼ぶ
【訳註：DEC は Compaq に吸収されましたが、Alpha マシンは健在です】
セクション 4 では、SWAR(SIMD Within A Register)を論じる。これは非常に制限のある並列実行モデルではあるが、一般的なプロセッサに組み込まれた機能でもある。最近では MMX(やその他類似の)命令セット拡張がプロセッサに加えられており、このアプローチがより有効になってきた
セクション 5 では、Linux PC を単独の並列計算システムを動かすホストとして使用する方法を論じる。付加プロセッサは追加のカードもしくは外付け機器の形をとって、Linux に特定のタイプのアプリケーションの実行に対して圧倒的な処理パワーを提供する。例えば、安価な ISA カードを利用することで、そこに搭載している複数の DSP プロセッサを使って計算の比重が大きい問題に数 100 MFLOPS の能力を割くことができる。しかしこれらの追加のボード類は、まさにプロセッサそのものである。OS が動いているわけでも、ディスクや端末の入出力などがあるわけではない。そのようなシステムを活用するには、Linux という「ホスト」が上記の機能を提供する必要がある

このドキュメントの最後のセクションでは、Linux を使った並列処理一般の関連事項について、上記の特定のアプローチにかかわり無くその特徴を取り上げます。

このドキュメントを読むに当たって気に止めておいて欲しいことは、すべてを検証してあるわけではない、ということです。またここであげた多くの事柄は「まだまだ研究中のものです」(「思うようには動かない」といった方が適切です ;-) しかし Linux を使った並列処理は現状でも役に立ちますし、並列処理をより良いものにするべく、グループとしての活動があちこちで増えつつあります。

この HOWTO の著者は、博士号を持つ Hank Dietz で、現在インディアナ州の郵便番号 47907-1285、ウエストラファイエットにあるパーデュ大学において、 Electrical and Computer Engineering の助教授をしています。Dietz はこのドキュメントに対して、the Linux Documentation Project のガイドラインに準拠した権利を有しています。このドキュメントの発表に当たって、正確で公正になるように努力しましたが、 Dietz 氏およびパーデュ大学はいかなる問題や誤りに対して責任を負えないだけでなく、パーデュ大学はここで議論された研究やその成果物に対して、何も保証しません。

【訳註：著者の Hank Dietz 氏は、1999 年 9 月にケンタッキー大学に異動され、それにともない研究活動の中心も同大学に移りました。このドキュメントでも述べられている彼自身の並列処理の研究は、 KAOS グループで継続されています。その成果物として KLAT2 等が稼働しています。 KLAT2 は、 IEEE/ACM SC2000 にて Gordon Bell Award を受けています。パーデュ大学での成果及び最近の研究については、 The Aggregate で見ることができます】

次のページ前のページ目次へ