0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@bit_otter

Shrike-LiteでAtCoder問題を解く(20)：ABC468A - Maximal Value

0
Last updated at Posted at 2026-07-27

はじめに

前回は、AtCoder Beginner Contest 468の各問題を、Shrike-Liteへ実装する場合の視点から確認しました。

今回は、その中からA問題の「Maximal Value」を実際に実装します。

ABC466から始めた問題解答編も、今回で3週目になりました。SPI通信についてはこれまでの記事で説明しているため、今回はMOSI/MISOや1byte遅延の一般的な説明を繰り返さず、ABC468A固有の通信仕様と回路を中心に進めます。

また、今回から新しく、4MHz SPIと最大256byteの可変長バースト転送に対応したSPIテンプレートV3を使用します。

今回も記事とコードの草稿作成にはAIを使用しています。

今回使用するもの

  • Shrike-Lite
  • ForgeFPGA Workshop
  • Thonny / MicroPython
  • AtCoder SPI Template V3

今回も、RP2040側ではテストデータの保持、FPGAへの送信、回答の受信を行います。

問題の判定処理はShrike-Lite側へ実装します。

コードの生成にはAIを使用し、通信仕様、回路構成、テスト条件はこちらで決めます。生成されたコードは、合成レポート、Timing Analysis、実機試験で確認します。

ABC468A - Maximal Value

問題はこちらです。

長さNの整数列Aについて、次の条件を満たす位置の個数を求めます。

A_i < A_{i+1} > A_{i+2}

つまり、連続する3つの値を見て、中央の値が左右の値より大きい場所を数えます。

制約は次のとおりです。

3 <= N <= 100
1 <= A_i <= 100

Nと各A_iは7bitで表せます。

また、答えも7bitに収まるため、FPGAからの返信はVALID 1bitと答え7bitを合わせた1byteとします。

素朴に3つずつ確認する

解法は、連続する3要素を順番に取り出し、大小関係を比較するだけです。

A_1, A_2, A_3
     ↓
A_2が左右より大きければ加算

A_2, A_3, A_4
     ↓
A_3が左右より大きければ加算

今回は、この処理をそのままFPGAへ持っていきます。

回路では直前の2要素を2つの7bit FFへ保持し、今回受信した値と合わせて3要素を確認します。

例えば、FFへA_1とA_2が入っているときにA_3を受信すると、

A_1 < A_2 かつ A_2 > A_3

を判定します。

判定後は、A_2とA_3を次の比較のために保持します。

これにより、配列全体を保存しなくても、直前の2要素だけを使って順番に判定できます。

最初の2回は番兵値で判定を無効にする

最初の2要素を受信した段階では、まだ比較に必要な3要素がそろっていません。

素朴な処理では、受信個数を確認し、3個目以降だけ大小比較を行います。

今回はこの判定を省くため、2つの7bit FFを入力範囲外の同じ値で初期化します。

A_iの最大値は100なので、その次の値である101を番兵値として使用します。Verilogでは7'd101と記述します。

受信時に比較する3つの値は、次のように変化します。

初期状態       101     101
A_1受信時      101     101     A_1
A_2受信時      101     A_1     A_2
A_3受信時      A_1     A_2     A_3

A_1を受信したときは、

101 < 101

が偽になります。

A_2を受信したときも、A_1は最大100なので、

101 < A_1

は必ず偽になります。

そしてA_3を受信すると、初めて実際の3要素による判定になります。

これにより、「3個目以降の受信か」を確認するためのカウンタ比較は不要になります。

ただし、A_iをN個受信し終えたかどうかを判断する残り個数の管理は引き続き必要です。

今回は7bitの大小比較を2回行うだけなので、かなり素直な回路になりそうです。

SPIテンプレートV3を使用する

