Monday, October 3, 2016 5:00AM to 11:00AM (UTC) Schedouled down time to change site domain

マルチプロセッサとスケジューラ(その1)

マルチプロセッサ、スケジューラ、Hyperthreading、NUMA... 今後のマイクロプロセッサ技術の進化に伴って、2.6以降のカーネルが新たにサポートしていくべき、密接に絡み合うトピックスについて、どのあたりから取り上げようかと考えてしまう。

マルチプロセッサ・サポートについては、カーネル2.0からこれまでの活動で、性能向上と安定性を手に入れてきているし、カーネル2.6ではNUMAもサポートされている。しかしマルチプロセッサといってもアーキテクチャは様々であり、従来までのカーネルがサポートしてきた主流のSMPとは違う技術が、今後は一般的になるかも知れない。「ムーアの法則」は今後20年ぐらいは有効らしいが、その間順調に数を増やし続けるトランジスタがどのように使われるのかまでは、ムーア氏も予測していない。

新しいアーキテクチャの登場

例えば最近では比較的安価になってきたIntel Pentium4プロセッサで採用されているHyperthreading Techmologyや、IBMのサーバ用最新プロセッサであるPOWER5は、ハードウェア・アーキテクチャ的には従来のSMPとは異なる。そのためにカーネル2.6でもまだ、完全に対応できていないという面がある。これらのアーキテクチャがそのまま将来の主流になるかどうかはわからないが、2.6以降のカーネルでは今後登場する様々の新しいアーキテクチャのマルチプロセッサに対応して、それらの性能を最大限に引き出さなくてはならないという難題が待ち構えているのは確かである。

本題に入る前に少しだけ、プロセッサ技術に関係する用語の確認をする。

CPUのアーキテクチャによる分類

- UMA (Uniform Memory Access)

単一メモリを共有する事で制御する構造
従来からの同じCPUを複数個搭載した、SMP(Symmetrical Multi Processor)と呼ばれるものや、単一チップに2つのCPUコアを搭載したIBM Power4等が相当する。

- NUMA (Non-Uniform Memory Access)

共有するメモリに異なるレイテンシ(アクセス速度)の階層があるモデル
UMAの単位をノードと呼び、複数のUMAを制御用メモリで結合する構成が多い。今後は特に、NUMAの中でもハードウェアでキャッシュの一致制御を行なうccNUMA(Cache Coherent NUMA)が主流になるとの見方もある。「NUMA:理論と実践」に詳しい説明がある。

- NORMA (NO Remote Memory Access)

共有メモリを持たずに、メッセージ交換で処理を行なう構造
Shared Nothing方式、Shared Disk方式といった分類があり、一般的にはCluster接続や、Gridコンピュータが含まれる。

Hyperthreading(HT)とSMT

1つのCPUがDual CPUに見えるというインテルの技術は、HT(Hyperthreading)という用語がインテルのトレードマークであるために、コンピュータ・サイエンスの分野では、SMT(Simultaneous Multithreading TechnologyまたはSimultaneous Multi-Threading)と呼ばれる。すべてのプロセッサ・リソースを2重に持つ真のSMPとは異なり、内部の実行ユニットが1セット分しか無いために、いくつかの制約がある。Linuxではカーネル2.4.17で初めてPentium4 XeonのHyperthreadingに対応した。

Spinlock

マルチプロセッサ環境において、クリティカルセクションを複数CPUが同時実行しないためのソフトウェア的な仕組みである。一種のセマフォだが、実装はカーネル内で特定の変数値を無限ループ(Spin)しながら参照するマクロとなっているため、セマフォ等の他の同期方式を使うよりも短い命令数の実行で排他制御ができるとされている。古典的な手法であるがカーネル2.4では、カーネルでのspinlock実装によって、SMPでのパフォーマンスが改善した。「相手方がクリティカルセクションから出るまで無限ループで待つ」というこの手法は、当然Hyperthreadingでは具合が悪いので工夫が必要となる。詳しくは別の機会に紹介したい。

IBM Power5

