【第1回: データ分析xブログ】データ分析の力でPV数は増やせるのか。現状を分析して目標を立てるまで

この記事を書いた理由

GoogleアナリティクスやGoogleサーチコンソールといった優秀なツールがあり、使い方を解説する記事が多数ある一方で

• どう使えばPV数が増えるのか
• 収益を生み出すには何に注目するのか

といったテーマの記事が非常に少ないことに気づいた。現状(2020/02/16時点)で1日の平均PV数が「10」のこのブログがGoogleアナリティクスやGoogleサーチコンソールのデータを使用したデータ分析によってPV数が増えていくのかを記録することが一番の目的になる。

ブログの現状

プログラミング関連(特にElixirという言語)の記事をメインに興味のあることをブログを書いている。2019年の3月にブログを開始して、はや１周年を迎えようとしており、書いた記事数は2020/02/16日時点で「89件」。99％が3ヶ月以内にブログを挫折するらしいのでよく続いているなと自分でも思う。ほほとんど「アウトプットしたい」という気持ちだけで続いている。

:
:

と思っていたが、自分のブログのPV数(ページビュー)を最近、気にするようになって落ち込んでいる。

(バァァァァアアアン)

一年もやっててPV数の合計はだいたい3,600程度。1日のPV数は多くて30~40ぐらいで、低い時は5以下といった具合。つまり何が言いたいのかというと「書いた記事をほとんど見てもらえない」ということ。ショック...

この企画について

普通に不労所得ほしいです

どんだけ良い記事を書いていたと思っていても、見てもらえなければ自己満足のメモ。それはそれで良いけど、PV数が少ないということは収益の可能性も低いということ。2020年の抱負は「何かしらでマネタイズする」であり、不労所得を生み出したい。何故、不労所得が欲しいかというと3つの理由がある。

• 心の余裕を保つため
• 時間労働の限界性を感じたから
• 母親に楽をさせてあげたい

せっかくブログをやっていて独自ドメインも取ってるし、はてなもproで契約してるのなら最低限、ブログの維持費分だけでも収益を出したいところ。

収益を生み出すためには

じゃあ、どうやったら収益って増えるのかを考えると最もシンプルな答えは「PV数を増やすこと」になる。アドセンスなりアフェリエイトなりまずは見てもらえる機会を増やすこと。じゃあ、どうやってPV数って増やせるのかを考えると、答えはめちゃくちゃ複雑で明確な解はない。

とはいえ、ブログで収益を生み出している先駆者の方々は存在しており、実際に結果を出している。こういう時は先駆者の考えや施策を調べまくる。どうやら、彼らが言うには収益を増やすために「キーワードの分析」が非常に重要らしい。

• どんなキーワードがPV数を稼いでいるのか
• google検索結果の1ページ目を獲得出来ている記事はどれだけあるか

など...

しかしながら、この辺りのノウハウは有料であったり(買えよと言わないで)、絶妙に内部化されており、何となくでしか情報を手に入れることが出来ない。マネをするのも戦略としては当然考えたが、自分のブログのスタイルを変えることはしたくないのでマネできる所だけマネはする。そんなことを考えていてあることに気づいた。

「業務でデータ分析やってるし、勉強ついでに分析もやってマネタイズ出来たら最高じゃね？」

今回の分析で知見を貯めれば、ついでにデータ分析の知見も貯まるし、業務にも還元される上に、お金も貰えるかもしれないと考えるとやらない理由がない ということでこの企画をスタートしてみた。

実践編

分析に使用している全体のコードについてはgithubを参照下さい
github.com

対象のデータについて

自分のドメインを登録済みのGoogleサーチコンソール(通称:サチコ)から検索パフォーマンスのデータを.csv形式でダウンロード。

downloadのディレクトリに.csv形式のファイルが生成されているので、さっそく開いてみるが文字化け。

しかもMicrosoft Officeのライセンス切れてて、Excelも使えない。まぁ、元々Excelでやるつもりはなかったので、データ分析のマストアイテムjupyter notebook(いつもの)を立ち上げてダウンロードしたcsvを読み込むことに。

都合が良いので先にカラムの説明を少々。何故かというと日本語表記だと参照する際に面倒なので、英語表記にしているからで「自分のcsvにはそんなカラムはないんですけど」という誤解を生み出さないため。
(左: 元のカラム名, 右: 変換後のカラム名)

• 検索キーワード -> keyword
• クリック数 -> click_num
• 表示回数 -> display_num
• CTR -> ctr(検索結果として表示された時にどれだけクリックされているかの割合)
• 掲載順位 -> top_n

pandasのpd.read_csv()という関数を使って読み込んだ結果(jupyter notebookの1セルで見えるところだけ)

すでに色々と思うことがあるが、感想としては色んなキーワードで調べられているなぁという程度...。ここから何をすれば良いのやら。順に考えていこう。

データの概要を見てみよう

何から始めて良いのか恐ろしいほど、全く分からないので、まずは定番データの概要を見てみる。pandasのdescribe()を使って表示したものがこちら

これだけでも色々なことが分かる。気になったことをリスト出ししてみた。

• mean: top_nより -> 掲載順位は大体が4ページ目ぐらい -> 1ページ以降を閲覧する割合はかなり低かったのでこれは致命的
• min: top_nより -> 検索すれば上から2番目(1ページ目)に表示される記事があることに驚きを隠せない
• 50%: top_nより -> 50%の時点で掲載順位の値が43(すなわち4ページ目)であるため、半数以上の記事は検索からの流入を全く期待出来ない
• 25%: top_nより -> 25%の記事は悪くても2ページ以内に表示されている様で20記事ぐらいは良い位置を取っている
• 全体的: click_numより -> めちゃくちゃ低い
• 全体的: display_numより -> この値から何を感じて良いのか分からない

ネガティブな所に目が行きがちだが、上から2番目に表示されている記事があったり、1ページ目に登場する記事が割とあったりとで素直に驚いた。PV数を稼ぐ上で「どれだけ上位の検索順位をキープできるか」かが重要だと判断出来るので、どのようなキーワードの組み合わせで1ページ目を抑えているのかを次に見ていこう。

