
スーパースカラプロセッサのアイデアを探求する一連の記事の続き
OoOおよびフロントエンドスタックマシン。 この記事のトピックは、メモリアクセスの最適化です。
前の記事:
1-直線作品の説明
2-関数呼び出し、レジスターの保存
3-関数呼び出し、内部ルック
これまでのところ、スタックされたすべてのマシンの弱点、つまり過剰なメモリアクセスに注意を払っていません。
実際、スタックマシンの単純なコードジェネレーターが変数「a」の値を取得する場合、「push a」という命令を書き込みます。 スタックプロセッサは、既に計算された式を参照する機会を提供しません。
レジスタプロセッサの場合、コンパイラは一時変数をレジスタに配置できるようにすることでこの問題を解決します。 外側に登録されていないアーキテクチャに対して同様のメカニズムを考え出すことは価値があります。
ただし、「すべてがすでに私たちの前で盗まれている」という何かを発明する必要はほとんどありません(C)。
- ブックマークを導入する
- bookmark-コンパイラーが番号でアクセスできるレジスター、レジスター番号とブックマークは一致する必要はありませんが、これにより作業が楽になります
- 各関数のコンパイラーが持つブックマークの数を決定します
- 関数が開始すると、必要な数のレジスターがブックマークの下で強調表示され、関数が完了するまで解放できません
- ブックマークは登録ウィンドウに分類され、FILL / SPILLメカニズムがそれらに作用します
- コンパイラーは計算された値を価値があると見なす場合、たとえば、命令「bmk 1」でブックマークを設定します。これは、スタックの最上部の値がブックマーク番号1と見なされるようになったことを示します。重要ではないブックマーク、実装の詳細
- 将来、コンパイラがこのタブからの値を必要とする場合、たとえば次のように使用できます: 'add_bmk 1'、つまり スタックの最上部の値はブックマーク1の値と合計され、この値に置き換えられます
- プロセッサバックエンドの観点から、3番目の2つのレジスタを合計する古き良きモップが生成されます
- 算術および論理命令の2行目(add-> add_bmk、mul-> mull_bmk、cmp-> cmp_bmk)が必要ですが、それだけの価値があります
- またはより一般的なオプション-引数のいずれかまたは3つの(2)の結果-adress命令はブックマークにすることができます
- 使用するレジスタの数を最適化するために最大数を強調表示せずに、ブックマークの動的選択を想像できますが、これは(一見)ハードウェアにとってはあまりにも残酷です
その結果、コンパイラには最適化のための2つの比較的新しいリソースがあります。
1つ目は、ブックマークの識別と配置です。ブックマークの数は非常に多くなる場合がありますが、ブックマークがないために使用可能なレジスタの数に制限されません。 概して、これは「高速」スタックにあるローカル変数に相当します。
2つ目は、式を内部並列性が最大限に発揮される形式に変換することです。 コンパイラは、幅を広げることで式ツリーの高さを削減しようとします。
さて、レジスターとその配布に向けられていない従来の最適化手法を忘れないでください。
これを実装する方法を理解するために、それらを見てみましょう
LLVMアセンブラが提供する可能性。 この分野で蓄積された「文化層」全体を本当に無視するつもりはありません。
LLVM
int a(int m, int n) { if (m == 0) return n + 1; if (n == 0) return a(m - 1, 1); return a(m - 1, a(m, n - 1)); }
LLVM asmを受信しました
; 関数属性:nounwind readnone define i32 @a(i32%m、i32%n)#0 { %1 = icmp eq i32%m、0 br i1%1、label%tailrecurse._crit_edge、label%.lr.ph tailrecurse._crit_edge :; preds =%tailrecurse.backedge、%0 %n.tr.lcssa = phi i32 [%n、%0]、[%n.tr.be、%tailrecurse.backedge] %2 = nsw i32%n.tr.lcssaを追加、1 ret i32%2 .lr.ph :; preds =%0、%tailrecurse.backedge %n.tr2 = phi i32 [%n.tr.be、%tailrecurse.backedge]、[%n、%0] %m.tr1 = phi i32 [%4、%tailrecurse.backedge]、[%m、%0] %3 = icmp eq i32%n.tr2,0 %4 = nsw i32%m.tr1、-1を追加 br i1%3、label%tailrecurse.backedge、label%5 ; <ラベル>:5; preds =%.lr.ph %6 = nsw i32%n.tr2を追加、-1 %7 =末尾呼び出しi32 @a(i32%m.tr1、i32%6) br label%tailrecurse.backedge tailrecurse.backedge :; preds =%5、%.lr.ph %n.tr.be = phi i32 [%7、%5]、[1、%.lr.ph] %8 = icmp eq i32%4、0 br i1%8、label%tailrecurse._crit_edge、label%.lr.ph }
ここでは、制御フローの命令のみが表示され、スタックマシンの特異性が現れる場所はありません(+ -1の計算を除く)。
「バタフライ」FFTについてはどうですか(これはデータフロー領域からの可能性が高いです)?
FFTフラグメント
...
for(n = 1; n <= LogN; n ++)
{
rw = Rcoef [LogN-n];
iw = Icoef [LogN-n];
if(Ft_Flag == FT_INVERSE)iw = -iw;
in = ie >> 1;
ru = 1.0;
iu = 0.0;
for(j = 0; j <in; j ++)
{
for(i = j; i <N; i + = ie)
{
io = i + in;
rtp = Rdat [i] + Rdat [io];
itp = Idat [i] + Idat [io];
rtq = Rdat [i]-Rdat [io];
itq = Idat [i]-Idat [io];
Rdat [io] = rtq * ru-itq * iu;
Idat [io] = itq * ru + rtq * iu;
Rdat [i] = rtp;
Idat [i] = itp;
}
sr = ru;
ru = ru * rw-iu * iw;
iu = iu * rw + sr * iw;
}
すなわち>> = 1;
}
...
for(n = 1; n <= LogN; n ++)
{
rw = Rcoef [LogN-n];
iw = Icoef [LogN-n];
if(Ft_Flag == FT_INVERSE)iw = -iw;
in = ie >> 1;
ru = 1.0;
iu = 0.0;
for(j = 0; j <in; j ++)
{
for(i = j; i <N; i + = ie)
{
io = i + in;
rtp = Rdat [i] + Rdat [io];
itp = Idat [i] + Idat [io];
rtq = Rdat [i]-Rdat [io];
itq = Idat [i]-Idat [io];
Rdat [io] = rtq * ru-itq * iu;
Idat [io] = itq * ru + rtq * iu;
Rdat [i] = rtp;
Idat [i] = itp;
}
sr = ru;
ru = ru * rw-iu * iw;
iu = iu * rw + sr * iw;
}
すなわち>> = 1;
}
...
最もネストされたLLVMアセンブラーループの本体
(clang -c bc -O3 --target = xcore -emit-llvm -S -o b_o3.ll)は次のようになります:
結果のアセンブラーLLVM
.lr.ph21:; preds =%.preheader19、%.lr.ph21
%i.020 = phi i32 [%76、%.lr.ph21]、[%j.025、%.preheader19]
%57 = NSW i32%i.020、%54を追加
%58 = getelementptr inbounds double *%Rdat、i32%i.020
%59 =ダブルロード*%58、4揃え、Tbaa!1
%60 = getelementptr inbounds double *%Rdat、i32%57
%61 =ダブルロード*%60、4揃え、Tbaa!1
%62 = fadd double%59、%61
%63 = getelementptr inbounds double *%Idat、i32%i.020
%64 =ダブルロード*%63、アライン4 、! Tbaa!1
%65 = getelementptr inbounds double *%Idat、i32%57
%66 =ダブルロード*%65、アライン4 、! Tbaa!1
%67 = fadd double%64、%66
%68 = fsub double%59、%61
%69 = fsub double%64、%66
%70 = fmul double%ru.023、%68
%71 = fmul double%iu.024、%69
%72 = fsub double%70、%71
double%72、double *%60を保存、4を揃える!tbaa!1
%73 = fmul double%ru.023、%69
%74 = fmul double%iu.024、%68
%75 = fadd double%74、%73
double%75、double *%65、4を揃える!tbaa!1
倍の62%、倍の*%58、4を揃える!tbaa!1
double%67、double *%63、4を揃える!tbaa!1
%76 = nsw i32%i.020、%ie.028を追加
%77 = icmp slt i32%76、%N
br i1%77、label%.lr.ph21、label%._ crit_edge22
...
%i.020 = phi i32 [%76、%.lr.ph21]、[%j.025、%.preheader19]
%57 = NSW i32%i.020、%54を追加
%58 = getelementptr inbounds double *%Rdat、i32%i.020
%59 =ダブルロード*%58、4揃え、Tbaa!1
%60 = getelementptr inbounds double *%Rdat、i32%57
%61 =ダブルロード*%60、4揃え、Tbaa!1
%62 = fadd double%59、%61
%63 = getelementptr inbounds double *%Idat、i32%i.020
%64 =ダブルロード*%63、アライン4 、! Tbaa!1
%65 = getelementptr inbounds double *%Idat、i32%57
%66 =ダブルロード*%65、アライン4 、! Tbaa!1
%67 = fadd double%64、%66
%68 = fsub double%59、%61
%69 = fsub double%64、%66
%70 = fmul double%ru.023、%68
%71 = fmul double%iu.024、%69
%72 = fsub double%70、%71
double%72、double *%60を保存、4を揃える!tbaa!1
%73 = fmul double%ru.023、%69
%74 = fmul double%iu.024、%68
%75 = fadd double%74、%73
double%75、double *%65、4を揃える!tbaa!1
倍の62%、倍の*%58、4を揃える!tbaa!1
double%67、double *%63、4を揃える!tbaa!1
%76 = nsw i32%i.020、%ie.028を追加
%77 = icmp slt i32%76、%N
br i1%77、label%.lr.ph21、label%._ crit_edge22
...
命令間の依存関係グラフの形式では、次のようになります。

