Shrike-LiteでAtCoder問題を解く(23)：ABC468B③ - BRAMに配列を置く

Last updated at 2026-07-31Posted at 2026-07-30

はじめに

前回は、ABC468B「Corridor Watch」を100bitのFF配列とDistributed RAMで実装しました。

Shrike-LiteでAtCoder問題を解く(22)：ABC468B② - 配列実装を試す

FF配列版はType=Lリソースが不足し、Placementに失敗しました。

一方、Distributed RAM版は同じ素朴な配列更新方式を維持したまま配置に成功し、4MHz SPIによる実機試験もPASSしました。

今回は、監視状態をForgeFPGAの内蔵BRAMへ保持してみて、他の方式との違いを確認してみます。

以前のBRAMテンプレートもV3へ更新する

ABC468Bの実装へ取りかかる前に、既存のBRAMテンプレートを更新することにしました。

以前の記事でSPI通信を高速化し、以下の機能を持つSPIテンプレートV3を作成しました。

SPI 4MHz
1～256byteの可変長バースト
送受信バッファの再利用
1byte遅延応答

今後BRAMを使う問題でも同じ通信方式を利用できるように、BRAMテンプレートにもV3のSPIを組み込んでおこうと考えました。

BRAM自体の構成は変更しないでおく方針です。

BRAM0だけを利用
深さ：512
幅  ：8bit

ついでにACKも追加する

機能強化として、RESETとSTARTを受信したことがホスト側から分かるように、ACKも追加することにしました。

RESET_ACK：0x5A
START_ACK：0xA5

ACKが返れば、MicroPython側からFPGA側の状況や通信手順を確認しやすくなります。

SPIの高速化が本来の更新目的でしたが、テンプレートとして使いやすくするため、ハンドシェイクも一緒に追加することにしました。

AIにテンプレートの更新を依頼する

仕様書と既存のテンプレートを用意し、AIへ更新を依頼しました。

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

BRAM0 8bitアクセステンプレートを母体にする
SPI通信をテンプレートV3へ更新する
SPI 4MHzと可変長バーストへ対応する
RESET ACKとSTART ACKを追加する
RESET時にBRAM全領域を0へ初期化する
BRAM書き込みと同期読み出しを確認する
既存のBRAMアクセス回路を利用する
SystemVerilog構文を使わない

AIによる実装後、BRAMの書き込み、読み出し、ACKなどを確認しました。

ひとまず、BRAMテンプレートV3は完成したように見えました。

BRAMの初期化中にSTARTが届いたらどうなる？

確認作業を進めている途中で、ひとつ疑問が浮かびました。

RESET ACKを受け取ってすぐにSTARTを送った場合、どういう動作になるのだろう？

このテンプレートでは、FPGAはRESETを受信すると、BRAMの512アドレスを順番に0x00へ初期化します。

アクセス回路は各アドレスについて書き込みとGAPの2状態を通るため、全領域のclearには約1024クロック必要です。

50MHzでは約20.5µsです。

一方、SPIは1byte遅延応答です。

マスターはRESETを送信した次のbyteでRESET ACKを受け取り、その後すぐにSTARTを送信するかもしれません。

RESET送信
↓
次のbyteでRESET ACK受信
↓
START送信

4MHz SPIでは、1byteの転送に約2µsかかります。

ということは、STARTがFPGAへ届いた時点でも、BRAMのclearはまだ続いている可能性があります。

そこで、clear中にSTARTを送った場合の動作を確認してみました。

調べてみると、マスターとFPGAの状態が食い違っていた

最初の実装では、BRAMのclear中でもSTARTを受理し、次のbyteでSTART_ACK=0xA5を返していました。

START ACKを受け取ったマスターは、FPGAの準備が完了し、BRAMへアクセスできると判断します。

しかし、FPGA内部ではまだclear処理が続いています。

マスター側の認識：準備完了・送信OK
FPGA側ステータス：BRAM初期化中

という状態の食い違いが発生していました。

この状態でWRITEを送信しても、BRAMアクセス回路はclear処理に使用されているため、通常の書き込み要求を処理できません。

READについても通常の読み出し処理を開始できませんが、SPI上は応答byteが返るため、マスター側では0x00を正常に読み出したように見える可能性があります。

