インベーダーゲームのソースの研究を読んで理解したことを記します。

UFOスコア表

参考にしたUFOスコア表です。

図319.1 UFOスコア表

BSV実装

この表には重なりがあるので、実は、表は1つで問題ありません。 弊社のBSV実装では以下の表を用いています。

UInt#(5) ufo_score[15] = {10,10,10,5,15,10,10,5,5,10,15,10,10,5,30};

ただし、インデックスの初期値を6としており、7番目から使用することで上記のアルゴリズムを再現しています。まず、インデックスの初期化です。

ufo_score_idx <= 6;

次にインクリメント部です。この表は15エントリしかないので、15でラップアラウンドします。

ufo_score_idx <= ufo_score_idx + 1; if (ufo_score_idx == 15) ufo_score_idx <= 0;

また、インベーダーゲームは得点の1の位は常に0なので、得点は1/10で記憶しています。

オリジナル

さて、ソースコードの研究によると、少々ズレています。

図319.2 UFOスコア表
コメントでも書かれているように、UFOスコア表は16エントリにも関わらず、バグにより15個までしか使用されず、15番目の次は0番目に戻っています。従って、最後の50点は使用されません。

Javascript実装

最後に、Javascriptによる実装でも同様なアルゴリズムにより、自弾ショット数の15の剰余を取った数に6のオフセットをかけています。

const // UFOスコアテーブル us = [100,100,100,50,150,100,100,50,50,100,150,100,100,50,300];

const plus = us[(6 + shotCount) % 15];

結果として、上記4種類は実装は微妙に異なるものの、最終的には同一の結果となります。

---

前のブログ 次のブログ

インベーダーゲームのソースの研究を読んで理解したことを記します。

敵弾速度

参考にしたcellvaderにおいて、敵弾の移動速度は1pixcel/tickでした(tick=1/60sec)。それで特に違和感がなかったのですが、上記資料を見ると、33%も速い4pixcel/3tickとのこと。そのため、3tick毎に4pixcel動かすように修正しますが、注意として衝突判定は1pixcel毎に行う必要があります。そうでないとすり抜けが起きる可能性があります。従って、

フレーム0:　何もしない
フレーム1:　何もしない
フレーム2:　y座標を-1して衝突判定、衝突の場合は衝突処理し、中断
　　　　　　y座標を-2して衝突判定、衝突の場合は衝突処理し、中断
　　　　　　y座標を-3して衝突判定、衝突の場合は衝突処理し、中断
　　　　　　y座標を-4して衝突判定、衝突の場合は衝突処理し、中断
　　　　　　y座標を-4して敵弾移動

この3フレームを繰り返すことになります。さらに、インベーダ―数が8未満の場合は敵弾速度が高速化するとのことです。具体的には5pixcel/3tickとなります。従って、上記のフレーム2においてさらに「y座標を-5して衝突判定、衝突の場合は衝突処理し、中断」の処理を加え、敵弾はy-5の場所に移動します。

歩行音

フリートトーン(fleet tone)、もしくはステップサウンド(step sounds)と書かれていますが、インベーダーの歩行音のことです。同じく参考にしたcellvaderでは、歩行音の発生間隔は1tone/1fleetでした。つまり隊の動作と歩行音が同期しています。ただし、歩行音の発生毎に4種類の歩行音を切り替えます。

ところが、インベーダーゲームのソースの研究では、隊の移動と歩行音は同期しておらず、歩行音間隔の最小は5だとのことです。具体的な表を示せば、オリジナルのアルゴリズムは以下の表318.1のようになります。確かに、現状の実装ではインベーダー数が1になる場合は歩行音が速すぎる気がします。原文には5未満になると不愉快な音になると書かれています。

表318.1　オリジナルの歩行音間隔表

インベーダー数[匹]	歩行音間隔[tick]
55	52
54	52
53	52
52	52
51	52
50	52
49	46
48	46
47	46
46	46
45	46
44	46
43	46
42	39
41	39
40	39
39	39
38	39
37	39
36	39
35	34
34	34
33	34
32	34
31	34
30	34
29	34
28	34
27	28
26	28
25	28
24	28
23	28
22	28
21	24
20	24
19	24
18	24
17	24
16	21
15	21
14	21
13	21
12	19
11	19
10	19
9	16
8	16
7	14
6	13
5	12
4	11
3	9
2	7
1	5

