このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

プログラムの同時実行をチャンと理解しよう: 並列と並行の違いなんて、どうでもいいからさ

定期的に、「並列(parallel)処理と並行(concurrent)処理は違うから混同しちゃいかん」みたいな話が出るんですが、言葉のニュアンスというか、雰囲気で使い分けるというなら、それは趣味嗜好の問題で人好き好きでしょ。違いを強調しながらも、明確なモデルを持たない話なら小うるさいだけでショウモナイ感じだしね。

というわけで、ハッキリとした議論の土台になるようなサンプルを紹介します。とても単純なサンプルですが、雰囲気で話すよりはマシだと思います。

内容:

なぜ「並列 vs. 並行」は無意味なのか

簡単なモデルにおいても、「プログラムの同時実行」と呼べそうな実行形態は3種類以上あります(後述します)。となると、「並列 vs. 並行」という二分法(dichotomy)は根拠があやしくなってきます。皆さん、どんな基準で2種に分けているのでしょうか。

よくある分かりやすい区別は、並列=マルチCPU/マルチコア、並行=時分割 というものです。一方で、「並列 vs. 並行」ではなくて、「並列 vs. 非並列」&「並行 vs. 非並行」の2×2で、四分法だなんて話もあります(よく知らんけど)。そうかと思うと、また別な意見として、並行が広い概念で、並列は(特殊例として)並行のなかに含まれる、というのも見かけました。並列が本物で並行は偽物だ、とか言う人も……。

並列 並行
英語 parallel concurrent
意見1 マルチCPU/マルチコア 時分割
意見2 並列 vs. 非並列 並行 vs. 非並行
意見3 特殊な例 一般的
意見4 本物 偽物
…… ……

もう何がナンだか?? こうなると、「並列」「並行」という2つの言葉に対して、色々な観点から、「私はこう使い分けたい」と銘々が言い放っているだけ、と、そんな様相。もはや不毛な議論でしょう。

特定のコミュニティ内で「並列」「並行」の使い方の合意を取ることは可能でしょうが、広範囲の合意は無理そうだし、合意することの意義もないと思います。2つの言葉/二分法を云々するより、もっと適切な分析や分類をするほうが建設的です。よって、「並列と並行の違いなんて、どうでもいい」のです。

議論の進め方と説明の方法

「並列と並行の違いは重要だ」と思っている人はたくさんいるでしょうから、僕が「どうでもいい」とか言うと、「なんだオマエは。イイカゲンなこと言いやがって」となるでしょう。いちおう根拠はあるつもりなんですが、それについてうまい説明の仕方がなかなか思い付かなかったんですよね。最近になって、極端に単純な抽象機械(abstract machine)を例題として、よく知られたプログラミング言語により、抽象機械のソフトウェア実装を示せばいいんじゃないか、と思い至りました。「よく知られたプログラミング言語」としてはJavaScriptを採用します。

このテのお題を、過去の経験やその場の雰囲気で話しているとラチがあかない曖昧な議論になります。過去の経験は人それぞれ別だし、雰囲気の捉え方も個人差があります。僕が推奨する手順は:

  1. ハッキリとしたモデル/サンプルを決めましょう。
  2. そのモデル/サンプルに基いて議論を進めることに合意しましょう。
  3. 合意できないときは、合意できそうな別なモデル/サンプルを探しましょう。

この記事では、僕が一方的にモデル/サンプルを提示しているので、それに合意できない人はそこで話がオシマイです。合意してくれることを期待してこれを書いています。

状態遷移モデルと超単純なサンプルP1

計算モデルとしては状態遷移モデルを採用します。状態空間(state space)をSとして、初期状態(initial state) i∈S は決まっているとします*1。CPUの機械語に相当する基本命令(instruction, action)により状態遷移が引き起こされます。基本命令の集まりを命令セット(instruction set)と呼びます。

我々が扱うサンプルでは、状態空間 S = {0, 1, 2}、初期状態 i = 0 とします。基本命令はNとUの2つだけで、N(No operationから)は「今の状態を変えない(何もしない)」命令、U(Upから)は「今の状態に1を足す」命令とします。ただし、2 + 1 はエラーとします。この具体例の状態遷移グラフは次のようです。