最新のIBMのサーバ用プロセッサ。AIXのほかLinuxも移植されている。IBM Power5はCPUのオンダイにSMTによって論理的に2個のプロセッサに見えるCPUコアを2個実装して、見かけ上は1チップで4CPU分として振舞うことができる。このチップを複数個結合するNUMA的構成も可能で、Macintosh(PowerMac)で採用されているPowerPC Gシリーズの将来の姿ではないかと噂されている。

Hyperthreading対応スケジューラの状況

前置きが長くなってしまった。Hyperthreadingとスケジューラに関する話題として、少し古いが2003年11月23日のLKML(Linux Kernel Mailing List)でのNick Pigginのスケジューラの提案から取り上げる。彼は、Nick's scheduler policyという名前で、以前からしばしば手を入れたスケジューラを発表していた。

Nick Pigginは次のように提案した。

我々はまだHTに対応したスケジューラを持っていないというのは、不運である。なぜなら、このような奇妙な物だけが、近い将来より一般的になるように見えるからである。
私は、一般化されたスケジューリング・クラスを実装するために、私の最近のNUMA/SMPスケジューリング成果の上にパッチを作った。この修正は、アーキテクチャがはるかにうまい方法でスケジューリング・ポリシーをコントロールすることができる。Hyperthreading対応は今後問題とされるべきではないし、階層的(NUMA)ノードも同様になるに違いない。
私は、アーキテクチャ固有のコードがどのように扱われると推測されるか正確に分からないので、いくつかの例を見なければならないだろう。基本的には、アーキテクチャは自分専用のスケジューリング「クラス」を構築することができる。
私は、何も与えられない場合に、クラスを構築するデフォルト機能を提供している。機能的には以前の標準ローカル / リモートでの振る舞いと同様になるように、それを構築している。
まだそれほど多くのテストをしていないので、コメントを求めている段階である。これらのクラスは皆にとって十分だろうか?
クラスはinclude/linux/sched.hの中のstruct sched_classである。デフォルト・クラスはカーネル/sched.c中のarch_init_sched_classesによって構成されている。
問題のパッチは次のサイトの次の場所にある
http://www.kerneltrap.org/~npiggin/w23/
http://www.kerneltrap.org/~npiggin/w23/broken-out/sched-domain.patch

Ingo Molnarは尋ねた、「ううむ、私のHTスケジューラ・パッチを見たのだろうか、特に最近の2.6のスケジューラの上に載せた、Fedora Core 1のHTスケジューラを。かなりうまく行っているのだが。」

Ingo Molnarは、カーネル2.6の性能向上に大きく寄与したと言われる、O(1)スケジューラを開発し、メンテナンスしているカーネル・メンテナである。2.6に新しく導入された、Native Posix Threading Library (NPTL)の開発にもにも貢献している。

Nickは返答した。「それは見ていない。あなたの成果と、またそれが良さそうなことを知り、私は申し訳なく思う。私はそれが採用されることに反対ではないし、Linusも賛成してくれると思う。とにかく私の行なった変更は、自由にあなたにあげることにする。私はそのようなものがまだ、Linusのツリーには無いという事を言いたかっただけである。」

Ingoは答えた。「Linusのツリーに無かったのは、私がそれを書いた時、既に機能変更がフリーズされていたので、変更をでしゃばらなかったからである。また私は、スケジューラのメンテナなので、あるレベルでは自分がわきまえる必要があると感じたからだ。」

Nick Pigginはbill davidsen の質問に答えて補足した。「私は、SMT、NUMA、CMPがLinuxカーネルにサポートされたアーキテクチャとしてはやや新しいと推測している。うまく動作するNUMAは、しばらくの間存在していたが、スケジューラは明らかにOpteronのような変則的で新しいNUMAのためには、それほどうまく動作しない。」

Nick Pigginはその後もさらに、彼のスケジューラをメンテナンスしているので、今後も登場することになる。そしてこの続きは、次回ということにさせて頂く。

(4月20日、用語と言い回しを一部修正)