自動並列化

自動並列化（ auto parallelization）は、共有メモリ型マルチプロセッサ（SMP）マシンで複数のプロセッサを同時に使用できるように、シーケンシャルコードをマルチスレッド化および/またはベクトル化コードに変換することを指します。 ^[1]シーケンシャルプログラムの完全自動並列化は、複雑なプログラム分析が必要であり、最適なアプローチがコンパイル時には不明なパラメータ値に依存する可能性があるため、困難です。^[2]

自動並列化が最も重点を置くプログラミング制御構造はループです。これは、一般に、プログラムの実行時間の大部分が何らかのループ内で行われるためです。ループの並列化には、パイプラインマルチスレッドと巡回マルチスレッドという 2 つの主なアプローチがあります。 ^[3]たとえば、各反復で 100 個の操作を適用し、1,000 回の反復を実行するループを考えてみましょう。これは、100 列 x 1,000 行のグリッド、合計 100,000 個の操作と考えることができます。巡回マルチスレッドでは、各行を異なるスレッドに割り当てます。パイプラインマルチスレッドでは、各列を異なるスレッドに割り当てます。

これは、スキャナが入力ソース ファイルを読み取って、すべての static および extern の使用を識別する最初の段階です。ファイル内の各行は、事前定義されたパターンに対してチェックされ、トークンに分離されます。これらのトークンは、後で文法エンジンによって使用されるファイルに保存されます。文法エンジンは、事前定義されたルールに一致するトークンのパターンをチェックして、コード内の変数、ループ、制御ステートメント、関数などを識別します。

アナライザーは、同時に実行できるコード セクションを識別するために使用されます。アナライザーは、スキャナー パーサーによって提供される静的データ情報を使用します。アナライザーは、まず、完全に独立したすべての関数を検出し、それらを個別のタスクとしてマークします。次に、アナライザーは依存関係があるタスクを検出します。

スケジューラは、実行時間と開始時間の観点から、すべてのタスクとそれらの相互依存関係をリストします。スケジューラは、使用するプロセッサの数またはアプリケーションの合計実行時間の観点から最適なスケジュールを作成します。

スケジューラは、すべてのタスクのリストと、タスクが実行されるコアの詳細、およびタスクの実行時間を生成します。コード ジェネレーターは、実行中にスケジューラによって読み取られる特別な構造をコードに挿入します。これらの構造は、特定のタスクがどのコアで実行されるかを、開始時間と終了時間とともにスケジューラに指示します。

循環マルチスレッド並列化コンパイラは、各反復を別々のプロセッサで同時に実行できるようにループを分割しようとします。

コンパイラは通常、実際の並列化の前に 2 回の分析パスを実行して、次のことを判断します。

• ループを並列化しても安全ですか？この質問に答えるには、正確な依存性分析とエイリアス分析が必要です。
• 並列化を行う価値はあるでしょうか? この答えを得るには、プログラムのワークロードと並列システムの容量の信頼性の高い推定 (モデリング) が必要です。

コンパイラの最初のパスでは、ループのデータ依存性分析を実行して、ループの各反復を他の反復から独立して実行できるかどうかを判断します。データ依存性は対処できる場合もありますが、メッセージの受け渡し、共有メモリの同期、またはその他のプロセッサ通信方法の形で追加のオーバーヘッドが発生する可能性があります。

2 番目のパスでは、並列化後のコードの理論的な実行時間とコードの順次実行時間を比較して、並列化の取り組みを正当化しようとします。直感に反しますが、コードは必ずしも並列実行のメリットを得られるわけではありません。複数のプロセッサを使用することで発生する余分なオーバーヘッドは、並列化されたコードの潜在的な高速化を阻害する可能性があります。

任意の呼び出しで、ループのすべての反復を同時に実行できる場合、そのループは DOALL と呼ばれます。

以下のFortranコードは DOALL であり、各反復が他の反復から独立しているため、コンパイラによって自動的に並列化でき、配列の最終結果はz他の反復の実行順序に関係なく正しいものになります。

   i = 1 、n z ( i ) = x ( i ) + y ( i )とします。   
         
   

このような DOALL ループを持つ、並列処理に適した問題はたくさんあります。たとえば、レイ トレーシング ムービーをレンダリングする場合、ムービーの各フレームを個別にレンダリングしたり、1 つのフレームの各ピクセルを個別にレンダリングしたりできます。

一方、次のコードは、 の値がz(i)前の反復の結果に依存するため、自動並列化できませんz(i - 1)。

   i = 2 、n z ( i ) = z ( i - 1 ) * 2とします。   
         
   