1ページを取っているキーワード

その前にtop_nの数値では何ページ目に表示されるのかが直感的に分からないので何ページ目に表示されるかを示すpage_numというカラムを追加して、page_numの値が1になるキーワードだけを抽出した。合わせてctrの値が0以外のデータ(少なくとも1回はクリックされている)と0のデータに分けてみた。

表示されるページが1ページかつ、クリックされたことがあるキーワードの組み合わせ

見たまんまの考察

• mecabとjanome(形態素解析器)の組み合わせ、もしくは「janome + 何か」が強い -> janomeの記事は2件だけなのになんじゃこれ
• メインでやってるElixir(プログラミング言語)に関係するキーワードがちらほら見つかる
• 地味にcloud functionが強くて高いctr値を保持している -> cloud fuctionの記事も2つのみだが

表示されるページが1ページかつ、クリックされたことががないキーワードの組み合わせ

見たまんまの考察

• やはり1ページに登場しているのは「janome, Elixir(elixir), cloud function」に関係するキーワードの組み合わせ
• elixir const多すぎ。1ページを取ってるのでctrあげたい
• connpass 勉強会で1ページ取ってるのやばい。ctrあげたい
• Elixirに関連する入門記事や、基礎知識に関するキーワードが皆無。これはつらい(ほとんどがElixirに関する初級~中級の記事なため)

比較としてpage_numが4以上のキーワードの組み合わせも抽出した。数が多すぎるので部分的に。

見たまんまの考察

• 訳の分からない単語が多い
• ビッグネームの単語が多くて、なぜかヒットしてしまいページが大きな数値に
• とはいいつつも、個人的には落としたくない単語もある(elixir enum mapとか、おそらく海外からの検索だろうけど)

一応page_num=2(2ページ目に表示)に該当するデータも最後に確認。個人的にElixir(elixir)とセットで調べられている単語を知りたいのでElixirを含むキーワードのみを抽出。

見たまんまの考察

• elixir 並行処理が2ページ目って凄い。ただクリックされていないので残念
• 他のプログラミング言語 + Elixir(elixir) という組み合わせが多い。「python使いの人のためのElixirの始め方」みたいな記事書くと良さそう
• コアな単語が少なくElixir(elixir) + syntax が多い。
• 特に狙っていたキーワードの組み合わせがなくて消化不良感

頻出キーワードからの考察

自分のブログを第3者から見た時(検索した時)にどのようなジャンルを扱っているブログなのかを考察するために、現時点で検索に使用されているキーワードをスペース区切りでsplitしたものをカウントしてみた。結果は降順ソート済みで数多いので、上位20件と下位10件をお見せします。

[No.1]: elixir: 86
[No.2]: python: 74
[No.3]: firebase: 66
[No.4]: functions: 47
[No.5]: cloud: 46
[No.6]: golang: 33
[No.7]: mecab: 31
[No.8]: janome: 22
[No.9]: 形態素解析: 22
[No.10]: deploy: 20
[No.11]: function: 18
[No.12]: authentication: 13
[No.13]: websocket: 13
[No.14]: node: 11
[No.15]: ntt: 11
[No.16]: バイト: 9
[No.17]: login: 8
[No.18]: 並行処理: 8
[No.19]: tokenizer: 7
[No.20]: request: 7
:
[No.442]: okb: 1
[No.443]: 公務員から民間企業に転職した結果: 1
[No.444]: 電話回線: 1
[No.445]: 基礎解析: 1
[No.446]: 電話加入: 1
[No.447]: ipアドレス: 1
[No.448]: 企業: 1
[No.449]: 導線解析: 1
[No.450]: できなくてもいい: 1
[No.451]: 難しい: 1

(誰がokbで調べたんだ...)

見たまんまの考察

今までの考察通り、現在、自分のブログは以下のジャンルに支えられていることが分かる。

• Elixir(elixir)
• python
• janome mecab(形態素解析)
• cloud function

Elixir(elixir)が1位になっているのは嬉しいのだけど、このブログにかけている労力はElixir(elixir) > python > janome / mecab, cloud functionの順に大きいが、数字ではほとんど差がないので元々、単語が持っているトレンド性、つまりは人気度が全然違うんだろうなと思う。そこでGoogle Trendsを使って、人気度を比較してみた。ここで出ている数値は「人気度」ということでどのように算出されているかはよく分からない。

https://trends.google.co.jp/trends/explore?geo=JP&q=elixir,python

pythonが平均で84という人気度を維持する中、Elixir(elixir)は平均も1、いつでも1...。これは確かに単語のパワーが違いすぎると認めざるを得ない。

これからすべきこと

分析から分かったこと

• 多くの記事の掲載順位は４ページ目ぐらい で、これは致命的
• 25%の記事は悪くても2ページ以内に表示されている様で20記事ぐらいは良い位置を取っている
• 現状のブログを支えているキーワードは「elixir, python, janome mecab, cloud function」でほとんどのPVはこの4つの関連するキーワードの組み合わせで獲得されている
• 間違いなくキーワードにはパワーの優劣がある。elixirをメインで扱いたいがptyhonには遠く及ばない

反省すべきこと

キーワードの選定を全く意識していなかった。書きたいものを書くだけではPVが稼げないのは数字から分かる。残念ながらElixir(elixir)というトピックだけではPVを稼ぐことは難しいため、何かしらの戦略が必要になってくるが脳筋で「Elixir(elixir)かつコアな記事」を書き続けていたことを反省。それもそれでブログとしてはありだけど、それだけではなく、流入を行うための記事も必要になる。

掲げた戦略

• Elixir(elixir)という単語だけではパワーに欠けるため、検索キーワードにも見られた「他プログラミング言語 x Elixir(elixir)」という分野を狙っていく(eg: python好きのためのElixir(elixir)入門みたいな)
• PVを稼いでいると思われる記事が何となく分かったので検索されているキーワードの組み合わせの形に合うようにリライトを行う
• パワーのある単語で1ページ目を狙う(eg: 「プログラミング 独学」, 「プログラミング 挫折」など)