これは誤解答の原因になりますね。

そこで、BRAMのclearが完了するまではSTARTを受理せず、初期化完了後にだけSTART ACKを返すように修正します。

修正方法を検討する

START ACKは、BRAMへの通常アクセスを開始できる状態になってから返す必要があります。

そこで、BRAMアクセス回路のbusyを使ってclear完了を判定することにしました。

clearを開始するとbusyがHighになり、512アドレスの初期化が終わるとLowへ戻ります。

ただし、clear要求直後はbusyがまだLowです。単純にbusy == 0だけを見ると、clear開始前を完了と誤認してしまいます。

そのため、

busyが一度Highになったことを確認する
その後Lowへ戻った時点をclear完了とする

という制御にします。

clear中のSTARTは受理せず、初期化完了後に再送された場合だけSTART ACKを返します。

AIへ追加要望を出す

検討した内容をAIへ伝え、テンプレートの修正を依頼しました。

主な追加要望は次のとおりです。

clear処理中であることをclear_activeで管理する
clear_busy_seenで、busyが一度Highになったことを記録する
busyがHighになった後、Lowへ戻った時点をclear完了とする
clear中のSTARTは受理しない
clear完了後に再送されたSTARTだけを受理する
STARTを受理した場合だけSTART_ACK=0xA5を返す

clear中にSTARTを受信した場合は、次の状態を維持します。

STARTへの応答   ：0x00
protocol_started：0
後続入力        ：無視

これで、マスターがSTART ACKを受け取った時点では、FPGA側もBRAMへの通常アクセスを開始できる状態になります。

RP2040側にも待ち時間を追加する

FPGA側では、BRAMのclearが完了するまでSTARTを受理しないようにしました。

一方、RP2040側でも、BRAMのclear時間約20.5µsに対して十分な余裕を取るため、RESET ACK受信後に1ms待ってからSTARTを送信するように変更します。

send_reset()
wait_reset_ack()

time.sleep_ms(1)

send_start()
wait_start_ack()

FPGA側にはclear中のSTARTを拒否する仕組みがありますが、通常の通信で毎回拒否と再送を発生させる必要はありません。

そこで、テンプレートではRP2040側にも待ち時間を入れ、clear完了後にSTARTを送る手順としました。

BRAM V3テンプレート完成

修正後のテンプレートでは、次を確認しました。

SPI 4MHz
CPOL=0、CPHA=0
1～256byteの可変長バースト
RESET ACK
START ACK
BRAM書き込み
BRAM読み出し
1byte遅延応答
RESET後の全領域ゼロクリア
4クロックの同期読み出し
clear中のSTART拒否

実機試験は10ケースすべてPASSしました。

SUMMARY PASS=10 FAIL=0 RESULT=PASS

GitHubでは次の場所へ公開しています。

atcoder_spi_bram0_8bit_template_v3

これで、ABC468B BRAM版の母体にできるテンプレートが用意できました。

修正版テンプレートでABC468Bを実装する

ここから、修正版のBRAM V3テンプレートを使ってABC468Bを実装します。

前回のDistributed RAM版と同じく、廊下の各マスについて監視済みかどうかをメモリへ保持します。

ただし、BRAMには書き込み完了待ちや同期読み出しがあるため、同じ処理をそのまま移植することはできません。

実装仕様を検討する

いつもの通り、まずは実装仕様を検討します。

BRAMへ保持する値

ABC468Bでは、アドレス0～M-1を廊下の各マスへ対応させます。

アドレス0～M-1：廊下の監視状態
アドレスM～511：回答には使用しない

BRAM V3テンプレートではRESET時に全512アドレスを0へ初期化します。

そこで、Distributed RAM版とは値の意味を反転しました。

0x00：未監視
0x01：監視済み

Gを受信した場合は、監視範囲へ0x01を書き込みます。

すでに0x01が書かれていても、現在値は確認せず、そのまま0x01を上書きします。

最後にアドレス0～M-1を読み出し、0x00の個数を数えます。

BRAM書き込みとSPI受信のタイミングを考える

今回のBRAMアクセス回路では、1wordの書き込みに2クロック必要です。

要求受付
↓
WRITE
↓
WRITE_DONE
↓
次の要求

最大100wordの範囲更新には、200クロック程度が必要になります。

