前回までのあらすじ
以前から気になっていた「並行コンピューティング技法」を衝動買い。全体の構造を読み解き、どんな知識がこの本から得られるかを考察した。合わせて、第1章を読み、内容を簡潔にまとめた。第1章は大きく以下のような内容を扱っている
- 並行と並列の違い
- 並行までの(現在の逐次処理を並行処理に書き直すため)の4ステップ
続いて、第2章を読み進めていこう
第2章
まずは前回同様に、見出しから第2章からどんな情報が得られるのかをざっくりと観察してリスト出ししてみた。
- 並行処理にするための2つの手法
- タスクの分解(特徴とサンプル)
- データの分解(特徴とサンプル)
- 並行不可能な場合の例(実際にはタイトルは適切ではなく、並行不可能な場合の回避テクニックに近い)
「並行処理にするための2つの手法」は実は第1章で既に登場した話であり、第2章では、この部分をより深掘りにしている。並行までの4つのステップの中の「スレッド化したいところを見つける」と「実行」の中間部分にあたるのではないだろうか。
並行処理にするための2つの手法
どちらかというと「データの分解」の方がしっくりくる。機械学習などで前処理を大量のデータに対して実行していく場合が想定しやすい。その一方でタスクの分解というと、メインの処理として逐次に実行すると処理が停止してしまうため、別スレッドやプロセスにて別処理を行うというイメージが強い(eg: メールの送信処理が完了までresponseを返さないのではなく、メールの送信処理は別スレッドにて実行し、メインの処理ではresponseを返してしまう)。というのが、私の2つの手法に対する事前に持ち合わせていた前知識だが、実際にどうなのかを確認していこう。
ここで基本用語が登場。「連続的整合性」は覚えざるを得ない。従来の逐次処理を並行処理に書き換えた際に、逐次処理として実行していた時の最終の結果が不変ではいけないという用語。つまり、並行処理は「連続的整合性」を必ず持っている必要がある。
タスクの分解
タスクとは何か
ここでいうタスクというのは「関数」であったり、処理を連ねた「パイプライン」であったりする。実装されたコードを熟知していればパーツ化可能なタスクを見つけ出すことは容易に行うことが可能だろう。タスクを別スレッドにて実行し、終了するまでの流れは基本的には変わらない。
- タスクを別スレッドにて起動
- タスクを実行していたスレッドが停止、もしくはスリープ(再開可能な状態で待機)
- メインのスレッドにて処理の終了を検知・管理
2つの原則
タスク分解する際の2つのお約束。以下引用。守ろう。
最小でもスレッド数(またはコア数)と同じ数のタスク数にする。
タスク内の処理量(粒度)はタスクやスレッドの管理に伴うオーバーヘッドよりも多くしなければならない
2つ目のがよく分からない。と思ったら、本書に解説がある。狙いは性能を向上させること。また、タスク内の処理量を「粒度」と呼ぶ。タスクを分解することで、メインスレッドにはスレッドの立ち上げ、他スレッドにて実行しているタスクの制御・管理などの本来、逐次処理を記述している際には発生しなかったオーバーヘッド(負荷となる処理)が発生する。スレッドが多くなればなるほど、オーバーヘッドが増えていくとすると、タスク量に対してスレッド数が適切でないと、オーバーヘッドの量が増え、元々の逐次処理よりも処理量が多くなり、性能が悪くor現状維持になってしまう可能性がある。そのために、タスク量とスレッド数のバランスを取るのが重要になる。 そのため、最低でもスレッド数とタスクの数は揃えるのだそうだ。
タスク間の依存性
例えば、算出値をmapやlistに保持する場合に複数のスレッドから行うと、データの整合性が取れなくなる可能性が高い。これがデータへの依存。もう1つが、実行順序に対する依存。Aの値がなければBの値が算出できないなど。
サンプル: 数値積分
ある関数が描く曲線の指定の定義域の下部の領域の面積を求めるタスクの分解を筆者と考える。が、筆者曰く、「読者に頑張ってほしい」とのことで具体的な回答は載っていない。問題の意味を理解する時間は自分にとって重要ではないので、何をすればいいのかだけ何となく分かった。要は積分を行う、定義域をスレッド毎に分割して、各スレッドにて算出された値を合計すれば良いのではないか
データ分解
共通する処理を分割したデータに対してスレッド毎に行う並行化の手法。データを分割して「チャンク(連続性を持つ部分領域?? -> マイクラのチャンクで考えると分かりやすい)」というものを作成して各チャンクを対象にそれぞれのスレッドにてタスクを実行する。となると、以下の２点が重要になる。
- どのようにデータをチャンクに分解するのか
- 各タスクが更新すべきデータにアクセスするには(アクセス可能な保証)
チャンクの分割方法
正直なところ、どんな分割方法を採用したとしても動作はする。しかしながら、分割の方法によって性能が左右される。どのような場合かというと、他のスレッドにて扱われているチャンクを参照する場合に発生する。
仮に4x4の行列を1x1のチャンク16個に分割した場合に他スレッドの全てのチャンクを参照しようとすれば16-1=15のチャンクに対してやりとりを行う必要がある(その分、1回あたりのデータ量は少なくなるだろうが)。これは先ほど話したオーバーヘッドになり得る。また別の場合、2x2のチャンク4個に分割した場合に全てのチャンクを参照しようとすれば4-1=3回のやりとりだけで済む。しかしながら、一度のやりとりで扱うデータ量は増える。そのためどのような形状にチャンクを分割するのか、データを交換するのかが重要になる。一般的には「処理の粒度(タスクの処理量)とチャンクの境界(4x4の行列を2x2の2つに分割した場合の境界は3ブロック)の比率を最大」にすれば良いらしい。
データへのアクセス
アクセス可能な保証というのがタイトルにあるが、実際にはどのようにデータをスレッド同士で参照するかという話。先ほど記述したように、スレッド同士でmessage passingや共有メモリを参照をすることでデータのやり取りを行うが、ここではゴーストセルと呼ばれる、チャンク分割時に各スレッドのストレージ(TLS -> thread local storage)にデータのコピーを行う方法の話がメイン。便利ではあるが、コピーするデータのサイズやコピー回数など、決して万能ではない旨が記述されている。
サンプル: 有限グリッドのライフゲーム
ライムゲームのグリッドを読者の任意のサイズで区切って(チャンクに分割)、並行化するとどうなるのかを考える。先ほどのサンプルと同様で、答えはなく読者が自発的にデータ分割について考えるためのサンプル。ライフゲームは以前、作成したことがあったので何をやればいいのかが何となく分かったので、思ったようにデータ分割について考えてみた
- 全体のグリッド(NxN)をMxMのチャンクに分割(※ただしM < N)
- 分割する際に、生死判定に必要となる隣接の単位グリッドをゴーストセルに確保
- 生死判定のプログラムを単位グリッドにそれぞれのチャンクを持つスレッドにて実行 <- 並列化はココ
- 集計値(次のグリッド)をメインのスレッドに集約
こうすることで更新場所が被ることはなく、最小限の隣接するグリッドのみをゴーストセルに配置するだけで、逐次処理を行なっていたコードにほとんど手を加える必要なく実装可能だと思った。
並列化不可能な場合
タイトルには並列化不可能とあるが、実際に読み進めていると並列化不可能な場合に出くわした際にどのように手を加えれば、並列化可能なコードに書き換えることが出来るかというテクニックがまとまっている。なぜ並列化出来ないかという視点だけ覚えて、後から参照出来るようにリストで例をまとめておく
状態を保つアルゴリズム(eg: 乱数値生成のためのseed値など)
注意が必要だが、ほとんどの場合は書き替え可能。各スレッドのTLSに保存するなど。
なお、過去に実は遭遇済み。確かにseed値をTLSではないが、各タスクの実行前に、それぞれのプロセスでseed値をセットするようにした記憶がある
漸化式(eg: nを求めるのにn-1の値が必要な式)
データをチャンクに分割した場合に先頭以外の各チャンクの一番目の要素が参照する値が算出前なので存在しないため並行化不可となる。多くの場合は並行化不可能だが、第6章で扱う「プリフィックス サム(prefix sum)」という条件を満たす漸化式であれば並行化可能らしい。
該当する処理
nums = [1, 2, 3, 4, 5] calced = list() for n in range(1, 5): calced[n] = nums[n-1]
帰納変数(eg: いわゆるインクリメント変数とかカウンタなどと呼ばれるもの)
実行時に帰納変数の状態が期待する数値とは限らないため、注意。帰納変数の値を一般化することで対処可能(関数にしてしまうのが良さそう)
該当する処理
count = 0 for num in range(1, 100): if num % 2 == 0: count += 1
リダクション(eg: forを回してsumを求めるような列挙可能なデータ構造に対する処理)
sumを求める場合には各スレッドにてチャンクより合計値を算出し、メインスレッドに集約して合計するなどデータのやり取りを工夫すれば対処可能。
該当する処理
sum_ = 0 for n in range(1, 1000, 3): sum += n
ループ内依存(eg: 過去の算出値を参照する場合など -> 漸化式にニュアンスは近い)
コードの書き換えによって参照する方法を更新することで対応可能だが、場合によっては処理量が増えることがある模様。
該当する処理
import random calced = list() weights = [random.random() for _ in range(500)] for n in range(5, 505): calced[n-5] = weights[n-5] * n
並行化する際の設計時に考慮する4つのスコア
左に本書の単語、括弧内に私が分かりやすく砕いた単語を記述しておく。
- 1.実行効率(パフォーマンス)
- 2.簡潔性(シンプルさ)
- 3.可搬性(使い回しのしやすさ)
- 4.スケーラビリティ
筆者の観点で上記4つのスコアに優先順位をつけると以下のようになる。
4 > 3 > 1, 2
スケール出来ることが一番重要で、これは時代が変化してプロセッサのコア数が増えたとしても問題なく、コードが動作することを重要視しているからだそうだ。
以上
