おふくろさまより愛をこめて

mmmpa ふとしです。誠実なプログラミングを心がけたい。

並行コンピューティング技法という本をやり終えました。

夏季休暇中 (8/11 - 8/19) の課題としてはじめた 並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング という本を、先日ようやくやり終えました。

久しぶりに技術書的な本を一冊やりおえたので、本の紹介や思い出日記を書きます。

今回の学習について

なぜやろうと思ったか。なぜわたしに必要だと思ったか。

仕事では Ruby、JavaScript を主に使っていますが、個人的には Go 言語を使いこなせるようになりたいと思っています。

Go 言語には並列処理を簡単にハンドリングできる goroutine という仕組みがあります。並列処理のための排他制御や終了を取りあつかうための仕組みも準備されており、使用開始は容易です。

しかし、何を並列化できるか、並列化をどのように行うかという素養が全くありませんでした。外部 API に対するリクエストなど並列化のメリットがわかりやすいものはともかく、一般的な処理になるとお手上げです。

そこで言語の機能やライブラリの使用法ではなく、並列化自体を解説しているこの本をやろうと思い至りました。

学習方法について

この本をやっている最中に Learn Better――頭の使い方が変わり、学びが深まる6つのステップ という本を読みました。

  • 学習する対象の価値を見出す
  • 具体的な目標を設定する
  • 学習対象は少し難しいものを選ぶ
  • 学習対象へ能動的に行動する (読む・聞く・写すなど受動行動だけではなく、自分や他人に対して説明・要約など行う)
  • 時間をおいた分散学習 (一度やって終わりではなく、時間をおいて再度同じことを学ぶ)

など、よりよく学習するための方法が紹介されています。

今回たまたまいくつかの点を満たして学習を開始しました。能動的にという点は当初より 読書メモ を残すということで無意識にやっていましたが、メモをより明確な意図を持って行うようになりました。

時間をおくという点については、あるアルゴリズムを並列化した直後ではなく、次のアルゴリズムの途中かそれが終わってからメモをおこすことで実践してみました。本ではなく実装前にノートに書いたメモ書きや記憶やコードを頼りに書くことにより、再び考える機会が訪れて良かったように思います。

この日記の後段でも作成した図とともに学習した内容について触れています。これもまた分散学習の一助になるように思います。

説明の有効性

説明の有効性については、最近読んだ 知ってるつもり――無知の科学 でも言及されていました。学習という観点ではなく、人がどれだけ自分の無知に無自覚であるかを検査する方法 (物事を説明しようとすることにより自分がどれだけその物事について知らないかを自覚する) としての紹介でした。

自分に対して説明することにより本当に理解できたかどうか検査できるので、有用性は確かなものであるようです。(実際コードを書きおえて動くようになってから説明を書いてみて、理解がずれていることに気づいたアルゴリズムがありました)

本について

前半

並列化において念頭におかなければならないことを解説しています。

  • 逐次処理で行われていたものを並列化するので、
    • 並列化処理を実装すること自体がオーバーヘッドであること。
    • 並列化実行コストが必ずオーバーヘッドであること。
  • 適切な処理の粒度にしないと無用なオーバーヘッドを生むこと。
  • 並列化スレッド同士の処理順序は絶対に予測不可能なこと。
  • 処理の中にはある処理が出した結果が他の処理に影響を与える場合があり、それをなんらかの方法で並列化した処理同士で共有する必要があること。
  • 処理の中には同じデータ領域を読み書きする場合があり、排他制御が必要なこと。
  • 扱うデータの範囲によって並列化する場合は、そのデータの形によって最終的なデータ統合の処理の量が変わること。

など、実際に並列化を数多く行ってきた著者が、実際的な問題として語ってくれます。

後半

よく知られたアルゴリズムを並列化することにより、並列化処理で実際に直面する問題への対応を解説しています。

処理の順序が決まっていて並列化が無理そうなソートアルゴリズムを並列化します。また、逆に各処理の独立性が高く並列化するのが楽そうなアルゴリズムにおいては、再帰をループに書きかえたり、終了条件を明確化に設定しなければならないなど、処理だけではない実装のオーバーヘッドについても体験できます。