AtCoder SPI Template V3は、SPIテンプレートV2を基に、RP2040側を次の構成へ更新したものです。

  • SPI通信速度：4MHz
  • 1～256byteの可変長バースト転送
  • バースト転送中はCSをLowのまま保持
  • TX/RXバッファを事前確保して再利用
  • 256byte未満の端数転送に対応

FPGA側のmain.vとspi_target.vはV2から変更していません。

テンプレートには、受信した1byteへ1を加え、次のSPI転送で返信するテストコードが実装されています。1byte互換試験に加えて、1、2、31、32、255、256byteのバースト転送を実機で確認しています。

今回は、このV3をコピーし、ABC468A固有の処理だけを追加します。

通信仕様を決める

NとA_iはどちらも7bitで表せます。

また、Nは3以上、A_iは1以上100以下なので、0x00と0xFD～0xFFは問題の入力値として現れません。

そこで、これらの値を制御用として予約します。

値 用途
0x00 NOP／ACK・回答読出し用のダミー転送
0xFD DEBUG用に予約
0xFE 転送開始（START）
0xFF SPI RESET

0xFDは将来のDEBUG機能用に確保し、今回は動作を割り当てません。

0xFFのSPI RESETは、FPGA側がどの状態にいても最優先で受理します。

各テストケースをSPI RESETから開始することで、前回の状態にかかわらず、SPI通信だけで問題回路を初期状態へ戻せます。

RESETとSTARTの応答

SPI RESETとSTARTが実際に受理されたことを確認するため、それぞれ異なるACKを返します。

RESET_ACK = 0x5A
START_ACK = 0xA5

MISOの返信は1byte遅れるため、コマンドを送った次の転送でACKを読み出します。

各テストケースの開始時の通信順序は次のとおりです。

  1. SPI RESETとして0xFFを送る
  2. NOPとして0x00を送り、RESET_ACK=0x5Aを確認する
  3. STARTとして0xFEを送る
  4. Nを送り、同時にSTART_ACK=0xA5を確認する
  5. 続くNbyteをA_1からA_Nとしてバースト送信する
  6. N個受信したらFPGA側で回答を準備する
  7. RP2040がダミーbyteを送り、MISOから回答を読む

開始確認後は受信状態によって各byteの意味を判断するため、NやA_iへコマンドbitを付加する必要はありません。

RP2040からFPGAへ送るデータ

転送 MOSI 同時に確認するMISO 転送方法
1 0xFF（SPI RESET） 前回の値なので無視 1byte転送
2 0x00（NOP） 0x5A（RESET_ACK） 1byte転送
3 0xFE（START） 0x00 1byte転送
4 N 0xA5（START_ACK） 1byte転送
5 A_1～A_N 回答準備前の値 Nbyteのバースト転送
6 0x00 VALID + ANSWER 回答読出し用のダミー転送

Nは最大100、配列も最大100byteです。

したがって、A_1からA_NまでをV3の256byteバッファへ収め、1回のバースト転送で送信できます。

FPGAからRP2040へ返すデータ

回答は1byteで返します。

bit 内容
7 VALID
6:0 ANSWER

有効な回答は次の形式です。

1AAAAAAA

VALID=1であれば、下位7bitを答えとして使用します。

reply = 0x80 | answer

回答準備前の通常値は0x00とします。

FPGA側の状態

FPGA側では、次のような状態で受信内容を管理します。

WAIT_START
  ↓ 0xFEを受信
WAIT_N
  ↓ Nを受信
RECEIVE_A
  ↓ AをN個受信
PREPARE_REPLY
  ↓ 回答をtx_dataへ保存
DONE

SPI RESETの0xFFは、現在の状態にかかわらず最優先で処理し、WAIT_STARTへ戻します。

SPI RESET

0xFFを受信した場合は、次を初期化します。

  • 状態をWAIT_STARTへ戻す
  • 2つの7bit FFを101へ戻す
  • 残り受信個数を初期化する
  • 回答カウンタを0へ戻す
  • tx_dataへRESET_ACK=0x5Aを準備する

WAIT_START

