Shrike-LiteでAtCoder問題を解く(9)：ABC466B - Representative Balls（完全版）をストリームループで実装する

Last updated at 2026-07-18Posted at 2026-07-17

はじめに

今回は、前回に引き続きAtCoder Beginner Contest 466のB問題をShrike-Liteへ実装します。

ABC466B - Representative Balls

前回は、色ごとの最大値をFFへ保持する方法を試すため、次の縮小制約を設定しました。

N < 16
M < 16
S_i <= 100

15色分の最大値レジスタと比較回路をgenerateで作成し、実機テストには成功しました。

しかし、合成後のCLB使用率はすでに65%でした。

ABC466Bの本来の制約は次のとおりです。

1 <= N <= 100
1 <= M <= 100
1 <= C_i <= M
1 <= S_i <= 100

15色分の回路をそのまま100色分まで増やすのは、Shrike-Liteの回路規模では厳しそうです。

そこで今回は、15色分の回路を大きくせず、担当する色の範囲を切り替えながら最大7回使い回すことにします。

1周目: 色1～15
2周目: 色16～30
3周目: 色31～45
...
7周目: 色91～105 （色101～105はM=100では出力対象外）

各周では同じ入力ストリームを最初から最後まで受信し、現在の担当範囲に入る色だけを処理します。

結果は各周の15色ごとにRP2040へ返信するため、追加で大きなFF領域を確保する必要はありません。

今回の主なテーマは次の三つです。

15色分の回路を時間分割で使い回す
FPGA側で周回番号と担当色範囲を管理する
FPGAからRP2040へ入力ストリームの再送を要求する

前回作成した最大値更新回路、破壊的シフト返信、rx_data_strobeはそのまま利用します。今回は変更部分を中心に見ていきます。

1. 実装方針

今回の方式を一言で表すと、次のようになります。

15色分の回路を7本並べる代わりに、1本の回路へ同じ入力ストリームを最大7回流す。

FPGA内部には、前回と同じ15個の最大値レジスタだけを置きます。

max_s[0]  : 現在の担当範囲の1色目
max_s[1]  : 現在の担当範囲の2色目
...
max_s[14] : 現在の担当範囲の15色目

FPGAは現在の担当範囲の先頭をcolor_baseとして保持します。

周回	`round_no`	`color_base`	担当色
1	1	1	1～15
2	2	16	16～30
3	3	31	31～45
4	4	46	46～60
5	5	61	61～75
6	6	76	76～90
7	7	91	91～105

入力されたC_iが現在の担当範囲に入っている場合だけ、最大値更新の対象にします。

