田舎で並行処理の夢を見る

試したこと、需要がないかもしれないけど細々とアウトプットしてます

【並行コンピューティング技法】全体の構成と得られる知識 & 第1章のまとめ

今回の購入物

前から買おうとは思っていたが、読む時間ないなぁと手を出さずにいた「並行コンピューティング技法」をたまたま立ち寄った本屋にて発見し、思い切って購入。最近、学習に対するモチベーションが下がっているので気持ち新たにスタートするためにも購入

f:id:takamizawa46:20200202140626j:plain:h550

著者について

こちらの初版は2009年で、すでに10年以上経過していることになる(早いなぁ)。著者のClayさんの現職場はIntelで2020年時点で16年の勤務経歴があり、20年以上に渡りマルチコア/マルチスレッドのアルゴリズムなどのコード実装に関わっている大ベテランだ。計算機科学のPhDでもあり、要はめちゃくちゃ強い人。ひえぇ...
LinkedIn: clay-breshears

全体の構成と本書から得られる知識について

本書を詳細に読み始める前に、最初に見出しに目を通して全体の構成がどのようになっているかを考察する。その上で自分が、今から読む本から何の情報を得たいのか、何が分かっていないかをリスト化しておき、頭の中か、紙などにメモしておく。そのためにも、まずは、見出しから考察した本書の全体の構造を考えてみる。本書は第1章から始まり、250程のページを経由して第11章までの構成を持つ。第11章までの構成をざっくりと4つに縮約すると以下のようになった。

  • 1.基礎知識:(並列と並行って何が違うの。スレッドとは、分散メモリとは..etc)
  • 2.並行プログラミングの実装における諸注意・考え方
  • 3.実践(ソートアルゴリズムなどを並行アルゴリズムに書き換え)
  • 4.並行プログラミングでのデバッグ、検証方法について

なるほど。まえがきにある通りに、この一冊を読み通せば、実際に並行処理を設計 -> 実装 -> 検証する上でのポイント、考え方が身に付くようだ。現段階で自分の中に持ち合わせていない知識は1.基礎知識以外のほとんど。よって、この書籍を読み通すことで、今持っている

  • 並行/配列処理
  • プロセス/スレッド/マルチスレッド/マルチコア
  • 分散処理/ノード
  • 分散メモリ/共通メモリ
  • ソートアルゴリズムなど

といった基礎的な単語レベルの知識をどのように設計、実装に転用するかを理解するのが第一目標。その上で検証方法やパフォーマンスチューニングの方法を学ぶことを第二目標とした

第1章

第1章を読む理由

自分の持っている知識が著者の認識と正しいかを確認するため。今更だけど、「並行」と「並列」の違いって確かによく分からない(説明出来ない)ので読んでみる。加えて第1章から得たい知識を頭の中に図化したものを書き出してみた。

f:id:takamizawa46:20200202140650j:plain:h550

この図を完成させるように第1章を読み進めた

第1章のまとめ

並行と並列の違い

まず並行と並列という単語の意味がどのように違うのか。自分は並列処理というのはA,B,C,Dという異なる処理を同時に実行させるもので、並行処理はA,A,A,Aという同じ処理を同時に実行させるものだと思っていたが、実際は大きく違っていた。そもそも並行と並列は同軸にはなくて関係上は

  • 並行
    • 並列

というようになる。並行は並列を内包している。書籍から「並行・並列」の項目を引用する

並行とは複数の動作を実行可能状態に保てる状態を備えていること
並列とは複数の動作を同時に実行できる場合のこと

自分の持っていた知識とは全然違っていた。分かりやすく記憶するためにイメージづけをしておく

影分身をして100人分、一気に修行する
  • 並行 -> 修行を開始して修行中の状態
  • 並列 -> 100人に分身が完了した状態

スレッド化の4ステップ

めちゃシンプル。機械学習の開発フローに似てるかも

  • スレッド化したいところ(独立可能な処理 -> 関数レベル、もしくはパイプライン)を見つける
    • アプリの実装が完了してからの方が望ましい。実装を熟知していればボトルネックを指摘できるが、そうでないときは、処理の計測ツールなどを使ってボトルネックを検出するのもok
  • 実装(本書を読み進めてねとある)
  • 実装したコードの検証と修正
  • パフォーマンスチューニング

共有メモリと分散メモリでの実装

言われてみれば当然のことだが、気になったところだけを簡単にメモっておく

共通部分
  • 分割方法 -> データを分割するのか処理を分割するのか
  • データ量やメモリ使用量によって動的にスケールするかどうか(k8sみたいもん)
異なる部分
  • データの同期の確保 -> 共有メモリへの参照・更新が非同期で行われるとデータの状態が思いもよらない物になるため同期を取る必要がある。
    • 例: 2人が同時にチケットの予約をした場合にチケットはどちらの物にするのか
    • 分散メモリではElixir, Erlangのようにmessage passing(メッセージの送受)によってデータの同期を取る
  • 排他制御 -> データを同期させるために共有メモリを参照・更新できるスレッドを制限する
PRAM(Parallel Random Access Machine)

理解のために簡単に...。複数のCPUが1つ以上のメモリに接続しているRAMモデルを変形した構成。メモリへの参照(読み取り)と更新は「並行 / 排他」のどちらかの条件で実行する(権限のようなイメージ)。

  • 並行 -> 誰(どのスレッド)でもOK
  • 排他 -> 参照もしくは更新できるのは1人(特定のCPUで実行される1スレッド)だけ
Producer-Consumer

共有メモリ上にqueueを配置して、タスクを格納しておき、手が空いたスレッドからqueueを参照してdequeueしてタスクを実行を繰り返すことで効率的に処理を行う

リードライトロック

共有メモリへの参照は値の変化を発生させないため、問題ないが、更新はダメ。更新処理が走った際には参照を一時的にストップ(参照の依頼を待ち状態にする)。更新処理が終了した後に参照が再び可能になる。

第1章については以上です