マルチプロセッサ向けソフトウェアパラダイムとは？

年末に会社の机を整理して、(席替えがきっかけだったのだけど)、読もうとおもってコピーしていた論文なんかを書類置きの下の方から発掘した。一度スタックにつまれてしまうと時々ゴミ集め(GC -- Garbage Collection)して整理しないと二度と発見されない。

半年ぶりにこんにちはの論文たちよ。その一つに"Ideas on improving Linux infrastructure for performance on multi-core platforms", Maxim Alt というのがある。

最初の会社に入社したのは20年以上前の話で、その頃わたしは、「ムーアの法則」などという言葉を知らなかったが、その会社は間違いなく「ムーアの法則」という事を正しく理解している会社であった。VAXというミニコンで一時代を築いた会社で、PDP-11という16ビットコンピュータのベストセラーマシンを開発したチームがVAXを開発していた。新人社員であるわたしはあこがれのエンジニア達の開発秘話に胸をときめかせたものである。

Godon BellだかBill Streckerかの論文にCPU memoryの需要は一年に0.7 bit増大する、従ってうんぬんかんぬんというお話があった。数百万円するワークステーションが何年かのうちに個人で経済的に利用できるようになる。

メモリコストがどんどん下るのならメモリを上手に利用するプログラミングパラダイムが絶対必要になる。その文脈でDECはVAX/VMSというアーキテクチャを設計した。VAX (Virtual Address eXtension)というアーキテクチャと VMS (Virtual Memory System)というOSは仮想記憶を徹底して意識した作りになっている。

DECにはVAXLというプログラミング言語のコミッティがあって共通言語インターフェースを定義していたがFORTRANの実装者もCOBOLの実装者もAdaの実装者も一つのコミュニティとして仮想記憶を意識したプログラミングパラダイムを共有していた。

プログラミング言語はソースコードを読みとり、字句解析、構文解析などをへて中間言語に翻訳され、最後に機械語になる。前方参照などを解決するために、ソースコードを複数回読む場合がある。通常ソースコードを読むプロセスをパスと呼ぶので複数回読むコンパイラをマルチパスコンパイラなどと呼ぶ。最もコストのかかる操作は物理的にファイルから読む作業なので、できればそれをさけたい。

VAXの言語コミュニティは論理的には複数回ソースコードを走査するのだが物理的には一度しか読まない実装をとった。一度読んだソースコードを仮想記憶上に展開し論理的なファイルを仮想記憶に持ち、それを複数回読むという実装をした。物理的な入出力にくらべ、仮想記憶へのアクセスは遥かに速いのでコンパイル速度は向上するという考えである。

仮想記憶の管理は言語処理系がするのではなくOSの仕事である。当時のVMSのチームにはトップノッチのエンジニアがごろごろいたので、仮想記憶のパフォーマンスチューニングは彼らにとっては、朝飯前の仕事であった。

仮想記憶の処理がうまくないとページングが発生し性能がでない。ページングは物理メモリにのりきらない仮想記憶をディスクへ退避復帰する処理なので物理的入出力が発生するため大変コストがかかる。いろいろなアルゴリズムを駆使してページングの発生を最小化するのがOSの仕事である。

いい実装であればページングはほとんど発生しないし、悪い実装であればページングが発生する。共有ライブラリのようなものは複数のプロセスで物理的なページを共有するので(物理メモリの需要が減る)、上手に実装するとページングを減少させる。VMSはデフォルトでそれを実装していたが、Unixでそれが一般化するよりはるか以前の頃の話である。

ハードウェアアーキテクチャ、OS、コンパイラ、ミドルウェア等々仮想記憶を前提に実装されていた。その結果、メモリがどんどん安くなってメモリを大量に装着できるようなると、ハードウェアを変更しなくても、ソフトウェアの実装を変更しなくても、メモリを追加するだけで文字通り性能が向上するという実装に収斂していったのである。

DEC社内のコミュニティはムーアの法則を仮想記憶の実装という形で理解していた。エンジニアリングコミュニティでそれが共有されていた。

