データフロー

データフローとは

データフローは、情報工学において複数の意味を持つ用語であり、特にメッセージパッシングと密接に関連しています。ここでは、データフローの多岐にわたる側面について解説します。

データフロー図

データフローという用語は、システム内のデータの流れを示す言葉としても用いられ、データフロー図内の矢印がデータフローと呼ばれます。データフロー図におけるデータフローは、外部のエンティティ、プロセス、データストア間のデータの流れを表現するものです。これにより、システム全体のデータの流れを可視化し、理解を深めることができます。

データフローネットワーク

データフローネットワークは、プロセス群やオートマトンが並行して実行されるネットワークであり、通信路を通してデータを相互にやり取りします（メッセージパッシングを参照）。特に重要なのはカーン・プロセス・ネットワークであり、ここでは各プロセスが入力データに対して変換処理を行い、結果を出力します。このモデルは、信号処理の抽象化において重要な役割を果たしています。また、データフローネットワークの概念は、アクターモデルという並行性モデルとも深く関連しています。

データフローアーキテクチャ

データフローアーキテクチャは、従来のノイマン型や制御フローアーキテクチャとは対照的なコンピュータアーキテクチャです。このアーキテクチャでは、プログラムカウンタを持たず、命令の実行は入力引数が利用可能になった時点で開始されます。この計算方式はデータ駆動と呼ばれます。商業的に成功した例は少ないですが、データベースエンジンの設計や並列コンピューティングフレームワークなど、様々なソフトウェアアーキテクチャにおいて概念的に採用されています。部分的には、アウト・オブ・オーダー実行として大きな成功を収めています。

ソフトウェアアーキテクチャとしてのデータフロー

ソフトウェアアーキテクチャにおけるデータフローは、変数の値が変更された際に他の変数の値を自動的に再計算するという考え方（リアクティブプログラミング）に基づいています。表計算ソフトは、この考え方を最も身近に体験できる例でしょう。セルに入力された計算式は、参照先のセルの値が変更されると自動的に再計算され、その依存関係は連鎖的に続きます。データフロー技術は、数値の再計算だけでなく、マウスの動きに応じた描画や、環境変化に反応するロボットの動作など、幅広い応用が可能です。

データフローの利点の一つに、プログラム内のコードの結合度を下げられる点が挙げられます。例えば、変数Xが変数Yに依存する場合、データフローを導入しないと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

データフロー