第1章 概要

• マルチコア・プロセッサーやメニーコア・プロセッサーの普及により、並列プログラミングは特殊なものではなく、この10年で一般化していた。
• しかし、並列プログラミングは簡単ではない。
• 本書では、効率よく、信頼性のある、保守しやすい、そして全てのコンピュータで性能がスケールなプログラムの設計と実装について説明する。
• 並列プログラミングのパターンがキーポイント
• パターンをどう実際の計算機で実装するかを例題で示す。それ以上の内容や実装についての足掛としてほしい

1.1 並列思考（Think Parallel）

ここでは、なぜThink Parallelすることの重要性を、最近のハードウェアの傾向から説明します。

逐次実行（シリアル化）

• 2010年ころから、並列化の重要性は非常に高くなりました。 CPUはこの頃からコア内で並列実行を行うことを主な目的として、研究開発がされる様になりました。 逆に言うと、それ以前のCPUは逐次実行を前提としてたからです。 なお、Out of Order実行などはソフトウェアから見えないので、それは除きます。

• しかし、プログラマとソフトウェアが並列化に追従するのは簡単ではありません。 並列化の考えかたは逐次実行のそれとは比較にならないほど複雑だからです。 また、逐次実行のCPUでは、並列化をしなくても性能に影響はありませんでした。 しかし、並列化がCPUでサポートされると、ソフトウェアも並列化されていないと性能が出せません。

• 決定性（deterministic）とは、「計算が行わる順番は必ず一緒」という性質です。 逐次実行は、決定性がある（決定的な実行）ので、ソースコードの上から順に処理が行われます。 並列実行では、決定性がないこともあるので、計算の順序がしばしば変わってしまい、実行するごとに計算結果が変わってしまうこともあります。

• シリアルの罠（serial trap）は、擬似的な逐次性のことで、真の逐次性でありません。 このシリアルの罠を回避して、プログラムやアルゴリズムを並列化しなければなりません。 うまく回避するために、本書では以下の2つの考え方について述べます。

  1. シリアルの罠の識別方法：
  2. 並列化パターンの修得：並列化パターンの観点からプログラミングを行ない、このパターンを効率よくハードウェアに実装する。

• 例：mapパターン。

逐次実行の擬似コード。search()は、for文により、順番に0からnumber_web_sitesまで実行される。

for(i = 0; i < number_web_sites; ++i){
        serarch(searchphrase, website[i]);
}

並列実行の擬似コード。search()は、parallel_for文により、順不同で0からnumber_web_sitesまで実行される。

parallel_for(size_t i = 0; i < number_web_sites; ++i){
        serarch(searchphrase, website[i]);
}

1.2 パフォーマンス

• シリアルの罠（その1）：四則演算など演算のみに注目してアルゴリズムの性能を議論してしまうこと。 近年は、演算よりも頻繁なメモリーアクセスや、通信が性能の阻害要因（ボトルネック）になってしまうことが多いです。

• シリアルの罠（その2）：アルゴリズムのスケーラビリティは、逐次実行部の長さ（スパン）で制限されてしまう。つまり、アムダールの法則。大規模並列計算をするときはかなりキツい。 アムダールの法則：$\displaystyle 性能向上の理論的上限 = \frac{1}{1-P + \frac{P}{S}}$, P: 並列実行可能な部分、S: 並列実行不可能な逐次実行部分

• 共有メモリマシンと局所性：現代のCPUは、共有メモリマシンと呼ばれる、メモリを共有するものです。 下の図の様に、同一の（ホモジニアス）CPUコアが、メインメモリを共有しています。 L1やL2キャッシュを共有しているものもあります。 重要な性質として、キャッシュは高速にアクセスできるが容量が小さい、また、メモリーは容量が大きいがアクセスが遅い、ということがあります。
  
  共有メモリマシンの例。対称型マルチプロセッサのブロック図。今さら聞けないマルチプロセッサの基礎教えます　――キャッシュの共有，割り込みの共有，OSによる制御｜Tech Village （テックビレッジ）　／　CQ出版株式会社

