An Introduction to Parallel Programming（並列プログラミング入門）

引用

Pacheco, P. S., & Malensek, M. (2021). An Introduction to Parallel Programming (2nd ed.). Morgan Kaufmann (Elsevier).

章の要約

第2版は約496ページ、全8章である。初版の3つのプログラミングインターフェース（分散メモリ向けのMPI、共有メモリ向けのPthreadsとOpenMP）に、CUDAによるGPUプログラミングの新しい章が加わった。著者は本書を、従来の単一プロセッサのシステムでプログラムを書けるが、マルチプロセッサシステムのプログラミング経験はほとんどない学生や専門家のための初歩的な入門書と位置づけている。出版社は、小さなプログラムから始めてより難しい例へと積み上げるチュートリアル式の進め方を強調しており、演習では例題プログラムをコンパイルし、実行し、改変することが求められる。著者がダウンロード提供しているソースコードには、各プログラムをそれを論じる節に対応づけた索引が付いており、各章が本書全体で繰り返し登場する少数の問題を軸に構成されていることがわかる。

第1章：Why Parallel Computing（なぜ並列計算か）

冒頭の章は、題名のとおり並列計算がなぜ必要なのかを述べ、その後本書はハードウェア、ソフトウェア、個々のプログラミングインターフェースへと進む。

第2章：Parallel Hardware and Parallel Software（並列ハードウェアと並列ソフトウェア）

並列ハードウェアとソフトウェアの背景知識。正誤表からは、ハードウェアの内容にキャッシュコヒーレンス（2.3.5節）が含まれることがわかり、バスはスケールしないため、スヌーピング方式のコヒーレンスは現在ではほとんど使われないという著者の注記が加えられている。コード索引によれば、2.7.1節に逐次版のヒストグラムプログラムがあり、これが並列プログラムを開発するこの章の例となっている。

第3章：Distributed Memory Programming with MPI（MPIによる分散メモリプログラミング）

全プロセスから挨拶を表示するプログラムから始め、台形公式をいくつかの版で並列化しながら、1対1のメッセージから、リダクションやブロードキャストといった集団操作へと進む。後半の節では、scatterとgatherによるベクトルの分配、行列・ベクトル積、派生データ型、実行時間の計測と性能評価、並列奇偶転置ソートを扱う。

第4章：Shared-Memory Programming with Pthreads（Pthreadsによる共有メモリプログラミング）

挨拶プログラムと行列・ベクトル積でスレッドを導入し、続いて円周率の推定を使って競合状態を明らかにし、クリティカルセクションを保護する方法としてビジーウェイト、ミューテックス、セマフォを比較する。さらに、3通りの方法で作るバリア、共有連結リストに適用する読み書きロック、そしてスレッドセーフでないライブラリ関数でテキストを字句分割する例によるスレッド安全性を扱う。

第5章：Shared-Memory Programming with OpenMP（OpenMPによる共有メモリプログラミング）

台形公式をクリティカルセクション、reduction節、parallel forループで改めて扱い、素朴には並列化できないループ（フィボナッチ数）を示す。さらに、変数のスコープ、奇偶ソート、ループのスケジューリング、critical・atomic・ロックを用いたスレッド間のメッセージ受け渡し、行列・ベクトル積、OpenMPのタスク、スレッド安全性を取り上げる。

第6章：GPU Programming with CUDA（CUDAによるGPUプログラミング）

この版で新設された章。スレッドの1ブロックとして起動するカーネルから始め、ベクトルの加算、デバイスからの結果の受け取り、段階的に洗練される3つのCUDA版の台形公式（正誤表によれば6.11節でワープシャッフル関数を扱う）へと進み、最後にバイトニックソートを、まず1つのスレッドブロック内で、次に複数のブロックにわたって実装する。

第7章：Parallel Program Development（並列プログラムの開発）

2つのより大きな事例研究で、それぞれを本書のすべてのインターフェースで解く。基本版と縮約版のn体問題ソルバーをOpenMP、Pthreads、MPI、CUDAで並列化し、続いてサンプルソートを逐次版とOpenMP、Pthreads、MPI、CUDA版で開発する。MPI版では異なる通信パターンが用いられる。

第8章：Where to Go from Here（この先どこへ進むか）

最終章は、題名が示すとおり、さらなる学習への道筋を示す。

主要概念

第1–2章：基礎

• 共有メモリと分散メモリ：並列システムの2つの大きな分類で、プロセスがメモリを介して通信するか、メッセージを介して通信するかを決める。
• キャッシュコヒーレンス：異なるコアのキャッシュにある共有データのコピーを一貫した状態に保つこと。
• 並列ソフトウェア：協調する複数のプロセスやスレッドとして動作するように書かれたプログラム。

第3章：MPI

• 1対1通信と集団通信：プロセスの組の間でのメッセージ送信と、全プロセスの間での一斉の通信（reduce、broadcast、scatter、gather）。
• データの分配：ベクトルや行列をブロック単位でプロセスに分割すること。
• 派生データ型：連続していないデータを1つのメッセージで送れるように記述すること。
• 性能評価：並列プログラムの実行時間を計測し、どの程度スケールするかを判断すること。3.6節の主題である。

第4–5章：PthreadsとOpenMP

