並行コンピューティング技法

The Art of Concurrency和訳書籍への推薦文
訳者まえがき
まえがき
1章　速くしたい人、手を挙げて！
    1.1　さまざまな疑問
        1.1.1　スレッドモンキー
        1.1.2　並列と並行：その違いは？
        1.1.3　そんなことを知る必要があるの？ どんな役に立つの？
        1.1.4　並行プログラミングって難しくないの？
        1.1.5　スレッドって危険じゃないの？
    1.2　スレッド化の4つのステップ
        1.2.1　ステップ1. 分析：並行性を持つ部分を見つけ出す
        1.2.2　ステップ2. 設計と実装：アルゴリズムをスレッド化する
        1.2.3　ステップ3. 正当性の検証：スレッド化の誤りの検出と修正
        1.2.4　ステップ4. 性能チューニング：性能ボトルネックの排除
        1.2.5　スクラッチ開発
    1.3　並列アルゴリズムの背景
        1.3.1　理論モデル
        1.3.2　分散メモリプログラミング
        1.3.3　並列アルゴリズムの書籍
    1.4　共有メモリプログラミングと分散メモリプログラミング
        1.4.1　共通する機能
        1.4.2　共有メモリに固有の機能
    1.5　並行プログラミングへのアプローチ
2章　並行か非並行か？　それが問題だ
    2.1　並行アルゴリズム設計モデル
        2.1.1　タスク分解
        2.1.2　データ分解
        2.1.3　並行設計モデルの要約
    2.2　並列化不可能？
        2.2.1　状態を持つアルゴリズム
        2.2.2　漸化式
        2.2.3　帰納変数
        2.2.4　リダクション
        2.2.5　ループ内依存
3章　正当性の検証と性能測定
    3.1　並列アルゴリズムの検証
    3.2　例題：クリティカルセクション問題
        3.2.1　第1段階
        3.2.2　第2段階
        3.2.3　第3段階
        3.2.4　第4段階
        3.2.5　Dekkerのアルゴリズム
        3.2.6　何を学んだか？
        3.2.7　スレッドは悪くない、悪いのはそのようにプログラミングすることだ
    3.3　性能指標（現状把握）
        3.3.1　高速化率
        3.3.2　実行効率
        3.3.3　高速化率と実行効率について最後に一言
    3.4　並列性に対応するハードウェアの進化
4章　マルチスレッドアプリケーション設計の8つのルール
    4.1　ルール1：真に独立した処理を特定する
    4.2　ルール2：並行性はより上位で実装する
    4.3　ルール3：コア数増加に備えスケーラビリティ対応を早期に計画する
    4.4　ルール4：スレッドセーフなライブラリを使用する
    4.5　ルール5：適切なスレッドモデルを採用する
    4.6　ルール6：実行順序を前提としない
    4.7　ルール7：ローカル変数を使用する、できなければロックで保護する
    4.8　ルール8：並行性向上のためのアルゴリズム変更を恐れない
    4.9　まとめ
5章　スレッドライブラリ
    5.1　抽象化ライブラリ
        5.1.1　OpenMP
        5.1.2　Intelスレッディング・ビルディング・ブロック
    5.2　明示的スレッドライブラリ
        5.2.1　Pthread
        5.2.2　Windowsスレッド
    5.3　その他のスレッドライブラリ
    5.4　特定分野のライブラリ
6章　並列和とプリフィクススキャン
    6.1　並列和
        6.1.1　PRAMアルゴリズム
        6.1.2　より現実的なアルゴリズム
        6.1.3　観点別設計スコアカード
    6.2　プリフィクススキャン
        6.2.1　PRAMアルゴリズム
        6.2.2　より現実的なアルゴリズム
        6.2.3　観点別設計スコアカード
    6.3　セレクション
        6.3.1　逐次アルゴリズム
        6.3.2　並行アルゴリズム
        6.3.3　設計上の注意点
    6.4　章のまとめとして
7章　MapReduce
    7.1　並行map処理
        7.1.1　並行mapの実装
    7.2　並行reduce処理
        7.2.1　自作リダクション
        7.2.2　バリアオブジェクトの実装
        7.2.3　観点別設計スコアカード
    7.3　MapReduceの応用
        7.3.1　friendly数サンプルのまとめ
    7.4　MapReduceの一般的並行性
8章　ソート
    8.1　バブルソート
        8.1.1　それって動作するの？
        8.1.2　観点別設計スコアカード
    8.2　奇偶転置ソート
        8.2.1　並行奇偶転置ソート
        8.2.2　並行性を向上させてみる
        8.2.3　観点別設計スコアカード
    8.3　シェルソート
        8.3.1　挿入ソートの簡単なおさらい
        8.3.2　逐次シェルソート
        8.3.3　並行シェルソート
        8.3.4　観点別設計スコアカード
    8.4　クィックソート
        8.4.1　再帰の並行性
        8.4.2　繰り返しの並行性
        8.4.3　スレッド化最終バージョン
        8.4.4　観点別設計スコアカード
    8.5　基数ソート
        8.5.1　基数交換ソート
        8.5.2　直接基数ソート
        8.5.3　並行直接基数ソート
        8.5.4　観点別設計スコアカード
9章　サーチ
    9.1　未ソートデータ
        9.1.1　サーチの削減
        9.1.2　観点別設計スコアカード
    9.2　バイナリサーチ
        9.2.1　とりあえず逐次バージョン
        9.2.2　そして並行バージョン
        9.2.3　観点別設計スコアカード
10章　グラフアルゴリズム
    10.1　深さ優先探索
        10.1.1　再帰による実装
        10.1.2　繰り返しによる実装
        10.1.3　並行ソリューションにはまだ早い
        10.1.4　いよいよ並行ソリューション
        10.1.5　観点別設計スコアカード
        10.1.6　幅優先探索
        10.1.7　静的グラフと動的グラフ
    10.2　全頂点対最短経路
        10.2.1　k番目の行でのデータ競合はどうなった？
        10.2.2　観点別設計スコアカード
        10.2.3　Floydのアルゴリズムの変形
    10.3　最小スパニングツリー
        10.3.1　Kruskalのアルゴリズム
        10.3.2　Primのアルゴリズム
        10.3.3　どちらの逐次アルゴリズムから始めるか
        10.3.4　Primのアルゴリズムの並行バージョン
        10.3.5　観点別設計スコアカード
11章　スレッド対応ツール
    11.1　デバッガ
        11.1.1　スレッド対応のデバッガ
        11.1.2　スレッド専用デバッガ：スレッドチェッカー
    11.2　性能解析ツール
        11.2.1　プロファイリング
        11.2.2　スレッドプロファイリング：標準的ツールとスレッド・プロファイラ
    11.3　その他のツール
    11.4　前へ進め、そして打ち勝て

用語解説
Photo Credits
索引

コラム目次
    2分で分かる並行プログラミング入門
    観点別設計スコアカード
    デッドロックを発生させる4つの条件
    プリフィクススキャンを用いた配列のパッキング
    総当たり方式でルービックキューブ問題は解けるか