記事の最初の部分では、データフローアーキテクチャと制御フローアーキテクチャの主な違いを調べ、最初のハードウェアデータフローマシンが登場した1970年代にツアーを行い、静的および動的ストリーミング計算モデルを比較しました。 今日は、引き続きデータフローアーキテクチャを紹介します。 猫へようこそ！

上記に加えて、動的ストリーミングシステムでのループ実装

サイクルの編成の例に関するコンテキストの作業をより詳細に検討してみましょう。 コンテキストは、データフローグラフノードのインスタンスを一意に識別するトークン構造内のフィールドであることを思い出してください。 ループの場合、コンテキストは反復数になります。

例1.フィボナッチ数

フィボナッチ数の計算は、反復がデータに依存するサイクルの典型的な例です。 N番目の数値は、（N-1）番目と（N-2）番目の合計です。

int fib [MAX_I]; fib [0] = 1; fib [1] = 1; for (i = 2; i < MAX_I; i++) { fib [i] = fib [i-1] + fib [i-2]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

計算のフローグラフを作成します。





グラフは、コンテキスト値（ノード画像の下の数字）のみが異なる（MAX_I-2）同一のノードで構成されていることが簡単にわかります。 ノードのロジック（擬似コード）は次のようになります。

  fib (:  A,  B)  i = _(A);  result = _(A) + _(B); _ (: result, : host, : i);  (i < MAX_I-1) _ (: result, : fib, : i+1); _ (: result, : fib, : i+2);     fib
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プログラムを開始するには、3つのトークンを送信する必要があります。

 _ (: 1, : fib, : 2); _ (: 1, : fib, : 2); _ (: 1, : fib, : 3);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ストリーミングプログラムの実行の結果として、トークンのセットがホストに送信されます。各トークンには、コンテキストフィールドにフィボナッチ数が、データフィールドには数自体が含まれます。 別のトークン（グラフ上で破線でマークされている）が「どこにも」送信されないことに注意してください。より正確には、トークンとペアになっているためにノードの実行を開始しません。 ノードコードに別の条件チェック（i <MAX_I-2）を追加するか、ソフトウェアまたはハードウェアの「ガベージコレクター」を整理することにより、それを取り除くことができます。

例2.マトリックスの追加

ここで、データによる反復間に依存関係がない例について考えてみましょう。行列C [i、j] = A [i、j] + B [i、j]の追加。

 int A [MAX_I][MAX_J]; int B [MAX_I][MAX_J]; int C [MAX_I][MAX_J]; GetSomeData (A, B); for (i = 0; i < MAX_I; i++) for (j = 0; j < MAX_J; j++) { C[i,j] = A[i,j] + B[i,j]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すべての（MAX_I * MAX_J）反復を同時に実行できます。 これは、行列加算行列がどのように見えるかです：





この場合のコンテキストは、2座標構造{i; j}。 これを念頭に置いて、グラフノードは次のようになります。

  add (:  A,  B)  {i, j} = _(A);  result = _(A) + _(B); _ (: result, : host, : {i, j});   add
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここには国境チェックがないことに注意してください！ 反復回数は、入力データの次元に基づいて自動的に選択されます。 ところで、入力は次の形式で入力する必要があります。

 _ (: A[0, 0], : add, : {0, 0}); _ (: B[0, 0], : add, : {0, 0}); _ (: A[0, 1], : add, : {0, 1}); _ (: B[0, 1], : add, : {0, 1}); ... _ (: A[MAX_I-1, MAX_J-1], : add, : {MAX_I-1, MAX_J-1}); _ (: B[MAX_I-1, MAX_J-1], : add, : {MAX_I-1, MAX_J-1});
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

重要な要素のみが実際に送信および処理されるため、データフローシステムはスパースデータの処理に非常に効果的です。

ハイブリッドデータフローアーキテクチャ

残念ながら、MIT Static Dataflow MachineやManchester Dataflow Machineで説明されているような「クリーン」なストリーミングアーキテクチャには、多くの弱点がありました。

• データフローマシンは、同時実行に大きな機会を提供しました。 この利点の裏側は、計算グラフの連続したセクションで、パフォーマンスの急激な低下を示したことです。
• アクチュエータのロードは、可能な最大値からはほど遠いものでした。 ほとんどのコンピューター時間は、オペランドの一致の検索、命令のフェッチに費やされ、アクチュエーターはこの間ずっとアイドル状態で、トークンの各ペアに対して1つの命令のみを実行しました。
• 一致するデバイスを設計することは困難でした。 同じサイズの従来のRAMと比較して、連想メモリはより複雑で、より高価で、より遅く、より多くのスペースを消費し、より多くのエネルギーを消費します。
• データフロー制御の原理では、効率的なパイプラインを編成できませんでした。 ほとんどすべてのデバイスは非同期で動作し、通信回線のバッファとキューが必要でした。
• 従来のマルチプロセッサアーキテクチャと比較して、スイッチングネットワークの負荷はデータフローマシンの方がはるかに大きかった。 結局のところ、実際には、各操作で2つのトークンを転送する必要がありました。

これらの問題を解決するために、データフローアーキテクチャと制御フローアーキテクチャの両方の要素を組み合わせたハイブリッドアーキテクチャが登場し始めました。

スレッド化されたデータフロー

この用語に対するロシア語への適切な翻訳はありません。 このアプローチの本質は、スレッド（順次実行される命令のセット）を置き換えることによって並列化できない計算グラフの連続したセクションを置き換えることです。 「余分な」中間トークンはすぐに消え、エグゼクティブデバイスの負荷が増加します。 スレッド化されたデータフローの原理は、1989年にEpsilonプロセッサ[21]で「ハードウェアで」具現化されました。

粗粒度のデータフローアーキテクチャ

スレッド化されたデータフローのさらなる開発は、いわゆる大粒度データフローです。 多くの場合、「純粋な」データフローの並列性が冗長であることが明らかになったとき、個別のステートメントからではなくブロックからフローグラフを構築するという決定が下されました。 したがって、粗粒度アーキテクチャでは、各ノードは単一の命令ではなく、古典的な順次プログラムです。 ノード間の相互作用は、データフローの原則に従って実行されます。 このアプローチの利点の1つは、従来のフォンノイマンプロセッサをアクチュエータとして使用できることでした。 「粗視化」という名前にもかかわらず、タスクが分割されるブロックは、たとえばクラスターシステムよりもはるかに小さいことに注意してください。 典型的なブロックサイズは、10-100命令と16-1Kバイトのデータです。

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

ベクトルストリーミングシステムでは、トークンには1つの値ではなく、一度に多くの値が含まれます。 したがって、演算はオペランドのペアに対してではなく、ベクトルのペアに対して実行されます。 そのようなシステムの例は、SIGMA-1（1988）マシン[22]です。 場合によっては、ベクターモードはシステムの一部のエグゼクティブデバイスのみでサポートされます。 多くの場合、一度に複数のアプローチを組み合わせたハイブリッドアーキテクチャも使用されます。たとえば、粗いアーキテクチャとベクトル操作を実行する機能があります。

再構成可能なシステム

FPGAテクノロジーの開発により、データフローアーキテクチャに対する根本的に新しいアプローチが可能になりました。 特定の問題の解決に焦点を合わせたマシンを組み立てたらどうなるでしょうか？ 目的の計算グラフを回路レベルで直接実装すると、驚くべき結果が得られます。 複雑で低速のマッチングデバイスの代わりに、1つの機能モジュールから別のモジュールへの無条件のデータリダイレクトを使用できます。 アクチュエータ自体を目的のタスクに合わせて「シャープ」にすることもできます。算術の種類、ビット深度、サポートされている操作の目的のセットを選択します。

もちろん、このようなマシンは非常に高度に特殊化されますが、FPGAの利点は、再プログラミングを繰り返す可能性にあります。 したがって、個々のタスクごとに必要なアーキテクチャが組み立てられます。 一部のシステムでは、プロセスの再構成も可能です。 FPGAチップに基づく再構成可能なシステムは現在、PC用の「アクセラレータ」ブロックから数TFlops程度の容量のシステムまで、さまざまな形式で大量生産されています[31] 。

再構成可能なアーキテクチャの欠点は次のとおりです。

• 基本的なシングルタスク。 新しいタスクを開始するには、システムを停止し、その一部であるFPGAを再プログラムする必要があります。
• プログラミングの難しさ。 各タスクのプログラミングには、特定のタスクのコンピューティングアーキテクチャ全体の合成が含まれます。
• 冗長なハードウェアの複雑さ。 FPGAの柔軟性の裏側は、計算に直接関与せず、再構成のみに役立つ要素の大部分がチップ上に存在することです。 ただし、これらの要素はエネルギーを消費し、動作中に熱を生成するため、システムのエネルギー性能が低下します（Gflops / W）。

データフローアーキテクチャのプログラミング

データフローパラダイムでのプログラミングは、通常の構造とは大幅に異なりますが、機能に近いものです。 変数、配列、その他の名前付きメモリ領域はありません;通常の意味で呼び出されるプロシージャや関数はありません。 ストリームプログラミングは、 単一の割り当ての原則を使用します。 各データユニット（通常はトークン）は、作成時に1回だけ値を受け取り、後でのみ読み取ることができます。 この原理は、計算グラフのブランチの単方向性を反映しています。

データフローでは、残念ながら、プログラミング標準は開発されていません。 通常、言語はアーキテクチャごとに開発されます。 最も有名ないくつかを紹介します。

ヴァル

VAL（Value-oriented Algorithmic Language） [41]は、1979年にマサチューセッツ工科大学（MIT）で、特にMIT Dataflow Machine向けに開発されました。 たとえば、VALの階乗の計算は次のようになります。

 for Y:integer := 1; P:integer := N; do if P ~= 1 then iter Y := Y*P; P := P-1; enditer; else Y endif endfor
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

サイザル

1983年に登場したSISAL（単一の割り当て言語でのストリームと反復） [42]は、VALのさらなる発展です。 VALとは異なり、SISALでは再帰を使用できます。

階乗計算：

 function factorial( n : integer returns integer ) if n <=1 then 1 else n * factorial( n - 1 ) end if end function
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

中間の habrayuzerからの再帰なしのオプション：

 function factorial (n : integer returns integer) for i in 1, n returns value of prod i end for end function
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Id

Id [43]は、MITで1970年代後半から1980年代初頭に作成された汎用並列言語です。 Idのさらなる研究により、平行したHaskellの方言であるpHが開発されました。

Idの階乗：

 ( initial j <- n; k <- 1 while j > 1 do new j <- j - 1; new k <- k * j; return k )
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、このプログラムの計算グラフは次のようになります。

明Luc

Lucid言語[44] [45]は 、1976年にBill WadgeとEd Ashcroftによって開発されました。 値フロー（変数のアナログ）とフィルター、またはコンバーター（関数のアナログ）の概念で動作します。

明idの階乗：

 fac where n = 0 fby (n + 1); fac = 1 fby ( fac * (n + 1) ); end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

クイル

Quil（2010） [46] -Lucidに基づく言語で、現在作業中です。 言語サイトにはオンラインインタープリターがあります。そのため、Quilの階乗計算は読者の独立したタスクとして残します。

おわりに

ストリーミングアーキテクチャの「ブーム」は1970年代および80年代に発生し、データフローへの関心は徐々に薄れていきました。 現在、ストリームコンピューターの要素は、DSP（シグナルプロセッサ）、ネットワークルーター、GPUのアーキテクチャに見られます。 しかし、徐々に、ますます多くの専門家が高性能コンピューティングのフレームワークのデータフローパラダイムに再び目を向けています。 これはおそらく、今日のフォンノイマンアーキテクチャがスケーラビリティの限界に近づいているという事実に起因している可能性があり、生産性をさらに高めるには新しいアプローチが必要です。

ソフトウェアとハ​​ードウェアの間の境界線が徐々に消去される、再構成可能なアーキテクチャは多少異なります。 未来はどんなテクノロジーですか？ 質問は未解決のままです。



ボーナスゲーム。 最も好奇心の強い読者には、記事の各部分のタイトルの「注意を引くための画像」にアルゴリズムのどのグラフが描かれているかを判断することをお勧めします。 頑張って

---

文学

ソースの番号付けは、最初の部分から続けられます。

ハイブリッドデータフローシステム

[21] -Epsilonデータフロープロセッサ、VG Grafe、GS Davidsonなど。

[22] -データフロースーパーコンピューターSIGMA-1での効率的なベクトル処理。

再構成可能なシステム

[31] -動的に調整可能なアーキテクチャを備えたマルチプロセッサコンピューティングシステムのファミリ、N.N。 ドミトリエンコ、I.A。 カリャエフなど。

[32] -マルチFPGAプラットフォームでの高性能デジタル信号処理のための動的に再構成可能なデータフローアーキテクチャ、Voigt、S.-O.、Teufel、T。

データフローシステムのプログラミング言語

[41] -VAL-価値志向のアルゴリズム言語

[42] -サイザル言語のチュートリアル

[43] -ID言語リファレンスマニュアル、Rishiyur S. Nikhil、1991年

[44]-データフロープログラミング言語のLUCID、Academic Press Professional、Inc. 米国カリフォルニア州サンディエゴ1985 ISBN：0-12-729650-6

[45] -Lucidでの流体プログラミング

[46] -クイル言語