FPGA開発日記

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

Chiselでfor文を用いた同一モジュールの複数インスタンス化の方法

Verilogでは、同一モジュールを複数インスタンスするときは以下のようにgenerate forが使える。

for (genvar i=1; i<=10; i=i+1) begin 
  subblock u_subblock(
        .clk(clk),
        .reset_n(reset_n),
        .a(a[i]),
        .b(b[i]),
        .out(out[i])
    );
end

これと同様に、Chiselでもfor文を用いた同一モジュールの複数インスタンス化が行える。書き方は単純だ。

class multi_module (width: Int) extends Module()
{
  val io = IO(new Bundle {
    val in0  = Input(Vec(width, UInt(32.W)))
    val in1  = Input(Vec(width, UInt(32.W)))
    val out = Output(Vec(width, UInt(32.W)))
  })

  val sub_modules = for (w <- 0 until width) yield {
    val d = Module (new sub_module)
    d
  }

  sub_modules.zipWithIndex.map { case (sub, i) =>
    sub.io.in0 := io.in0(i)
    sub.io.in1 := io.in0(i)
    io.out(i) := sub.io.out
  }
}

大きく分けて2種類の手法を示した。一つはfor文を用いてモジュールそのものをインスタンス化する。ここでは、multi_moduleモジュールの中でsub_moduleを複数回インスタンスしている。 インスタンスする個数はパラメータwidthに依存している。 このとき、sub_modulesがその複数のモジュールを配列の形式として格納している。

サブモジュールを操作するにあたり、同様にfor文で回しても良いのだが、それ以外にmapを使った方法が取れる。 sub_modules.zipWithIndex.mapでは、sub_modulesに格納されている複数のモジュールを、zipWithIndexで0から番号のついたペアに変換し、それぞれに対してmapを行う。

  • sub_modules : {sub_modules(0), sub_modules(1), sub_modules(2), sub_modules(3), ...}
  • sub_modules.zipWithIndex : {{sub_modules(0), 0}, {sub_modules(1), 1}, {sub_modules(2), 2}, {sub_modules(3), 3}, ...}

それぞれに対して、入出力ポートを接続する記述をしている。 これで、生成されるVerilogは以下のようになった。

  wire [31:0] sub_modules_4_io_in1; // @[multi_module.scala 15:20:@65.4]
  wire [31:0] sub_modules_4_io_out; // @[multi_module.scala 15:20:@65.4]
  sub_module sub_modules_0 ( // @[multi_module.scala 15:20:@53.4]
    .io_in0(sub_modules_0_io_in0),
    .io_in1(sub_modules_0_io_in1),
    .io_out(sub_modules_0_io_out)
  );
  sub_module sub_modules_1 ( // @[multi_module.scala 15:20:@56.4]
    .io_in0(sub_modules_1_io_in0),
    .io_in1(sub_modules_1_io_in1),
    .io_out(sub_modules_1_io_out)
  );
  sub_module sub_modules_2 ( // @[multi_module.scala 15:20:@59.4]
    .io_in0(sub_modules_2_io_in0),
    .io_in1(sub_modules_2_io_in1),
    .io_out(sub_modules_2_io_out)
  );
...
  assign io_out_0 = sub_modules_0_io_out; // @[multi_module.scala 22:15:@70.4]
...
  assign io_out_4 = sub_modules_4_io_out; // @[multi_module.scala 22:15:@82.4]
  assign sub_modules_0_io_in0 = io_in0_0; // @[multi_module.scala 20:16:@68.4]
...
  assign sub_modules_2_io_in0 = io_in0_2; // @[multi_module.scala 20:16:@74.4]
  assign sub_modules_2_io_in1 = io_in0_2; // @[multi_module.scala 21:16:@75.4]
  assign sub_modules_3_io_in0 = io_in0_3; // @[multi_module.scala 20:16:@77.4]
...
  assign sub_modules_4_io_in1 = io_in0_4; // @[multi_module.scala 21:16:@81.4]
f:id:msyksphinz:20190719002040p:plain
モジュールのインスタンスイメージ

LLVMのバックエンドを作るための第一歩 (40. objdumpのサポート)

f:id:msyksphinz:20190425001356p:plain

現状、llvm-objdumpを実行すると以下のようになってしまう。これをサポートする。

% ./bin/llvm-objdump -d results/if_ctrl-O0_-march=mips_-relocation-model=static/if_ctrl.bc
./bin/llvm-objdump: error: 'results/if_ctrl-O0_-march=mips_-relocation-model=static/if_ctrl.bc': The file was not recognized as a valid object file
  • lib/Target/MYRISCVX/CMakeLists.txt
lib/Target/MYRISCVX/CMakeLists.txt
  • llvm-myriscvx/lib/Target/MYRISCVX/Disassembler/MYRISCVXDisassembler.cpp