この状態遷移系を、プロセッサ(CPU)の超単純化したモデルと考えます。「プロセッサ その1」ということでP1と呼びます。

プロセッサ名 状態空間 初期状態 命令セット
P1 {0, 1, 2} 0 {N, U}

抽象機械群のJavaScriptによる実装一式は、Gihub Gistに貼ってあります。

適宜、JavaScriptコードの一部を引用します。今述べた内容は、次のようなコードになっています。

/* 
 * プロセッサ その1 (P1)
 */

// P1 の基本命令
const N = "N"; // No operation
const U = "U"; // Up

// Stat = {0, 1, 2}
// Inst = {N, U}

// P1 : Stat×Inst → Stat
function P1(stat, inst) {
  // stat : 0, 1, 2 のいずれか
  // inst : N, U のどちらか

  switch (inst) {
  case N:
    switch (stat) {
    case 0: return 0;
    case 1: return 1;
    case 2: return 2;
    default: throw "Invalid state: " + stat
    }
  case U:
    switch (stat) {
    case 0: return 1;
    case 1: return 2;
    case 2: throw "Not defined"
    default: throw "Invalid state: " + stat
    }
  default: throw "Invalid instraction: " + inst
  }
}

次のようなHTMLファイルを使えば、ブラウザのJavaScriptコンソールから試せます。

<script src="VerySimpleAbstractMachines.js"></script>
<h1>VerySimpleAbstractMachines.js</h1>

言葉使いに関する注意

「プロセッサ」、「コア」、「マシン」といったハードウェアっぽい言葉を使います。しかし、ほんとのハードウェアの話をしたいわけではありません(ハードウェアよく知らんし)。このような言葉を使って状態遷移モデルについて語りたい、ということです。

マシン(機械)は抽象機械のことであり、ラベル付き遷移系(labeled transition system)と同義です。ほんとのハードウェアではなく、プロセスやエージェントと呼ばれるソフトウェア的な実行単位をイメージしています。念の為に、用語の対応を表にしておきます。

状態遷移モデル ハードウェアっぽい言葉
ラベル付き遷移系 マシン
状態空間 (メモリの)状態空間
初期状態 初期状態
ラベル(アクション記号) 基本命令
ラベルの集合 命令セット
遷移写像/遷移関係 プロセッサ本体(の機能)

2コアプロセッサの超単純なサンプルP2

もう1つのプロセッサP2を定義しておきます。P2は、P1を2個一緒にしたようなもので、2コアと言えなくもないでしょう。前節で注意したとおり、「コア」は比喩的に言っているだけですけどね。P2の状態空間も命令セットも、P1のそれを(集合の意味で)二乗したものです。

  • P2の状態空間 = S×S = {0, 1, 2}×{0, 1, 2} = {(0, 0), (0, 1), (0, 2), (1, 0), ..., (2,2)}
  • P2の初期状態 = (0, 0)
  • P2の命令セット = {N_N, N_U, U_N, U_U}

P2の基本命令は x_y の形をしてますが、これは、コア1でxを実行し、同時にコア2でyを実行することです。P2では、P1の2つの命令を同時に実行できるわけです。P1の基本命令とP2の基本命令は機能性が違うので、混乱の恐れがあるときはP1-命令P2-命令のように呼び分けることにします。

P2の状態遷移グラフは次のようです。

プロセッサP2の仕様を、既に出したP1の仕様と共にまとめます。P2の状態空間は9個の要素=状態点からなりますが、省略しています。

プロセッサ名 状態空間 初期状態 命令セット
P1 {0, 1, 2} 0 {N, U}
P2 {(0, 0), ..., (2, 2)} (0, 0) {N_N, N_U, U_N, U_U}

抽象プロセッサP2のJavaScriptによる実装は次のとおり。

/* 
 * プロセッサ その2 (P2)
 */

// P2 の基本命令
const N_N = [N, N];
const N_U = [N, U];
const U_N = [U, N];
const U_U = [U, U];

// P2 : (Stat×Stat)×(Inst×Inst) → Stat×Stat
function P2(stat, inst) {
  // stat : 0, 1, 2 を要素とするペア
  // inst : N, U を要素とするペア
  
  var stat1 = stat[0];
  var stat2 = stat[1];
  var inst1 = inst[0];
  var inst2 = inst[1];
  return [P1(stat1, inst1), P1(stat2, inst2)];
}