• 局所性は、時間的、もしくは、空間的に近いデータを扱うことを指します。大きく、以下の2種類があります。

  1. 空間的局所性は、配列の中の前後左右を利用して計算を行う、というものです。
  2. 時間的局所性は、さっき使ったデータを次のタイミングで改めて利用する、というものです。 これらの性質を利用して、次に利用されるであろうデータをキャッシュ入れておくことが高速化のポイントです。

並列アルゴリズムを設定する際、次の3点が重要です。

1. 演算ワークの総量
2. スパン（クリティカルパス）
3. 通信の総量（暗黙の共有メモリを含む）

図1.1: タスクは独立しており、それぞれに依存性がない。独立したタスクを分散させることは難しくないが、タスク自体を分割することは難しい。分割できないかもしれないし、分割のためのオーバーヘッド（共通する前処理など）と通信が増えてしまう事が考えられる。分割した結果、分割する前より計算時間が長くなってしまうこともありえる。

図1.2: タスクBとCが、タスクAと依存関係がある場合。この図の左の(a)は、依存関係がある場合を示している。具体的には、タスクAが終わった後に、タスクBとCを始めなければならない、というもの。

演算の分解と通信の管理が並列プログラミングに固有の作業。これを効率化することが並列プログラミングのポイント。本書の並列パターンはこれらをカバーするものである。

ロードバランスが実装の問題になる時がある タスクをうまく分割できないと、これを均一化することは出来ない。根本的に解決できないこともある

1.3 モチベーション：拡散する並列性

ここでは、なぜ一般的に明示的な並列プログラミングが必要なのかを述べる。

1.3.1 ハードウェアのトレンドが並列性を牽引する

原因1：ムーアの法則とその停滞

ムーアの法則：「集積回路あたりの部品数が毎年2倍になる」という経験則

このムーアの法則は、以下の様に広まった集積回路の経験則。長い年月を経さまざまな尾ひれがついてしまっており、オリジナルの解釈とはかなり異なることに注意。

2020年ころまでのトランジスタの数の推移。2010年頃まで3年で4倍になっており、ムーアの法則が成り立っている。[^1]

ムーアの法則についての細かい話：【福田昭のセミコン業界最前線】「間違いだらけ」のムーアの法則 - PC Watch

原因2：プロセッサーの動作クロックの停滞。その3つの壁

• a. 電力の壁：動作クロックの増加による電力の増加
  CPUの発する熱密度が、太陽表面のそれに追いついてしまう？デカい計算機を作れなくなってしまう。この本が書かれたよりももっと、電力性能の問題は深刻になってきている。
• b. 命令レベル並列性の壁：利用できる命令レベル並列性が界になった
  ILPは、プログラムで利用できるいくつかの並列性の中でもとも粒度の小さいも。逐次実行を想定して書かれたソースコドから、命令レベル並列性を自動的に利用する研究が限界ま来てしまった。パイプライン処理により複数の命令を同時並的に行ったり、投機実行を行って処理を前倒しして行う技術ある。しかし、自動的にこれらを利用する研究も限界に来てまった。今も研究は進んでいるが、どれも劇的な性能向上は込めなくなった。

• c.メモリーの壁：メモリのアクセス速度の向上が、プロセッの計算速度の向上に付いて行けなくなった
  今後は、演算ではなく、メモリーをどう効率的に利用するか鍵になる。メモリーへのアクセス時間は、演算1回を行う時の10〜50倍にもなる。
  プロセッサとメモリのレイテンシのギャップの関係

• Sut05, The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software
  プログラム側が明示的な並列化をせずに、プログラムがそのままCPUの高速化にただ乗りして高速化される時代は終わった、という2005年の記事。著者は、MicrosoftのC++開発者 Herb Sutter。ソフトウェア側の技術者がこれを書いたことが重要。

P.13 2段落目のまとめが重要。

1.3.2 並列化に関する歴史的トレンド