WAIT_STARTでは、STARTの0xFEを待ちます。

0x00のNOPを受信した場合は、状態を変更せず、次の転送に備えてtx_dataを0x00へ戻します。

0xFEを受信した場合は、tx_dataへSTART_ACK=0xA5を準備し、WAIT_Nへ進みます。

STARTが正しく届かなければ、次の転送で0xA5が返らないため、RP2040側で開始失敗を検出できます。

0xFDはDEBUG用の予約値ですが、今回は状態を変更しません。

WAIT_N

STARTの次に受信したbyteを、配列の残り受信個数として設定します。

同時に、2つの7bit FFを番兵値101へ戻し、回答カウンタを0へ初期化してRECEIVE_Aへ進みます。

N送信時のMISOでは、直前のSTARTに対する0xA5を返信します。

RECEIVE_A

rx_data_strobeがHighになるたびに、直前の2要素と新しく受信した値を使って、

A_{i-2} < A_{i-1} かつ A_{i-1} > A_i

を判定します。

番兵値によって最初の2回は必ず不成立になるため、判定開始用のカウンタ比較は行いません。

条件を満たしていれば、回答カウンタを1増やします。

判定後は直前の2要素を更新し、残り受信個数を1減らします。A_Nまで受信したらPREPARE_REPLYへ進みます。

PREPARE_REPLY

最後のA_Nを受信したクロックでも、A_{N-2} < A_{N-1} かつ A_{N-1} > A_Nの条件を満たせば回答カウンタが加算されます。

その場合、同じalwaysブロック内でカウンタ更新と返信データ生成を行うと、ノンブロッキング代入によって加算前の値を返信してしまいます。

そこで、最後の値を受信したあと、返信準備用のPREPARE_REPLY状態へ移って、そこに1クロックだけ滞在します。

次のクロックでは更新後の回答カウンタを参照できるため、PREPARE_REPLY状態で回答をtx_dataへ格納し、そのままDONE状態へ進みます。

tx_data[7]   = 1
tx_data[6:0] = answer

SPI通信とのタイミングを検討しておく

第18回記事のパイプライン化では、処理を2クロックへ分けたことで、最終処理結果がレジスタへ反映される前に返信データの準備が進められる可能性がありました。

そのため、更新予定の値を次段へ直接渡すバイパスルートを設けました。

今回も、最後のA_Nを受信してから回答がtx_dataへ反映されるまでには、複数のFPGAクロックが必要です。

第18回と同じような対策を行わなくても大丈夫でしょうか。ここで、SPI通信とのタイミングを確認しておくのがよさそうです。

Shrike-LiteでAtCoder問題を解く(20)_002.png

SPIテンプレートでは、最後のA_Nの8bit目が、SPIクロックの8回目の立上りで取り込まれます。

その後、SPI Target側でSCKの同期と受信完了の検出におよそ2～3クロック、main.v側で最後の判定とPREPARE_REPLYによる回答生成に2クロックを使用します。

FPGAは50MHzで動作しているため、全体でもおよそ4～5クロック、80～100ns程度で返信データの準備が整います。

一方、回答が送信用レジスタへ取り込まれるのは、CSがHighのギャップを挟んだ次のCS立下りです。

したがって、返信要求が始まるまでには十分な余裕があり、第18回のようなバイパス処理は必要ありません。

FPGA側の処理時間をクロック数から明確に見積もり、実際の通信間隔と比較できる点は、FPGAを使うありがたみの一つです。

DONE

RP2040からのダミー転送に対して、準備済みの回答をMISOへ返します。

状態はDONEのまま維持し、次のテストケースはSPI RESETの0xFFから開始します。

これにより、各テストケースを同じSPI通信手順で初期状態から開始できます。

実装準備を行う

実装仕様の検討は済みましたので、実装を始めます。

V3テンプレートからABC468Aを作る

V3のフォルダをコピーし、ABC468A用のプロジェクトを作成します。フォルダ名はabc468aとします。

