３章 ハードウェアとそのくせ
ほとんどの人は、システムの間でメッセージを送るのは、単一システムの囲いの中で単純な計算をするよりは、ずっと高価であることを直感的に理解します。しかし、単一の共用メモリシステムの囲いの中で、スレッド同士が通信するのが、同様にとても高価であるかは、常に明らかであるとは言えません。なのでこの章は、共用メモリシステム内の同期と通信のコストを調べます。これらのわずかのページでは、共用メモリ並列ハードウェア設計の表面をひっかくくらいのことしかできません。より詳しく学びたい読者は、Hennessy and Patterson の古典的教科書 [HP95] の最新版から始めるのがよいでしょう。
クイッククイズ３．１： なぜ、並列プログラマが、ハードウェアの低レベルの性質をわざわざ学ばないといけないのですか？より高いレベルの抽象化に留まるほうが、簡単で、好ましく、より一般的でないですか？
３．１ 概要
計算機システムのスペックシートを注意深く読まないと、CPU 性能は、図３．１のような、整地されたトラック上の徒競走であると思うかもしれません。最も素早いものが、競争に勝つわけです。 図３．１が示す理想に近い、CPU バウンドなベンチマークはいくつかあるでしょうが、典型的なプログラムはレーストラックよりは、障害物競争にずっと似ています。これは、CPU の内部アーキテクチャが、ムーアの法則のおかげでこの数十年の間にドラマチックに変わったためです。以下の節でその変更点を述べます。
３．１．１ パイプラインされた CPU
１９８０年代初め、典型的なマイクロプロセッサは、１つの命令をフェッチして、それをデコードして、そして実行しました。典型的には、少なくても３クロックサイクルを使って、１つの命令を完了し、次の命令を処理しました。それに対して、１９９０年代後半から２０００年代初めのCPUは、多くの命令を同時に実行します。CPUの内部で命令のフローを制御するために、深い「パイプライン」を使います。これらの現代的なハードウェア機能は、図３．２が示すように、大いに性能を向上させることができます。 長いパイプラインを持つCPUで、完全な性能を得るには、プログラムの全体で、高度に予測可能な制御フローが必要です。主にタイトなループを実行するプログラムは、最適な制御フローを提供することができます。例えば、大きな配列やベクトル計算です。その場合、CPUはループの最後の分岐がほとんどすべての場合に行われることを正しく予測することができます。その結果、パイプラインは一杯に保たれ、CPUはフルスピードで実行することができます。 しかし、小さなループ数を持つループがたくさんあるプログラムではどうでしょう。あるいは、多くの異なる実オブジェクトを参照する多くの仮想オブジェクトを持つオブジェクト指向プログラムで、実オブジェクトのすべてが頻繁に呼ばれるメンバ関数の異なる実装を持っているとしたらどうでしょう。これらの場合、CPU がある分岐がどこに飛ぶのかを予測するのは困難あるいは不可能です。するとCPUは、分岐がどこに飛ぶのかわかるまで実行が進むのを待ってストールするか、あるいは推測するしかありません。なお、予測不可能な制御フローを持つプログラムに対しては、推測はしばしば外れます。推測の誤りはとても高価です。なぜならば、CPUは、誤った推測に基づいて投機的に実行されたすべての命令の結果を捨てないといけませんから。さらに、CPUがストールするにしても推測するにしても、パイプラインは空になり、再補充されなくてはいけませんから、ストールすることになり、図３．３に楽しく描かれるように劇的に性能が落ちます。 不幸にも、パイプラインフラッシュは、現代的CPUが走らなくてはいけない障害物競争の唯一の障害ではありません。次の節は、メモリ参照の障害を述べます。
３．１．２ メモリ参照
１９８０年代では、しばしば、マイクロプロセッサがメモリから値をロードする方が、命令を実行するよりも時間がかかりませんでした。２００６年には、マイクロプロセッサは、メモリをアクセスするのに必要な時間の間に、数百あるいは数千の命令を実行する能力がありました。この乖離は、ムーアの法則が、CPU性能を、メモリの性能を増すよりもずっと大きく増した事実が原因です。それは部分的には、メモリサイズが増した比率のせいです。例えば、典型的な１９７０年代のマイクロプロセッサは４KB （そうです。キロバイトです。メガバイトでないし、ギガバイトはとんでもないことです。）のメインメモリを持ち、シングルサイクルでアクセスしました。 脚注。これらのシングルサイクルは、１．６マイクロ秒以上必要だったと付け加えておくのが公平でしょう。 ２００８年においても、CPU設計者は、シングルサイクルアクセスの４KB メモリを構築することができます。数 GHz クロック周波数のシステムにおいてさえです。そして、実際そのようなメモリを構築することがしばしばあります。ただ、今ではそれは「レベル０キャッシュ」と呼ばれ、４KB よりずっと大きいです。 現代的マイクロプロセッサに見られる大きなキャッシュは、メモリアクセス遅延と戦うために多大なはたらきをすることができますが、これらのキャッシュは、うまくメモリ遅延を隠すためには高度に予測可能なデータアクセスパターンを必要とします。不幸にも、連結リストをたどるなどのよくある操作は、極めて予測不可能なメモリアクセスパターンを持ちます。結局、パターンが予測可能なら、私達ソフトウェア屋さんはポインタなんて面倒なものは使いませんよね？ なので、図３．４にあるように、メモリ参照はしばしば、現代的CPUにとって厳しい障害です。 これまで、私達は、あるCPUがシングルスレッドのコードを実行する間に起きる障害だけを考えてきました。マルチスレッディングはCPUにさらに障害を与えます。それは以下の節で。
３．１．３ アトミック操作
そのような障害の一つが、アトミック操作です。アトミック操作の概念そのものは、ある意味、CPUパイプラインの、一つの工程を一つづつ、というアセンブリライン操作と矛盾します。ハードウェア設計者の名誉のために言っておきますが、現代的なCPUは多くの極端に賢いトリックを使って、そのような操作が、実際には工程ごとに実行されているにもかかわらず、アトミックに見えるようにしています。しかし、そうであっても、あるアトミック操作が正しく完了することができるようにするために、パイプラインを遅延あるいはフラッシュしなくてはいけない場合があります。 図３．５は、この結果が性能に与える影響を示します。 不幸にも、アトミック操作は通常、データの単一の要素だけに適用されます。多くの並列アルゴリズムは、複数のデータ要素を更新する時にオーダリングの制限が維持されることを必要としますから、ほとんどのCPUはメモリバリアを提供しています。このメモリバリアはまた、性能を落とす障害としてはたらきます。これは次の節で。
クイッククイズ３．２ 複数のデータ要素へのアトミック操作ができるマシンとは、どんなタイプのものですか？
幸運なことに、CPU設計者はアトミック操作に大いに焦点を当ててきました。このため、２０１２年初めには、そのオーバヘッドはかなり（完全に無くなったわけではありませんが）削減されました。
３．１．４ メモリバリア
メモリバリアについては、１４．２節と、付録 C でより詳しく考察されます。まずは、以下の単純なロックベースのクリティカルセクションを考えましょう。 1 spin_lock(&mylock); 2 a = a + 1; 3 spin_unlock(&mylock); もしCPUがこれらの文を、この順序で実行するのを強制されなければ、その結果、変数“a”は、“mylock”の保護なしで加算されることがあります。それは明らかに、ロックを取る意味をなくします。そのような破壊的なリオーダリングを防ぐため、ロックプリミティブは明示的あるいは暗黙的なメモリバリアを含みます。これらのメモリバリアのそもそもの目的は、それがなければCPUが性能向上のために行うであろうリオーダリングを止めることですから、メモリバリアはほぼ常に、図３．６が示すように性能を落とします。 アトミック操作と同様に、CPU設計者はメモリバリアのオーバヘッドを減らすために努力を続けており、かなりの進歩が得られています。
３．１．５ キャッシュミス
もうひとつの、CPU性能への、マルチスレッディング障害は「キャッシュミス」です。前に述べたように、現代的なCPUは、高いメモリ遅延が引き起こす性能ペナルティを減らすために、大きなキャッシュを持ちます。しかし、このキャッシュは、CPUの間で頻繁に共有される変数にとっては、実際は非生産的です。これはなぜなら、あるCPUがその変数を更新しようとする時には、どれか他のCPUがそれを最近、更新した可能性が高いからです。その場合、その変数はその他のCPUのキャッシュにあり、このCPUのキャッシュにはありません。なので、高価なキャッシュミス（詳しくは、C.1 節を参照）を起こします。このようなキャッシュミスは、図３．７が示すように、CPU性能への大きな障害となります。
クイッククイズ３．３ ならば、CPU設計者は、キャッシュミスのオーバヘッドを大いに減らすことにも成功してきたのですね？
３．１．６ I/O 操作
キャッシュミスは、CPU から CPU への I/O 操作と考えることができます。そして、そのため、考えうる最も安価な I/O 操作の一つです。ネットワーキング、大容量記憶域、あるいは（それより悪い）人間が関与する I/O 操作は、これまでの節で述べた内部的な障害に比べてずっと大きな障害となります。これは、図３．８に示すとおりです。 これは、共用メモリ並列性と分散システムの間の違いの一つです。共用メモリ並列プログラムは通常は、キャッシュミス以上の障害を扱う必要はありません。一方、分散並列プログラムは、典型的にはより大きなネットワーク通信遅延を起こします。いずれの場合も、問題の遅延は、通信コストと考えられます。シーケンシャルプログラムでは存在しないコストです。なので、実行される実際の仕事に比べた、通信オーバヘッドの比率は、鍵となる設計パラメタです。並列ハードウェア設計の主なゴールは、目的とする性能とスケーラビリティのゴールを達成するために必要なだけ、この比率を減らすことです。その一方で、６章で述べるように、並列ソフトウェア設計の主なゴールは、通信やキャッシュミスのような高価な操作の頻度を下げることです。 もちろん、ある操作が障害であると言うことと、その操作が大きな障害であると示すことは、とても違います。以下の節で、この違いを説明します。
３．２ オーバヘッド
この節は、以前の節で一覧にした性能への障害の実際のオーバヘッドを示します。しかし、まずは、ハードウェアシステムアーキテクチャの大まかなビューを得る必要があります。それについては次の節で。
３．２．１ ハードウェアシステムアーキテクチャ 図３．９は、８コア計算機システムの大まかな図式です。それぞれのダイはCPUコアの対を持ち、コアには自身のキャッシュと、CPU対が互いに通信するためのインターコネクトがあります。図の中央のシステムインターコネクトは、４つのダイが通信できるようにするとともに、それらをメインメモリに接続します。 データは、このシステム内を、「キャッシュライン」を単位として移動します。それは、２の累乗の固定長のアラインされたメモリブロックで、普通は３２から２５６バイト長です。CPUがある変数をメモリから自分のレジスタの１つにロードするとき、まず、その変数を含むキャッシュラインを自分のキャッシュにロードする必要があります。同様に、CPUが自分のレジスタの１つからメモリに値を格納するとき、その変数を含むキャッシュラインを自分のキャッシュにロードする必要があります。さらに、そのキャッシュラインのコピーを、他のCPUが誰も持っていないことを保証しなくてはいけません。 例えば、CPU０が、変数にコンペアアンドスワップ（CAS)操作を行うとして、その変数のキャッシュラインがCPU７のキャッシュに存在する場合、以下のかなり単純化されたイベントのシーケンスが起きる必要があります。
１ CPU０は、自分のローカルキャッシュを調べるが、キャッシュラインが見つからない。
２ 要求は、CPU０と１のインターコネクトに転送される。そして、CPU１のローカルキャッシュを調べるが、キャッシュラインが見つからない。
３ 要求は、システムインターコネクトに転送される。そして、他の３つのダイを調べる。キャッシュラインは、CPU６と７を含むダイが持っていることがわかる。
４ 要求は、CPU６と７のインターコネクトに転送される。そして、両方のCPUのキャッシュを調べて、CPU７のキャッシュに値を見つける。
５ CPU７は、キャッシュラインを自分のインターコネクトに転送する。さらに、自分のキャッシュからそのキャッシュラインをフラッシュする。
６ CPU６と７のインターコネクトは、キャッシュラインをシステムインターコネクトに転送する。
７ システムインターコネクトは、そのキャッシュラインを、CPU０と１のインターコネクトに転送する。 ８ CPU０と１のインターコネクトは、そのキャッシュラインを、CPU０のキャッシュに転送する。
９ CPU０は、これで、自分のキャッシュの値に対して、CAS 操作を実行できる。
クイッククイズ３．４ これが、単純化されたイベントのシーケンスですって？これがさらに複雑になるなんて、どうしたら可能なのですか？
クイッククイズ３．５ なぜ、CPU７のキャッシュから、そのキャッシュラインをフラッシュする必要がありますか？
３．２．２ 操作コスト
表３．１に、並列プログラムで重要ないくつかの一般的な操作のオーバヘッドを示しました。このシステムのクロック周期は、ほぼ、 0.6ns です。現代のマイクロプロセッサでは、クロック周期ごとに複数の命令をリタイアできるというのも珍しくありませんが、操作は、３つ目の、"Ratio"、比率と書いてある列に、完全なクロック周期で正規化されています。この表で最初に注意すべきは、比率の多くにある巨大な値です。
最良のCAS操作は，ほぼ４０ナノ秒消費します。クロック周期の６０倍以上です。ここで、「最良の場合」とは、ある変数に CAS 操作を今やっているCPUが、その変数に操作した最後のCPUと同じだということです。なので、対応するキャッシュラインは既にそのCPUのキャッシュに保持されています。同様に、最小のロック操作（ロック確保とそれに続くロック解放からなる「ラウンドトリップ」対です。）は６０ナノ秒以上、１００クロック周期以上を消費します。同じく、「最良の場合」とは、ロックを表すデータ構造が、ロックを確保し解放するCPUに属するキャッシュに既に存在することを意味します。ロック操作は、CASよりより高価です。なせなら、それはロックデータ構造に２つのアトミック操作を必要とするからです。
キャッシュをミスする操作はほぼ１４０ナノ秒、２００クロック周期以上を消費します。このキャッシュミス測定に使ったコードは２つのＣＰＵ間でキャッシュラインをあちこち渡しあいます。このキャッシュミスはメモリから満足されるのではなく、相手のＣＰＵのキャッシュからです。CAS操作は、変数の古い値を見るとともに、新しい値を格納する必要がありますから、３００ナノ秒以上、５００クロック周期以上を消費します。これを少し考えてください。1つのCAS操作をするのに必要な時間の間に、ＣＰＵは５００以上の普通の命令を実行できるのです。これは、細かい粒度のロックの限界だけでなく、細かい粒度のグローバルな合意に基づく全ての同期機構の限界も明らかに示しているといえます。
クイッククイズ３．６： 確かに、ハードウェア設計者は、この状況を改善するように、説得されるべきです！なぜ彼らは、1命令の操作がこんなひどい性能だというのに満足してきたのですか？
I/O 操作はさらにもっと高価です。InfiniBand や、いくつかのプロプライエタリなインターコネクトのような、高性能の(そして高価な！)通信ファブリックは、ざっと３マイクロ秒の遅延を持ちます。その時間の間には、５０００命令が実行できます。標準ベースの通信ネットワークは、しばしばなんらかのプロトコル処理が必要です。それはさらに遅延を増します。もちろん、地理的距離も遅延を増します。理論的に、光速で世界一周する遅延は、ざっと１３０ミリ秒、２億クロック周期以上になります。
クイッククイズ３．７： これらの数字はばかげて大きいです！一体どうやって想像したらいいでしょう？
つまり、ハードウェアとソフトウェア技術者は実際に同じ側に立って、物理法則の範囲で最善の力を尽くして、計算機をより速くするために戦っています。それは、図３．１０に面白く描かれたようなものです。そこでは、私たちのデータストリームが光速を越えようとがんばっています。次の節は、ハードウェア技術者ができる(あるいはできないかも)だろういくつかの事を議論します。この戦いに、ソフトウェアができる事は、この本の残りの章で説明します。
３．３ ハードウェアフリーランチ？
この何年かに渡って、並列性がこれほどの関心を集めている主な原因は、ムーアの法則によるシングルスレッド性能向上（あるいは、「フリーランチ」 [Sut08]）が、１０ページの図２．１が示すとおり、終わりを告げたためです。この節は、ハードウェア設計者がある種の「フリーランチ」を取り戻すことができるかもしれないいくつかの方法を簡単にサーベイします。
しかし、これまでの節は、並列性を追求するときの重要なハードウェア上の障害をいくつか述べてきました。ハードウェア設計者が直面する１つの厳しい物理的限界は、光速の有限性です。２９ページの図３．９で示したとおり、光は、1.8 GHz クロック周期の間に、真空をたった８センチメートルくらいしか移動できません。この距離は、 5 GHz クロックの場合、ほぼ３センチメートルに落ちます。これらの距離は、現代的な計算機システムの大きさと比べると、比較的小さいです。 事態をさらに悪くすることに、シリコン中の電子は、真空中の光よりも３から３０倍も遅く移動します。そして、一般的な、クロックトロジック構成要素は、さらに遅く動作します。例えば、メモリ参照は、その要求がシステムの残りの部分に渡される前に、ローカルキャッシュの参照が完了するのを待たないといけません。 訳注。意味が通じない。AND 回路とバスドライバの話をしているのだよね。 さらに、電子信号をあるシリコンダイから別のダイに伝えるためには、比較的低速度で高パワーのドライバが必要です。それは例えば、CPUとメインメモリの通信に使われます。
クイッククイズ３．８ でも、個々の電子は、導体中であってもまるでそんなに速くは動きません！！！半導体で見られる、低電圧下の導体中の電子のドリフト速度は、たった、秒速１ミリメートルのオーダーです。どういうこと？？？
それでも、事態を改善するかもしれないいくつかの技術（ハードウェアとソフトウェアの両方）があります。
１ ３次元統合
２ 新素材とプロセス
３ 電子に代わって光を使う
４ 専用アクセラレータ
５ 既存の並列ソフトウェア 以下の節で、これらを一つづつ紹介します。
３．３．１ ３次元統合
３次元統合（3DI）は、とても薄いシリコンダイを垂直に重ねて貼り合わせるものです。この方法は潜在的な利益をもたらしますが、同時に重大な製造上の挑戦も与えます [Kni08]。
たぶん、３DI の最も重要な利益は、図３．１１に示すような、システム内のパス長の減少です。１つの３センチメートルのダイが、４枚の１．５センチメートルのダイの重ね合わせに代わり、理論的には、システム内の最大パスを半分にします。それぞれの層はとても薄いことに注意下さい。さらに、設計と配置に適切な注意を払えば、長い水平の電子的接続（それは低速で、パワーをくいます）を、より速く、電源効率の良い短い垂直の電子的接続に代えることができます。 しかし、多レベルのクロックトロジックが原因の遅延は、３次元統合でも減ることはありません。また、３次元統合が本番で使えるようになるためには、製造、テスト、電源供給、そして、熱拡散の深刻な問題が、解決されなくてはいけません。有望ではありますが。熱拡散問題は、ダイアモンドをベースとする半導体を使って解決できるかもしれません。それは、熱に対して良好な伝導体で、電子的には絶縁体です。とは言え、巨大な単一のダイアモンド結晶を育てるのはいまだ難しいですし、それをスライスしてウェファーにするのはさらに困難です。また、これらの技術のどれかが、人々がこれまでなじんできた指数的増加を提供することができるとは思えません。とは言え、それは、最近 Jim Gray が言っていた、「smoking hairy golf balls」[Gra02] に向けた必要なステップなのかもしれません。
訳注。未来のスーパーサーバ
３．３．２ 新素材とプロセス
聞くところによると、スティーヴン・ホーキングは半導体製造者は２つの基本的問題を持つと主張したそうです。（１）有限な光速と、（２）物質の原子的性質です [Gar07]。半導体製造者はこれらの限界に近づいているのかもしれません。しかし、これらの基本的限界を回避することに焦点を当てた研究と開発は、それでも、いくつか行われています。
物質の原子的性質への１つの回避策は、「high-K dielectric」物質と呼ばれます。それは、極小デバイスの電子的性質を、より大きなデバイスで真似することができるようにします。これらの物質は、いくつかの厳しい製造上の挑戦を課します。それでも、フロンティアを少し先に伸ばす役に立つかもしれません。もうひとつの、より奇妙な回避策は、単一の電子に複数のビットを格納します。これは、電子がいくつかのエネルギーレベルに存在できる事実を元にします。この特別のアプローチが本番の半導体デバイスで安定して動作するようにできるのかは未だ不明です。 もうひとつの提案された回避策は、「quantum dot」アプローチで、ずっと小さなデバイスサイズを可能とします。しかし、これはまだ研究段階です。
３．３．３ 電子に代わって光を使う
光の速度は厳格な限界となるでしょうが、半導体デバイスは、光速でなくて、電子の速度で限界付けられているのは事実です。半導体物質中の電子は、真空中の光に比べて、３％から３０％の速度で移動するからです。シリコンデバイスに、銅のコネクションを使うのは、電子の速度を増す一つの方法です。そして、実際の光速により近づくためのさらなる進歩は十分にありえます。また、チップの中とチップ間のインターコネクトに、小さな光ファイバーを使う実験がいくつかありました。これは、ガラス中の光速は、真空中の光速の６０％以上であるという事実に基づきます。そのような光ファイバーへの１つの問題は、電子から光へ、そしてその逆の変換効率の悪さです。これは電源消費と熱拡散問題を起こします。 とは言え、物理学分野でのなんらかの基本的進歩がない限り、データフロー速度の指数的増加は、真空中の実際の光速によって、いずれ、厳しく制限されることでしょう。
３．３．４ 専用アクセラレータ
特別な問題を解いている汎用CPUは、しばしば、多くの時間とエネルギーを、目的の問題にはあまり関係ない作業をするために費やしていることがあります。例えば、２つのベクトルの内積を計算するのに、汎用CPUは普通、ループカウンタを持つループ（アンロールされているかもしれません）を使います。命令をデコードして、ループカウンタを加算して、このカウンタを判定して、そしてループの先頭に戻って分岐するというのは、ある意味、無駄な努力です。真のゴールは、そうでなくて、２つのベクトルの対応する要素を掛け算することです。なので、ベクトルを掛け算するために専用に設計された特別なハードウェア部品を使えば、仕事はより速くでき、エネルギー消費も少なくて済むかもしれません。 これが、実際に、多くのコモディティマイクロプロセッサに存在するベクトル命令の動機です。それらの命令は複数のデータアイテムに同時に動作しますから、内積を計算するのに、より少ない命令デコードとループオーバヘッドで済むでしょう。
同様に、専用のハードウェアを使えば、暗号と複号、圧縮と伸張、エンコードとデコードそしてそれ以外の多くの仕事が、より効率的に行えます。不幸にも、この効率はタダでは来ません。この特別のハードウェアを含む計算機システムはより多くのトランジスタを含み、それは使われていない時でもある程度の電力を消費します。この特別のハードウェアを活用するために、ソフトウェアは変更が必要です。また、この特別のハードウェアは、十分に一般的に利用可能でないと、高いハードウェア設計コストを十分な数のユーザに分散して、その特別のハードウェアを低価格にすることができません。部分的にこれらのたぐいの経済的問題の結果、特別のハードウェアは、これまで、いくつかの限られたアプリケーション領域にしか現れませんでした。それは、グラフィック処理（GPU)、ベクトル処理（MMX, SSE, そして VMX 命令）、そして、それらよりは少ないですが、暗号化の領域です。 サーバーとPC 領域と違って、スマートフォンは広い種類のハードウェアアクセラレータをこれまで使ってきました。これらのハードウェアアクセラレータはしばしば、メディアデコーディングに使われます。ハイエンド MP3 プレーヤが音楽を数分に渡って再生でき、CPU はその間完全に電源オフできるくらいです。これらのアクセラレータの目的は、エネルギー効率を高めて、電池寿命を伸ばすことです。専用目的ハードウェアはしばしば、汎用CPUよりもより効率的に計算ができます。これは２．２．３節で述べた基準のもうひとつの例です。汎用性はほとんど決してタダではない。 しかし、ムーアの法則によるシングルスレッド性能の増加の終焉を考えると、これからはより多くの種類の特別目的ハードウェアが現れるだろうと予想するのが安全と思われます。
３．３．５ 既存の並列ソフトウエア
マルチコアCPUは、計算機産業を驚かせたようですが、共用メモリ並列計算機システムは１／４世紀以上に渡って商用利用可能であるというのは事実です。これは、重要な並列ソフトウェアが現れるには十分以上な時間であり、実際そうなりました。並列オペレーティングシステムはとても一般的であり、並列スレッドライブラリ、並列リレーショナルデータベース管理システムや並列数値計算ソフトウェアも同様です。既存の並列ソフトウェアを使うことで、私達は、直面するかもしれない並列ソフトウェア危機を解決するために多くのことができるでしょう。 たぶん、最も一般的な例は、並列リレーショナルデータベース管理システムです。しばしば、高レベルのスクリプト言語で書かれたシングルスレッドプログラムが、中心的なリレーショナルデータベースを並列にアクセスするのはめずらしくありません。結果となる高度に並列なシステムでは、データベースだけが、実際に直接並列性を扱う必要があります。うまくいけば、とても素晴らしいトリックです！
３．４ ソフトウェア設計への影響
表３．１の値の比率は致命的に重要です。それは、ある並列アプリケーションの効率を制限するからです。これを考えるために、その並列アプリケーションが、CAS操作をスレッド間で通信するために使うとしましょう。これらのCAS操作は典型的にはキャッシュミスを起こします。つまり、スレッドが自分自身でなくて他のスレッドと主に通信するとすればです。さらに、それぞれのCAS通信操作に対応する仕事の単位は 300ns だとします。それは、いくつかの浮動小数超越関数を計算するのに十分です。すると、実行時間のおよそ半分は、CAS通信操作に使われるということです！これはつまり、そのような並列プログラムを実行する２ＣＰＵシステムは、単一ＣＰＵでシーケンシャルな実装を走らせるのと速さは変わらないということです。 この状況は、分散システムの場合にはさらに悪化します。そこでは、１つの通信操作の遅延が、何千、ときには何百万の浮動小数演算の長さになります。これは、通信操作がとてもまれで、とても大量の処理を引き起こすべきであるということの重要性を明らかにします。
クイッククイズ３．９： 分散システムの通信が、そんなにおそろしく高価なら、なんでそんなものを使う人がいるのですか？
教訓はとても明らかです。並列アルゴリズムは、ほとんど独立したスレッドで走るように明示的に設計されなくてはいけません。スレッドの通信（アトミック操作、ロックあるいは明示的なメッセージ、何にせよ）が少なければ少ないほど、アプリケーションの性能とスケーラビリティは良くなります。つまり、素晴らしい並列性能とスケーラビリティを得るためには、なんちゃって並列アルゴリズムと実装を求めることを意味します。それは、注意深くデータ構造とアルゴリズムを選ぶことで実現できるかもしれませんし、既存の並列アプリケーションと環境を使うのかもしれませんし、あるいは、問題をなんちゃって並列ソリューションが存在するものへと変換すればよいのかもしれません。
クイッククイズ３．１０： わかりました。私達は分散プログラミングのテクニックを共用メモリ並列プログラムに適用しないといけないのですね。ならば、いつもこの分散テクニックを使って、共用メモリは、やめにしたらどうですか？
さて、まとめです。
１ 良い知らせは、マルチコアシステムは低価格で容易に入手可能だということです。
２ もうひとつ、良い知らせは、多くの同期操作のオーバヘッドは、２０００年代初頭の並列システムと比べて、ずっと小さいことです。
３ 悪い知らせは、キャッシュミスのオーバヘッドはいまだに、特に巨大システムでは、高いということです。 この本の残りは、この悪い知らせに対処する方法を説明します。 特に、４章は並列プログラミングに使われる低レベルのツールを説明します。５章は、並列カウンティングの問題と解決策を調べます。そして６章は、性能とスケーラビリティを高める設計指針を議論します。
以上