CPU内のキャッシュラインを置き換えるためのフローについて考える

キャッシュの置き換えアルゴリズムというのはいろいろあるけれども、ここではそういう話ではなくて「どうアトミックにキャッシュを置き換えるか」ということを考えた。 つまり、キャッシュを掃き出してロードするまでには間隔があくわけで、それをきちんと実行しないとキャッシュラインを吐き出した後に残っているCPUキャッシュラインに 誤ってデータをストアしてしまう可能性がある。

L1Dのデータ置き換え操作についてフローを考えたので、備忘録として残しておく。 以下はメモ。

L1Dデータの掃き出し

L1Dデータの掃き出し(eviction)は、以下の条件で実行されます。 1. ロード命令パイプライン実行中にL1Dキャッシュを確認した際、L1Dミス発生かつ当該キャッシュラインに空きがない場合 2. ストア命令が完了後にL1Dキャッシュに書き込む際、L1Dミス発生かつ当該キャッシュラインに空きがない場合

掃き出し行うキャッシュラインの管理は、LRQ内で行われます。

1. の場合、L1DキャッシュリクエストがLRQ内のエントリに格納されると同時に、 同じエントリに掃き出し対象のキャッシュラインの情報が格納されます。 このとき、L1Dキャッシュのタグ情報は更新されないため、LRQ内のエントリは、そのエントリが有効である間、LSUパイプラインを監視し、 同じアドレス範囲のメモリアクセスが発生するとハザードを通知し、LRQの処理とL1Dキャッシュの完全な入れ替えが完了するまでは 当該後続命令の再実行を禁止します。

2. の場合、ストア命令のコミット終了後にL1Dキャッシュラインの存在確認が行われ、もし2. の条件を満たした場合は 掃き出し対象のキャッシュラインがLRQに取得されます。

LRQはミスを発生したキャッシュラインを取得するためにCPU外部にリードリクエストを送出しますが、 同時に掃き出し対象のキャッシュラインもCPU外部にライトリクエストで放出します。

"同じアドレス範囲のメモリアクセスが発生すると完全な入れ替えが完了するまでは当該命令の再実行を禁止する"理由は、 L1Dキャッシュのタグ情報は置き換え対象となるキャッシュラインの情報にまだ置き換わっていないため、 もし後続の命令が吐き出されるキャッシュラインに対して書き込みを行っても、すでにキャッシュラインがCPU外部に吐き出されてしまっているためです。

Digital Design and Computer Architecture RISC-V Edition を買った

Digital Design and Computer Architecutre というのは、通称Hariss & Harris と呼ばれ、デジタル回路、コンピュータアーキテクチャの基礎的な題材を取り扱う非常に有名な教科書だ。

これまで第1版、第2版と出てきて、さらにARM版も出てきている。これらは日本語にも翻訳されており初心者向けに分かりやすい内容となっている。

Digital Design and Computer Architecture (English Edition)

ディジタル回路設計とコンピュータアーキテクチャ 第2版

ディジタル回路設計とコンピュータアーキテクチャ[ARM版]

そしてついにこのシリーズにおける最新版、RISC-Vに対応した新刊が登場した。 まだAmazonではデジタル紙媒体は入手できないが、デジタル版はElsevierでも入手できるようなので早速購入した。

実は私はこのシリーズはこれまでに英語版、日本語版を含め購入したことがない(少し初心者向けかなと思い購入していなかった)。 今回初めて買ってみて、まだ内容を読んでおらず目次だけ眺めているのだが、大体以下のような構成となっている。

• 第1章: From Zero to One (ゼロから1へ)
• 第2章: Combinational Logic Design (組み合わせ回路の設計)
• 第3章: Sequential Logic Design (順序回路の設計)
• 第4章: Hardware Description Languages (ハードウェア記述言語)
• 第5章 : Digital Building Blocks (デジタルビルディングブロック)
• 第6章 : Architecture (アーキテクチャ)
• 第7章 : Microarchitecture (マイクロアーキテクチャ)
• 第8章 : Memory Systems (メモリシステム)
• 第9章 : Embedded I/O Systems (組み込みI/Oシステム)

という訳で、前半は殆ど昔の版と同じではないかと予想する。前半についてはあまり詳細に読み込む必要はないかなと思うけれども、いい機会だし復習するのもいいかもしれない。まずは興味のあるところだけ読み進めていくかな。

ストアバッファについて考える

最近は色々あってCPUのストアバッファについて考えている。 ストアバッファは簡単に言えばコミット済みのストア命令を、STQ(Store Queue)から分離しL1Dキャッシュもしくは外部へ書き込むまでの生存管理を行うものだ。 STQによるLSUパイプライン実行とL1Dへの書き込み処理を分離することで、効率よく動作を管理できるようになる。

ストアバッファについては以下の文章が参考になる。

developer.arm.com

stackoverflow.com

で、自分でいろいろ考えながら自作CPUのために仕様を書いてみた。以下は備忘録。

---