次回について

今回の分析で分かったことと、掲げた戦略に対する取り組みを行い、どれだけPV数が変化するのかを次回の記事にて報告しようと思います。自分自身、今まで学んだ分析に合わせて、トライアンドエラーで得られる知見が凄い楽しみかつ、PV数が増えるかもしれないという明確な報酬があるため気合いが入りまくっています。

では、第1回の結果をお楽しみに。

【第17回清流elixir勉強会】Elixirを用いた並行和アルゴリズムの実装

トピック

あけましておめでとうございます。1月2月は色々と忙しくて、全く清流elixirにて勉強会を開催できず...
2ヶ月ぶりの開催となりましたが常連の方、新規の方、リモートでの接続、多くの方に参加して頂けました。ありがとうございました。ハッピーターンを持ち合わせていったのですが気づいたら自分が半分以上食べてしまっていました。忍びない..

elixir-sr.connpass.com

清流elixir-infomation
開催場所: 丸の内(愛知)
参加人数: 3 -> 6 update!
コミュニティ参加人数 : 37 -> 40
2020/02/14現在

第17の勉強会について

今回は新年最初の勉強会であったため、メインテーマがお恥ずかしながら未定であったため、「もくもく会」という形で勉強会を開催しました。各々、自身の取り組みたい内容について約2時間、取り組みました。僕は最近読み始めた「並行コンピューティング技法」の書籍で第6章で紹介されている「並行和」というアルゴリズムの実装をElixirで挑戦してみました。書籍にはOpenMPとPthreadでのコードが記載されているのですが中々のボリュームな上、OpenMPやPthreadは計算機科学の分野で広く仕様されるライブラリため親しみが全くありません。これを「Elixirで書き換えたらどんなもんやろなぁ」という単純な興味からのスタートです。

www.okb-shelf.work

実装したコードはこちら
github.com

並行和について

詳しくは「並行コンピューティング技法 第6章のまとめ」という記事を後日出し、そちらで解説を行うが、ざっくりとした説明をしておく。何かしらのデータが手元に存在しているとして、それはN個の要素を持つ配列だと考える。このN個の要素を持つ配列をM個の間隔でデータを分割してチャンクを作成する。作成したチャンクをチャンク数分だけ用意したスレッド、もしくはプロセスの内部で配列の要素を合計した数値を算出する。そして、それぞれのスレッド、もしくはプロセスによって合計された値をメインのスレッド、もしくはプロセスにて集約する。この一連の処理を「並行和」と言っている。

# N個(今回はN=10)の要素を持つ配列を用意
[1,2,3,4,5,6,7,8,9,10]

# 用意したデータをM(今回はM=2)の間隔で分割してチャンクを作成
[
  [1,2],
  [3,4],
  [5,6],
  [7,8],
  [9,10]
]

# 作成したチャンクをそれぞれのスレッド、もしくはプロセスに割り当てて合計値を算出する
[
  [1+2],
  [3+4],
  [5+6],
  [7+8],
  [9+10],
]

# それぞれのスレッド、もしくはプロセスによって算出された合計値をメインのスレッド、もしくはプロセスにて合計
[3 + 7 + 11 + 15 + 19] -> 55

この一連の処理をElixirを用いて作成していく。

暗黙の仕様について

手元に丁度、頃合いのデータがないこともあり、作成するデータの性質と自動でスケールさせるかについて実装前に決めておく。以下の仕様(といっても、作成するのは自分だけなので暗黙の仕様ということで)を実装にあたり遵守する。

• データ分割による並行化を行い、データのサイズによって自動でスケール(起動させるプロセス数をコントロール)するようにする
• データはN個の要素を持つ配列を採用。要素はint型の上限値を定めて生成するランダム値

この勉強会の2時間の間で何とか動く所までは実装することが出来た。といっても、並行処理に関してはElixirは実装されているモジュールが優秀なため、ほとんど自前で作成したものはなく、ほとんどがwrap関数とhelper関数になった。さすがのElixir

並行処理の起動までの流れ

実装についてはgithubの方を参照して頂ければ良いので全体の処理の流れを解説しておく。

• N個のランダム値の要素を持つ配列を用意
• M個の間隔でチャンクに分割
• 分割したチャンクをプロセスの専属データとして、プロセスを新規で立ち上げる
• それぞれのプロセスにて合計値(sum)を算出
• メインのプロセスにて各プロセスの合計値を合計

この一連の処理をまとめているのが以下のファイル
./parallel_sum_ex/lib/parallel_sum.ex

defmodule ParallelSum do
  @moduledoc """
    メインモジュール。他モジュールにて抽象化した関数群をpipeline化する
  """

  @doc """
    並行処理によって合計値を算出するpipeline関数
  """
  def parallel_exec(_, ""), do: :error
  def parallel_exec([], _), do: :error
  def parallel_exec(data_size, mode)  do
    # ランダム値を要素に持つリストを分割したチャンクデータを作成
    dataset =
      ParallelSum.DataCreater.create_N_size_list(data_size)
      |> ParallelSum.Scheduler.list_spliter()

    # 立ち上げるプロセス数を算出
    process_num = ParallelSum.Scheduler.calc_total_process(data_size)

    # プロセスを立ち上げて並行和を算出
    parallel_sum = ParallelSum.Scheduler.start_task(mode, dataset, process_num)
    Enum.sum(parallel_sum)
  end
end

別ファイルにて定義したモジュール内関数を利用して先ほどの流れを実行していく。自動スケールについてだが、スケール、すなわち立ち上げるプロセス数は全データのサイズをconfigにて設定した1プロセスが扱える最大要素数の数によって決定される。算出式はめちゃくちゃシンプルで全データ数を1プロセセスが扱える最大要素数で割るだけ。仮にデータ数が1000であり、最大要素数が100であれば10個のプロセスを立ち上げることになる。

