読者です 読者をやめる 読者になる 読者になる

FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

リネームレジスタを模倣する機能をISSに追加する

http://www-personal.umich.edu/~rovinski/images/die_shot.jpg

前回の記事で、アウトオブオーダの考え方、リネームレジスタの考え方についてまとめた。

msyksphinz.hatenablog.com

CPUを実装するにあたり、リネームレジスタが正しく実装できているかどうかを確認したい。 リネームレジスタが正しく動作しているかは、

  • 新しい命令のIDが正しく割り当てられているか
  • レジスタ書き込みを起こすならば、その命令のリネームIDが正しく割り当てられているか
  • フリーリストのポインタが正しく動作しているか

これらを確認するためには、やはりISSでリネームレジスタを模倣し、動作一致検証するのがよさそうだ。 まずは、リネームマップをISSで模倣することを考えよう。

ISSでは投機実行の概念は存在しない

リネームレジスタISSで模倣するにあたり、非常に有利な点が存在する。それは、ISSにおいて投機実行の概念は存在しない。 もちろん、ISSは命令の実行はすべて確定的であり、分岐予測ミスは(そこまで模倣しない限り)発生しない。ハードウェアの場合は投機的な実行が絡むので、もし例外や分岐予測ミスが発生すると、オンザフライな命令のIDはすべてフリーリストに戻して、確定しているポイントからやり直さなければならない。 一方で、IDの割り当ては常に確定的で、ハードウェアのような複雑性は存在しないため、ISSでの再現が非常に楽なのだ。

命令のIDだって、例外が起きた時点で投機的なIDをもとに戻す必要はない。そういう意味では、

何番目に実行される命令か%最大リネーム番号=リネームID

なのでこれも非常に楽だ。

ISSでのリネームマップの実装

github.com

とりあえず、以下のメンバ変数を定義した。

  std::unique_ptr<uint32_t []> m_future_map;
  std::unique_ptr<uint32_t []> m_freelist;
  uint32_t m_freelist_head, m_freelist_tail;

m_future_mapと言いつつ、アーキテクチャレジスタと物理レジスタの対応を取るためのテーブル。 m_freelistはレジスタ書き込み命令の場合に割り当てるリネームIDを格納しているリスト。 m_freelist_head, m_freelist_tailはフリーリストの先頭と最後尾を格納しているポインタだ。

レジスタ書き込み命令を実行した場合のモデリング

命令トレース内にレジスタ書き込みが存在した場合、以下のような動作が発生する。

        for (trace_count = 0; trace_count < GetTrace()->GetMax (); trace_count ++) {
          if (GetTrace()->GetTraceType(trace_count) == TraceInfo::trace_regwrite) {
            trace_addr = GetTrace()->GetTraceAddr  (trace_count);
            break;
          }
        }
        if (trace_count != GetTrace()->GetMax ()) {
          uint32_t old_map = m_future_map[trace_addr];
          m_future_map[trace_addr] = m_freelist[m_freelist_head];
          m_freelist[m_freelist_tail] = old_map;
          m_freelist_head = (m_freelist_head + 1) % 64;
          m_freelist_tail = (m_freelist_tail + 1) % 64;
          DebugPrint ("(%02d,%02d)", m_future_map[trace_addr], old_map);
          DebugPrint (":(%02d,%02d) ", m_freelist_head, m_freelist_tail);
        }

trace_addrはアーキテクチャレジスタのインデックスのこと。書き込みレジスタアドレスに対して、m_freelistの先頭から新しいIDを取り出す。 さらに、フリーリストの最後尾に、もともとfuture_mapに入っていた元のIDを格納する。つまり、あるアーキテクチャレジスタの値を参照するのに、古いIDをフリーリストに戻して、この命令以降は新しいIDを参照することになる。

リネームマップの初期化

では、リネームマップはリセット状態でどのような値を保持しているべきなのか?

まず、最初の命令が参照するオペランドは、何がしかのIDが割り当てられている必要がある。これらは、リセット時にfuture_mapに格納しておく。新しい命令に0から順番にIDを割り当てていきたいので、最初に割り当てておくのは余っているID、ここでは32から63をアーキテクチャレジスタに割り当てておく。 フリーリストの先頭は0番目のインデックス、順番に0から32までの新たに割り当てられるIDが格納されており、最後尾は32番目を指している。

  // Rename Buffer File and FreeList
  m_future_map = std::unique_ptr<uint32_t[]>(new uint32_t[32]);
  m_freelist = std::unique_ptr<uint32_t[]>(new uint32_t[64]);
  for (int i = 0; i < 32; i++) {
    m_future_map[i] = i + 32;
  }
  for (int i = 0; i < 64; i++) {
    m_freelist[i] = i;
  }
  m_freelist_head = 0;
  m_freelist_tail = 32;