ストアバッファ

コミットされたストア命令はデータをL1Dに書き込みますが、その前にアドレスとデータの情報はストアバッファに移されます。 ストアバッファはコミットされたストア命令が、L1Dキャッシュに書き込まれるまでの状態を管理します。 ストアバッファは XLEN * 2 ビット幅のデータを管理することができ、隣接する複数のデータを管理することができます。

コミット処理により複数のストア命令がコミット状態になった時、コミット対象の先頭となる命令に対して、 連続する後続のコミット状態の命令も同じストアバッファの管理アドレス範囲に存在している場合、 その複数の命令はマージされてストアバッファに格納されます。

• ストア対象となるアドレスがL1Dに存在しているかどうかをチェックする
  • 存在する場合はL1Dに書き込みを行う
  • 存在していない場合はLoad L1D Requester(LRQ)に対して当該キャッシュラインのロード要求を行う
• ストアバッファは後続のコミット済みストア命令が同じキャッシュラインに書き込みを行う場合、それを検出してマージを行います。
  • マージされたデータは、一緒にL1Dに書き込まれます。

ストアバッファは複数のエントリを持ち、それぞれのエントリは以下のように動作します。

1. サイクル1. L1Dキャッシュに対して当該物理アドレスの読み込み処理を行う。2. へ移動する
2. サイクル2. L1Dキャッシュに存在していれば(Hit)、3. へ移動する。そうでなければ4.へ移動する
3. サイクル3. L1Dキャッシュへの書き込みを行う。処理を終了する
4. サイクル3. L1Dキャッシュに存在していない場合、L1D LRQ(Load Requester)にロード要求を発行する。5. へ移動する
5. サイクルN. Load Requesterからデータのロード通知を受けると、L1Dキャッシュに対してロードデータのマージリクエストを通知する。処理を終了する

RVWMOにおけるリトマステストについて調べる

RISC-VはメモリコンシステンシモデルとしてRVWMO (RISC-V Weakl Memory Ordering)を採用している。 RVWMOについての説明はRISC-Vの仕様書のAppendixについて説明されているが、ここを読んでいくことにする。

RVWMOを理解するにあたって、リトマステストというのを使用する。リトマステストについてはかつて論文を読んで勉強していたのだが、本章を読んで思い出してみよう。

GitHub - riscv/riscv-isa-manual: RISC-V Instruction Set Manual

A.2 リトマステスト

本章では、メモリモデルのある特定の側面をテストしたり、強調したりするために設計された小さなプログラムである、リトマステストを用いて説明します。図 A.1は、2 つの hart を使ったリトマステストの例です。ここでは、すべての hart で s0～s2 が同じ値に設定されており、s0 が x、s1 が y、s2 が z と表示されたアドレスを保持しているものとします。左側にリトマステストのコード、右側に有効または無効な実行結果を表示しています。

リトマステストは、特定の具体的な状況におけるメモリモデルの意味合いを理解するために使用されます。例えば、図 A.1のリトマステストでは、第 1 の hart の a0 の最終値は、実行時の各 hart からの命令ストリームの動的インターリーブによって、2、4、5 のいずれかになります。しかし、この例では、hart 0 の a0 の最終的な値が 1や 3 になることはありません。直感的には、ロードが実行される時点では 1 の値は見えなくなり、ロードが実行される時点では 3 の値はまだ見えていません。

RISC-V 拡張命令の命名ポリシについて

RISC-Vの仕様書27章にある「ISA Extension Naming Convensations」が面白かったので纏めてみる。

• RISC-Vの命名文字列(つまり、RV64IMAFDCやRV32IMCなど)は、大文字小文字を区別しない。
• 標準拡張、つまり以下の拡張命令には表記の順序がある。以下の表において、上から下に文字列を並べる必要がある。つまり、"RV64IMACV"は有効だが"RV64IMAVC"は無効となる。

• 拡張命令にはバージョン番号を付けることができる。実はRISC-Vバージョン1.0では、正式な名称を、以下のように表記する。
  • RV64I1p0M1p0A1p0F1p0D1p0
  • アルファベットの次にメジャーバージョン、pの次にマイナーバージョンを示す。メジャーバージョンを変更せずにマイナーバージョンのみを変更した場合、後方互換性を維持する必要がある。
• アンダースコアを使って可読性を上げることができる。特に、Packed SIMDを示す"P"はマイナーバージョンの"p"と区別するために必ずアンダースコアを付ける。
• "RV32I2p2" : 32ビットRISC-Vバージョン2.2
• "RV32I2_p2" : 32ビットRISC-Vバージョン2とP拡張バージョン2.0
• スーパーバイザレベル命令の拡張には"S"を接頭語とする。
• ハイパーバイザレベル命令の拡張には"H"を接頭語とする。
• マシンレベル命令セットの拡張には"Zxm"を接頭語とする。
• 非標準の拡張には"X"を接頭語として付ける。例えばHwachaベクトルフェッチISAの拡張の場合には"Xhawacha2"とする。

