第７章ステートメントレベルでの並列化明石研究室 6311617 大木和田留概要 • Ｃ言語は逐次的であるＣＰＵに合わせて逐次的な命令を記述するように設計された言語であり、この章ではＣ言語による逐次的プログラミングと並列化、高速化されたハードウェア間の相違について記述している。 7.1 FPGAを用いた計算 • 従来のＣＰＵと同様に制御回路、算術演算装置、クロック制御は存在する • 但し、ＦＰＧＡにおいての計算は加算器、減算器、乗算器のように予めその用途ごとの演算装置として設計されたものによって処理される • ＣＰＵと同じくしてこれらの複数インスタンスが並列処理を可能にしているのだがＦＰＧＡでは利用可能なハードウェアと接続している装置の数に依存して並列化の限界が決まる • ＣＰＵとＦＰＧＡは共にクロックにより演算処理の速度を制御している • 演算装置ごとに固有のサイクル内で1つのタスクを処理するので、結果として最大クロック数は演算装置のパフォーマンスに依存している • ＣＰＵでは１クロックでいくつかの算術演算をこなしているのに対し、ＦＰＧAでは複数のクロックで異なる算術演算を各々異なる比率で処理している • ＦＰＧＡも結局はＣＰＵのようにどのデータがどの演算装置に送られ出力結果がどこへ送られるのかを示すために処理精度を保つコントローラの導入が不可欠である • ＣＰＵと異なることとしてコントローラは実行されているアルゴリズム固有のものを使用できる • 生成されるハードウェアの構造がＣＰＵと酷似しているのならば計算の高速化は何に起因しているのか？ • 近代のＣＰＵに特有の多くの欠点は計算のモデル生成をすることにより回避できる • 第一に従来のＣＰＵはデータをデコードしたり様々なものを実行しているため制御と計算を同時に実行できない • それに対し計算に特化したＦＰＧＡの場合、これらの処理は演算装置と並列に処理が可能なコントローラによって並列的に実行することができる（最近の高性能ＣＰＵはパイプライン化、プレフェッチにより並列処理に優れているが） • 第二にソフトウェアのプロセスを直にハードウェアにコンパイルすることで演算装置を必要な限りいくらでも生成することが可能であると言われている（これに対し一般用途のＣＰＵは固定の装置しか持たない） • 第三に生成されたハードウェアは元のアルゴリズムにおいての複数の異なるステートメントと最適化された命令パイプラインにより形成された1サイクルでの処理をする • 最後にＣＰＵは一般的にＦＰＧＡ実行に伴い生成されたハードウェアは相互、またはI/O処理に対し並列的に実行され複数のメモリ処理を支えるＲＡＭのブロックや外部資源を利用できる（ＣＰＵは一般的にメモリ資源のみを利用する） 7.2 Ｃ言語と並列化 • プログラミング言語の意味を理解することによりプログラマーのデバッグの効率があがる • いかなる最適化を目的とするときもアルゴリズムを可能な限りシンプルに設計し、目標の実行速度が達成できるまでコードを改良することが最善である • この章ではハードウェア上でどの程度処理が行われているのか、シングルプロセス内での並列化を説明し、続く３章では実際に高速化の具体例を紹介する • 次章ではシステムレベルでの並列化の例 7.3 命令レベルでの並列化 • Impulse C toolsはCとRTLオプティマイザーから成る（一般的なFPGAで特に使われるStage Masterと同様の一般C言語を最適化する） • Impulse Cにより実行速度と回路構成の大きさを最善のものにするためにこれらのオプティマイザーによりどのようにCのコードが並列化されるかについての最低限の知識が必要である • プロセスやループ文における個々のブロック単位での最適化は可能である • 各々のブロックに対し命令のパイプライン化、データが衝突しない命令をスケジュールすることでオプティマイザーは命令ステージ数を最小限に抑える • 逐次的なアルゴリズム文から最適化されたハードウェア同様のパフォーマンスを得るためには並列化は欠かせないパイプライン生成 • PIPELINE pragmaを用いてパイプライン化が可能な特定のステージを並列化する • パイプライン化ができなければそのステージは逐次的に生成され、ステージ内の全ての文は1クロック内で逐次的に実行されることとなるＣのコードにおける命令レベルでの3つの並列化方法 1. 複合文の副演算は並列化できる、例えばx=(a+b)*(c+d) は従来のプロセスでは乗算が実行される前に加算を実行し、異なる2つの命令サイクルを必要としていたが2つの加算の合計は並列的に同じサイクルで実行できる 2. 相関がない下記のような命令は並列化できる x=a+b; x=a+c; これらのような２文、あるいはそれ以上のものは並列的にハードウェアで実行でき、1クロックで処理できる 3. ループ文の繰り返しはパイプライン化により並列的に実行でき、パイプライン化することにより現在の繰り返しを実行途中でも次の繰り返しを並列的に実行できるオプティマイザー処理 • Impulseオプティマイザー（Stage Master)の基本処理はCの手続きを細分化し各々の処理を 1つかそれ以上のステージに割り当てる、それらのステージはハードウェアでの１クロックサイクルで実行される • しかし例外的に特定のステージが外部の資源を待機している時はデータが来るまで１クロックかそれ以上の遅延を引き起こす • ハードウェアコントローラはどのステージが現在実行されていて、次にどのステージが実行されるかを制御している • オプティマイザーは以下の４つの過程に基づき実行される 1. 内部ループの展開し並列化のためにコードのブロックを複製する 2. ブロックを実行するためのスケジューリングを行い可能な限り最小限のステップ数、ステージ数に抑える 3. 個々のステージの遅延のバランスを取る 4. 次（またはその先も含む）の繰り返しをいつ現在の繰り返しと並列処理するかを資源の制限と繰り返しの相関について分析し決定する計算式レベルでの最適化 • オプティマイザーは自動的に複数の式や文の並列化を行う、例えば以下のコード X = a + b + c; X = X << 2; Y = a - c; ではオプティマイザーは最初の文の２つの加算、２文目のシフト演算、そして３つ目の減算を１つのステージに割り当てるしかし多くの処理が１つのステージ内に割り当てられていると最大クロック速度は著しく低下する（これは処理の実行に必要な回路の大きさに関係なく各々のステージは１サイクルで実行されるからである）但しImpulse C付属のStageDelayを用いることによりプログラマーはオプティマイザーが１ステージに割り当ててしまったことによる最長の遅延の原因を特定し制御することができるブロック内での最適化 • 基本的なブロックとは if,while など介入制御文を必要としない連続的な固まりのことである、例えば if(odd){ x = a+b+c; x = x << 2; } y = a – c; という固まりにおいてオプティマイザーは (a + b + c) << 2 を第１ステージに割り当て、a – cの実行を第2ステージに割り当てる