Clever Geek Handbook

スーパースカラースタックプロセッサ：最適化



スーパースカラプロセッサのアイデアを探求する一連の記事の続き

OoOおよびフロントエンドスタックマシン。 この記事のトピックは、メモリアクセスの最適化です。



前の記事：

1-直線作品の説明

2-関数呼び出し、レジスターの保存

3-関数呼び出し、内部ルック





これまでのところ、スタックされたすべてのマシンの弱点、つまり過剰なメモリアクセスに注意を払っていません。



実際、スタックマシンの単純なコードジェネレーターが変数「a」の値を取得する場合、「push a」という命令を書き込みます。 スタックプロセッサは、既に計算された式を参照する機会を提供しません。



レジスタプロセッサの場合、コンパイラは一時変数をレジスタに配置できるようにすることでこの問題を解決します。 外側に登録されていないアーキテクチャに対して同様のメカニズムを考え出すことは価値があります。



ただし、「すべてがすでに私たちの前で盗まれている」という何かを発明する必要はほとんどありません（C）。



その結果、コンパイラには最適化のための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;

}

...



最もネストされた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

...



命令間の依存関係グラフの形式では、次のようになります。



ちなみに、複数のエッジが出てくるツリーの各頂点は、ブックマークのタイトルの候補です。 少なくとも浮動小数点計算に関しては。



いずれにせよ、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;

}





エピローグ



だから私たちは予備的な仕上げに来ました。

新しいアーキテクチャが必要な理由を見つけ、解決策を提案しました。

最初は、このアーキテクチャが設定要件を満たしているかどうかが問題でした。

そして今、私たちは答えることができます、少なくともその小さな部分Cで、私たちはそれを検証することができました。



一見したところ（素人）、ハードウェアでのそのようなアーキテクチャの実装を妨げる基本的な問題は見えません。



私たちは次のようなことを意図的に考慮しませんでした。



これらの質問はすべて重要ですが、基本的ではありません。

そして現時点では、著者は自分のタスクが完了したと考えています。


More articles:


All Articles