はじめに
今回は、AtCoder Beginner Contest 466のB問題をShrike-Liteへ実装します。
この問題では、色ごとにボールの大きさの最大値を求めます。ということは、素朴に実装するとFPGAに「色ごとの最大値」を記憶しておく必要があります。
S_iの最大値は100ですから、1色あたり7bitのデータをFPGAに保持させておく必要があります。
しかしForgeFPGAには、レジスタなどの値を保持するCLB FFが1120個しかありません。
問題の制約は M <= 100ですから、FFに最大値を記憶させておくだけで 100 x 7 = 700個のFFを必要とします。
さらに比較回路やSPI制御にも回路資源が必要になるため、最初から M <= 100 を目指すのはなかなかキビしいかな、と感じます。
そこで今回は、まず次の制約版を実装してみたうえで、合成時のリソース消費量を確認してみる方針にします。
N < 16
M < 16
S_i <= 100
15色分の最大値を7bitレジスタへ保持し、色ごとの比較回路をgenerateで生成します。
返信時は、最大値レジスタ配列そのものを破壊的にシフトし、色1から順番に結果を返します。
今回の主なテーマは次の三つです。
-
generateを使って色ごとの最大値更新回路を並べる - 最大値レジスタ配列を破壊的にシフトして返信する
-
rx_data_validを1byteにつき1回の処理イベントへ変換する
前回までに作成したSPI通信テンプレートを利用し、問題固有部分を中心に整理します。
1. 問題の解法
N個のボールがあり、i番目のボールには色C_iと大きさS_iが与えられます。
色kについて、その色のボールの大きさの最大値を求めます。
max_size[k] = 色kのボールの大きさの最大値
色kのボールが存在しない場合は-1を出力します。
ソフトウェアであれば、色ごとの最大値を配列へ保持しながら入力を順番に処理すれば解けます。
max_size[C_i] = max(max_size[C_i], S_i)
FPGA側でも同じ考え方を使います。
今回は最大15色なので、色ごとに最大値レジスタを1個ずつ持ちます。
色1用最大値レジスタ
色2用最大値レジスタ
...
色15用最大値レジスタ
S_iの範囲は1～100なので7bitで表現できます。
15色 × 7bit = 105bit
各最大値レジスタの初期値は0とします。
S_iに0は存在しないため、レジスタ値0を「その色のボールはまだ存在しない」という意味に利用できます。
0 : その色のボールは存在しない
1～100: その色の最大サイズ
FPGAから0が返ってきた場合、RP2040側で-1へ変換します。
2. RP2040とFPGAの役割分担
今回の役割分担は次のとおりです。
| 処理 | 担当 |
|---|---|
テストケースのN、M、C_i、S_iを保持する |
RP2040 |
C_iとS_iをSPIフレームへ変換する |
RP2040 |
| 入力データを順番に送信する | RP2040 |
入力ストリームの終了をEODで通知する |
RP2040 |
| 色ごとの最大値を判定する | FPGA |
| 色ごとの最大値をレジスタへ保持する | FPGA |
| 色1から順番に結果を返す | FPGA |
返信値0を-1へ変換する |
RP2040 |
| 期待値との比較、表示、時間測定を行う | RP2040 |
NとMはFPGAへ送りません。
FPGAはEODを受信するまで、C_iとS_iの組を順番に処理します。
返信数はRP2040がMから判断します。
EOD送信後に、NOP_RCVをM回送る
RP2040はデータの整形、管理、送受信回数の制御を行いますが、色ごとの最大値は判断しません。
3. MOSIフレーム形式
MOSIは1byteを次のように分割します。
bit 7 bit 5 bit 4 bit 3 bit 0
+-----------------+-----+-------------------------------+
| CMD[2:0] | AUX | DATA[3:0] |
+-----------------+-----+-------------------------------+
| bit | 名前 | 内容 |
|---|---|---|
| 7～5 | CMD |
コマンド |
| 4 | AUX |
コマンドごとの補助bit |
| 3～0 | DATA |
4bitデータ |
今回使用するコマンドは次のとおりです。
| コマンド | CMD | 用途 |
|---|---|---|
NOP_WAIT |
000 |
RESET後のWAIT確認 |
SEND_C |
001 |
色C_iを送る |
SEND_S_MSB |
010 |
大きさS_iの上位3bitを送る |
SEND_S_LSB |
011 |
大きさS_iの下位4bitを送り、値を確定する |
EOD |
100 |
入力ストリームの終了、返信フェーズへ移行 |
NOP_RCV |
101 |
返信データを1byte受信する |
DEBUG |
110 |
デバッグ用 |
RESET |
111 |
内部状態を初期化する |
コマンドだけを送る場合、AUXとDATAは0とします。
| コマンド | 送信byte |
|---|---|
NOP_WAIT |
0x00 |
EOD |
0x80 |
NOP_RCV |
0xA0 |
DEBUG |
0xC0 |
RESET |
0xE0 |
SEND_S_MSBとSEND_S_LSBでは、AUXは0固定とします。
NOP_RCVの下位5bitは今回は使用しません。
返信シーケンス番号を含める方法も考えられますが、初版ではRP2040が送信回数を管理し、各返信のREPLY_VALIDだけを確認します。
4. C_iの送信形式
C_iは1byteで送ります。
CMD = SEND_C
AUX = C_i[4]
DATA = C_i[3:0]
FPGA側では次のように5bitへ戻します。
C_i = {AUX, DATA[3:0]}
今回のM < 16ではAUX=0です。
ただし、AUXまで利用すれば0～31を表現できるため、将来30色程度まで拡張する場合もMOSI形式を変更せずに済みます。
たとえば、C_i=13は次の1byteになります。
CMD = 001
AUX = 0
DATA = 1101
0010_1101 = 0x2D
5. S_iの送信形式
S_iの範囲は1～100なので7bit必要です。
MOSIのDATAは4bitなので、上位側と下位側の2byteに分割します。
今回はAUXで上位・下位を識別せず、SEND_S_MSBとSEND_S_LSBを独立したコマンドにします。
3bitのCMDを8種類すべて使用しますが、FPGA側ではコマンドだけを見て処理を分岐できるため、実装が単純になります。
上位側
CMD = SEND_S_MSB
AUX = 0
DATA = {1'b0, S_i[6:4]}
S_i[6:4]は3bitなので、DATA[3]には0を入れます。
下位側
CMD = SEND_S_LSB
AUX = 0
DATA = S_i[3:0]
上位側と下位側は、それぞれ独立したコマンドで識別します。
SEND_S_LSBを受信したこと自体が、1個のS_iが完成したことを示します。
たとえば、S_i=100は7bitで次の値です。
100 = 110_0100
送信byteは次のようになります。
上位側:
CMD = 010
AUX = 0
DATA = 0110
0100_0110 = 0x46
下位側:
CMD = 011
AUX = 0
DATA = 0100
0110_0100 = 0x64
FPGA側では、上位側のS_i[6:4]だけを3bitレジスタへ保存します。
下位側を受信したクロックでは、保存済みの上位3bitと今回受信した下位4bitをwireで結合します。
received_s = {s_high[2:0], DATA[3:0]}
完成したS_iを別のレジスタへいったん保存せず、このreceived_sを比較と最大値更新へ直接使用します。
6. MISOの返信形式
MISOは1回のSPI通信で次の1byteを返信します。
bit 7 bit 6 bit 0
+--------+---------------------------------------------+
| VALID | MAX_SIZE[6:0] |
+--------+---------------------------------------------+
| bit | 名前 | 内容 |
|---|---|---|
| 7 | REPLY_VALID |
有効な返信なら1
|
| 6～0 | MAX_SIZE |
色ごとの最大サイズ |
返信値の意味は次のとおりです。
| MISO | 意味 |
|---|---|
0x00 |
有効な返信なし |
0x80 |
有効な返信、その色のボールは存在しない |
0x81～0xE4
|
有効な返信、最大サイズ1～100 |
FPGAは色番号を返信しません。
返信は必ず色1、色2、…、色Mの順番で行います。
RP2040に何回目の返信かを管理してもらうことによって、返信順から色番号を判断できます。
1回目の返信 = 色1
2回目の返信 = 色2
...
M回目の返信 = 色M
MAX_SIZE=0を受信した場合、RP2040側で-1へ変換します。
7. 処理シーケンス
ABC466Bでは、入力ストリームの最後まで処理しなければ、回答が確定しません。
そこで、次の順番で処理を行います。
データ受信 → EOD → 回答返信 → RESET → WAIT
受信フェーズ
C_i、S_iを受信
色ごとの最大値を更新
EOD
入力終了
色1をtx_dataへ準備
max_s配列を1段だけシフト
返信フェーズへ移行
返信フェーズ
NOP_RCVごとに次の色の値をtx_dataへ準備
max_s配列を1段だけシフト
RESET
全状態を初期化
SEND_C、SEND_S_MSB、SEND_S_LSBは受信フェーズだけで処理し、NOP_RCVは返信フェーズだけで処理します。
8. rx_data_validを1クロックパルスへ変換する
この処理シーケンスでは、EODやNOP_RCVを受信するたびに、返信フェーズへの移行や配列のシフトを1回だけ実行する必要があります。
しかし、公式spi_target.vのrx_data_validは、1byteの受信後に複数クロックHighを維持します。
そのままコマンド処理の条件にすると、1回受信したEODやNOP_RCVに対して、返信フェーズへの移行や配列のシフトが複数回実行されます。
そこでmain.vでは、rx_data_validの立上りを検出し、1byteの受信につき1クロックだけHighになるrx_data_strobeを生成します。
reg rx_data_valid_d;
wire rx_data_strobe;
assign rx_data_strobe = rx_data_valid && !rx_data_valid_d;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
rx_data_valid_d <= 1'b0;
end else begin
rx_data_valid_d <= rx_data_valid;
end
end
rx_data_valid
受信データが有効な期間を示すレベル信号
rx_data_strobe
新しい1byteを受信した瞬間だけHighになる1クロックパルス
今後、SPI通信1byteあたり1回だけ実行する処理は、rx_data_validではなくrx_data_strobeを条件にします。
これにより余計なトラブルを避けられるだけでなく、1byteの受信を契機とする処理が明確になり、コード全体の見通しが良くなる効果も得られそうです。
今回は次の処理をrx_data_strobeを条件にして実行します。
- コマンド処理
-
RESETコマンド - 最大値更新
-
EODによる返信開始 -
NOP_RCVによる返信シフト
9. SPI通信シーケンス
SPIではMOSI送信とMISO受信が同時に行われます。
FPGAが受信したコマンドを処理してtx_dataを更新した場合、その値をRP2040が受け取れるのは次のSPI転送です。
各テストケースは次の順番で処理します。
RESET
NOP_WAIT
C_1
S_1上位（SEND_S_MSB）
S_1下位（SEND_S_LSB）
...
C_N
S_N上位
S_N下位
EOD
NOP_RCV × M
RESET
NOP_WAIT
EODを受信すると、rx_data_validが立ち上がります。
main.vでは、その立上りを検出してrx_data_strobeを1クロックだけHighにし、次の二つを同じ内部クロックで行います。
tx_data ← {1'b1, max_s[0]}
max_s配列を1段シフト
ノンブロッキング代入なので、tx_dataにはシフト前の色1が入り、配列は次の状態として色2を先頭へ移します。
続く最初のNOP_RCVでRP2040が色1を受信します。
そのNOP_RCVに対応するrx_data_strobeで、FPGAは色2をtx_dataへ準備し、配列をもう1段シフトします。
最終結果を受信した後は、前回までと同様に次の流れでWAIT状態へ戻します。
RESET → NOP_WAIT
10. FPGA側の最大値更新
FPGA側では、色ごとに7bitの最大値レジスタを持ちます。
概念的には次の配列です。
reg [6:0] max_s [0:14];
色1をmax_s[0]、色15をmax_s[14]へ対応させます。
色ごとの回路はgenerateで生成します。
genvar i;
generate
for (i = 0; i < 15; i = i + 1) begin : GEN_MAX_S
// 色ごとの最大値更新回路
end
endgenerate
SEND_S_LSBを受信したクロックで、完成したreceived_sを使用します。
各生成ブロックの更新条件は概念的に次のとおりです。
受信フェーズ
かつ
CMD == SEND_S_LSB
かつ
current_c == i + 1
かつ
received_s > max_s[i]
条件を満たしたレジスタだけをreceived_sで更新します。
max_s[i] <= received_s
比較されるmax_s[i]はクロック直前の値です。
ノンブロッキング代入を使うことで、現在値と受信値を比較し、次の状態として新しい最大値を保存できます。
received_sは、保存済みの上位3bitと、今回受信した下位4bitをwireで結合して作ります。
wire [6:0] received_s;
assign received_s = {s_high[2:0], data[3:0]};
このreceived_sを、そのまま最大値の比較に使用します。
下位4bitをいったんレジスタへ保存すると、そのクロックではまだ保存後の値を使用できません。完成したS_iを比較に使うには、もう1クロック待つための仕組みが必要になり、実装が複雑になります。
そこで今回は、受信した下位4bitをレジスタへ保存せず、wireで結合したreceived_sを直接比較回路へ渡します。
11. 最大値レジスタ配列の破壊的シフト
今回の実装では返信する値をmax_s[0]に固定したうえで、max_sのレジスタ列そのものを返信ごとにシフトさせる方法を試します。
max_s[0] ← max_s[1]
max_s[1] ← max_s[2]
...
max_s[13] ← max_s[14]
max_s[14] ← 0
EOD受信時
tx_data ← {1'b1, max_s[0]}
max_s配列を1段シフト
reply_mode ← 1
NOP_RCV受信時
現在のtx_dataをMISOで返信
tx_data ← {1'b1, max_s[0]}
max_s配列を1段シフト
ノンブロッキング代入を使うため、tx_dataにはシフト前のmax_s[0]が入り、max_sには1段シフトした次の状態が保存されます。
12. FPGA側の内部レジスタ
最終版で使用する主なレジスタは次のとおりです。
| レジスタ | bit数 | 用途 |
|---|---|---|
current_c |
5 | 直前に受信した色 |
s_high |
3 |
S_i[6:4]を保持 |
reply_mode |
1 | 受信フェーズと返信フェーズの識別 |
max_s[0:14] |
105 | 色1～15の最大サイズと返信用シフト列 |
rx_data_valid_d |
1 | 1クロック前のrx_data_valid
|
tx_data |
8 | 次回SPI転送で返すデータ |
このうち、rx_data_valid_dは外部リセットでは0へ初期化しますが、RESETコマンドでは初期化しません。
RESETコマンドの受信後もrx_data_validがHighを維持している間にrx_data_valid_dだけを0へ戻すと、次のクロックで同じRESETコマンドを新たな立上りとして検出してしまうためです。
13. MicroPython側の実装方針
MicroPythonファイル名はabc466b_restricted_test.py、bitstream名はabc466b_restricted.binとします。
SPIの初期化、ピン設定、周波数、CPOL、CPHA、FPGAリセット、1byte送受信処理は既存テンプレートをそのまま使用します。
各テストケースでは次の処理を行います。
-
RESETを送る -
NOP_WAITを送り、0x00を確認する - 各ボールについて
SEND_Cを送る -
SEND_S_MSBを送る -
SEND_S_LSBを送る - 全ボール送信後に
EODを送る -
NOP_RCVをM回送り、色1～Mの返信を受け取る - 各返信の
REPLY_VALIDを確認する -
MAX_SIZE=0を-1へ変換する - 期待値と比較する
-
RESET、NOP_WAITでWAIT状態へ戻す
RP2040側では、色ごとの最大値を計算しません。
期待値はテストケースへあらかじめ記載し、FPGAから受信した結果との比較だけを行います。
MOSIフレーム生成
def make_frame(command, aux=0, data=0):
return (
((command & 0x07) << 5)
| ((aux & 0x01) << 4)
| (data & 0x0F)
)
C_iの送信
tx_c = make_frame(
SEND_C,
(c >> 4) & 0x01,
c & 0x0F,
)
S_iの送信
tx_s_high = make_frame(
SEND_S_MSB,
0,
(s >> 4) & 0x07,
)
tx_s_low = make_frame(
SEND_S_LSB,
0,
s & 0x0F,
)
MISOの変換
def decode_reply(rx):
valid = (rx >> 7) & 0x01
value = rx & 0x7F
if not valid:
return None
if value == 0:
return -1
return value
14. テストケース
ABC466Bの公式入力例2件に加え、今回の縮小制約における境界値や、最大値更新、存在しない色、破壊的シフトを確認するテストケースを用意します。
主な確認項目は次のとおりです。
-
N=1、M=1の最小構成 - 色15、大きさ100の最大値
- 15色すべてへの入力と返信
- 同じ色に対する複数回の最大値更新
- ボールが存在しない色の返信
- 同じ大きさを複数回受信した場合
-
N=15で同じ色だけを繰り返す場合
各ケースについて、次の情報を1行程度で表示します。
- テストケース名
NM- FPGAから受信した結果
- 期待結果
-
REPLY_VALIDとWAIT状態の確認結果 - PASSまたはFAIL
- 概算処理時間
1件がFAILになっても、残りのテストケースは継続して実行します。
具体的なテストケースは、後掲のabc466b_restricted_test.pyを見てください。
テンプレートからABC466B制約版用プロジェクトを作る
前回と同様に、atcoder_spi_templateをコピーしてABC466B制約版用プロジェクトを作ります。
主なファイル構成は次のとおりです。
abc466b_restricted/
├─ abc466b_restricted.ffpga
├─ bitstream/
│ └─ abc466b_restricted.bin
├─ ffpga/
│ └─ src/
│ ├─ main.v
│ └─ spi_target.v
└─ firmware/
└─ micropython/
└─ abc466b_restricted_test.py
テンプレートの.ffpgaファイルをabc466b_restricted.ffpgaへリネームします。
問題固有部分は、main.vのコマンド処理、最大値レジスタ、返信シフト処理と、abc466b_restricted_test.pyのテスト・通信処理です。
spi_target.vとMicroPython側のShrike-Lite共通処理は変更しません。
AIへVerilog実装を依頼する
Shrike-LiteでABC466B - Representative Ballsの制約版を実装するため、
既存の atcoder_spi_template の main.v を参考にして、
abc466b_restricted用の main.v を作成してください。
今回は次の制約だけを対象とします。
- N < 16
- M < 16
- 1 <= C_i <= M
- 1 <= S_i <= 100
spi_target.v、abc466b_restricted.ffpga、MicroPythonファイルは変更しないでください。
Verilogで実装し、SystemVerilog固有構文は使用しないでください。
MOSIは次の1byte構成です。
- bit7:5 = CMD
- bit4 = AUX
- bit3:0 = DATA
コマンド：
- NOP_WAIT = 3'b000
- SEND_C = 3'b001
- SEND_S_MSB = 3'b010
- SEND_S_LSB = 3'b011
- EOD = 3'b100
- NOP_RCV = 3'b101
- DEBUG = 3'b110
- RESET = 3'b111
SEND_Cでは、C_iを次の形で受信します。
- AUX = C_i[4]
- DATA = C_i[3:0]
current_cは5bitレジスタへ保存してください。
SEND_S_MSBでは、S_iの上位3bitを送信します。
- AUX = 0
- DATA = {1'b0, S_i[6:4]}
- S_i[6:4]を3bitレジスタs_highへ保存
SEND_S_LSBでは、S_iの下位4bitを送信します。
- AUX = 0
- DATA = S_i[3:0]
SEND_S_LSBを受信したクロックでは、
wire [6:0] received_s = {s_high[2:0], DATA[3:0]}
を使用し、別の完成値レジスタは作らないでください。
色1～15について、7bitの最大値レジスタを15個持たせてください。
初期値はすべて0です。
reg [6:0] max_s [0:14] の配列とgenerateを使用し、
各色の最大値更新回路を生成してください。
受信フェーズでSEND_S_LSBを受信したとき、
current_cが自分の色と一致し、
received_sが現在のmax_sより大きければ更新してください。
受信フェーズと返信フェーズをreply_modeで分離してください。
EOD受信時に、次の処理を同じクロックで行ってください。
- tx_dataへ{1'b1, max_s[0]}を設定
- max_s配列を1段破壊的にシフト
- max_s[14]へ0を設定
- reply_modeを1へ設定
返信フェーズではNOP_RCVを受信するたびに、
次の返信値をtx_dataへ設定し、
max_s配列を1段破壊的にシフトしてください。
SPIの1byte遅延を利用し、
最初のNOP_RCVで色1、その後は色2、色3の順に返信します。
返信中にSEND_C、SEND_S_MSB、SEND_S_LSBは処理しません。
受信中にNOP_RCVは処理しません。
MISO形式：
- bit7 = REPLY_VALID
- bit6:0 = MAX_SIZE
MAX_SIZE=0は、その色のボールが存在しないことを表します。
RESETは受信・返信どちらのフェーズでも受け付け、
current_c、s_high、reply_mode、tx_data、
15個のmax_sをすべて初期化してください。
各max_s要素は一つのalwaysブロックだけから更新してください。
優先順位は次の順にしてください。
1. 外部リセットまたはRESETコマンド
2. EODまたは返信中NOP_RCVによるシフト
3. 受信中SEND_S_LSBによる最大値更新
4. 保持
大きな出力選択MUXやreply_indexによる配列参照は使用せず、
返信は破壊的レジスタシフトで実装してください。
spi_target.vのrx_data_validは1クロックパルスではなく、
複数クロックHighを維持するレベル信号です。
main.v側にrx_data_valid_dを追加し、
rx_data_validの立上りだけで1クロックHighになる
rx_data_strobeを生成してください。
コマンド処理、RESETコマンド、SEND_S_LSBによる最大値更新、
EODおよびNOP_RCVによるシフトは、
rx_data_validではなくrx_data_strobeを条件にしてください。
rx_data_valid_dは外部リセットで0へ初期化してください。
RESETコマンドではrx_data_valid_dを0へ戻さないでください。
既存テンプレートのSPIインターフェイス名とリセット方式は維持してください。
完成したVerilogコード
main.vの問題固有部分です。SPI通信に関係する設定などは既存コードをそのまま利用できます。
spi_target.vも既存のテンプレートファイルをそのまま利用します。
// ============================================================
// ABC466B - Representative Balls 制約版の問題固有回路
//
// 対象制約:
// 1 <= C_i <= 15
// 1 <= S_i <= 100
//
// clk、rst_n、rx_data、rx_data_valid、tx_dataは、
// 既存のSPIテンプレート側で宣言されているものを使用する。
// ============================================================
// 受信した1byteをコマンド、補助bit、データへ分解する。
wire [2:0] cmd;
wire aux;
wire [3:0] data;
// 保存済みのS_i上位3bitと、今回受信した下位4bitを結合した値。
wire [6:0] received_s;
// 1byteの受信を1回の処理イベントへ変換するための信号。
reg rx_data_valid_d;
wire rx_data_strobe;
// RESETコマンドと返信シフトの実行条件。
wire cmd_reset_valid;
wire shift_reply;
// 直前に受信した色番号。
reg [4:0] current_c;
// S_iの上位3bit。
reg [2:0] s_high;
// 0: 受信フェーズ
// 1: 返信フェーズ
reg reply_mode;
// 色1～15の最大サイズを保持する。
//
// 受信フェーズでは最大値レジスタとして使用し、
// 返信フェーズでは破壊的にシフトする。
reg [6:0] max_s [0:14];
// ============================================================
// MOSIコマンド
// ============================================================
localparam CMD_NOP_WAIT = 3'b000;
localparam CMD_SEND_C = 3'b001;
localparam CMD_SEND_S_MSB = 3'b010;
localparam CMD_SEND_S_LSB = 3'b011;
localparam CMD_EOD = 3'b100;
localparam CMD_NOP_RCV = 3'b101;
localparam CMD_DEBUG = 3'b110;
localparam CMD_RESET = 3'b111;
// ============================================================
// MOSIフレームの分解
// ============================================================
assign cmd = rx_data[7:5];
assign aux = rx_data[4];
assign data = rx_data[3:0];
// SEND_S_LSB受信時は、保存済みの上位3bitと
// 今回受信した下位4bitを直接結合して比較に使用する。
assign received_s = {s_high[2:0], data[3:0]};
// ============================================================
// rx_data_validの立上り検出
// ============================================================
// spi_targetのrx_data_validは、1byte受信後も
// SSが解除されるか、次のbyteの最初のサンプリングエッジまで
// 複数クロックHighを維持する。
//
// そのままシフト処理の条件にすると、1回のNOP_RCVで
// max_sが複数段シフトするため、立上りだけを取り出す。
assign rx_data_strobe = rx_data_valid && !rx_data_valid_d;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
rx_data_valid_d <= 1'b0;
end else begin
rx_data_valid_d <= rx_data_valid;
end
end
// rx_data_valid_dはRESETコマンドでは初期化しない。
//
// RESETコマンド受信中にrx_data_valid_dだけを0へ戻すと、
// rx_data_validがHighのままなので、同じRESET byteを
// 次のクロックでも立上りとして検出してしまう。
// ============================================================
// コマンドイベントの生成
// ============================================================
// RESETは受信フェーズと返信フェーズのどちらでも受け付ける。
assign cmd_reset_valid =
rx_data_strobe && (cmd == CMD_RESET);
// EOD受信時と、返信フェーズ中のNOP_RCV受信時に、
// max_s配列を1段シフトする。
assign shift_reply =
rx_data_strobe &&
(((reply_mode == 1'b0) && (cmd == CMD_EOD)) ||
((reply_mode == 1'b1) && (cmd == CMD_NOP_RCV)));
// ============================================================
// 受信・返信フェーズの制御
// ============================================================
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
current_c <= 5'd0;
s_high <= 3'd0;
reply_mode <= 1'b0;
tx_data <= 8'h00;
end else if (cmd_reset_valid) begin
// RESETコマンドでWAIT状態へ戻す。
current_c <= 5'd0;
s_high <= 3'd0;
reply_mode <= 1'b0;
tx_data <= 8'h00;
end else if (rx_data_strobe) begin
if (reply_mode == 1'b0) begin
// ----------------------------
// 受信フェーズ
// ----------------------------
case (cmd)
CMD_SEND_C: begin
// 色番号C_iを保持する。
current_c <= {aux, data};
end
CMD_SEND_S_MSB: begin
// S_iの上位3bitを保持する。
s_high <= data[2:0];
end
CMD_EOD: begin
// 色1の値を次回のSPI返信用に準備し、
// 返信フェーズへ移行する。
//
// 同じクロックでmax_sもシフトされるが、
// ノンブロッキング代入なので、ここでは
// シフト前のmax_s[0]が参照される。
reply_mode <= 1'b1;
tx_data <= {1'b1, max_s[0]};
end
default: begin
// NOP_WAIT、SEND_S_LSB、NOP_RCV、DEBUGは
// このalwaysブロックでは状態を変更しない。
//
// SEND_S_LSBによる最大値更新は、
// 後段のgenerateブロックで行う。
end
endcase
end else begin
// ----------------------------
// 返信フェーズ
// ----------------------------
case (cmd)
CMD_NOP_RCV: begin
// 現在のSPI転送では、更新前のtx_dataが返信される。
//
// ここでは、シフト前のmax_s[0]を
// 次回のSPI返信用としてtx_dataへ準備する。
tx_data <= {1'b1, max_s[0]};
end
default: begin
// 返信中はNOP_RCVとRESET以外を処理しない。
end
endcase
end
end
end
// ============================================================
// 色ごとの最大値更新と破壊的シフト
// ============================================================
genvar i;
generate
// max_s[0]～max_s[13]
//
// 返信時には、後ろの要素を現在の要素へ移動する。
for (i = 0; i < 14; i = i + 1) begin : gen_max_s
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
max_s[i] <= 7'd0;
end else if (cmd_reset_valid) begin
max_s[i] <= 7'd0;
end else if (shift_reply) begin
// 次の色の最大値を1段前へ移動する。
max_s[i] <= max_s[i + 1];
end else if ((reply_mode == 1'b0) &&
rx_data_strobe &&
(cmd == CMD_SEND_S_LSB) &&
(current_c == (i + 1)) &&
(received_s > max_s[i])) begin
// 受信した色と自分の担当色が一致し、
// received_sのほうが大きい場合だけ更新する。
max_s[i] <= received_s;
end
end
end
// 最後の要素max_s[14]には後続要素が存在しないため、
// 返信シフト時は0を入れる。
for (i = 14; i < 15; i = i + 1) begin : gen_max_s_last
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
max_s[i] <= 7'd0;
end else if (cmd_reset_valid) begin
max_s[i] <= 7'd0;
end else if (shift_reply) begin
max_s[i] <= 7'd0;
end else if ((reply_mode == 1'b0) &&
rx_data_strobe &&
(cmd == CMD_SEND_S_LSB) &&
(current_c == (i + 1)) &&
(received_s > max_s[i])) begin
max_s[i] <= received_s;
end
end
end
endgenerate
Verilogコードの合成結果
Verilogコードを合成してbitstreamを生成します。
リソースレポートは次の通りでした。CLBsが65%使われていますね。
CLBs (Configurable Logic Blocks)は、LUTやFFをいくつかまとめて収容する、FPGA内部の物理的な区画です。
Shrike-Lite上のForgeFPGAでは、CLBが140区画あり、ひとつのCLBには8つのLUT(5入力換算)と8つのFFがあります。
レポートを見ると、332個のLUTと153個のCLB FFが91区画のCLBにまたがって配置されていることがわかります。
「もっと少ないCLBにLUTやFFを効率よく詰め込んでほしい」と思うかもしれませんが、ForgeFPGA Workshopでは、合成後のLUTやFFをどのCLBに収容するかは、Place & Route処理が自動的に決定します。
少なくともForgeFPGA Workshopの通常の操作では、「このLUTとFFを同じCLBへ入れる」と細かく指定する機能は見当たりませんので、基本的にはあるがままを受け入れることになります。
2026/7/22追記： ForgeFPGA WorkshopにはPlacement Constraintsが用意されています。ユーザーが関連するロジック群を近くへまとめたり、指定した領域内へ配置するように条件を与えることが可能です。ただし、「このLUTとFFを同じCLBへ収容する」といった細かなパッキングを直接指定するものではなく、具体的な配置はPlace & Route処理によって決定されます。
AIへMicroPython実装を依頼する
Shrike-LiteでABC466B - Representative Ballsの制約版をテストするため、
既存の atcoder_spi_template_test.py を参考にして、
abc466b_restricted_test.py を新規作成してください。
bitstream名は abc466b_restricted.bin です。
Shrike-Liteへのbitstream書き込み、FPGAリセット、
SPI初期化、ピン設定、周波数、CPOL、CPHA、
1byteのSPI送受信処理は既存テンプレートをそのまま使用してください。
main.v、spi_target.v、abc466b_restricted.ffpga、abc466b_restricted.binは変更しないでください。
対象制約：
- N < 16
- M < 16
- 1 <= C_i <= M
- 1 <= S_i <= 100
MOSIは次の1byte構成です。
- bit7:5 = CMD
- bit4 = AUX
- bit3:0 = DATA
コマンド：
- NOP_WAIT = 3'b000
- SEND_C = 3'b001
- SEND_S_MSB = 3'b010
- SEND_S_LSB = 3'b011
- EOD = 3'b100
- NOP_RCV = 3'b101
- DEBUG = 3'b110
- RESET = 3'b111
各テストケースの開始時はRESET → NOP_WAITとしてください。
NOP_WAITで受信するMISOが0x00であることを確認してください。
各ボールについて、次の3byteを送信してください。
1. SEND_C
- AUX = C_i[4]
- DATA = C_i[3:0]
2. SEND_S_MSB
- AUX = 0
- DATA = (S_i >> 4) & 0x07
3. SEND_S_LSB
- AUX = 0
- DATA = S_i & 0x0F
全ボールを送信した後、EODを送信してください。
その後、NOP_RCVをM回送信し、
色1から色Mまでの結果を順番に受信してください。
MISO形式：
- bit7 = REPLY_VALID
- bit6:0 = MAX_SIZE
すべての返信についてREPLY_VALID=1を確認してください。
MAX_SIZE=0の場合は-1へ変換してください。
1～100の場合はその値を結果として使用してください。
M個の結果を受信した後はRESET → NOP_WAITとし、
WAIT状態へ戻ったことを確認してください。
RP2040側では色ごとの最大値を計算しないでください。
テストケースに記載された期待値との比較だけを行ってください。
公式入力例2件を必ず含めてください。
さらに次の観点のテストケースを含めてください。
- N=1、M=1、S=1
- C=15、S=100
- M=15のすべての色を1回ずつ送る
- 同じ色を複数回更新する
- 存在しない色を含む
- 同じサイズを複数回送る
- N=15で同じ色だけを繰り返す
各ケースについて、ケース名、N、M、受信結果、
期待結果、PASS/FAIL、概算処理時間を1行程度で表示してください。
1件がFAILになっても残りのケースを継続してください。
全ケース終了後にPASS数、FAIL数、総処理時間を表示してください。
完成したMicroPythonコード
# ===== ABC466B Representative Balls 制約版の問題固有部分 =====
# 対象制約: 1 <= C_i <= 15, 1 <= S_i <= 100
CMD_NOP_WAIT = 0b000
CMD_SEND_C = 0b001
CMD_SEND_S_MSB = 0b010
CMD_SEND_S_LSB = 0b011
CMD_EOD = 0b100
CMD_NOP_RCV = 0b101
CMD_DEBUG = 0b110
CMD_RESET = 0b111
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,
],
},
]
def make_frame(command, aux=0, data=0):
return (
((command & 0x07) << 5)
| ((aux & 0x01) << 4)
| (data & 0x0F)
)
def decode_reply(rx):
valid = (rx >> 7) & 0x01
value = rx & 0x7F
if valid == 0:
return None
if value == 0:
return -1
return value
def reset_to_wait():
spi_exchange(make_frame(CMD_RESET))
return spi_exchange(make_frame(CMD_NOP_WAIT)) == 0x00
def run_case(case):
wait_ok = reset_to_wait()
received_values = []
valid_ok = True
start_us = time.ticks_us()
for ball in case["balls"]:
c = ball[0]
s = ball[1]
spi_exchange(make_frame(CMD_SEND_C, (c >> 4) & 0x01, c & 0x0F))
spi_exchange(make_frame(CMD_SEND_S_MSB, 0, (s >> 4) & 0x07))
spi_exchange(make_frame(CMD_SEND_S_LSB, 0, s & 0x0F))
spi_exchange(make_frame(CMD_EOD))
for _ in range(case["m"]):
rx = spi_exchange(make_frame(CMD_NOP_RCV))
value = decode_reply(rx)
if value is None:
valid_ok = False
received_values.append(value)
elapsed_us = time.ticks_diff(time.ticks_us(), start_us)
wait_ok = reset_to_wait() and wait_ok
passed = (received_values == case["expected"]) and valid_ok and wait_ok
print(
"NAME={} N={} M={} RX={} EXPECT={} VALID_OK={} WAIT_OK={} {} TIME_US={}".format(
case["name"],
case["n"],
case["m"],
received_values,
case["expected"],
1 if valid_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
for test_case in TEST_CASES:
try:
passed, elapsed_us = run_case(test_case)
except Exception as e:
passed = False
elapsed_us = 0
print(
"NAME={} N={} M={} RX=[] EXPECT={} VALID_OK=0 WAIT_OK=0 FAIL TIME_US=0 ERROR={}".format(
test_case["name"],
test_case["n"],
test_case["m"],
test_case["expected"],
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
)
)
動作確認
完成したbitstreamとMicroPythonコードをShrike-LiteのUSBドライブにコピーして、Thonnyからabc466b_restricted_test.pyを実行します。
NAME=official_sample_1 N=4 M=5 RX=[7, 10, -1, 9, -1] EXPECT=[7, 10, -1, 9, -1] VALID_OK=1 WAIT_OK=1 PASS TIME_US=3492
NAME=official_sample_2 N=5 M=5 RX=[-1, 7, -1, -1, 12] EXPECT=[-1, 7, -1, -1, 12] VALID_OK=1 WAIT_OK=1 PASS TIME_US=4045
NAME=minimum_values N=1 M=1 RX=[1] EXPECT=[1] VALID_OK=1 WAIT_OK=1 PASS TIME_US=1074
NAME=maximum_color_and_size N=1 M=15 RX=[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 100] EXPECT=[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 100] VALID_OK=1 WAIT_OK=1 PASS TIME_US=4478
NAME=all_colors_once N=15 M=15 RX=[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] EXPECT=[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] VALID_OK=1 WAIT_OK=1 PASS TIME_US=11803
NAME=repeated_updates_and_missing_color N=8 M=4 RX=[100, 100, -1, 100] EXPECT=[100, 100, -1, 100] VALID_OK=1 WAIT_OK=1 PASS TIME_US=5533
NAME=equal_values N=6 M=5 RX=[-1, 7, 42, -1, 100] EXPECT=[-1, 7, 42, -1, 100] VALID_OK=1 WAIT_OK=1 PASS TIME_US=4702
NAME=maximum_n_same_color N=15 M=15 RX=[-1, -1, -1, -1, -1, -1, -1, 15, -1, -1, -1, -1, -1, -1, -1] EXPECT=[-1, -1, -1, -1, -1, -1, -1, 15, -1, -1, -1, -1, -1, -1, -1] VALID_OK=1 WAIT_OK=1 PASS TIME_US=11527
SUMMARY PASS=8 FAIL=0 TOTAL_TIME_US=46654
8ケースすべてPASSしました。
SUMMARY PASS=8 FAIL=0
RESETとNOP_WAITを除くSPI転送回数は次のとおりです。
3N + M + 1
今回の最大制約N=15、M=15では61byteです。
all_colors_onceとmaximum_n_same_colorは、どちらも約11.5～11.8msでした。同じNとMであれば、入力値の内容よりSPI転送回数の影響が大きいことが分かります。
今回のまとめ
今回は、ABC466BをShrike-Liteへ実装するため、次の縮小制約を設定しました。
N < 16
M < 16
S_i <= 100
最大15色について、7bitの最大値レジスタをgenerateで作成しました。
入力ストリームの終了後は、最大値レジスタ配列を破壊的にシフトし、色1から順番に結果を返します。
また、rx_data_strobe信号を新たに準備して、rx_data_validの立ち上がりを検出できるようにしました。
assign rx_data_strobe = rx_data_valid && !rx_data_valid_d;
この構成で8ケースすべてPASSしました。
SUMMARY PASS=8 FAIL=0
次回
次回は今回の最大15色版を元に、N <= 100へ拡張したN=100バージョンを作成してみます。お楽しみに。
前回: Shrike-LiteでAtCoder問題を解く(7)：ABC466A - Compromise
次回: Shrike-LiteでAtCoder問題を解く(9)：ABC466B - Representative Balls（完全版）をストリームループで実装する