以下の図は、教科書の図1.3,1.4,1.5,1.6をまとめたものです。この図は、次の解釈できます。まず、2004年に電力の壁にぶち当たってしまった。そのため、周波数が4GHz程度からあまり上がらなくなり、Free Lunchもそこで終わった。ムーアの法則が続いているので、トランジスタは増やすことができたので、増えたトランジスタを並列度を利用するために利用した。例えば、広い幅のSIMD命令、キャッシュサイズの増加などです。

トランジスタ数、動作周波数、消費電力、コア数の推移（1970年～2010年）

教科書では、P.17あたりからSPEC CPU2006という指標を使って、電力性能について解説していますが、この資料では、GREEN500というスーパーコンピュータの電力性能を競うコンテストの結果をもとに、これを説明をします。

Free Lunchが終わった2004年頃から、GPU（Tsubame KFC）が登場する2013年あたりまでは、性能がなだらかです。その後、2016年くらいまでGPUが電力性能の向上を牽引します。2016年のZettaScaler-1.6cから性能がジャンプアップします。これは、ここらへんから各社が非常にGREEN500の指標を重要視して、力を入れ始めたということもあります。 米国の次のスパコンシステムの性能目標である、20MWで1ExaFlopsを達成するには、50GFlops/Wを超えなければならない。半分くらいまで来たところです。富岳は、30MWで500TFLOPS程度です。

GREEN500の電力性能の推移（2008年～2020年）

1.3.3 明示的な並列プログラミングの必要性

ここでは、なぜ並列化が自動的に行われないのかをプログラミングの視点から解説します。自動的に行われない大きな原因の1つはシリアルの罠です。

並列化を自動的に行うためには、コンパイラーがソースコードから並列性を見つけるか、実行時にCPUが命令列からILPなどの並列性を見つけなければなりません。しかし、これは簡単ではありません。

以下の例では、コンパイラがaddme()関数内部に依存性があるかもしれないと判断して並列化を中止してしまいます。

リスト 1.1

void addme(int n, double a[n], double b[n], double c[n]){
    int i;
    for (i = 0; i < n; ++i)
        a[i] = b [i] + c[i];  // a,b,cが完全に独立している保障がない
}

リスト 1.2

doubel a[10];
a[0] = 1;
addme(9. a+1, a, a); // 配列b,cにaを入れており、for文を順番に計算しないと意図した結果にならない。これがポインタ演算はエイリアスの原因となる

教科書の例の他にはには、#pragma ivdepをfor文の前に導入すると、多くのコンパイラで、各配列が重複しないとヒントを与えることができる。その結果、並列化が促進される。

リスト1.4では、加算を並列にしてよいのであれば、「リダクション」というパターンを使うことができるが、

リスト 1.4

double summe(int n, double a[n]){
    double mysum = 0;
    int i ;
    for (i = 0; i < n; ++i)
        mysum += a[i];    // 加算が逐次であるべきかはコンパイラはわからない
    return mysum;
}

1.4 構造化されたパターンベースのプログラミング

History does not repeat itself, but it rhymes. （歴史は繰り返さない、ただ韻をふむのみ。） Mark Twain

本書で解説するパターンの位置づけ

1. デザインパターン：高い抽象度での設計に向いている。重要だが抽象的
2. アルゴリズム戦略パターン：1と3の間。セマンティクス（意味論）と実装から成る
3. 実装パターン：特定のアーキテクチャの詳細な構成に注目する。

セマンティクス：アルゴリズムの構成要素として、パターンがどのように利用されるかに着目する。アルゴリズムを設計する際に利用される。セマンティクスは、タスクとデータの依存性の関係から成る。これは、パターンを構成するタスクが実際に特定の実装で並列に実行されるかどうかなど、詳細を隠蔽する抽象化。

実装：特定のアーキテクチャやプログラミング言語で、パターンをどのように実現するか。パターンを改良したり、違うパターンの選択も有りうる。

図 1.11 並列パターンの概要

基本的な3つの並列性。データ並列性として考えても良い。

