マルチコアプロセッサの登場により、逐次アルゴリズムから並列アルゴリズムへ、ソフトウェア開発は大転換期を迎えています。マルチコア時代の現在、急速に高まる並列プログラミング/マルチスレッドプログラミングの需要に応えるために本書は執筆されました。並列プログラミングの基礎から、具体的な設計、実装方法を解説。従来の逐次実行の考え方から移行しやすいように、並行ソフトウェア開発の経験豊かなIntelの技術者である著者が、ポイントを押えてていねいに解説します。マルチスレッドプログラミングで役立つツールも紹介。マルチコアプロセッサの性能を最大限に引き出すために必須の一冊です。
並行コンピューティング技法
―実践マルチコア/マルチスレッドプログラミング
Clay Breshears 著、千住 治郎 訳
- TOPICS
- Programming
- 発行年月日
- 2009年12月
- PRINT LENGTH
- 284
- ISBN
- 978-4-87311-435-4
- 原書
- The Art of Concurrency, 1st Edition
- FORMAT
- Print PDF
正誤表
ここで紹介する正誤表には、書籍発行後に気づいた誤植や更新された情報を掲載しています。以下のリストに記載の年月は、正誤表を作成し、増刷書籍を印刷した月です。お手持ちの書籍では、すでに修正が施されている場合がありますので、書籍最終ページの奥付でお手持ちの書籍の刷版、刷り年月日をご確認の上、ご利用ください。
第1刷正誤表
並行コンピューティング技法 第1刷正誤表
2010年1月14日更新
|
目次
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つの条件 プリフィクススキャンを用いた配列のパッキング 総当たり方式でルービックキューブ問題は解けるか