P1とP2を使った2つのマシンM1とM2

P1とP2は裸のCPUみたいなもので、これだけではプログラムの実行は出来ません。プログラムとは、基本命令の並びです。JavaScriptによる抽象機械の実装では、[N, U, U] とか [U_U, N_U] とかの配列を抽象機械のプログラムと考えます。必要があれば、P1-命令の並びをP1-プログラム、P2-命令の並びをP2-プログラムと呼び分けることにします。

マシンは初期状態から動作を開始して、プログラム(基本命令の配列)に含まれる各命令を順番に実行します。プログラムを読みきった時点で実行を終了し、終了時の状態をプログラムの結果とします。

プログラム [N, U, U] をプロセッサP1を使って実行すれば、0 → 0 → 1 → 2 と状態遷移して、プログラムの結果は 2 となります。また、プログラム [U_U, N_U] をプロセッサP2を使って実行すれば、(0, 0) → (1, 1) → (1, 2) と状態遷移して、プログラムの結果は (1, 2) となります。

途中でエラーが発生すれば、プログラムの実行結果はありません。[U, U, U] はエラーするプログラムの例です。

プロセッサP1を使用したマシンM1と、プロセッサP2を使用したマシンM2に対応するJavaScript関数を実行してみると:

> M1([N, U, U])
  2
> M2([U_U, N_U])
  [1, 2]
> M1([U, U, U])
(X) Error: Not defined

TRACEという変数をtrueにしておけば、トレース情報が表示されます。((i)はconsole.infoによる表示のつもり。)トレース情報は次の型式です。

  • ステップ番号:(その時の状態)
> TRACE=true
  true
> M1([N, U, U])
(i) 0:(0)
(i) 1:(0)
(i) 2:(1)
(i) 3:(2)
  2
> M2([U_U, N_U])
(i) 0:(0, 0)
(i) 1:(1, 1)
(i) 2:(1, 2)
  [1, 2]
> M1([U, U, U])
(i) 0:(0)
(i) 1:(1)
(i) 2:(2)
(X) Error: Not defined

M1とM2のJavaScriptによる実装は、https://gist.github.com/m-hiyama/7e896ef4a3734c323eb2 のなかで関数を探してください。これから述べる M3, M4, M5 についても同様です。

時分割実行方式M3と2コア実行方式M4

マシンM3とマシンM4は、どちらも2つのプログラムを実行するマシンです。M3はプロセッサP1を使い、M4はプロセッサP2を使います。どちらも、実行に先立ってプログラムの変換(合成)を行います。M3はシャッフルで変換し、M4はジップで変換します。JavaScriptソースコード内の、shuffle関数、zip関数が変換用の関数です。

シャッフルって、2つに分けたトランプ束を綺麗に混ぜあわせる技のことね*2


[*3]

ここで使うシャッフルは、手品またはイカサマ用です。どういうことかと言うと、左右どちらの束から来たか分かるようにカードに目印を付けています。シャッフルした後でも目印をたよりに元に戻せます。この手品用シャッフルは、コンテキスト・スイッチの情報を前持って命令に埋め込んで直列化する操作に対応します。

マシンM3は、2つのプログラムをシャッフルしてから、それをプロセッサP1により実行します。例えば、2つのプログラムが [N, U, U] と [U, N] なら、シャッフルの結果は [[1, N], [2, U], [1, U], [2, N], [1, U]] です。番号1または2が手品用の目印ですね。TRACE = true の状態で実行してみると、次のようになります。

> M3([N, U, U], [U, N])
(i) [[1, "N"], [2, "U"], [1, "U"], [2, "N"], [1, "U"]]
(i) 0:(0, 0)
(i) 1:(0, 0)
(i) 2:(0, 1)
(i) 3:(1, 1)
(i) 4:(1, 1)
(i) 5:(2, 1)
  [2, 1]

実行には5ステップを要しています。

次に、マシンM4が使うジップは、圧縮じゃなくて、ズポンの前とかに付いているジッパー/ファスナーのことね。

[*4]

