カーン過程ネットワーク
計算モデル

カーンプロセスネットワーク（KPN、またはプロセスネットワーク）は、決定論的なシーケンシャルプロセス群が、無制限の先入先出チャネルを介して通信する分散 計算モデルです。このモデルでは、チャネルからの読み取りはブロッキング、書き込みはノンブロッキングである必要があります。これらの重要な制約により、結果として得られるプロセスネットワークは、計算のタイミングや通信遅延に依存しない決定論的な動作を示します。

カーン過程ネットワークはもともと並列プログラムのモデリングのために開発されましたが、組み込みシステム、高性能コンピューティングシステム、信号処理システム、ストリーム処理システム、データフロープログラミング言語、その他の計算タスクのモデリングにも有用であることが証明されています。KPNは1974年にジル・カーンによって導入されました。[1]

3つのプロセス（頂点）と3つの通信チャネル（辺）を持つカーンプロセスネットワーク。実行中、プロセスPはチャネルAとBから読み取り、チャネルCに書き込みます。

実行モデル

KPNは、無限のデータストリームが順次または並列に実行されるプロセスによって段階的に変換される信号処理システムを記述するための一般的なモデルです。並列プロセスであるにもかかわらず、このモデルの実行にはマルチタスクや並列処理は必要ありません。

KPN では、プロセスは無制限のFIFOチャネルを介して通信します。プロセスは、チャネルとの間でアトミックデータ要素(トークンとも呼ばれる)の読み取りと書き込みを行います。チャネルへの書き込みは非ブロッキングです。つまり、常に成功し、プロセスを停止しません。一方、チャネルからの読み取りはブロッキングです。つまり、空のチャネルから読み取るプロセスは停止し、チャネルに十分なデータ項目 (トークン) がある場合にのみ続行できます。プロセスは、トークンを消費せずに入力チャネルにトークンが存在するかどうかをテストすることはできません。FIFO は複数のプロセスで消費することはできず、複数のプロセスが単一の FIFO に書き込むこともできません。プロセスの特定の入力 (トークン) 履歴が与えられると、プロセスは常に同じ出力 (トークン) を生成するように決定論的である必要があります。プロセスのタイミングまたは実行順序は結果に影響してはならないため、入力チャネルでトークンをテストすることは禁止されています。

プロセスに関する注意事項

  • プロセスは純粋なデータソースとして機能するため、入力を読み込んだり、入力チャネルを持つ必要はありません。
  • プロセスは出力を書き込む必要も、出力チャネルを持つ必要もありません。
  • 入力チャネルの空状態（または非ブロッキング読み取り）のテストは最適化のために許可されますが、出力には影響を与えてはなりません。チャネルを待つのではなく、事前に何らかの処理を実行することが有益であり、また可能である場合もあります。例えば、異なるチャネルから2つの読み取りがあるとします。最初の読み取りは停止（トークンの待機）しますが、2番目の読み取りは直接成功する場合、読み取り自体に時間がかかることが多いため（メモリ割り当てやコピーなど）、2番目の読み取りを先に行うことで時間を節約できます。

ペトリネットとしてのプロセス発火セマンティクス

上の画像に表示されているペトリネットでモデル化されたプロセスPの発火セマンティクス

上記の KPN のプロセスPが、最初にチャネルAからデータを読み取り、次にチャネルBからデータを読み取り、何かを計算し、最後にチャネルCにデータを書き込むように構築されていると仮定すると、プロセスの実行モデルは、右側に示すペトリネットでモデル化できます。 [2] PE リソース プレース内の単一のトークンは、プロセスが異なる入力データに対して同時に実行することを禁止します。データがチャネルAまたはBに到着すると、トークンはそれぞれFIFO AとFIFO B のプレースに配置されます。ペトリネットの遷移は、それぞれの I/O 操作と計算に関連付けられています。データがチャネルCに書き込まれると、PE リソースは初期マークで再び満たされ、新しいデータの読み取りが可能になります。

有限状態機械としてのプロセス

プロセスの有限状態機械

プロセスは、次の 2 つの状態のいずれかにある 有限状態マシンとしてモデル化できます。

  • アクティブ; プロセスはデータを計算または書き込みます
  • 待機; プロセスはデータをブロック（待機）しています

有限状態機械がプロセスに関連付けられたプログラム要素を読み取ると仮定すると、「計算トークン」、「読み取りトークン」、「書き込みトークン」の3種類のトークンを読み取る可能性があります。さらに、待機状態からアクティブ状態に戻るには、特別な「取得トークン」を読み取る必要があります。これは、待機に関連付けられた通信チャネルに読み取り可能なデータが含まれていることを意味します。

プロパティ

チャネルの有界性

チャネルが、実行可能なあらゆる処理に対して未使用トークンが最大で 個ある場合、そのチャネルはによって厳密に制限されます。KPNが によって厳密に制限されるのは、すべてのチャネルが によって厳密に制限される場合です。 b {\displaystyle b} b {\displaystyle b} b {\displaystyle b} b {\displaystyle b}

消費されないトークンの数は、プロセスの実行順序（スケジューリング）に依存します。スケジューラがトークンを消費するプロセスを実行しない場合、自発的なデータソースはチャネルに任意の数のトークンを生成する可能性があります。