/// MYRISCVXDisassembler - a disasembler class for MYRISCVX32.
class MYRISCVXDisassembler : public MYRISCVXDisassemblerBase {
 public:
  /// Constructor     - Initializes the disassembler.
  ///
  MYRISCVXDisassembler(const MCSubtargetInfo &STI, MCContext &Ctx, bool bigEndian)
      : MYRISCVXDisassemblerBase(STI, Ctx, bigEndian) {
  }

  /// getInstruction - See MCDisassembler.
  DecodeStatus getInstruction(MCInst &Instr, uint64_t &Size,
                              ArrayRef<uint8_t> Bytes, uint64_t Address,
                              raw_ostream &VStream,
                              raw_ostream &CStream) const override;
};

} // end anonymous namespace
/// Read four bytes from the ArrayRef and return 32 bit word sorted
/// according to the given endianess
static DecodeStatus readInstruction32(ArrayRef<uint8_t> Bytes, uint64_t Address,
                                      uint64_t &Size, uint32_t &Insn,
                                      bool IsBigEndian) {
  // We want to read exactly 4 Bytes of data.
  if (Bytes.size() < 4) {
    Size = 0;
    return MCDisassembler::Fail;
  }

  if (IsBigEndian) {
    // Encoded as a big-endian 32-bit word in the stream.
    Insn = (Bytes[3] <<  0) |
        (Bytes[2] <<  8) |
        (Bytes[1] << 16) |
        (Bytes[0] << 24);
  }
  else {
    // Encoded as a small-endian 32-bit word in the stream.
    Insn = (Bytes[0] <<  0) |
        (Bytes[1] <<  8) |
        (Bytes[2] << 16) |
        (Bytes[3] << 24);
  }

  return MCDisassembler::Success;
}

DecodeStatus
MYRISCVXDisassembler::getInstruction(MCInst &Instr, uint64_t &Size,
                                     ArrayRef<uint8_t> Bytes,
                                     uint64_t Address,
                                     raw_ostream &VStream,
                                     raw_ostream &CStream) const {
  uint32_t Insn;

  DecodeStatus Result;

  Result = readInstruction32(Bytes, Address, Size, Insn, IsBigEndian);

  if (Result == MCDisassembler::Fail)
    return MCDisassembler::Fail;

  // Calling the auto-generated decoder function.
  Result = decodeInstruction(DecoderTableMYRISCVX32, Instr, Insn, Address,
                             this, STI);
  if (Result != MCDisassembler::Fail) {
    Size = 4;
    return Result;
  }

  return MCDisassembler::Fail;
}
static DecodeStatus DecodeBranch12Target(MCInst &Inst,
                                         unsigned Insn,
                                         uint64_t Address,
                                         const void *Decoder) {
  int BranchOffset = SignExtend32<12>((fieldFromInstruction(Insn, 31, 1) << 12) |
                                      (fieldFromInstruction(Insn, 25, 6) <<  5) |
                                      (fieldFromInstruction(Insn,  8, 4) <<  1) |
                                      (fieldFromInstruction(Insn,  7, 1) << 11));
  Inst.addOperand(MCOperand::createImm(BranchOffset));
  return MCDisassembler::Success;
}

アセンブルを追加して、以下のようになった。

Disassembly of section .text:
0000000000000000 _Z11test_ifctrlv:
       0:       13 01 81 ff     addi    x11, x11, -8
       4:       13 05 00 00     addi    x6, zero, 0
       8:       23 22 a1 00     sw      x6, 4(x11)
       c:       03 25 41 00     lw      x6, 4(x11)
      10:       63 10 05 00     bne     x6, zero, 0
      14:       03 25 41 00     lw      x6, 4(x11)
      18:       13 05 15 00     addi    x6, x6, 1
      1c:       23 22 a1 00     sw      x6, 4(x11)

0000000000000020 $BB0_2:
      20:       03 25 41 00     lw      x6, 4(x11)
      24:       13 01 81 00     addi    x11, x11, 8
      28:       67 80 10 00     ret     x10

「ハロー "Hello, World"」を読み始めた

だいぶスタートダッシュが遅れたが、「ハロー"Hello, World"」を読み始めた。 最初からかなりしっかり説明があるが、いきなりprintf()の中に飛び込んだので若干の低レイヤの知識があった方が読みやすいように思う。

幸いなことに、「30日でできるOS自作入門」を読んでいたので、x86の割り込みの仕組みなどの前提知識があった。 前提知識がある分、ソフトウェア割込みの章などは読みやすい。 そうでないといきなり大量の逆アセンブルやコードなどが出てきて読み進めるのが大変である。もう少し図を入れてくれると良かったな。

30日でできる! OS自作入門

30日でできる! OS自作入門

とりあえず、4章くらいまでは読み進めた。 時間を見つけて、さらに読んでいくつもり。

最初の方はGDBを使ってHello Worldのコードを読み解いていくが、これがなかなか楽しい。 gdbserverってこうやって使うのか、など勉強になった。

RISC-Vのベクトル拡張命令RVVの環境を試す (1. gccのビルドとシミュレータのビルド)

f:id:msyksphinz:20190505224354p:plain

