このブログは、旧・はてなダイアリー「檜山正幸のキマイラ飼育記 メモ編」(http://d.hatena.ne.jp/m-hiyama-memo/)のデータを移行・保存したものであり、今後(2019年1月以降)更新の予定はありません。

今後の更新は、新しいブログ http://m-hiyama-memo.hatenablog.com/ で行います。

高次遷移系がイマイチ、別な定式化を探そう

higher-dimensional transition systemの関係論文を少し見ただけで、こう言うのはナンだが; 定義や定理がなんかイマイチで、役に立つ感じがしない。抽象論は大好きだが、CPU、メモリ、マシン(またはプロセス)などとの対応が鮮明じゃないと現実に適用しにくい。僕は現実の並列計算を説明したい。

同時実行をインターリーブして展開すると効果(effect)が変わる。そこが問題なのに、同時実行とインターリーブ展開を区別しない(同値にしてしまう)ような定式化してもショウモナイ。それは複数の計算が独立・無干渉なときに限られる話だ。

遷移だけ見ててもダメで、遷移の変形(deformation)が問題。変形は書き換え(並列プログラムのリファクタリングや最適化)と言ってもいい。状態点=0セル、遷移=1セル、変形=2セルとしての高次圏が必要だ。1セルにマルチアクションのラベルを付けても、実際には高次になってない。アクションラベルの集合がタプルになっただけで、状態空間の幾何構造が変わってない(1次元のまま)。

豊饒圏を作るとき、対象の集合の完全グラフを作って、辺に値の圏V(enriching category)のホム対象を割り当てる。この作り方は正方行列の定義と同じで、グラフで言えば隣接行列がホム対象の割り当ての記述になる。1次元グラフ=普通のグラフでは、すべての頂点は潜在的には辺で繋げる可能性を持っている。この事実を、頂点(のペア)は1-connectableと言うことにする。XとYが1-connectableのとき、hom(X, Y) が意味を持つ。

基礎となる1次元グラフの辺のあいだに2-connectableの関係を入れる。このときアクションのタプルを使う。同時実行遷移と、それをインターリーブ展開(分解)したパスは2-pre-connectableとして、2-pre-connectableを反射的対称な関係として拡張して2-connectableを定義する。2-connectable関係を〜とすると; p〜p、p〜q ⇒ q〜p となる。

2-ラベルの集合というものを考えて、2-ラベル係数の行列 A[p, q] (ただし p〜q)を与える。これが2-隣接行列。問題は、2-隣接行列の計算と、2-隣接行列/1-隣接行列のあいだの関係。1-隣接行列の推移的閉包は簡単に定義できて、これで計算的振る舞いを定義できた。類推すると、2-隣接行列の推移的閉包が2-振る舞いを定義しそう。2-ラベルの集合が真偽値なら、2-振る舞いはホモトピーになると思われる。

キーとなる概念は:

  • インターリーブ展開
  • 非交替(non-interchangeable)圏
  • 実行(run)のホモトピー

同時実行をインターリーブ展開すると、たくさんのパスが出てくるが、これらが交替律を満たすとは限らない。非交替の度合いがサブシステムの相互干渉を測る目安となる。その非交替性はホモトピーで記述されると思う。

ところで、実行(run)て概念も問題で、それほど素朴なもんじゃない。線形パスを実行として捉えていいのは単純直列プログラムの話であって、並行処理プログラムではそうはいかない。並行実行を、そのなかに含まれる直列実行の集合で特徴づけるアプローチは確かに有効だが、それがプライマリーな定義になるのはおかしい。もっと直接的な実行(run)の定義があってしかるべき。

以前、「時間の空間」という変な言葉を使っていたが、並列実行の定義はまさに「時間の空間」の問題だと思う。いくらなんでも「時間の空間」って言葉はひどいから、時間形状とか時間図式とか言えばいいのかも。時間図式にアクションでラベル付けしたものが並列フローチャート(これはプログラムそのもの)で、並列フローチャートからモデル圏への関手が実行(の記述)ってことだろう。