はじめに
前回は、SPIで1byteを受信したことを示すrx_data_strobeを共通化し、SPIテンプレートV2を作成しました。
今回は、そのSPIテンプレートV2をさっそく使って、AtCoder Beginner Contest 467のA問題をShrike-Liteへ実装します。
問題も回路もシンプルですので、今回はテンプレートをコピーして実装し、実機で動作を確認するところまで進めます。
この連載での役割分担と縛り（更新版: メモリに関する項目追加）
第6回の記事でも触れましたが、この連載でのRP2040とFPGAの役割分担を改めて明示しておきます。
第10回でBRAMを利用できるようになりましたので、問題を解くために使用できる記憶領域についても、ここで縛りルールを決めておきましょう。
問題を解くためにRP2040のSRAMを使ってよいか少し悩みましたが、これもShrike-Lite上の資源です。FPGAから発行された読み書きリクエストに従って使用する場合に限り、利用してよいことにします。
以下が、ここからの新しいルールブックです。
この連載では、Shrike-LiteをOut-of-the-box、つまり購入時の構成のまま使用します。
- Shrike-Liteへジャンパケーブル、外付け回路、追加のハードウェアを接続しない
- RP2040とFPGA間の通信には、Shrike-Lite基板上にあらかじめ用意された接続だけを利用する
- 開発は、Thonny／MicroPythonとForgeFPGA Workspaceを用いてできる範囲に限定する
- テストケースはMicroPythonスクリプトへ埋め込み、外部PCからUSBシリアル通信などで逐次入力しない
- RP2040では、入力データの選別、並べ替え、反転など、問題を解くためのデータ変換を行わない
- RP2040側でデータを置き換えてよいのは、固有名詞や
Yes／Noなどを通信用の数値表現へ変換し、また元の表現へ戻す場合だけとする - 問題を解くための記憶領域として、FPGA上のBRAMやRP2040のSRAM上に確保した領域を利用してよい
- RP2040のSRAMを問題を解くための記憶領域として利用する場合は、FPGAが発行する読み書きリクエストに従ってアクセスする
- この場合、読み書きするアドレス、データ、操作内容はFPGA側が指定し、RP2040側では問題の内容に基づいて読み書き対象を選択しない
RP2040が担当するのは、上記の縛りを破らない範囲で、テストケースの保持、FPGAとの通信、FPGAから返された結果と期待値の比較、標準出力へのテスト結果表示などです。
外部PC上のThonnyはプログラムの実行や結果確認に使用しますが、問題データの逐次入力や一時保存には使用しません。
問題を解くための計算や判定、およびRP2040のSRAMへ読み書きする対象の決定は、FPGA側で行います。
ABC467Aの問題
身長H[cm]と体重W[kg]が与えられます。
BMIが25以上ならYes、25未満ならNoを出力する問題です。
制約は次のとおりです。
1 <= H <= 300
1 <= W <= 300
HとWは、どちらも9bitで表現できます。
解法を整数の比較へ変換する
BMIの定義をそのまま使うと、身長をcmからmへ変換したうえで除算を行う必要があります。
今回は、次のように式を変形します。
W / (H / 100)^2 >= 25
10000W >= 25H^2
400W >= H^2
したがって、FPGAでは次の条件だけを判定すれば十分です。
400 * W >= H * H なら Yes
それ以外なら No
最大値は次のようになります。
H^2 <= 300^2 = 90000
400W <= 400*300 = 120000
どちらも17bitに収まります。実装では、演算時のビット幅を明示するため18bitの信号として扱います。
浮動小数点数や除算は使わず、乗算と整数比較だけで実装します。
RP2040とFPGAの役割分担
今回の役割分担は次のようにします。
| 処理 | 担当 |
|---|---|
テストケースからHとWを取り出す |
RP2040 |
| 9bit値を2byteへ分割して送信する | RP2040 |
400W >= H^2を判定する |
FPGA |
| 判定結果を1bitで返す | FPGA |
YesまたはNoへ変換し、期待値と比較する |
RP2040 |
RP2040では問題の判定を行わず、入力値の分割、SPI通信、結果表示だけを担当します。
SPI MOSIのフレーム構成
MOSIは、SPIテンプレートと同じく上位3bitをコマンド、下位5bitをデータとして使用します。
bit 7 bit 5 bit 4 bit 0
+--------------------+----------------------------+
| COMMAND[2:0] | DATA[4:0] |
+--------------------+----------------------------+
HとWは9bitですので、それぞれを上位4bitと下位5bitへ分割します。
1個の9bit値
1byte目：bit8:5
2byte目：bit4:0
HとWを合わせると、入力データの送信は合計4byteです。
今回使用するコマンドは次のとおりです。
| コマンド | 値 | DATAの内容 |
|---|---|---|
NOP |
000 |
00000 |
SEND_H_HI |
001 |
0 + H[8:5]
|
SEND_H_LO |
010 |
H[4:0] |
SEND_W_HI |
011 |
0 + W[8:5]
|
SEND_W_LO |
100 |
W[4:0] |
DEBUG |
110 |
通常処理では未使用 |
RESET |
111 |
00000 |
MicroPython側では、9bit値を次のように分割できます。
upper = (value >> 5) & 0x0F
lower = value & 0x1F
送信byteは、これまでと同じ式で作成します。
tx = (command << 5) | data
SPI MISOのフレーム構成
MISOは、bit7をVALID、bit0をANSWERとして使用します。
bit 7 bit 6 bit 1 bit 0
+--------+----------------------------------+--------+
| VALID | reserved | ANSWER |
+--------+----------------------------------+--------+
| MISO | 意味 |
|---|---|
0x81 |
有効な返信、答えはYes
|
0x80 |
有効な返信、答えはNo
|
0x00 |
有効な返信なし |
SPI通信シーケンス
1ケースの通信は次の順番で行います。
RESET
NOP
SEND_H_HI
SEND_H_LO
SEND_W_HI
SEND_W_LO
NOP ← VALIDとANSWERを読み出す
RESET
NOP
FPGAはSEND_W_LOを受信した時点で、受信中の下位5bitを含むWを使って判定し、MISO送信用の値を準備します。
これにより、その次のNOPで判定結果を読み出せます。
SPIテンプレートV2をコピーする
前回作成したatcoder_spi_template_v2をコピーし、ABC467A用のプロジェクトを作成します。
abc467a/
├── abc467a.ffpga
├── bitstream/
│ └── abc467a.bin
├── ffpga/
│ └── src/
│ ├── main.v
│ └── spi_target.v
└── firmware/
└── micropython/
└── abc467a_test.py
今回、spi_target.vは変更しません。
main.vの問題固有部分では、V2で追加したrx_data_strobeをそのまま使用します。
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
// 初期化
end else if (rx_data_strobe) begin
// 受信した1byteを1回だけ処理
end
end
各問題のmain.vへ受信信号の立上り検出回路を追加する必要はありません。
AIへVerilog実装を依頼する
main.vの実装は、AIへ次のように依頼します。
Shrike-LiteでABC467A - Obesityを実装するため、
atcoder_spi_template_v2のmain.vを元に、
abc467a用のmain.vを作成してください。
spi_target.vは変更しないでください。
Verilogで実装し、SystemVerilog固有構文は使用しないでください。
問題の入力はHとWです。
- 1 <= H <= 300
- 1 <= W <= 300
- Hは9bitで保持する
- Wは上位4bitだけを保持する
判定条件は次のとおりです。
400 * W >= H * H ならANSWER=1
それ以外ならANSWER=0
計算途中の値は18bitで扱ってください。
MOSIはbit7:5をCOMMAND、bit4:0をDATAとします。
コマンド：
- NOP = 3'b000
- SEND_H_HI = 3'b001
- SEND_H_LO = 3'b010
- SEND_W_HI = 3'b011
- SEND_W_LO = 3'b100
- DEBUG = 3'b110
- RESET = 3'b111
受信方法：
- SEND_H_HIのDATA[3:0]をH[8:5]へ保存
- SEND_H_LOのDATA[4:0]をH[4:0]へ保存
- SEND_W_HIのDATA[3:0]をWの上位4bitとして保存
- SEND_W_LOのDATA[4:0]は保存しない
SEND_W_LOを受信したクロックで、保存済みのW上位4bitと
今回受信したDATA[4:0]を組み合わせてWを作り、
判定結果をtx_dataへ保存してください。
MISOは次の形式です。
- bit7: VALID
- bit6:1: 0
- bit0: ANSWER
- Yesは0x81
- Noは0x80
- 有効な返信なしは0x00
RESETではH、Wの上位4bit、tx_dataを0へ初期化してください。
問題固有処理はrx_data_strobeを条件に1回だけ実行してください。
main.vを全文提示してください。
今回も記事とコードの草稿作成にはAIを使用しています。
Verilogコード例(問題固有部分)
// ===== 問題ごとに変更する部分 =====
// ABC467Aでは、HとWをそれぞれ2byteで受信する。
// SEND_W_LOを受信したとき、保存済みの上位4bitと
// 受信中の下位5bitからWを組み立て、浮動小数点演算を使わず、
// 400 * W >= H * Hで肥満かどうかを判定する。
localparam NOP = 3'b000;
localparam SEND_H_HI = 3'b001;
localparam SEND_H_LO = 3'b010;
localparam SEND_W_HI = 3'b011;
localparam SEND_W_LO = 3'b100;
localparam DEBUG = 3'b110;
localparam RESET = 3'b111;
reg [8:0] h;
reg [3:0] w_hi;
wire [8:0] completed_w;
wire [17:0] h_operand;
wire [17:0] w_operand;
wire [17:0] h_squared;
wire [17:0] w_times_400;
// Wの下位5bitは保持せず、今回受信中の下位5bitを使ってWを組み立てる。
assign completed_w = {w_hi, rx_data[4:0]};
assign h_operand = {9'b0, h};
assign w_operand = {9'b0, completed_w};
assign h_squared = h_operand * h_operand;
assign w_times_400 = 18'd400 * w_operand;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
h <= 9'd0;
w_hi <= 4'd0;
tx_data <= 8'h00;
end else if (rx_data_strobe) begin
case (rx_data[7:5])
NOP: begin
tx_data <= 8'h00;
end
SEND_H_HI: begin
h[8:5] <= rx_data[3:0];
end
SEND_H_LO: begin
h[4:0] <= rx_data[4:0];
end
SEND_W_HI: begin
// Wの上位4bitを保存する。
w_hi <= rx_data[3:0];
end
SEND_W_LO: begin
// 保存済みの上位4bitと今回受信した下位5bitを組み合わせて判定する。
// 判定結果は次のSPI通信で返信する。
if (w_times_400 >= h_squared) begin
tx_data <= 8'h81;
end else begin
tx_data <= 8'h80;
end
end
DEBUG: begin
// デバッグコマンドではレジスタを変更しない。
end
RESET: begin
h <= 9'd0;
w_hi <= 4'd0;
tx_data <= 8'h00;
end
default: begin
// 未定義コマンドではレジスタを変更しない。
end
endcase
end
end
AIへMicroPython実装を依頼する
次に、実機テスト用のabc467a_test.pyを作成します。
Shrike-LiteでABC467AをテストするMicroPythonプログラムを作成してください。
atcoder_spi_template_v2_test.pyを参考にして、
abc467a_test.pyを新規作成してください。
bitstream名はabc467a.binです。
SPI設定、ピン設定、FPGAリセット処理、
1byteのSPI送受信処理は既存テンプレートと同じにしてください。
HとWは9bit値として扱い、それぞれ次の2byteへ分割してください。
- 上位byteのDATA：value[8:5]
- 下位byteのDATA：value[4:0]
コマンド：
- NOP = 0b000
- SEND_H_HI = 0b001
- SEND_H_LO = 0b010
- SEND_W_HI = 0b011
- SEND_W_LO = 0b100
- DEBUG = 0b110
- RESET = 0b111
1ケースの通信順序：
1. SEND_H_HI
2. SEND_H_LO
3. SEND_W_HI
4. SEND_W_LO
5. NOPを送信してMISOを受信
6. RESET
7. NOP
MISOはbit7がVALID、bit0がANSWERです。
- 0x81ならYes
- 0x80ならNo
- VALIDが0ならNO_REPLYとしてFAIL
次のテストケースを実行してください。
- (180, 60, "No")
- (182, 188, "Yes")
- (180, 80, "No")
- (180, 81, "Yes")
- (200, 99, "No")
- (200, 100, "Yes")
- (300, 224, "No")
- (300, 225, "Yes")
- (1, 1, "Yes")
- (300, 300, "Yes")
各ケースについてNAME、H、W、TX、RX、VALID、EXPECT、RESULT、
PASSまたはFAIL、処理時間を1行で表示してください。
最後にPASS数、FAIL数、TOTAL、全体の処理時間を1行で表示してください。
1件がFAILになっても残りのテストを続けてください。
MicroPythonコード例 (問題固有部分)
# ===== 問題ごとに変更する部分：ABC467Aの入力と期待値 =====
# HとWをそれぞれ上位4bit、下位5bitに分割してFPGAへ送信する。
# 期待結果はテストケースへあらかじめ埋め込み、
# MicroPython側ではABC467Aの判定を行わない。
# ===== ABC467A固有処理 =====
NOP = 0b000
SEND_H_HI = 0b001
SEND_H_LO = 0b010
SEND_W_HI = 0b011
SEND_W_LO = 0b100
DEBUG = 0b110
RESET = 0b111
# 期待結果はあらかじめ埋め込み、MicroPython側では問題の判定を行わない。
TEST_CASES = [
("case_no_1", 180, 60, "No"),
("case_yes_1", 182, 188, "Yes"),
("boundary_180_below", 180, 80, "No"),
("boundary_180_equal", 180, 81, "Yes"),
("boundary_200_below", 200, 99, "No"),
("boundary_200_equal", 200, 100, "Yes"),
("boundary_300_below", 300, 224, "No"),
("boundary_300_equal", 300, 225, "Yes"),
("minimum_values", 1, 1, "Yes"),
("maximum_values", 300, 300, "Yes"),
]
def make_command(command, data=0):
# DATAは必ず下位5bitへ制限する。
return (command << 5) | (data & 0x1F)
def split_9bit(value):
# 9bit値を上位4bitと下位5bitへ分割する。
return (value >> 5) & 0x0F, value & 0x1F
def decode_reply(rx):
# bit7のVALIDを確認し、bit0のANSWERをYesまたはNoへ変換する。
valid = (rx >> 7) & 0x01
if valid == 0:
return valid, "NO_REPLY"
answer = rx & 0x01
return valid, "Yes" if answer == 1 else "No"
def run_test_case(name, h, w, expected):
h_hi, h_lo = split_9bit(h)
w_hi, w_lo = split_9bit(w)
tx_bytes = [
make_command(SEND_H_HI, h_hi),
make_command(SEND_H_LO, h_lo),
make_command(SEND_W_HI, w_hi),
make_command(SEND_W_LO, w_lo),
]
# SEND_H_HI直前から、結果を受信するNOPの完了までを測定する。
start_us = time.ticks_us()
spi_exchange(tx_bytes[0])
spi_exchange(tx_bytes[1])
spi_exchange(tx_bytes[2])
spi_exchange(tx_bytes[3])
rx = spi_exchange(make_command(NOP))
elapsed_us = time.ticks_diff(time.ticks_us(), start_us)
valid, result = decode_reply(rx)
passed = valid == 1 and result == expected
status = "PASS" if passed else "FAIL"
# 次のテストケースに備えてFPGA側の保持値と返信値を初期化する。
spi_exchange(make_command(RESET))
spi_exchange(make_command(NOP))
tx_text = "[0x{:02X},0x{:02X},0x{:02X},0x{:02X}]".format(
tx_bytes[0],
tx_bytes[1],
tx_bytes[2],
tx_bytes[3]
)
print(
"NAME={} H={} W={} TX={} RX=0x{:02X} VALID={} EXPECT={} "
"RESULT={} {} TIME_US={}".format(
name,
h,
w,
tx_text,
rx,
valid,
expected,
result,
status,
elapsed_us
)
)
return passed
# 最初の通信でFPGA側の保持値と返信値を初期化する。
spi_exchange(make_command(RESET))
spi_exchange(make_command(NOP))
pass_count = 0
total_start_us = time.ticks_us()
for name, h, w, expected in TEST_CASES:
if run_test_case(name, h, w, expected):
pass_count += 1
total_time_us = time.ticks_diff(time.ticks_us(), total_start_us)
fail_count = len(TEST_CASES) - pass_count
print(
"SUMMARY PASS={} FAIL={} TOTAL={} TOTAL_TIME_US={}".format(
pass_count,
fail_count,
len(TEST_CASES),
total_time_us
)
)
Verilogを合成する
main.vを保存したら、ForgeFPGA Workspaceで合成とbitstream生成を行います。
Synthesize
↓
Generate Bitstream
生成したbitstreamは、次の名前へ変更します。
abc467a.bin
合成結果
合成後のリソースレポートは次の通りでした。
18bitの乗算を使用しているため、単純な比較だけを行ったこれまでの問題よりもLUT使用量が増えたようですね。それでもLUT使用率は17.5%で、まだ十分に余裕があります。
実機で動作確認する
abc467a.binとabc467a_test.pyをShrike-Liteへ配置し、Thonnyからテストを実行します。
テスト結果
[shrike_fpga] flashing: abc467a.bin
[shrike_flash] FPGA programming done.
NAME=case_no_1 H=180 W=60 TX=[0x25,0x54,0x61,0x9C] RX=0x80 VALID=1 EXPECT=No RESULT=No PASS TIME_US=796
NAME=case_yes_1 H=182 W=188 TX=[0x25,0x56,0x65,0x9C] RX=0x81 VALID=1 EXPECT=Yes RESULT=Yes PASS TIME_US=902
NAME=boundary_180_below H=180 W=80 TX=[0x25,0x54,0x62,0x90] RX=0x80 VALID=1 EXPECT=No RESULT=No PASS TIME_US=886
NAME=boundary_180_equal H=180 W=81 TX=[0x25,0x54,0x62,0x91] RX=0x81 VALID=1 EXPECT=Yes RESULT=Yes PASS TIME_US=902
NAME=boundary_200_below H=200 W=99 TX=[0x26,0x48,0x63,0x83] RX=0x80 VALID=1 EXPECT=No RESULT=No PASS TIME_US=865
NAME=boundary_200_equal H=200 W=100 TX=[0x26,0x48,0x63,0x84] RX=0x81 VALID=1 EXPECT=Yes RESULT=Yes PASS TIME_US=883
NAME=boundary_300_below H=300 W=224 TX=[0x29,0x4C,0x67,0x80] RX=0x80 VALID=1 EXPECT=No RESULT=No PASS TIME_US=865
NAME=boundary_300_equal H=300 W=225 TX=[0x29,0x4C,0x67,0x81] RX=0x81 VALID=1 EXPECT=Yes RESULT=Yes PASS TIME_US=862
NAME=minimum_values H=1 W=1 TX=[0x20,0x41,0x60,0x81] RX=0x81 VALID=1 EXPECT=Yes RESULT=Yes PASS TIME_US=882
NAME=maximum_values H=300 W=300 TX=[0x29,0x4C,0x69,0x8C] RX=0x81 VALID=1 EXPECT=Yes RESULT=Yes PASS TIME_US=887
SUMMARY PASS=10 FAIL=0 TOTAL=10 TOTAL_TIME_US=33591
1ケースあたり、およそ0.9msでPASSしています。ACですね。
今回のまとめ
今回は、前回作成したSPIテンプレートV2をコピーし、ABC467Aを実装しました。
ABC467Aの判定式は、浮動小数点数や除算を使わず、次の整数比較へ変換できます。
400 * W >= H * H
また、9bitのHとWは、それぞれ上位4bitと下位5bitの2byteに分けて送信しました。
問題固有処理では、V2で共通化したrx_data_strobeをそのまま利用できます。テンプレート側の受信ストローブ生成処理を意識せず、入力の組み立てと判定処理に集中できました。
次回
次回から、ABC467Cの実装に取り組む予定です。お楽しみに。
前回：Shrike-LiteでAtCoder問題を解く(12) Interlude：受信ストローブを共通化したSPIテンプレートV2を作る
次回：Shrike-LiteでAtCoder問題を解く(14)：ABC467C Naive実装編（準備中）