assign color_in_range =
    (current_c >= color_base) &&
    (current_c < (color_base + 8'd15));

assign local_index = current_c - color_base;

たとえば2周目ではcolor_base=16です。

C_i=16 → local_index=0
C_i=30 → local_index=14
C_i=15、31など → 担当範囲外なので無視

各周の入力が終わったら、15色分の結果を返信します。

次の周が必要なら、最大値レジスタをクリアし、round_noとcolor_baseを更新して同じ入力ストリームをもう一度待ちます。

2. RP2040とFPGAの役割分担

今回も、RP2040ではなるべく問題そのものを解かない方針にします。

処理	担当
テストケースと期待値を保持する	RP2040
`M`、`C_i`、`S_i`をSPIで送信する	RP2040
FPGAから要求されたら同じ入力を再送する	RP2040
FPGAが通知した周回番号から、受信結果に対応する色番号を判断する	RP2040
`M`を超える色の返信を最終結果から除外する	RP2040
色1～`M`の結果を標準出力する	RP2040
受信結果を期待値と比較し、テスト結果を表示する	RP2040
現在の周回番号を管理する	FPGA
現在の担当色範囲を管理する	FPGA
担当範囲外の色を無視する	FPGA
色番号を0～14のローカル番号へ変換する	FPGA
各色の最大値を計算する	FPGA
次の周が必要か判定する	FPGA
今回の返信が何周目か通知する	FPGA

RP2040はMから必要周回数を事前計算しません。

FPGAから返されたステータスを見て、次の入力ストリームを送るか、処理を終了するかを決めます。

また、15色分の結果が何色に対応するかも、RP2040側の送信回数ではなく、FPGAが通知した周回番号から判断します。

ただし、各周の返信数は15色分で固定しているため、最終周では色番号がMを超える返信が含まれる場合があります。

たとえばM=100の場合、7周目には色91～105の結果が返されますが、色101～105は問題の出力範囲外です。RP2040はこれらを最終結果へ格納せず、色1～100の結果だけを標準出力します。

3. MOSIを4bit CMD＋4bit DATAへ変更する

前回のMOSIは、次の構成でした。

CMD 3bit + AUX 1bit + DATA 4bit

今回はMと最大100までのC_iを受信するコマンドが必要になります。

そこでAUXもコマンド領域へ取り込み、次の構成へ変更します。

bit7          bit4 bit3          bit0
+----------------+------------------+
| CMD 4bit       | DATA 4bit        |
+----------------+------------------+

使用するコマンドは次のとおりです。

CMD	名前	用途
`0x0`	`NOP_WAIT`	WAIT確認
`0x1`	`SET_M_MSB`	`M`の上位4bit
`0x2`	`SET_M_LSB`	`M`の下位4bit
`0x3`	`SEND_C_MSB`	`C_i`の上位4bit
`0x4`	`SEND_C_LSB`	`C_i`の下位4bit
`0x5`	`SEND_S_MSB`	`S_i`の上位4bit
`0x6`	`SEND_S_LSB`	`S_i`の下位4bit
`0x7`	`EOD`	1周分の入力終了
`0x8`	`NOP_RCV`	MISO返信受信用
`0x9`	`RESET`	状態初期化
`0xA`	`DEBUG`	デバッグ用

送信byteは次の形で作ります。

def make_frame(command, data=0):
    return ((command & 0x0F) << 4) | (data & 0x0F)

M、C_i、S_iはいずれも上位4bitと下位4bitに分けて送ります。

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))

Mは最初に1回だけ送信します。

各ボールは次の4byteです。

SEND_C_MSB
SEND_C_LSB
SEND_S_MSB
SEND_S_LSB

Nは送信せず、全ボールの送信後にEODを送ります。

4. MISOへ周回番号付きステータスを追加する

各周で返信するデータは、次の固定16byteとします。

1～15byte目 : 15色分の最大値
16byte目    : 周回番号付きステータス

MISOのbit構成は前回と同じです。

bit7 bit6                      bit0
+----+----------------------------+
| 1  | PAYLOAD 7bit               |
+----+----------------------------+

通常の最大値では、PAYLOAD 0～100を使います。

0     : その色のボールが存在しない
1～100: その色の最大サイズ

S_iの最大値は100なので、未使用の101～114をステータスとして利用します。

次周が必要な場合

PAYLOAD 101～107を使用します。

PAYLOAD = 100 + round_no

MISO	意味
`0xE5`	1周目の結果、次周あり
`0xE6`	2周目の結果、次周あり
`0xE7`	3周目の結果、次周あり
`0xE8`	4周目の結果、次周あり
`0xE9`	5周目の結果、次周あり
`0xEA`	6周目の結果、次周あり
`0xEB`	7周目の結果、次周あり

今回の周で完了する場合

PAYLOAD 108～114を使用します。

PAYLOAD = 107 + round_no

MISO	意味
`0xEC`	1周目の結果、完了
`0xED`	2周目の結果、完了
`0xEE`	3周目の結果、完了
`0xEF`	4周目の結果、完了
`0xF0`	5周目の結果、完了
`0xF1`	6周目の結果、完了
`0xF2`	7周目の結果、完了

たとえばM=31の場合、ステータス列は次のようになります。

0xE5 : 1周目、次周あり
0xE6 : 2周目、次周あり
0xEE : 3周目、完了

RP2040はこのステータスから、直前の15byteが何番目の色の処理結果かを判断します。

start_index = (round_no - 1) * 15

5. SPI通信シーケンス

各テストケースでは、次の順番で通信します。

RESET
NOP_WAIT

Mを2byteで送信