./parallel_sum_ex/lib/scheduler.ex

defmodule ParallelSum.Scheduler do
  @moduledoc """
    データのチャンク分割とプロセスの起動の一連のスケジューリングを実行するための関数
    他プロセスによるタスク実行はmessage passingでやると手間なのでTaskに任せる
  """

  @doc """
    configに設定された1chunkが扱える最大要素数を元に立ち上げるべきプロセスの総数を算出する
    processs_num = 配列の要素数 / １チャンク辺りの扱える要素の最大値
  """
  def calc_total_process(data_size) do
    each_chunk_size_max = ParallelSum.Config.each_chunk_list_size_limit()
    div(data_size, each_chunk_size_max)
  end
end

少しだけテクいことをしているとすれば、Taskモジュールを仕様したタスクを持つプロセスの作成と実行結果の受け取り部分。過去に何度も同じことをやったことがあるが、Task.async()に実行する無名関数を渡して、生成されたプロセスのpidを要素に持つリストを作成する。パイプライン演算子を仕様して、立ち上げたプロセスの実行結果をTask.await()とすることで受け取っていく。割と頻出の処理なので新規性は特にない(はず)。

Taskの使い方は過去の記事にまとめているのでご参照ください。

www.okb-shelf.work

再帰関数とEnum.sum()を使った際でパフォーマンスに差が出来るのかを後々、測定したいので第1引数に対してパターンマッチを行い、実行する無名関数を変化させている。あいかわらずパターンマッチ半端ないって。
./parallel_sum_ex/lib/scheduler.ex

defmodule ParallelSum.Scheduler do
  @moduledoc """
    データのチャンク分割とプロセスの起動の一連のスケジューリングを実行するための関数
    他プロセスによるタスク実行はmessage passingでやると手間なのでTaskに任せる
  """

  @doc """
    分割されたデータと算出された立ち上げるプロセス数を元にTask moduleを起動して再帰関数によって集計処理を実行
    各プロセスが算出した合計値がリストになって返ってくる
  """
  def start_task(_, lst, _) when length(lst) == 0, do: :error
  def start_task(_, _, 0), do: :error
  def start_task("", _, _), do: :error

  def start_task("recursive", splited_lst, process_num) do
    # プロセスを起動し、チャンクを割り当て
    Enum.map(1..process_num, fn index ->
      Task.async(fn -> ParallelSum.Sum.recurcive_sum(Enum.at(splited_lst, index-1)) end)
    end)
    |> Enum.map(fn task -> Task.await(task) end)
  end

  def start_task("enum", splited_lst, process_num) do
    # プロセスを起動し、チャンクを割り当て
    Enum.map(1..process_num, fn index ->
      Task.async(fn -> ParallelSum.Sum.sum(Enum.at(splited_lst, index-1)) end)
    end)
    |> Enum.map(fn task -> Task.await(task) end)
  end
end

Usage

今回は実行結果を確認する部分までしか実装できなかった。本当はメモリ使用率や経過時間なども出力して、グラフ化して色々と満たされたいのだがご愛嬌。実行にはElixirがインストール済みである必要がある。

# iexを立ち上げる
> $ iex -S mix


# N -> 配列の要素数
# mode -> sumの集計方法(recurcive -> 再帰処理, enum -> Enum.sum() のどちらか)

# 並行和(複数プロセスによる算出)
iex> ParallelSum.parallel_exec(N, mode)

# 逐次和(単一プロセスによる算出)
iex> ParallelSum.serial_exec(N, mode)

実行結果

iex(1)> ParallelSum.parallel_exec(100_000, "recursive")
50084347

iex(2)> ParallelSum.parallel_exec(100_000, "enum")     
50113202

iex(3)> ParallelSum.serial_exec(100_000, "recursive")
50099269

iex(4)> ParallelSum.serial_exec(100_000, "enum")     
50106982

実装して気づいたけど、明らかに逐次処理の方が速い。何でだろう...🤔
プロセスの立ち上げやデータ参照等がオーバーヘッドになっているということだろうけど厳密な検証は実行時間などを確認出来る様にしてから行なっていこう

参加者の方々の成果物

確認できるものを一部、参照させて頂きます。

kikuyutaさん

意外にさっくり出来た。半固定抵抗の位置をログ出力してます。#清流Elixir
I have just finished to make a program to indicate a potentiometer register with #Nerves at #SeryuElixir. pic.twitter.com/gffCqSgOzD

— KIKUCHI Yutaka ☀ 菊池 豊 (@kikuyuta) 2020年2月14日

自分はハードウェアはさっぱりですが、内部処理の仕組みについて教えて頂きました。

直接見せて頂きました。今日は絶好調だっと伺っています。これはセンサーの値を常駐プロセスで監視して差分を検知したらメインのプロセスにメッセージ送ってるという様な仕組みなんだろうか…🤔 https://t.co/d0J8KGZHw7

— OKB (@sing_mascle69) 2020年2月14日

GKBR56さん
ElixirでMMORPGを作られている方です。youtubeで実際に動くところを確認することが出来ます。オンラインゲームの仕組みがどうなっているか自分はさっぱりですが、最初はシンプルなechoサーバーを作るところから始めたと伺いました。

https://www.youtube.com/watch?v=nwxHhOcTHBw

mmo.ex デモ動画

近日、新たな動画を公開予定だそうです。Qiitaの記事は以下を参照下さい
qiita.com

【並行コンピューティング技法】第3章のまとめ

前回までのあらすじ

実際に並行処理を記述する際にどのように手法を決めて実装していくのかという話が第2章のメインであった。 並行処理の方針を決める手法は以下の2通りで、第2章ではそれぞれの特徴やマナー、サンプルに触れながら内容が進んでいく。

• タスク分解
• データ分解(データをチャンクに分解)

加えて、筆者が並行処理を作成する際に、何を重要としているか(1にスケーラビリティ, 2にパフォーマンス)という話も登場した。詳細は、前回の記事をご参照下さい。