一方、4MHz SPIでは1byteが2µsです。50MHz内部クロックでは、約100クロックしかありません。

BRAM最大範囲更新：200クロック
次のSPI byte到着：100クロック

単純にDistributed RAM版を移植すると、更新処理が終わる前に次のGが届きます。

Gが立て続けに到着すると、1件保留バッファだけでは、未処理Gのキューがオーバーフローしそうです。

何か対策を考える必要がありますね。

更新要求を溜めず、書き込み範囲だけを更新する

ABC468Bの範囲更新には、次の特徴があります。

書き込む値は常に0x01
文字位置は左から右へ進む
更新範囲の開始位置と終了位置は、それぞれ右にしか移動しない

この性質を利用します。

現在、次の範囲を書き込んでいるとします。

[0, 50]

途中で次の更新要求、

[40, 90]

を受信した場合、別の要求として保存しないで、現在の書き込み終了位置を、

50 → 90

へ延長します。

発行済みのBRAM命令を変更しているわけではありません。

まだ発行していない未来の書き込み操作の終点だけを変更しています。

離れた区間は1件だけ保留する

新しい範囲が現在の範囲と重複も隣接もしない場合は、1件保留バッファへ保存します。

実行中：[0,20]
新要求：[30,50]

このとき、21～29まで監視済みにしてはいけないため、単純に終了位置を50へ伸ばすことはできません。

その場合は、保留区間バッファへ保存し、現在の更新完了後に処理します。

さらに新しい要求が届いた場合は、

実行中区間と統合できるか
保留区間と統合できるか
どちらにも入らないか

を判定します。

この仕組みでBRAMの更新書き込みはまにあうはずですが、どちらにも統合できない3番目の不連続区間が届いた場合は、update_overrun=1にします。

最終集計

すべての文字を受信した後も、直ちに集計は始めません。

次をすべて待ちます。

実行中更新なし
保留更新なし
BRAM busyなし
未発行書き込みなし

その後、アドレス0～M-1を順番に読み出します。

BRAMの読み出しは同期式で、REN受付からread_validまで4クロック必要です。

そこで、集計FSMを次のように分けました。

COUNT_REQUEST
↓
busy確認
↓
read_valid待ち
↓
データ集計
↓
次アドレス

最後のアドレスの値を加算した後、PREPARE_REPLYを1クロック挟みます。

これにより、非ブロッキング代入で最後の加算前の値を返信する問題を避けています。

AIにABC468Bの実装を依頼する

今回も、仕様書と参照実装を用意してAIへ実装を依頼しました。

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

BRAM V3テンプレートを母体にする
spi_target.vを変更しない
bram0_8bit_access.vを変更しない
.ffpgaとSDCを変更しない
ABC468B Distributed RAM版の入力FSMと範囲更新を移植する
BRAMのbusyと4クロック読み出し待ちを正しく扱う
4MHz最大負荷でもupdate_overrun=0にする
大きなFIFOを追加しない

すると、AIから仕様の改善を提案されました。

完了済みの範囲はもう書かない

AIから提示された改善提案理由を確認すると、BRAM書き込みのスループットに余裕がないことが挙げられていました。

検討してみると、確かに、1ケースで最大5000回のBRAM書き込みが発生する可能性があります。

これはD=99の条件で、Gと.が交互に送られてくるようなケースで見られます。

最初の'G' → [0,99]区間を200クロック(4μs)かけて書き込み処理
　　↓ SPI 1byte後 (2μs + α)
次の '.'
　　↓ SPI 1byte後 (2μs + α)
次の 'G'  → 最初の[0,99]更新が終わっているため、改めて[0,99]更新を開始
　　↓ SPI 1byte後 (2μs + α)
以下100要素目まで繰り返し

50セット x 各100word = 5000書き込み

これは理論上のスループット限界に近い状態です。シングルランでは許容できそうですが、あまりスマートではありません。

そこで、最後に書き込みを完了した区間の右端を1レジスタへ保持するように仕様を変更します。

新しい更新範囲が、すでに完了した範囲へ完全に含まれている場合は、BRAMへ再度書き込みません。

先ほどと同じケースでは、以下のような動作をします。

