perfbook ６章の訳
６章 分割と同期の設計
この章は、コモディティシステムでますます見られるようになってきた複数 CPU を、活用できるソフトウエアをどのように設計したらいいかを説明します。そのために、いくつかのイディオム、あるいは、「デザインパターン」を紹介します。それらは、あなたが性能、スケーラビリティ、そして応答時間をバランスさせる助けになるはずです。以前の章で述べたように、あなたが並列ソフトウエアを作成するときに行う最も重要な決断は、どのように分割を行うかです。正しく分割された問題は、単純で、スケーラブルで、そして高性能のソリューションに導きます。一方、誤って分割された問題は、遅くて複雑なソリューションになります。この章は、あなたがご自分のコードで分割を設計するのを助けます。「設計」という語はとても重要です。あなたはまず、分割をして、そして次にコーディングするべきです。この順を逆にすると、しばしば低い性能とスケーラビリティになり、フラストレーションも大きくなります。
さて、そのために、６．１節は分割の演習問題をします。６．２節は分割可能性についての設計指針を振り返り、６．３節は適切な同期粒度を選ぶことを議論します。６．４節は重要な、並列高速パスの概要を示します。それは、一般的な場合には速度とスケーラビリティを提供し、普通でない場合にはより単純であまりスケーラブルでないフォールバックの「低速パス」を提供します。最後に、６．５節は分割の先にあるものを簡単に考えます。
６．１ 分割の演習問題
この節は、分割の価値を示すために、２つの演習問題（古典的な食事をする哲学者問題と、双方向キュー）を使います
６．１．１ 食事をする哲学者問題
図６．１は古典的な食事をする哲学者問題の絵です。この問題には５人の哲学者がいて、考えることと、食べるために２つのフォークを必要とする「とても難しい種類のスパゲッティ」を食べること以外は何もしません。哲学者は、自分のすぐ右あるいは左のフォークしか使うことが許されません。そして、哲学者がフォークを取り上げたら、満腹するまで、それを置きません。
脚注
２つのフォークを必要とする食べ物を想像するのが難しい読者は、その代わりにお箸だと思っても良いです。
目的は、全く文字通り、飢餓を防ぐアルゴリズムを作ることです。一つの飢餓シナリオは、すべての哲学者が同時に自分の左側のフォークを取ることです。食べるまで、誰もフォークを置くことはなく、少なくても一人が食べ終わらない限り、誰も２つ目のフォークを取れないので、皆、飢えます。少なくても一人の哲学者が食べることができるだけでは不十分なことに注意下さい。図６．２にあるように、哲学者の何人かが飢えるのも防げなくてはいけません。
Dijkstra の解決策は、グローバルなセマフォを使いました。それは、通信遅延が無視できるという前提のもとではうまくはたらきました。しかしその前提は、１９８０年代終わりあるいは１９９０年代初めには無効となりました。
脚注
２０１２年の視点から Dijkstra を非難するのは実に簡単です。その頃からもう４０年以上もたっています。それでもあなたが Dijkstra を非難したいとお考えなら、何かを出版して、４０年待って、あなたの言葉がどのように時の検証に耐えたかを見られることをおすすめします。
なので、最近の解決策は、図６．３のようにフォークに番号をつけます。それぞれの哲学者は、彼あるいは彼女のお皿の隣の小さい番号のフォークをまず取り、次に大きい番号のフォークを取ります。図の一番上の位置に座っている哲学者はまず、左のフォークを取り、次に右のフォークを取ります。他の哲学者は、そうでなく、先に自分の右側のフォークを取ります。哲学者の二人が最初にフォーク１を取ろうとして、片方だけが成功するため、４人の哲学者に対して５つのフォークがあります。これら４人のうち、少なくても一人は２つのフォークを得られる保証があるので、食べることに進むことができます。
資源を番号付けて、数字の順に取るというこの一般的テクニックはデッドロック防止テクニックとして大いに使われています。しかし、皆が空腹なのに、一度に一人の哲学者だけが食べていることになるイベントのシーケンスを想像するのは容易です。
1. P2 がフォーク 1 を取り、 P1 は取れなくなります。
2. P3 がフォーク 2 を取ります。
3. P4 がフォーク 3 を取ります。
4. P5 がフォーク 4 を取ります。
5. P5 がフォーク 5 を取り、食べます。
6. P5 はフォーク 4 と 5 を置きます。
7. P4 がフォーク 4 を取り、食べます。
要するに、このアルゴリズムは、５人の哲学者全てが空腹なのに、一度に一人の哲学者だけが食べる結果になることがあります。２人の哲学者が同時に食べるために十分なフォークがあってもです。
この先を読む前に、食事をする哲学者問題を分割する方法を考えてください。
図６．４は一つのアプローチです。分割テクニックをより良く示すために、５人でなくて４人の哲学者がいます。ここで、上と、右の哲学者はフォークの対を共用し、下と左の哲学者は別のフォークの対を共用します。もし全ての哲学者が同時に空腹でも、少なくても２人が常に同時に食べることができます。さらに、図が示すように、フォークはまとめてあるので、対は同時に取り上げ、取り下げられ、確保と解放アルゴリズムを簡単にします。
クイッククイズ６．１
食事をする哲学者問題に、これより良い解法がありますか？
これは、「水平並列性」あるいは「データ並列性」の例です。哲学者の対に、依存性がないので、そういう名前です。水平並列のデータ処理システムでは、あるデータのアイテムは、複製されたソフトウェアコンポーネントのセットのうち、ただ一つによって処理されます。
クイッククイズ６．２
この「水平並列性」は、なんで、「水平」と呼ばれるのですか？
６．１．２ 双方向キュー
双方向キューとは、要素のリストを持つデータ構造で、どちらの終端からも要素を挿入、削除できるものです。双方向キューで、両方の終端への同時操作を許すロックベースの実装は難しいと言われてきました。この節は、いかに分割設計戦略が、十分に単純な実装を可能とするかを、３つの一般的なアプローチを以下の節で示します。
６．１．２．１ 左側と右側のロック
一つの、明らかに直裁的なアプローチは、右と左のロックを持つ二重連結リストを使うものです。左終端のエンキューとデキュー操作には左のロックを使い、右終端には右のロックを使います。これを、図６．５に示します。しかし、このアプローチの問題は、リストに４より少ない要素があるときには、二つのロックの領域がオーバラップしてしまうことです。このオーバラップは、ある要素を削除することは、その要素だけでなく、その右と左のお隣に影響するという事実に由来します。図は、この領域を色で示しました。青い、右下がり斜め縞が、左のロックの領域で、赤い、右上がりの縞が右のロックの領域です。そして紫（縞なし）が、オーバラップする領域です。このように働くアルゴリズムを作成するのは可能ですが、それが、少なくても５つの特別ケースを持つという事実は、大きな赤い旗を掲げるべきです。特に、リストの反対側の同時実行するアクティビティが、キューをある特別ケースから別のケースにいつでもシフトできるというのは特に危険です。他の設計を考えるのがずっと良いでしょう。
６．１．２．２ 複合双方向キュー
オーバラップしないロック領域を強制する一つの方法を図６．６に示します。二つの双方向キューが並んで働いています。それぞれは自身のロックで守られます。これは、要素は時には、ある双方向キューからもう一つのに、送られないといけないことを意味します。その場合、両方のロックを取る必要があります。デッドロックを防ぐには、単純なロック階層を使えます。例えば、右のロックを取る前に必ず左のロックを取るなど。これは、双方向キューに二つのロックを使うことに比べてずっと単純です。なぜならば、左側のキューに左エンキューするのは無条件にできます。右も同じです。主な複雑さは、空のキューからデキューする時に起きます。その場合、以下のようにする必要があります。
１ 右のロックを持っていれば放して、左のロックを取ります。
２ 右のロックを取ります。
３ 二つのキューの間で要素を再バランスします。
４ 目的の要素があれば、除きます。
５ 両方のロックを放します。
訳注。私は誤解していましたが、要素は、図６．６の DEQR の箱の右に、右エンキューされて伸びます。左も同じです。DEQL と DEQR の箱の間にはいかなる時も何もつながりません。
クイッククイズ６．３
この複合双方向キューの実装において、ロックを放して、再び取る間にキューが空でなくなったらどうしたらいいでしょう？
結果となるコード (locktdeq.c) はとても直裁的です。再バランス操作は、ある要素を二つのキューの間で行ったり来たりさせることがあります。これは時間の無駄で、最適な性能を得るためには、ワークロードに依存したヒューリスティクスが必要かもしれません。場合によってはこれが最適なアプローチかもしれませんが、より決定論的なアルゴリズムを試すのも面白いでしょう。
６．１．２．３ ハッシュされた双方向キュー
データ構造を決定論的に分割する最も単純で最も効果的な方法の一つは、ハッシュすることです。双方向キューの要素にリスト中のその要素の位置を元にするシーケンス番号を与えることで、それを自明なやり方でハッシュすることができます。空のキューに左エンキューされた最初の要素はゼロで、空のキューに右エンキューされた最初の要素は１です。空のキューに左エンキューされる要素列は、減少する番号 (-1, -2, -3, ...) を割り当てられ、空のキューに右エンキューされる要素列は増加する番号 (2, 3, 4, ...) を割り当てられます。鍵となる点は、ある要素の番号を実際に表現する必要はないことです。この数字は、キューの中の位置でわかりますから。
このアプローチでは、左側のインデックスを守るために一つのロックをアサインし、右側のインデックスを守るために一つ、そして、それぞれのハッシュチェーンごとに一つのロックをアサインします。図６．７は、四つのハッシュチェーンの場合の、結果となるデータ構造を示します。ロック領域はオーバラップしないことに注意下さい。そして、デッドロックは、チェーンロックの前にインデックスロックを取ることと、同じ型の(インデックスあるいはチェーン)ロックを一度に一つより多くは決して取らないことで避けられています。
それぞれのハッシュチェーン自身は、双方向キューで、この例では、それぞれは４つごとの要素を持ちます。図６．８の一番上の部分は、一つの要素（“R1”）が右エンキューされた後の状態を示します。右側のインデックスは加算されて、ハッシュチェーン２を指します。同じ図の真ん中の部分は、さらに３つの要素が右エンキューされた後の状態です。見てお分かりのように、インデックスは初期状態に戻っています（図６．７を参照）。しかし、各ハッシュチェーンは空ではありません。この図の下の部分は、さらに３つの要素が左エンキューされ、一つの要素が右エンキューされた後の状態です。
図６．８の最後の状態において、左デキュー操作は、要素“L-2”を返し、左側のインデックスがハッシュチェーン２を指すようにするはずです。そしてハッシュチェーン２は、単一の要素 (“R2”) だけを持つようになります。この状態で、左エンキューが右エンキューと同時に走ると、ロック競合になります。しかし、そのような競合の確率は、大きなハッシュテーブルを使えば任意に低いレベルに落とすことができます。
図６．９は、１２要素が、４ハッシュバケツを持つ並列双方向キューにどのように収まるかを示します。それぞれの、元となる単一ロックの双方向キューは並列双方向キューの全ての要素の四分の一の部分を保持します。
図６．１０は、対応する C 言語のデータ構造です。既存の struct deq は、自明な、ロックのある双方向キュー実装であるとします。このデータ構造は２行目に左側のロックを持ち、３行目に左側のインデックス、４行目に右側のロック（これは、実際の実装ではキャッシュアラインされています）、５行目に右側のインデックス、そして最後に、６行目に単純なロックベースの双方向キューのハッシュされた配列を持ちます。高性能な実装は、当然、偽の共有を避けるために、パディングあるいは特別なアラインメントを使うべきでしょう。
図６．１１(lockhdeq.c)は、エンキューとデキュー関数の実装です。
脚注
他のいろいろな言語で、ポリモルフな実装を作成するのは容易でしょう。しかし、それは読者への課題とします。
左側の操作だけを議論します。右側の操作はそれから自明にわかるはずです。
１から１３行目は、pdeq_pop_l() です。これは、可能ならば要素を左デキューして返します。なければ、NULL を返します。６行目で左側のスピンロックを取り、７行目でデキュー対象のインデックスを計算します。８行目は要素をデキューし、９行目で結果が NULL でないなら、１０行目は新しい左側インデックスを記録します。いずれの場合も、１１行目でロックを放し、最後に、１２行目で、あれば要素を、なければ、NULL を返します。
２９から３８行は pdeq_push_l() です。これは、指定された要素を左エンキューします。３３行目で左側のロックを取り、３４行目で左側インデックスをピックアップします。３５行目は指定された要素を、左側インデックスが指す双方向キューに左エンキューします。そして３６行目で左側インデックスを更新し、３７行目でロックを放します。
前に述べたように、右側の操作は完全に左側の操作に似ていますので、それを調べるのは読者への課題とします。
クイッククイズ６．４
ハッシュされた双方向キューは良い解決策でしょうか？なぜそうですか、そうでないならなぜですか？
６．１．２．４ 複合双方向キュー再訪
この節は、複合双方向キューをもう一度考えます。今、空であるキューに、空でないキューのすべての要素を移すという、自明な再バランススキームを使います。
クイッククイズ６．５
空になったキューに全ての要素を移すですって？この頭のおかしい解決策が、どのような意味であれ最適であるとは、どんな可能な宇宙においてなのでしょう？？？
以前の節で紹介したハッシュされた実装と違って、この複合実装は、双方向キューの、ロックもアトミック操作も使わないシーケンシャルな実装を元にします。
図６．１２は、実装を示します。ハッシュされた実装と違って、この複合実装は非対称です。なので、 pdeq_pop_l() と pdeq_pop_r() をそれぞれ考察しなくてはいけません。
クイッククイズ６．６
なぜ、複合双方向キュー実装を対称にできないのですか？
図の１から１６行目は、pdeq_pop_l() 実装です。５行目で左側のロックを取ります。１４行目で放します。６行目は左側の双方向キューから要素を左デキューしようとします。それができれば、８から１３行目に行って、単純にこの要素を返します。そうでない時は、８行目で右側のロックを取り、９行目で右側のキューから要素を左デキューします。１０行目で右側のキューに残る全ての要素を左側のキューに移します。１１行目で右側のキューを初期化し、１２行目で右側のロックを放します。１０行目でデキューされた要素があれば、それを返します。
図の１８から３８行目は、pdeq_pop_r() 実装です。以前と同じように、２２行目は右側のロックを取り（３６行目で放します）、２３行目は右側のキューから要素を右デキューしようとします。それができれば、２４から３５行目に行って、単純にこの要素を返します。しかし、もし２４行目でデキューできる要素がないと判断した場合、２５行目は右側のロックを放して、２６と２７行目で両方のロックを正しい順に取ります。そして２８行目でもう一度右側のリストから要素を右デキューしようとします。２９行目で、この二度目の試みが失敗したと判断したら、３０行目で左側のキューから（もしあれば）要素を右デキューします。３１行目は左側のキューに残っている要素があれば全て、右側のキューに移し、３２行目は左側のキューを初期化します。いずれの場合も、３４行目で左側のロックを放します。
クイッククイズ６．７
なぜ、図６．１２の２８行目で右デキュー操作をもう一度試みる必要がありますか？
クイッククイズ６．８
左側のロックはいつかは空くはずです！！！それならなぜ、図６．１２の２５行目は無条件に右側のロックを放す必要があるのですか？
図６．１２の４０から４７行目は、pdeq_push_l() 実装です。４４行目で左側のスピンロックを取り、４５行目で要素を左側のキューに左エンキューし、最後に４６行目でロックを放します。pdeq_enqueue_r() 実装（４９から５６行目にあります）はとても似ています。
６．１．２．５ 双方向キューの議論
複合実装は、６．１．２．３節で紹介したハッシュされた変種に比べて、よりいくらか複雑です。でもそれはまだかなり単純です。もちろん、より賢い再バランススキームは任意の複雑さになることができます。しかし、ここで示した単純なスキームは、ソフトウェアの代替案に比べて性能が良いことが示されています。ハードウェア補助を使うアルゴリズムに比べてもそうです。しかし、私たちがそのようなスキームから期待できる最大のスケーラビリティは、二倍です。最大でも二つのスレッドが双方向キューのロックを同時に保持していることができるからです。この制限は、Michael の、コンペアアンドスワップをベースとする双方向キューのアルゴリズムのような、ノンブロッキング同期をベースとするアルゴリズムにも当てはまります。
脚注
この論文は、双方向キューのロックなし実装にとって、特別な、ダブルコンペアアンドスワップ(DACS) 命令はいらないことを示した点で、興味深いです。その代わり、一般的なコンペアアンドスワップ(つまり、 x86 cmpxchg )で十分です。
実際、Dice 達が述べたように、同期をしないシングルスレッドの双方向キューは、彼らが研究した全ての並列実装に比べて顕著に性能が良かったのです。なので、鍵となる点は、実装に依存することなく、共用キューのエンキューとデキューはかなりのオーバヘッドがあるということです。これは、３章で取り上げた題材のことを思えば、驚くことではないかもしれません。また、キューは厳格な FIFO の性質を持ちますし。
さらに、これらの厳格な FIFO キューは、コール元からは見えない、linearization point から見た限りにおいて厳格な FIFO なのです。
脚注
要するに、linearization point とは、ある関数の中の一点であり、その関数が効果を発揮したと言える点です。このロックベースの実装において、linearization point は、仕事をするクリティカルセクションの中のどの点であると言ってもよいです。
実は、これらの例では、linearization point はロックベースのクリティカルセクションに埋め込まれています。これらのキューは、（言うなれば）個々の操作が開始した時刻においてみると、厳格な FIFO ではありません。これは、厳格な FIFO という性質は、同時実行プログラムにおいてはそれほど価値のあるものではないことを示します。そして、実際、Kirsch 達はより厳格ではないキューであって、より優れた性能とスケーラビリティを与えるものを示しました。
脚注
Nir Shavit は、ほぼおなじ理由で、ゆるめたスタックを作成しました。この状況を見ると、linearization point は開発者よりは理論家にとって便利であるかのように思う人もいるかもしれません。あるいは、そのようなデータ構造とアルゴリズムの設計者たちが、その使用者の要求をどの程度考慮に入れているのかと疑問に思う人もいるでしょう。
とはいえ、もしあなたがあなたの同時実行プログラムで使われる全てのデータを単一のキューにプッシュしているとしたら、あなたはご自分の設計全体を考えなおすことが真に必要でしょう。
６．１．３ 分割の例の議論
６．１．１節のクイッククイズの答えで示された、食事をする哲学者問題の最適な解は、「水平並列性」あるいは「データ並列性」の優れた例でした。この場合の同期オーバヘッドは、ほとんど(あるいは正確に、と言ってもいいでしょう)ゼロです。それに対して、双方向キューの実装は、「垂直並列性」あるいは「パイプライニング」の例です。そこでは、データはあるスレッドから他に移動します。パイプラインが必要とするより緊密な連携は、その結果、あるレベルの効率を得るためには、より大きな仕事の単位を必要とします。
クイッククイズ６．９
横並びの双方向キューは、ハッシュされた双方向キューに比べて、２倍ほど速く走ります。ハッシュテーブルを、正気を超える大きさにしても同じです。これはなぜ？
クイッククイズ６．１０
双方向キューの同時実行を扱う、顕著に優れた方法があるでしょうか？
これらの二つの例は、並列アルゴリズムを考案するのに分割がいかに強力かを示しました。６．３．５節は３つ目の例、行列の掛け算を簡単に調べます。しかし、これら３つの例は全て、より多く、より優れた並列プログラムの基準を必要とします。それについては次の節で。
６．２ 設計基準
最高の性能とスケーラビリティを得る一つの方法は、可能な限り最高の並列プログラムに収束するまで、単純にハックし続けることです。不幸にも、あなたのプログラムが、顕微鏡で見るくらいに小さいのでない限り、可能な並列プログラムの空間はあまりに大きいので、宇宙の寿命の間で収束があるかは保証されません。それに、「可能な限り最高の並列プログラム」とは、正確には、何でしょう？結局、２．２節は、３つの並列プログラミングのゴール、性能、生産性、そして一般性を示しました。そして、可能な限りの最高性能は、生産性と一般性の点でコストを払っていることが予想されます。私達は開発中に、その並列プログラムが古臭いものとなる前に、許容できるくらいに良いレベルに到達するためには、高いレベルの選択をすることができなくてはいけないのは明らかです。
しかし、実際に実世界の設計を作り出すためには、より詳細な設計基準が必要です。この節では、その作業を取り上げます。これは実世界ですから、これらの基準はしばしば、多少なりとも矛盾します。なので、設計者は注意深く結果のトレードオフをバランスさせることが必要です。
なので、これらの基準は、設計に働く「力」と考えることができます。その中で、これらの力の間の特に優れたトレードオフが、「デザインパターン」と呼ばれるのです。
３つの並列プログラミングのゴールを達成するための設計基準は、高速化、競合、オーバヘッド、読み書き比率、そして複雑性です。
高速化：２．２節で述べたように、性能向上は、わざわざ時間を使いトラブルを起こしても並列化をしたい主な理由です。高速化の定義は、あるプログラムのシーケンシャルなバージョンを走らせるのに必要な時間と、並列化バージョンを走らせるのに必要な時間の比率です。
競合：ある並列プログラムがビジーにすることのできる数以上のCPUが使われると、余分のCPUは競合によって、役に立つ仕事をすることができません。これは、ロック競合、メモリ競合、あるいは、その他多数の性能キラーかもしれません。
仕事と同期の比率：ある並列プログラムの、ユニプロセッサ、シングルスレッド、ノンプリエンプティブ、そして割り込み不可能なバージョンは、どのような同期プリミティブも必要ないはずです。なので、これらのプリミティブが使う時間（通信キャッシュミスや、メッセージ遅延、ロックプリミティブ、アトミック命令、そしてメモリバリアを含みます）は、オーバヘッドです。それはそのプログラムが実現するように意図された役に立つ仕事に直接寄与しないものです。なお、重要な測定値は、同期オーバヘッドと、クリティカルセクションにあるコードのオーバヘッドの関係であることに注意下さい。つまり、長いクリティカルセクションは、より大きな同期オーバヘッドを許容します。仕事と同期の比率は、同期の効率という概念に関係しています。
読み書き比率：ほとんど更新されないデータ構造は、分割するのでなく、複製することが多いでしょう。さらに、それは非対称な同期プリミティブで守られることでしょう。それは、更新者の同期オーバヘッドを犠牲にしてリーダーのそれを減らします。そうして、全体としての同期オーバヘッドを減らします。５章で述べるように、更新が頻繁なデータ構造に対しては、対応する最適化が可能です。
複雑性：並列プログラムは、同等のシーケンシャルプログラムよりもより複雑です。なぜならば、並列プログラムはシーケンシャルプログラムに比べて、よりすっと大きな状態空間を持つからです。なお、この大きな状態空間は、十分な規則正しさと構造を持つならば、ある場合には、簡単に理解することができます。並列プログラマは、同期プリミティブ、メッセージ、ロック設計、クリティカルセクションの認識、そしてデッドロックを、この大きな状態空間の文脈で考慮する必要があります。
このより大きな複雑さは、しばしば、開発と維持のより高いコストに変換されます。なので、既存のプログラムに加えられる変更の数とタイプは、予算によって制限されることがあります。ある高速化の程度は、それに見合う時間とトラブルによってしか得られないからです。さらに悪いことに、加わった複雑さが、実際に性能とスケーラビリティを減らすこともあります。
なので、ある点を超えると、並列化よりも安価でより効果的な潜在的なシーケンシャル最適化があるかもしれません。２．２．１節で述べたように、並列化は、多数の性能最適化のうちの一つに過ぎません。それに、それはCPUベースのボトルネックに最も適する最適化です。
これらの基準は、最大の高速化を実現するためにまとめてはたらきます。最初の３つの基準は深く関連しているので、この節の残りでは、これらの関連を解析します。
脚注
実際の世界の並列システムは、これより多くの設計基準の元にあります。例えば、データ構造レイアウト、メモリサイズ、メモリ階層のレイテンシー、バンド幅の制限、そしてI/Oの問題などです。
これらの基準は、要求仕様の一部としても現れることがあることに注意下さい。例えば、高速化は、相対的な要求（「速ければ速いほど良い」）としてはたらくことも、ワークロードの絶対的要件（「システムは、少なくても、１秒に１００万ウェブヒットをサポートしなくてはいけない」）としてはたらくことも、あります。古典的なデザインパターン言語は、相対的要求を力で、絶対的要件を文脈で表します。
並列プログラムのための適切な設計トレードオフを決めるときに、これらの設計基準の間の関係を理解するのはとても役に立ちます。
１ プログラムがクリティカルセクションで過ごす時間が短ければ短いほど、潜在的高速化は大きくなります。これはアムダールの法則の結果であり、一度に１つのCPUだけがあるクリティカルセクションで実行することができるという事実の結果です。
より正確には、そのプログラムがある排他的クリティカルセクションで過ごす時間の割合は、CPU数の逆数よりもずっと小さくなくてはいけません。そうでないと、実際に得られる高速化がCPU数に近づくことはできません。例えば、１０CPUで動くプログラムは、それがとても良くスケールするためには、最も制限の強いクリティカルセクションで、自分の時間の１０分の１よりもずっと短い時間しか過ごしてはいけません。
２ 実際の高速化が使用可能なCPU数よりも小さいなら、競合の効果は、余分のCPUと そして／あるいは 実時間を浪費しているはずです。CPU数と実際の高速化の差が大きくなるほど、CPUの使用効率は下がります。同様に、要求される効率が高ければ、達成可能な高速化は小さくなります。
３ 使用可能な同期プリミティブが、それが守るクリティカルセクションに比べて高いオーバーヘッドを持つならば、高速化を改善する最適な方法は、そのプリミティブが呼ばれる回数を減らすことです。（たぶん、クリティカルセクションをまとめるとか、データ所有を使うとか、非対称なプリミティブを使うとか（９章を参照）、あるいは、コードロッキングのようなより荒い粒度の設計に進むなどの方法により。）
４ もし、クリティカルセクションがそれを守るプリミティブに比べて高いオーバーヘッドを持つならば、高速化を改善する最適な方法は、リーダーライターロッキングや、データロッキング、非同期あるいはデータ所有に進むなどの方法により、並列性を増すことです。
５ もし、クリティカルセクションがそれを守るプリミティブに比べて高いオーバーヘッドを持ち、かつ、守られるデータ構造が更新よりもずっと多く読まれるならば、並列性を改善する最適な方法は、リーダーライターロッキングあるいは非同期プリミティブに進むことです。
６ SMP性能を改善する多くの変更、例えば、ロック競合を減らすなど、は、同時にリアルタイム遅延も改善します。
クイッククイズ６．１１
クリティカルセクションについてのこれら全ての問題が意味するのは、私達は、単純に、常に、クリティカルセクションを持たないノンブロッキング同期を使うべきだということではないでしょうか？
６．３ 同期粒度
図６．１３は、同期粒度の異なるレベルの絵を示します。以下の節で、一つづつ取り上げます。これらの節は主に、ロックに焦点を当てますが、同期の全ての形においても同様の粒度の問題が現れます。
６．３．１ シーケンシャルプログラム
もしそのプログラムが単一プロセッサで十分に速く走り、他のプロセス、スレッド、割り込みハンドラと相互作用を何もしないならば、あなたは同期プリミティブを削除すべきです。そして、それらのオーバーヘッドと複雑さから、あなたを自由にするのがよいでしょう。何年か前に、ムーアの法則は最終的にすべてのプログラムを強制的にこのカテゴリに入れるだろうと主張した人がいました。しかし、図６．１４でわかるように、シングルスレッドの指数的性能向上は、２００３年ころに終わりました。なので、性能を向上させるには、より多くの並列性が必要です。
脚注
このプロットは、理論的に１クロックで１つ以上の命令をリタイアできる新しいCPUのクロック周波数と、最も簡単な命令の実行にさえ複数クロックを必要とした古いCPUのMIPSを示します。このアプローチを取った理由は、新しいCPUのクロックあたり複数の命令をリタイアできる能力は典型的にはメモリシステムの性能で制限されるためです。
この新しい潮流の結果、１つのチップに数千のCPUがのるようになるかという討論の結果はすぐには出そうにありません。しかし、Paul はこの文を、デュアルコアのラップトップでタイプしている事から見て、SMPの時代が訪れたようです。また、図６．１５が示すように、イーサネットのバンド幅も増加し続けていることに注意するのは重要です。この増加は、通信の負荷を処理するためにマルチスレッドのサーバーを動機づけるでしょう。
これは、あなたがそれぞれ全てのプログラムをマルチスレッド式にコードするべきだということを意味しないことに注意下さい。繰り返しますが、もしプログラムが単一プロセッサで十分速く走るなら、あなたはわざわざ、SMP同期プリミティブのオーバヘッドと複雑さにかかわることはありません。図６．１６のハッシュテーブル検索コードの単純さはこの点を裏付けます。
脚注
この節の例は、Hart et al. [HMB06] から取りました。複数ファイルから関連するコードを集めて、わかりやすくするために修正をしてあります。
鍵となる点は、並列化によるスピートアップは、通常はCPU数を上限とすることです。それに対して、例えば、データ構造を注意深く選ぶなどによるシーケンシャル最適化によるスピートアップは任意に大きくなることができます。
一方、あなたがこの幸せな状況におられないなら、読み続けましょう！
６．３．２ コードロッキング
コードロッキングは、それがグローバルロックだけを使うという事実から、とても単純です。
脚注
もしあなたのプログラムがそうでなくてロックをデータ構造に持っていたり、 Java の場合、synchronized インスタンスを持つクラスを使っているならば、あなたは６．３．３節で述べる「データロッキング」を使っています。
既存のプログラムを、マルチプロセッサで走らせるために、コードロッキングを使うように変更するのは特に簡単です。もしプログラムが単一の共用資源しか持たないならば、コードロッキングは最適な性能を発揮することさえあります。しかし、より大きく、より複雑なプログラムの多くは、実行の多くがクリティカルセクションで行われることを必要とします。その結果、コードロッキングは著しくスケーラビリティが制限されます。
なので、コードロッキングは、実行時間のごく一部分をクリティカルセクションで費やすプログラムか、あるいは、ほどほどのスケーリングしか要求されないプログラムにおいて使うのが良いでしょう。これらの場合、コードロッキングは、図６．１７に示すように、そのシーケンシャル版ととても似ている、比較的単純なプログラムを提供します。しかし、図６．１６の hash_search() では、単純に比較結果を返すだけだったのが、戻る前にロックを放さないといけないために３つの文になっているのに注意下さい。
不幸にも、コードロッキングは特に、「ロック競合」を起こしやすいです。そこでは、複数のCPUが同時にロックを取る必要があります。小さい子供達のグループ（あるいは、子供のように振る舞う大人達のグループ）の世話をしたことのあるSMPプログラマは、図６．１８に示すように、何かがたった一つしか無いことの危険を直ちに理解できるでしょう。
この問題の一つの解決策は「データロッキング」と呼ばれ、次の節で説明します。
６．３．３ データロッキング
多くのデータ構造は分割可能です。データ構造のそれぞれの分割がそれ自身のロックを持つようにできます。すると、データ構造のそれぞれの部分に対応するクリティカルセクションは並列に実行できます。ただし、ある分割のある時点では、ただ一つのクリティカルセクションのインスタンスしか、実行できません。競合を減らす必要があり、同期オーバヘッドが高速化を制限しているのでないならば、データロッキングを使うべきです。データロッキングは、必要以上に大きいクリティカルセクションのインスタンスを、複数のデータ構造に分散することによって、競合を減らします。例えば、図６．１９に示すように、ハッシュテーブルでハッシュバケツごとのクリティカルセクションを維持します。スケーラビリティの増加は、同時に、追加されたデータ構造である struct bucket という少しばかりの複雑さの増加につながります。
図６．１８に示した競合状況に比べて、データロッキングは図６．２０に示した平和を促進する助けとなります。そして、並列プログラミングでは、これは、ほとんど常に、性能とスケーラビリティの増加につながります。このために、Sequent は、その DYNIX と DYNIX/ptx オペレーティングシステム両方において、データロッキングを大いに使いました。
しかし、小さい子供達の世話をしたことのある人はまたしても、十分な量が行き渡るようにしても、平和の保証とはならないことを証言するでしょう。似たことが、SMPプログラムでも起きます。例えば、Linuxカーネルは、ファイルとディレクトリのキャッシュ（dcache と呼ばれます）を維持します。このキャッシュのそれぞれのエントリは自身のロックを持ちます。しかし、ルートディレクトリと、その直下の子供に対応するエントリは、それより端っこにあるエントリと比べて、ずっとトラバースされることが多いと言えます。この結果、多くのCPUがこれら著名なエントリのロックを取り合うことになり、図６．２１に示す状況と対して変わらないことになります。
多くの場合、データかたよりのインスタンスを減らすためのアルゴリズムを設計することができます。ある場合には、完全にそれを除くこともできます（Linux カーネルの dcache でも可能と思われるように[MSS04]）。データロッキングは、ハッシュテーブルのような分割可能データ構造でしばしば使われています。また、複数のエントリがそれぞれ、あるデータ構造のインスタンスで表現されるような場合にもです。Linux カーネルバージョン 2.6.17 のタスクリストは後者の例です。それぞれのタスク構造体は自分の proc_lock を持ちます。
ダイナミックに確保される構造でデータロッキングをする時の鍵となる挑戦は、ロックが取られるときに構造が存在し続けることを保証することです。図６．１８のコードは、ロックを、静的に確保されているハッシュバケツに置くことで、この挑戦を巧みにかわします。それは決して解放されませんから。しかし、このトリックは、ハッシュテーブルがサイズ変更可能の時にはうまくいきません。ロックは今回はダイナミックに確保されるからです。この場合は、ロックが取られるその間に、ハッシュバケツが解放されるのを防ぐための何らかの手段が必要です。
クイッククイズ６．１２：
構造体のロックが取られるときに構造体が解放されるのを防ぐための方法はどんなものがありますか？
６．３．４ データ所有
データ所有は、あるデータ構造をスレッドあるいはCPUごとに分割して、そのスレッドあるいはCPUがデータ構造の自分のサブセットを、一切の同期オーバーヘッドなしでアクセス可能とします。しかし、もしあるスレッドがどれか他のスレッドのデータをアクセスしたくても、最初のスレッドはそれを直接行うことができません。その代わり、最初のスレッドは２つ目のスレッドと通信して、２つ目のスレッドに最初のスレッドの代わりにその操作を実行してもらうか、あるいは、そのデータを最初のスレッドのところに移動しなくてはいけません。
データ所有は難しく見えるかもしれませんが、とてもひんぱんに使われています。
１ ある一つのCPUあるいはスレッドからだけアクセスできる変数（C と C++ の auto 変数のように）は、そのCPUあるいはスレッドに所有されます。
２ ユーザインタフェースのあるインスタンスが、そのユーザのコンテキストを持っています。並列データベースエンジンと相互作用するアプリケーションが、完全にシーケンシャルプログラムであるかのように書かれるのはとても一般的です。そういうアプリケーションは、ユーザインタフェースと現在のアクションを所有します。明示的な並列化は、このため、データベースエンジン自身に閉じ込められています。
３ パラメータシミュレーションはしばしば、それぞれのスレッドが、パラメータ空間の特定の領域を所有することを許すことによって、自明なやり方で並列化することができます。このたぐいの問題のために設計された計算フレームワークもいくつかあります[UoC08]。
もしも共有が多い時は、スレッドあるいはCPUの間の通信は、重大な複雑さとオーバーヘッドになることがあります。さらに、最もひんぱんに使われるデータが、単一CPUが所有するデータであった場合、そのCPUは「ホットスポット」になります。図６．２１に描かれるようなことになります。しかし、共用がいらない状況では、データ所有は理想的な性能を発揮します。そして、コードも、図６．１６に示すシーケンシャルプログラムと同じくらいに単純となります。そういう状況はしばしば、「なんちゃって並列」と呼ばれ、最適な場合、以前に図６．２０に示した状況に近づきます。
データ所有のもう一つの重要な例は、データがリードオンリーの時です。この場合、全てのスレッドはそれを、複製によって「所有」できます。
データ所有については、８章でより詳しく述べます。
６．３．５ ロック粒度と性能
この節は、数学的な同期の効率性という観点から、ロック粒度と性能を調べます。数学な苦手な読者はこの節を飛ばしてもよいです。
単一の共用されたグローバル変数を操作する同期機構の効率性を、M/M/1 キューを元とする、生のキューイングモデルを使うアプローチを取ります。M/M/1 キューイングモデルは、指数分布する「到着間隔率」λ と、指数分布する「サービス率」µ を基礎とします。到着間隔率 λ は、同期に要する時間がゼロの時にシステムが処理できる１秒あたりの同期操作の平均数と考えられます。言葉を変えて言えば、 λ は、それぞれの同期を含まない仕事の単位のオーバーヘッドの逆数です。例えば、それぞれの仕事の単位がトランザクションであり、一つのトランザクションを処理するのに、同期オーバーヘッドを含めないで１ミリ秒必要ならば、λ は、1,000 トランザクション／秒です。
サービス率 µ も同様に定義されます。今回はそれは、トランザクションに要する時間がゼロの時にシステムが処理できる１秒あたりの同期操作の平均数です。なお、CPUは同期操作が完了するまでお互いに待たなくてはいけない事実は無視します。言葉を変えて言えば、µ は競合のない時の同期オーバーヘッドとざっと考えることができます。例えば、それぞれの同期操作がアトミック加算命令を持ち、その計算機システムは、CPUがプライベート変数に対してアトミック加算をするのに２５ナノ秒かかるとします。
脚注。
もちろん、８つのCPUがいて、皆が同じ共有変数を加算するならば、それぞれのCPUは、自分が加算をして２５ナノ秒を消費する前に、他のCPUがそれぞれ自分の加算をするまで、少なくても１７５ナノ秒待たなくてはいけません。実際の場合は、変数をあるCPUから他に移動する必要があるので、待ち時間はより長くなるでしょう。
すると、µ の値は、ほぼ、 40,000,000 アトミック命令／秒です。
もちろん、λ の値はCPUが増えると増えます。それぞれのCPUは独立にトランザクションを処理できるからです（今回も同期を無視します）。
n はCPUの数で、 λ0 は単一CPUのトランザクション処理能力です。単一CPUが単一トランザクションを処理する時間の期待値は 1/λ0 であることに注意ください。
CPUが単一の共用変数を加算する機会を得るためには、それぞれ「列に並んで待つ」必要がありますから、待ち時間全体の期待値は、M/M/1 キューイングモデルの式を使うことができます。
λ を代入すると、こうなります。
次に、効率とは、同期が無いときにトランザクションを処理するのに必要な時間(1/λ0)と、同期を含む、必要な時間(T +1/λ0)との比率です。
この式にT を代入して、簡略化すると、こうなります。
しかし、μ/λ0 の値は、トランザクションを処理するのに必要な時間（同期オーバーヘッドはなし）と、同期オーバーヘッド自身（競合はなし）の比率そのものです。これを、f と呼ぶと、こうなります。
図６．２２は、同期効率 e を、CPUあるいはスレッド数 n の関数としてプロットします。オーバーヘッド比率 f のいくつかの値について示します。例えば、再び２５ナノ秒のアトミック加算を使うと、f = 10 の線は、それぞれのCPUが２５０ナノ秒ごとにアトミック加算を試みるのに対応し、f = 100 の線は、それぞれのCPUが２．５マイクロ秒ごとにアトミック加算を試みるのに対応します。後者は、つまり、数千命令に一度ということになります。どの線も、CPUあるいはスレッド数が増えると激しく落ちますから、単一のグローバル共用変数をアトミック操作することを元にする同期機構は、現代のコモディティハードウェアにおいてひんぱんに使われるならば、うまくスケールしないと結論付けることができるでしょう。これが、５章で議論した、並列カウンティングアルゴリズムを導くに至った強制力の、数学的記述です。
効率という概念は、正式な同期を全くあるいはほとんど使わない時にも、便利です。例えば、行列の掛け算を考えましょう。ある行列の列が、（「ドット積」により）他の行列の行に掛け算されて、３つ目の行列のエントリとなります。これらの操作はいずれも競合しないので、最初の行列の列をスレッドのグループに分割して、それぞれのスレッドが結果となる行列の対応する列を計算することが可能です。このスレッドはこうして、完全に独立に動作できます。いかなる同期オーバーヘッドもありません。これを、matmul.c に示します。なので、並列行列掛け算は、完全な効率、１．０を持つと期待できます。
しかし、図６．２３は異なる物語を示します。特に、６４かける６４行列の掛け算は、０．７以上の効率になることが決してありません。単一スレッドで動作してもです。５１２かける５１２行列の掛け算の効率は、１０スレッド以下ではわずかに１．０を下回ります。１０２４かける１０２４行列の掛け算でさえ、数十のスレッドにおいて、完璧から明らかに乖離してきます。とはいえ、この図は、バッチ効果が性能とスケーラビリティに与える利益を明らかに示しています。あなたが同期オーバーヘッドを起こさないといけないにしても、払ったお金だけの価値は得ることが可能です。
クイッククイズ６．１３
単一スレッドの６４かける６４行列の掛け算が、１．０より小さい効率になるなんて、どうやったらありえるのです？図６．２３の全ての線は、ただ１スレッドで動作したならば、正確に１．０の効率を持つべきでないのですか？
このような非効率があるため、６．３．３節で述べたデータロッキングのような、よりスケーラブルなアプローチを調べるのは意味の有ることです。あるいは、次の節で述べる、並列高速パスアプローチも。
クイッククイズ６．１４
データ並列テクニックが、どうやったら、行列掛け算の役に立つのです？それは既にデータ並列でしょう！！！
６．４ 並列高速パス
細粒度の(なので普通は、高性能の)設計は、典型的には荒い粒度の設計よりも複雑です。多くの場合、オーバヘッドのほとんどは、コードの小さな部分によって起こされます。ならば、その小さな部分に努力を集中したらどうでしょう？
これが、並列高速パスのデザインパターンの背後にある考えです。つまり、アルゴリズム全体を強力に並列化するのに必要となる複雑さを避けて、一般的なコードパスを強力に並列化するというものです。あなたは、並列化したい特定のアルゴリズムを理解するだけでなく、そのアルゴリズムが動くワークロードも理解する必要があります。並列高速パスを実現するには、多大な創造性と設計努力が、しばしば必要です。
並列高速パスは、異なるパターンを結合します。(一つは高速パスのため、もう一つは他で)なので、それは、テンプレートパターンです。
以下の並列高速パスのインスタンスは、しばしば見られるので、図６．２４に示す、それ専用のパターンであると言えます。
１ リーダーライターロック（以下、６．４．１節で述べます）
２ リード、コピー、アップデート（RCU)。これは、リーダーライターロックの高性能な代替として使うことができ、９．３節で紹介します。この章では、これ以上は扱いません。
３ 階層ロック。これは、６．４．２節で述べます。
４ 資源確保キャッシュ。詳しくは、６．４．３節を参照。
６．４．１ リーダーライターロック
もし同期オーバヘッドが無視でき(例えば、プログラムは大きなクリティカルセクションを持ち、荒い粒度の並列性を使っているならば)、そして、クリティカルセクションの小さな部分だけがデータを変更するならば、複数のリーダーが並列に進行できるようにすれば、スケーラビリティは大いに上がります。ライターは、リーダーと、ライターの両方を排他します。リーダーライターロッキングには多くの実装があり、４．２．４節で述べた POSIX 実装も含まれます。図６．２５は、ハッシュ検索をリーダーライターロックを使って実装するのを示します。
リーダーライターロッキングは、非対称ロックの単純な例です。Snaman [ST87] は、いくつかのクラスタシステムで使われる、はるかに華麗な６モードの非対称ロックについて述べています。ロック一般について、あるいは、特にリーダーライターロッキングについては、７章で十分に取り上げます。
６．４．２ 階層ロック
階層ロッキングの背後にある考えは、どの細粒度のロックを取ったらいいかを決めるために必要な時間だけ、荒い粒度のロックを取るというものです。図６．２６に、おなじみのハッシュテーブル検索を、階層ロックを使うようにしたものを示します。しかしそれは同時に、このアプローチの重大な弱点を示しています。私たちは、２つ目のロックをとるというオーバーヘッドを支払いましたが、それをわずかの時間しか、保持しないのです。この場合、より単純なデータロッキングアプローチの方が、単純で、性能も良いように思えます。
クイッククイズ６．１５
階層ロックがうまくいくのは、どのような状況でしょう？
６．４．３ 資源確保キャッシュ
この節は、並列の固定ブロック長のメモリアロケータの単純化された概要を示します。より詳しい説明は、論文あるいは、Linuxカーネルにあるでしょう。
６．４．３．１ 並列資源確保問題
並列メモリアロケータが直面する基本的問題は、極端に速いメモリ確保と解放を一般的な場合に提供する必要性と、不都合な確保と解放パターンの時にでもメモリを効率よく分散する必要性との間の緊張関係です。
この緊張関係を見るために、この問題に、データ所有を直裁的に適用したところを考えましょう。単純に、メモリを切り分けて、それぞれのCPUが自分の持ち分を占有するようにします。例えば、２つのCPUを持つシステムが２ギガバイトのメモリを持つとします(ちょうど、私が今これをタイプしているこれのように)。単純にそれぞれのCPUに１ギガバイトを割り当てて、それぞれのCPUが自分のプライベートなメモリのチャンクをアクセスさせることができます。そうすればロックの必要はなく、その複雑さもオーバヘッドもありません。不幸にも、この単純な計画は、CPU０がすべてのメモリを確保して、CPU１がそれを解放するように動くアルゴリズムの元では破綻します。それは、単純な生産者、消費者ワークロードではあり得ることです。
別の極限であるコードロッキングは、過剰なロックの競合とオーバヘッドの問題があります。
６．４．３．２ 資源確保のための並列高速パス
よく使われる解決策は、並列高速パスを使います。そこでは、それぞれのCPUが、わずかのブロックをキャッシュして所有し、残りのブロックはコードロックした大きな共用プールに置きます。ある特定のCPUがメモリブロックを独占するのを防ぐため、それぞれのCPUのキャッシュに置くことのできるブロック数に上限を設けます。２CPUのシステムでは、メモリブロックの流れは、図６．２７に示すようになります。あるCPUが、自分のプールが一杯の時にブロックを解放しようとしたら、そのブロックをグローバルプールに送ります。同様に、CPUが自分のプールが空の時にブロックを確保しようとしたら、ブロックをグローバルプールからとります。
６．４．３．３ データ構造
図６．２８に、アロケータキャッシュの「おもちゃの」実装のための実際のデータ構造を示します。図６．２７の「グローバルプール」は、struct globalmempool 型の globalmem で実装され、２つのCPUプールは、 percpumempool 型の percpumem というCPUごとの変数で実装されます。これらのデータ構造はどちらも、ブロックへのポインタの配列を、その pool フィールドに持ちます。配列は、インデックス０から上へと使われます。なので、もし globalmem.pool[3] が NULL なら、配列の残り、インデックス４から上も NULL でなくてはいけません。 cur フィールドは、 pool 配列の使用中の要素の最大のインデックスを持ちます。あるいは、全ての要素が空なら、 -1 です。globalmem.pool[0] から globalmem.pool[globalmem.cur] までの全ての要素は使用中であり残りは空でなくてはいけません。
脚注
どちらのプール長(TARGET_POOL_SIZE と GLOBAL_POOL_SIZE) も、非現実的に小さいです。しかし、この小ささのおかげで、プログラムをシングルステップして、それがどのように動くのかを感じることがより簡単です。
プールデータ構造の操作を、図６．２９に示します。６つの箱が、 pool フィールドを作るポインタの配列を示します。そしてその前の数字が、cur フィールドです。塗ってある箱は NULL でないポインタを示し、白い箱は NULL ポインタを示します。重要な、しかし、潜在的に混乱する、このデータ構造の不変量は、cur フィールドは常に、NULL でないポインタの数よりも１つ小さいことです。
６．４．３．４ 確保関数
図６．３０に、確保関数 memblock_alloc() を示します。７行目で現在スレッドのスレッドごとプールを取り上げます。８行目でそれが空かを見ます。
そうなら、９から１６行目でそれをグローバルプールから持ってきて一杯にしようとします。スピンロックは９行目で取って、１６行目で放します。１０から１４行目でブロックを、グローバルからスレッドごとのプールに移します。それは、ローカルプールがその目標の大きさ(半分まで一杯)に達するか、グローバルプールが空になるまで行われます。１５行目は、スレッドごとプールの数を適切な値にします。
いずれの場合も、１８行目でスレッドごとプールがまだ空かを見て、そうでないなら、１９から２１行でブロックを取り除いて戻ります。あるいは、２３行目でメモリがなくなったという悲しいお話を告げます。
６．４．３．５ 解放関数
図６．３１は、メモリブロック解放関数です。６行目でこのスレッドのプールへのポインタを得て、７行目でこのスレッドごとのプールが一杯かを見ます。
そうならば、８から１５行目でスレッドごとプールの半分をグローバルプールに移します。スピンロックは８行目で取り、１４行目で放します。９から１２行目はブロックをローカルからグローバルなプールに移すループを実装します。１３行目は、スレッドごとプールの数を適切な値にします。
いずれの場合も、１６行目で新しく解放されたブロックをスレッドごとプールに置きます。
６．４．３．６ 性能
図６．３２に、荒い性能結果を示します。
脚注
このデータは統計的に意味のある方法で採取されたのではないので、大きな懐疑と共に見なければいけません。１１章は良いデータ採取と還元の実践を議論します。とは言え、繰り返した実行は似た結果を出しましたし、これらの結果は、類似のアルゴリズムのより注意深い評価にも一致します。
これは、デュアルコアインテル x86 周波数 1GHz (4300 bogomips per CPU) で測ったものです。それぞれのCPUのキャッシュには最大で６ブロックが許されます。このマイクロベンチマークでは、それぞれのスレッドは繰り返し、ブロックのグループを確保して、次にそのグループのブロックを全て解放します。"X" は、２スレッドの実行で、"+" は、１スレッドの実行の結果です。
６までのラン長は、線形にスケールし、素晴らしい性能を示しますが、６より大きいラン長は性能が悪く、ほぼ常に負のスケーリングを示すことに注意下さい。なので、TARGET_POOL_SIZE を十分に大きくすることはとても大切です。幸運にもそれは、実際に行うのが通常はとても簡単です。特に、最近はメモリが大きいですから。例えば、ほとんどのシステムで、TARGET_POOL_SIZE を１００にするのはとても合理的です。その場合、確保と解放は９９％以上、スレッドごとのプールに閉じ込められることが期待できます。
図でわかるように、一般的な、データ所有が適用できる状況(６までのラン長)は、ロックを取らなくてはいけない場合に比べて大いに改善された性能を与えます。一般的な場合に同期を避けるというのは、この本全体に繰り返し現れる主題であるでしょう。
クイッククイズ６．１６
図６．３２で、３つのサンプルから成るグループにおいて、ラン長が長くなると性能が上がるパターンがあります。例えば、ラン長１０，１１，１２です。なぜでしょう？
クイッククイズ６．１７
２スレッドのテストで、ラン長が１９以上の時、確保失敗が見られました。以下の条件の元で、失敗が起きる可能性のある最小の確保ラン長はいくつでしょう？グローバルプール長は４０。スレッドごとの目標プール長 s は３。スレッド数 n は２。スレッドごとのプールは最初、空で、使用中のメモリは無し。(それぞれのスレッドは繰り返し、m ブロックのメモリを確保し、次に m ブロックのメモリを解放することに注意下さい。)
あるいは、n スレッドがあり、それぞれのプール長は s であり、m ブロックのメモリを確保し、次に m ブロックのメモリを解放するとしたら、グローバルプール長はどのくらい大きくないといけないでしょう？
注意: 正しい答えを得るには、smpalloc.c ソースコードをよく調べる必要があります。多分、シングルステップする必要もあるでしょう。私はちゃんと警告しましたからね！
６．４．３．７ 実世界の設計
おもちゃの並列資源アロケータはとても単純でした。しかし、実世界の設計は多くの点でこのアプローチを拡張します。
まず、実世界のアロケータは、広い範囲の確保長を扱う必要があります。このおもちゃの例で示した、単一長ではありません。これを行うよくある方法は、いろいろな長さの固定の集合を提供することです。外部と内部の断片化をバランスするように長さの集合を決めます。ちょうど、１９８０年代後半の BSD メモリアロケータのようにです。これをするというとは、「globalmem」変数は、長さごとに必要であることを意味します。対応するロックも同様に複製する必要があります。その結果、おもちゃのコードのコードロッキングでなくて、データロッキングになります。
次に、本番品質のシステムは、メモリを再使用しなくてはいけません。つまり、ブロックをくっつけて、ページのようなより大きな構造にすることができなくてはいけません。くっつけるためにもロックで守る必要があり、これも長さごとに複製する必要があります。
３つめに、くっつけたメモリは、元となるメモリシステムに返さなくてはいけませんし、メモリのページは、元となるメモリシステムから確保しなくてはいけません。このレベルで必要となるロックは、元となるメモリシステムのロックに依存するでしょうが、コードロッキングでもかまいません。しばしば、このレベルではコードロッキングが許容されます。なぜならば、良く設計されたシステムでは、このレベルはほとんど動くことはないからです。
この実世界の設計の大きな複雑さにも関わらず、元になる考えは同じです。表６．１に示すように、並列高速パスを繰り返し適用することです。
６．５ 分割を越えて
この章は、単純で線形にスケールする並列プログラムを設計するためにデータ分割をどのように使うことができるかを議論してきました。６．３．４節は、データ複製の可能性を示唆しました。これは、９．３節で大いに使われます。
分割と複製を適用する主なゴールは、線形のスピードアップを得ることです。言葉を変えて言えば、必要な仕事の全体の量が、CPUあるいはスレッドの数が増えても大幅に増えることのないことを保証することです。分割と／あるいは複製によって、線形のスピードアップが得られて解決できる問題を、なんちゃって並列と呼びます。でも、それより上手くやることはできるでしょうか？
この質問に応えるために、迷路と迷宮の解法を調べましょう。もちろん、迷路と迷宮は何千年も前から、興味の対象でした。なので、それが計算機を使って作成、解決されるのは驚くべきことではありません。計算機には、生物計算機、GPGPU、そして離散ハードウェアさえも含まれます。迷路の並列解法は、時には大学のクラスのプロジェクトに使われたり、並列プログラミングフレームワークの効果を誇示するビークルとしても使われます。
一般的な忠告は、parallel work-queue アルゴリズム (PWQ) を使うことです。この節は、PWQ をシーケンシャルアルゴリズム(SEQ)と比較したり、また、他の並列アルゴリズムと比較することで、この忠告を評価します。いずれの場合も、ランダムに生成された正方形の迷路を解きます。６．５．１節はPWQ を議論し、６．５．２節は他の並列アルゴリズムを議論します。６．５．３節はその異常な性能を解析し、６．５．４節は他の並列アルゴリズムから、改善されたシーケンシャルアルゴリズムを導き出します。６．５．５節はさらに性能比較を行い、最後に６．５．６節は将来の方向性とまとめの言葉を述べます。
６．５．１ ワークキュー並列迷路ソルバ
PWQ は SEQ に基づき、図６．３３ (maze_seq.c)に示されます。迷路は二次元のセルの配列と、->visited と呼ばれる線形配列に基づくワークキューで表されます。
７行目で最初のセルを訪問します。８から２１行目にあるループのそれぞれの繰り返しは、一つのセルの先にある道をトラバースします。９から１３行目にあるループは ->visited[] の訪問したセル配列の中で、訪問していないお隣を探します。そして１４から１９行目にあるループはそのお隣の先にあるサブ迷路の一つの分岐をトラバースします。２０行目は外側のループの次の繰り返しのための初期化をします。
maze_try_visit_cell() の疑似コードを図６．３４の１から１２行目に示します。４行目でセル c と n が隣接しつながっているかを調べます。５行目でセル n がまだ訪問されてないかを見ます。celladdr() 関数はそのセルのアドレスを返します。どちらかのチェックが失敗したら、６行目で失敗を返します。
７行目は次のセルを返します。８行目はこのセルを ->visited[] 配列の次のスロットに記録します。９行目はこのスレットが一杯であることを示します。１０行目はこのセルを訪問済みにして、迷路の開始点からの距離も記録します。１１行目で成功を返します。
図 (maze.c) の１４から２８行は、maze_find_any_next_cell() の擬似コードです。１７行目で現在のセルの距離＋１をピックアップします。１９，２１，２３そして２５行目はそれぞれの方向のセルをチェックし、２０，２２，２４そして２６行目で対応するセルが、次のセルの候補であるなら真を返します。prevcol(), nextcol(), prevrow(), そして nextrow() はそれぞれ、指定された配列のインデックス変換操作をします。候補となるセルがなければ、２７行目で偽を返します。
パスを迷路に記録するのは、開始点からのセルの数を数えることで行います。これを図６．３５に示します。開始セルは左上で終了セルは右下です。終了セルから初めて、連続して減少するセル番号をたどれば、解をトラバースできます。
並列ワークキューソルバは、図６．３３と６．３４に示したアルゴリズムの直裁的な並列化です。図６．３３の１０行目は fetch-and-add を使わなくてはならず、ローカル変数 vi はいろいろなスレッド間で共用されなくてはいけません。図６．３４の５と１０行目は、CAS ループに組み込まれなくてはいけません。CAS の失敗は、迷路にループがあることを示します。この図の８と９行目は fetch-and-add を使って、->visited[] 配列に同時にセルを記録しようとする試みを調停しなくてはいけません。
このアプローチはたしかに、 2.53GHz で動作する dual-CPU Lenovo(TM) W500 で大きなスピートアップを提供します。それを図６．３６に示します。それは、５００かける５００の正方形のランダムに生成された異なる５００の迷路の解決に対して、２つのアルゴリズムの解決に要した時間の cumulative distribution function (CDF) 累積分布関数を示します。CDF を x 軸に射影した時のかなりのオーバーラップについては、６．５．３節で説明します。
興味深いことに、シーケンシャルな解答パス追跡は、並列アルゴリズムでもそのまま変えずに動きます。しかし、これは並列アルゴリズムの重要な弱点を明らかにします。ある時間の一点において、最大一つのスレッドだけが、解答パスにそって進行を許されるのです。次の節でこの弱点を説明します。
６．５．２ 他の迷路ソルバ
初期の迷路解決者はしばしば、両方の終端から始めるように勧められました。そしてこの忠告は、最近も、自動迷路解決の文脈で繰り返されてきました。この忠告は、分割につながります。それは、オペレーティングシステムカーネルにとってもアプリケーションにとっても、並列プログラミングの文脈でこれまで、強力な並列化戦略でした。この節はこの戦略を適用します。解決パスの両側の端から開始する２つの子スレッドを使います。そして、性能とスケーラビリティの結果を簡単に観察します。
図６．３７ (maze_part.c) に partitioned parallel algorithm (PART) 分割並列アルゴリズムを示します。これは、SEQ に似ていますが、いくつかの重要な違いがあります。一つ目は、それぞれの子スレッドは自分自身の visited 配列を持ちます。これは、１行目に示すように、親から渡されます。それは全て、[-1,-1] に初期化されなくてはいけません。７行目はこの配列へのポインタをスレッドごとの変数 myvisited に格納して、ヘルパ関数がアクセスできるようにします。同様に、ローカルの訪問インデックスへのポインタも格納します。２つ目は、親はそれぞれの子のために、最初のセルを訪問します。子はそれを８行目で得ます。３つ目は、ある子が他の子によって訪問されたセルを見つけた時に迷路は解けます。maze_try_visit_cell() がこれを検出したら、それは、迷路の構造体に ->done フィールドを設定します。４つ目、それぞれの子は、そのために、定期的に ->done フィールドをチェックする必要があります。これは、１３，１８，そして２３行目にあります。ACCESS_ONCE()
プリミティブは、連続するロードを結合させたり、値を再ロードする可能性のある全てのコンパイラ最適化を無効にしなくてはいけません。C++1x の volatile relaxed load で十分です。最後に、maze_find_any_next_cell() 関数はセルを訪問済みとするためには compare-and-swap を使わなくてはいけません。しかし、スレッド生成とジョインが提供する以上のオーダリングの制限は必要ありません。
maze_find_any_next_cell()の疑似コードは、図６．３４に示したものと同じです。しかし、maze_try_visit_cell() の疑似コードは違います。これを図６．３８に示します。８と９行目でセルが接続されているかを見ます。そうでないなら失敗を返します。１１から１８行目にあるループは新しいセルを訪問済みにしようとします。１３行目でそれが既に訪問済みかを見て、そうなら、１６行目で失敗を返します。なおその前に、１４行目で他のスレッドに出会ったかを見ます。そうなら、１５行目で解が見つかったことを示します。１９行目で新しいセルを設定し、２０と２１行目でこのスレッドの訪問済み配列を更新し、２２行目で成功を返します。
性能テストは驚くべき異常を見つけました。これを図６．３９に示します。PARTの解決時間(１７ミリ秒)は、SEQのそれ(７９ミリ秒)に比べて４倍以上速いのです。たった２つのスレッドで走らせているにもかかわらず。次の節はこの謎を解明します。
６．５．３ 性能比較１
異常な性能への最初の応答は、バグを調べることです。アルゴリズムは実際に有効な解を見つけていますが、図６．３９のCDFのプロットは独立したデータ点を前提とします。これは良くありません。性能テストはランダムに迷路を生成し、次に全てのソルバをその迷路に対して走らせます。なので、CDFを、それぞれの生成された迷路ごとに解法にかかった時間の比率でプロットするのは意味があります。これを図６．４０に示します。これで、CDFのオーバラップが大いに減りました。
訳注。よくわからない。
このプロットを見ると、ある迷路に対しては、PARTはSEQよりも４０倍以上速いことがわかります。それに対し、PWQはSEQよりもほぼ２倍以上速いことはけっしてありません。２スレッドで４０倍のスピードアップは説明が必要です。結局、これはただのなんちゃって並列ではありません。それなら、分割可能性は、スレッドを追加することで全体の計算コストが増えないというだけです。そうでなくこれは、屈辱的に並列です。スレッドを追加することで全体の計算コストが大いに減ります。その結果、アルゴリズム的な線形を超える大きなスピードアップが得られます。
さらに調べると、PARTは、時には迷路のセルの２%以下しか訪れないことがわかります。SEQとPWQは、ほぼ９％以下を訪れることはけっしてありません。この違いの理由を図６．４１に示します。もし、解を左上からトラバースするスレッドが丸に達したら、他のスレッドは迷路の右上の部分にはけっして行けません。同様に、他のスレッドが四角に達したら、最初のスレッドは迷路の左下の部分には行けません。なので、PARTは解とならないパスのセルのうち小さい部分しか訪れない傾向にあります。要するに、線形を超えるスピードアップは、スレッドがお互いの道をふさぎ合うためでした。これは、何十年にもわたる並列プログラミングの経験とは極めて異なります。そこでは、研究者たちはスレッドがお互いの道をふさがないように努力してきました。
図６．４２は、全ての３つの方法について、訪問されたセルと解決に要した時間との間に強い相関があることを確認します。PART の散布図の傾きは SEQ のそれよりも小さいです。これは、PART のスレッドの対は迷路の指定された部分を、SEQ の単一スレッドが行うよりも速く訪れることを示します。PART の散布図はさらに、小さい訪問パーセントにかたよっています。これは、PARTが全体に少ししか作業をしないのを確認します。なので、屈辱的並列が見られます。
PWQが訪れるセルの割合は、SEQのそれと似ています。また、PWQが解決に要した時間はPARTのそれよりも大きいです。それは、訪問割合が同じ時にもです。図６．４３はこの理由を示します。そこでは、２つ以上のお隣を持つセルに赤い丸をつけてあります。そのようなセルはそれぞれ、PWQでは競合になります。一つのスレッドが入ることができ、２つのスレッドが出ることができるからです。それはこの章の初めのほうで述べたように性能を損ないます。それに対して、PARTにはそのような競合がありますが、ただ一度だけ、つまり、解が見つかった時です。もちろん、SEQはけっして競合しません。
PARTのスピートアップは印象的ですが、シーケンシャル最適化を無視することはできません。図６．４４は、-O3 つきでコンパイルされたSEQは、最適化されていない PWQの２倍ほど速く、最適化されていないPARTの性能に近づくことを示します。全ての３つのアルゴリズムを-O3 でコンパイルすると、図６．４０に示した結果と似たものに（それより速いですが）なります。ただ、PWQはSEQに比べてほとんど速くなりません。これは、アムダールの法則通りです。しかし、もしもゴールが、最適な性能を得ることではなく、最適化されていないSEQに比べて性能を倍にすることであるなら、コンパイラの最適化はとても魅力的です。
キャッシュアラインメントとパディングは、偽の共有を減らすことで性能をしばしば改善します。しかし、これらの迷路解決アルゴリズムでは、迷路セルの配列をアラインとパッドするのは、１０００かける１０００の迷路において性能を最高４２％だけ落とします。大きな迷路では、偽の共有を減らすことよりも、キャッシュの局所性の方が重要なのです。より小さな２０かける２０あるいは５０かける５０の迷路では、アラインとパッドは、PART で、最大４０％の性能向上を得られます。しかし、このような小さいサイズでは、SEQの方がそれでも性能が良いです。PARTがスレッド作成と終了のオーバヘッドを挽回するだけの十分な時間が無いためです。
要するに、分割された並列迷路ソルバは、アルゴリズム的な線形を超えるスピートアップの面白い例でした。もし、「アルゴリズム的な線形を超えるスピートアップ」が、認識論的に耳障りなら、次の節に進んで下さい。
６．５．４ 他のシーケンシャル迷路ソルバ
アルゴリズム的な線形を超えるスピードアップの存在は、並列性をコルーチンでシミュレートしたらどうかと思わせます。例えば、図６．３７の主の do-while ループのそれぞれのパスで、スレッドの間で手でコンテキストをスイッチするのです。このコンテキストは、変数 c と vi だけからなるので、コンテキストスイッチは直裁的です。同じ効果を得る方法はたくさんありますが、これは、コンテキストスイッチのオーバヘッドと訪問パーセントの間の良いトレードオフです。図６．４５でわかるように、このコルーチンアルゴリズム(COPART) はとても効率的です。一つのスレッドの性能は、二つのスレッドの PART の約３０％以内です。(maze_2seq.c)
６．５．５ 性能比較２
図６．４６と６．４７は、迷路の大きさを変えながら、二つのスレッドで動く PWQ と PART を、それぞれ SEQ あるいは COPART と比べたものです。90%-confidence エラーバーがついています。PARTは、１００かける１００以上の大きさの迷路で、SEQに対して線形を超えるスケーラビリティを示し、COPARTに対してやや優位なスケーラビリティを示します。PARTはほぼ２００かける２００の迷路の大きさで、COPARTに対して理論的なエネルギー効率の点からの均衡点をむかえます。高い周波数では、電力消費はほぼ周波数の二乗で増加することを考えると、２スレッドで１．４倍のスケーリングは、一つのスレッドが同じ解決速度で行うときと同じエネルギーを使います。それに対して、PWQは最適化がない場合を除いては、SEQとCOPARTに対して、貧弱なスケーラビリティしか示しません。図６．４６と６．４７は、-O3 を使って生成されました。
図６．４８は、COPART と比較したPWQとPARTの性能を示します。一つ以上のスレッドでPARTを動かした時、追加のスレッドは、開始セルと終了セルを結ぶ対角線にそって均等な間隔で開始されます。二つ以上のスレッドを使うPART実行が、早く終了するのを検出するために、単純化された link-state routing が使われました。（スレッドが開始点と終了点の両方につながった時に、解決が宣言されます。）PWQはとても性能が悪いです。しかし、PARTは２スレッドと、再び５スレッドにおいて、均衡点に達します。５スレッド以上ではほどほどのスピートアップを達成します。理論的なエネルギー効率の均衡点は、７と８スレッドにおいて 90% confidence interval 内にあります。２スレッドでのピークの理由は、（１）２スレッドの場合は終了の検出がそれほど複雑でないことと、（２）３番目以降のスレッドが有効な進捗をしている確率は低いという事実のためです。最初の２つのスレッドだけが、正解の線上で開始する保証があります。図６．４７の結果と比べた時にこの性能ががっかりさせる理由は、2.66GHz で動作する、より大きくてより古い Xeon (R) システムで使われているハードウエアがあまり緊密に統合されていないためです。
６．５．６ 将来の方向と結論
するべきことはたくさんあります。一つ目は、この節では、人間の迷路解決者が使う一つのテクニックを適用しただけです。他には、迷路の一部を除くために壁をつたうとか、以前にトラバースしたパスの場所を元に内部的な開始点を決めるなどがあります。二つ目は、開始点と終了点の異なる選択は異なるアルゴリズムを有利とするかもしれません。三つ目、PARTアルゴリズムの最初の二つのスレッドの配置は直裁的ですが、残りのスレッドの配置スキーマはいくらもあります。最適な配置はきっと開始点と終了点に依存するでしょう。四つ目、解決不可能な迷路とサイクルのある迷路の研究は面白い結果を生みそうです。五つ目、軽量の C++11 アトミック操作は性能を上げるかもしれません。六つ目、三次元迷路(あるいはもっと高次元の迷路)のスピードアップを比べるのは面白いでしょう。最後に、迷路に対して、屈辱的並列性は、コルーチンを使ったより効率的なシーケンシャル実装を示唆しました。屈辱的並列アルゴリズムは常により効率的なシーケンシャル実装につながるのでしょうか。それとも、コルーチンのコンテキストスイッチオーバヘッドがスピードアップを上回るような根本的に屈辱的な並列アルゴリズムがあるのでしょうか？
この節は迷路解法アルゴリズムの並列化をデモンストレーションし、解析しました。通常のワークキューを元とするアルゴリズムはコンパイラの最適化が無効な時だけ、うまくいきました。これは、高レベルあるいは高オーバヘッド言語を使って得られたこれまでの結果のいくらかは最適化の進歩によって無効になることを示唆します。
この節は、並列性にアプローチするのに、シーケンシャルアルゴリズムの派生物としてではなく、それを第一級の最適化テクニックとして行うことが、シーケンシャルアルゴリズムの改良にも道を開くということの明確な例を与えました。並列性を、設計時に高レベルで適用することは、研究の実り多い分野であると思われます。この節は、ほどほどにスケーラブルなものから始まって、屈辱的に並列なもの、そしてまた戻るというように、迷路を解く問題を扱いました。この経験が、並列性を、第一級の、設計時のアプリケーション全体の最適化テクニックとして扱うための研究の動機付けとなることを希望します。既存のプログラムに、事実が起きた後で追加される、最適とはとても言いがたいマイクロ最適化としてではなく。
６．６ 分割、並列、そして最適化
この章は、設計レベルで並列性を適用することで素晴らしい結果が得られることを示しましたが、最も大切なことをこの最後の節で言うならば、それでは十分ではないということです。迷路解決のような探索問題で、探索戦略の方が、並列設計よりもずっと重要なことを示しました。そうです。この特定の迷路の型に対しては、賢い並列性の適用はより優れた探索戦略の発見につながりました。しかしこの種類の幸運は探索戦略自身への明確な集中の代わりとはなりません。
２．２節で以前述べたように、並列性は、多数の潜在的な最適化の中の一つでしかありません。成功する設計は最も重要な最適化に焦点を当てる必要があります。私がどんなに主張しても、並列化は最適化である時もそうでない時もあります。
しかし、並列化が正しい最適化である多くの場合のために、次の章はその同期の働き馬である、ロックを取り上げます。
以上