• ネスト(nesting)：スーパースカラー・シーケンスとフォーク・ジョインのことのようだ。タスク（青い四角）をいくつかのタスクに分解したり、逆に、複数のタスクを1つにまとめて、階層構造にすること。構成の容易性 (composability) が上がるが、並列化の際に利用するのは簡単ではない。全体構造を示す時に良さそう。

• マップ(map)：Embarrassingly parallel（日本語ではバカパラなどと呼ばれる）は、高い並列度を持つパターンの代表例。

• フォーク・ジョイン(fork-join)：問題を回区分に再帰的に細分化して、並列化に利用できる。分割統治にの実装に役立つ。

1.5 並列プログラミング・モデル

ここでは、本書で利用するプログラミング・モデルの基本的な背景の説明する。

※ TBBやCilk Plus、ArBBを用いた具体例が本文中には出てくるが、講義資料では、それらは取り上げない。

1.5.1 必須特性

PythonやC言語、古いC++やJavaは、言語として並列プログラミング向けに設計されていません。並列プログラミング・モデルは以下の特性を持つべきです。（実現難しそう）

• パフォーマンス：CPU単体で高い性能を発揮し、CPUやマシンの台数が増えてもスケールし、性能や通信時間が予測可能かつ調整できる。
• 生産性：パターンを表現し、それらを構成できる。また、デバッグできて、保守が可能である。
• 移植性：いろいろなCPUやマシンで、現在もそして将来も動作するべき。

教科書で扱うプログラミング・モデル

1. Intel Threading Building Block (Intel TBB)
   C++の並列実装に利用するテンプレート・ライブラリー。2021年現在、oneTBBと名称が代わり、oneAPIの一部として無償で利用できる。
   oneapi-src/oneTBB: oneAPI Threading Building Blocks (oneTBB)
   インテル oneTBB | C++ 並列化テンプレート・ライブラリー | XLsoft Intel

2. Intel Cilk Plus (2021年時点では開発終了)

教科書で扱われていないが重要なプログラミング・モデル

1. C++1z 並列アルゴリズムライブラリ
   C++17などの規格で追加された並列アルゴリズム

2. kokkos
   ANLNが作っている計算パターンのためのDSL

1.5.2 メカニズムに代わる抽象化

パターンを使わずに、POSIXスレッドや直接ハードウェアの並列化の機能（intrinsic）などを使うのは、移植性や再構築性の観点から避けるべきです。

1.5.3 規則的なデータ並列の表現

データ並列性は、スケーラビリティを達成するための鍵です。 異なる並列化方針である機能分割では、非常に高い並列性を実現するのは難しい。

データ並列には、規則的なデータ並列（regular data parallelism）というサブカテゴリーがある。SIMDなどのベクトル命令を利用する際に用いられる考え方。なお、ベクトル命令はベクトル長も処理方式も各アーキテクチャで異なるので、抽象化して移植を簡単にしたい、というニーズがある。これらを言語レベルでサポートしたのが、並列プログラミング・モデルの大きなポイントの1つです。

リスト1.8 C言語によるシリアルのベクトル加算のループ

for (i = 0; i < 10000; ++i){
        a[i] = b[i] + c[i];
}

リスト1.8はコードを記述した開発者はおそらく、「配列bとcの対応する全ての要素を計算して、結果を配列aの対応する位置に格納すること」を意図しているでしょう。しかし、このコードは次のようにも読めます。加算は0～10000の順番で行わなければならない。また、C++などの言語ではこれらの配列にポインタの値を代入できますが、ポインタの値（配列a、b、cのデータ格納場所）が重複しているかもしれません。コンパイラは、計算結果の正しく保つために、順番を守って計算を行ないます。つまり、並列化されません。また、配列の各要素は、アラインメントされていない可能性があります。これはコンパイラが持つベクトル機能を効果的に使用することを困難にします。プログラマーの意図を正しくコンパイラーに伝えるための機能が、並列プログラミングモデルには必要です。

1.5.4 構成の容易性