そのため、現状での隊(rack)の先頭での歩行音処理を廃止し、次の処理を追加します。

• 歩行音間隔タイマーを設置します。
• インベーダー1匹の処理につき、歩行音間隔タイマーを1だけデクリメントし、タイマーがゼロになったら歩行音を鳴らします。
• タイマーがゼロになったら、その時点のインベーダー数で上表を引き、歩行音間隔値をロードします。

インベーダーが減るたびに上表を引いて歩行音間隔値を変更するのではありません。それだとタイマーがゼロになる寸前でインベーダーが死ぬと新たなタイマー値がロードされ、歩行音間隔が約2倍の長さとなる不具合が起きる可能性があります。

歩行音が隊と同期はしていても不快な音にならないように、最小を5にするだけで良いような気もしますが。

Javascript実装

Javascriptによる実装では、インベーダ数=55の時に52、インベーダ数=1の時に5と、上表と同様ですが、その間は線形補完しているようです。

---

前のブログ 次のブログ

ソースの解読

ここからはソースを読んで行きます。パイプラインプロセッサは、その名のとおり各ステージがパイプラインとして動作するもので、つまりステージ毎にステージを構成するレジスタでできています。逆に、レジスタ以外は全て組み合わせ回路です。これに気づくとソースの理解が速そうです。

難しいのはパイプラインレジスタの更新ロジックで、パイプラインが動作したりストールしたりするのはこのレジスタ更新論理ですが、一方、ステージの実質のロジックは単なる組み合わせ回路です。最も分かりやすいのが演算ステージStage1で、ALU等はファンクション(組み合わせ回路)で記述されます。

それらのファンクションはパイプラインのステージからコールされ、パイプラインにはパイプライ制御のロジックしかなくなります。従って、Fluteの複雑そうな各パイプラインステージは非常に簡単な記述になっています。表280.1に各ステージのbsvで記述された行数を示します。

表280.1　パイプラインステージとその行数

ファイル名	行数
CPU_StageF.bsv	170
CPU_StageD.bsv	153
CPU_Stage1.bsv	336
CPU_Stage2.bsv	627
CPU_Stage3.bsv	245

---

前のブログ 次のブログ

ループにおける効率調査

前稿のプログラムは命令試験プログラムだったので、キャッシュの効果が出ていませんでした。そのため、ここではループにおける効率の向上を調査します。合わせてgccの効率も調べます。