これは、コードを並列化できないことを意味するものではありません。実際、これはDOALLループと同等です。

   i = 2 、n z ( i ) = z ( 1 ) * 2 ** ( i - 1 )とします。   
         
   

しかし、現在の並列化コンパイラは通常、これらの並列性を自動的に実現することができず、そもそもこのコードが並列化の恩恵を受けるかどうかは疑問です。

パイプライン化されたマルチスレッド並列化コンパイラは、ループ内の一連の操作を一連のコード ブロックに分割して、各コード ブロックを別々のプロセッサで同時に実行できるようにします。

特にパイプとフィルターを使用するシステムでは、このような比較的独立したコード ブロックを持つ、満足のいく並列処理の問題が数多くあります。

たとえば、テレビの生放送を制作する場合、次のタスクを 1 秒間に何度も実行する必要があります。

1. 画像センサーから生のピクセルデータのフレームを読み取り、
2. 生データに対してMPEGモーション補正を行う。
3. エントロピーは動きベクトルやその他のデータを圧縮し、
4. 圧縮されたデータをパケットに分割し、
5. 適切なエラー訂正を追加し、FFTを実行してデータパケットをCOFDM信号に変換し、
6. COFDM 信号をテレビアンテナから送信します。

パイプライン化されたマルチスレッド並列化コンパイラは、これら 6 つの操作をそれぞれ別のプロセッサ（おそらくシストリック アレイ内に配置されます）に割り当て、1 つのプロセッサの出力を次のプロセッサに転送するための適切なコードを挿入することができます。

^{最近の研究では、GPU [4]}とマルチコアシステム^[5]のパワーを使用して、実行時にこのような独立したコードブロック (または単にループの独立した反復) を計算することに焦点を当てています。アクセスされたメモリ (直接的か間接的かに関係なく) は、ループの異なる反復に対して簡単にマークされ、依存関係の検出のために比較できます。この情報を使用して、反復はレベルにグループ化され、同じレベルに属する反復は互いに独立し、並列に実行できます。

コンパイラやツールによる自動並列化は、以下の理由により非常に困難である。^[6]

• 間接アドレス指定、ポインタ、再帰、または間接関数呼び出しを使用するコードの場合、コンパイル時にそのような依存関係を検出するのが難しいため、依存関係の分析は困難です。
• ループの反復回数は不明です。
• グローバル リソースへのアクセスは、メモリ割り当て、I/O、共有変数の観点から調整するのが困難です。
• 入力依存間接参照を使用する不規則なアルゴリズムはコンパイル時の解析と最適化を妨害する。 ^[7]

完全自動並列化には固有の難しさがあるため、並列プログラムを高品質にするためのより簡単な方法がいくつかあります。その 1 つは、プログラマがプログラムに「ヒント」を追加してコンパイラの並列化をガイドできるようにすることです。分散メモリシステムの場合はHPF、共有メモリシステムの場合はOpenMPまたはOpenHMPPなどです。もう 1 つの方法は、プログラマと並列化ツール/コンパイラの間に対話型システムを構築することです。有名な例としては、Vector Fabricsの Pareon、SUIF Explorer (スタンフォード大学中間形式コンパイラ)、Polaris コンパイラ、および ParaWise (旧称 CAPTools) があります。最後に、もう 1 つの方法は、ハードウェアでサポートされる投機的マルチスレッドです。

自動並列化のための研究用コンパイラのほとんどは、Fortranプログラムを考慮します^{[引用が必要]。これは、Fortran が}Cなどの言語よりもエイリアシングに関して強力な保証を提供しているためです。典型的な例は次のとおりです。

• パラダイムコンパイラ
• Polaris コンパイラ
• Rice Fortran D コンパイラ
• SUIFコンパイラ
• Vienna Fortran コンパイラ

• ループネストの最適化
• 並列化契約
• 多面体モデルは多面体モデルとも呼ばれます
• スケーラブルな並列処理
• ビーエムディーエム
• ベクトル化
• シーケンスL

• Pountain, Dick (1989 年 12 月)。「並列プログラムの構成、パート 1: 現在開発中の Occam Transpiler により、並列処理用のソフトウェアの作成が容易になります」。BYTE 。第 14 巻、第 13 号。McGraw -Hill, Inc. pp. 349–352。ISSN 0360-5280。ark  :/13960/t34188734。2022年1 月 6 日に閲覧。(注: Occam トランスパイラという用語は、通常のoccamプログラムを入力として受け取り、リンクとチャネルの割り当てなどが追加された新しい occam ソース コードを出力として導出し、トランスピュータのネットワーク上で可能な限り効率的に並列処理を実行するように構成するプリプロセッサとして機能するソースからソースへのコンパイラの同義語として使用します。)