ELFからHEXに変換するためのツール

ModelSim(32-bit版)を使うにあたり、これまで使っていたlibelfが使用できなくなり、elfをhexに変換してRAMにロードする必要が生じた。 しかもRAMとしてシミュレーション用に連想配列を使っているので、readmemhで読み込む際にアドレス情報が必要になる。いくつかツールを探したがないので自分で実装した。

もとはELFをダンプするためのツールだったのだが、hexファイルを出力するためにいくつか改良した。

もともと以下のリポジトリにelf2hexがあるのだが、binファイルを経由するのでアドレス情報が消えてしまっている。アドレス情報を残したうえでreadmemhに流したい。

github.com

hexファイルにおいてアドレスは@で指定することができる。

www.asic-world.com

例えば以下のようにする。以下は256ビットのRAMに対して0x8000_0000へのアクセスを行うための初期値配置。0x8000_0000に対して256ビット(32バイト)なのでアドレスを5ビットシフトして0x0400_000に置いている。

@04000000 // 80000000
03ff026300b00f9303ff066300900f9303ff0a6300800f9334202f7304c0006f
5391e1930040006f000f546334202f73000f0067000f0463fe0f0f1380000f17
0000029300000213000001930000011300000093ff9ff06ffc3f202300001f17
0000069300000613000005930000051300000493000004130000039300000313
00000a9300000a13000009930000091300000893000008130000079300000713

こんな感じでELFを読み取って吐き出すコードを作った。

      fprintf (stdout,"@%08lx // %08lx\n", base / dump_bytewidth, base);
      for(count=0; count < valsRead; count=count+dump_bytewidth) {

        base = base + dump_bytewidth;
        switch (identity[EI_DATA]) {

          case 1: {     /* Little endian */
            int max_count = valsRead - count < dump_bytewidth ? valsRead - count : dump_bytewidth;
            for (count2 = max_count-1;count2 >= 0;count2--) {
              fprintf (stdout,"%.2x",static_cast<uint8_t>(buffer[count+count2]));
            }
            fprintf (stdout,"\n");
            break;
          }
          case 2:       /* Big endian */
            for (count2=0;count2<4;count2++) {
              fprintf (stdout,"%.2x",static_cast<uint8_t>(buffer[count+count2]));
            }
            fprintf (stdout,"\n");
            break;

          default:
            printf ("Undetermined Endianness.  Fatal error.\n");
            exit(EXIT_FAILURE);
        }
      }

LLVM13でのAPI変更点について確認

LLVMバックエンドの開発で、これまで使用していたrelease/12.xブランチからrelease/13.xに移行したときのAPIの変更点について確認した。 今回はAPIの変更点が少ない。

namespace llvm {

// 以下のコードを追加
class formatted_raw_ostream;

• MCTargetDesc/MYRISCVXTargetStreamer.h

bool MYRISCVXFrameLowering::hasFP(const MachineFunction &MF) const {
  const MachineFrameInfo &MFI = MF.getFrameInfo();
  const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo();

  // フレームの条件コードが変わっていた
   return MF.getTarget().Options.DisableFramePointerElim(MF) ||
      RegInfo->hasStackRealignment(MF) || MFI.hasVarSizedObjects() ||
      MFI.isFrameAddressTaken();
}

これでリコンパイルして一応動作を確認することが出来た。

$ ./bin/llvm-lit ../llvm/test/CodeGen/MYRISCVX

-- Testing: 37 tests, 16 workers --
PASS: LLVM :: CodeGen/MYRISCVX/fp_ops_mad.ll (1 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/fp_ops_simple.ll (2 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/func_lot_arguments.ll (3 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/constants.ll (4 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/struct_pass_rv32.ll (5 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/arith_32bit_rv32.ll (6 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/arith_64bit_rv64.ll (7 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/load_pointer.pic.ll (8 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/arith_32bit_rv64.ll (9 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/fp_args.ll (10 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/global_variable.pic.ll (11 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/sum_array.ll (12 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/int_array.static.ll (13 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/int_array.pic.ll (14 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/load_pointer.static.ll (15 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/global_variable.static.ll (16 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/do_while_count.static.ll (17 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/caller.static.ll (18 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/compare_slt.ll (19 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/cond_if.static.ll (20 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/arithmetics.ll (21 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/simple_func.ll (22 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/constants2.ll (23 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/callee.static.ll (24 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/switch_table.static.ll (25 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/mem_access.ll (26 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/select_exp.static.ll (27 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/struct_pass_rv64.ll (28 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/make_frame.ll (29 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/struct_char.static.ll (30 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/struct_pattern_match.static.ll (31 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/rotate.ll (32 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/zero_return.ll (33 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/simple_select.static.ll (34 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/value_return.ll (35 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/long_value.ll (36 of 37)
PASS: LLVM :: CodeGen/MYRISCVX/tailcall.ll (37 of 37)

Testing Time: 0.82s
  Passed: 37