ちなみに、複数のエッジが出てくるツリーの各頂点は、ブックマークのタイトルの候補です。 少なくとも浮動小数点計算に関しては。
いずれにせよ、LLVMで説明されているアーキテクチャの実装は、絶望的なイベントのようには見えません。
ドットファイル、突然便利になります。
fft.dot
digraph graphname {
L000 [ラベル= "%54"];
L001 [ラベル= "%Rdat"];
L002 [label = "%Idat"];
L003 [label = "%ru.023"];
L004 [ラベル= "%iu.024"];
L005 [ラベル= "%i.020"];
L02 [label = "%57 = add nsw i32%i.020、%54"];
L03 [label = "%58 = getelementptr double *%Rdat、i32%i.020"];
L04 [label = "%59 = load double *%58"];
L05 [label = "%60 = getelementptr double *%Rdat、i32%57"];
L06 [label = "%61 = load double *%60"];
L07 [label = "%62 = fadd double%59、%61"];
L08 [label = "%63 = getelementptr double *%Idat、i32%i.020"];
L09 [label = "%64 = load double *%63"];
L10 [label = "%65 = getelementptr double *%Idat、i32%57"];
L11 [label = "%66 = load double *%65"];
L12 [label = "%67 = fadd double%64、%66"];
L13 [label = "%68 = fsub double%59、%61"];
L14 [label = "%69 = fsub double%64、%66"];
L15 [label = "%70 = fmul double%ru.023、%68"];
L16 [label = "%71 = fmul double%iu.024、%69"];
L17 [label = "%72 = fsub double%70、%71"];
L18 [label = "store double%72、double *%60"];
L19 [label = "%73 = fmul double%ru.023、%69"];
L20 [label = "%74 = fmul double%iu.024、%68"];
L21 [label = "%75 = fadd double%74、%73"];
L22 [label = "store double%75、double *%65"];
L23 [label = "store double%62、double *%58"];
L24 [label = "store double%67、double *%63"];
L005-> L02; L000-> L02; L005-> L03; L001-> L03;
L03-> L04; L001-> L05; L02-> L05; L05-> L06; L04-> L07;
L06-> L07; L002-> L08; L005-> L08; L08-> L09; L002-> L10;
L02-> L10; L10-> L11; L09-> L12; L11-> L12; L04-> L13;
L06-> L13; L09-> L14; L11-> L14; L003-> L15; L13-> L15;
L004-> L16; L14-> L16; L15-> L17; L16-> L17; L17-> L18;
L003-> L19; L14-> L19; L004-> L20; L13-> L20; L19-> L21;
L20-> L21; L10-> L22; L21-> L22; L07-> L23; L03-> L23;
L08-> L24; L12-> L24; L05-> L18;
}
L000 [ラベル= "%54"];
L001 [ラベル= "%Rdat"];
L002 [label = "%Idat"];
L003 [label = "%ru.023"];
L004 [ラベル= "%iu.024"];
L005 [ラベル= "%i.020"];
L02 [label = "%57 = add nsw i32%i.020、%54"];
L03 [label = "%58 = getelementptr double *%Rdat、i32%i.020"];
L04 [label = "%59 = load double *%58"];
L05 [label = "%60 = getelementptr double *%Rdat、i32%57"];
L06 [label = "%61 = load double *%60"];
L07 [label = "%62 = fadd double%59、%61"];
L08 [label = "%63 = getelementptr double *%Idat、i32%i.020"];
L09 [label = "%64 = load double *%63"];
L10 [label = "%65 = getelementptr double *%Idat、i32%57"];
L11 [label = "%66 = load double *%65"];
L12 [label = "%67 = fadd double%64、%66"];
L13 [label = "%68 = fsub double%59、%61"];
L14 [label = "%69 = fsub double%64、%66"];
L15 [label = "%70 = fmul double%ru.023、%68"];
L16 [label = "%71 = fmul double%iu.024、%69"];
L17 [label = "%72 = fsub double%70、%71"];
L18 [label = "store double%72、double *%60"];
L19 [label = "%73 = fmul double%ru.023、%69"];
L20 [label = "%74 = fmul double%iu.024、%68"];
L21 [label = "%75 = fadd double%74、%73"];
L22 [label = "store double%75、double *%65"];
L23 [label = "store double%62、double *%58"];
L24 [label = "store double%67、double *%63"];
L005-> L02; L000-> L02; L005-> L03; L001-> L03;
L03-> L04; L001-> L05; L02-> L05; L05-> L06; L04-> L07;
L06-> L07; L002-> L08; L005-> L08; L08-> L09; L002-> L10;
L02-> L10; L10-> L11; L09-> L12; L11-> L12; L04-> L13;
L06-> L13; L09-> L14; L11-> L14; L003-> L15; L13-> L15;
L004-> L16; L14-> L16; L15-> L17; L16-> L17; L17-> L18;
L003-> L19; L14-> L19; L004-> L20; L13-> L20; L19-> L21;
L20-> L21; L10-> L22; L21-> L22; L07-> L23; L03-> L23;
L08-> L24; L12-> L24; L05-> L18;
}
エピローグ
だから私たちは予備的な仕上げに来ました。
新しいアーキテクチャが必要な理由を見つけ、解決策を提案しました。
最初は、このアーキテクチャが設定要件を満たしているかどうかが問題でした。
そして今、私たちは答えることができます、少なくともその小さな部分Cで、私たちはそれを検証することができました。
- 予想されるハードウェアの簡素化
- レジスタ数の外部から見えないスケーラビリティ
- 機能デバイスの数と同様に
- コンパイラの簡素化の可能性
一見したところ(素人)、ハードウェアでのそのようなアーキテクチャの実装を妨げる基本的な問題は見えません。
私たちは次のようなことを意図的に考慮しませんでした。
- 浮動小数点計算、別のスタックが必要か、...
- コンテキストを切り替えるときにプロセッサの状態を保存する
- 中断
- ...
これらの質問はすべて重要ですが、基本的ではありません。
そして現時点では、著者は自分のタスクが完了したと考えています。