www.okb-shelf.work

第3章

まずは、いつものように見出しからどんな情報が得られるかを観察。第3章は大きく以下のような構成になっている。

• 並行処理(並行アルゴリズム)の検証方法 -> どのように連続的整合性を確認するのか
• 実際に2つのスレッドを用いたアルゴリズムをベースに筆者と共に検証(4段階)
• 並行化した際の指標

ご覧の通り、第3章は作成した並行処理に対してどのように検証作業を行なっていくのかがメイントピックになっており、並行処理を作成した後の話になる。しかし、並行処理を記述する際にも、第3章で登場する考え方(一般化方法)は非常に重要であり、「ちゃんと読んでね」という筆者のメッセージが込められているため、飛ばさずに読む。

並行処理の検証について

M.Ben-Ariという強すぎる方が記した著書「Principles of Concurrent and Distributed Programming」で並行処理、および分散プログラミングが仕様通りに動いているかを一般化(誰がやっても同じようになるように)したそうで、この一般化方法が並行アルゴリズムを設計する上で最も大切になるとのこと(絶対に後悔させないから読んでくれと熱いメッセージが記述されている)。まずはこのBen-Ariが提案した一般化方法を理解することからこの章は始まる

Ben-Ariの並行アルゴリズムの一般化

「うわー、理論的で絶対に難しいやろなぁ」と思いつつ読み進めてみると人生初遭遇の単語が多いが、書かれている内容は意外とシンプルで慌てる必要はなさそう。順に見ていく。

プログラムはアトミックな実行文の連続である

その通りだとしか言いようがない。アトミックというのは原子を英語でアトムというので、処理を構成する部品のことだと思えばいい。本書によると、この粒感はプログラムコードの1行に当たるものであったり、アセンブリ言語で記述された1行であったりと見方によって変化するようだが、並行アルゴリズムを設計する際には高級言語で記述するコードの1行だと考えるのが良いのだそう。

どんな複雑な処理であっても、コードを1つ1つ分解していけば、1行のプログラムコードの連続になるという主張になる

name = "OKB" # アトミック
print(name) # アトミック

if name != "OKB": # アトミック
  print("Who are you???") # アトミック

インタリーブ(意味: 相互に挟み込む)

並行プログラムは必ずしも複数のスレッドが毎回、同じ順番で実行されることはなく、実行する度に処理される順序や処理時間は変化する。しかし、毎回実行する度に結果が異なるというのは冪等性に欠けており並行プログラムとしては欠陥品と言える。この複数のスレッドの実行文がそれぞれ、実行される順序の組み合わせのことを「インタリーブ」と呼び、並行プログラムは実行されうる全てのインタリーブ(組み合わせ)で同じ結果になることを証明する必要がある

インタリーブの数はスレッド数が増えると指数関数的に増えるため、全てのインタリーブに注目するのではなく、連続的整合性を証明するために必要な部分のみを取捨選択することが重要になる。

軽くPythonでサンプルを記述してみた。以下の処理は買い物カゴに関数funcAが引数に渡されてきた値を追加し、関数funcBが先頭要素を取り出し、返すという極シンプルなもの。逐次処理でfuncA -> funcBという順に呼び出されるのであれば問題はなさそうだが、並行プログラムとして関数それぞれをスレッドで動作させるとどうだろうか。

# 買い物カゴ
cart = []

# スレッドAに実行される関数
def funcA(goods):
  print("A was start")
  cart.append(goods)
  
# スレッドBに実行される関数
def funcB():
  print("B was start")
  # 買い物カゴから先頭要素をpop
  goods = cart.pop(0)
  return goods

# 以下のように逐次実行されるなら問題はないが...  
funcA("orange")
print(cart)
funcB()
print(cart)

インタリーブを考えると以下のようになる。print()の処理はどんな順で呼び出されても今の所は問題ないだろうからインタリーブからは外しておく。

• case: 1
  • A: カートに値を追加
  • B: カートから値を取得
• case: 2
  • B: カートから値を取得
  • A: カートに値を追加

case: 2の場合はリストに値が存在しないにも関わらずpop()を実行することになるため、実行時errorになる。これは先ほど述べた「実行されうる全てのインタリーブで同じ結果になる」という証明が出来ていないため、並行プログラムとしては欠陥品だと言える

Traceback (most recent call last):
  File "Main.py", line 17, in <module>
    funcB()
  File "Main.py", line 12, in funcB
    goods = cart.pop(0)
IndexError: pop from empty list

Ben-Ariの4つの並行実行一般化まとめのまとめ

本書にあるものを噛み砕いて記述しておく。情報を整理して覚えやすくする。

• プログラムは連続したアトミックな実行文
• 並行プログラムは複数スレッドが実行する処理の組み合わせ(アトミックのインタリーブと本書に有り)
• 並行プログラムは実行されうる全てのインタリーブで結果が同じになるように
• どのインタリーブでも他スレッドの実行を妨げてはならない -> 他スレッドの処理を停止させたり、実行を占有してはならない

これでBen-Ariの並行アルゴリズムの一般化方法に関する知識を身につけたことになる。次にBen-Ariの一般化方法をどのように使用するのかという話になっていく。

例題: クリティカルセクション問題

並行アルゴリズムで共有変数を参照/更新する部分を「クリティカルセクション」と言い、並行アルゴリズムを設計する上で良い例題となるらしい(著者はクリティカルリージョンと言うのが好みの様)。クリティカルセクションでは以下2つの性質を満たす必要がある。

守るべき性質

• 排他制御(アクセス可能なスレッドは1つのみ)
  • 他スレッドが共有変数を参照/更新 中は共有変数へのアクセスを禁止される。
• 他スレッドが他スレッドの共有変数へのアクセスを妨げてはならない

簡略化のためスレッドは2つで固定(スレッドzeroとスレッドone)してインタリーブを考える。コードをそのまま転載するのはアレなので、Pythonでそれっぽいものに書き換えたものを載せておく。
以下のコードはそのまま実行すると自動で終了しないので注意して下さい!!

