|
次のページ
前のページ
目次へ
2. SMP Linuxこのドキュメントでは、
SMP Linux
システムを並列処理に使う方法について、要点をかいつまんで見ていきます。
SMP Linux の最新の情報は、SMP Linux プロジェクトのメーリングリスト
で得られます。majordomo@vger.rutgers.edu に SMP Linux は本当に動作するのでしょうか? 1996 年 6 月に新品の(実はノー
ブランド ;-)100MHz 駆動の Pentium を 2 個搭載したシステムを購入しました。
パーツから組み上げたシステムで、プロセッサと Asus のマザーボード、256 K
のキャッシュ、32 MB の RAM、1.6 GB のディスク、6 倍速の CD-ROM、ビデオ
カードに Stealth 64、15 インチの Acer のモニターがついて、合計 1,800
ドルでした。プロセッサが 1 つのシステムと比べて数 100 ドル高くなりました。
SMP Linux を動かすのは難しいことではなく、単独プロセッサ用の「普通について
くる」Linux をインストールして、makefile にある 次にわからないのは、はたして SMP Linux でどの程度のレベルの高さ で共有メモリを使った並列プログラムをコーディングして実行できるかと いうことでしょう。 1996 年前半では、まだ十分とはいえませんでした。しかし状況は変わりました。 例えば、現在では極めて完成度が高い POSIX スレッドライブラリがあります。 本来の共有メモリ方式と比べてパフォーマンスは劣りますが、SMP Linux システムでは、もともとソケット通信を使ったワークステーション上で動く クラスタ用に開発した並列処理用のソフトウェアのほとんどを利用できます。 ソケット(セクション 3.3 を参照のこと)は、単独の SMP Linux 上で動作し、 クラスタをネットワーク上で組んだ複数の SMP マシンでも動作します。 しかし、ソケットは SMP にとっては必要ないオーバーヘッドがかなり多く あります。オーバーヘッドのかなりの部分はカーネルや割り込み制御にあり ます。これが問題をさらに悪化させています。というのも、通常 SMP Linux は、カーネル内で同時に動作できるプロセッサは 1 つだけで、割り込み コントローラとして設定できるプロセッサもたった 1 つだけなのです。 つまりブートしたプロセッサしか割り込みをかけられません。 それにもかかわらず、標準的な SMP の通信機器は、大部分のクラスタを組んだ ネットワークよりも優れています。クラスタ用に設計されたソフトウェアが、 クラスタ上で動くよりも SMP 上の方がうまく動作することが多いようです。 【訳註:Linux のカーネルが 2.4 になり SMP 対応が改良されました。 2.2 系列以前では、システムコールが呼び出されるとそれが動いているプロセッサ がカーネルを離すまでカーネル全体にロックをかけていました。 つまり他のプロセッサがカーネルを利用しようとしても(システムコールを発行 しても)、カーネルのロックがはずれるまで(現在動いているシステムコールの 処理が終わるまで)処理待ちになっていました。2.4 系列ではカーネル全体ではなく、 カーネル内部でプロセッサ間で共有している資源単位でのロックが可能になりました。 ただしすべてが資源単位でのロックに変更されたわけではなく、依然としてカーネル をロックする部分もあります。 割り込みについても、それぞれのプロセッサからかけることが可能になりました】 このセクションの残りの部分では、SMP のハードウェアについて論じ、Linux で 並列プログラムのプロセスがメモリを共有し合う基本的なしくみを見て行くこと にします。アトミックな処理や変数の保存、資源のロック、キャッシュ・ライン について 少し意見を述べて、最後に他の共有メモリ並列処理についての資料を いくつか紹介したいと思います。 2.1 SMP のハードウェアSMP システムはもう何年も動き続けていますが、つい最近まで基本的な機能の 実装がそれぞれのマシンで異なる傾向にあったため、オペレーティングシステム のサポートは移植性があるとは言えませんでした。 この状況が変わるきっかけになったのが、MPS と呼ばれる Intel の Multiprocessor Specification です。MPS 1.4 の仕様は、PDF ファイルで http://www.intel.com/design/pro/datashts/242016.htm から利用 できます。また MPS 1.1 についての概要が http://support.intel.com/oem_developer/ial/support/9300.HTM 【訳註:リンク切れ】にあります。ただ、intel の WWW サイトはよく構成を変える ので注意してください。 プロセッサを最大 4 つまで搭載する MPS 互換のシステムは、数多くの ベンダーが構築して います。しかし MPS は理論上もっと多数のプロセッサをサポートしています。 非 MPS で 非 IA-32 なシステムで SMP Linux がサポートしているものは、 Sun4m を載せたマルチプロセッサの SPARC マシンです。SMP Linux は Intel の MPS バージョン 1.1 もしくは 1.4 互換のマシンをサポートしており、16 個までの 486DX、Pentium、Pentium MMX、Pentium Pro、Pentium II をサポート しています。 サポートしていない IA-32 プロセッサには、Intel の 386 と Intel の 486SX/SLC です(SMP のしくみと浮動小数点演算装置をつなぐインタフェースがありません)。 AMD と Cyrix プロセッサ(SMP をサポートするチップが異なるので、この ドキュメントを書いている時点では利用できません)が上げられます。 【訳註:先に述べた KLAT2 は、AMD の Athlon を搭載していて、SWAR として intel の MMX に加えて、AMD のマルチメディア拡張命令である 3DNow! も利用しています】 大切なのは、MPS 互換のシステムのパフォーマンスが大きくばらつくことを 知っておくことです。皆さんの予想通り、プロセッサの速度はパフォーマンス の差に影響を与える要因の 1 つです。クロック速度が速ければ速いほど、より 高速なシステムになる傾向にありますし、Pentium Pro は Pentium よりも高速 です。しかし MPS 自体は共有メモリの実装がどのようであるかについて仕様 を決めているわけではなく、ただソフトウェアの点からどのように実装が機能 すべきなのかを決めているに過ぎません。つまりパフォーマンスとは、共有メモリ の実装がどのように SMP Linux やユーザのプログラムの特性と相互に連係して いるかの結果でもあります。 まず MPS に準拠したシステムそれぞれで見なければいけないのは、どのように システムが物理的な共有メモリにアクセスできるのかということです。 それぞれのプロセッサは独自の L2 キャッシュを持っているか?MPS Pentium の一部やすべての MPS Pentium Pro、Pentium II システムは、 独立した L2 キャッシュを持っています(Pentium Pro や Pentium II はモ ジュールに組み込まれています)。独立した L2 キャッシュは一般的に コンピュータのパフォーマンスを最大限に引き出すと見なされていますが、Linux ではそれほど単純ではありません。複雑にしている第 1 の原因は、現状の SMP Linux のスケジューラがプロセスそれぞれを同じプロセッサに割り当て続け ないようにしている点にあります。これはプロセッサ・アフィニティ と呼ばれている考え方です。 これはすぐにでも変更されるかもしれません。最近「プロセッサ・バインディ ング」というタイトルで、SMP Linux の開発コミュニティでこの考え方が 何度か議論されました。プロセッサ・アフィニティがないと、独立した L2 キャッシュが存在した場合無視できないオーバーヘッドが発生してしま います。それは、あるプロセスが最後に実行していたプロセッサではなく、 別のプロセッサでタイムスライスを割り当てられた場合に発生します。 【訳註:カーネル2.2系列では、特定の CPU に特定のプロセスを割り 当てることは標準ではできませんが、パッチとして PSET - Processor Sets for the Linux kernel( http://isunix.it.ilstu.edu/~thockin/pset/) が用意されています。 2.4 系列では、プロセスを同じプロセッサになるべく処理させるように スケジューリング方法が変更されています。またプロセッサ・バインディング は、割り込みについては実装されており、プロセスについては検討中です】 比較的安価なシステムの多くは、1 つの L2 キャッシュを 2 つの Pentium プロセッサで共有しています。困ったことにキャッシュの競合が発生して、複数 の独立した順次処理をするプログラムに対して深刻なパフォーマンスの低下を引き 起こします。逆に良い点は、並列プログラムの多くが実際に共有したキャッシュ の恩恵を受ける可能性があることです。というのは、両方のプロセッサが 共有メモリの同じラインにアクセスしようとする場合、キャッシュにデータを フェッチしなければならないのは 1 つのプロセッサだけで、バスの競合が避けられ ます。プロセッサ・アフィニティがなければ、共有の L2 キャッシュのデータ 不整合をより低く押えることもできます。つまり並列処理にとって、予想していた ほど、共有の L2 キャッシュに欠点があるとは断定できません。 私達が所有している 2 つの Pentium を搭載した 256 K のキャッシュを持つ システムを使用した経験からすると、パフォーマンスに非常にばらつきがあり、 その原因はカーネルが負う処理のレベルに依存しています。最悪で約 1.2 倍 の速度向上にしかなりません。しかし 2.1 倍まで高速化ができたことから、 計算中心の SPMD スタイルのコードはまさに「フェッチの共有」効果がでて いることになります。 バスの構成?最近の大部分のシステムでは、プロセッサに 1 つ以上の PCI バスが接続して いて、その PCI バスに 1 つ以上の ISA や EISA バスが「ブリッジ」しています。 これらのブリッジが遅延を引き起こし、さらに EISA と ISA は PCI に比べて帯域 も狭くなります(ISA が最も遅い)。そのためディスクドライブやビデオカード他の 高いパフォーマンスを必要とするデバイスは、普通 PCI バスインタフェース経由 で接続すべきです。 MPS システムでは、PCI バスが 1 つしかなくても計算が多くを占める並列プロ グラムを高速に実行できます。しかし入出力処理は、プロセッサが 1 つのもの より良いとは言えません…恐らくプロセッサによるバスの競合で若干 パフォーマンスが落ちてしまいます。つまり入出力の速度向上に注目するとすれ ば、複数の独立した PCI バスと入出力コントローラがある MPS システムを手に 入れる方が良いということになります(例えば複数の SCSI 接続)。ここで注意 しなければいけないのは、SMP Linux があなたが所有する部品をサポートして いるか、ということです。また最新の SMP Linux が基本的にカーネル上では 常に 1 つのプロセッサしか動いていないということも忘れないでください。 そういう訳で、入出力コントローラには入出力処理それぞれに必要となるカーネル の処理時間が最小のものを選ぶように心がけてください。本当に高性能を目指す ならば、システムコールを使わないで、ユーザ・プロセスから直接 raw デバイス を使って入出力することを考慮してもいいのではないでしょうか。これは思った ほど難しいことではありませんし、セキュリティレベルを下げることにもなり ません(セクション 3.3 で基本的なやり方を説明します)。 バスの速さとプロセッサのクロックの速さの関係がここ数年でいびつになって いることをぜひ知っておいてください。 現状ではシステムの大部分は同一の PCI のクロック速度を使用していますが、 高速なプロセッサのクロックと低速なバスのクロックの組合せは、まれなケース とは言えません。Pentium 133 は Pentium 150 より速いバスを 採用しており、様々なベンチマークで一見不思議な結果を出しているのが良い例 です。これらの影響は SMP システムではさらに大きくなります。より速いバス・ クロックがより重要なのです。 【訳註:Pentium 133 は 66 MHz の 2 倍速、Pentium 150 は 60 MHz の 2.5 倍速で駆動します】 メモリのインタリーブと DRAM の技術?本来、メモリをインタリーブすることは MPS とは何の関係もありませんが、 MPS システムではよく触れられる話です。というのも、これらのシステムは 往々にしてメモリの帯域幅をより必要とするからです。普通は、2 way もしくは 4 way をインタリーブして RAM を構成します。そのためブロック・アクセスは、 1 つのバンクだけではなく、複数のバンクを使用します。 これによって、より広い帯域幅でメモリにアクセスでき、とりわけキャッシュ のロードやストアに効果があります。 【訳註:インタリーブとは、メモリ上のデータ読み書きの高速化を はかるための方法の 1 つで、搭載されているメモリをグループ分けします。 このグループをバンクと呼び、このバンク単位に並列にアクセスする方式を とります。 2 way は 2 バンク、4 way は 4 バンクにメモリをグループに 分けて並列にアクセスします】 しかしこの効果については、状況が少々混沌としてきました。その理由は、 EDO DRAM と他の様々なメモリ関連技術が同じような種類の操作に改良 を加えてきているためです。DRAM 技術についてとてもよくまとめられた 資料が、 http://www.pcguide.com/ref/ram/tech.htm で見られます。 それでは、2 way でインタリーブしている EDO DRAM とインタリーブして いない SDRAM ではどちらがパフォーマンスが優れているでしょうか? この 質問はとてもいい質問なのですが、簡単には答えらえません。というのも、 インタリーブするのも、魅力ある DRAM 技術も、とても高価になりがちだから です。同じお金をかけて普通のメモリを購入すれば、より多くのメモリを 確保できるのは明らかです。一番遅い DRAM でも、ディスクベースの仮想 メモリより比べものにならないほど高速です…。 【訳註:SDRAM と EDO RAM の大きな違いは、SDRAM は PC のベース クロックと同期して動作するのに対して、EDO RAM はベースクロックとは非 同期に動作する点にあります。しかし SDRAM もはじめのアドレスにあるデータ にアクセスする時には EDO DRAM と同様に遅延(RAS、CASの)が発生します。次 世代メモリと言われる RDRAM もより広いメモリ帯域幅が実現できますが、DRAM を使用することにはかわりなく、やはり遅延が発生してしまいます。 つまり、現在までのメモリの高速化はバーストモードの高速化が中心であって、 DRAM 自体が抱えている遅延の問題を根本的に見直しているわけではありません】 2.2 共有メモリを使ったプログラミングをはじめるにあたってそろそろ並列処理を SMP で動かすことが、いかに素晴らしいかを理解できたと 思いますが…。どこからはじめたらいいでしょうか? まずは共有メモリ通信が 実際にどのように動くのか、少しばかり勉強してみましょう。 あるプロセッサが値をメモリにストアして、あるプロセッサがそれをロード する―こう言うと単純なことに思われるかもしれませんが、残念ながらそれほど 単純ではありません。例えば、プロセスとプロセッサの関係はきっちり決って いるわけではありません。しかし、プロセッサの個数以上にプロセスが動いて いないなら、プロセスとプロセッサという言葉を入れ換えてしまっても、 おおざっぱに言って同じことです。このセクションの残りの部分では、大きな 問題になると思われるキーポイントを概観して、ポイントを外したままになら ないようにしたいと思います。何を共有すべきかを決めるのに使われるモデルを 2 つと、アトミックな操作、変数の保存のしかた、ハードウェアのロック操作、 キャッシュ・ラインの効果、Linux におけるプロセスのスケジューリングを 扱います。 すべてを共有するのか、一部を共有するのか共有メモリを使うプログラミングには、根本的に異なる 2 つのモデルがあり ます。それはすべてを共有する場合と一部を共有する場合 です。この 2 つのモデルとも、プロセッサが共有メモリからもしくは共有 メモリへロードやストアをしてやりとりできます。違うところは、すべてを 共有する場合がデータ構造すべてを共有メモリに置くのに対して、一部を共有 する場合は、ユーザがはっきりとどのデータ構造が共有メモリを使用する可能性 があり、どのデータ構造が単一プロセッサのローカルなメモリを使用 するかを示す必要があります。 どちらの共有メモリモデルを使うべきでしょうか? たいていの場合は好みの 問題と言ってもいいと思います。すべてを共有するモデルを好む人々が多いの は、データ構造のどれが宣言されたその時に共有されるべきか、ということを 区別する必要がまったくないからです。ただ競合しそうなアクセスにロックを かけて、共有しているものが 1 つのプロセス(プロセッサ)からしか一時に アクセスしないようにします。繰り返しますが、これも上記のように単純なわけ ではありません。そこで、比較的安全である共有するものを一部にとどめる方法 を選ぶ人々が多数いるのです。 すべてを共有するすべてを共有する利点は、既にある順次実行プログラムがたやすく手に入ること、 そしてそのプログラムをすべてを共有することを前提にした並列プログラムに、 それほど手間をかけず修正していける点にあります。どのデータが他のプロセッサ によってアクセスされるかを最初から解決する必要はありません。 簡単に言うと、すべてを共有する上で大きな問題となるのは、あるプロセッサが 処理したことすべてが他のプロセッサに影響を与えてしまうかもしれない点 にあります。この問題が顕著になるケースは 2 つあります。
上記の類の問題は、一部を共有する方法をとった場合にはほとんど起こり ません。それは、はっきりと指定したデータ構造だけを共有するためです。 また、すべてを共有する方法が動作するのは、プロセッサすべてが全く同じ メモリ・イメージを実行している場合だけです。これはほとんど疑う余地が ないことです。すべてを共有して複数の異なるコード・イメージを扱うこと はできません(つまり、SPMD は利用できますが、MIMD はできません)。 すべてを共有する場合にプログラムがサポートする典型的なタイプが、スレッド・ライブラリです。 Threads は、本来「軽量(light-weight)」なプロセスとして、通常 の UNIX 上のプロセスとは違ったスケジュールで動作していました。ここで とても大切なのは、1 つのメモリ・マップを共有してアクセスする点にあります。 POSIX Pthreads のパッケージは、移植に対してたいへんな労力を注いできました。 ここで非常に疑問なのは、移植されたものが本当に SMP Linux 上のプログラム のスレッドとして並列に動作するのか、ということです(理想的には、ある プロセッサでそれぞれのスレッドが動作する)。POSIX API は、そこまでを 求めていませんし、 http://www.aa.net/~mtp/PCthreads.html 【訳註:リンク切れ】のようなバージョンは、スレッドを並列に実行することを まったく考慮していません。プログラムから実行されるスレッドはすべて、Linux の 1 つのプロセス内で動き続けます。 SMP Linux の並列処理を最初にサポートしたスレッド・ライブラリは、既に
過去のものになりつつある bb_threads ライブラリで、
ftp://caliban.physics.utoronto.ca/pub/linux/ にあります。これは
とても小規模なライブラリで Linux の 最近になって、 【訳註:POSIX スレッドは IEEE 1003.1 として標準化されています。 各種スレッドライブラリについては Multithreading Libraries、マルチスレッドのプログラミングについては マルチスレッドのプログラミングが役に立ちます】 一部を共有する実際のところ一部を共有するということは、「共有する必要があるものだけを 共有する」ということです。このアプローチは、一般的には MIMD(SPMD ではない) に合致していて、それぞれのプロセッサのメモリ・マップ上で同じ位置にある共有 するオブジェクトを扱う点に注意が必要となります。もっと大切なのは、一部を共有 することでパフォーマンスの予測と改善やコードのデバック等が簡単になることです。 ただ問題になるのは、
現状では、Linux のプロセスグループを独立したメモリ空間に置くのに非常に
似かよった手法が 2 つあります。共有するものすべては、そのメモリ空間上で
はほんのわずかなセグメントを使用するだけです。Linux システムを設定する
時に「System V IPC」をうっかり外してしまわなければ、 Linux は「System V
Shared Memory(共有メモリ)」というとても移植性が高いしくみを利用できる
ようになります。他の選択としてメモリのマッピング機能も利用でき、これは
いろいろな UNIX システム間でそれぞれ実装されています。それが アトミックな処理と処理の順序上記どちらのモデルを使うにしても、結果はそれほど違いません。要は並列 プログラムの中から、すべてのプロセッサがアクセスできる読み書き可能な メモリの一部へのポインタを得るわけです。これが意味するところは、共有 メモリ上のオブジェクトをアクセスする並列プログラムが、そのオブジェクト がローカルなメモリにあるかのごとく扱える、ということなのでしょうか? そうとも言えるのですが、ちょっと違います… アトミックな処理というのは、ある対象に対する操作を部分に分け たり、割り込みが入ったりすることなく、連続して処理をする考え方です。 残念ながら共有メモリのアクセスでは、共有メモリ上にあるデータに対する すべての操作がアトミックに行われるわけではありません。何か手を打たない 限り、単純なロードやストア操作のようなバス上での処理が 1 回で済む操作 (つまり、8、16、32 ビットにアラインされた操作。アラインされていなかったり、 64 ビットの操作は異なる)だけが、アトミックな処理になります。 さらに都合が悪いことに、GCC のような「賢い」コンパイラでは最適化が働い てしまい、あるプロセッサの処理が完了したことを他のプロセッサが検知する のに必要となるメモリ上の操作を取り除いてしまいがちです。 幸いなことには、これらの問題 2 つとも改善することができます。気になる アクセスの効率とキャッシュ・ラインの大きさの関係をそのままにして置くのです。 しかしこれらの問題点を論じる前に、それぞれのプロセッサがメモリを参照
する時には、前提としてコーディングした順番で参照するということをはっきり
しておくことは無駄ではありません。Pentium がそうですが、将来の Intel の
プロセッサがそうであるとは限らない、ということも忘れないでください。
そのようなわけで、気に止めておいて欲しいことがあります。それは将来の
プロセッサが、保留しているメモリへのアクセスを完了させる命令を通じて
共有メモリにアクセスする必要が出てくるかもしれない、ということです。
つまり、メモリへのアクセスに順番を付ける機能を提供するわけです。 変数の保存のしかたレジスタにある共有メモリのバッファされているオブジェクトの値を GCC が
最適化しないようにするには、共有メモリ上のすべての実体を
volatile int * volatile p; このコードでは、最初の プロセッサのすべてのレジスタが更新されたことを知らせる役目であるアセンブリ
言語のロックを使うと、GCC が適切にすべての変数をフラッシュして、
通常の変数に対して ロック
BTS, BTR, BTC mem, reg/imm XCHG reg, mem XCHG mem, reg ADD, OR, ADC, SBB, AND, SUB, XOR mem, reg/imm NOT, NEG, INC, DEC mem CMPXCHG, XADD しかしこれらの命令を全面的に採用することは、良い思い付きとはいえない
でしょう。例えば、
__asm__ __volatile__ ("xchgl %1,%0" :"=r" (reg), "=m" (obj) :"r" (reg), "m" (obj)); GCC のインラインのアセンブリ・コードで、ビット操作を使ってロックを かける例は、 bb_threads library にあります。 しかし、おぼえておいて欲しいことがあります。それはメモリ操作をアトミック に行うと、それなりにコストがかかるということです。ロックをかける操作は かなり大きなオーバーヘッドがかかり、通常の参照がローカルなキャッシュを 利用するのに比べ、他のプロセッサからのメモリ参照は遅延が生じてしまうこと になるでしょう。最適なパフォーマンスを得るには、できるだけロック操作を 使用しないことです。また、これら IA32 でのアトミックな命令は、当然ですが 他のシステムには移植できません。 この他にも解決方法はいろいろあります。通常の命令に対して、同期をいろいろ ととるための実装がいくつも用意されています。その中には 相互排他 (mutual exclusion。略称 mutex))があり、少なくとも 1 つのプロセッサ がいつでも共有しているオブジェクトを更新できることを保証しています。 たいていの OS のテキストでは、これらのテクニックの内のいくつかを論じて います。Abraham Silberschatz 氏 と Peter B. Galvin 氏の共著である、 Operating System Concepts、ISBN 0-201-50480-4 の第 4 版で非常に 優れた議論がなされています。 キャッシュ・ラインの大きさアトミックな操作に関して必須で、SMP のパフォーマンスに劇的な影響を あたえることがもう 1 つあります。それはキャッシュ・ラインの大きさです。 MPS 規格ではキャッシュが使われていてもいなくても、同期するための参照が 必要とされています。しかし 1 つのプロセッサがメモリのあるラインに書き 込みを行うと、以前書き込まれたライン上にあるキャッシュしてあるものは、 すべてを無効にするか更新する必要があります。2 つ以上のプロセッサどれもが データを同じラインの違う部分に書くとすると、キャッシュやバスに多量のやり 取りが発生してしまうかもしれません。これは事実上キャッシュ・ラインから 受渡しが起こることを意味しています。この問題は、偽共有(false sharing) と言われています。解決するのはいたって単純で、並列にアクセスする 場合は、それぞれのプロセスに対して、データをできるだけ異なるキャッシュ・ ラインから取ってくるようにデータを構成することです。 偽共有は、CPU が共通して使用する L2 キャッシュを持っているシステムには
関係ない問題と思われるかもしれませんが、独立して存在する L1 キャッシュ
を忘れてはいけません。キャッシュの構成や独立したレベルの数は両者とも
変動するもので、Pentium の L1 のキャッシュ・ラインの大きさは 32 バイトで
外部キャッシュ・ラインの典型的な大きさは 256 バイト程度です。仮に 2 つの
要素のアドレス(物理、仮想どちらでも)が a と b として、
プロセッサ毎の最大のキャッシュ・ラインの大きさが c としてそれが
2 の累乗の大きさとします。厳密に言うと、もし Linux のスケジューラの問題点並列処理で共有メモリを使用する際には、あらゆる部分で OS のオーバー ヘッドを避けなければいけませんが、OS のオーバーヘッドは通信それ自体 以外のところから発生する可能性があります。既にこれまでに述べてきました が、プロセスの数はマシンに付けてあるプロセッサ数以下にするように 構成すべきです。でもどうやって動かすプロセス数を正確に決められるので しょうか? 最高のパフォーマンスを得るには、並列プログラムで動かすプロセス
数は、そのプログラムで起動するプロセスが同時に異なるプロセッサで
動かせると思われる数と同じにすべきです。例えば、4 つのプロセッサ
を持つ SMP システムでは、通常 1 つのプロセッサは何か別の目的(例えば
WWW サーバ)に使われているとすると、3 つのプロセッサだけで並列プログ
ラムを動かすことになるはずです。
おおまかにどのくらいのプロセスがシステムでアクティブなのかは、
これとはまた別の方法があり、並列プログラムで使っているプロセスの実行
優先順位を引き上げることが可能です。例えば、 SMP システムを並列処理マシンをただ一人で扱うユーザでないなら、2 つ以上 の並列プログラムを同時に実行しようとすると、プログラム間で衝突が起こる 恐れがあります。普通これを解決する方法は、ギャングスケジューリング (gang scheduling)をとります。すなわち、スケジューリングの優先度を 操作して、いつでもただ 1 つの並列プログラムに関するプロセスだけが動いて いるようにします。しかし思い出してみてください。並行処理を行えば行うほど 結果を得られにくくなり、スケジューラにオーバーヘッドが加わります。つまり 例えば、4 つのプロセッサを持つマシンが、強制スケジュールを使って 2 つの プログラムをそれぞれ 4 つのプロセスで動かすよりも、2 つのプログラムを それぞれ 2 つのプロセスで動かす方が効率良いのは確かです。 さらにもう 1 つこの問題をややこしくしている事があります。あるマシンで プログラムを開発していて、そのマシンは終日とても忙しく動いているが、 夜間は並列処理に丸々使えるとします。プロセスすべてを立ち上げて正しく動く ようにコードを書いて、それをテストしなければいけませんが、昼間のテストは 遅いことを思い知らされると思います。実のところとても遅くなり ます。もし現在動いていない(他のプロセッサ上の)他のプロセスが変更した共有 メモリ上の値をビジーウエイトしているプロセスがあるならば。同様 の問題は、プロセッサが 1 つしかないシステムでコードを開発したりテストし たりする時にも起こります。 解決方法は、コードに呼び出しを組み込むことです。どんな場合でも、他の
プロセスからの動きをループを使って待つようにします。そうすると Linux
は、他のプロセスが動く機会を与えることができます。私は C のマクロを
使って 2.3 bb_threadsbb_threads (「Bare Bones」(必要最低限の) threads)ライブラリは、
ftp://caliban.physics.utoronto.ca/pub/linux/ にある非常に
簡素なライブラリです。Linux の bb_threads ライブラリを使った基本的なプログラムの構築方法は、 下記の通りです。
下記の C プログラムはセクション 1.3 で論じたアルゴリズムを元に、2 つの bb_threads を使って円周率の近似値を求めています。
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/wait.h> #include "bb_threads.h" volatile double pi = 0.0; volatile int intervals; volatile int pids[2]; /* Unix PIDs of threads */ void do_pi(void *data, size_t len) { register double width, localsum; register int i; register int iproc = (getpid() != pids[0]); /* set width */ width = 1.0 / intervals; /* do the local computations */ localsum = 0; for (i=iproc; i<intervals; i+=2) { register double x = (i + 0.5) * width; localsum += 4.0 / (1.0 + x * x); } localsum *= width; /* get permission, update pi, and unlock */ bb_threads_lock(0); pi += localsum; bb_threads_unlock(0); } int main(int argc, char **argv) { /* get the number of intervals */ intervals = atoi(argv[1]); /* set stack size and create lock... */ bb_threads_stacksize(65536); bb_threads_mutexcreate(0); /* make two threads... */ pids[0] = bb_threads_newthread(do_pi, NULL); pids[1] = bb_threads_newthread(do_pi, NULL); /* cleanup after two threads (really a barrier sync) */ bb_threads_cleanup(wait(NULL)); bb_threads_cleanup(wait(NULL)); /* print the result */ printf("Estimation of pi is %f\n", pi); /* check-out */ exit(0); } 2.4 LinuxThreadsLinuxThreads(
http://pauillac.inria.fr/~xleroy/linuxthreads/) は、POSIX 1003.1c
のスレッド標準規格に基づいて「すべてを共有する」ことを申し分なくしっかり
と実装しています。他の POSIX 準拠のスレッドの移植と違い、LinuxThreads は
カーネルのスレッド機能( LinuxThreads ライブラリを使った基本的なプログラムの構築のしかたは、 下記の通りです。
次にあげるのは、円周率の計算を LinuxThreads を使って並列に行う例です。 セクション 1.3 で使ったアルゴリズムが使用されていて、bb_threads と同様に 2 つのスレッドを並列に実行します。
#include <stdio.h> #include <stdlib.h> #include "pthread.h" volatile double pi = 0.0; /* Approximation to pi (shared) */ pthread_mutex_t pi_lock; /* Lock for above */ volatile double intervals; /* How many intervals? */ void * process(void *arg) { register double width, localsum; register int i; register int iproc = (*((char *) arg) - '0'); /* Set width */ width = 1.0 / intervals; /* Do the local computations */ localsum = 0; for (i=iproc; i<intervals; i+=2) { register double x = (i + 0.5) * width; localsum += 4.0 / (1.0 + x * x); } localsum *= width; /* Lock pi for update, update it, and unlock */ pthread_mutex_lock(&pi_lock); pi += localsum; pthread_mutex_unlock(&pi_lock); return(NULL); } int main(int argc, char **argv) { pthread_t thread0, thread1; void * retval; /* Get the number of intervals */ intervals = atoi(argv[1]); /* Initialize the lock on pi */ pthread_mutex_init(&pi_lock, NULL); /* Make the two threads */ if (pthread_create(&thread0, NULL, process, "0") || pthread_create(&thread1, NULL, process, "1")) { fprintf(stderr, "%s: cannot make thread\n", argv[0]); exit(1); } /* Join (collapse) the two threads */ if (pthread_join(thread0, &retval) || pthread_join(thread1, &retval)) { fprintf(stderr, "%s: thread join failed\n", argv[0]); exit(1); } /* Print the result */ printf("Estimation of pi is %f\n", pi); /* Check-out */ exit(0); } 2.5 System V の共有メモリSystem V の IPC(プロセス間通信(Inter-Process Communication))は、 システムコールを数多く提供してます。メッセージ・キューやセマフォ、 共有メモリといったしくみです。もちろん本来このしくみは、複数の プロセスをプロセッサが 1 つのシステムで動かすことを目的としていました。 しかし、SMP Linux で複数のプロセス間での通信にも使えるはずです。たとえ どんなプロセッサであっても。 これらのシステムコールの使い方の説明に入る前に、System V の IPC に含まれて いるセマフォやメッセージ通信のようなシステムコールを使用すべきではないこと を理解しておいてください。どうしてでしょうか? SMP Linux ではこれらの機能は 概して処理が遅く、順次実行されるからです。説明はこれで十分ですね。 共有メモリのセグメントに一様にアクセスするために、プロセスのグループを作成 する基本的な手続きは次の通りです。
このようにいくつかのシステムコールが設定の際に必要となりますが、一度 共有メモリのセグメントが確保されれば、どのプロセッサがメモリ上の値を変え ても自動的にすべてのプロセッサから見ることができます。最も大切なことは、 システムコールのオーバーヘッドなしに操作ができることです。 System V の共有メモリのセグメントを使った C のプログラム例です。これ は円周率を計算するもので、セクション 1.3 で使ったのと同じアルゴリズム を利用しています。
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <sys/ipc.h> #include <sys/shm.h> volatile struct shared { double pi; int lock; } *shared; inline extern int xchg(register int reg, volatile int * volatile obj) { /* Atomic exchange instruction */ __asm__ __volatile__ ("xchgl %1,%0" :"=r" (reg), "=m" (*obj) :"r" (reg), "m" (*obj)); return(reg); } main(int argc, char **argv) { register double width, localsum; register int intervals, i; register int shmid; register int iproc = 0;; /* Allocate System V shared memory */ shmid = shmget(IPC_PRIVATE, sizeof(struct shared), (IPC_CREAT | 0600)); shared = ((volatile struct shared *) shmat(shmid, 0, 0)); shmctl(shmid, IPC_RMID, 0); /* Initialize... */ shared->pi = 0.0; shared->lock = 0; /* Fork a child */ if (!fork()) ++iproc; /* get the number of intervals */ intervals = atoi(argv[1]); width = 1.0 / intervals; /* do the local computations */ localsum = 0; for (i=iproc; i<intervals; i+=2) { register double x = (i + 0.5) * width; localsum += 4.0 / (1.0 + x * x); } localsum *= width; /* Atomic spin lock, add, unlock... */ while (xchg((iproc + 1), &(shared->lock))) ; shared->pi += localsum; shared->lock = 0; /* Terminate child (barrier sync) */ if (iproc == 0) { wait(NULL); printf("Estimation of pi is %f\n", shared->pi); } /* Check out */ return(0); } この例では、IA32 のアトミックな交換(exchange)命令を使ってロックを実現 しています。 パフォーマンスと移植性をさらに良くするには、バスをロックする命令を回避 するような同期のしくみに置き換えてください(セクション 2.2 で論じたように)。 コードをデバッグする場合は、現在使われている System V の IPC 機能の状態
をレポートする 2.6 メモリマップ・システムコールシステムコールはファイル入出力をともなうと重くなります。実際に、ユーザ
レベルでのバッファを介したファイル入出力ライブラリ( 本質的に Linux の
shmptr = mmap(0, /* system assigns address */ b, /* size of shared memory segment */ (PROT_READ | PROT_WRITE), /* access rights, can be rwx */ (MAP_ANON | MAP_SHARED), /* anonymous, shared */ 0, /* file descriptor (not used) */ 0); /* file offset (not used) */
munmap(shmptr, b); 私見ですが、System V の共有メモリのかわりに 次のページ 前のページ 目次へ |
[ |