最初の'G' → [0,99]区間を200クロック(4μs)かけて書き込み処理
　　↓ SPI 1byte後 (2μs + α)
次の '.'
　　↓ SPI 1byte後 (2μs + α)
次の 'G'  → 最初の[0,99]更新が終わっているため、改めて[0,99]更新を準備
　　　　　　 ここで書き込み完了レジスタ値は`99`なので、実際には更新しない
　　↓ SPI 1byte後 (2μs + α)
以下100要素目まで繰り返し

初回 1セット x 100word = 100書き込み

最初の1回だけ100wordを書き込み、2回目以降の同じ更新要求は包含済みとして省略できます。

AIにABC468Bの仕様変更実装を依頼する

検討した仕様変更をAIへ伝え、実装を更新してもらいました。

主な追加要望は次のとおりです。

書き込み完了区間の右端を保持する
完了済みの範囲は再度書き込まない
右端が伸びた場合は、未書き込み部分だけを更新する
実行中区間と保留区間の統合処理は維持する
BRAMの最終word受付と新しいGの受信が重なっても、更新要求を失わない
spi_target.vとbram0_8bit_access.vは変更しない
大きなFIFOは追加しない

完成したコードを確認した後、ForgeFPGA Workshopでの合成と実機試験へ進みます。

コードを確認する

完全なコードはGitHubへ掲載しています。

第23回コード全文

完了済み範囲への再書き込みを省略する

書き込みを完了した右端は、次のレジスタへ保持します。

reg       covered_valid;
reg [8:0] covered_end;

実行中区間も保留区間もない場合は、新しい要求とcovered_endを比較します。

else if (covered_valid &&
         request_start <= (covered_end + 9'd1)) begin
    if (request_end > covered_end) begin
        update_active  <= 1'b1;
        update_address <= covered_end + 9'd1;
        update_end     <= request_end;
    end
end else begin
    update_active  <= 1'b1;
    update_address <= request_start;
    update_end     <= request_end;
end

要求全体が完了済みなら何も行いません。右端だけが伸びる場合は、covered_end + 1以降だけを書き込みます。

区間の切り替えとSPI入力の重なりを処理する

現在区間の最終wordをBRAMへ渡すクロックと、新しいGを受信するクロックが重なる場合があります。

そのため、コードでは現在区間の完了と保留区間の回収を検出し、新しい要求を統合するか、空いた保留区間へ保存します。

assign update_finishing =
    bram_write_req && (update_address == update_end);
assign pending_consumed =
    update_finishing && pending_valid;
assign pending_recovering =
    !update_active && pending_valid && !bram_access_busy;

これにより、BRAM更新とSPI受信を並行させても、更新要求を取りこぼさない構成になっています。

合成結果

ForgeFPGA Workshopで合成と配置を行い、Bitstream生成まで成功しました。

監視状態の保存には、4k BRAMを1ブロック使用しています。

一方、CLB LUTの使用率は51.07%、CLBブロックの使用率は77.14%でした。

メモリ本体は専用BRAMへ移りましたが、clear、区間統合、保留、同期読み出しなどの制御回路が加わったため、Distributed RAM版より回路全体は大きくなっています。

実機試験

生成したBitstreamをShrike-Liteへ書き込み、50MHz内部クロック、4MHz SPIで実機試験を行いました。

clear中のSTART拒否、範囲のクリップ、最後の文字がGのケース、保留区間、完了済み範囲への再要求、処理途中のRESETなどを含む17ケースを実行し、すべてPASSしました。

SUMMARY PASS=17 FAIL=0 TOTAL=17 RESULT=PASS

最大負荷ケースは次の条件です。

M=100
D=99
S="G"を100文字

このケースでも、未監視マス数0を正しく返信できました。

ANSWER   ：0
VALID    ：1
ポーリング：6回

これで機能面の確認は完了です。

50MHzへわずかに届かない

最後に、20ns、50MHz制約でTiming Analysisを確認しました。

WNS                  -0.747ns
TNS                 -12.817ns
TNS Endpoints        25
Constrained Period   20.000ns
Achievable Period    20.746ns
Achievable Frequency 48.202MHz

実機試験はPASSしましたが、WNSは-0.747nsでした。

達成可能周波数は48.202MHzで、50MHz制約へわずかに届いていません。

BRAM版は機能として動作したものの、Timing上はまだ課題が残っています。