以下は、perfbook の２章の kanda.motohiro@gmail.com による全訳です。perfbook の訳の他の部分は、親文書を参照。
２章 前書き
並列プログラミングは、ハッカーが挑戦できる最高に難しい領域の１つだという評判を得てきました。論文や教科書は、デッドロック、ライブロック、競合条件、非決定性、スケーリングに関するアムダールの法則の限界、それに、長すぎるリアルタイム遅延の害毒について警告しています。そして、これらの害毒は全く本当のことなのです。私達著者は、それらと対決する数えきれない年月に渡る経験を積み重ね、心に傷を負い、髪は灰色に、あるいは抜けていきました。
しかし、初めて出てきた時は使うのが難しい新技術も、必ず、時と共により簡単になっていきます。例えば、かつては貴重であった、車を運転する能力は、今では多くの国で一般的となっています。このドラマチックな変化は２つの理由から起きました。（１）車はより安く、簡単に手に入るようになりました。そこで、より多くの人々が運転を学ぶ機会が増えました。そして、（２）オートマチックギア、オートマチックチョーク、オートマチックスターター、大きく改善した信頼性、そして多くのそれ以外の技術の進化により、車はより操作が簡単になりました。
同じことが、計算機を含む多くのそれ以外の技術についてもあてはまります。今では、プログラムするためにキーパンチ操作は必要ありません。２、３０年前は専門家のチームが必要だった作業も今ではプログラマーでない普通の人が自分の計算機でスプレッドシートを使って結果を出すことができます。最も顕著な例は、２０００年代初期から、訓練や教育を受けていない人々が今では一般的となったいろいろなソーシャルネットワーキングツールを使って簡単にできるようになった、ウェブサーフィングとコンテンツ作成でしょう。１９６８年頃には、そのようなコンテンツ作成は、遠大な研究プロジェクトであり [Eng68]、当時は、「UFO がホワイトハウスの芝生に着陸するようなもの」 [Gri00] と思われていました。
なので、並列プログラミングが現在多くの人にとって難しく感じられることが、将来にわたっても同じであるだろうと主張する人は、いろいろな領域での努力と、何世紀にもわたって現れてきた反例をよく見て、自分の主張を証明する義務があります。
２．１ 歴史的な並列プログラミングの難しさ
タイトルでわかるように、この本は異なるアプローチをとります。並列プログラミングの難しさに文句を言うより、なぜ、並列プログラミングが難しいかその理由を調べます。そして、読者がそれらの困難を克服できるよう、助けようとします。後で説明しますが、これらの困難は、いくつかのカテゴリーに分けることができます。例えば、
１． 歴史的に、並列システムは高コストで、ある場所は限られていました。
２． 典型的な研究者も実務家も並列システムの経験が少なかった。
３． パブリックにアクセス可能な並列コードは少なかった。
４． 並列プログラミングについて、広く理解されている技術規範がありませんでした。
５． 行う処理に比較して、通信オーバーヘッドが大きかった。これは、密結合共用メモリ計算機においてもそうでした。
これらの歴史的困難の多くは、今や、克服されようとしています。まず、最初の1つとして、この数十年に渡って、ムーアの法則のおかげで、並列システムのコストは、家何軒分から、自転車の何分の一かにまで下落しました。マルチコアＣＰＵの利点を主張する論文は、早くも1996年に公開されました [ONH+96]。IBMは、2000年に、自社のハイエンド POWERファミリーに、同時実行マルチスレッディングを導入し、2001年には、マルチコアを導入しました。インテルは、2000年11月に、自社のコモディティー Pentium ラインにハイパースレッディングを導入し、AMDとインテルの両社は2005年にデュアルコアＣＰＵを導入しました。Sunは、2005年末に、マルチコアかつ、マルチスレッドの Niagara で続きました。実際、2008年には、シングルＣＰＵのデスクトップシステムを見つけるのは困難になってきました。シングルコアＣＰＵは、ネットブックや、組み込みデバイスに追いやられていきました。2012年には、スマートフォンさえも、複数ＣＰＵを活用しだしています。
2つめとして、低コストで容易に入手可能なマルチコアシステムの到来は、かつては稀であった並列プログラミングの経験が、今やほとんどすべての研究者と実務家に可能だということを意味します。実際、並列システムは今では生徒やホビイストの予算の範囲にあります。このため、並列システムのまわりで、発明やイノベーションのレベルが大いに増えることが期待されます。そして、そのような一般化が続くうちに、かつては、寄り付くことのできないほど高価な並列プログラミングのフィールドが、ずっと親しみやすく、普通のものになることが期待されます。
3つめとして、20世紀には、高度な並列ソフトウエアの巨大システムは、ほとんど常に、しっかり保護されたプロプライエタリな秘密でした。それに比べてありがたいことに21世紀は多くのオープンソース（ということはパブリックに入手可能な）並列ソフトウエアプロジェクトがあらわれました。それには、Linuxカーネル [Tor03c] 、データベースシステム [Pos08, MS08]、そして、メッセージパッシングシステム [The08, UoC08] があります。この本は主に、Linuxカーネルを扱いますが、ユーザーレベルのアプリケーションにも適用できる多くの題材を提供する予定です。
4つめに、1980と1990年代の大規模並列プログラミングプロジェクトのほとんどがプロプライエタリプロジェクトであったにもかかわらず、これらのプロジェクトはコミュニティーの種をまき、その中心には製品品質の並列コードを開発するのに必要な技術規範を理解した開発者がいました。この本の主な目的は、この技術規範を提供することです。
不幸にも、5つ目の困難、つまり処理に比較した通信コストの高さは、今もなお、強力です。この困難は、新しい世紀において、より高い関心をひいていますが、スティーヴン・ホーキングによれば、有限の光の速度と、物質の原子的性質により、この分野での進歩は限界があります [Gar07, Moo03]。幸い、この困難は1980年代後半から明らかだったので、前記技術規範は、それを扱うための現実的で効率の良い戦略を進化させてきました。さらに、ハードウエア設計者はこの問題により気づいてきたので、3．3節で述べるように、将来のハードウエアは並列ソフトウエアに対してより親切になっているかもしれません。
クイッククイズ２．１：
しっかりしてください!!!並列プログラミングは、何十年にわたって、とても難しいものだと知られてきました。あなたは、それほど難しくはないとほのめかしているようです。一体どういうつもりです？
しかし、並列プログラミングは、一般的に宣伝されているほどは難しくないかもしれないとしても、普通は、シーケンシャルプログラミングより多くの仕事があります。
クイッククイズ２．２：
並列プログラミングが、シーケンシャルプログラミングと同じくらい易しいって、ありえますか？
なので、並列プログラミングの代替案を考えるのは意味のあることです。ただ、並列プログラミングのゴールを理解せずに並列プログラミングの代替案を合理的に考えることは不可能です。次の節は、その話です。
２．２ 並列プログラミングのゴール
並列プログラミングの３つの主なゴール（シーケンシャルプログラミングのそれに加えて）は、以下です。
１ 性能
２ 生産性
３ 一般性
クイッククイズ２．３：
うーん？？？正確さ、保守性、堅牢さ、などは？
クイッククイズ２．４：
そして、正確さ、保守性、堅牢さが一覧に入らないなら、生産性と一般性が入っているのはなぜですか？
クイッククイズ２．５：
並列プログラムは、シーケンシャルプログラムに比べて、正しいことを証明するのがずっと難しいはずですよね。もう一度うかがいますが、正確さは、本当に一覧に入らないのですか？
クイッククイズ２．６：
単に楽しむこと、というのは？
以下の節で、これらのゴールを１つづつ詳しく説明します。
２．２．１ 性能
性能は、ほとんどの並列プログラミング努力の背後にある主なゴールです。結局、性能が問題でないなら、好きにしてかまいません。シーケンシャルなコードを書いて、幸せでしょう？ずっと簡単で、素早くできるはずです。
クイッククイズ２．７：
並列プログラミングが、性能以外のものをめざす場合というのはありますか？
なお、「性能」とはここでとても広く解釈されます。それは、スケーラビリティ（CPU ごとの性能）と、効率性（例えば、ワットあたりの性能）が含まれます。
しかし、性能の焦点は、ハードウェアから並列ソフトウエアにシフトしてきました。この焦点の変化は、ムーアの法則がトランジスタの密度の増加をもたらし続ける一方、伝統的なシングルスレッドの性能の増加をもたらすのをやめてしまったのが原因です。これは、図２．１でわかります。
脚注
このプロットは、理論的にクロックあたり１つ以上の命令をリタイアする能力のある新しいCPUに対してはクロック周波数を示します。そして、最も単純な命令を実行するのにも複数クロックを必要とする古いCPUに対してはMIPS（百万命令／秒。通常、古い Dhrystone ベンチマークから）を示します。この２つの測定対象を変えた理由は、新しいCPUがクロックあたり複数の命令をリタイアする能力は、典型的には、メモリシステム性能によって制限されるからです。さらに、古いCPUに対して一般的に使われたベンチマークはもはや時代遅れですが、そうかといって、古いCPUを持つシステムに対してより新しいベンチマークを実行するのは困難です。一つには、その古いCPUの動作する実物を探すのが難しいからです。
シングルスレッドのコードを書いて、１年か２年、CPUがキャッチアップするのを待つだけというのは、もう選択肢ではありません。現在、すべての主要製造者が、マルチスレッド、マルチコアに向かっている最近の傾向からして、自分のシステムの完全な性能を求める者にとっては、並列性が進むべき道です。
そうであっても、最初のゴールは性能であって、スケーラビリティではありません。特に、線形のスケーラビリティを得る最も簡単な方法は、それぞれのCPU性能を落とすことだとすれば、なおさらです [Tor01]。
４CPUのシステムがあったとして、次のどちらがいいですか？単一CPUで１００トランザクション／秒をこなすけど全くスケールしないプログラムですか。単一CPUで１０トランザクション／秒をこなして、完全にスケールするプログラムですか。最初の方が良さそうですが、あなたが３２CPUシステムを所有することになったら、返事は変わるかもしれません。
しかし、あなたがたくさんのCPUを持っていることが、それを全部使わなくてはいけない理由にはなりません。特に、最近は、マルチCPUシステムが安くなってきましたし。理解すべき鍵となる点は、並列プログラミングは、主として、性能最適化であり、ということは、いくつもある最適化のうちの１つの潜在的改善策であるということです。もしあなたのプログラムが今書かれたままで十分に速いなら、最適化する理由はありません。並列化によっても、たくさんある潜在的シーケンシャル最適化のいくつかを適用するにしても。
脚注
もちろんあなたがホビイストで、あなたの主な興味が並列ソフトウェアを書くことならば、あなたがお好きなソフトウェアをなんでもかんでも並列化することの十分な理由になります。
同様に、あなたが、シーケンシャルプログラムに、並列化を適用して最適化しようとしているならば、あなたは並列アルゴリズムと、最良のシーケンシャルアルゴリズムを比べる必要があります。これは少し注意する必要があるかもしれません。あまりに多くの論文が、並列アルゴリズムの分析をするときに、シーケンシャルなケースを無視しているからです。
２．２．２ 生産性
クイッククイズ２．８：
技術的でない問題についてなぜこんなにおしゃべりするんです？？？それに、技術的でない問題の中でも、すべての事の生産性？興味ないです。
この数十年、生産性はますます重要になってきました。これを考えるために、初期の計算機の値段は、何千万ドルもしたことを思い出して下さい。そのころ技術者の給料はせいぜい、１年で２，３千ドルでした。１０人の技術者のチームをそのようなマシンに割り当てて、その性能が、たった１０％でも上がるなら、その人達の給料を何倍も支払うことが出来ました。
そのようなマシンの１つが、 CSIRAC です。最古の、現存するプログラム格納式計算機です [Mus04, Mel06]。それは、１９４９年に稼働しました。このマシンは、トランジスタ時代の前に作られたので、２０００本の真空管でできていました。クロックは 1kHz で、 30kW の電力を使い、３トン以上ありました。このマシンがたった、７６８ワードのRAMしか持たなかったことを考えると、現在の大規模ソフトウエアプロジェクトをしばしば害する生産性の問題には苦しまなかったと言ってよいでしょう
今ではこれほど小さな計算能力のマシンを買うのはとても難しいでしょう。たぶん、最も近い同等品は、尊敬すべき Z80 [Wik08] に代表される８ビット組み込みマイクロプロセッサでしょう。しかし、古い Z80 でも、CSIRAC より１０００倍以上速いCPUクロック周波数を持っていました。Z80 CPUは８５００トランジスタを持っており、２００８年時点で、１０００ユニット単位の場合、１個２米国ドル以下で買えます。CSIRAC とは大いに違うことは、Z80 ではソフトウエア開発コストが、何よりも重要だということです。
CSIRAC と Z80は、長期間のトレンドの両極端です。これは、図２．２でわかります。この図はダイあたりの計算能力の近似値をこの３０年にわたってプロットしたものです。一貫して、４桁の増加を示しています。２００３年に、クロック周期の壁が訪れたのにもかかわらず、マルチコアCPUの到来によって、この増加が衰えることなく継続しているのに注意下さい。
ハードウェアコストの急速な減少の、回避できない結果の１つは、ソフトウエア生産性がより重要になってきたということです。ハードウエアを効率よく使うだけではもう十分ではありません。今では、ソフトウエア開発者をとても効率的に使うことも重要です。この傾向は、シーケンシャルハードウェアについて今までもずっとありましたが、並列ハードウェアはごく最近、低コストのコモディティになってきました。なので、並列ソフトウエアを作るときに高生産性が致命的に重要になったのはごく最近のことなのです。
クイッククイズ２．９：
並列システムがこんなに安くなってきたことを思うと、それをプログラムするために人々にお金を払うのに意味があるのでしょうか？
もしかすると、ある時は、並列ソフトウエアの唯一の目的は性能だったかもしれません。しかし、今は、生産性がスポットライトを浴び始めています。
２．２．３ 一般性
並列ソフトウエアを開発する高いコストを正当化する１つの方法は、最大の一般性を求めることです。他のことが全部同じなら、より一般的なソフトウエア作品のコストは、一般的でないものと比べてより多くのユーザに分散させることができます。 不幸にも、一般化はしばしば、性能、生産性、あるいは両方のコストを伴います。それを見るために、以下の人気のある並列プログラミング環境を考えましょう。 C/C++ “Locking Plus Threads” : このカテゴリーは、POSIX スレッド(pthread) [Ope97]、 Windows スレッド、そして多くのオペレーティングシステムカーネル環境を含みます。そして、優れた性能（少なくても、単一の SMP システム内では）を提供し、一般性も確かなものです。やや、生産性が低いのが残念です。
Java : この汎用で、本質的にマルチスレッドなプログラミング環境は、自動ガーベッジコレクタと豊富なクラスライブラリのセットにより、C あるいは C++ と比べてずっと高い生産性を提供すると広く信じられています。しかし、その性能は、２０００年代初めに大いに改善されたとは言え、C と C++ には及びません。 MPI : この Message Passing Interface [MPI08] は、世界の最大級の科学技術計算クラスタに力を与え、他に並ぶものの無い性能とスケーラビリティを提供します。理論的にはこれは汎用ですが、主に、科学技術計算に使われています。その生産性は、 C/C++ “locking plus threads” 以下であると信じる人が多いようです。
OpenMP : このコンパイラディレクティブのセットは、ループを並列化するのに使われます。なので、これはその作業にとても特化しており、その特殊性のためにしばしば性能が限られます。しかし、MPI あるいは C/C++ “locking plus threads” よりも使うのはずっと簡単です。 SQL : Structured Query Language [Int92] は、リレーショナルデータベース問い合わせ専用です。しかし、その性能は Transaction Processing Performance Council (TPC) ベンチマーク結果 [Tra01] が示すようにとても良いです。生産性は素晴らしいです。実際、この並列プログラミング環境を使うと、並列プログラミング概念についてあまりあるいは全く知らない人でも、巨大な並列システムを使いこなすことができます。
世界級の性能、生産性、そして一般性を提供する、並列プログラミング環境の涅槃はまだ、まるで、存在しません。そんな涅槃が現れるまで、性能、生産性、そして一般性についての技術的トレードオフをする必要があります。そのようなトレードオフの１つが、図２．３です。生産性が、システムスタックの上の層で、より重要になるのを示し、性能と一般性がシステムスタックの下の層でより重要になるのを示します。
低い層での巨大な開発コストは、同じ様に巨大なユーザ数に分散されなくてはいけません。（だから一般性が大事）そして、低い層での性能損失は、スタックの上に行っても回復するのは難しいです。スタックの上の層では、ある特定のアプリケーションにはごく少数のユーザしかいないかもしれません。そのような場合、生産性への配慮が最も重要です。これが、スタックの上の方が、「水ぶくれソフトウエア」になりがちなことの説明になります。追加のハードウエアはしばしば追加の開発者よりも安いです。この本はスタックの底に近い開発者に向けて書かれています。そこでは、性能と一般性がとても重要です。 生産性と一般性のトレードオフは、多くの分野で何世紀にもわたって存在した事に注意下さい。１つの例として、ネイルガンは釘を打つには、ハンマーよりもずっと生産的です。しかし、ハンマーは釘を打つこと以外にもいろいろ使えます。なので、似たようなトレードオフが並列プログラミングの分野でもあるのは、驚くことではありません。このトレードオフは、図式的に図２．４に表されます。ここで、ユーザ１，２，３，４は計算機にやってほしい仕事がそれぞれあります。あるユーザにとって最も生産的な言語あるいは環境とは、単純にそのユーザの仕事を実行し、プログラミング、設定、セットアップなどを何もしなくて良いもののことでしょう。
クイッククイズ２．１０： これはばかげて実現不可能な理想です！実際に実現可能な他のことに注目したらどうです？
不幸にも、ユーザ１に必要な仕事をするシステムは、ユーザ２の仕事はしないでしょう。つまり、最も生産的な言語と環境は、ドメイン固有です。なので、定義からして、一般性を欠きます。 他の選択肢は、あるプログラミング言語あるいは環境をそのハードウエアシステム専用にしつらえることです。（例えば、アセンブラ、C, C++, あるいは Java）あるいは、いくらかの抽象化（例えば、Haskell, Prolog, あるいは Snobol）これは、図２．４の中心あたりの丸い領域で示されます。これらの言語は、ユーザ１，２，３，４が必要とする仕事にとっては、同じようにうまく当てはまらないという点で、一般的であると考えることができます。つまり、それらの一般性は、ドメイン固有の言語と環境と比べた時に生産性が低いという犠牲のもとで得られたわけです。さらに悪いことに、ある抽象化に対してしつらえられた言語は、誰かがその抽象化を実際のハードウエアに効率よくマップする方法を思いつかない限り、性能とスケーラビリティ問題に悩まされることが多いです。 並列プログラミングの３つのゴール、性能、生産性、そして一般性、これらはしばしば矛盾しますが、それらを胸に抱いて、さあ、いよいよ、並列プログラミングに代わるものを探して、これらの矛盾を回避する方法を考える時が来ました。
２．３ 並列プログラミングに代わるもの
正しく、並列プログラミングに代わるものを考えるためには、まずあなたは、並列性があなたに何をしてくれるのを期待するかを正確に決めなくてはいけません。２．２節で見たように、並列プログラミングの主なゴールは性能、生産性、そして一般性です。この本はソフトウエアスタックの底に近いところにある性能クリティカルなコードを書いている開発者に向けて書かれているので、この節の残りは主に、性能改善に焦点を当てます。 並列性は性能を上げるための方法の１つにすぎないことを心に留めるのは大切です。他のよく知られたアプローチは、以下があります。ほぼ、順に難しくなります。
１ シーケンシャルアプリケーションの複数インスタンスを動かす。
２ アプリケーションが既存の並列ソフトウエアを使うようにする。
３ シリアルアプリケーションに性能最適化を行う。
以下の節で、これらのアプローチを説明します。
２．３．１ シーケンシャルアプリケーションの複数インスタンス
シーケンシャルアプリケーションの複数インスタンスを動かすことであなたは、実際に並列プログラミングをしなくても、並列プログラミングができます。これにアプローチするにはたくさんの方法があり、アプリケーションの構造によります。 もしあなたのプログラムが、異なるたくさんのシナリオを解析するか、あるいはたくさんの独立したデータセットを解析しているなら、１つの簡単で効果的なアプローチは、１つの解析を実行する１つのシーケンシャルアプリケーションプログラムを作成して、たくさんあるスクリプティング環境（例えば、 bash シェル）のどれでもいいので、それを使って、そのシーケンシャルプログラムの、多数のインスタンスを並列に動かすことです。このアプローチをマシンのクラスタに容易に拡張できる時もあります。 このアプローチはずるをしているように見えるかもしれません。そして実際、そのようなプログラムを「なんちゃって並列」と中傷する人もいます。まあ、たしかにこのアプローチは潜在的な短所がいくつかあります。メモリ消費の増加、共通の中間結果を再計算することによるCPUサイクルの浪費、あるいはデータ複写の増加、などがあげられます。しかし、これはしばしば、極端に生産的です。追加の作業はわずかあるいは全くなくて、すばらしい性能増加が得られます。
２．３．２ 既存の並列ソフトウエアを使う シングルスレッドのプログラミング環境を提供することのできる並列ソフトウエア環境は、最近では豊富にあります。それには、リレーショナルデータベース [Dat82]、ウェブアプリケーションサーバ、そして、マップリデュース環境が含まれます。例えば、一般的な設計では、ユーザごとに別のプログラムを提供し、それぞれが SQL プログラムを生成します。これらの、ユーザごとのSQLプログラムは、共通のリレーショナルデータベースに対して並列に動かされ、ユーザの問い合わせを自動的に並列に実行します。ユーザごとのプログラムはユーザインタフェースだけに責任があり、リレーショナルデータベースが、並列性と永続性に関わる困難な問題に完全に責任を持ちます。
このアプローチを取るのは、しばしばある程度の性能を犠牲にします。少なくても、完全な並列性アプリケーションを注意深く手でコーディングするのと比べるとです。しかし、その犠牲はしばしば、必要な開発努力が大いに削減されることで正当化されます。
２．３．３ 性能最適化
２０００年代初めまで、CPU性能は１８ヶ月ごとに倍増しました。そのような環境では、新しい機能を作成するほうが、注意深い性能最適化をするよりもしばしばずっと重要でした。しかし、ムーアの法則が、トランジスタ密度とトランジスタごとの性能の両方を増加させなくなって、トランジスタ密度「だけ」を増加させるようになった今は、性能最適化の重要性を考えなおすよい機会かもしれません。結局、新しいハードウエア世代は、シングルスレッド性能の飛躍的改善をもはやもたらさなくなったのです。さらに、多くの性能最適化はエネルギーも節約できます。 この視点から見ると、並列プログラミングも性能最適化の１つに過ぎません。ただそれは、並列システムがより安く、入手しやすくなってきたため、よりずっと魅力的になってきました。 しかし、並列性によって得られる高速化は、ほぼ、CPU の数に制限されることを心に留めるのは賢明です。それに対し、伝統的なシングルスレッドのソフトウエアの最適化で得られる高速化は、ずっと大きいことがあります。例えば、長い連結リストをハッシュテーブルか検索木に変えることで性能を何桁も上げることが可能かもしれません。この高度に最適化されたシングルスレッドのプログラムは最適されていない並列版よりもずっと速く走ることができ、並列化を不要にするかもしれません。もちろん、高度に最適化された並列プログラムの方がより優れているかもしれません。追加の開発コストは必要かもしれませんが。 さらに、異なるプログラムは異なる性能ボトルネックを持つかもしれません。例えば、あなたのプログラムがほとんどの時間をディスクドライブからデータが来るのを待っているのに使っているなら、複数CPUを使っても、ディスクを待って浪費される時間を増やすだけでしょう。実際、あるプログラムが回転するディスクにシーケンシャルに置かれた１つの巨大なファイルを読んでいるとしたら、そのプログラムを並列化しても、余分のシークオーバーヘッドのためにずっと余計に遅くなることがありえます。その代わりに、データレイアウトを変えてファイルを小さくする（そうすれば、読むのに速い）、ファイルをチャンクに分割する（異なるドライブから並列にアクセスできる）、よく使うデータをメインメモリにキャッシュする、あるいは、可能ならば、読む必要のあるデータ量を減らす、などの改善をするのが良いでしょう。
クイッククイズ２．１１： CPUを追加しても、性能が増加しない場合のボトルネックにはどんなものが他にありますか？
並列性は強力な最適化技術です。しかし、それだけが最適化ではありませんし、すべての状況で適切だとも限りません。もちろん、あなたのプログラムを並列化するのが簡単であればそれだけ、最適化として並列化は魅力的になります。並列化は、とても難しいという評判です。さて、では、「実際に、並列プログラミングをそんなに難しくしているのは何でしょう？」という疑問がおきます。
２．４ 何が並列プログラミングを難しくしていますか？
並列プログラミングが難しいというのは、並列プログラミング問題の技術的性質のいくつかであると同じくらい、ヒューマンファクタの問題であることに注意するのは重要です。並列システムに何をすべきかを伝えるために人間は必要です。これをプログラミングと呼びます。しかし、並列プログラミングには２方向のコミュニケーションがあります。マシンから人間へのコミュニケーションは、プログラムの性能とスケーラビリティです。つまり、人間はプログラムを書いて、計算機に何をすべきかを使え、計算機はそのプログラムを結果となる性能とスケーラビリティによって批評します。このため、抽象化や数学的解析の有効性は、しばしばとても限定されたものとなります。 産業革命の頃、人間とマシンのインタフェースが、ヒューマンファクタの研究によって評価されました。これを、time-and-motion 研究と呼びます。並列プログラミングを調べる、いくつかのヒューマンファクタの研究がありますが [ENS05, ES05,HCS+05, SS94] 、これらの研究はとても狭いフォーカスを持っているために、一般的な成果を何も示すことができませんでした。さらに、プログラマの生産性の通常の範囲は、１桁以上の違いがあることを考えると、何らかの研究が、（例えば）１０％の生産性の違いを検出することが可能だと期待するのは非現実的です。
もちろん、そのような研究が、間違いなく、何桁もの違いを検出することが本当にできるならば、それはとても価値のあることですが、最も重要な改善は１０％の改善の長い連鎖に基づくことが多いのです。 なので、別のアプローチを取らなくてはいけません。 １つのそのようなアプローチは、シーケンシャルプログラマには必要なく、並列プログラマがやらなくてはいけない仕事を注意深く調べることです。そして、あるプログラム言語や環境が、これらの仕事において、開発者をどれくらい良く助けられるかを評価します。これらの仕事は図２．５に示す４つのカテゴリに分かれます。以下の節で、それぞれを説明します。
２．４．１ 仕事分割
仕事の分割は、並列実行には絶対に必要です。もし１つの仕事の「かたまり」があるだけだったら、それは一度に最大１つのCPUでしか実行できず、定義からしてシーケンシャル実行です。しかし、コードを分割するのは大変な注意が必要です。例えば、均等でない分割をすると、小さい部分が完了した後はシーケンシャル実行になってしまいます [Amd67]。それほど極端でない場合は、負荷分散をして、可能なハードウエアを完全に稼働させ、性能とスケーラビリティを回復することができます。
分割は性能とスケーラビリティを大いに改善するとは言え、複雑さも増します。例えば、分割は、グローバルなエラーとイベントの処理を面倒にします。並列プログラムは、そのようなグローバルイベントを安全に処理するために自明でない同期をしなくてはいけないことがあります。より一般的に言うと、それぞれの分割は、ある種の通信を必要とします。結局、あるスレッドが全く通信をしないならば、それは何の影響も持たず、実行する必要も無いわけです。しかし、通信はオーバーヘッドを伴いますから、不注意な分割の選択はひどい性能の低下につながることがあります。 さらに、同時実行するスレッドの数は、しばしば、制御されなくてはいけません。それら個々のスレッドはCPUキャッシュの領域などの、共通資源を専有するからです。もしあまりに多くのスレッドが同時に実行を許されると、CPUキャッシュがオーバーフローし、高いキャッシュミス率を起こし、その結果、性能を低下させます。その一方で、計算とI/Oをオーバラップさせて、I/Oデバイスを完全に稼働させるためには、しばしば、多数のスレッドが必要です。
クイッククイズ２．１２： CPUキャッシュ容量の他に、同時実行するスレッドの数を制限するものは何がありますか？
最後に、スレッドが同時実行するのを許すと、プログラムの状態空間はとても大きくなります。その結果、プログラムは理解とデバッグが困難になり、生産性を落とします。他のすべてが同じなら、より規則的な構造を持つ、より小さい状態空間は、理解がより簡単です。しかしこれは、技術的、数学的問題であるとともに、ヒューマンファクタの問題です。良い並列設計はとても大きな状態空間を持つかもしれませんが、それでも規則的な構造のために理解しやすいかもしれません。一方、悪い設計は、比較的小さい状態空間を持っていても、理解不能かもしれません。最良の設計は、なんちゃって並列性を活用します。あるいは、問題を、なんちゃって並列ソリューションを持つものへと変換します。どちらの場合も、「なんちゃって並列」は、実際には、富者の困惑なのです。現在の最高技術の良い設計はいくつもあります。状態空間の大きさと構造についてより一般的な判断をするには、もっと調査が必要です。
２．４．２ 並列アクセス制御
シングルスレッドのシーケンシャルプログラムであれば、その1つのスレッドはプログラムのすべての資源に完全なアクセスをできます。これら資源のほとんどは、メモリ上のデータ構造でしょうが、CPU,メモリ（キャッシュも含みます）、I/Oデバイス、計算アクセラレータ、ファイル、その他いろいろもあります。 最初の、並列アクセス制御の問題は、ある資源へのアクセスの形態が、その資源の位置に依存するかです。例えば、多くのメッセージパッシング環境では、ローカル変数のアクセスは式と代入で行われます。一方、リモート変数のアクセスは、全く異なるシンタックス、普通はメッセージの関与が必要です、を使います。POSIX スレッド環境 [Ope97]、Structured Query Language (SQL) [Int92]、Universal Parallel C(UPC) [EGCD03] のような、partitioned global address-space (PGAS) 環境は、暗黙的なアクセスを提供します。一方、Message Passing Interface (MPI) [MPI08] は明示的なアクセスを提供します。リモートデータへのアクセスは、明示的なメッセージが必要だからです。
もうひとつの並列アクセス制御の問題は、スレッドの資源へのアクセスをどのように調停するかです。この調停は、いろいろな並列言語環境において、とてもたくさんの同期機構によって実行されます。その機構には、メッセージパッシング、ロック、トランザクション、参照カウンティング、明示的なタイミング、共用アトミック変数、そしてデータ所有などがあります。デッドロック、ライブロック、トランザクションロールバックなどの、多くの、伝統的な並列プログラミングの問題は、この調停を起源とします。このフレームワークは、これら同期機構の比較を含むように精密化することもできます。例えば、ロック対トランザクションメモリ [MMW07] というように。しかし、そのような精密化は、この節のスコープを超えます。（トランザクションメモリについて詳しくは、１６．２と１６．３節を参照下さい。）
２．４．３ 資源分割と複製
最も効率的な並列アルゴリズムとシステムは、資源の並列化を活用します。これはとても有効なので、並列化を始めるにはまず、あなたのライトが主な資源を分割し、アクセス頻度の高いリードが主な資源を複製することから始めるのが賢明です。問題となる資源は普通はデータで、複数の計算機システム、大容量記憶デバイス、NUMA ノード、CPUコア（あるいはダイ、あるいは、ハードウエアスレッド）、ページ、キャッシュライン、同期プリミティブのインスタンス、あるいは、コードのクリティカルセクションなどに分割されているでしょう。例えば、ロッキングプリミティブに従って分割するのは、「データロッキング」 [BK85] と呼ばれます。
資源分割はしばしば、アプリケーション依存です。例えば、数値計算アプリケーションはしばしばマトリックスを行、列、あるいはサブマトリックスに分割します。そして、商用アプリケーションはしばしば、ライトが主なデータ構造を分割し、リードが主なデータ構造を複製します。このようにして、商用アプリケーションはある顧客のデータを巨大なクラスタ内のいくつかの計算機にアサインすることがあります。アプリケーションはデータを静的に分割することも、時が経過して分割をダイナミックに変更することもあります。 資源分割はとても効果的です。しかし、複雑な複数リンクのデータ構造でそれをやるのはとても大変でしょう。
２．４．４ ハードウエアと相互作用する
ハードウエアとの相互作用は、普通はオペレーティングシステム、コンパイラ、ライブラリ、その他のソフトウエア環境インフラストラクチャの領域です。しかし、新奇なハードウエア機能とコンポーネントに取り組む開発者は、そのようなハードウエアと直接取り組む必要があることがしばしばです。さらに、あるシステムの性能の最後の一滴を絞りとろうとするには、ハードウエアへの直接のアクセスが必要な時があります。この場合開発者は、アプリケーションを、対象とするハードウエアのキャッシュジオメトリ、システムトポロジ、あるいは接続プロトコルにあわせて調整したり設定する必要があるかもしれません。 場合によっては、ハードウエアは前の節で述べた、分割とアクセス制御に従う資源であると考えられることがあります。
２．４．５ 複合能力
これら４つの能力は基本的ですが、良い技術的慣習はこれら能力を混ぜて使います。例えば、データ並列のアプローチはまず、データを分割して、分割同士の通信の必要性を最小にしようとします。そしてコードをそれに従って分割し、最後にデータ分割とスレッドをマップして、スレッド間の通信を最小にする一方、スループットを最大にしようとします。これを図２．６に示します。開発者はそうすれば、それぞれの分割を別々に考えることができ、対応する状態空間の大きさをとても小さくすることができます。それは生産性を高めます。問題によっては分割不可能なものもあるかもしれませんが、分割を許す形になんとかうまく変換できれば、ときには、性能とスケーラビリティの両方が大いに強化できることがあります [Met99]。
２．４．６ 言語と環境はどのようにしてこの作業の助けとなりますか？
多くの環境では、開発者がこれらの仕事を手作業で行う必要がありますが、多大な自動化をもたらすことのできる環境が、以前からあります。そういう環境の代表選手は SQL です。その多くの実装は、１つの大きな問い合わせを自動的に並列化し、独立した問い合わせと更新の同時実行も自動化します。 これらの４つの仕事のカテゴリは、すべての並列プログラムで実行される必要がありますが、もちろんそれは開発者が手作業でこれらの仕事をやらなくてはいけないことは意味しません。並列システムがより安価に、より入手が容易になり続けるにつれ、これら４つの仕事の自動化がどんどん進んでいくのが期待されます。
クイッククイズ２．１３：
並列プログラミングには、それ以外の障害がありますか？
２．５ 議論
この章は、並列プログラミングの困難、ゴール、そして代案、の概要を見ました。概要に続いて、並列プログラミングが難しいのはなぜか、並列プログラミングの困難と対処するための高レベルのアプローチ、の両方を議論しました。さて、いよいよ、次の章に進む準備ができました。そこでは、私達の並列ソフトウエアの元となる、並列ハードウエアの関連する性質を詳しく調べます。
以上