ffpgaファイル、pyファイルは、それぞれ abc468a.ffpga、abc468a_test.pyとリネームしてください。

実装時の変更対象は次の2ファイルです。

ffpga/src/main.v
firmware/micropython/abc468a_test.py

spi_target.vはV3から変更しません。

AIに実装を依頼する

今回も、ここまでに決めた仕様と、いつもの実装条件をまとめてAIへ渡します。

主な依頼内容は次のとおりです。

  • V3テンプレートをコピーしてABC468A用プロジェクトを作る
  • spi_target.vは変更しない
  • 0xFDをDEBUG用として予約する
  • 0xFEをSTARTとして実装する
  • 0xFFを全状態共通のSPI RESETとして実装する
  • SPI RESET受信後にRESET_ACK=0x5Aを準備する
  • START受信後にSTART_ACK=0xA5を準備する
  • STARTの次の1byteをNとして受信する
  • 続くNbyteをCS保持バーストで受信する
  • 直前の2要素を保持する7bit FFを101で初期化する
  • 番兵値により最初の2回の山判定を自然に不成立とする
  • A_i < A_{i+1} > A_{i+2}を判定してカウントする
  • N個の受信完了を管理する
  • 最終値を含む判定結果を返信へ反映する
  • VALID＋7bit回答を1byteで返す
  • V3のMicroPythonテストをABC468A用のabc468a_test.pyへ更新する
  • 各テストケースはSPI RESETから開始する
  • Git操作は行わない
  • 日本語コメントを維持する

生成されたVerilogコードを確認する

生成されたmain.vのうち、ABC468A固有の部分を確認します。

完全なソースコードはGitHubへ掲載し、記事中では動作の中心となる部分だけを抜粋します。

第20回コード全文

状態とレジスタ

状態は、仕様どおり5つに分かれています。

localparam [2:0] WAIT_START    = 3'd0;
localparam [2:0] WAIT_N        = 3'd1;
localparam [2:0] RECEIVE_A     = 3'd2;
localparam [2:0] PREPARE_REPLY = 3'd3;
localparam [2:0] DONE          = 3'd4;

問題固有のレジスタは、残り受信個数、回答カウンタ、直前の2要素です。

reg [6:0] remaining_count;
reg [6:0] answer_count;
reg [6:0] a_middle;
reg [6:0] a_right;

今回受信した値はrx_dataにあるため、3要素すべてをFFへ保存する必要はありません。

SPI RESETを最優先で処理する

SPI RESETは、状態を判定するcase文より前に置かれています。