第1段階

thread_number = 0 # 実行中のスレッド番号

def thread_zero():
  while True:
    # spin wait(待機し続ける)
    while(thread_number == 1):
      pass
    # 共有変数へのアクセス
    critical_region_zero()
    # 実行スレッドを0から1に切り替え
    thread_number = 1
    # 何かしらの処理
    other_stuff_zero()
  

def thread_one():
  while True:
    # spin wait(待機し続ける)
    while(thread_number == 0):
      pass
    # 共有変数へのアクセス
    critical_region_one()
    # 実行スレッドを1から0に切り替え
    thread_number = 0
    # 何かしらの処理
    other_stuff_one()

それぞれのスレッドが実行される度にthread_numberの値を参照して、自分に実行権があるのかを確認する。実行権があればクリティカルリージョンへのアクセスを行う。アクセスが終了した際にthread_numberをzeroなら1に、oneなら0に切り替える。これで問題なく排他制御がされるはず。

しかしながら、これは互いのスレッドが動作していることが前提であり片方のスレッドが何かしらの原因で停止した際には、もう片方のスレッドはthread_numberの値が変わることを期待して待機し続けてしまい結果的にデッドロックが発生してしまう。

第2段階

thread_0_inside = 0 # zeroがクリティカルリージョン中か
thread_1_inside = 0 # oneがクリティカルリージョン中か

def thread_zero():
  while True:
    while(thread_1_inside):
      pass
    # クリティカルリージョンへアクセス中ということを表明
    thread_0_inside = 1
    # 共有変数へのアクセス
    critical_region_zero()
    # クリティカルリージョンへのアクセスが終了したことを表明
    thread_0_inside = 0
    # 何かしらの処理
    other_stuff_zero()
  

def thread_one():
  while True:
    while(thread_0_inside):
      pass
    # クリティカルリージョンへアクセス中ということを表明
    thread_1_inside = 1
    # 共有変数へのアクセス
    critical_region_one()
    # クリティカルリージョンへのアクセスが終了したことを表明
    thread_1_inside = 0
    # 何かしらの処理
    other_stuff_one()

第1段階で課題となった「他方のスレッドが停止した場合にデッドロックが発生する」という問題に対応するために、他方のスレッドがクリティカルリージョンへアクセスしている際には自身の処理をスピンウェイトするという処理に更新された。こうすることで他方が何かしらの原因で停止したとしてもデッドロックは発生しなくなる。しかしながら、この方法には大きな問題がある。thread_0_insideの値、もしくはthread_1_insideの値を1に更新する最中に、他方のスレッドがクリティカルリージョンにアクセスしてしまう可能性がある。これは排他制御が機能していないことを意味している。
このようにそれぞれのスレッドが「アクセスするで」という意思を表明した後に、すぐにクリティカルリージョンにアクセスするような解法を著者は「自分勝手なスレッド」と言うそう。

第3段階

thread_0_wants_enter = 0 # zeroがクリティカルリージョンへのアクセスを依頼中か
thread_1_wants_enter = 0 # oneがクリティカルリージョンへのアクセスを依頼中か

def thread_zero():
  while True:
    # zeroがクリティカルリージョンへのアクセスをしようとしていることを表明
    thread_0_wants_enter = 1
    while(thread_1_wants_enter):
      pass
    # 共有変数へのアクセス
    critical_region_zero()
    # zeroがクリティカルリージョンへのアクセスが終了したことを表明
    thread_0_wants_enter = 0
    # 何かしらの処理
    other_stuff_zero()

def thread_one():
  while True:
    # oneがクリティカルリージョンへのアクセスをしようとしていることを表明
    thread_1_wants_enter = 1
    while(thread_0_wants_enter):
      pass
    # 共有変数へのアクセス
    critical_region_one()
    # oneがクリティカルリージョンへのアクセスが終了したことを表明
    thread_1_wants_enter = 0
    # 何かしらの処理
    other_stuff_one()

先ほどの自分勝手なスレッドを改修して、第3段階ではクリティカルリージョンへのアクセスの意思を表明してから、他方のスレッドがアクセスしようとしていないかを確認するようになっている。こうすることで同時にクリティカルリージョンへアクセスする問題は発生しなくなり、排他制御が正常に行われると判断出来ると思いきや、先ほどと同じ様にデッドロックが発生しうる。
thread_0_wants_enterとthread_1_wants_enterがほぼ同時に1に更新された時に、お互いに値が0になるまでスピンウェイトする。これはいつまでたっても終わることがない。互いに「どうぞどうぞ」と道を永遠に譲り続ける状態となってしまう。

第4段階

import time
import random

thread_0_wants_enter = 0 # zeroがクリティカルリージョンへのアクセスを依頼中か
thread_1_wants_enter = 0 # oneがクリティカルリージョンへのアクセスを依頼中か

def thread_zero():
  while True:
    # zeroがクリティカルリージョンへのアクセスをしようとしていることを表明
    thread_0_wants_enter = 1
    while(thread_1_wants_enter):
      # アクセスしたい表明を一旦取り下げる
      thread_0_wants_enter = 0
      # ランダム秒だけ待機
      time.sleep(random.uniform())
      # 再度、アクセスを表明
      thread_0_wants_enter = 1
      
    # 共有変数へのアクセス
    critical_region_zero()
    # zeroがクリティカルリージョンへのアクセスが終了したことを表明
    thread_0_wants_enter = 0
    # 何かしらの処理
    other_stuff_zero()

def thread_one():
  while True:
    # oneがクリティカルリージョンへのアクセスをしようとしていることを表明
    thread_1_wants_enter = 1
    while(thread_0_wants_enter):
      # アクセスしたい表明を一旦取り下げる
      thread_1_wants_enter = 0
      # ランダム秒だけ待機
      time.sleep(random.uniform())
      # 再度、アクセスを表明
      thread_1_wants_enter = 1

    # 共有変数へのアクセス
    critical_region_one()
    # oneがクリティカルリージョンへのアクセスが終了したことを表明
    thread_1_wants_enter = 0
    # 何かしらの処理
    other_stuff_one()