全N個のC_i、S_iを送信
EOD
NOP_RCV × 16

ステータスが「次周あり」なら、
同じ全N個のC_i、S_iを再送
EOD
NOP_RCV × 16

「完了」が返るまで繰り返す

RESET
NOP_WAIT

SPIでは送信と受信が同時に行われるため、前回と同じく返信は1byte遅延します。

EOD受信時に色1の結果をtx_dataへ準備し、その後の16回のNOP_RCVで15色分とステータスを受け取ります。

6. FPGA側の主な変更

前回の次の部分は、そのまま利用します。

15個のmax_sレジスタ
generateによる最大値更新回路
max_s自体を使った破壊的シフト返信
rx_data_strobe
spi_target.v

追加・変更した主なレジスタは次のとおりです。

レジスタ	用途
`current_m`	色数`M`を保持
`current_c`	5bitから8bitへ拡張し、受信した色番号を保持
`round_no`	現在の周回番号
`color_base`	現在の担当範囲の先頭色
`reply_count`	15色＋ステータスの返信位置
`all_done`	全周完了後の入力受付停止

次周が必要かどうかは、次の条件で判定します。

assign next_round_needed =
    ((color_base + 8'd14) < current_m);

ステータスは組合せ回路で生成します。

assign status_payload =
    next_round_needed
        ? (7'd100 + {4'd0, round_no})
        : (7'd107 + {4'd0, round_no});

返信位置はreply_countで管理します。

`reply_count`	処理
1～14	次の色を`tx_data`へ準備し、`max_s`をシフト
15	ステータスを`tx_data`へ準備
16	ステータス送信完了後、次周または全完了へ移行

次周へ進む場合は、15色分の最大値レジスタをクリアします。

end else if (start_next_round) begin
    max_s[i] <= 7'd0;

同時に、制御側では周回と担当色範囲を更新します。

round_no  <= round_no + 3'd1;
color_base <= color_base + 8'd15;

Mは次周でも保持します。

7周目で完了した後はall_done=1とし、次のRESETまで通常入力を受け付けません。

7. MicroPython側の主な変更

MicroPythonファイル名はabc466b_test.py、bitstream名はabc466b.binとしました。

1周分の送信処理は次のとおりです。

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))

各周では、色による選別を行わず、同じballsを同じ順番で送ります。

ステータスは次のように復号します。

def decode_status(rx):
    if (rx & 0x80) == 0:
        return None

    payload = rx & 0x7F

    if 101 <= payload <= 107:
        return payload - 100, True

    if 108 <= payload <= 114:
        return payload - 107, False

    return None

FPGAが通知したround_noだけを使って結果の格納位置を決めます。

start_index = (round_no - 1) * 15

プロトコルの異常を見つけやすくするため、次の点も確認します。

結果byteのVALIDが1である
結果PAYLOADが0～100である
ステータスPAYLOADが101～114である
最初のround_noが1である
周回番号が重複、逆行、飛び越ししていない
7周目に次周要求が返ってこない
受信したステータス列がテストケースの期待値と一致する

期待値と期待ステータスは、入力データから計算せず、テストケースへ静的に記載します。

たとえばM=100の期待ステータスは次のとおりです。

"expected_status": [
    0xE5,
    0xE6,
    0xE7,
    0xE8,
    0xE9,
    0xEA,
    0xF2,
]

8. AIへVerilog実装を依頼する

今回は、第8回で完成したmain.vとabc466b_restricted_test.pyを土台にし、問題固有部分だけを変更しました。

AIへ依頼した内容の要点は次のとおりです。

- main.vの問題固有部分だけを変更する
- CMD 4bit + DATA 4bitへ変更する
- M、C、Sを上位4bit・下位4bitで受信する
- 15色分のmax_sとgenerateは維持する
- round_noとcolor_baseをFPGA側で管理する
- 担当範囲外のCは無視する
- 15色分の返信後に周回番号付きステータスを返す
- ステータス送信完了後に次周へ進む
- 次周開始時にmax_sをクリアし、Mは保持する
- spi_target.vは変更しない
- Git操作は行わない

