スケジューラアクティベーション続き。一番最初に抱いたモヤモヤ感というの
はカーネルはプロセッサをアドレス空間に分配するという概念だったのだ。時
分割ではなく空間分割。とはいえ..片手で数えれる程度のプロセッサ数であれ
ば最終的には空間分割を時分割にせざるを得ない。そうなると横取りのための
頻繁なアップコールによってさらに性能が悪化してしまう。この論文はもっと
大くのプロセッサを想定していた。
Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism Thomas E.Anderson, Brian N.Bershad, Edward D.Lazowska and Henry M.Levy University of Washington ACM Transactions on Computersystems, Vol.10, No.1, February 1992,p53-79. 5.3 アプリケーションの性能 我々のシステムがアプリケーションに寄与する性能を例証するため、同じ並列 プログラムを、Topazのカーネルスレッド、Topazのカーネルスレッドの上に構 築された元のFastThreads、スケジューラアクティベーションの上で走るように 改造されたFastThreadsを使って測定した。測定したアプリケーションは、 O(NlogN)解のN体問題[3]である。アルゴリズムは、空間のそれぞれの部分の重 心の木表現にし、木を辿ってそれぞれについての力を計算する。離れた質量の 集合による力はその集合の重心からの力で近似される。 プロセッサ速度と使用可能なメモリ量の相対比によって、このアプリケーショ ンは計算限界にもI/O限界にもなり得る。このアプリケーションのメモリ管理の 部分を、アプリケーションのデータのバッファキャッシュになるように改造し た。こうすることで、アプリケーションで使うメモリの量を制御することがで きる。問題を解くのに十分に小さいメモリサイズは、バッファキャッシュが Fireflyの物理メモリに合うように選ばれる。一層の単純化として、スレッドが そのキャッシュにミスしたら、カーネルの中で単純に50msecブロックすること とした。キャッシュミスは普通ディスク操作をするだろう。(この測定は定性的 にディスク操作を考慮した場合と同じになる; Fireflyの浮動小数点性能と物理 メモリ量は現在のシステムに較べて一桁悪いので、あくまで例証だけというこ とを意図している) 最初に、アプリケーションがカーネルサービスをほとんど使わない場合の説明 する。我々のシステムはTopazスレッドを使った場合に較べて、元の FastThreadsと同程度にずっと速い。図2のでは、他のアプリケーションはなく、 ほとんどI/Oがなく、十分なメモリがある状態での、プロセッサ数の増加に対す るアプリケーションの速度の向上をグラフにした。(速度の向上は、このアルゴ リズムを単一処理した(並列処理をせずに)実装に対する比較である) 1プロセッサでは3つのシステムとも単一処理実装より悪い。これは並行処理し た時のスレッドの作成と同期のオーバーヘッドのためである。このオーバーヘッ ドは他のユーザ層スレッドシステムよりも大きい。 プロセッサ数が増加するにつれて、Topazカーネルスレッドの性能は最初は良く なるものの、その後は伸びない。Topazにおいて、スレッドはきわどい領域のア プリケーションのロックの獲得/開放はカーネルを必要としないので、ロックに 対する競合はない。しかし、ビジーロックを獲得しようとする時には、スレッ ドはカーネル内でブロックし、そのロックが開放される時だけ再スケジュール される。このようにして、Topazのロックのオーバーヘッドは競合が起きるとと ても大きくなる。よい性能を出した、ユーザ層スレッドはどちらも、アプリケー ションとして十分な並行性を見せている。カーネルスレッドのオーバーヘッド が性能向上の妨害となっている。 カーネルスレッドを使った場合、そのきわどい領域がボトルネックにならない ように、あるいはロックが獲得できない時にカーネルに入る前にちょっとの間 ユーザ層でスピンする[12]ように再構成することでアプリケーションの性能を 向上するようにできたかもしれない。これらの最適化はユーザ層スレッドの上 でのアプリケーションでは重要ではない。 元のFastThreadsと我々のシステムとでは、4,5プロセッッサのあたりで性能が 異なる。このテスト中には他のアプリケーションは走行していないが、Topaz OSはいくつかのデーモンが周期的に起床し、ちょっとだけ走行し、また寝る。 我々のシステムでは明示的にプロセッサをアドレス空間に割当てるので、これ らのデーモンは、まったくアイドル中のプロセッサがない時にだけ横取りをす る。これは元々のTopazのスケジューラでは違う。そのスケジューラは元の FastThreadsの仮想プロセッサとして使われるカーネルスレッドを制御する。ア プリケーションがその機械の全てのプロセッサを使おうとした場合(この場合、 6プロセッサ)、両方のユーザ層スレッドシステムの横取りの数は同じである。 (元のFastThreadsにとってその横取りの影響は少ない。その所用時間は小さい からだ) 次に、アプリケーションがI/Oによってカーネルの介入を必要とする場合を見る。 我々のシステムは元のFirstThreads、Topazスレッドよりも良い性能である。図 3のグラフは使用可能メモリを変化させた場合にアプリケーションを6プロセッ サで実行した時の所用時間である。3つのシステムで、最初のうちはゆっくりと 性能が下がっていく。そしてアプリケーションのワーキングセットがメモリに 入らなくなると急激に悪くなる。しかしながら、元のFastThreadsの性能は他の 二つに較べてさらに急激に悪くなる。これはユーザ層スレッドがカーネル内で ブロックすると、その仮想プロセッサとしてのカーネルスレッドもブロックし、 そのためI/Oの間そのプロセッサをアプリケーションは使用できないからである。 我々のシステムとTopazスレッドの悪化率は同じである。これはI/Oの間に有効 にプロセッサを並行処理に利用できるからである。図2にあるように、それでも 我々のシステムでのアプリケーションの性能がTopazスレッドよりもいいのは、 ほとんどのスレッド操作がカーネルの介入なしに実行できるからである。 最後に、図3はアプリケーションによって引き起こされるカーネル事象による性 能への影響を示したが、並行処理が引き起こすシステムによるカーネル事象に 起因するものにも、我々のシステムは、他の二つ(元のFastThreadsとTopazスレッ ド)よりも良い性能である。これを試験するために、二つのN体問題のプログラ ムを6プロセッサのFirefly上で同時に実行し、その平均時間を測定した。表5に はそれぞれのスレッドシステムでの速度向上を一覧にした。3倍の速度向上が限 界である。 ---------------------------------------------------------------------- 表5. N体問題 並列処理=2, 6プロセッサ 全てのメモリが使える状態 Topaz Original New threads FastThreads FastThreads 1.29 1.26 2.45 ---------------------------------------------------------------------- 我々のシステムは並行処理環境でも良い性能ことを表5は示している。3プロセッ サで単一処理のプログラムを動かした時では5%以内の向上である。 この低下はバスの競合と、デーモンに周期的にプロセッサを明け渡す必要があ るためだと思う。対照的に、異なる理由で並行処理環境での性能は元の FastThreads、Topazスレッドともにもっと悪い。 元のFastThreadsをアプリケーションが使用した場合、OSは仮想プロセッサとし て使われるカーネルスレッドを時分割する。これによってロックを保持したス レッドがスケジューリングを外されている間、そのロックの開放を待っている スレッドの物理プロセッサはアイドル状態となってしまう。Topazスレッドのス レッドが我々のシステムより悪いのは、一般的なスレッド操作のコストが高い からである。さらに、Topazは明示的なプロセッサの割当てをしないので、ある アドレス空間は他のアドレス空間よりも、より大くのカーネルスレッドをスケ ジュールされるかもしれない。図2では、3つ以上のプロセッサがアプリケーショ ンに割当てられた時に、Topazスレッドは性能が伸びないことを示している。 Fireflyは概念を試作するにはとてもよい環境ではあるが、プロセッサの数が限 られているので、非常に並行度の高いアプリケーションや、並行実行環境での 並行プログラムの実行という実験には理想的ではない。このため、我々はスケ ジューラアクティベーションをMachとそのCThreadsに実装している。さらに Amber[6]というマルチプロセッサネットワーク用のプログラミングシステムを このFireflyの上に実装している。
