カーン過程ネットワーク

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

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

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

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

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

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

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

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

有限状態マシンがプロセスに関連付けられたプログラム要素を読み取ると仮定すると、"Compute"、"Read"、"Write token" の 3 種類のトークンを読み取る可能性があります。さらに、待機状態では、待機に関連付けられた通信チャネルに読み取り可能なデータが含まれていることを意味する特別な "Get token" を読み取ることによってのみ アクティブ状態に戻ることができます。

チャネルが、実行可能なすべての未使用トークンを最大で個持っている場合、チャネルは によって厳密に制限されます。すべてのチャネルが によって厳密に制限されている場合、 KPN はによって厳密に制限されます。 ${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$

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

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

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

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

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

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

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

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

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

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

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

一部のAMD Xilinx VersalのAIエンジンはカーンプロセスネットワークの構成要素です。^[7]

• 同期データフロー
• 連続プロセスの伝達
• フローベースプログラミング
• データフロープログラミング

• Lee, EA; Parks, TM (1995). 「データフロープロセスネットワーク」(PDF) . Proceedings of the IEEE . 83 (5): 773–801. doi :10.1109/5.381846. ISSN  0018-9219 . 2019-02-13に取得。
• Josephs, Mark B. (2005)。「データフロー シーケンシャル プロセスのモデル」。Abdallah, Ali E.、Jones, Cliff B.、Sanders, Jeff W. (編)。シーケンシャル プロセスの通信。最初の 25 年間: CSP 25 周年記念シンポジウム、ロンドン、英国、2004 年 7 月 7 ～ 8 日。改訂版招待論文。Lecture Notes in Computer Science。第 3525 巻。ベルリン、ハイデルベルク: Springer Berlin Heidelberg。pp. 85 ～ 97。CiteSeerX 10.1.1.60.5694。doi :  10.1007/ 11423348_6。ISBN 978-3-540-32265-8。