FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

分岐予測の評価キット Branch Prediction Championship Kit を試す (2. トレースファイルを解析する)

Branch Prediction Championship Simulatorの続きを試す。

Branch Prediction Simulatorのトレースファイルの中身を解析する。

トレースファイルの中身を読んで見る

例えば、SHORT_MOBILE-24.bt9.trace.gzの中身は以下のようになっている。大きく分けて4つの領域に分かれているように見える。

  1. たぶんトレースファイルの諸元のようなところ。
BT9_SPA_TRACE_FORMAT
bt9_minor_version: 0
has_physical_address: 1
md5_checksum:
conversion_date:
original_stf_input_file:
total_instruction_count:       1000000000    # Instruction count
branch_instruction_count:         38684343    # Branch count
invalid_physical_branch_target_count:          2226408    # Invalid Physical Target Count
A32_instruction_count:       1000000000    # A32 instructions
A64_instruction_count:                0    # A64 instructions
T32_instruction_count:                0    # T32 instructions
unidentified_instruction_count:                0    # Unidentified instructions
  1. ノード。つまり命令そのものを表す。ここでは、分岐命令しか定義しないようだ。
BT9_NODES
#NODE   id      virtual_address    physical_address          opcode  size
NODE    0                    0                    -                0    0
NODE    1           0x40015a98           0xcb25ea98       0x1afffffb    4    class:  JMP+DIR+CND  behavior:  DYN+DIR  taken_cnt:       61  not_taken_cnt:        1  tgt_cnt:   1  # mnemonic: "bne       0x0000000040015a8c"
NODE    2           0x40015a9c           0xcb25ea9c       0xeaffee70    4    class:  JMP+DIR+UCD  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "b         0x0000000040011464"
NODE    3           0xffff0008           0xcb174008       0xe59ff410    4    class:  JMP+IND+UCD  behavior:   AT+DIR  taken_cnt:       13  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "ldr       pc, [pc, #1040]    ; 0x00000000ffff0420"
NODE    4           0xc0023f0c           0xcaa12f0c       0x1a000008    4    class:  JMP+DIR+CND  behavior:  ANT+DIR  taken_cnt:        0  not_taken_cnt:       13  tgt_cnt:   0  # mnemonic: "bne       0x00000000c0023f34"
NODE    5           0xc0023f18           0xcaa12f18       0x3798f107    4    class:  JMP+IND+CND  behavior:  DYN+IND  taken_cnt:       12  not_taken_cnt:        1  tgt_cnt:   2  # mnemonic: "ldrcc     pc, [r8, r7, lsl #2]"
NODE    6           0xc0023f2c           0xcaa12f2c       0x2a000ebe    4    class:  JMP+DIR+CND  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "bcs       0x00000000c0027a2c"
NODE    7           0xc0027a50           0xcaa16a50        0xa00001f    4    class:  JMP+DIR+CND  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "beq       0x00000000c0027ad4"
NODE    8           0xc0027adc           0xcaa16adc       0x979ff101    4    class:  JMP+IND+CND  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "ldrls     pc, [pc, r1, lsl #2]"
NODE    9           0xc0027c58           0xcaa16c58       0xea000016    4    class:  JMP+DIR+UCD  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "b         0x00000000c0027cb8"
NODE   10           0xc0027cc0           0xcaa16cc0       0xe89da870    4    class:  RET+IND+UCD  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "ldm       sp, {r4, r5, r6, r11, sp, pc}"
NODE   11           0xc0023e0c           0xcaa12e0c       0x1a000006    4    class:  JMP+DIR+CND  behavior:  DYN+DIR  taken_cnt:        6  not_taken_cnt:        7  tgt_cnt:   1  # mnemonic: "bne       0x00000000c0023e2c"
NODE   12           0xc0023e28           0xcaa12e28       0xe1b0f00e    4    class:  RET+IND+UCD  behavior:   AT+IND  taken_cnt:        7  not_taken_cnt:        0  tgt_cnt:   2  # mnemonic: "movs      pc, lr"
NODE   13           0x40011478           0xcb262478       0x512fff1e    4    class:  RET+IND+CND  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "bxpl      lr"
NODE   14           0x40016c28           0xcb25dc28       0xe12fff35    4    class: CALL+IND+UCD  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "blx       r5"
NODE   15           0x4807ea34           0xe36cba34       0xeb000032    4    class: CALL+DIR+UCD  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "bl        0x000000004807eb04"
NODE   16           0x4807eb1c           0xe36cbb1c       0xe12fff1e    4    class:  RET+IND+UCD  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "bx        lr"
NODE   17           0x4807ea3c           0xe36cba3c       0xeb000051    4    class: CALL+DIR+UCD  behavior:   AT+DIR  taken_cnt:        1  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "bl        0x000000004807eb88"
NODE   18           0x4807eb90           0xe36cbb90       0xebffffea    4    class: CALL+DIR+UCD  behavior:   AT+DIR  taken_cnt:        4  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "bl        0x000000004807eb40"
NODE   19           0x4807eb50           0xe36cbb50       0xebfe4be4    4    class: CALL+DIR+UCD  behavior:   AT+DIR  taken_cnt:        6  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "bl        0x0000000048011ae8"
NODE   20           0x48011af0           0xe3640af0       0xe5bcf324    4    class:  JMP+IND+UCD  behavior:   AT+DIR  taken_cnt:        6  not_taken_cnt:        0  tgt_cnt:   1  # mnemonic: "ldr       pc, [r12, #804]!   ; 0x324"
NODE   21           0xc003f0f4           0xcaa2e0f4        0xa000011    4    class:  JMP+DIR+CND  behavior:  ANT+DIR  taken_cnt:        0  not_taken_cnt:        6  tgt_cnt:   0  # mnemonic: "beq       0x00000000c003f140"
  1. エッジ。つまりノードからノードへどのように飛ぶのかを見ている。ある分岐命令から、次の分岐命令までどのように飛ぶ選択肢があるのかを示しているようだ。