int main() {
  for (int j = 0; j < 100; j++) {
    for (int i = 0; i <= 9; i++) {
      *UART0_ADDR = '0'+i;
    }
    *UART0_ADDR = '\n';
  }

このようなループの関数を作成し、gccにより-O, -O2, -O3でコンパイルします。まず+v1で実行命令数を確認すれば、それぞれ、5617、5517、2422実行命令数となりました。

次に+v2でパイプラインの状況を確認します。

表279.1 ステージ毎のパイプラインの状態(-O)

状態	StageF	StageD	Stage1	Stage2	Stage3
BUSY	91	0	1,150	2,251	0
EMPTY	106	198	178	1,410	3,664
PIPE処理	9,187	9,186	8,056	5,723	5,720
合計	9,384

表279.2 ステージ毎のパイプラインの状態(-O2)

状態	StageF	StageD	Stage1	Stage2	Stage3
BUSY	88	0	23	2,259	0
EMPTY	106	172	170	284	2,544
PIPE処理	7,972	7,994	7,973	5,623	5,622
合計	8,166

表279.3 ステージ毎のパイプラインの状態(-O3)

状態	StageF	StageD	Stage1	Stage2	Stage3
BUSY	152	0	1,023	2,264	0
EMPTY	4	131	131	1,138	3,403
PIPE処理	5,672	5,697	4,674	2,426	2,425
合計	5,828

これらの表の合計欄がマシンサイクルを意味しています。従って、最適化度合いに対するCPIは、-O, -O2, -O3のそれぞれで1.67、1.48、2.41となりました。

表279.3の-O3においてはインナーループを展開しているため、命令キャッシュミスが若干増加しており、デコードステージ以下のパイプラインバブルが発生していますが、命令数をぐっと少なくしてマシンサイクルを縮めています。いずれも表264.1と比較すると、ループであるため命令キャッシュミスによるパイプラインストールがかなり少なくなっており、効率が向上しています。

---

前のブログ 次のブログ

Bsimによるシミュレーション

./exe_HW_sim +v1 +tohost

によりBsimのシミュレーションが実行されます。+v1で命令毎のトレース、+v2でパイプライン内容を含めたトレースが表示されます。さらに波形観測のためには

./exe_HW_sim +v1 +tohost -V dump.vcd

のようにVCDファイルを指定します。これをGtkwaveにより開き、波形を観測してみます。\$80000000から開始しており、キャッシュラインバウンダリでのブロックインが観察されます。

図278.1 シミュレーション波形

2回目に実行する場合は基本的にキャッシュヒットし、1サイクルで動作しています。

図278.2 シミュレーション波形(続き)

BsimにはUARTが実装されているため、UARTに対して、\$68('h'),\$65('e'),\$6c('l'),\$6c('l'),\$6f('o'),\$21('!'),\$0a('lf')と出力されていることが確認できます。

図278.3 シミュレーション波形(続き)

---

前のブログ 次のブログ

Bsimによるシミュレーション

QemuのシミュレーションからBsimのシミュレーションに切り替えます。ここで、Flute SoCではUARTのアドレスが異なっているため、テストプログラムのUARTアドレスを

<volatile char* UART0_ADDR = (char*)0x10000000;
>volatile char* UART0_ADDR = (char*)0xc0000000;

と変更した上でコンパイルします。

$ riscv32-unknown-elf-gcc -march=rv32i -mabi=ilp32 -nostartfiles -Tlink.lds -Wall -O2 hello.c -o hello.elf

ここで、リンカへの指示であるlink.ldsは以下のようにしています。

OUTPUT_ARCH("riscv")
ENTRY(main)

SECTIONS
{
    . = 0x80000000;
    .text.startup : { *(.text.startup) }
    .text   : {
            _start = .;
            *(.text);
            _text_end = .;
            exit = .;
         }
    .rodata : { *(.rodata) }
    .sdata   : { *(.sdata) }
    .bss    : { *.(.bss) }
    /DISCARD/ : { *(.comment);
          *(.riscv.attributes);
          *(.strtab*);
          *(.shstrtab);
        }
    . = ALIGN(8);
     = . + 0x4000;
    sp_top = .;
}

前稿で作成したelfを、Bsimによるシミュレーションが可能なhexファイルに変換します。これはFlute/Tests/elf_to_hex/elf_to_hexで行います。

$ ../Flute/Tests/elf_to_hex/elf_to_hex hello.elf Mem.hex
c_mem_load_elf: hello.elf is a 32-bit ELF file
Section .text.startup   : addr         80000000 to addr         8000006c; size 0x      6c (= 108) bytes
Section .sdata          : addr         80000068 to addr         80000070; size 0x       8 (= 8) bytes
Section .comment        : Ignored
Section .riscv.attributes: Ignored
Section .symtab         : Searching for addresses of '_start', 'exit' and 'tohost' symbols
Writing symbols to:    symbol_table.txt
    No 'exit' label found
    No 'tohost' symbol found
Section .strtab         : Ignored
Section .shstrtab       : Ignored
Min addr:                    80000000 (hex)
Max addr:                    80000073 (hex)
Writing mem hex to file 'Mem.hex'
Subtracting 0x80000000 base from addresses

作成されたhello.hexの内容は以下のようになっています。逆アセンブルリストと比較して概ね良さそうです。

@0000000    // raw_mem addr;  byte addr: 00000000
00c6802306c007130707a68300d7002306500613068006930707a703800007b7    // raw_mem addr 00000000;  byte addr 00000000
0707a70300d7002306f006930707a70300e680230707a68300e680230707a683    // raw_mem addr 00000001;  byte addr 00000020
000057b706c7a703800007b700e7802300a007130707a78300d7002302100693    // raw_mem addr 00000002;  byte addr 00000040
00000000000000000000000010000000001000000000806700f7102355578793    // raw_mem addr 00000003;  byte addr 00000060
@07fffff    // last raw_mem addr;  byte addr: 0fffffe0
000000000000000000000000000000000000000000000000000000000000000    // raw_mem addr 007fffff;      byte addr 0fffffe0

---

前のブログ 次のブログ

開発環境のインストール

開発環境のインストールを行います。最初にct-ngをインストールしようとしたのですが、RV32ではうまく行きませんでした。そこで、この記事を参考にインストールを実施しました。make中にインストールもしているので、あらかじめ/opt/riscvを作成しておき、記事中にもあるように自分が書き込み可能にしておくのが良さそうです。

qemuについてもこの記事のとおりにインストールしますが、

ERROR: glib-2.48 gthread-2.0 is required to compile QEMU

このようなエラーが出ました。私はFedora32を使用しているので、

$ sudo dnf install glib2 glib2-devel pixman-devel

と不足しているパッケージを追加したところ、configureが通ったので、makeします。

テストプログラム実行

早速、テストプログラムhello.cをコンパイルして実行してみます。Qemuを前提とするプログラムで、QemuのUartとシミュレーション停止アドレスが定義されています。

volatile char* UART0_ADDR = (char*)0x10000000;
volatile short* VIRT_TEST_ADDR = (short*)0x100000;

void _start(void) __attribute__((section(".text.startup")));

void _start(void) {
  *UART0_ADDR = 'h';
  *UART0_ADDR = 'e';
  *UART0_ADDR = 'l';
  *UART0_ADDR = 'l';
  *UART0_ADDR = 'o';
  *UART0_ADDR = '!';
  *UART0_ADDR = '\n';
  *VIRT_TEST_ADDR = 0x5555;
}

gccによりコンパイルし、qemuによりシミュレーションを行います。

$ riscv32-unknown-elf-gcc -march=rv32i -mabi=ilp32 -nostartfiles -Tlink.lds -Wall -O2 hello.c -o hello.elf
$ qemu-system-riscv32 -nographic -M virt -m 4096 -serial mon:stdio -bios none -kernel hello.elf
hello!

Qemuによりシミュレーションができました。また、逆アセンブラはobjdumpであり、以下の方法でアセンブルリストが確認できます。

$ riscv32-unknown-elf-objdump -D hello.elf

hello.elf:     ファイル形式 elf32-littleriscv

セクション .text.startup の逆アセンブル:

80000000 <_start>:
80000000:       800007b7                lui     a5,0x80000
80000004:       0707a703                lw     a4,112(a5) # 80000070 <sp_top+0xffffbff8>
80000008:       06800693                li      a3,104
8000000c:       06500613                li      a2,101
80000010:       00d70023                sb      a3,0(a4)
80000014:       06c7a683                lw      a3,108(a5)
80000018:       06c00713                li      a4,108
8000001c:       00c68023                sb      a2,0(a3)
80000020:       06c7a683                lw      a3,108(a5)
80000024:       00e68023                sb      a4,0(a3) 
:

---

前のブログ 次のブログ

シミュレーションモデルの波形を観測してみます。テストプログラムは、\$80000000から始まっていますが、シミュレーションは\$1000から始まっています。これはBootROMのようです。BootROMのブロックインが19サイクルかかっています。

図275.1はGtkwaveによるシミュレーション波形で、pcをオレンジ色で塗っています。

図275.1 シミュレーション波形
BootROMの処理が終わり、\$80000000にジャンプし、すぐに\$8000004cにジャンプしています。ここでpcだけを見ると、\$80000000が20サイクル、\$8000004cが24サイクルも継続しています。Linuxが動作するMMUを持つプロセッサであるためやむを得ないとはいえ、キャッシュアクセスレイテンシが大きいように思われます。 図275.2 シミュレーション波形(続き)
図275.2はテストプログラム実行中で、このような波形が続きますが、24サイクルのブロックインに引き続き、8命令を1サイクル実行しています。

---

前のブログ 次のブログ

前々稿の記事において、シミュレーションモデルが生成できましたが、これを実行させてみます。

テストプログラムは、add命令単体テストで、

80000000 <_start>:
80000000:       04c0006f                j       8000004c <reset_vector>
8000004c <reset_vector>:

8000004c:       f1402573                csrr    a0,mhartid
80000050:       00051063                bnez    a0,80000050 <reset_vector+0x4>
80000054:       00000297                auipc   t0,0x0
80000058:       01028293                addi    t0,t0,16 # 80000064 <reset_vector+0x18>
8000005c:       30529073                csrw    mtvec,t0
80000060:       18005073                csrwi   satp,0
:

80000100 <test_2>:
80000100:       00000093                li      ra,0
80000104:       00000113                li      sp,0
80000108:       00208f33                add     t5,ra,sp
8000010c:       00000e93                li      t4,0
80000110:       00200193                li      gp,2
80000114:       4ddf1663                bne     t5,t4,800005e0 <fail>

80000118 <test_3>:
80000118:       00100093                li      ra,1
8000011c:       00100113                li      sp,1
80000120:       00208f33                add     t5,ra,sp
80000124:       00200e93                li      t4,2
80000128:       00300193                li      gp,3
8000012c:       4bdf1a63                bne     t5,t4,800005e0 <fail>
:

のように構成されています。Bsimによるシミュレーションは、+v1で命令トレースが、+v2でパイプラインステージの内容を表示させるようになっています。+v2で実行させた結果をgrepにより計数してみると、表274.1のようになりました。パイプラインの各ステージの出力ステータスの意味は、以下のとおりです。

• EMPTY --- 入力が来ないためアイドルとなっている
• BUSY --- 入力があるが、処理中で出力がレディではない
• PIPE --- 入力があり、パイプラインは正常な出力を行っている
• NONPIPE --- 入力があり、出力は例外的な場合(トラップ等)

表274.1 ステージ毎のパイプラインの状態

状態	StageF	StageD	Stage1	Stage2	Stage3
BUSY	1,118	0	23	26	0
EMPTY	22	1,094	959	1,373	1,409
PIPE処理	743	789	901	484	474
合計	1,883

この表だけでもいろいろなことが推測されます。

• 試験命令数は473命令だったので、CPI(Cycles Per Instruction)は3.98となりました。命令キャッシュミスのためにかなり大きく(悪く)なっています。
• マシンサイクル1,883サイクルのうち、実際に処理しているのは半分くらいであり、主なパイプラインストールは命令キャッシュによるものだと考えられます。
• StageFがBUSYの分だけStageD以降がEMPTYとなり、空いています。すなわち約1,100サイクルがパイプラインバブルとなっています。
• Stage1に対してStage2のPIPE処理が半分なのは、ロードストア命令が半分(レジスタとロードストアが1:1)くらいだからかもしれません。
• StageDに対してStage1のPIPE処理が増加しているのは、マルチサイクル命令のためかもしれません。

これだけ見るとかなり効率が悪そうですが、対象がテストプログラムでループが無いため、基本的にキャッシュミスが頻発します。一般のアプリケーションのようにループがあれば、ずっと効率が向上するはずです。

---

前のブログ 次のブログ

Fluteの階層構造

CPUの階層構造を図273.1に示します。5段のパイプラインは図273.1に示すように、"F"(命令Fetchステージ), "D"(命令デコードステージ), "1"(命令実行ステージ), "2"(メモリアクセス、長レインテンシステージ), "3"(ライトバックステージ)とステージ名が付けられています。なぜステージ"1”,"2",...,"5"でないかと言えば、3段パイプラインのPiccoloとステージを共用しているため書かれていました。Piccoloではパイプラインステージは”1", "2", "3"と名付けられており、Fluteでは、Piccoloの"1"を"F", ”Ｄ”, "1"に分解したようです。

図273.1 Flute CPU階層構造

各モジュールがmk〇〇と名付けられているのはBSVのお作法です。モジュールとそのインスタンスは一対nの関係にあり、モジュール名はいわばテンプレート名を意味するため、モジュールからインスタンスがmakeされるということを表しています。例えば上図のmkMMU_Cacheはどちらも同じモジュールですが、それぞれ命令用とデータ用に2個インスタンシエートしています。

キャッシュは上記のように、パラメタライズ可能な命令キャッシュ、データキャッシュの2つがあります。その他に、分岐予測器があります。

---

前のブログ 次のブログ