Alphaの開発チームはVAX開発チームの後継で、ある意味DNAを受けついでいるのだが、当時の論文(90年ごろ)で、マイクロプロセッサのスケーラビリティを、クロックの向上で10倍、アーキテクチャの進歩で10倍、マルチプロセッサで10倍、10x10x10=1000倍の性能向上を達成するとかしないとか書いてあって、感心したのを覚えている。

第一世代のAlphaは150MHzで当時他社製プロセッサは20〜40MHzだったので、それでも十分高クロックであったが、それを10倍も高めるアーキテクチャ上の設計になっているというのに心底たまげた。今からふりかえってみれば10倍というのも控え目のゴールで20倍ないし30倍程度は向上した。

アーキテクチャの進歩というのはスーパースカラ、スーパーパイプライン、アウトオブオーダ実行、投機的実行等々様々なアイデアを実装することによって性能向上をはかるという事である。コンパイラの進歩もあいまってこれも10倍程度の性能向上はあったであろう。

最後のマルチプロセッサ化による性能向上というのは、別段とりたてておどろくような話ではないが、最初の二つがアプリケーションソフトウェアの変更をほとんどなしにシステムによってほぼ自動的に達成できる類のものに比べ、マルチプロセッサというのはアプリケーション側で積極的に対応しないと性能向上になかなか寄与しない。という事で一番地味で簡単に達成可能かと思われたマルチプロセッサでの性能向上というのがソフトウェア的には一番最後まで残ってしまったということである。

OSのマルチプロセッサ対応の歴史は古くからあるのだが、その上に載るRDBMS等のミドルウェア、さらに上のアプリケーションなどはじめからマルチプロセッサを意識した作りになっていないと、プロセッサの数を10倍増したからといっても性能が10倍向上するということはない。

Cのような低レベルの言語で書いているのであれば、それもしょうがないと思うが、スクリプト言語で書いたようなアプリケーションであれば言語処理系でよきにはからって欲しいとも思う。例えば構文で繰り返しを発見したらそれを自動的に並列化するくらいの事をやってくれてもばちはあたらない。Fortranのような数値計算処理系だとDOループを自動的にパイプライン化したり並列化したりして性能向上をシステムがおこなってくれたりする。

SQLの最適化エンジンも実行プランをかなり賢く選択するようになってきている。

で、話をムーアの法則に強引に戻すと、20年前であれば、それは仮想記憶をどう上手に使うかという問題に帰着したわけで、それと同様な問題を設定するとすると、ムーアの法則をソフトウェアパラダイムの問題として考えると、それはマルチコアなプロセッサをどう上手に使うかという問題に帰着する。

数年前にインテルがハイパースレッディング技術をうちだしたとき、何もしない(？)で20〜30%性能が向上するというふれこみであったが、残念ながらなかなかそう上手くはいかなかった。アーキテクチャ上の工夫(スーパスカラとか投機的実行のたぐい)というより、むしろマルチプロセッサによる性能向上というような技術に近かったため、アプリケーションの変更が必要であったからと言える。

32ビットアーキテクチャから64ビットアーキテクチャの移行はある程度機械的な変更でおこなえるがシングルプロセッサ向けのソフトウェアをマルチプロセッサ向けへ変更する事は容易ではない。

ロックをはじめとする同期のアルゴリズムの再発見が必要となる。

ということで今後ますますマルチプロセッサ技術が重要になるというブログ初エントリーである。

机を整理していたら、Wait-Free Synchronization, Maurice Herlihy, 1993というのも発見されたことを付記しておく。

Comments

[投稿： ひら]

>ということで今後ますますマルチプロセッサ技術が重要になるというブログ初エントリーである。

同感です(^-^)
コア数が数百個のレベルになると既存のパラダイムで扱えるのか？その辺が興味あります。
新しい要求により新しいパラダイムが生まれるのではないかと。

[投稿： hyoshiok]

ひらさん、コメントありがとうございます。

仰る通りですね。

大規模パラレルマシン向けアルゴリズムの研究が全然遅れているような気がするのですが、どうでしょう。