Composabilityは、プログラムをほかの場所で利用する際に、他の機能にかかわりなくその機能を利用できることを表します。つまり、他のプログラミングと組み合わせて利用しても問題なく動作する、という性質です。

1.5.5 機能性の可搬性

OSやプロセッサーに関わらず、様々なプラットフォームでコードを実行されることが望まれます。多くの並列プログラミング言語はC++の拡張やライブラリーの形で提供されています。これは既存のプログラム（特に自然科学計算系）に後付けで拡張するという現実的な問題を解決しつつ、機能性の可搬性を保つためです。

1.5.6 パフォーマンスの可搬性

パフォーマンスの可搬性は、ある計算機で高い性能を発揮するプログラムが、別の計算機では高い性能を発揮できるかどうかを指します。これに関しては2021年現在も活発に研究開発が行われており、とても異な研究テーマです。kokkosはパフォーマンスの可搬性を実現することが1つの目標です。

1.5.7 安全性、決定性、および保守性

決定性と非決定性は、並列計算には必須の考え方です。決定性はプログラムが動作する時に結果が常に同じであることを意味します。逐次演算では、処理の順番は必ず固定されており、結果は自然に決定的になります。しかし、並列計算では、自然に決定的ではありません。異なる複数のスレッドによる処理の順番が逆転したり、大きく入れ替わってしまいます。その結果、複数のスレッドがデータを更新すると、同じ入力データであっても実行ごとに結果が異なってしまいます。これを非決定性と呼びます。例えば浮動小数点の掛け算では、計算順序が変わることによって最終的な計算結果が微妙に異なってしまいます。

1.5.8 本書で使用されるプログラミング・モデルの概要

※ Cilk PlusとArBBはスキップ

Threading Building Block (TBB)

TBBは言語拡張ではなく、ライブラリーです。C++の機能を利用して実装されており、プログラミングにはC++のテンプレートとジェネリックプログラミングを用います。具体的には、コードブロックの並列実行を明示するために関数オブジェクトとラムダ式を用います。TBBはスレッドではなく、タスクを基本単位としてプログラムします。これはオーバーヘッドを軽減し、より効率よくリソースを管理するためです。すべてのタスクで共有される共通のスレッドプールを持ち、ワークスティールによってロードバランシングされます。主な特長は以下の通りです。

• テンプレートライブラリは、規則性あり・なしの両方の並列性をサポート
• map, fork-join, reduction, scan, pipelineなど多くの並列パターンを直接サポート。タスクグラフによるユーザ独自のパターンも記述可能
• ワークスティールによる効率的なロードバランシング
• スレッドセーフなデータ構造のサポート
• アトミック操作やメモリー割り当てなど効率よい低レベルの基本関数をサポート

OpenMP

OpenMPは言語拡張やライブラリーではなく、注釈構文（プラグマ）です。ピンクのスレッド並列を簡単に記述するために開発されました。その後、本書で示すようなタスクをベースにした並列実行を行えるように拡張されています。（が、タスクのOpenMPはあまり流行っていないような？）

• コードブロックを連携してして実行する、スレッドのチームを生成可能。
• 簡単なプラグマだけで、スレッドをチームで並列実行するようにループ境界の範囲を変換可能。
• スレッドの明示的なチームで実行をサポートするタスクモデル。
• アトミック演算とロックをサポート。
• 事前定義された処理によるリダクションをサポート

1.5.9 いつどのモデルを使用するか

いろいろ書かれていますが、実質的な選択肢はOpenMPタスクとkokkos, TBBのみだと思います。1番手をつけやすいのがOpenMPタスク、続いてkokkos、最後にTBBかなと思います。

1.6 本書の構成

略

1.7 まとめ

• 明示的な並列プログラミングが求められる要因となった歴史的な背景
• 動作周波数の向上を阻害する3つの壁：電力性能の壁、命令レベル並列性の壁、メモリーの壁
• なぜ並列パターンを利用するのかの解説
• 移植性、性能可搬性、構成の容易性
• 並列プログラミング言語についての概要説明
• TBB, OpenMP, kokkos