RISC-Vのベクトル拡張命令であるRISC-V Vector Extensionは仕様の策定されており、徐々に実装が進んでいる。

  • riscv-toolsのSpike命令セットシミュレータ
  • riscv-gnu-toolchainの対応

現在の実装の状況を見てみることにした。

riscv-toolsのインストール

riscv-toolsには、RVV(RISC-V Vector Extension)をサポートするためのブランチが切ってある。

git clone https://github.com/riscv/riscv-tools.git

新たにRVVのツールセットをインストールするディレクトリを決めて、インストールする。

  • riscv-isa-sim (Spike)
export RISCV=${HOME}/riscv_rvv
cd riscv-isa-sim
git checkout b1bde2b
./configure --prefix=${HOME}/riscv_rvv
make -j4
make install

バージョンの確認。

Spike RISC-V ISA Simulator 1.0.1-dev

usage: spike [host options] <target program> [target options]
Host Options:
  -p<n>                 Simulate <n> processors [default 1]
  -m<n>                 Provide <n> MiB of target memory [default 2048]
  -m<a:m,b:n,...>       Provide memory regions of size m and n bytes
                          at base addresses a and b (with 4 KiB alignment)
  -d                    Interactive debug mode
  -g                    Track histogram of PCs
  -l                    Generate a log of execution
  -h, --help            Print this help message
  -H                    Start halted, allowing a debugger to connect
  --isa=<name>          RISC-V ISA string [default RV64IMAFDC]
  --varch=<name>        RISC-V Vector uArch string [default v128:e32:s128]
  --pc=<address>        Override ELF entry point
  --hartids=<a,b,...>   Explicitly specify hartids, default is 0,1,...
  --ic=<S>:<W>:<B>      Instantiate a cache model with S sets,
  --dc=<S>:<W>:<B>        W ways, and B-byte blocks (with S and
  --l2=<S>:<W>:<B>        B both powers of 2).
...
git clone https://github.com/riscv/riscv-gnu-toolchain.git
cd riscv-gnu-toolchain
git checkout rvv-0.7.x
mkdir build
cd build
../configure --prefix=${RISCV}
make -j4

バージョン確認

$ riscv64-unknown-elf-gcc --version
riscv64-unknown-elf-gcc (GCC) 8.3.0
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

簡単なプログラムをコンパイルしてみる。

まだauto-vectorizationは効かないようなので、サンプルでテスト用についているプログラムをコンパイルしてみる。

riscv64-unknown-elf-gcc -O3 -march=rv64gcv /home/msyksphinz/work/riscv/riscv-tools/riscv-gnu-toolchain/riscv-binutils/gas/testsuite/gas/riscv/vector-insns.s -c
riscv64-unknown-elf-objdump -d vector-insns.o | less
...
vector-insns.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <.text>:
       0:       80c5f557                vsetvl  a0,a1,a2
       4:       0005f557                vsetvli a0,a1,e8,m1,d1
       8:       7ff5f557                vsetvli a0,a1,2047
       c:       0455f557                vsetvli a0,a1,e16,m2,d4
      10:       12050207                vlb.v   v4,(a0)
      14:       12050207                vlb.v   v4,(a0)
      18:       10050207                vlb.v   v4,(a0),v0.t
      1c:       12055207                vlh.v   v4,(a0)
      20:       12055207                vlh.v   v4,(a0)

とりあえず、Vector命令をコンパイルできるツールセットを構築した。

高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (7. RISC-VのアウトオブオーダコアBOOMのGshare実装を見てみる)

プロセッサアーキテクチャについて再度復習その7。分岐予測の基本について学んだので、実際の実装を見てみたいと思う。

RISC-VのアウトオブオーダBOOMの実装を眺めてみることにした。こちらはChiselをベースにしているので読み解くのは少し厄介だが、できない事は無い。

github.com

今回見てみる実装はGshareである。これはriscv-boom/src/main/scala/bpu/bpd/gshare/gshare.scalaに格納されている。

github.com


gshare分岐予測器

ベースとなるクラス。br-predictor.scalaが基底クラスとなっている。GShareBrPredictorBoomBrPredictorから派生している。

  • boom/src/main/scala/bpu/bpd/br-predictor.scala
