演習
マンデルブロットジェネレータの固定小数点実装を書いてください。
a.
異なるピクセルや異なるフレーム間でパフォーマンスが一定しないことに気がつくでしょう。
b.
一番内側のループ本体の演算強度は、メモリからアクセスされる1バイトあたりの演算で、どれくらいですか。 ARM CPUに対応するパフォーマンスバウンドは何ですか？
c.
Measure the following performance metrics for the innermost loop body:
▪
instructions per iteration
▪
instructions per operation
▪
CPI
▪
cache miss rate
d.
ループ本体で、以下のパフォーマンスを測定します。
インラインアセンブリを使用して最も内側のループ本体を実装し、パートcのメトリクスに対する性能の影響を測定します。コンパイラが生成したコードと比較した場合の速度向上はどの程度ですか。 最も外側の（行）ループに parallel-for 指令を適用する。
a.
最初のフレームについて、1スレッドと2スレッドの最も内側のループの各反復（多項式を評価する）に必要な平均サイクル数を測定する。
b.
静的スケジュールと比較して動的スケジュールを使用した場合の最初のフレーム内のすべてのピクセルを計算する時間を測定する。
マンデルブロ集合生成器に SIMD 操作を適用することが困難な理由は何ですか。
Linuxフレームバッファの実効書き込みスループットを測定してください。 ヒープから割り当てられたメモリ配列の書き込みスループットと同等か。
画像変換プログラムの演算強度を1ピクセルあたりの演算で計算せよ。 ARM CPUの実効メモリスループットを考えると、その性能限界はどの程度か？
OpenMPを使用して、固定小数点画像変換プログラムにマルチコアサポートを追加します。 これを行うには、最も外側（行）のループに並列用プラグマを適用します。
4コアのARM CPUでそのパフォーマンスを測定します。 1、2、3、および 4 つのスレッドで実行した場合、そのパフォーマンスはどのように変化するか。
intrinsics を使用して、イメージ変換プログラムの固定小数点バージョンに NEON SIMD サポートを追加してください。 4ウェイ演算を使用して、4つのピクセルのグループに対して、ソースピクセルの位置、分数の抽出、および重みの計算を行う。 これによりどの程度パフォーマンスが向上するか？
隣接するピクセルが異なる数の多項式評価を必要とする場合があり、多項式の各反復は前の評価に依存するので、SIMD命令を使用してマンデルブロー生成プログラムを簡単に最適化することはできない。 別の方法としては、ループをインラインアセンブリで実装し、少なくとも4回アンロールした後、ソフトウェアパイプライニングを使用してループのCPIを向上させるという方法があります。 この場合、アンロールされたループ内での条件分岐を避ける必要があります。 発散したc値はその後の評価でも発散し続けるので、4回反復の各グループの後にループ終了条件を確認するのを待つことができます。 しかし、Pc()が半径2円の外側で発散した後に追加の多項式評価を実行すると、固定小数点フォーマットの範囲要件を考慮する必要があります。 この最適化のための固定小数点範囲要件を再計算し、これが最大ズーム レベルをどの程度低下させるかを判断します。
固定小数点の主な利点は、演算レイテンシーの削減と、ある種のグラフィックス コードでの型変換を回避できることです。 第2章では、演算遅延の影響を受けやすいプログラム例として、ホーナー法を取り上げます。 ホーナー法のコードで固定小数点の範囲制限を許容できると仮定すると、固定小数点に変換することで性能は向上するのでしょうか？
3.6.5 節では、一般化された固定小数点加算プリプロセッサ・マクロの 2 つの異なる実装を示しました。 1 つは gcc で最大限の最適化を行って生成したもの、もう 1 つはインライン・アセンブリ言語を使って手作業でコーディングしたものです。
a.
両方の実装において、リード・アフター・ライトのデータ依存性を示してください。 プロセッサが1命令順発行で、すべての整数演算のレイテンシを4サイクルと仮定すると、両実装に必要なデータストール・サイクルの数はいくつになるか比較してください。
c.
3つすべての実装（コンパイラ生成、インラインアセンブリ、スケジュールされたインラインアセンブリ）が性能についてどのように特徴付けられるかを実証するコードを書いてください。
この質問では、セクション 3.6.6.
a で説明した一般化固定小数点乗算のインラインアセンブリ実装を調べます。
res = (((long long)op1 * (long long)op2) >> (rp1>rp2?rp1:rp2)) と同等のコンパイラ生成コードと比較して、命令数と実行性能の面でどのように比較されるのでしょうか? +（rp1>rp2 ? ((((long long)op1 * (long long)op2) >> (rp1-1))&1) :
(((long long)op1 * (long long)op2) >> (rp2-1))&1);
gccでコンパイルをする際には「-O3」「-marm」スイッチで確実に行うようにしましょう。
b.
multiply マクロのインラインアセンブリ版の命令をスケジュールして、データ依存のストールを最小にします。
c.
インラインアセンブリの実装において、基数点の位置がコードのように可変ではなく、固定であるように変更した場合、どの程度全体が達成されるか。 この質問には、命令数と実際の実行時の動作の両方を用いること。
マンデルブロー集合の画素値を計算するには、反復回数をR、G、Bの色チャンネルに変換する関数が必要である。 3つのチャンネルをすべて同じ値に設定するとグレー画像が生成されるため、各カラーチャンネル関数の傾きは一意でなければならず、どの傾きが最大であっても画像の色相は決定されます。
3.8.1節で述べたように、多項式の評価数はカラーチャンネルの範囲を超える値を超えてしまうことがあります。 潜在的なオーバーフローを回避するためには、各ピクセル値を計算する際に飽和演算を使用する必要があります。 この方法では、計算された値が最大許容値を超える場合、最大値に設定します。
8 ビット符号なし飽和乗算を実行する C マクロを記述します。 この関数は2つの8ビットオペランドを取り、積が255を超える場合は255に設定された8ビット積を生成する。
この演習では、マンデルブロ・ジェネレータの固定小数点型の精度を64ビットに高めることを検討します。
a.
1.5zoom のズームレートを使用して、この精度を超える前にフレームをどのレベルまでズームすることができますか。 このマクロは4つの32ビット加算を使用して128ビット加算を実行し、キャリーフラグを使用して各32ビットグループから次の最上位32ビットグループへのキャリーを実装できます。 このマクロをパートbの64ビット加算マクロの上に構築します。
図3.6に示すように、64ビット乗算を実行する簡単な方法は、それぞれが64ビット結果を生成する4つの32ビット乗算/シフト/累算操作を連続して実行します。
図3.6. 4ビット乗算器で実装した8ビット乗算器。
図では、値1110と1410を保持する2つの4ビット値AとBはそれぞれA1、A0とB1、B0という2ビット上下に分離されています。 積が4ビットであると仮定すると、8ビット積は、(A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) 2 + (A0*B0) と計算されます
これを64ビット積に適用するには、64ビット値のそれぞれを32ビットレジスタ2本に保持しなければなりません。
d.
これらのマクロを使用して、64ビットマンデルブロ集合ジェネレータを実装し、結果の性能差を測定する。
e.
両方のマクロをインラインアセンブリ言語で実装し、dの部分と比較してマンデルブロジェネレータの結果速度向上を測定する。