Loading article…
自動並列化、または自動並列化とは、共有メモリマルチプロセッサ（SMP）マシンで複数のプロセッサを同時に使用するために、逐次コードをマルチスレッドコードやベクトル化コードに変換することを指します。 [ 1 ]逐次プログラムの完全な自動並列化は、複雑なプログラム解析が必要であり、最適なアプローチはコンパイル時に不明なパラメータ値に依存する可能性があるため、困難です。[ 2 ]
自動並列化が最も重視するプログラミング制御構造はループです。これは、一般的にプログラムの実行時間の大部分が何らかの形式のループ内で発生するためです。ループの並列化には、パイプライン型マルチスレッドとサイクリック型マルチスレッドの 2 つの主要なアプローチがあります。 [ 3 ]例えば、各反復で 100 回の操作を実行し、1000 回反復するループを考えてみましょう。これは、100 列 × 1000 行のグリッド、合計 100,000 回の操作と考えることができます。サイクリック型マルチスレッドでは、各行を異なるスレッドに割り当てます。パイプライン型マルチスレッドでは、各列を異なるスレッドに割り当てます。
これは、スキャナが入力ソースファイルを読み込み、すべての静的および外部使用を識別する最初の段階です。ファイル内の各行は、事前に定義されたパターンと照合され、トークンに分割されます。これらのトークンはファイルに保存され、後で文法エンジンによって使用されます。文法エンジンは、事前に定義されたルールに一致するトークンのパターンをチェックし、コード内の変数、ループ、制御文、関数などを識別します。
アナライザーは、並行して実行可能なコードセクションを特定するために使用されます。アナライザーは、スキャナ・パーサによって提供される静的データ情報を使用します。アナライザーはまず、完全に独立した関数をすべて見つけ出し、それらを個別のタスクとしてマークします。次に、アナライザーは依存関係のあるタスクを特定します。
スケジューラは、すべてのタスクとその相互依存関係を、実行時間と開始時間の観点から一覧表示します。スケジューラは、使用するプロセッサ数またはアプリケーションの総実行時間の観点から、最適なスケジュールを作成します。
スケジューラは、すべてのタスクのリストと、それらが実行されるコアの詳細、および実行時間を生成します。コードジェネレータは、スケジューラが実行時に読み取る特別な構造をコードに挿入します。これらの構造は、特定のタスクがどのコアで実行されるか、および開始時刻と終了時刻をスケジューラに指示します。
循環型マルチスレッド並列化コンパイラは、ループを分割して、各反復処理を別々のプロセッサで同時に実行できるようにしようとします。
コンパイラは通常、実際の並列化の前に2回の解析を行い、以下の事項を決定します。
コンパイラの最初のパスでは、ループのデータ依存性分析を行い、ループの各反復処理が他の反復処理から独立して実行できるかどうかを判断します。データ依存性は対処可能な場合もありますが、メッセージパッシング、共有メモリの同期、またはその他のプロセッサ間通信方法といった追加のオーバーヘッドが発生する可能性があります。
2回目の検証では、並列化後のコードの理論的な実行時間と、コードの逐次実行時間を比較することで、並列化の取り組みを正当化しようと試みます。しかし、やや直感に反するかもしれませんが、コードは必ずしも並列実行によって恩恵を受けるとは限りません。複数のプロセッサを使用することに伴う余分なオーバーヘッドが、並列化されたコードの潜在的な高速化効果を相殺してしまう可能性があるからです。
ループは、任意の呼び出しにおいて、そのすべての反復処理を同時に実行できる場合、DOALLと呼ばれます。
以下のFortranコードは DOALL であり、各反復処理が互いに独立しているため、コンパイラによって自動的に並列化できます。また、配列の最終結果は、z他の反復処理の実行順序に関係なく正しくなります。
do i = 1 , n z ( i ) = x ( i ) + y ( i ) enddoこのようなDOALLループを持つ、並列処理に適した問題は数多く存在する。例えば、レイトレーシングで動画をレンダリングする場合、動画の各フレームを個別にレンダリングでき、さらに1つのフレームの各ピクセルも個別にレンダリングできる。
一方、次のコードは、の値がz(i)前の反復の結果に依存するため、自動並列化できませんz(i - 1)。
do i = 2 , n z ( i ) = z ( i - 1 ) * 2 enddoこれは、このコードが並列化できないという意味ではありません。実際、これは DOALL ループと同等です。
do i = 2 , n z ( i ) = z ( 1 ) * 2 ** ( i - 1 ) enddoしかし、現在の並列化コンパイラは通常、これらの並列性を自動的に引き出すことができず、そもそもこのコードが並列化によって恩恵を受けるかどうかは疑問である。
パイプライン型マルチスレッド並列コンパイラは、ループ内の一連の操作を複数のコードブロックに分割し、各コードブロックを別々のプロセッサで同時に実行できるようにします。
特にパイプやフィルタを使用するシステムでは、比較的独立したコードブロックを持つ、並列処理に適した問題が数多く存在します。
例えば、生放送のテレビ番組を制作する場合、次のような作業を1秒間に何度も実行する必要があります。
パイプライン処理によるマルチスレッド並列化コンパイラは、これら6つの操作をそれぞれ異なるプロセッサに割り当て、おそらくシストリック配列に配置し、あるプロセッサの出力を次のプロセッサに転送するための適切なコードを挿入することができる。
最近の研究では、GPU [ 4 ]やマルチコアシステム[ 5 ]のパワーを利用して、実行時にこのような独立したコードブロック（あるいは単にループの独立した反復）を計算することに焦点が当てられています。アクセスされたメモリ（直接アクセスか間接アクセスかを問わず）は、ループの異なる反復ごとに簡単にマークすることができ、依存関係の検出のために比較できます。この情報を使用して、反復はレベルごとにグループ化され、同じレベルに属する反復は互いに独立しており、並列に実行できます。
コンパイラやツールによる自動並列化は、以下の理由により非常に困難です。[ 6 ]
完全自動並列化には本質的に困難が伴うため、より高品質な並列プログラムを実現するためのより簡単な方法がいくつか存在する。その一つは、プログラマがプログラムに「ヒント」を追加してコンパイラの並列化を誘導できるようにする方法である。例えば、分散メモリシステムの場合はHPF 、共有メモリシステムの場合はOpenMPやOpenHMPPなどが挙げられる。もう一つの方法は、プログラマと並列化ツール／コンパイラの間で対話型システムを構築することである。代表的な例としては、Vector FabricsのPareon、SUIF Explorer（スタンフォード大学中間フォーマットコンパイラ）、Polarisコンパイラ、ParaWise（旧CAPTools）などがある。最後に、ハードウェアでサポートされる投機的マルチスレッド化も有効な方法である。
自動並列化のための研究用コンパイラのほとんどはFortranプログラムを対象としています。これは、FortranがCなどの言語よりもエイリアシングに関してより強力な保証を提供するためです。典型的な例は次のとおりです。
Aubert、Rubiano、Rusch、Seiller [ 8 ]は、 Cプログラムのループを自動的に並列化するために依存関係分析技術[ 9 ]を使用しました。