実際に実装されたコードの問題固有部分は以下のようになりました。

    // ============================================================
    // ABC466B - Representative Balls 完全版の問題固有回路
    //
    // 対象制約:
    //   1 <= N <= 100
    //   1 <= M <= 100
    //   1 <= C_i <= M
    //   1 <= S_i <= 100
    //
    // FPGA内部には15色分の最大値レジスタだけを用意する。
    // 1周ごとに担当する15色の範囲を切り替え、必要に応じて
    // RP2040へ同じ入力ストリームの再送を要求する。
    // ============================================================

    // MOSIの1byteを4bitのコマンドと4bitのデータへ分解する。
    wire [3:0] cmd;
    wire [3:0] data;

    // 保存済みの上位4bitと、今回受信した下位4bitを結合したS_i。
    wire [7:0] received_s;

    // spi_targetのrx_data_validを、1byteにつき1クロックだけHighになる
    // 処理イベントへ変換するための信号。
    reg        rx_data_valid_d;
    wire       rx_data_strobe;

    // RESET、返信シフト、次周開始の実行条件。
    wire       cmd_reset_valid;
    wire       shift_reply;
    wire       start_next_round;

    // current_cが現在の担当色範囲に含まれるかを示す。
    wire       color_in_range;

    // current_cを、15色分の最大値レジスタで使用する
    // 0～14のローカル番号へ変換した値。
    wire [7:0] local_index;

    // 現在の周の後に、さらに次周が必要かを示す。
    wire       next_round_needed;

    // 15色分の返信後に返す、周回番号付きステータスのPAYLOAD。
    wire [6:0] status_payload;

    // 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;

    // 現在の周回番号と、担当する先頭色。
    // 1周目はround_no=1、color_base=1で色1～15を担当する。
    reg [2:0] round_no;
    reg [7:0] color_base;

    // 現在tx_dataへ準備済みの返信番号。
    // 1～15は色ごとの結果、16は周回番号付きステータスを表す。
    reg [4:0] reply_count;

    // 0: 入力ストリーム受信中
    // 1: 15色分の結果とステータスを返信中
    reg       reply_mode;

    // 全周の返信が完了し、RESET待ちであることを示す。
    reg       all_done;

    // 現在の周で担当する15色分の最大サイズを保持する。
    // 受信中は最大値レジスタ、返信中は破壊的シフトレジスタとして使う。
    reg [6:0] max_s [0:14];


    // ============================================================
    // MOSIコマンド
    // ============================================================

    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;


    // ============================================================
    // MOSIフレームの分解と8bit値の復元
    // ============================================================

    assign cmd = rx_data[7:4];
    assign data = rx_data[3:0];

    // SEND_S_LSB受信時は、保存済みの上位4bitと
    // 今回受信した下位4bitをwireで直接結合する。
    assign received_s = {s_high, data};


    // ============================================================
    // 担当色範囲と周回ステータスの生成
    // ============================================================

    // 現在の周が担当する範囲は、color_baseから15色分。
    assign color_in_range =
        (current_c >= color_base) &&
        (current_c < (color_base + 8'd15));

    // 担当範囲内の色番号を、max_s[0]～max_s[14]に対応する
    // 0～14のローカル番号へ変換する。
    assign local_index = current_c - color_base;

    // 現在の担当範囲の末尾よりMが大きければ、次周が必要になる。
    assign next_round_needed =
        ((color_base + 8'd14) < current_m);

    // PAYLOAD 101～107: 1～7周目の結果、次周あり
    // PAYLOAD 108～114: 1～7周目の結果、処理完了
    assign status_payload =
        next_round_needed
            ? (7'd100 + {4'd0, round_no})
            : (7'd107 + {4'd0, round_no});


    // ============================================================
    // rx_data_validの立上り検出
    // ============================================================

    // spi_targetのrx_data_validは、SSが解除されるか、次byteの最初の
    // サンプリングエッジが来るまで複数クロックHighを維持する。
    // そのままコマンド処理の条件にすると、1byteに対して同じ処理が
    // 複数回実行されるため、立上りだけを1クロックパルスとして取り出す。
    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受信中に0へ戻すと、rx_data_validがHighのままなので、
    // 同じRESET byteを次のクロックでも立上りとして再検出してしまう。


    // ============================================================
    // コマンドイベントの生成
    // ============================================================

    // RESETは受信中、返信中、全周完了後のどの状態でも受け付ける。
    assign cmd_reset_valid = rx_data_strobe && (cmd == CMD_RESET);

    // EOD受信時に色1を準備して1回シフトする。
    // 返信中はNOP_RCVの1～14回目だけシフトし、色2～15を順に準備する。
    assign shift_reply =
        rx_data_strobe &&
        (((reply_mode == 1'b0) &&
          (all_done == 1'b0) &&
          (cmd == CMD_EOD)) ||
         ((reply_mode == 1'b1) &&
          (cmd == CMD_NOP_RCV) &&
          (reply_count >= 5'd1) &&
          (reply_count < 5'd15)));

    // 16回目のNOP_RCVでステータス送信が完了した後、
    // 次周が必要な場合だけ周回番号と担当範囲を進める。
    assign start_next_round =
        rx_data_strobe &&
        (reply_mode == 1'b1) &&
        (cmd == CMD_NOP_RCV) &&
        (reply_count == 5'd16) &&
        next_round_needed;


    // ============================================================
    // 入力受信、返信、周回管理
    // ============================================================

    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;
            round_no <= 3'd1;
            color_base <= 8'd1;
            reply_count <= 5'd0;
            reply_mode <= 1'b0;
            all_done <= 1'b0;
            tx_data <= 8'h00;
        end else if (cmd_reset_valid) begin
            // RESETコマンドで1周目の受信待ち状態へ戻す。
            m_high <= 4'd0;
            current_m <= 8'd0;
            c_high <= 4'd0;
            current_c <= 8'd0;
            s_high <= 4'd0;
            round_no <= 3'd1;
            color_base <= 8'd1;
            reply_count <= 5'd0;
            reply_mode <= 1'b0;
            all_done <= 1'b0;
            tx_data <= 8'h00;
        end else if (rx_data_strobe) begin
            if (reply_mode == 1'b1) begin
                // ----------------------------
                // 返信フェーズ
                // ----------------------------
                if (cmd == CMD_NOP_RCV) begin
                    if (shift_reply) begin
                        // 現在のSPI転送では更新前のtx_dataが返信される。
                        // ここでは次の色の結果を次回返信用に準備する。
                        tx_data <= {1'b1, max_s[0]};
                        reply_count <= reply_count + 5'd1;
                    end else if (reply_count == 5'd15) begin
                        // 15色目を送信中に、16byte目の周回番号付き
                        // ステータスを次回返信用として準備する。
                        tx_data <= {1'b1, status_payload};
                        reply_count <= 5'd16;
                    end else if (reply_count == 5'd16) begin
                        // ステータスの送信完了後に返信状態を終了する。
                        tx_data <= 8'h00;
                        reply_count <= 5'd0;
                        reply_mode <= 1'b0;
                        c_high <= 4'd0;
                        current_c <= 8'd0;
                        s_high <= 4'd0;

                        if (start_next_round) begin
                            // Mは保持したまま、担当範囲を次の15色へ進める。
                            round_no <= round_no + 3'd1;
                            color_base <= color_base + 8'd15;
                            all_done <= 1'b0;
                        end else begin
                            // 最終周の返信が完了したので、RESETを待つ。
                            all_done <= 1'b1;
                        end
                    end
                end
            end else if (all_done == 1'b0) 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_EOD: begin
                        // 1周分の入力終了。
                        // 色1の結果を次回SPI返信用に準備し、返信へ移る。
                        // 同じクロックでmax_sもシフトされるが、
                        // ノンブロッキング代入なので、ここではシフト前の
                        // max_s[0]がtx_dataへ入る。
                        reply_mode <= 1'b1;
                        reply_count <= 5'd1;
                        tx_data <= {1'b1, max_s[0]};
                    end
                    default: begin
                        // SEND_S_LSBによる最大値更新は、後段のgenerateで行う。
                        // NOP_WAIT、NOP_RCV、DEBUGはここでは状態を変更しない。
                    end
                endcase
            end
        end
    end


    // ============================================================
    // 15色分の最大値更新と破壊的返信シフト
    // ============================================================

    genvar i;
    generate
        // max_s[0]～max_s[13]
        //
        // 受信中は担当色の最大値を更新する。
        // 返信時は後ろの要素を1段前へ移動し、常にmax_s[0]から返す。
        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 (start_next_round) begin
                    // 次周では同じ15本のレジスタを別の色範囲に再利用する。
                    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) &&
                             (all_done == 1'b0) &&
                             rx_data_strobe &&
                             (cmd == CMD_SEND_S_LSB) &&
                             color_in_range &&
                             (local_index == i) &&
                             (received_s[6:0] > max_s[i])) begin
                    // 受信した色が現在の担当範囲に入り、
                    // 今までの最大値より大きい場合だけ更新する。
                    max_s[i] <= received_s[6:0];
                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 (start_next_round) begin
                    max_s[i] <= 7'd0;
                end else if (shift_reply) begin
                    max_s[i] <= 7'd0;
                end else if ((reply_mode == 1'b0) &&
                             (all_done == 1'b0) &&
                             rx_data_strobe &&
                             (cmd == CMD_SEND_S_LSB) &&
                             color_in_range &&
                             (local_index == i) &&
                             (received_s[6:0] > max_s[i])) begin
                    max_s[i] <= received_s[6:0];
                end
            end
        end
    endgenerate

9. AIへMicroPython実装を依頼する

今回は、第8回で作成したabc466b_restricted_test.pyを土台にし、問題固有部分だけを変更しました。

AIへ依頼した内容の要点は次のとおりです。

- abc466b_restricted_test.pyをabc466b_test.pyへ変更する
- bitstream名をabc466b.binにする
- Mは最初に1回だけ送信する
- FPGAが次周を要求した場合、同じ全入力を再送する
- 15色＋ステータスの16byteを受信する
- FPGAが通知したround_noで結果位置を決める
- RP2040側で最大値や必要周回数を計算しない
- 期待値と期待ステータスは静的に記載する
- 既存8ケースに境界4ケースを追加する
- Git操作、bitstream生成、ほかのファイル変更は行わない

以下が作成されたコードの問題固有部分です。

# ===== ABC466B固有部分 =====
# ABC466B完全制約: 1 <= N, M <= 100, 1 <= C <= M, 1 <= S <= 100
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

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],
        "expected_status": [0xEC],
    },
    {
        "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],
        "expected_status": [0xEC],
    },
    {
        "name": "minimum_values",
        "n": 1,
        "m": 1,
        "balls": [
            (1, 1),
        ],
        "expected": [1],
        "expected_status": [0xEC],
    },
    {
        "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,
        ],
        "expected_status": [0xEC],
    },
    {
        "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,
        ],
        "expected_status": [0xEC],
    },
    {
        "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],
        "expected_status": [0xEC],
    },
    {
        "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],
        "expected_status": [0xEC],
    },
    {
        "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,
        ],
        "expected_status": [0xEC],
    },
    {
        "name": "boundary_m16",
        "n": 5,
        "m": 16,
        "balls": [
            (15, 20),
            (16, 30),
            (15, 100),
            (16, 1),
            (1, 7),
        ],
        "expected": [7] + [-1] * 13 + [100, 30],
        "expected_status": [0xE5, 0xED],
    },
    {
        "name": "boundary_m30",
        "n": 3,
        "m": 30,
        "balls": [
            (1, 3),
            (16, 16),
            (30, 100),
        ],
        "expected": [3] + [-1] * 14 + [16] + [-1] * 13 + [100],
        "expected_status": [0xE5, 0xED],
    },
    {
        "name": "boundary_m31",
        "n": 3,
        "m": 31,
        "balls": [
            (30, 31),
            (31, 30),
            (31, 100),
        ],
        "expected": [-1] * 29 + [31, 100],
        "expected_status": [0xE5, 0xE6, 0xEE],
    },
    {
        "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]
        ),
        "expected_status": [
            0xE5,
            0xE6,
            0xE7,
            0xE8,
            0xE9,
            0xEA,
            0xF2,
        ],
    },
]


def make_frame(command, data=0):
    return ((command & 0x0F) << 4) | (data & 0x0F)


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))


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))


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


def decode_status(rx):
    if (rx & 0x80) == 0:
        return None

    payload = rx & 0x7F

    if 101 <= payload <= 107:
        return payload - 100, True

    if 108 <= payload <= 114:
        return payload - 107, False

    return None


def receive_round():
    values = []
    values_ok = True

    for _ in range(15):
        rx = spi_exchange(make_frame(CMD_NOP_RCV))
        value = decode_value(rx)

        if value is None:
            values_ok = False

        values.append(value)

    status_rx = spi_exchange(make_frame(CMD_NOP_RCV))

    return values, status_rx, values_ok


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 = [-1] * case["m"]
    status_bytes = []
    valid_ok = True
    protocol_ok = True
    done = False
    previous_round_no = 0
    rounds = 0

    start_us = time.ticks_us()
    end_us = start_us

    send_value(CMD_SET_M_MSB, CMD_SET_M_LSB, case["m"])

    for stream_count in range(1, 8):
        rounds = stream_count
        send_stream(case["balls"])

        round_values, status_rx, values_ok = receive_round()
        end_us = time.ticks_us()
        status_bytes.append(status_rx)
        status = decode_status(status_rx)

        if not values_ok:
            valid_ok = False
            protocol_ok = False
            break

        if status is None:
            protocol_ok = False
            break

        round_no, need_next = status

        if round_no < 1 or round_no > 7:
            protocol_ok = False
            break

        if round_no != previous_round_no + 1:
            protocol_ok = False
            break

        start_index = (round_no - 1) * 15

        for offset in range(15):
            index = start_index + offset

            if index < case["m"]:
                received_values[index] = round_values[offset]

        previous_round_no = round_no

        if not need_next:
            done = True
            break

        if round_no == 7 or stream_count == 7:
            protocol_ok = False
            break

    if not done:
        protocol_ok = False

    elapsed_us = time.ticks_diff(end_us, start_us)
    status_ok = status_bytes == case["expected_status"]
    result_ok = received_values == case["expected"]

    wait_ok = reset_to_wait() and wait_ok
    passed = (
        result_ok
        and status_ok
        and valid_ok
        and protocol_ok
        and done
        and wait_ok
    )

    status_text = ",".join(
        ["0x{:02X}".format(value) for value in status_bytes]
    )

    print(
        "NAME={} N={} M={} ROUNDS={} STATUS=[{}] RX={} EXPECT={} VALID_OK={} STATUS_OK={} PROTOCOL_OK={} WAIT_OK={} {} TIME_US={}".format(
            case["name"],
            case["n"],
            case["m"],
            rounds,
            status_text,
            received_values,
            case["expected"],
            1 if valid_ok else 0,
            1 if status_ok else 0,
            1 if protocol_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
        exception_wait_ok = False

        try:
            exception_wait_ok = reset_to_wait()
        except Exception:
            exception_wait_ok = False

        print(
            "NAME={} N={} M={} ROUNDS=0 STATUS=[] RX=[] EXPECT={} VALID_OK=0 STATUS_OK=0 PROTOCOL_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
    )
)

10. プロジェクト構成

今回の主なファイル構成は次のとおりです。

abc466b/
├─ abc466b.ffpga
├─ bitstream/
│  └─ abc466b.bin
├─ ffpga/
│  └─ src/
│     ├─ main.v
│     └─ spi_target.v
└─ firmware/
   └─ micropython/
      └─ abc466b_test.py

spi_target.vと、MicroPython側のShrike-Lite共通部分は変更していません。

11. Verilogコードの合成結果

Verilogコードを合成してbitstreamを生成します。

リソースレポートは次のとおりでした。

主な結果を前回と比較します。

Resource	第8回制約版	第9回完全版
LUT5s	332	472
CLB FFs	153	182
CLBs	91 / 140（65.00%）	101 / 140（72.14%）
4k BRAMs	0	0

追加したのは、Mの受信、8bit化したC、周回番号、担当色範囲、範囲判定、返信ステータスなどです。

それでもCLBの増加は10区画に収まりました。

91 CLB → 101 CLB
65.00% → 72.14%

15色分の処理回路を増やさず、時間分割で使い回した効果が出ています。

12. 実機テスト

公式サンプル2件を含む前回の8ケースを維持し、さらに次の境界ケースを追加しました。

M=16：色15と16の境界
M=30：2周目の末尾で完了
M=31：3周目へ進む境界
N=100、M=100：最大7周

実機テストの結果、12ケースすべてPASSしました。

NAME=boundary_m16 N=5 M=16 ROUNDS=2 STATUS=[0xE5,0xED] ... PASS TIME_US=14868
NAME=boundary_m30 N=3 M=30 ROUNDS=2 STATUS=[0xE5,0xED] ... PASS TIME_US=12234
NAME=boundary_m31 N=3 M=31 ROUNDS=3 STATUS=[0xE5,0xE6,0xEE] ... PASS TIME_US=17911
NAME=full_n100_m100 N=100 M=100 ROUNDS=7 STATUS=[0xE5,0xE6,0xE7,0xE8,0xE9,0xEA,0xF2] ... PASS TIME_US=505264
SUMMARY PASS=12 FAIL=0 TOTAL_TIME_US=620091

M=100では、FPGAから次のステータスが返っています。

0xE5 : 1周目、次周あり
0xE6 : 2周目、次周あり
0xE7 : 3周目、次周あり
0xE8 : 4周目、次周あり
0xE9 : 5周目、次周あり
0xEA : 6周目、次周あり
0xF2 : 7周目、完了

RP2040はこの指示に従って、同じ100件の入力を7回送りました。

最大値計算、担当色範囲の判定、周回管理はすべてFPGA側で行われています。

500msかかっていますが、ACをとれそうです。

13. 処理時間について

最大ケースでは、1周あたり次のSPI転送が必要です。

100個 × 4byte = 400byte
EOD             =   1byte
返信受信用      =  16byte
-------------------------
1周             = 417byte

7周に加えて、最初にMを2byte送るため、合計は次のとおりです。

417 × 7 + 2 = 2921byte

SPI 1MHzで2921byteを純粋に転送する時間は、約23.4msです。

実測は約505msなので、FPGA内部の最大値比較よりも、次のようなMicroPython側の処理時間が大部分を占めていると考えられます。

1byteごとのspi_exchange()呼び出し
1byteごとのCS操作
bytesとbytearrayの生成
MicroPythonのループと関数呼び出し

前回までと同じく、FPGA内部の演算より、RP2040とFPGAの間でデータを運ぶ時間のほうが支配的です。

今回の方式は問題に指定されている最大制約へ対応できますが、そのために同じ入力を最大7回送ります。

回路資源を節約する代わりに、通信時間を使う

という実装です。

今回のまとめ

今回は、前回作成した15色分の最大値回路を最大7回使い回し、ABC466Bの制約に完全対応しました。

主な変更は次のとおりです。

MOSIをCMD 4bit + DATA 4bitへ変更
M、C_i、S_iを2byteで受信
FPGA側へround_noとcolor_baseを追加
現在の担当範囲外の色を無視
15色分の返信後に周回番号付きステータスを返信
FPGAが必要な場合だけ、RP2040へ同じ入力の再送を要求
FPGAから通知された周回番号で結果位置を決定

実機テストは12ケースすべてPASSしましたが、最大ケースでの処理時間は約500msになりました。

次回

次回は、ForgeFPGAに内蔵されているBRAMの使い方を確認し、今後のAtCoder実装で再利用できるBRAMテンプレートを作成します。

その後、BRAMへ100色分の最大値を保存し、入力ストリームを1回だけ送るABC466B_BRAM利用版へ進む予定です。お楽しみに。

前回: Shrike-LiteでAtCoder問題を解く(8)：ABC466B - Representative Balls（制約版）を実装する

次回: Shrike-LiteでAtCoder問題を解く(10)：BRAMテンプレートを作る

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up