第3段階の単純なスピンウェイトを改めて、すでに他方のスレッドがクリティカルリージョンへアクセスした場合に自身がアクセスしたいという表明(thread_0_wants_enterもしくはthread_1_wants_enterを0に)を取り下げて、ランダム秒だけ待機する。2つの乱数が一致することが無い限り、お互いに道を譲り合うような状態は発生することが無くなり、デッドロックは起こり得ない。 お、完璧やんと思いつつ、実はまだ問題がある。
例えば、zeroのスレッドが処理を終了しthread_0_wants_enterの値を0に戻す。次に新たなスレッドがクリティカルリージョンへのアクセスを依頼する。依頼してきたのはzeroのスレッド。thread_1_wants_enterの値を確認し、0であれば(0と仮定)、thread_0_wants_enterを1に更新して、クリティカルリージョンへのアクセスを再度行う。アクセスが終了したタイミングでthread_0_wants_enterを0に更新する。再度、新たなスレッドがクリティカルリージョンへのアクセスを依頼する。依頼してきたのはzeroのスレッド...

このようにどちらかのスレッドが永遠にアクセス権限を独占してしまう可能性があるということが記述されている。この現象をスターベーション(枯渇)と言う。なるほど。この問題を解消するためにDekkerのアルゴリズムを実装するが、その前にデッドロックが発生する4条件について触れておく。

デッドロックを発生させる4つの条件

左側が本書から引用した言葉、右側が意味を噛み砕いた文章。

• 1.相互排他条件 -> 同時にいくつかのスレッドがアクセス可能。もしくは1スレッドのみがアクセス中
• 2.獲得後のウエイト -> アクセスを終了したスレッドが再度、続けてアクセスをしようとする
• 3.プリエンプトなし(先取する) -> 参照された値を削除して良いのは参照したスレッドのみ(値の解放)
• 4.循環待ち -> すでに他スレッドで参照されている値を参照しようとする

1, 2は何となくアカンのやろなぁと分かるが、3, 4に関しては場面想定が上手く出来ないが、鍵を持って箱を開けて得た中身の処理は開けた本人(スレッド)に責任を要求するという様に考えておけばいいだろう。

Dekkerのアルゴリズム

先ほど第4段階で実装したコードをDekkerのアルゴリズムの形に改修する。

auth = 0 # クリティカルリージョンへアクセス可能なスレッド番号(スイッチ)
thread_0_wants_enter = 0 # zeroがクリティカルリージョンへのアクセスを依頼中か
thread_1_wants_enter = 0 # oneがクリティカルリージョンへのアクセスを依頼中か

def thread_zero():
  while True:
    # zeroがクリティカルリージョンへのアクセスをしようとしていることを表明
    thread_0_wants_enter = 1
    while(thread_1_wants_enter):
      # アクセス権限があるかを確認
      if auth == 1:
        # アクセスしたい表明を一旦取り下げる
        thread_0_wants_enter = 0
        # アクセス権限がなければ待機
        while auth == 1:
          pass
        # 再度、アクセスを表明
        thread_0_wants_enter = 1

    # 共有変数へのアクセス
    critical_region_zero()
    # アクセス権限を譲る
    auth = 1
    # zeroがクリティカルリージョンへのアクセスが終了したことを表明
    thread_0_wants_enter = 0
    # 何かしらの処理
    other_stuff_zero()

def thread_one():
  while True:
    # oneがクリティカルリージョンへのアクセスをしようとしていることを表明
    thread_1_wants_enter = 1
    while(thread_0_wants_enter):
      # アクセス権限があるかを確認
      if auth == 0:
        # アクセスしたい表明を一旦取り下げる
        thread_1_wants_enter = 1
        # アクセス権限がなければ待機
        while auth == 0:
          pass
        # 再度、アクセスを表明
        thread_1_wants_enter = 1
      
    # 共有変数へのアクセス
    critical_region_one()
    # アクセス権限を譲る
    auth = 0
    # oneがクリティカルリージョンへのアクセスが終了したことを表明
    thread_1_wants_enter = 0
    # 何かしらの処理
    other_stuff_one()

構造としてはクリティカルリージョンにアクセス可能なスレッドをauth(本書にはfavoredとあり)という変数によって制御する。このauthはいわば、クリティカルリージョンへアクセスするための優先権となる。どちらかのスレッドがクリティカルリージョンへアクセスしようとしても、アクセスするための優先権がなければ、アクセスすることは出来ない。そのため、先ほどのように何度も同じスレッドがクリティカルリージョンへアクセスするという現象を回避することが出来る。より詳細なインタリーブは本書を読んでみてほしい。

性能評価

いたって単純。算出式の妥当性だとか、どうしてこの式が定義されているのかは追求しない。賢い人に任せる。 評価の軸は以下の2つ。

• 高速化率
• 実行効率

高速化率

「従来の逐次処理に対して、並行化したこの処理は300％早くなりました!」と言われるよりも「従来の逐次処理の3倍早くなりました」と言われた方が直感的で理解し易い。高速化率とは元の逐次処理が並行化したことで何倍早くなったのかを算出するための指標値になる。高速化率を算出するためには逐次処理の実行時間数値が必要になるので注意が必要。理想値はコア数に比例して高速化率も増えていくような数値になる。(コア数が10倍 -> 高速化率も10)

算出式は以下の2つが紹介されており、2つの算出式の違いはGustafson-Barsisの法則ではコア数が増えるにつれて、データ量の増加しているという前提が含まれているという点で算出方法が異なる。

Amdahlの法則: Amdahl's law - Wikipedia
Gustafson-Barsisの法則: Gustafson's law - Wikipedia

実行効率

高速化率をコア数で割れば算出可能。どれだけコンピューターリソースを上手く使えたかという指標になる。仮に90%という値が算出されたのであれば、残りの10%は処理全体を平均して、全てのコアが10%はアイドルになっていたということになる。この10%を減らすことが出来れば、完璧な効率化が出来たといえるが、実際になぜ実行効率の値が低いのかと言う原因は要因が複雑すぎるため、厳密な考察が必要だそう。

