バイナリ モジュラー データフロー マシン

バイナリ モジュラー データフロー マシン( BMDFM ) は、複数のプロセッサを使用して共有メモリ対称型マルチプロセッシング(SMP) コンピュータでアプリケーションを並列実行し、単一のアプリケーションの実行を高速化できるようにするソフトウェア パッケージです。BMDFM は、以前は順次プログラムだった データフロー命令シーケンスの静的および主に動的なスケジュール設定により、並列性を自動的に識別して活用します。

BMDFM 動的スケジューリング サブシステムは、タグ付きトークンデータフローマシンの対称型マルチプロセッシング(SMP)エミュレーションを実行し、アプリケーションに透過的なデータフロー セマンティクスを提供します。並列実行の指示は必要ありません。

現在の並列共有メモリ SMP は複雑なマシンであり、高性能を達成するには多数のアーキテクチャの側面を同時に処理する必要があります。最近の技術計算用のコモディティ SMP マシンは、密に結合された多数のコアを持つことができます (良い例としては、Intel ( CoreまたはXeon ) またはIBM ( Power ) のマルチコア プロセッサに基づく SMP マシンがあります)。コンピュータ メーカーの発表によると、SMP ノードあたりのコア数は数年ごとに倍増する予定です。

マルチコア プロセッサは、ソフトウェアによって識別されるスレッド レベルの並列処理を活用することを目的としています。したがって、最も難しいタスクは、マルチコア プロセッサのパワーを効率的に活用してアプリケーション プログラムを並列処理する方法を見つけることです。フォーク ジョイン ランタイム ライブラリを使用した静的並列化の既存の OpenMP パラダイムは、ループを多用する通常の配列ベースの計算にのみ非常に有効に機能しますが、コンパイル時の並列化方法は一般に弱く、不規則なアプリケーションにはほとんど適用できません。

• 不確定な時間がかかる操作が多数あり、特定のデータがいつ利用可能になるかを正確に把握することが困難です。
• マルチレベル キャッシュを備えたメモリ階層では、メモリ アクセスのレイテンシが予測できません。
• マルチユーザー モードでは、他の人のコードがリソースを使い果たしたり、コンパイラが考慮できない方法で計算の一部を遅くしたりする可能性があります。
• コンパイル時の手続き間および条件間の最適化は困難です (多くの場合不可能です)。これは、コンパイラが条件がどの方向に進むかを把握できなかったり、関数呼び出し全体で最適化できなかったりするためです。

BMDFM技術は主に動的スケジューリングを使用してアプリケーションプログラムの並列性を活用し、コンパイル時の方法の欠点を回避します。^{[1] [2]} BMDFMはマルチコアSMP用の並列プログラミング環境であり、以下を提供します。

• 並列実行のためのディレクティブを必要としない従来のプログラミング パラダイム。
• システム内の利用可能なすべてのマルチコア プロセッサを自動的に使用して、自然で負荷分散された方法で並列処理を透過的に (暗黙的に) 活用します。

BMDFM は、既知のアーキテクチャ原則の利点を単一のハイブリッド アーキテクチャに統合し、動的スケジューリングのオーバーヘッドが無視でき、ボトルネックのないアプリケーションの暗黙的な並列処理を活用できるようにします。主に、基本的なデータフロー原則が使用されます。データフロー原則は、「命令または関数は、その引数がすべて準備でき次第実行できます。データフロー マシンは、実行時にすべてのデータのタグを管理します。データが計算されると、データは準備完了タグでマークされます。準備完了引数を持つ命令は、結果データが準備完了としてマークされて実行されます」と述べています。

BMDFM の主な機能は、最上位レベルで従来のプログラミング パラダイム、いわゆる透過的なデータフロー セマンティクスを提供することです。ユーザーは BMDFM を仮想マシン(VM) として理解します。仮想マシンは、アプリケーション プログラムのすべてのステートメントを並列に実行し、すべての並列化および同期メカニズムを完全に透過的にします。アプリケーション プログラムのステートメントは、任意のシングル スレッド プログラムを構成する通常の演算子です。これには、変数の割り当て、条件付き処理、ループ、関数呼び出しなどが含まれます。

以下に示すコードフラグメントがあるとします。

( setq a ( foo0 i )) # a = foo0 ( i ); ( setq b ( foo1 ( + i 1 ))) # b = foo1 ( i + 1 ); ( setq b ( ++ b )) # b ++ ; ( outf "a = %d \n " a ) # printf ( "a = %d \n " , a ); ( outf "b = %d \n " b ) # printf ( "b = %d \n " , b );              
          
              
          
          

