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

マルチコアプロセッサの登場により、逐次アルゴリズムから並列アルゴリズムへ、ソフトウェア開発は大転換期を迎えています。マルチコア時代の現在、急速に高まる並列プログラミング / マルチスレッドプログラミングの需要に応えるために本書は執筆されました。並列プログラミングの基礎から、具体的な設計、実装方法を解説。従来の逐次実行の考え方から移行しやすいように、並行ソフトウェア開発の経験豊かな Intel の技術者である著者が、ポイントを押さえてていねいに解説します。マルチスレッドプログラミングで役立つツールも紹介。マルチコアプロセッサの性能を最大限に引き出すために必須の一冊です。

マルチコアプロセッサーの性能を引き出すために、逐次実行を前提に書いてきたプログラムをどう並列化するかを学ぶ本です。『並行コンピューティング技法』 (Clay Breshears 著、千住 治郎 訳、オライリー・ジャパン発行、オーム社発売、2009 年 12 月刊) は、原書 The Art of Concurrency の日本語版で、副題は「実践マルチコア/マルチスレッドプログラミング」です。版元の紹介によると、著者は並行ソフトウェア開発の経験が豊かな Intel の技術者で、並列プログラミングの基礎から具体的な設計と実装方法までを、従来の逐次実行の考え方から移行しやすいように解説し、マルチスレッドプログラミングで役立つツールも紹介しています。

前半 5 章、スレッド化の手順と設計のルール

1 章「速くしたい人、手を挙げて!」は、並列と並行の違いやスレッドは危険ではないのかといった疑問から入り、分析、設計と実装、正当性の検証、性能チューニングからなる「スレッド化の 4 つのステップ」を示します。2 章「並行か非並行か? それが問題だ」はタスク分解とデータ分解という設計モデルと、状態を持つアルゴリズム、漸化式、帰納変数、リダクション、ループ内依存といった並列化を妨げる要因を扱います。3 章は段階を追って Dekker のアルゴリズムへ進むクリティカルセクション問題の例題と、高速化率と実行効率という性能指標、4 章は「マルチスレッドアプリケーション設計の 8 つのルール」です。5 章「スレッドライブラリ」では、抽象化ライブラリとして OpenMP と Intel スレッディング・ビルディング・ブロック、明示的スレッドライブラリとして Pthread と Windows スレッドを取り上げます。

6 章から 10 章、ソートやグラフのアルゴリズムを並行化する

後半は、よく知られたアルゴリズムを題材に並行化を試す章です。6 章は並列和、プリフィクススキャン、セレクション、7 章は MapReduce、8 章はバブルソート、奇偶転置ソート、シェルソート、クィックソート、基数ソート、9 章は未ソートデータのサーチとバイナリサーチ、10 章は深さ優先探索と幅優先探索、全頂点対最短経路、最小スパニングツリーを扱います。いくつかの節は逐次版を示してから並行版へ進む組み立てで、6 章から 10 章の多くの節の末尾には「観点別設計スコアカード」という項が置かれています。11 章「スレッド対応ツール」はスレッド対応のデバッガーと性能解析ツールを取り上げ、巻末には用語解説と索引が付きます。コラムには「デッドロックを発生させる 4 つの条件」なども収められています。

共有データとロックをめぐる並行化の難しさ

処理を複数のスレッドに分けて 並行処理 にすれば、コアの数だけ速くなるわけではありません。複数のスレッドが同じデータを読み書きすると、実行のたびに順序が入れ替わり、結果が変わる 競合状態 が起きます。それを防ぐには ミューテックス などで共有データへのアクセスを守る必要がありますが、守る範囲が広いほどスレッドが互いを待つ時間が増え、並行化した意味が薄れます。正しさと速さの両方を確かめる手間がかかる点が、並行プログラミングの難しさです。本書が 3 章「正当性の検証と性能測定」を独立した章として立て、後半の多くの節に設計を評価する項を設けているのは、この両面を同時に見る姿勢の表れと読めます。

向いている読者と、2009 年刊という前提

逐次のプログラムは書けるものの、並列化の経験が浅く、どこから手を付ければよいか分からない人に向く本です。ソートや探索のような馴染みのある題材で考え方を追えます。一方、取り上げるスレッドライブラリは 2009 年の刊行時点のもので、特定の言語に組み込まれた並行処理の機能の使い方を知りたい場合は、その言語の本を別に選ぶほうが近道です。版元のページには第 1 刷の正誤表も掲載されています。マルチスレッドのプログラムを設計するときに、どこが並列化でき、どこが妨げになるかを自分で判断できるようになりたい人にとって、手順とルールとアルゴリズムの実例を 1 冊で通して学べる本書は、手元に置いて繰り返し開く価値のある一冊です。