以下のようなよく知られたアルゴリズムを並列化しました。

  • ソートの章: バブルソート、シェルソート、クイックソート、奇偶転置ソート、基数交換ソート、直接基数ソート
  • サーチの章: 線形探索、二分探索 (を並列化する n 分探索)
  • グラフの章: 深さ優先探索、Floyd アルゴリズム (全頂点対最短経路) 、Prim アルゴリズム (最小全域木)

基本的なアルゴリズムは以前別の本でも学習しましたが、並列化するにあたって長時間接することにより、より具体的に理解できたような気がします。

学習中の思い出

学習中に図を多く描いたので、せっかくなので思い出話とともに羅列します。

図はほとんど whimsical で作成しました。機能が少なく、選択できる色も少ないので、逆に安定した図が描けるので便利です。

ただ、グラフは描きづらかったので、そこは Cacoo を使用しました。

データの形状について

分割したデータの形状によっても処理量が変わるという目からウロコな解説でした。ゴーストセルはスレッド間で競合するデータをどうやって持つかの一例です。

imageimage

データ分解について

これは学習中に書いた別の日記で言及した処理の図です。要は for i := threadNumber; i < l; i += threadTotalCount で回すとスレッド数分に分割された処理量になるという話でした。

imageimage

プリフィックススキャン

プリフィックススキャンは配列の各要素を足すなどの処理を加えていくので、一見並列化が難しそうな処理です。しかし、各スレッドの結果をプリフィックススキャンした結果を各スレッドに適用するとちゃんと結果が得られるという話でした。

imageimage

PRAM

無限の CPU を持つ抽象機械による並列和はこうなるけど実際にはそんなものないから使えないよ。

という話が最初の方であるのですが、各スレッドが出した結果をリダクションするときにはスレッド数分 (大体の場合において CPU 数分) のデータしかないから使えるよねと突如復活する話でした。

image

並列ウェイブフロント

バブルソートは順序依存が激しい処理ですが、並列化はできるという話でした。

imageimage

奇偶転置ソート

他のスレッドの割当範囲も更新するんだけど、アルゴリズムの特性上問題ないんだよという話でした。当初、データ分割量を必ず偶数にしないといけないと気づかなくて、データ競合して大変でした。

imageimage

シェルソート

遠くからの値をとっておおまかにソートしてから挿入ソートするとすごく速くなるというシェルソートの話です。実際の h はいい感じの速度がでるステップがあります。 (…, 121, 40, 13, 4, 1)

imageimage

クイックソート

おなじみクイックソートです。pivot 指定されたものと length == 1 になった部分は整列済みとして扱いカウント、カウントが配列の長さと同じになるのが終了条件という話でした。

image

基数交換ソート

ビットで行うクイックソート (pivot ナシ) ですね。終了条件は length == 1 になったもの、もしくはビットが末尾に至ったものという点で、並列クイックソートとは少しちがうのがミソという話です。

直接基数ソートは図を描くのが大変なので諦めて table にしました。こちらは末尾から任意のビット数でソートしていきます。

プリフィックススキャンによる array パッキングがミソです。

image

base 1 pass 2 pass 3 pass
485 340 526 041
041 041 739 188
340 485 340 340
526 526 041 387
188 387 485 485
739 188 387 488
489 988 188 489
387 488 988 526
988 739 488 739
488 489 489 988

線形探索

線形探索です。サーチは全データをさわりますが、探索は見つかった時点で処理が終わりなので、並列化においては他のスレッドにその終わりをどう伝えるかがミソになってくるという話です。

imageimage

n 分探索

範囲ではなくあくまで分割位置で探索する n 分探索で、毎ループごとに待ち合わせる必要があります。

imageimage

グラフ

おなじみグラフです。エッジ情報を行列で扱うという方法を知りませんでした。便利ですね。

imageimageimage

深さ優先探索スタック

深さ優先探索を再帰ではなくループにした場合、次に訪れるノードの管理はスタックで行うという図です。キューではないのがミソでした。

image

全域木、最小全域木

実質最終章のシメの問題でした。

imageimage

まとめ

一冊全てやり終えると気持ちが良い。