abstract class BoomBrPredictor(
   val historyLength: Int)(implicit p: Parameters) extends BoomModule
{
...
  • boom/src/main/scala/bpu/bpd/tage/gshare.scala
class GShareBrPredictor(
   historyLength: Int = 12
   )(implicit p: Parameters)
   extends BoomBrPredictor(historyLength)
   with HasGShareParameters
{

GShareのパラメータ

GShareを構成するにあたり、必要なのは以下のパラメータだ。

  • historyLength : Global History Registerのサイズ。デフォルトでは12ビット。
  • numSets : GShareのPattern History Tableのサイズ。デフォルトでは4096エントリ。

GShareのRAMはTAGEと異なり1つだけである。分岐予測に対してインデックスの計算方法が異なる。

  • boom-template/boom/src/main/scala/bpu/bpd/gshare/gshare.scala
  //------------------------------------------------------------
  // Predictor state.

  val counter_table = SyncReadMem(nSets, UInt(rowSz.W))

RAMの横幅はfetchWidthの2倍である。

/**
 * Trait to inherit parameters from the configuration
 */
trait HasGShareParameters extends HasBoomCoreParameters
{
  val gsParams = boomParams.gshare.get
  // prevent us from building something too big (and taking millions of cycles to initialize!)
  val nSets = gsParams.numSets

  val idxSz = log2Ceil(nSets)
  val rowSz = fetchWidth*2
}

予測前の初期化。ステートマシンによりテーブルの初期化を行う。

  val s_reset :: s_wait :: s_clear :: s_idle :: Nil = Enum(4)
  val fsm_state = RegInit(s_reset)
  val nResetLagCycles = 64
  val nBanks = 1
  val (lag_counter, lag_done) = Counter(fsm_state === s_wait, nResetLagCycles)
  val (clear_row_addr, clear_done) = Counter(fsm_state === s_clear, numEntries/nBanks)

  switch (fsm_state) {
    is (s_reset) { fsm_state := s_wait }
    is (s_wait)  { when (lag_done) { fsm_state := s_clear } }
    is (s_clear) { when (clear_done) { fsm_state := s_idle } }
    is (s_idle)  { when (io.do_reset) { fsm_state := s_clear } }
  }

リセット後にステートマシンがs_waitに代わり、64サイクル待つ(リセットの非同期対応?)。次にs_clearステートに移り、テーブルのエントリを1つずつ初期化する。すべてが完了すると、s_idle状態に遷移し、定常状態に移る。

予測の手順

分岐予測のリクエストに対して、現在のフェッチしたPCとグローバルヒストリレジスタの値をハッシュし、RAMアクセスのインデックスを決める。

  private def Hash (addr: UInt, hist: UInt) = {
    // fold history if too big for our table
    val folded_history = Fold (hist, idxSz, historyLength)
    ((addr >> (log2Ceil(fetchWidth*coreInstBytes).U)) ^ folded_history)(idxSz-1,0)
  }
...
  val s1_ridx = Hash(this.r_f1_fetchpc, this.r_f1_history)

リクエストが来ると、まずはRAMをReadして予測値を引っ張ってくる。これには1サイクルが消費される。

  // return data to superclass (via f2_resp bundle).
  val s2_out = counter_table.read(s1_ridx, this.f1_valid)

これをElasticRegという2エントリのQueueのようなものに挿入し、この値をそのまま返して予測値とする。

予測のアップデート

予測のアップデートは、TAGEと同様にコミット時に行う。コミット時の予測更新信号に応じて、カウンタをアップデートする。もとのカウンタの値はパイプラインの外に出て行って戻ってきたものをそのまま使用し、これにアップデートの論理をかけてRAMに再度格納する。

  val com_info = (io.commit.bits.info).asTypeOf(new GShareResp(fetchWidth, idxSz))
  val com_idx = Hash(io.commit.bits.fetch_pc, io.commit.bits.history)(idxSz-1,0)

  val wen = io.commit.valid || (fsm_state === s_clear)
  when (wen) {
    val new_row = updateEntireCounterRow(
      com_info.rowdata,
      io.commit.bits.mispredict,
      io.commit.bits.miss_cfi_idx,
      io.commit.bits.taken)

    val waddr = Mux(fsm_state === s_clear, clear_row_addr, com_idx)
    val wdata = Mux(fsm_state === s_clear, initRowValue(), new_row)

    counter_table.write(waddr, wdata)
  }
  // Pick out the old counter value from a full row and increment it.
  // Return the new row.
  private def updateCounterInRow(old_row: UInt, cfi_idx: UInt, taken: Bool): UInt = {
    val row = Wire(UInt(rowSz.W))
    val shamt = cfi_idx << 1.U
    val mask = Wire(UInt(rowSz.W))
    mask := ~(0x3.U << shamt)
    val old_cntr = (old_row >> shamt) & 0x3.U
    val new_cntr = updateCounter(old_cntr, taken)
    row := (old_row & mask) | (new_cntr << shamt)
    row
  }
f:id:msyksphinz:20190712232022p:plain:w400
Gshare分岐予測器

高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (6. RISC-VのアウトオブオーダコアBOOMのTAGE実装を見てみる)

プロセッサアーキテクチャについて再度復習その6。分岐予測の基本について学んだので、実際の実装を見てみたいと思う。

RISC-VのアウトオブオーダBOOMの実装を眺めてみることにした。こちらはChiselをベースにしているので読み解くのは少し厄介だが、できない事は無い。

github.com


TAGE分岐予測器

ベースとなるクラス。br-predictor.scalaが基底クラスとなっている。TageBrPredictorBoomBrPredictorから派生している。

  • boom/src/main/scala/bpu/bpd/br-predictor.scala
abstract class BoomBrPredictor(
   val historyLength: Int)(implicit p: Parameters) extends BoomModule
{
...
  • boom/src/main/scala/bpu/bpd/tage/tage.scala
class TageBrPredictor(
  numTables: Int,
  tableSizes: Seq[Int],
  historyLengths: Seq[Int],
  tagSizes: Seq[Int],
  cntrSz: Int,
  ubitSz: Int
  )(implicit p: Parameters)
  extends BoomBrPredictor(
    historyLength = historyLengths.max)
...

TAGEのパラメータ

TAGEを構成するにあたり、必要なのは以下のパラメータだ。

  • numTable : TAGEテーブルの数 (=4)
  • tableSize : TAGEテーブルのエントリ数。すべてのテーブルで1024。
  • historyLength : 分岐履歴レジスタのうち、TAGEのハッシュ生成に使うビット長。
    • 4つのテーブルでそれぞれ、27, 45, 63, 90
  • tagSize : エントリのヒット・ミスを示すためのタグビットのサイズ。
    • 4つのテーブルですべて9ビット
  • cntrSz : 各エントリのカウンタのサイズ (=3)。
  • ubitSz : usefulnessカウンタのサイズ (=1)。

テーブルの構成。TAGEには分岐予測のためのテーブルが必要だ。実際のテーブルのImplementationはTageTableに記載されているが、デフォルトではこのTAGEテーブルがnumTables(=4)だけ実装されている。

  val tables = for (i <- 0 until numTables) yield {
    val table = Module(new TageTable(
      id                 = i,
      numEntries        = tableSizes(i),
...
    // check that the user ordered his TAGE tables properly
    if (i > 0) require(historyLengths(i) > historyLengths(i-1))

    table
  }

TAGETableの構成

TAGETableは以下の入出力ポートを持つ。

  • bp1_req : 予測のリクエスト。インデックスとタグを含む。
  class TageTableReq(val idxSz: Int, val tagSz: Int) extends Bundle
  {
    val index = UInt(idxSz.W)
    val tag = UInt(tagSz.W)
  }
  • bp2_req : 予測のレスポンス。bp1_reqに対して1サイクル遅れる。以下の情報が返される。
  class TageTableResp(val tagSz: Int, val cntrSz: Int, val ubitSz: Int)(implicit p: Parameters) extends BoomBundle
  {
    val tag  = UInt(tagSz.W)                 // 入力TAGの値をそのまま返す。
    val cntr = UInt(cntrSz.W)                // 2-bit counterの値そのもの
    val cidx = UInt(log2Ceil(fetchWidth).W)  // cidx。複数命令Issueの場合は対象命令の位置を返す。
    val ubit = UInt(ubitSz.W)                // usefulnessビット
  
    def predictsTaken = cntr(cntrSz-1)       // 2ビットカウンタのビットのうち、最上位ビットが立っていればTaken。
  }
  • write : TAGEの情報を更新するための信号。予測結果に基づいて情報をアップデートする。
  class TageTableWrite(val idxSz: Int, val tagSz: Int, val cntrSz: Int, val ubitSz: Int)(implicit p: Parameters)
    extends BoomBundle
  {
    val index = UInt(idxSz.W) // アップデート対位法のテーブルインデックス
    val old = new TageTableEntry(tagSz, cntrSz, ubitSz)
  
    // What kind of write are we going to perform?
    val allocate = Bool()     // テーブルのアロケートを行う。
    val update   = Bool()     // テーブルのアップデートを行う。
    val degrade  = Bool()     // テーブルの削除を行う。
    // What was the outcome of the branch?
    val mispredict = Bool()   // 分岐の結果、予測が外れた。
    val taken = Bool()        // 分岐の結果が、Takenであった。
  }

予測前の初期化。ステートマシンによりテーブルの初期化を行う。

  val s_reset :: s_wait :: s_clear :: s_idle :: Nil = Enum(4)
  val fsm_state = RegInit(s_reset)
  val nResetLagCycles = 64
  val nBanks = 1
  val (lag_counter, lag_done) = Counter(fsm_state === s_wait, nResetLagCycles)
  val (clear_row_addr, clear_done) = Counter(fsm_state === s_clear, numEntries/nBanks)

  switch (fsm_state) {
    is (s_reset) { fsm_state := s_wait }
    is (s_wait)  { when (lag_done) { fsm_state := s_clear } }
    is (s_clear) { when (clear_done) { fsm_state := s_idle } }
    is (s_idle)  { when (io.do_reset) { fsm_state := s_clear } }
  }

リセット後にステートマシンがs_waitに代わり、64サイクル待つ(リセットの非同期対応?)。次にs_clearステートに移り、テーブルのエントリを1つずつ初期化する。すべてが完了すると、s_idle状態に遷移し、定常状態に移る。

  //------------------------------------------------------------
  // Update (Commit)

  when (io.write.valid || fsm_state === s_clear)
...
    when (fsm_state === s_clear) {
      widx := clear_row_addr
      wentry.tag := 0.U
      wentry.cntr := 0.U
      wentry.cidx := 0.U
      wentry.ubit := 0.U
...
    ram.write(widx, wentry)

TAGEのテーブルそのものは以下で構成されている。ビットカウンタが3ビットあり、しかも0から始まると言う事は、Strongly Not Takenから始まると言う事だろうか?これでいいの?

class TageTableEntry(val tagSz: Int, val cntrSz: Int, val ubitSz: Int)(implicit p: Parameters) extends BoomBundle
{
  val tag  = UInt(tagSz.W)                 // Tag.
  val cntr = UInt(cntrSz.W)                // Prediction counter.
  val cidx = UInt(log2Ceil(fetchWidth).W)  // Control-flow instruction index.
  val ubit = UInt(ubitSz.W)                // Usefulness counter.
}

実体はどのように作ってもかまわないだろうが、Read/Writeをそれぞれ1ポートずつ持つRAMが生成されている。上記のポートは合計16ビットのデータを保持するので、16ビットのSRAMを接続しなければならないと言う事になる。

  val ram = SyncReadMema(numEntries, new TageTableEntry(tagSz, cntrSz, ubitSz))
  ram.suggestName("TageTableDataArray")
module TageTableDataArray(
  input  [9:0] R0_addr,
  input        R0_en,
  input        R0_clk,
  output [8:0] R0_data_tag,
  output [2:0] R0_data_cntr,
  output [2:0] R0_data_cidx,
  output       R0_data_ubit,
  input  [9:0] W0_addr,
  input        W0_en,
  input        W0_clk,
  input  [8:0] W0_data_tag,
  input  [2:0] W0_data_cntr,
  input  [2:0] W0_data_cidx,
  input        W0_data_ubit
);
...

予測の手順

bp1から入ってきた信号は、まずはすべてのテーブルに対してRead Requestが発行される。

  tables_io.zipWithIndex.map{ case (table, i) =>
    table.InitializeIo

    // perform tag hash
    val n = numTables
    bp1_tags(i) := TagHash(r_f1_fetchpc, bp1_idxs((i+1) % n), bp1_idxs((i+2) % n))

    // Send prediction request. ---
    table.bp1_req.valid := f1_valid
    table.bp1_req.bits.index := bp1_idxs(i)
    table.bp1_req.bits.tag := bp1_tags(i)

    table.do_reset := false.B // TODO
  }

この時のインデックスとタグの作り方だが、

  • テーブルインデックス : フェッチPC、グローバルヒストリ(r_f1_history)を使ってインデックスを生成する。
    tables_io.zipWithIndex.map{ case (table, i) =>
      bp1_idxs(i) := IdxHash(r_f1_fetchpc, r_f1_history, historyLengths(i), log2Ceil(tableSizes(i)))
    }
  • テーブルタグ : フェッチPC、1つ後ろのテーブルインデックス、2つ後ろのテーブルインデックスを使用している。これはなんでだ?
     tables_io.zipWithIndex.map{ case (table, i) =>
  ...
       bp1_tags(i) := TagHash(r_f1_fetchpc, bp1_idxs((i+1) % n), bp1_idxs((i+2) % n))
  ...

各TAGEテーブルでの参照は、RAMに対してReadリクエストを出している。1サイクル後に応答が返ってくる。同時に、タグがヒットするかを確認している。

  • boom/src/main/scala/bpu/bpd/tage/tage-table.scala
  val s2_out = ram.read(s1_idx, s1_valid)
  val s2_tag_hit = s2_out.tag === RegEnable(s1_tag, s1_valid)
  // TAGEテーブルの応答
  io.bp2_resp.valid     := s2_tag_hit && RegNext(fsm_state === s_idle, false.B)
  io.bp2_resp.bits.tag  := s2_out.tag
  io.bp2_resp.bits.cntr := s2_out.cntr
  io.bp2_resp.bits.cidx := s2_out.cidx
  io.bp2_resp.bits.ubit := s2_out.ubit

TAGEテーブルから戻ってきた信号は、ElasticReg(2エントリのキューのようなもの)に格納する。このキューはテーブルの数だけ並んでいる。

  • boom/src/main/scala/bpu/bpd/tage/tage.scala
  // Buffer all of the table responses into a queue.
  // Match the other ElasticRegs in the FrontEnd.
  val q_f3_resps = for (i <- 0 until numTables) yield {
    val q_resp = withReset(reset.toBool || io.fe_clear || io.f4_redirect)
     {Module(new ElasticReg(Valid(new TageTableResp(tagSizes.max, cntrSz, ubitSz))))}

    q_resp.io.enq.valid := io.f2_valid
    q_resp.io.enq.bits := tables_io(i).bp2_resp
    q_resp.io.deq.ready := io.resp.ready

    assert (q_resp.io.enq.ready === !io.f2_stall)
    assert (q_resp.io.deq.valid === q_f3_history.io.deq.valid)

    q_resp
  }

それぞれのTAGEテーブルについて、PCがヒットしたか、Taken/Not Takenの情報を取得する。

  // get predictions.
  val f3_tag_hits    = q_f3_resps.map( q => q.io.deq.valid && q.io.deq.bits.valid )
  val f3_predictions = q_f3_resps.map( q => q.io.deq.bits.bits )

予測テーブルのヒットマトリックスを作成する。ヒットマトリックスというのは、縦軸がTAGEテーブルエントリの番号、横軸が同時にフェッチされた命令ラインのインデックス(4命令同時デコードならば4ビット)となる。これにより、どの命令が度のテーブルでヒットしたかが明らかになる。

  val f3_hits_matrix = for (i <- 0 until numTables) yield {
    // For each table, return a one-hot bit-mask if there's a tag-hit AND cfi-idx hit.
    io.f3_is_br.asUInt & Mux(f3_tag_hits(i), UIntToOH(f3_predictions(i).cidx), 0.U)
  }

この中からヒットした値を探し出すのだが、HistoryLengthの長い方が優先されるので、TAGEテーブルをインデックスとは逆純に追いかけていき、最初にヒットしたのがf3_best_hit(w), f3_best_ids(w)であり、2番目にHistoryLengthが長くてヒットしたものがf3_alt_hit(w), f3_alt_ids(w)として格納される(この第2候補は実際には使用されない。)

この情報を使用して、対象となる命令のTaken/NotTakenを決定する。

    f3_takens(w) :=
      Mux(f3_best_hits(w),
        VecInit(f3_predictions)(f3_best_ids(w)).predictsTaken,
        false.B)

こうして、TAGEにヒットした場合は、実際の命令の位置predicted_cidxを計算したのちに予測結果をResponce信号に接続して応答する。

  val resp_info = Wire(new TageResp(
    fetchWidth = fetchWidth,
    numTables = numTables,
    maxHistoryLength = historyLengths.max,
    maxIndexSz = log2Ceil(tableSizes.max),
    maxTagSz = tagSizes.max,
    cntrSz = cntrSz,
    ubitSz = ubitSz))

  val f3_has_hit = f3_best_hits.reduce(_|_)
  val f3_pred = VecInit(f3_predictions)(f3_best_ids(predicted_cidx))

  assert (!(f3_has_hit && !f3_best_hits(predicted_cidx)), "[tage] was a hit but our cidx is wrong.")

  io.resp.valid       := f3_has_hit || io.f2_bim_resp.valid
  io.resp.bits.takens := Mux(f3_has_hit,
                             GetPredictionOH(f3_pred.cidx, f3_pred.cntr),
                             io.f2_bim_resp.bits.getTakens)

TAGEの更新

TAGEテーブルの更新は、命令のコミット時に行われる。コミットする命令のインデックスを計算し、アップデートを行うためのTAGの計算を行う。

  • boom/src/main/scala/bpu/bpd/tage/tage.scala
  val r_commit = RegNext(io.commit)
  val r_info = (r_commit.bits.info).asTypeOf(new TageResp(
    fetchWidth = fetchWidth,
    numTables = numTables,
    maxHistoryLength = historyLengths.max,
    maxIndexSz = log2Ceil(tableSizes.max),
    maxTagSz = tagSizes.max,
    cntrSz = cntrSz,
    ubitSz = ubitSz
  ))

  val com_indexes = historyLengths zip tableSizes map { case (hlen, tsize)  =>
    val idx = IdxHash(r_commit.bits.fetch_pc, r_commit.bits.history, hlen, log2Ceil(tsize))
    idx
  }

  val com_tags = for (i <- 0 until numTables) yield {
    val n = numTables
    TagHash(r_commit.bits.fetch_pc, com_indexes((i+1) % n), com_indexes((i+2) % n))
  }

最終的に各テーブルに対してWriteEntryを行う。

  for (i <- 0 until numTables) {
    when (table_wens(i)) {
      // construct old entry so we can overwrite parts without having to do a RMW.
      val com_entry = Wire(new TageTableEntry(tagSizes.max, cntrSz, ubitSz))
      com_entry.tag  := Mux(table_allocates(i), com_tags(i), r_info.tags(i))
      com_entry.cntr := r_info.cntrs(i)
      com_entry.cidx := Mux(table_allocates(i), r_commit.bits.miss_cfi_idx,  r_info.cidxs(i))
      com_entry.ubit := r_info.ubits(i)

      tables_io(i).WriteEntry(
        com_indexes(i),
        com_entry,
        table_allocates(i),
        table_updates(i),
        table_degrades(i),
        r_commit.bits.mispredict,
        r_commit.bits.taken)
      // TODO XXX if "update", only write to u-bit (!mispredict=>ubit) if !alt_agrees.
    }
  }
f:id:msyksphinz:20190712231551p:plain
TAGE分岐予測器の構造

LLVMのバックエンドを作るための第一歩 (39. 可変長引数で生成されたアセンブリを見てみる)

f:id:msyksphinz:20190425001356p:plain

前回の続き。サンプルプログラムをコンパイルして、どのようなアセンブリ言語が出力されるのか観察する。

  • vararg.cpp
#include <stdarg.h>

int sum_i(int amount, ...)
{
  int i = 0;
  int val = 0;
  int sum = 0;
    
  va_list vl;
  va_start(vl, amount);
  for (i = 0; i < amount; i++)
  {
    val = va_arg(vl, int);
    sum += val;
  }
  va_end(vl);
  
  return sum; 
}

int test_vararg()
{
  int a = sum_i(10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
  return a;
}

上記のコードをコンパイルして、どのようなコードが生成されているのか見てみる。

./bin/clang -O0 -c vararg.cpp -emit-llvm -o vararg.bc
# ABI=LP64でコンパイルした場合
./bin/llc -stats -debug -target-abi=lp64 -march=myriscvx32 -mcpu=simple32 -enable-MYRISCVX-tail-calls=false -relocation-model=static -filetype=asm vararg.bc -o -
# ABI=STACK32でコンパイルした場合
./bin/llc -stats -debug -target-abi=stack32 -march=myriscvx32 -mcpu=simple32 -enable-MYRISCVX-tail-calls=false -relocation-model=static -filetype=asm vararg.bc -o -
  • Caller側
    • ABI=LP64の場合
        addi    x10, zero, 7    # レジスタ経由で入りきらない引数はスタックを経由する。第8引数
        sw      x10, 0(x2)
        addi    x10, x2, 8
        addi    x11, zero, 9    # レジスタ経由で入りきらない引数はスタックを経由する。第10引数
        sw      x11, 0(x10)
        addi    x10, x2, 4
        addi    x11, zero, 8    # レジスタ経由で入りきらない引数はスタックを経由する。第9引数
        sw      x11, 0(x10)
        addi    x10, zero, 10   # 引数の数 : amount
        addi    x11, zero, 0    # 第1引数
        addi    x12, zero, 1    # 第2引数 ...
        addi    x13, zero, 2
        addi    x14, zero, 3
        addi    x15, zero, 4
        addi    x16, zero, 5
        addi    x17, zero, 6    # レジスタ経由はこれが限界
        jal     _Z5sum_iiz

レジスタ渡しできる限りはレジスタ経由で渡す。A0-A7までのレジスタを使って引数を渡し、それでも足りないので残りはスタック経由で渡している。

  • ABI=STACK32の場合
        addi    x10, zero, 10
        sw      x10, 0(x2)
        addi    x10, x2, 40
        addi    x11, zero, 9
        sw      x11, 0(x10)
        addi    x10, x2, 36
...
        addi    x11, zero, 1
        sw      x11, 0(x10)
        addi    x10, x2, 4
        addi    x11, zero, 0
        sw      x11, 0(x10)
        jal     _Z5sum_iiz

見てわかる通り、すべてスタック経由での引数渡しとなっている。

  • Callee側
    • ABI=LP64の場合
_Z5sum_iiz:
        .cfi_startproc
...
# %bb.0:                                # %entry
        addi    x2, x2, -64
        .cfi_def_cfa_offset 64
        sw      x17, 60(x2)     # 可変引数8をスタックに格納
        sw      x16, 56(x2)     # 可変引数7をスタックに格納
        sw      x15, 52(x2)     # ....
        sw      x14, 48(x2)
        sw      x13, 44(x2)
        sw      x12, 40(x2)
        sw      x11, 36(x2)     # 可変引数1をスタックに格納
        sw      x10, 32(x2)     # 引数amountをスタックに格納
        addi    x10, zero, 0

まず、レジスタ経由で渡した引数をすべてスタックに格納する。もったいないだが、こうすることで以降の処理コードをより簡潔にする。

  • ABI=STACK32の場合
_Z5sum_iiz:
...
# %bb.0:                                # %entry
        addi    x2, x2, -32
        .cfi_def_cfa_offset 32
        sw      x10, 28(x2)
        lw      x10, 32(x2)
        addi    x10, zero, 0
...

引数のスタック退避はない。

続いて、実際の引数の処理に入る。先ほど説明したように、引数のサイズが40バイトを超えない場合はスタックで処理され、それを超える場合はグローバル領域経由で処理される。

# %bb.2:                                # %for.body
                                        #   in Loop: Header=BB0_1 Depth=1
        addi    x10, x2, 0
        lw      x12, 0(x2)
        addi    x11, zero, 40
        sltu    x11, x11, x12
        bne     x11, zero, $BB0_4

続いて、実際の引数の処理に入る。40バイト以内では、vaarg.in_regのラベルがついているコードが実行される。

# %bb.3:                                # %vaarg.in_reg
                                        #   in Loop: Header=BB0_1 Depth=1
        addi    x11, x10, 12
        lw      x11, 0(x11)
        add     x11, x11, x12
        addi    x12, x12, 8
        sw      x12, 0(x10)
        j       $BB0_5

最終的に加算が行われるのは以下だ。%vararg.endラベル以下が、実際の処理になる。

$BB0_5:                                 # %vaarg.end
                                        #   in Loop: Header=BB0_1 Depth=1
        lw      x10, 0(x11)
        sw      x10, 20(x2)
        lw      x10, 20(x2)
        lw      x11, 16(x2)
        add     x10, x11, x10
        sw      x10, 16(x2)