データフロー
データフロー（英: dataflow）は、情報工学において使われる用語であり、様々な意味を持つ。特にメッセージパッシングと関連が深い。
データフロー図
[編集]データフローという用語は、システム内のデータの流れを指す言葉としても使われ、データフロー図内の矢印がデータフローと呼ばれている。データフロー図のデータフローは、外部実体やプロセスやデータストアの間のデータの流れを表現したものである。
データフローネットワーク
[編集]データフローネットワークとは、プロセス群やオートマトンを並行的に実行するネットワークであり、通信路を通してデータを相互にやり取りする（メッセージパッシング参照）。
カーン・プロセス・ネットワーク はデータフローネットワークの中でも特に重要なクラスである。この場合、各プロセスは継続的に入ってくるデータに何らかの変換を加えて出力する。信号処理の抽象モデルとして重要とされている。
データフローネットワークの概念はアクターモデルと呼ばれる並行性モデルとも密接に関連している。
データフローアーキテクチャ
[編集]データフローアーキテクチャ[1]は、ノイマン型や制御フローアーキテクチャと正反対のコンピュータ・アーキテクチャを意味する。データフローアーキテクチャではプログラムカウンタを持たないか、（少なくとも概念的には）命令の実行が入力引数が使用可能となった時点で行われる。このような計算方式をデータ駆動という。データフローアーキテクチャを採用したコンピュータで商業的に成功したものはないが、データベースエンジン設計や並列コンピューティングフレームワークなどの各種ソフトウェアアーキテクチャは概念としてデータフローアーキテクチャを採用している。しかし、部分的にはアウト・オブ・オーダー実行として、大きな成功を収めている。
ソフトウェアアーキテクチャ
[編集]ソフトウェアアーキテクチャとしてのデータフローは、ある変数の値が変更されたときに他の変数の値を自動的に再計算させるという考え方（リアクティブプログラミング）に基づいている。
データフロー言語はその原理を取り入れたもので、その意味では表計算ソフトが最も一般的な例であろう。例えば、表計算ソフトでは、あるセルに他のセルの値を使った計算式を対応付けることができる。そして、任意のセルの値を変更すると、自動的にその値に依存している他のセルの再計算が行われる。これは依存関係がある限りずっと続く。
データフロー技術は数値の再計算だけに限られない。例えば、マウスの動きに対応して絵を再描画するとか、周囲の明るさの変化に対応してロボットが反応するといったこともデータフロー的な考え方に基づいている。
データフローの利点の1つとして、プログラム内のコードの結合度を減らすことができる点が挙げられる。例えば、変数 X が 変数 Y に依存しているとする。データフローを導入しない状況では、Y が変更されたら明示的に X を再計算しなければならない。これはつまり、Y が X と密接に結合していることを示す。同時に X の値は Y の値に依存しているので、X も Y に結合している。この依存関係からプログラム内に環状の依存関係が生まれる。このような状況に対処する手法として Observer パターンがあるが、そのためのコード量は決して少なくない。データフローでは、X の再計算を自動的に行うことで Y から X への結合を解消し、この状況を改善する。データフローは通常なら多大なコードを要するようなことを暗黙のうちに実現している。
データフローをサポートすべく作成されたプログラミング言語もいくつか存在する。特にビジュアルプログラミング言語にはデータフローの考え方に基づいているものが多い。Javaベースのフレームワークの例として Pervasive DataRush がある。
ハードウェアアーキテクチャ
[編集]データフロー型のハードウェアアーキテクチャは1970年代から1980年代初期にかけて盛んに研究された。データフローアーキテクチャの概念は、スタンフォード大学の D.A. Adams（1968年）とMIT の J.E. Rodriguez（1969年）が発表したのを始まりとして、MIT のジャック・デニスらが研究を進めた。
コンピュータアーキテクチャの分類
[編集]コンピュータ・アーキテクチャを分類するにあたって、ここでは処理を進行させる鍵は何であるかに着目する。
- プロセッサ駆動 - プログラムやデータが先に用意されていて、プロセッサによって処理の進行が駆動される方式
- 機能集中型 - 汎用的なプロセッサが自ら命令やデータを格納場所から取り出す方式。ノイマン型
- 機能分散型 - プロセッサ群に命令やデータが送られてくる方式。静的データフローアーキテクチャ
- トークン駆動 - プロセッサ群にプログラムの命令を割り付けておき、トークンと呼ばれるデータや制御がそのプロセッサに到着した時点で処理が行われる方式。動的データフローアーキテクチャ
- プロセッサ仲介型 - 他のプロセッサからトークンが送られてくる方式。
- 通信仲介型 - 通信網を仲介してトークンが送られてくる方式。
デニスの先駆的研究は静的データフローアーキテクチャである。動的データフローアーキテクチャの例としては、Manchester Dataflow Machine や MIT Tagged Token がある。
プロセッサ駆動機能分散型
[編集]プロセッサ駆動機能分散型のデータフローマシンは、ノード（プロセッサ機能すなわち命令）とトークン（入力データ）とアーク（出力データの出力先ノードを示す一種のポインタ）をパケットとし、メモリに格納しておく。各パケットは必要なトークンが全て揃うと実行可能になる。実行可能なパケットはプロセッサに送られ、プロセッサはそれを解釈実行し、出力トークンをメモリに戻す。その出力トークンは元のアークで示されているノードのパケット内に格納される。これを繰り返すことで処理が行われる。
例えば、2つの整数の加算命令パケットには、加算命令のノード情報と2つの入力トークンと加算結果の出力先情報（複数の場合もある）が格納されており、2つのトークンが揃うと実行可能と判断され、プロセッサに送られる。プロセッサはノードに示された加算命令を実行し、結果のトークンをアークで示されたアドレスに書き込む（正確にはタグによるパターンマッチングを伴うことが多い）。
コンパイラはプログラムを解析してデータの依存関係を明らかにする。これはよりよい最適化を命令列に施すためであるが、一般にコンパイル結果の実行コードにはその依存関係に関する情報は含まれない。データフローマシン向けにコンパイルされたプログラムでは、この依存関係情報を保持する。データフローコンパイラでは各依存関係ごとにユニークなタグを生成する。これにより依存関係のない命令群の並列実行可能性を引き出す。各命令にはタグ付きのオペランドがあり、これが実行コードとして格納される。これは上述のパケットにほぼ相当するが、入力トークンは実行時まで存在しない。
実行コードは、データフローマシンの連想メモリに格納される。ある命令のタグ付きオペランドが全て使用可能となったとき、その命令が実行可能となる。これを命令の「発火」という。実行ユニットが命令を実行すると、その出力データが（タグと共に）連想メモリに送られる。タグのマッチングによってそのデータを必要とする命令の状態が更新され、次の命令が発火する。命令はデータの到着順に発火していき、これはプログラマがプログラムした順番とは異なる可能性がある。
トークン駆動型
[編集]トークン駆動型では、プロセッサ同士がネットワークで相互接続されている。ネットワークのトポロジーにより、各プロセッサが任意の他のプロセッサに直接通信可能であれば「通信仲介型」、そうでない場合は「プロセッサ仲介型」と呼ばれる。ネットワーク上の各プロセッサにはそれぞれ複数のノードが割り当てられる。これにトークンが入力されると、そのトークンを処理するノードが処理を実行し、結果をトークンとしてネットワーク上に流す。さらにそのトークンを入力とするノードがそれを処理する。このようにして処理が行われる。トークンに入力データを使う場合はデータフローだが、ノイマン型との親和性を高めるため（ノイマン型向けの集積回路などを流用しやすくするため）データはメモリに格納しておいて、データが利用可能であることを示す制御トークンを使う場合もある（これを正確にはコントロールフローと言う）。
問題点
[編集]初期の設計では、タグとしてそのパケットのアドレスなどが使われていた。しかし、これでは同じサブルーチンを並行的に複数呼び出す場合や再帰的に呼び出す場合に、パケットの依存関係の解釈に混乱が生じてしまう。同様にループを実行する場合も同じ問題が生じる。その後の設計ではタグのつけ方を改善してこれらの問題に対処した。
しかし、次のような問題は解決できていない:
- 超並列システム上でのデータトークンのブロードキャストの効率化
- 超並列システム上での命令トークンの効率的な分配
- 実用的なプログラムを格納できるほどの大きな連想メモリの構築
また、システムが巨大化すればするほど個々の命令や依存関係情報を通信でやりとりするコストが増大し、計算にかかるコストに比較して無視できなくなる。つまり、分割の粒度があまりにも細かすぎたのである。
アウト・オブ・オーダー実行は、マイクロプロセッサ内でデータフロー的な最適化を行う方式であり、現在では多くのマイクロプロセッサで実装されている。基本的な手法としては scoreboarding と Tomasuloのアルゴリズム があるが、どちらも演算器の数などの計算資源による可能な同時処理数にもとづいた制限があるのが一般的であり、以上で述べたようなオーバヘッドの増大は設計段階で避けている。
参考文献
[編集]- 曽和将容（著）、『データフローマシンと言語』、昭晃堂、1986年、ISBN 4-7856-3543-6