end else if (rx_data_strobe && rx_data == 8'hFF) begin
    tx_data <= RESET_ACK;
    state <= WAIT_START;
    remaining_count <= 7'd0;
    answer_count <= 7'd0;
    a_middle <= 7'd101;
    a_right <= 7'd101;
end else begin
    case (state)

これにより、配列の受信途中や回答準備後でも、0xFFを受信すれば同じ初期状態へ戻ります。

直前の2要素と今回値で判定する

問題の中心となる処理はRECEIVE_Aです。

直前の2要素をa_middleとa_rightへ保持し、今回受信したrx_dataと合わせて山を判定します。

a_middle      2つ前の値
a_right       直前の値
rx_data       今回受信した値

今回受信した値はrx_dataから直接使えるため、回路で保持するFFは2つで十分です。

RECEIVE_A: begin
    if (rx_data_strobe) begin
        a_middle <= a_right;
        a_right <= rx_data[6:0];

        if (a_middle < a_right &&
            a_right > rx_data[6:0]) begin
            answer_count <= answer_count + 7'd1;
        end

        if (remaining_count == 7'd1) begin
            remaining_count <= 7'd0;
            state <= PREPARE_REPLY;
        end else begin
            remaining_count <= remaining_count - 7'd1;
        end
    end
end

ノンブロッキング代入では右辺に更新前の値が使われるため、このクロックでは直前の2要素と今回値で山を判定できます。

その後、2つのFFは次の比較に使う値へ更新されます。

最後の加算を返信へ反映する

最後の値を受信するとPREPARE_REPLYへ進みます。

PREPARE_REPLY: begin
    tx_data <= {1'b1, answer_count};
    state <= DONE;
end

DONE: begin
    // 回答読出し用NOPを受信しても返信値と状態を保持する。
end

PREPARE_REPLYを1クロック挟むことで、最後のA_Nによる加算を含む回答がtx_dataへ格納されます。

合成する

ForgeFPGA Workshopで合成します。

今回の回路は、7bitの大小比較2個、小さなカウンタ、直前の2要素を保持するFF、SPI RESETとSTARTを扱う状態管理が中心です。

合成結果は次のとおりです。

Shrike-LiteでAtCoder問題を解く(20)_001.png

十分余裕をもって合成～配置ができました。

Timing Analysisを確認する

第17回と第18回では、ABC467Cで発生したタイミング違反へ対応しました。

今回は、同じように50MHzのクロック制約を設定します。

create_clock -name clk {clk} -period 20.000

結果は次のとおりです。

Constrained Period    20.000ns
Achievable Period     10.148ns
Achievable Frequency  98.542MHz
WNS                    +9.851ns
TNS                     0ns
Logic stage             3

必要な50MHzに対して、約98.5MHzまで動作可能という結果です。

今回の最長経路は最大3段で、WNSにも約9.85nsの余裕があります。ABC467Cのようなタイミング対応は必要ありませんでした。

abc468a_test.pyで実機確認する

合成したabc468a.binをShrike-Liteへ書き込み、abc468a_test.pyをThonnyから実行します。

テストには、公式サンプル、最小入力、番兵値、最後の要素による加算、最大入力、DEBUG予約値、配列受信途中のSPI RESETなど、18ケースを用意しました。

代表的な結果は次のとおりです。

ケース N ANSWER EXPECT TIME_US 結果
N3_NO_PEAK 3 0 0 710 PASS
N3_ONE_PEAK 3 1 1 621 PASS
LAST_A_ADDS 4 1 1 623 PASS
SENTINEL_NO_FALSE_ADD 3 0 0 648 PASS
N100_MIXED 100 28 28 1773 PASS
ALTERNATING_1_100 100 49 49 1753 PASS
DEBUG_BEFORE_START 3 1 1 917 PASS
RESET_DURING_ARRAY 5 2 2 1159 PASS

すべてのケースで、RESET_ACK=0x5AとSTART_ACK=0xA5も正しく返りました。

最後の集計結果は次のとおりです。

SUMMARY PASS=18 FAIL=0 RESULT=PASS

最後のA_Nで回答が増えるケース、番兵値による誤加算、配列受信途中からのSPI RESET復帰も含め、すべてPASSしました。

処理時間を確認する

ABC468Aでは、最大でもN=100です。

実機試験で最も時間がかかったのはN=100のケースで、約1.77msでした。

N100_MIXED         1773µs
ALTERNATING_1_100  1753µs

ACをとれそうですね。

今回のまとめ

今回は、SPIテンプレートV3を使ってABC468Aを実装しました。

FPGA側では、直前の2要素と今回受信した値を比較し、中央が左右より大きい場所を数えます。2つのFFを101で初期化することで、最初の2回の判定も自然に無効化できました。

合成後は50MHz制約を満たし、実機試験も18ケースすべてPASSしました。最大入力N=100の処理時間は約1.77msでした。

次回

次回は、ABC468BをShrike-Liteへ実装できるか検討します。

お楽しみに。

前回：
Shrike-LiteでAtCoder問題を解く(19)：Interlude - ABC468の各問題をFPGA目線で見てみる

次回：
Shrike-LiteでAtCoder問題を解く(21)：ABC468B - Corridor Watch

今回のコード：
第20回コード全文

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?