実行結果

Google Flagsで新たなオプションを定義して、そのオプションを指定したらリネームマップをシミュレーションするようにした。

         0:M:MBar:[00000200][P00000200] 00000093 : (00,33):(01,33) addi       r01,r00,0x000        r00=>0000000000000000 r01<=0000000000000000
         1:M:MBar:[00000204][P00000204] 00000113 : (01,34):(02,34) addi       r02,r00,0x000        r00=>0000000000000000 r02<=0000000000000000
         2:M:MBar:[00000208][P00000208] 00000193 : (02,35):(03,35) addi       r03,r00,0x000        r00=>0000000000000000 r03<=0000000000000000
         3:M:MBar:[0000020c][P0000020c] 00000213 : (03,36):(04,36) addi       r04,r00,0x000        r00=>0000000000000000 r04<=0000000000000000
         4:M:MBar:[00000210][P00000210] 00000293 : (04,37):(05,37) addi       r05,r00,0x000        r00=>0000000000000000 r05<=0000000000000000
         5:M:MBar:[00000214][P00000214] 00000313 : (05,38):(06,38) addi       r06,r00,0x000        r00=>0000000000000000 r06<=0000000000000000
         6:M:MBar:[00000218][P00000218] 00000393 : (06,39):(07,39) addi       r07,r00,0x000        r00=>0000000000000000 r07<=0000000000000000
         7:M:MBar:[0000021c][P0000021c] 00000413 : (07,40):(08,40) addi       r08,r00,0x000        r00=>0000000000000000 r08<=0000000000000000
...
        29:M:MBar:[00000274][P00000274] 00000f13 : (29,62):(30,62) addi       r30,r00,0x000        r00=>0000000000000000 r30<=0000000000000000
        30:M:MBar:[00000278][P00000278] 00000f93 : (30,63):(31,63) addi       r31,r00,0x000        r00=>0000000000000000 r31<=0000000000000000
        31:M:MBar:[0000027c][P0000027c] 03000293 : (31,04):(32,00) addi       r05,r00,0x030        r00=>0000000000000000 r05<=0000000000000030
        32:M:MBar:[00000280][P00000280] 3002b073 :                 csrrc      r00,0x300,r05        r05=>0000000000000030 mstatus=>0000000000000000 mstatus<=0000000000000000
        33:M:MBar:[00000284][P00000284] 00800293 : (33,31):(33,01) addi       r05,r00,0x008        r00=>0000000000000000 r05<=0000000000000008
        34:M:MBar:[00000288][P00000288] 3002a073 :                 csrrs      r00,0x300,r05        r05=>0000000000000008 mstatus=>0000000000000000 mstatus<=0000000000000008
        35:M:MBar:[0000028c][P0000028c] 000032b7 : (34,33):(34,02) lui        r05,0x00003          r05<=0000000000003000
        36:M:MBar:[00000290][P00000290] 3002a073 :                 csrrs      r00,0x300,r05        r05=>0000000000003000 mstatus=>0000000000000008 mstatus<=0000000000003008
        37:M:MBar:[00000294][P00000294] 0000c2b7 : (35,34):(35,03) lui        r05,0x0000c          r05<=000000000000c000
        38:M:MBar:[00000298][P00000298] 3002a073 :                 csrrs      r00,0x300,r05        r05=>000000000000c000 mstatus=>0000000000003008 mstatus<=000000000000f008
        39:M:MBar:[0000029c][P0000029c] f00022f3 : (36,35):(36,04) csrrs      r05,0xf00,r00        r00=>0000000000000000 mcpuid=>0000000080000000 r05<=0000000080000000
        40:M:MBar:[000002a0][P000002a0] 0002c663 : (37,00):(37,05) blt        r05,r00,0x00         r05=>ffffffff80000000 r00=>0000000000000000 pc<=00000000000002ac

各行において、

         0:M:MBar:[00000200][P00000200] 00000093 : (00,33):(01,33) addi       r01,r00,0x000        r00=>0000000000000000 r01<=0000000000000000
                                                    ~~ <------------ 新たに割り当てられたリネームID
                                                       ~~ <--------- 古い(フリーリストに戻される)リネームID
                                                            ~~ <---- フリーリストの先頭
                                                               ~~ <- フリーリストの最後尾

となる。まず先頭の命令では、新たなリネームIDとして0番が取り出され、その代わり初期値として入っていたR1のリネームID=33が書き戻された。 このためフリーリストが更新され、先頭インデックスが1、最後尾が33となっている。

最初の状態は以下のようになる。

f:id:msyksphinz:20160428020330p:plain

1命令実行すると、リネームマップが更新されて、以下のようになったということだ。

f:id:msyksphinz:20160428020953p:plain