以上

参考文献

• 並行コンピューティング技法
• Mordechai Ben-Ari
• Principles of Concurrent and Distributed Programming (2nd Edition)
• interleave
• preempt
• Amdahl's law
• Gustafson's law

【並行コンピューティング技法】第2章のまとめ

前回までのあらすじ

以前から気になっていた「並行コンピューティング技法」を衝動買い。全体の構造を読み解き、どんな知識がこの本から得られるかを考察した。合わせて、第1章を読み、内容を簡潔にまとめた。第1章は大きく以下のような内容を扱っている

• 並行と並列の違い
• 並行までの(現在の逐次処理を並行処理に書き直すため)の4ステップ

www.okb-shelf.work

続いて、第2章を読み進めていこう

第2章

まずは前回同様に、見出しから第2章からどんな情報が得られるのかをざっくりと観察してリスト出ししてみた。

• 並行処理にするための2つの手法
  • タスクの分解(特徴とサンプル)
  • データの分解(特徴とサンプル)
• 並行不可能な場合の例(実際にはタイトルは適切ではなく、並行不可能な場合の回避テクニックに近い)

「並行処理にするための2つの手法」は実は第1章で既に登場した話であり、第2章では、この部分をより深掘りにしている。並行までの4つのステップの中の「スレッド化したいところを見つける」と「実行」の中間部分にあたるのではないだろうか。

並行処理にするための2つの手法

どちらかというと「データの分解」の方がしっくりくる。機械学習などで前処理を大量のデータに対して実行していく場合が想定しやすい。その一方でタスクの分解というと、メインの処理として逐次に実行すると処理が停止してしまうため、別スレッドやプロセスにて別処理を行うというイメージが強い(eg: メールの送信処理が完了までresponseを返さないのではなく、メールの送信処理は別スレッドにて実行し、メインの処理ではresponseを返してしまう)。というのが、私の2つの手法に対する事前に持ち合わせていた前知識だが、実際にどうなのかを確認していこう。

ここで基本用語が登場。「連続的整合性」は覚えざるを得ない。従来の逐次処理を並行処理に書き換えた際に、逐次処理として実行していた時の最終の結果が不変ではいけないという用語。つまり、並行処理は「連続的整合性」を必ず持っている必要がある。

タスクの分解

タスクとは何か

ここでいうタスクというのは「関数」であったり、処理を連ねた「パイプライン」であったりする。実装されたコードを熟知していればパーツ化可能なタスクを見つけ出すことは容易に行うことが可能だろう。タスクを別スレッドにて実行し、終了するまでの流れは基本的には変わらない。

• タスクを別スレッドにて起動
• タスクを実行していたスレッドが停止、もしくはスリープ(再開可能な状態で待機)
• メインのスレッドにて処理の終了を検知・管理

2つの原則

タスク分解する際の2つのお約束。以下引用。守ろう。

最小でもスレッド数(またはコア数)と同じ数のタスク数にする。
タスク内の処理量(粒度)はタスクやスレッドの管理に伴うオーバーヘッドよりも多くしなければならない

2つ目のがよく分からない。と思ったら、本書に解説がある。狙いは性能を向上させること。また、タスク内の処理量を「粒度」と呼ぶ。タスクを分解することで、メインスレッドにはスレッドの立ち上げ、他スレッドにて実行しているタスクの制御・管理などの本来、逐次処理を記述している際には発生しなかったオーバーヘッド(負荷となる処理)が発生する。スレッドが多くなればなるほど、オーバーヘッドが増えていくとすると、タスク量に対してスレッド数が適切でないと、オーバーヘッドの量が増え、元々の逐次処理よりも処理量が多くなり、性能が悪くor現状維持になってしまう可能性がある。そのために、タスク量とスレッド数のバランスを取るのが重要になる。 そのため、最低でもスレッド数とタスクの数は揃えるのだそうだ。

タスク間の依存性

例えば、算出値をmapやlistに保持する場合に複数のスレッドから行うと、データの整合性が取れなくなる可能性が高い。これがデータへの依存。もう1つが、実行順序に対する依存。Aの値がなければBの値が算出できないなど。

サンプル: 数値積分

ある関数が描く曲線の指定の定義域の下部の領域の面積を求めるタスクの分解を筆者と考える。が、筆者曰く、「読者に頑張ってほしい」とのことで具体的な回答は載っていない。問題の意味を理解する時間は自分にとって重要ではないので、何をすればいいのかだけ何となく分かった。要は積分を行う、定義域をスレッド毎に分割して、各スレッドにて算出された値を合計すれば良いのではないか

データ分解

共通する処理を分割したデータに対してスレッド毎に行う並行化の手法。データを分割して「チャンク(連続性を持つ部分領域?? -> マイクラのチャンクで考えると分かりやすい)」というものを作成して各チャンクを対象にそれぞれのスレッドにてタスクを実行する。となると、以下の２点が重要になる。

• どのようにデータをチャンクに分解するのか
• 各タスクが更新すべきデータにアクセスするには(アクセス可能な保証)

minecraft-ja.gamepedia.com

チャンクの分割方法

正直なところ、どんな分割方法を採用したとしても動作はする。しかしながら、分割の方法によって性能が左右される。どのような場合かというと、他のスレッドにて扱われているチャンクを参照する場合に発生する。
仮に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値をセットするようにした記憶がある

www.okb-shelf.work

漸化式(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

スケール出来ることが一番重要で、これは時代が変化してプロセッサのコア数が増えたとしても問題なく、コードが動作することを重要視しているからだそうだ。

以上

参考文献

• 並行コンピューティング技法
• チャンク - Minecraft Wiki

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

今回の購入物

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

著者について

こちらの初版は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章から得たい知識を頭の中に図化したものを書き出してみた。

この図を完成させるように第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章については以上です