実際のアプリケーションでは無制限のFIFOを持つことはできないため、実用的な実装ではFIFOのスケジューリングと最大容量を設計する必要があります。FIFOの最大容量は、いくつかの方法で処理できます。

  • FIFOオーバーフローを回避するために、設計時にFIFOの境界を数学的に導出することができます。しかし、これはすべてのKPNに対して可能というわけではありません。KPNが厳密に で制限されているかどうかをテストすることは決定不可能な問題です。[要出典]さらに、実際の状況では、境界はデータに依存する場合があります。 b {\displaystyle b}
  • FIFOの境界は必要に応じて拡大できる。[3]
  • ブロッキング書き込みは、FIFOがいっぱいになった場合にプロセスをブロックするために使用できます。このアプローチは、設計者がFIFOの安全な境界を適切に導出していない限り、残念ながら人為的なデッドロックにつながる可能性があります（Parks, 1995）。正しい出力を生成するために、実行時に局所的な人為的な検出が必要になる場合があります。[4]

閉鎖系と開放系

クローズドKPNには外部入力チャネルも出力チャネルもありません。入力チャネルを持たないプロセスはデータソースとして機能し、出力チャネルを持たないプロセスはデータシンクとして機能します。オープンKPNでは、各プロセスは少なくとも1つの入力チャネルと出力チャネルを持ちます。

決定論

KPNのプロセスは決定論的です。同じ入力履歴に対して、常に全く同じ出力を生成する必要があります。プロセスは、決定論性が維持される限り、任意の順序または回数でポートへの読み取りと書き込みを行うシーケンシャルプログラムとしてモデル化できます。結果として、KPNモデルは決定論的であり、以下の要因によってシステムの出力が完全に決定されます。

  • プロセス
  • ネットワーク
  • 初期トークン

したがって、プロセスのタイミングはシステムの出力に影響しません。

単調性

KPNプロセスは単調です。トークンの読み取りは、トークンの書き込みにのみつながります。将来読み取られたトークンは、将来書き込まれるトークンにのみ影響を与えます。KPNでは、シグナル内のイベントには完全な順序があります[説明が必要] 。 [説明が必要]。しかし、異なるシグナル内のイベント間には順序関係はありません。したがって、KPNは部分的にしか順序付けされておらず、時間制限のないモデルに分類されます。

アプリケーション

KPN は、その高い表現力と簡潔性により、計算モデルの基盤として、特定の特性 (データフロー指向、ストリーム ベースなど) を持つストリーミング アプリケーションを表現するために、いくつかの学術的モデリング ツールに適用されます。

ライデン大学のライデン組込み研究センターが管理するオープンソースのDaedalusフレームワーク[5]は、C言語で記述されたシーケンシャルプログラムを受け付け、対応するKPNを生成します。このKPNは、例えばFPGAベースのプラットフォームにKPNを体系的にマッピングするために使用できます。

Ambric Am2045超並列プロセッサアレイは、実際のシリコン上に実装されたKPNです。[6] 336個の32ビットプロセッサは、専用FIFOのプログラム可能な相互接続によって接続されています。そのため、チャネルはブロッキング書き込みによって厳密に制限されています。

一部のAMD Xilinx Versalに搭載されているAIエンジンは、カーンプロセスネットワークの構成要素です。[7]

参照

参考文献

  1. ^ Kahn, G. (1974). Rosenfeld, Jack L. (編). 並列プログラミングのための単純な言語の意味論(PDF) . Proc. IFIP Congress on Information Processing. North-Holland. ISBN 0-7204-2803-3。
  2. ^ ベルナルデスキ、C.;デ・フランチェスコ、N. Vaglini、G. (1995)。「データ フロー ネットワークのペトリ ネット セマンティクス」。アクタ・インフォマティカ。32 (4): 347–374。土井:10.1007/BF01178383。
  3. ^ パークス、トーマス・M. (1995). プロセスネットワークの境界付きスケジューリング (Ph.D.). カリフォルニア大学バークレー校.
  4. ^ Geilen, Marc; Basten, Twan (2003). Degano, P. (編).カーンプロセスネットワークの実行要件. Proc. 12th European Symposium on Programming Languages and Systems (ESOP). Springer. pp.  319– 334. CiteSeerX 10.1.1.12.7148 . 
  5. ^ http://daedalus.liacs.nl LIACS Daedalus フレームワーク
  6. ^ Mike Butts、Anthony Mark Jones、Paul Wasson、「再構成可能コンピューティングのための構造的オブジェクトプログラミングモデル、アーキテクチャ、チップ、ツール」、FCCMの議事録、2007年4月、IEEE Computer Society
  7. ^ AMD Xilinx UG1076 (v2022.2) 2022年10月19日 AIエンジンツールとフロー、p.11

さらに読む

  • Lee, EA; Parks, TM (1995). 「データフロープロセスネットワーク」(PDF) . Proceedings of the IEEE . 83 (5): 773– 801. doi :10.1109/5.381846. ISSN  0018-9219 . 2019年2月13日閲覧.
  • ジョセフス, マーク B. (2005). 「データフロー型シーケンシャルプロセスのためのモデル」. アブダラ, アリ E.、ジョーンズ, クリフ B.、サンダース, ジェフ W. (編).通信シーケンシャルプロセス. 最初の25年間：CSP25周年記念シンポジウム、英国ロンドン、2004年7月7日～8日. 改訂招待論文. コンピュータサイエンス講義ノート. 第3525巻. ベルリン、ハイデルベルク：シュプリンガー・ベルリン・ハイデルベルク. pp.  85– 97. CiteSeerX  10.1.1.60.5694 . doi :10.1007/11423348_6. ISBN 978-3-540-32265-8。
「https://en.wikipedia.org/w/index.php?title=Kahn_process_networks&oldid=1317314473」から取得