最初の 2 つのステートメントは独立しているため、BMDFM のデータフロー エンジンは、それらを異なるプロセッサまたはプロセッサのコアで実行できます。最後の 2 つのステートメントも並列で実行できますが、"a" と "b" が計算された後のみです。データフロー エンジンは、実行時にデータフロー グラフを動的に構築できるため、依存関係を自動的に認識します。さらに、データフロー エンジンは出力ストリームを正しく順序付けして、結果を順番に出力します。したがって、順序外処理の後でも、結果は自然な方法で表示されます。

上記のコード フラグメントがループ内にネストされているとします。

( for i 1 1 N ( progn # for ( i = 1 ; i <= N ; i ++ ) { ( setq a ( foo0 i )) # a = foo0 ( i ); ( setq b ( foo1 ( + i 1 ))) # b = foo1 ( i + 1 ); ( setq b ( ++ b )) # b ++ ; ( outf "a = %d \n " a ) # printf ( "a = %d \n " , a ); ( outf "b = %d \n " b ) # printf ( "b = %d \n " , b ); )) # }                      
                  
                
                  
              
              
                          

BMDFM のデータフロー エンジンは、各反復で変数「a」と「b」を一意のコンテキストに保持します。実際には、これらは変数の異なるコピーです。コンテキスト変数は、命令コンシューマによって参照されるまで存在します。その後、参照されないコンテキストは実行時にガベージ コレクションされます。したがって、データフロー エンジンは、反復内のローカル並列処理とグローバル並列処理の両方を活用し、複数の反復を同時に実行できます。

BMDFM は、複数のアーキテクチャ パラダイム (フォン ノイマン、SMP、データフロー) を MIMD で統合した、便利な並列プログラミング環境であり、マルチコア SMP 用の効率的なランタイム エンジンです。

• まず、これはコモディティ SMP 上でマルチスレッドで実行されるハイブリッド データフロー エミュレーターです。SMP は MIMD を保証し、データフローは暗黙的な並列処理を活用します。
• 2 番目に、これはフォン ノイマン フロントエンド VM によって制御されるハイブリッド マルチスレッド データフロー ランタイム エンジンです。データフロー ランタイム エンジンは、タグ付きトークンのコンテキスト並列命令 (制限されたフォーク ジョイン パラダイムとは逆) を実行し、フォン ノイマン フロントエンド VM はコンテキストを初期化し、マーシャリングされた命令のクラスターをデータフロー ランタイム エンジンに供給します。
• 3 番目は、静的並列化と動的並列化のハイブリッドです。フォン ノイマン フロントエンド VM は、アプリケーションを並列マーシャリングされた命令のクラスターに静的に分割しようとしますが、データフロー ランタイム エンジンは、静的並列化メソッドを動的に補完します。

BMDFM は、従来のフォーク ジョイン ランタイム ライブラリの代わりに、不規則なアプリケーションを自動的に並列実行できる並列ランタイム エンジンの役割で使用することを目的としています。透過的なデータフロー セマンティクスにより、BMDFM はアプリケーション プログラマーにとってシンプルな並列化手法であると同時に、マルチコア SMP コンピューターにとってはるかに優れた並列プログラミングおよびコンパイル テクノロジです。

BMDFM の基本概念は、市場で入手可能な基礎となるコモディティ SMP ハードウェアに依存しています。通常、SMP ベンダーは、SVR4/POSIX UNIX インターフェイス (Linux、HP-UX、SunOS/Solaris、Tru64OSF1、IRIX、AIX、BSD、MacOS など) を備えた独自の SMP オペレーティング システム (OS) を提供しています。SMP OS 上で、マルチスレッド データフロー ランタイム エンジンは、データフロー マシンのソフトウェア エミュレーションを実行します。このような仮想マシンには、仮想マシン言語および C へのインターフェイスがあり、従来のプログラミングに透過的なデータフロー セマンティクスを提供します。

BMDFM は、いくつかのアーキテクチャ原則のハイブリッドとして構築されています。

• MIMD (複数命令ストリーム、複数データ ストリーム) は、コモディティ SMP によってサポートされます。
• データフロー エミュレーションによって暗黙的な並列実行が保証されます。
• フォン・ノイマン計算原理は、フロントエンド制御仮想マシンを実装するのに適しています。

アプリケーション プログラム (入力シーケンシャル プログラム) は、予備コード再編成 (コード再編成)、ステートメントの静的スケジューリング (静的スケジューラ)、およびコンパイル/ロード (コンパイラ、ローダ) の 3 つの段階で処理されます。静的スケジューリング段階後の出力は、ボトルネックを回避するように設計されたインターフェイスを介してマルチスレッド エンジンに供給される複数のクラスター フローです。複数のクラスター フローは、コンパイルされた入力プログラムをマーシャリングされたクラスターに分割したものと考えることができます。このクラスターでは、すべてのアドレスが解決され、コンテキスト情報を使用して拡張されます。マーシャリングされたクラスターに分割すると、マルチスレッドでロードできます。コンテキスト情報により、反復を並列処理できます。リスナー スレッドは、順序外処理後に出力ストリームを順序付けます。

BMDFM 動的スケジューリング サブシステムは、タグ付きトークン データフロー マシンの効率的な SMP エミュレーターです。共有メモリ プールは、入出力リング バッファ ポート(IORBP)、データ バッファ(DB)、および操作キュー(OQ) の 3 つの主要部分に分かれています。フロントエンド制御仮想マシンは、入力アプリケーション プログラムを静的にスケジュールし、入力プログラムのクラスター化された命令とデータを IORBP に配置します。リング バッファ サービス プロセス (IORBP PROC) は、データを DB に移動し、命令を OQ に移動します。操作キュー サービス プロセス (OQ PROC) は、必要なオペランドのデータにアクセスできる場合に、命令を実行準備完了としてタグ付けします。実行プロセス (CPU PROC) は、準備完了としてタグ付けされた命令を実行し、計算されたデータを DB または IORBP に出力します。さらに、IORBP PROC と OQ PROC は、コンテキストが処理された後にメモリを解放する役割を担います。コンテキストは、タグ付きトークン データフロー アーキテクチャに従って、異なる反復本体内のデータのコピーを表す特別な一意の識別子です。これにより、動的スケジューラは複数の反復を並行して処理できるようになります。

SMP OS で実行する場合、プロセスは利用可能なすべての実マシン プロセッサとプロセッサ コアを占有します。複数のプロセスが同じデータに同時にアクセスできるようにするために、BMDFM 動的スケジューラは SVR4/POSIX セマフォ操作を介して共有メモリ プール内のオブジェクトをロックします。ロック ポリシーは、複数の読み取り専用アクセスと変更用の排他的アクセスを提供します。

ANSI CおよびPOSIX ; UNIX System V (SVR4)をサポートするすべてのマシンでBMDFM を実行できます。

BMDFM は、以下の完全なマルチスレッド バージョンとして提供されます。

• x86 : Linux/32、FreeBSD/32、OpenBSD/32、NetBSD/32、MacOS/32、SunOS/32、UnixWare/32、Minix/32、Android/32、Win-Cygwin/32、Win-UWIN/32、 Win-SFU-SUA/32;
• x86-64 : Linux/64、FreeBSD/64、OpenBSD/64、NetBSD/64、MacOS/64、SunOS/64、Android/64、Win-Cygwin/64;
• VAX : Ultrix/32;
• Alpha : Tru64OSF1/64、Linux/64、FreeBSD/64、OpenBSD/64;
• IA-64 : HP-UX/32、HP-UX/64、Linux/64、FreeBSD/64;
• XeonPhiMIC : Linux/64;
• MCST-Elbrus : Linux/32、Linux/64;
• PA-RISC : HP-UX/32、HP-UX/64、Linux/32;
• SPARC : SunOS/32、SunOS/64、Linux/32、Linux/64、FreeBSD/64、OpenBSD/64;
• MIPS : IRIX/32、IRIX/64、Linux/32、Linux/64;
• MIPSel : Linux/32、Linux/64、Android/32、Android/64;
• PowerPC : AIX/32、AIX/64、MacOS/32、MacOS/64、Linux/32、Linux/64、FreeBSD/32、FreeBSD/64;
• PowerPCle : Linux/32、Linux/64;
• S/390 : zOS-USS/32、zOS-USS/64、Linux/32、Linux/64;
• M68000 : Linux/32;
• ARM : Linux/32、Linux/64、FreeBSD/64、Android/32、Android/64、MacOS/64;
• ARMbe : Linux/64;
• RISC-V : Linux/32、Linux/64;
• LoongArch : Linux/64;
• x86 : Win/32用の限定シングルスレッド バージョン。

• データフロー
• 並列コンピューティング
• 対称型マルチプロセッシング

• BMDFM公式サイト
• BMDFM 総合マニュアル
• YouTubeの BMDFM デモ ビデオ
• BMDFM GitHub リポジトリ
• BMDFM公式サイトのBMDFMダウンロードページ
• download3k の BMDFM ダウンロード ページ
• SourceForge の BMDFM ダウンロード ページ