BT9_EDGES
#EDGE    id  src_id   dest_id  taken      br_virt_target       br_phy_target   inst_cnt
EDGE      0      0      1        N                    0                    -        6   traverse_cnt:        1
EDGE      1      1      1        T           0x40015a8c           0xcb25ea8c        3   traverse_cnt:       61
EDGE      2      1      2        N           0x40015a8c                    -        0   traverse_cnt:        1
EDGE      3      2      3        T           0x40011464           0xcb262464        3   traverse_cnt:        1
EDGE      4      3      4        T           0xc0023ec0           0xcaa12ec0       19   traverse_cnt:       13
EDGE      5      4      5        N           0xc002591c                    -        2   traverse_cnt:       13
EDGE      6      5      6        N           0xc00414ae                    -        4   traverse_cnt:        1
EDGE      7      6      7        T           0xc0027a2c           0xcaa16a2c        9   traverse_cnt:        1
EDGE      8      7      8        T           0xc0027ad4           0xcaa16ad4        2   traverse_cnt:        1
EDGE      9      8      9        T           0xc0027c38           0xcaa16c38        8   traverse_cnt:        1
EDGE     10      9     10        T           0xc0027cb8           0xcaa16cb8        2   traverse_cnt:        1

これから見て分かるのは、

  • エッジ1 : ノードID1からノードID1へ、分岐成立
  • エッジ2 : ノードID1からノードID2へ、分岐非成立

となるように表現されている。ここで矛盾がないようにこのノードが構成されているわけだが、まあ実際の実行ログから作られているだろうし、矛盾は含まれていないだろう。

  1. シーケンス

さきほどのエッジを使って、どの命令からどの命令へ移っていくのかが全部リストになっている。リストと言ってもひたすら数字が並んでいる。

1   // Node1 -> Node1 Taken
1   // Node1 -> Node1 Taken
1   // Node1 -> Node1 Taken
1   // Node1 -> Node1 Taken
1   // Node1 -> Node1 Taken
2   // Node1 -> Node2 UnTaken
3   // Node2 -> Node3 Taken
4   // Node3 -> Node4 Taken
5   // Node4 -> Node5 UnTaken
6   // Node5 -> Node6 UnTaken
7   // Node6 -> Node7 Taken
8   // Node7 -> Node8 Taken
9   // Node8 -> Node9 Taken
10  // Node9 -> Node10 Taken
11
12