• 競合状態とクリティカルセクション：複数のスレッドが同時に共有データを更新するときに生じる誤りと、保護しなければならないコード領域。
• ミューテックス、セマフォ、バリア、条件変数、読み書きロック：Pthreadsの同期の道具。
• 指示文と節：ループや領域を並列化するOpenMPの方法で、リダクションやスケジューリングを含む。
• スレッド安全性：複数のスレッドから同時に呼ばれたときに関数が正しく動作するかどうか。

第6–7章：GPUとより大きなプログラム

• カーネル、スレッド、ブロック：ブロックにまとめられた多数の軽量スレッドをGPU上で走らせるCUDAのモデル。
• ワープ単位の操作：ワープ内のスレッドが効率よく値を交換できるようにする、ワープシャッフルなどの関数。
• n体シミュレーションとサンプルソート：現実的な問題で4つのインターフェースすべてを比較するために使われる事例研究。

批判的分析

長所

• すべてのインターフェースで同じ問題を扱う。 台形公式はMPI、OpenMP、CUDAに登場し、行列・ベクトル積と奇偶転置ソートも繰り返し現れる。第7章ではn体問題とサンプルソートを4つのインターフェースすべてで解く。学生は互いに無関係な例で一つずつ学ぶのではなく、プログラミングモデルを直接比べることができる。
• 壊れたプログラムから学ぶ。 コード索引からは、まずバグのある版や素朴な版（競合の起こりやすい円周率の推定、誤ったフィボナッチのループ、スレッドセーフでない字句分割）を示し、それから修正するという意図的な構成がわかる。これにより、同期の道具がなぜ存在するのかが身につく。
• 実践的で、実際に動かせる。 著者はすべてのソースコードを提供し、ウェブサイトで正誤表を更新している。出版社は教員向けに講義スライド、解答集、図版集を挙げている。演習ではプログラムのコンパイル、実行、改変が求められる。
• GPUに対応した内容。 新しいCUDAの章と第7章のCUDA版によって、それまでCPUとクラスタのみを扱っていた教科書にアクセラレータが加わった。

短所

• C言語とAPIが中心。 すべてのプログラムはCで書かれており、本書は4つの特定のインターフェースを教える。より高水準のフレームワークや、例題に必要な範囲を超えた並列アルゴリズムの理論は扱わない。
• GPUはCUDAのみ。 他のアクセラレータや移植性のあるGPUフレームワークを使う読者は、別の資料が必要になる。出版社はヘテロジニアスプログラミングにも言及しているが、目次にはそれを独立に扱う章がないので、その話題の詳しい扱いは期待しないほうがよい。
• 分散システムの教科書ではない。 本書は一つの計算を多数のプロセッサで高速化することを扱う。このコースの他の部分の中心である耐故障性、一貫性、複製は範囲外である。
• ハードウェアの内容には古くなりやすいものがある。 著者自身の正誤表が、第2章のスヌーピング方式のコヒーレンスの記述は、現在ではほとんど使われない技術を反映していると注記している。

コースにおける位置づけ

分散システムのコースの中で、本書は並列計算の側面、すなわち多数のコア、多数のノード、あるいはGPUを使って一つの計算を速く走らせるプログラムの書き方を担う。他の本は、信頼できない機械とネットワークにまたがって動き続けるサービスをどう作るかという別の問いを扱っている。ロベルト・ヴィティッロの Understanding Distributed Systems は、ネットワーク化されたサービスにおける通信、協調、スケーリング、回復力について開発者向けに簡潔に紹介する本であり、クルリスらの Distributed Systems: Concepts and Design とファン・スティーンとタネンバウムの Distributed Systems は、アーキテクチャ、名前付け、協調、一貫性、複製、耐故障性を原理から説く教科書である。

クレップマンとリコミニの Designing Data-Intensive Applications は、本番のデータシステムにおける複製、パーティショニング、ストリーム処理を扱い、カシャン、ゲラウイ、ロドリゲスの Introduction to Reliable and Secure Distributed Programming は、耐故障性のある抽象化と合意を扱う大学院の教科書である。パチェコとマレンセクの第3章のMPIが最も近い架け橋となる。プロセス間のメッセージパッシングは共通の土台だが、本書の目的は故障への耐性ではなく速度である。コースに並列プログラミングが含まれる場合、あるいは分散システムの教科書の実践的な補完として本書を読むとよい。

本書の使い方

本書は、並列計算や高性能計算の最初の授業を受ける学部生、自分のコードを高速化する必要のある理工系の学生、そして並列の経験のないプログラマに向いている。例題はすべてCで書かれているので、ポインタや配列を含め、Cでのプログラミングに慣れている必要がある。

• 中核： 語彙と設計の方法のために第1–2章、続いて少なくとも一つのインターフェースを深く学ぶ。多くの授業は第3章（MPI）と第5章（OpenMP）を扱う。第4章（Pthreads）は低いレベルでの同期を最もはっきり見せてくれる。
• GPUの選択肢： 第6章。GPUに重点を置く授業では第2章の直後に読んでもよい。
• 総まとめ： 第7章は、学んだインターフェースの後に読む。それらのインターフェースでn体問題とサンプルソートの解法をたどり、性能を比べる。
• 締めくくり： さらなる学習の方向については第8章。

著者のサイトからソースコードをダウンロードし、読みながらすべての例を実行して、プロセスやスレッドの数を変えて時間を計るとよい。ここで性能評価が具体的なものになる。GPUのコードリストに頼る前に正誤表を確認すること。性能の振る舞いは単一のコアでは学べないので、可能であれば実際のマルチコアマシンと小規模なクラスタ、あるいはGPUを使うとよい。