同じ長さのプログラムじゃないとジップできないけど、ここでは、短いほうの末尾に基本命令Nを埋めて長さを揃えています。例えば、[N, U, U] と [U, N] をジップした結果は、[[N, U], [U, N], [U, N]]、これはP2-プログラムであり、[N_U, U_N, U_N] とも書けます。

ジップした結果の配列の要素の [N, U] などのペアは、これ自体でプロセッサP2の基本命令(P2-命令)なので、ワンタイミング(1クロックサイクル)で実行されます。単一のP2-命令であることを強調する意味で、[N, U] をN_Uのような名前に定義してあったのでした。

// P2 の基本命令
const N_N = [N, N];
const N_U = [N, U];
const U_N = [U, N];
const U_U = [U, U];

2つのプログラム [N, U, U] と [U, N] をM4で実行してみましょう。

> M4([N, U, U], [U, N])
(i) [["N", "U"], ["U", "N"], ["U", "N"]]
(i) 0:(0, 0)
(i) 1:(0, 1)
(i) 2:(1, 1)
(i) 3:(2, 1)
  [2, 1]

結果はM3と同じですが、M4は3ステップで実行しています。高速なんです。

ひとつのプログラムを並列化して実行するM5

最後に登場するマシンM5は、1つのP1-プログラムをP2-プログラムに変換してから実行します。使っている変換方式はカップリングJavaScriptによる実装ではcouple関数)です。

[*5]

カップリングは、1列に並んでいる行列の先頭の二人をカップルにして相席に座らせてしまう、という方法です*6。[N, U, U, N] という列から、[N, U] と [U. N] というカップルが形成されます。

カップリングにより作られたP2-プログラムが終了した結果は2つの状態のペアなので、次のmerge関数により結果を1つにまとめます。

// 2つの結果(状態)を1つにする
// Stat×Stat → Stat
function merge(stat1, stat2) {
  // stat1 : 0, 1, 2 のいずれか(を想定)
  // stat2 : 0, 1, 2 のいずれか(を想定)

  var stat = stat1 + stat2;
  if (stat > 2) throw "Can not merge";
  return stat;
}

M5による実行を見てみましょう。

> M5([N, U, U, N])
(i) [["N", "U"], ["U", "N"]]
(i) 0:(0, 0)
(i) 1:(0, 1)
(i) 2:(1, 1)
  2
> M5([N, U, U])
(i) [["N", "U"], ["U", "N"]]
(i) 0:(0, 0)
(i) 1:(0, 1)
(i) 2:(1, 1)
  2
> M5([U, U])
(i) [["U", "U"]]
(i) 0:(0, 0)
(i) 1:(1, 1)
  2

M5による実行のステップ数は、M1のほぼ半分になります。つまり、速度は倍です。

5つのマシンのまとめ

今までに説明した5つのマシンについてまとめておきましょう。プログラムの長さ(並んでいる基本命令の数)をnとします。プログラムが2つあるときは、nとmです。結果の個数は、0, 1, 2 の数がペアになっていれば「2つ」と勘定しています。ceil関数は「数の切り上げ」をする関数です。

マシン ひと言 プロセッサ プログラム 結果 ステップ数
M1 素直にP1使用 P1 1つ 1つ n
M2 素直にP2使用 P2 1つ 2つ n
M3 時分割方式 P1 2つ 2つ n + m
M4 2コアで2プログラム P2 2つ 2つ max(n, m)
M5 高速化 P2 1つ 1つ ceil(n/2)

M3, M4, M5 では、実行すべきプログラムを前もって変換します。その変換方式をまとめれば:

マシン 変換方式 変換前 変換後
M3 shuffle P1-プログラムが2つ P1-プログラム(目印付き)が1つ
M4 zip P1-プログラムが2つ P2-プログラムが1つ
M5 couple P1-プログラムが1つ P2-プログラムが1つ

二分法は色々あるんだよ

二分法が好きな人は多いでしょう。僕も好きです。今までに紹介した5つのマシンを二分法で分類してみます。

まずは、マシンが実行しようとするプログラムの数で分類してみると:

分類基準 該当するマシン
1 単一プログラムを実行 M1, M2, M5
2 複数プログラムを実行 M3, M4

マシンが使用しているプロセッサで分類すれば:

