はじめに
今回は、AtCoder Beginner Contest 466のB問題を、Shrike-LiteのBRAMを利用して実装します。
第9回では、15色分の最大値レジスタを使い回し、同じ入力ストリームを最大7回送ることで、M <= 100の完全制約へ対応しました。
この方法はShrike-Liteの小さな回路規模でも動作しましたが、最大ケースでは約3000byteのSPI転送が必要になり、最大ケースの実行時間は実測で約500msでした。
第10回では、ForgeFPGAに内蔵されているBRAMを利用しやすくするために、bram0_8bit_access.vを作成してテンプレート化しました。
早速、このテンプレートをABC466Bの回答に使ってみましょう。
色番号C_iをそのままBRAMのアドレスとして使い、各アドレスへ色ごとの最大サイズを保存します。
BRAM[C_i] = max(BRAM[C_i], S_i)
100色分の結果をBRAMへ保持できるため、入力ストリームを繰り返し送る必要はありません。
今回の主なテーマは次の三つです。
- 色番号をBRAMアドレスとして使う
- BRAM上の値をread-modify-writeで更新する
- 100色分の結果をBRAMから順番に返信する
MOSIの通信形式など、第9回までに説明した共通部分はそのまま利用し、今回はBRAM利用によって変わる部分を中心に見ていきます。
1. 実装方針
ABC466Bでは、色iごとに、その色のボールの最大サイズを求めます。
今回は、BRAMのアドレスと色番号を次のように対応させます。
BRAMアドレス1 : 色1の最大サイズ
BRAMアドレス2 : 色2の最大サイズ
...
BRAMアドレス100 : 色100の最大サイズ
BRAMアドレス0は使用しません。
第10回で作成したテンプレートは、BRAM0を512 × 8bitとして使用します。
ABC466Bで必要なのはアドレス1～100だけですが、色番号を変換せず、そのままBRAMアドレスとして使えるため、問題の処理を単純に記述できます。
最初にRESETをFPGAに送信してから処理を始めることによって、初期状態を、BRAM全体が0になるようにします。
0 : その色のボールは存在しない
1～100: その色の最大サイズ
RP2040側では、受信値0を問題の出力形式である-1へ変換します。
最大値の更新
各ボールのC_iとS_iを受信したら、次の順番で処理します。
BRAM[C_i]を読み出す
↓
現在値とS_iを比較する
↓
S_iの方が大きい場合だけBRAM[C_i]へ書き戻す
処理内容は次の一式だけです。
BRAM[C_i] = max(BRAM[C_i], S_i)
第9回で必要だった次の仕組みは不要になります。
- 15色分の最大値レジスタ
- 担当色範囲の切り替え
round_nocolor_base- 入力ストリームの再送要求
- 周回番号付きステータス
- 破壊的シフト返信
第9回と今回の違いを整理すると、次のようになります。
| 項目 | 第9回 ストリームループ版 | 第11回 BRAM利用版 |
|---|---|---|
| 最大値の保存先 | 15個のFF | BRAM |
| 一度に保持できる色数 | 15色 | 100色以上 |
| 入力ストリーム | 最大7回送信 | 1回だけ送信 |
| 色番号の扱い | 担当範囲からローカル番号へ変換 | そのままBRAMアドレスに使用 |
| 結果返信 | 15色単位＋周回ステータス | 色1～Mを連続返信 |
| 周回管理 | 必要 | 不要 |
2. RP2040とFPGAの役割分担
今回も、RP2040では問題そのものを解かない方針にします。
RP2040の役割はテストケースをそのままSPIでFPGAに引き渡し、FPGAからの返信に最低限の処理を行い標準出力にprintすることにします。
但しSPI通信の制御や通信エラー検知はRP2040で行う事にします。
| 処理 | 担当 |
|---|---|
| テストケースと期待値を保持する | RP2040 |
M、C_i、S_iをSPIで送信する |
RP2040 |
Mを保持する |
FPGA |
C_iとS_iを受信する |
FPGA |
BRAM[C_i]を読み出す |
FPGA |
現在値とS_iを比較する |
FPGA |
| 必要な場合だけ最大値を書き戻す | FPGA |
BRAMアドレス1～Mを順番に読み出す |
FPGA |
M、最大値、REPLY_DONEを返信する |
FPGA |
FPGAから返信されたMを確認する |
RP2040 |
M個の最大値を受信する |
RP2040 |
受信値0を-1へ変換する |
RP2040 |
受信数とMが一致することを確認する |
RP2040 |
REPLY_DONEを確認する |
RP2040 |
| 受信結果を期待値と比較する | RP2040 |
3. BRAMテンプレートを利用する
第10回で作成したbram0_8bit_access.vは、BRAM固有の制御を問題固有回路から分離するためのモジュールです。
問題固有側からは、次のような一般的な読み書きインターフェイスとして利用できます。
write_req
write_addr
write_data
read_req
read_addr
read_data
read_valid
clear
busy
BRAMのEnableがActive Lowであることや、同期読み出しの待ち時間などは、bram0_8bit_access.v側で処理します。
ABC466B側では、次の処理だけを考えればよくなります。
C_iをread_addrへ設定
read_reqを1クロック出力
read_validを待つ
S_iとread_dataを比較
必要ならwrite_reqを1クロック出力
BRAM制御をテンプレート化したことで、今回の問題固有回路はかなり小さくなります。
RESET時のクリア
ハードウェアリセットとRESETコマンドでは、第10回と同じようにBRAM全体を0でクリアします。
BRAMのクリア中は新しいテストケースを開始せず、クリア完了後にMと入力ストリームを送信します。
4. SPIが遅いためFIFOは不要
BRAMはFFとは異なり、読み出し要求を出してから結果を受け取るまで数クロック待つ必要があります。
そのため、最大値の更新は次のようなread-modify-writeになります。
C_i、S_iを保持
↓
BRAM読み出し要求
↓
read_validを待つ
↓
大小比較
↓
必要ならBRAM書き込み要求
ただし、今回のSPIは1MHzです。SPIで1byteを転送するだけでも約8µsかかります。
それに対し、BRAMへのRead/Write操作はFPGAの50MHzクロックで動作しますので、8usの間に400クロック分の操作ができることになります。
最大値更新の要求が発生するのは、SEND_S_LSBの1byteを受信したときだけです。BRAMの読み出し、比較、必要な場合の書き込みは、次の更新要求が来るまでに十分完了できます。
したがって、次のような仕組みは追加しません。
- SPI受信FIFO
- BRAM更新要求キュー
- 複数要求の並列処理
- FIFOのオーバーフロー管理
今回は、SPI通信の遅さがBRAM制御を単純にしてくれます。
5. SPI通信形式
MOSI
MOSIは第9回と同じCMD 4bit + DATA 4bit形式を使用します。
M、C_i、S_iを上位4bitと下位4bitに分けて送信し、全ボールの送信後にEODを送ります。
Mを送信
N回繰り返し:
C_iを送信
S_iを送信
EOD
Nは送信しません。
MOSIコマンドの割り当ても第9回から変更しません。
MISO
MISOは第9回と同じく、bit7をVALID、bit6～0をPAYLOADとする形式を使用します。
bit7 bit6 bit0
+----+----------------------------+
| 1 | PAYLOAD 7bit |
+----+----------------------------+
返信データは次の順番にします。
M
Smax_1
Smax_2
...
Smax_M
REPLY_DONE
| 返信位置 | 内容 |
|---|---|
| 1byte目 | FPGAが保持しているM
|
2～M+1byte目 |
色1～Mの最大サイズ |
M+2byte目 |
REPLY_DONE |
PAYLOADの割り当ては次のとおりです。
0～100 : Mまたは色ごとの最大サイズ
101 : REPLY_DONE
したがって、実際の返信byteは次のようになります。
M : 0x80 | M
Smax_i : 0x80 | Smax_i
REPLY_DONE : 0xE5
未返信／待機値 : 0x00
最大値のPAYLOADは次の意味を持ちます。
0 : その色のボールは存在しない
1～100: その色の最大サイズ
存在しない色の返信は0x80となるため、未返信や待機状態を表す0x00と区別できます。
先頭でMを返信する理由
RP2040は、送信したMをすでに知っています。
それでもFPGAから最初にMを返信させることで、次の点を確認できます。
- FPGAが正しい
Mを保持している - これから何個の最大値が返されるか分かる
- 受信した最大値の個数と
Mを比較できる - 返信途中の欠落やずれを検出しやすい
Python側では、次の条件をすべて確認します。
返信されたM == 送信したM
最大値の受信数 == M
M個の最大値の直後にREPLY_DONEを受信
6. SPI通信シーケンス
各テストケースでは、次の順番で通信します。
RESET
BRAMクリア完了待ち
Mを2byteで送信
全N個のC_i、S_iを送信
EOD
NOP_RCVでMを受信
NOP_RCVでSmax_1～Smax_Mを受信
NOP_RCVでREPLY_DONEを受信
RESET
BRAMクリア完了待ち
SPIでは送信と受信が同時に行われるため、返信は1byte遅れて見えます。
FPGAは各NOP_RCVの受信完了後に次のBRAMアドレスを読み出し、次回のSPI転送までにtx_dataへ返信値を準備します。
SPIが十分遅いため、BRAMの読み出し待ち時間は次のNOP_RCVが届くまでに吸収できます。
7. FPGA側の実装方針
FPGA側の問題固有処理は、大きく次の二つに分かれます。
入力中の最大値更新
SEND_S_LSBを受信したとき、保存済みのC_iと完成したS_iを使って更新処理を開始します。
IDLE
↓ SEND_S_LSB受信
BRAM[C_i]読み出し要求
↓
read_valid待ち
↓
最大値比較
├─ 更新不要 → IDLE
└─ 更新必要 → 書き込み要求 → IDLE
SPIの次のbyteを受信するまでに処理が完了するため、入力を蓄える必要はありません。
結果の返信
EODを受信したら返信状態へ移ります。
Mを返信
↓
BRAM[1]を返信
↓
BRAM[2]を返信
↓
...
↓
BRAM[M]を返信
↓
REPLY_DONEを返信
返信用アドレスを1からMまで増やしながら、BRAMを順番に読み出します。
EOD受信時にtx_dataへMを設定します。最初のNOP_RCVでMを送信した後、BRAMアドレス1を読み出し、次回のSPI転送までにSmax_1をtx_dataへ設定します。
以降も、各NOP_RCVの受信完了後に次のアドレスを読み出します。これにより、現在送信中のtx_dataをBRAMの読み出し結果で途中上書きすることを避けます。
第9回のような15色単位の破壊的シフトや周回管理は不要です。
bram0_8bit_access.vとの接続
main.vでは、ABC466B固有の制御回路とbram0_8bit_access.vを接続します。
実装時には、主に次の信号を使用します。
| 信号 | 用途 |
|---|---|
clear |
RESET時にBRAM全体を0クリア |
busy |
BRAMアクセス処理中を確認 |
read_req |
最大値または返信データの読み出し要求 |
read_addr |
C_iまたは返信中の色番号 |
read_data |
BRAMから読み出した最大値 |
read_valid |
読み出し結果が有効 |
write_req |
最大値の書き込み要求 |
write_addr |
C_i |
write_data |
新しい最大値S_i
|
8. AIへVerilog実装を依頼する
今回は、第10回で作成したBRAMテンプレートをコピーし、ABC466B用プロジェクトとして整理しました。
AIへ依頼した内容の要点は次のとおりです。
- 第10回のBRAMテンプレートを土台にする
- 変更対象はabc466b_bram/ffpga/src/main.vだけにする
- spi_target.vとbram0_8bit_access.vは変更しない
- MOSI形式とコマンド割り当ては第9回と同じにする
- M、C_i、S_iを上位4bit・下位4bitで受信する
- C_iをそのままBRAMアドレスとして使用する
- SEND_S_LSB受信後にBRAM[C_i]を読み出す
- S_iが現在値より大きい場合だけ書き戻す
- read_valid後はbusy=0を待ってからwrite_reqを出す
- MISOはbit7をVALID、bit6～0をPAYLOADとする
- EOD受信後に0x80 | Mを返信する
- 各NOP_RCVの受信完了後に次のBRAMアドレスを読み出す
- 0x80 | BRAM[1]～0x80 | BRAM[M]を順番に返信する
- 最後にREPLY_DONEとして0xE5を返信する
- SPI受信FIFOは実装しない
- Verilogで実装し、SystemVerilog固有構文は使用しない
- Git操作や対象外ファイルの変更は行わない
AIには、最初に既存ファイルを確認して変更方針だけを提示させました。
方針を確認した後、main.vだけを変更するように指示しました。
実装された問題固有部分は次のとおりです。
// ============================================================
// 問題ごとに変更する部分
// ============================================================
// ABC466Bでは、色番号をBRAMアドレスとして使用し、
// 各アドレスへその色のボールの最大サイズを保存する。
// SEND_S_LSB受信後にread-modify-writeを行い、
// EOD受信後はM、色1～Mの最大値、REPLY_DONEの順に返信する。
// ============================================================
// 第9回と同じ、上位4bitがCMD、下位4bitがDATAのSPIコマンド定義
localparam CMD_NOP_WAIT = 4'h0;
localparam CMD_SET_M_MSB = 4'h1;
localparam CMD_SET_M_LSB = 4'h2;
localparam CMD_SEND_C_MSB = 4'h3;
localparam CMD_SEND_C_LSB = 4'h4;
localparam CMD_SEND_S_MSB = 4'h5;
localparam CMD_SEND_S_LSB = 4'h6;
localparam CMD_EOD = 4'h7;
localparam CMD_NOP_RCV = 4'h8;
localparam CMD_RESET = 4'h9;
localparam CMD_DEBUG = 4'hA;
// MISO返信のbit7はVALID。PAYLOAD 101は全返信完了を表す。
localparam REPLY_DONE = 8'hE5;
// ABC466B全体を制御する小さなFSM。
localparam [3:0] STATE_CLEAR_START = 4'd0;
localparam [3:0] STATE_CLEAR_WAIT = 4'd1;
localparam [3:0] STATE_INPUT = 4'd2;
localparam [3:0] STATE_UPDATE_READ_REQ = 4'd3;
localparam [3:0] STATE_UPDATE_READ_WAIT = 4'd4;
localparam [3:0] STATE_UPDATE_WRITE_REQ = 4'd5;
localparam [3:0] STATE_UPDATE_WRITE_WAIT_BUSY = 4'd6;
localparam [3:0] STATE_UPDATE_WRITE_WAIT_DONE = 4'd7;
localparam [3:0] STATE_REPLY_M_READY = 4'd8;
localparam [3:0] STATE_REPLY_READ_REQ = 4'd9;
localparam [3:0] STATE_REPLY_READ_WAIT = 4'd10;
localparam [3:0] STATE_REPLY_DATA_READY = 4'd11;
localparam [3:0] STATE_REPLY_DONE_READY = 4'd12;
localparam [3:0] STATE_DONE = 4'd13;
wire [3:0] cmd;
wire [3:0] data;
wire [7:0] received_s;
wire cmd_reset_valid;
// M、C_i、S_iを上位・下位4bitから復元するための保持レジスタ。
reg [3:0] m_high;
reg [7:0] current_m;
reg [3:0] c_high;
reg [7:0] current_c;
reg [3:0] s_high;
// SEND_S_LSB受信時の色アドレスとサイズを、更新完了まで保持する。
reg [8:0] update_addr;
reg [7:0] update_size;
// 現在返信中の色番号。1からMまで順番に進める。
reg [7:0] reply_color;
reg [3:0] main_state;
// BRAMアクセス要求、アドレス、書き込みデータと読み出し結果。
reg bram_clear;
reg bram_write_req;
reg bram_read_req;
reg [8:0] bram_access_addr;
reg [7:0] bram_access_write_data;
wire [7:0] bram_access_read_data;
wire bram_access_read_valid;
wire bram_access_busy;
assign cmd = rx_data[7:4];
assign data = rx_data[3:0];
assign received_s = {s_high, data};
assign cmd_reset_valid = rx_data_strobe && (cmd == CMD_RESET);
// 入力受信、最大値のread-modify-write、BRAM返信を一つのFSMで制御する。
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
m_high <= 4'd0;
current_m <= 8'd0;
c_high <= 4'd0;
current_c <= 8'd0;
s_high <= 4'd0;
update_addr <= 9'd0;
update_size <= 8'd0;
reply_color <= 8'd0;
main_state <= STATE_CLEAR_WAIT;
bram_clear <= 1'b0;
bram_write_req <= 1'b0;
bram_read_req <= 1'b0;
bram_access_addr <= 9'd0;
bram_access_write_data <= 8'd0;
tx_data <= 8'h00;
end else begin
// BRAM要求信号は必要な1クロックだけHighにする。
bram_clear <= 1'b0;
bram_write_req <= 1'b0;
bram_read_req <= 1'b0;
// RESETは入力中、BRAMアクセス中、返信中、完了後の全状態で最優先する。
// rx_data_valid_dはここで初期化せず、同じRESET byteの再検出を防ぐ。
if (cmd_reset_valid) begin
m_high <= 4'd0;
current_m <= 8'd0;
c_high <= 4'd0;
current_c <= 8'd0;
s_high <= 4'd0;
update_addr <= 9'd0;
update_size <= 8'd0;
reply_color <= 8'd0;
main_state <= STATE_CLEAR_START;
bram_clear <= 1'b1;
bram_write_req <= 1'b0;
bram_read_req <= 1'b0;
bram_access_addr <= 9'd0;
bram_access_write_data <= 8'd0;
tx_data <= 8'h00;
end else begin
case (main_state)
STATE_CLEAR_START: begin
// clearをBRAM側が受け付ける1クロックを挟んでからbusyを監視する。
main_state <= STATE_CLEAR_WAIT;
end
STATE_CLEAR_WAIT: begin
// ハードウェアリセット後とCMD_RESET後は、全領域のクリア完了を待つ。
if (!bram_access_busy)
main_state <= STATE_INPUT;
end
STATE_INPUT: begin
// 返信中でない場合だけ、通常のMOSIコマンドを処理する。
if (rx_data_strobe) begin
case (cmd)
CMD_SET_M_MSB: begin
// Mの上位4bitを保持する。
m_high <= data;
end
CMD_SET_M_LSB: begin
// 保存済みの上位4bitと結合し、Mを確定する。
current_m <= {m_high, data};
end
CMD_SEND_C_MSB: begin
// C_iの上位4bitを保持する。
c_high <= data;
end
CMD_SEND_C_LSB: begin
// 保存済みの上位4bitと結合し、C_iを確定する。
current_c <= {c_high, data};
end
CMD_SEND_S_MSB: begin
// S_iの上位4bitを保持する。
s_high <= data;
end
CMD_SEND_S_LSB: begin
// C_iをBRAMアドレスとして、完成したS_iの最大値更新を開始する。
update_addr <= {1'b0, current_c};
update_size <= received_s;
bram_access_addr <= {1'b0, current_c};
main_state <= STATE_UPDATE_READ_REQ;
end
CMD_EOD: begin
// 現在の転送終了後、次のNOP_RCVでMを返信できるよう準備する。
tx_data <= {1'b1, current_m[6:0]};
reply_color <= 8'd0;
main_state <= STATE_REPLY_M_READY;
end
default: begin
// NOP_WAIT、NOP_RCV、DEBUG、予約コマンドでは状態を変更しない。
end
endcase
end
end
STATE_UPDATE_READ_REQ: begin
// BRAMがIDLEのときだけ、読み出し要求を1クロック出力する。
if (!bram_access_busy) begin
bram_access_addr <= update_addr;
bram_read_req <= 1'b1;
main_state <= STATE_UPDATE_READ_WAIT;
end
end
STATE_UPDATE_READ_WAIT: begin
// read_validの1クロックで現在値とS_iを比較する。
// この時点ではbusy=1なので、書き込み要求はまだ出さない。
if (bram_access_read_valid) begin
if (update_size > bram_access_read_data) begin
bram_access_write_data <= update_size;
main_state <= STATE_UPDATE_WRITE_REQ;
end else begin
main_state <= STATE_INPUT;
end
end
end
STATE_UPDATE_WRITE_REQ: begin
// 読み出し処理後にbusy=0となり、BRAMがIDLEへ戻るまで待つ。
if (!bram_access_busy) begin
bram_access_addr <= update_addr;
bram_write_req <= 1'b1;
main_state <= STATE_UPDATE_WRITE_WAIT_BUSY;
end
end
STATE_UPDATE_WRITE_WAIT_BUSY: begin
// 書き込み要求が受理され、busy=1になったことを確認する。
if (bram_access_busy)
main_state <= STATE_UPDATE_WRITE_WAIT_DONE;
end
STATE_UPDATE_WRITE_WAIT_DONE: begin
// 書き込み完了でbusy=0へ戻った後、次の入力を受け付ける。
if (!bram_access_busy)
main_state <= STATE_INPUT;
end
STATE_REPLY_M_READY: begin
// 最初のNOP_RCVでは、EOD受信時に準備したMが送信される。
if (rx_data_strobe && (cmd == CMD_NOP_RCV)) begin
reply_color <= 8'd1;
bram_access_addr <= 9'd1;
main_state <= STATE_REPLY_READ_REQ;
end
end
STATE_REPLY_READ_REQ: begin
// 直前の返信送信完了後、次の色をBRAMから読み出す。
if (!bram_access_busy) begin
bram_read_req <= 1'b1;
main_state <= STATE_REPLY_READ_WAIT;
end
end
STATE_REPLY_READ_WAIT: begin
// 次回のNOP_RCVに備え、VALID付き最大サイズをtx_dataへ設定する。
if (bram_access_read_valid) begin
tx_data <= {1'b1, bram_access_read_data[6:0]};
main_state <= STATE_REPLY_DATA_READY;
end
end
STATE_REPLY_DATA_READY: begin
// 現在のNOP_RCVで準備済みの色を送信し、次の返信を準備する。
if (rx_data_strobe && (cmd == CMD_NOP_RCV)) begin
if (reply_color < current_m) begin
reply_color <= reply_color + 8'd1;
bram_access_addr <=
{1'b0, (reply_color + 8'd1)};
main_state <= STATE_REPLY_READ_REQ;
end else begin
// 色Mの送信完了後、次回返信用にREPLY_DONEを設定する。
tx_data <= REPLY_DONE;
main_state <= STATE_REPLY_DONE_READY;
end
end
end
STATE_REPLY_DONE_READY: begin
// REPLY_DONEの送信完了後は待機値へ戻し、RESETだけを待つ。
if (rx_data_strobe && (cmd == CMD_NOP_RCV)) begin
tx_data <= 8'h00;
main_state <= STATE_DONE;
end
end
STATE_DONE: begin
// 全返信完了後は通常コマンドを受け付けず、CMD_RESETを待つ。
end
default: begin
// 不正状態からはBRAM全体をクリアし、入力待ちへ復帰する。
m_high <= 4'd0;
current_m <= 8'd0;
c_high <= 4'd0;
current_c <= 8'd0;
s_high <= 4'd0;
update_addr <= 9'd0;
update_size <= 8'd0;
reply_color <= 8'd0;
main_state <= STATE_CLEAR_START;
bram_clear <= 1'b1;
bram_access_addr <= 9'd0;
bram_access_write_data <= 8'd0;
tx_data <= 8'h00;
end
endcase
end
end
end
最大値更新は、一つのFSMで次の順番に処理します。
SEND_S_LSB受信
→ BRAM読み出し要求
→ read_valid待ち
→ 最大値比較
→ 更新が必要ならbusy=0待ち
→ 書き込み要求
→ busy=1を確認
→ busy=0を確認
→ 入力待ち
返信側も同じFSMで管理します。
M
→ BRAM[1]
→ BRAM[2]
→ ...
→ BRAM[M]
→ REPLY_DONE
15色分のFF配列、範囲判定、周回番号、破壊的シフト返信はすべて不要になりました。
9. AIへMicroPython実装を依頼する
MicroPython側では、第10回のBRAMテンプレートに含まれる次の共通部分をそのまま利用しました。
- Shrike-Liteへのbitstream書き込み
- ハードウェアリセット
- SPI0、1MHz、CPOL=0、CPHA=0の初期化
- CSを手動制御する1byte送受信
- RESET後のBRAMクリア待ち
第9回からは、12件のテストケース、静的な期待値、M、C_i、S_iの送信処理を再利用しました。
一方、次の処理は削除しました。
- 入力ストリームの再送
- 周回番号の管理
- 15色単位の受信
- 周回ステータスの復号
- 最大7周の繰り返し
AIへ依頼した内容の要点は次のとおりです。
- 変更対象はabc466b_bram_test.pyだけにする
- bitstream名をabc466b_bram.binにする
- 入力ストリームは1回だけ送信する
- EOD時のMISO値は破棄する
- NOP_RCVでVALID付きMを受信する
- 返信されたMが送信値と一致した場合だけ後続受信へ進む
- NOP_RCVをM回送り、Smax_1～Smax_Mを受信する
- VALIDとPAYLOAD 0～100を確認する
- PAYLOAD 0を-1へ変換する
- 復号失敗位置にはNoneを残す
- 最後にREPLY_DONE=0xE5を確認する
- RESET後は1ms待ち、NOP_WAITの0x00を確認する
- 第9回と同じ12件を実行し、処理時間とPASS/FAILを表示する
- Git操作や対象外ファイルの変更は行わない
Shrike-Liteへの書き込みやSPI初期化などの共通部分を除く、ABC466B固有部分は次のとおりです。
# ===== ABC466B固有部：SPIコマンドとMISO返信 =====
CMD_NOP_WAIT = 0x0
CMD_SET_M_MSB = 0x1
CMD_SET_M_LSB = 0x2
CMD_SEND_C_MSB = 0x3
CMD_SEND_C_LSB = 0x4
CMD_SEND_S_MSB = 0x5
CMD_SEND_S_LSB = 0x6
CMD_EOD = 0x7
CMD_NOP_RCV = 0x8
CMD_RESET = 0x9
CMD_DEBUG = 0xA
REPLY_DONE = 0xE5
# 第9回の12ケースから周回ステータスだけを除き、静的な期待値を再利用する。
TEST_CASES = [
{
"name": "official_sample_1",
"n": 4,
"m": 5,
"balls": [
(1, 3),
(2, 10),
(1, 7),
(4, 9),
],
"expected": [7, 10, -1, 9, -1],
},
{
"name": "official_sample_2",
"n": 5,
"m": 5,
"balls": [
(2, 6),
(5, 12),
(5, 2),
(5, 9),
(2, 7),
],
"expected": [-1, 7, -1, -1, 12],
},
{
"name": "minimum_values",
"n": 1,
"m": 1,
"balls": [
(1, 1),
],
"expected": [1],
},
{
"name": "maximum_color_and_size",
"n": 1,
"m": 15,
"balls": [
(15, 100),
],
"expected": [
-1, -1, -1, -1, -1,
-1, -1, -1, -1, -1,
-1, -1, -1, -1, 100,
],
},
{
"name": "all_colors_once",
"n": 15,
"m": 15,
"balls": [
(1, 15),
(2, 14),
(3, 13),
(4, 12),
(5, 11),
(6, 10),
(7, 9),
(8, 8),
(9, 7),
(10, 6),
(11, 5),
(12, 4),
(13, 3),
(14, 2),
(15, 1),
],
"expected": [
15, 14, 13, 12, 11,
10, 9, 8, 7, 6,
5, 4, 3, 2, 1,
],
},
{
"name": "repeated_updates_and_missing_color",
"n": 8,
"m": 4,
"balls": [
(2, 100),
(2, 1),
(2, 50),
(4, 99),
(4, 100),
(1, 1),
(1, 100),
(1, 99),
],
"expected": [100, 100, -1, 100],
},
{
"name": "equal_values",
"n": 6,
"m": 5,
"balls": [
(3, 42),
(3, 42),
(3, 1),
(5, 100),
(5, 99),
(2, 7),
],
"expected": [-1, 7, 42, -1, 100],
},
{
"name": "maximum_n_same_color",
"n": 15,
"m": 15,
"balls": [
(8, 1),
(8, 2),
(8, 3),
(8, 4),
(8, 5),
(8, 6),
(8, 7),
(8, 8),
(8, 9),
(8, 10),
(8, 11),
(8, 12),
(8, 13),
(8, 14),
(8, 15),
],
"expected": [
-1, -1, -1, -1, -1,
-1, -1, 15, -1, -1,
-1, -1, -1, -1, -1,
],
},
{
"name": "boundary_m16",
"n": 5,
"m": 16,
"balls": [
(15, 20),
(16, 30),
(15, 100),
(16, 1),
(1, 7),
],
"expected": [7] + [-1] * 13 + [100, 30],
},
{
"name": "boundary_m30",
"n": 3,
"m": 30,
"balls": [
(1, 3),
(16, 16),
(30, 100),
],
"expected": [3] + [-1] * 14 + [16] + [-1] * 13 + [100],
},
{
"name": "boundary_m31",
"n": 3,
"m": 31,
"balls": [
(30, 31),
(31, 30),
(31, 100),
],
"expected": [-1] * 29 + [31, 100],
},
{
"name": "full_n100_m100",
"n": 100,
"m": 100,
"balls": (
[(90, 1)] * 48
+ [(91, 100)] * 50
+ [(90, 100), (100, 99)]
),
"expected": (
[-1] * 89
+ [100, 100]
+ [-1] * 8
+ [99]
),
},
]
# CMDとDATAを上位/下位4bitへ格納し、1byteのMOSIフレームを生成する。
def make_frame(command, data=0):
return ((command & 0x0F) << 4) | (data & 0x0F)
# 8bit値を上位・下位4bitに分け、指定された2コマンドで送信する。
def send_value(msb_command, lsb_command, value):
spi_exchange(make_frame(msb_command, (value >> 4) & 0x0F))
spi_exchange(make_frame(lsb_command, value & 0x0F))
# 全ボールを1回だけ送信し、最後にEODを送る。EOD時のMISO値は使用しない。
def send_stream(balls):
for c, s in balls:
send_value(CMD_SEND_C_MSB, CMD_SEND_C_LSB, c)
send_value(CMD_SEND_S_MSB, CMD_SEND_S_LSB, s)
spi_exchange(make_frame(CMD_EOD))
# VALID付きMを復号し、後続ループに使用できる1～100だけを返す。
def decode_m(rx):
if (rx & 0x80) == 0:
return None
payload = rx & 0x7F
if payload < 1 or payload > 100:
return None
return payload
# VALID付き最大値を復号する。存在しない色のPAYLOAD 0は-1へ変換する。
def decode_value(rx):
if (rx & 0x80) == 0:
return None
payload = rx & 0x7F
if payload > 100:
return None
return -1 if payload == 0 else payload
# M、色1～Mの最大値、REPLY_DONEを、SPIの1byte遅延に合わせて受信する。
def receive_results(expected_m):
m_rx_byte = spi_exchange(make_frame(CMD_NOP_RCV))
m_rx = decode_m(m_rx_byte)
m_ok = m_rx is not None and m_rx == expected_m
values = []
valid_count = 0
done_rx = None
# Mが不正な場合、その値をループ回数に使わず、後続返信も受信しない。
if not m_ok:
return m_rx, values, valid_count, done_rx, m_ok
# 復号失敗もNoneとして格納し、色ごとの受信位置を常に維持する。
for _ in range(expected_m):
received_byte = spi_exchange(make_frame(CMD_NOP_RCV))
value = decode_value(received_byte)
values.append(value)
if value is not None:
valid_count += 1
done_rx = spi_exchange(make_frame(CMD_NOP_RCV))
return m_rx, values, valid_count, done_rx, m_ok
# コマンドリセットを送り、BRAM全領域ゼロクリア後の待機値を確認する。
def reset_to_wait():
spi_exchange(make_frame(CMD_RESET))
time.sleep_ms(1)
return spi_exchange(make_frame(CMD_NOP_WAIT)) == 0x00
def format_optional_integer(value):
if value is None:
return "None"
return str(value)
def format_optional_byte(value):
if value is None:
return "None"
return "0x{:02X}".format(value)
# 1ケースを実行し、MISOプロトコルと静的な期待値をまとめて判定する。
def run_case(case):
start_wait_ok = reset_to_wait()
start_us = time.ticks_us()
send_value(CMD_SET_M_MSB, CMD_SET_M_LSB, case["m"])
send_stream(case["balls"])
m_rx, values, valid_count, done_rx, m_ok = receive_results(case["m"])
end_us = time.ticks_us()
elapsed_us = time.ticks_diff(end_us, start_us)
valid_ok = valid_count == case["m"]
count_ok = valid_count == case["m"]
done_ok = done_rx == REPLY_DONE
result_ok = values == case["expected"]
end_wait_ok = reset_to_wait()
wait_ok = start_wait_ok and end_wait_ok
passed = (
m_ok
and valid_ok
and count_ok
and done_ok
and result_ok
and wait_ok
)
print(
"NAME={} N={} M={} M_RX={} COUNT={} DONE={} RX={} EXPECT={} "
"M_OK={} VALID_OK={} COUNT_OK={} DONE_OK={} WAIT_OK={} {} TIME_US={}".format(
case["name"],
case["n"],
case["m"],
format_optional_integer(m_rx),
valid_count,
format_optional_byte(done_rx),
values,
case["expected"],
1 if m_ok else 0,
1 if valid_ok else 0,
1 if count_ok else 0,
1 if done_ok else 0,
1 if wait_ok else 0,
"PASS" if passed else "FAIL",
elapsed_us
)
)
return passed, elapsed_us
pass_count = 0
fail_count = 0
total_time_us = 0
# 各ケースを個別に保護し、異常時もRESETして次のケースへ進む。
for test_case in TEST_CASES:
try:
passed, elapsed_us = run_case(test_case)
except Exception as e:
passed = False
elapsed_us = 0
exception_wait_ok = False
try:
exception_wait_ok = reset_to_wait()
except Exception:
exception_wait_ok = False
print(
"NAME={} N={} M={} M_RX=None COUNT=0 DONE=None RX=[] EXPECT={} "
"M_OK=0 VALID_OK=0 COUNT_OK=0 DONE_OK=0 WAIT_OK={} FAIL "
"TIME_US=0 ERROR={}".format(
test_case["name"],
test_case["n"],
test_case["m"],
test_case["expected"],
1 if exception_wait_ok else 0,
e
)
)
total_time_us += elapsed_us
if passed:
pass_count += 1
else:
fail_count += 1
print(
"SUMMARY PASS={} FAIL={} TOTAL_TIME_US={}".format(
pass_count,
fail_count,
total_time_us
)
)
FPGAから返信されたMが不正な場合は、その値をループ回数に使わず、テストケースをFAILとしてRESETします。
各最大値の復号に失敗した場合は、RXの対応位置へNoneを残します。これにより、途中の1byteだけが不正だった場合でも、後続の色番号との対応がずれません。
10. プロジェクト構成
今回の主なファイル構成は次のとおりです。
abc466b_bram/
├─ abc466b_bram.ffpga
├─ bitstream/
│ └─ abc466b_bram.bin
├─ ffpga/
│ └─ src/
│ ├─ main.v
│ ├─ spi_target.v
│ └─ bram0_8bit_access.v
└─ firmware/
└─ micropython/
└─ abc466b_bram_test.py
今回変更したのは、次の二つです。
-
main.vの問題固有部分 -
abc466b_bram_test.pyの問題固有部分
次の共通ファイルは、第10回のテンプレートから変更していません。
spi_target.vbram0_8bit_access.v
11. Verilogコードの合成結果
ForgeFPGA Workspaceで合成し、bitstreamを生成しました。
Linter、合成、配置配線はいずれもエラーなしで完了し、bitstreamの生成にも成功しました。
但し、配置配線では、BRAMの読み出し端子などについて、FFをIOB内へ配置できないという警告が複数表示されました。
主な対象は次のとおりです。
bram0_read_data[7:0]spi_miso_enrst_n
ツールは該当するFFをIOBから外し、内部ロジック側へ配置して処理を継続しています。また、clkが専用のクロックバッファを経由していないという警告も表示されました。
いずれもエラーにはならず、bitstreamは正常に生成されました。SPIは1MHzで動作し、BRAMアクセスにも十分な待ち時間を設けているため、まずは実機動作を確認することにします。
リソースレポートは次のとおりでした。
第9回のストリームループ版と比較します。
| Resource | 第9回 ストリームループ版 | 第11回 BRAM利用版 |
|---|---|---|
| LUT5s | 472 | 275 |
| CLB FFs | 182 | 143 |
| CLBs | 101 / 140（72.14%） | 55 / 140（39.29%） |
| 4k BRAMs | 0 | 1 / 8（12.50%） |
BRAMを1個使用する代わりに、CLB使用数は次のように減りました。
101 CLB → 55 CLB
72.14% → 39.29%
CLBは46区画減り、使用数は第9回の約54%になりました。
LUTも472個から275個へ減っています。
第9回では、15色分の最大値レジスタ、範囲判定、周回管理、破壊的シフト返信が必要でした。
今回は、色番号をそのままBRAMアドレスとして使うことで、これらの回路をまとめて削減できました。
12. 実機テスト
第9回で使用した12件のテストケースを、BRAM利用版でも実行しました。
確認した主な内容は次のとおりです。
- 同じ色が複数回登場した場合に最大値だけが残る
- より小さい値ではBRAMが上書きされない
- 登場しない色が
-1として出力される - 色1と色100を正しく読み書きできる
- FPGAから返信された
Mが送信値と一致する - 各返信byteのVALIDが1になっている
- 最大値のPAYLOADが0～100に収まっている
- 最大値をちょうど
M個受信できる - 最後に
REPLY_DONE=0xE5を受信できる - RESET後に前のテストケースの値が残らない
実機テストの結果、12件すべて一度でPASSしました。
長いRXとEXPECTは一部省略しています。
NAME=official_sample_1 N=4 M=5 M_RX=5 COUNT=5 DONE=0xE5 RX=[7, 10, -1, 9, -1] EXPECT=[7, 10, -1, 9, -1] M_OK=1 VALID_OK=1 COUNT_OK=1 DONE_OK=1 WAIT_OK=1 PASS TIME_US=4885
NAME=boundary_m16 N=5 M=16 M_RX=16 COUNT=16 DONE=0xE5 RX=[7, -1, ..., 100, 30] EXPECT=[7, -1, ..., 100, 30] M_OK=1 VALID_OK=1 COUNT_OK=1 DONE_OK=1 WAIT_OK=1 PASS TIME_US=7860
NAME=boundary_m31 N=3 M=31 M_RX=31 COUNT=31 DONE=0xE5 RX=[-1, ..., 31, 100] EXPECT=[-1, ..., 31, 100] M_OK=1 VALID_OK=1 COUNT_OK=1 DONE_OK=1 WAIT_OK=1 PASS TIME_US=9634
NAME=full_n100_m100 N=100 M=100 M_RX=100 COUNT=100 DONE=0xE5 RX=[-1, ..., 100, 100, -1, ..., 99] EXPECT=[-1, ..., 100, 100, -1, ..., 99] M_OK=1 VALID_OK=1 COUNT_OK=1 DONE_OK=1 WAIT_OK=1 PASS TIME_US=90295
SUMMARY PASS=12 FAIL=0 TOTAL_TIME_US=177401
最大ケースでも、色90、色91、色100の値が正しく保存・返信されています。
すべてのケースで次の確認項目が1になりました。
M_OK=1
VALID_OK=1
COUNT_OK=1
DONE_OK=1
WAIT_OK=1
答えが一致しただけでなく、MISOプロトコルとテストケース間のBRAMクリアも正常に動作しています。
13. SPI転送量と処理時間の比較
第9回のストリームループ版では、最大ケースで同じ100個の入力を7回送信しました。
1周:
100個 × 4byte = 400byte
EOD = 1byte
返信受信用 = 16byte
-------------------------
1周 = 417byte
417 × 7 + M送信2byte = 2921byte
今回のBRAM利用版では、入力ストリームを1回だけ送信します。
N=100、M=100の場合は次のとおりです。
M送信 = 2byte
100個 × 4byte = 400byte
EOD = 1byte
MISO返信受信用 = 102byte
--------------------------------
合計 = 505byte
MISO返信の102byteは、次の内訳です。
M = 1byte
Smax_1～Smax_100 = 100byte
REPLY_DONE = 1byte
SPI転送量は次のように減りました。
2921byte → 505byte
約5.8分の1です。
最大ケースの実測時間を比較します。
| 実装 | 最大ケースの処理時間 |
|---|---|
| 第9回 ストリームループ版 | 505264µs |
| 第11回 BRAM利用版 | 90295µs |
処理時間は約5.6分の1になり、約82%減少しました。
約505ms → 約90ms
SPI転送量の減少率と、最大ケースの実測時間の改善率はかなり近い値になりました。
FPGA内部のBRAM読み出しや最大値比較よりも、1byteごとのSPI転送とMicroPython側の処理時間が支配的であることが、今回の結果からも確認できます。
12ケース全体の合計時間も次のように減りました。
620091µs → 177401µs
今回のまとめ
今回は、第10回で作成したBRAMテンプレートをABC466Bへ適用し、完全制約版を実装しました。
主な結果は次のとおりです。
- BRAM0を
512 × 8bitとして使用 - 色番号
C_iをそのままBRAMアドレスに使用 -
BRAM[C_i]とS_iを比較し、最大値だけを書き戻す - 入力ストリームを1回だけ送信
- SPIが十分遅いため受信FIFOは使用しない
- MISOはVALID＋7bit PAYLOAD形式
-
M → Smax_1～Smax_M → REPLY_DONEの順に返信 - 12件の実機テストがすべてPASS
- CLB使用率が72.14%から39.29%へ減少
- 最大ケースが約505msから約90msへ短縮
第9回では、回路資源を節約するために同じ入力を最大7回送信しました。
今回はBRAMへ100色分の結果を保存することで、回路規模、SPI転送量、処理時間のすべてを改善できました。
CLB使用数 : 101 → 55
SPI転送量 : 2921byte → 505byte
処理時間 : 約505ms → 約90ms
第10回でBRAMアクセスをテンプレート化していたため、今回の問題固有処理は、色番号をアドレスとして最大値を更新するだけで実装できました。
BRAMテンプレートを作成した効果を、すぐ次の実装で確認できました。
ちょっとしたメモリがあると、パフォーマンス改善につながることを感じられたのが収穫ですね。
次回
次回の解答実装はお休みして、SPIテンプレートのアップデートを行います。お楽しみに。
前回: Shrike-LiteでAtCoder問題を解く(10)：BRAMテンプレートを作る
次回: Shrike-LiteでAtCoder問題を解く(12) Interlude：受信ストローブを共通化したSPIテンプレートV2を作る