分類基準 該当するマシン
1 プロセッサP1を使用 M1, M3
2 プロセッサP2を使用 M2, M4, M5

結果がいくつ出るかで見れば:

分類基準 該当するマシン
1 単一の結果を出す M1, M5
2 複数の結果を出す M2, M3, M4

「高速化が期待できるか」という観点ではどうでしょう。プログラムの長さ(2つのときは長さの和)と実行時のステップ数を比較してみます。(空プログラムは考えない。)

分類基準 該当するマシン
1 長さ = ステップ数 M1, M2, M3
2 長さ > ステップ数 M4, M5

直交する二分法*7を2つ組み合わせると四分法になるし、3つ組み合わせると八分法になります。二分法は、最も基本的な分類法であり、より精密な分類の基本になるものです。

しかし、分類基準が異なる二分法を混同したり、単一の名称で呼ぼうとするのは馬鹿げています。また、無関係な分類基準/観点の優劣を論じるのも実りがありません。

二分法に拘らなくてもいいし

ここで、マシンが実行しようとするP1-プログラムの数と、プロセッサが同時に実行可能なP1-命令の数に注目してみましょう。マシンM1, M3, M5, M4を取り出して表にすると:

マシン 実行するP1-プログラムの数 同時実行可能なP1-命令の数
M1 1つ 1つ
M3 2つ 1つ
M5 1つ 2つ
M4 2つ 2つ

1-1, 2-1, 1-2, 2-2 という組み合わせがすべて出現しています。ここでは、1と2から選んだ組み合わせですが、任意の正整数n, mの組み合わせを考えることができます。つまり、次の状況を考えることになります。

  • n個のプログラムを、同時にm命令を実行可能なプロセッサ上で実行する。

m = 1 ならば、複数のプログラムを単一プロセッサ上で上手に動かす方法を探すことになるし、n = 1 ならば、与えられたひとつのプログラムを並列化して高速実行する話になるでしょう。

nとmに依存して、問題意識や考え方は変わってきます。ここでの分類は、正整数nとmの組を指標とするもので、無理に二分することに意味があるとは思えません。

モデルの精密化とか

「議論の進め方と説明の方法」の節で、僕が提示するモデル/サンプルに同意できないなら、そこから先には進めない、と言いました。5つのマシンのモデルは単純化し過ぎのそしりは免れません。なにしろ、もとになる状態遷移系は3状態-2命令ですから。

「そんなオモチャで何が分かる?」という疑念はもっともです。ですが僕は、「こんなオモチャでもけっこう分かる」と感じています。状態空間と命令セットを大きくすることは容易ですし、抽象プロセッサや抽象機械の組み合わせ(composition, combination)には、オモチャでも本格的モデルでも同じやり方が使えます。

今回のモデルには、共有メモリや通信チャネルのような相互作用の手段が一切入ってません。相互作用が入ると話は格段に難しくなります。しかし、相互作用なしでも実行方式は多様で、「簡単すぎて無意味」ってことはないでしょう。

“so-called 並列/並行”をモデル化する話は、過去記事でもたくさんしています。例えば、テンソル半加法圏は並列性を含むモデルです。でも、並列性の議論であることが分かりにくかったかも知れません。

今回の超単純モデルとテンソル半加法圏の中間に位置する話題をいつか扱いたいですね。

*1:初期状態を1つに決めるのがいつでも良いとは限りません。複数の初期状態を持たせるのが自然な場合もあります。

*2:正確には、リフル・シャッフル(riffle shuffle )というらしいです。

*3:オリジナル画像: http://www.geocities.jp/magicsatoru/technique/riffleshuffle/riffleshuffle07.jpg

*4:オリジナル画像: http://image.rakuten.co.jp/deskdepot/cabinet/zipper/talon5a.jpg

*5:オリジナル画像:http://ono-blog.com/wp-content/uploads/%E8%A1%8C%E5%88%97%E3%80%80%E9%A3%B2%E9%A3%9F.jpg

*6:現実には、このように無理やり作ったカップルは、相性が悪くて喧嘩してしまうことがあります。相性が良さそうな二人だけカップリングして、そうでないときは一人席に座らせるような工夫が必要です。

*7:「直交する」って何だ? と聞かれると答えるのが難しいです。チャンとした定義をご存知でしたら、教えてください