はじめに
前回は、ABC472の各問題をShrike-Liteや仮想理想FPGAを中心に、CPU、AVX、GPUも含めた計算機アーキテクチャの視点から眺めました。
今回の記事では、A問題「A」をShrike-Liteへ実装します。
処理そのものは非常に簡単です。
入力された文字を、
1文字受信したら、その場で1文字変換して返す
ストリーム処理にしてみます。
※ 今回もコード実装やテストレポート生成にはCodexの全面的なサポートを受けています。
※ 今回のコードや実装資料はGitHubに上げてあります。文末のリンクからご参照ください。
※ 本記事のテストや測定は筆者のローカル環境（Win 11, i7-12700H, Shrike-Lite V1.0 R0.5）で行っています。
問題
英大文字からなる文字列Sが与えられます。
Sのうち、A以外の文字をすべて.へ置き換えて出力します。
制約は、
1 <= |S| <= 100
Sは英大文字のみ
です。
例えば、
ATCODER
なら、
A......
を出力します。
1文字ずつ変換する
今回の処理は、文字列全体を見なくても決められます。
ある1文字cについて、
c == 'A' ?
├─ Yes → 'A'
└─ No → '.'
とすれば終わりです。
ASCIIコードでは、
'A' = 0x41
'.' = 0x2E
なので、FPGA側の処理はほとんど8bitの比較と選択だけです。
入力文字列の長さは最大100文字ですが、FPGA内部に100文字分のバッファを用意する必要もありません。
入力文字0 → 変換 → 出力文字0
入力文字1 → 変換 → 出力文字1
入力文字2 → 変換 → 出力文字2
...
と、同じ回路を使い続ければ十分です。
A問題らしい、小さな専用回路になりそうです。
SPI通信
今回もSPIテンプレートV3を使います。
通信条件は、
SPI clock : 4MHz
Mode : 0 (CPOL=0, CPHA=0)
Data : 8bit / MSB first
です。
RP2040がMaster、FPGAがTargetです。
標準入力の文字列はRP2040側でASCII byte列にして、そのままFPGAへ送ります。
例えばATCODERなら、
41 54 43 4F 44 45 52
です。
FPGA側では受信した各byteを、
0x41 ('A') → 0x41 ('A')
その他 → 0x2E ('.')
へ変換します。
1バーストのやり取り
SPIには今回、REQ/ACKのような別のハンドシェイク信号はありません。
CSをLowにすると通信開始、Highに戻すと通信終了です。
1文字列を、最後のflush byteまで含めて1回のCS Low区間で送ります。
SPIは全二重なので、RP2040がMOSIで1byte送っている同じ8クロックの間に、MISOからも1byte受け取れます。
ただしFPGAがS[0]を変換できるのはS[0]を受信し終わった後です。
そのためR[0]を返せるのは次のbyte転送時になります。
byteの並びだけを見ると、
MOSI: S[0] S[1] S[2] ... S[N-1] flush
MISO: dummy R[0] R[1] ... R[N-2] R[N-1]
となります。
最後の結果だけは次に送る入力byteがないので、flushを1byte送ってR[N-1]を回収します。
通信終了時にCSをHighへ戻すとMISOは無効になり、FPGA側の返信byteもdummyへ戻します。
これで前回の最後の結果が、次の通信の先頭へ混入しません。
今回の実装は、このSPIの全二重通信を使って「1文字送りながら、1文字前の結果を受け取る」 ところがポイントです。
RTL
実際のmain.vでも、保持している問題データは返信用の1byteだけです。
localparam [7:0] DUMMY_BYTE = 8'h00;
localparam [7:0] ASCII_A = 8'h41;
localparam [7:0] ASCII_DOT = 8'h2e;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
tx_data <= DUMMY_BYTE;
end else if (!spi_miso_en) begin
tx_data <= DUMMY_BYTE;
end else if (rx_data_strobe) begin
tx_data <= (rx_data == ASCII_A) ? ASCII_A : ASCII_DOT;
end
end
rx_data_strobeが来るたびに受信byteを1回だけ判定し、その結果を次のMISO応答に設定します。
CSが非選択の間はtx_dataをdummyへ戻しています。
これによって、前回のトランザクションの最後の結果が次のトランザクション先頭へ混入しないようにしています。
文字列バッファも、問題固有の複雑なFSMもありません。
実装とテストはCodexにおまかせ
今回も実装とテストはCodexにお願いしました。
依頼内容はWORK_abc472a.mdへまとめ、Codexへ渡す最初の指示もCODEX_PROMPT_abc472a.txtとして保存しています。
今回の作業では、RTL実装・テスト、Synth / PNR、実機時間測定の準備を、段階ごとにWORK / PROMPTへ分けて依頼しています。
主な生成ファイルは、
ffpga/src/main.v
ffpga/src/spi_target.v
firmware/micropython/abc472a_test.py
sim/tb_abc472a.v
sim/run_iverilog.ps1
REPORT_abc472a.md
です。
興味がある方は文末のリンクからファイルを参照してください。
Icarus VerilogではSPI通信まで含めて35ケースを自動テストしました。
ここもCodexに自動実行してもらっています。
結果は、35 cases PASS / 0 FAIL です。
公式サンプル3件、A-Z全26文字、長さ1・100、ランダムケースに加え、
- 先頭dummy
- 1byte応答遅延
- 最後のflush
- 連続トランザクション
などの通信プロトコル上の特殊ケースも確認しています。
Synth / PNR / bitstream生成もCodexまかせにしてみる
今回はForgeFPGA Workshopのプロジェクト作成からSynth / PNR / bitstream生成までCodexにお願いしてみました。
前回のABC471Aプロジェクトをひな形として、同じShrike-Liteデバイス、I/O割当、50MHz制約を使用しています。
ForgeFPGA Workshopには内蔵Tclコマンドがあり、今回はその通常フローを使ってSynth / PNR / bitstream生成まで自動実行できました。
結果は次の通りです。
| 項目 | 結果 |
|---|---|
| LUT5 | 40 / 1120 |
| FF | 31 |
| CLB | 9 / 140 |
| BRAM | 0 / 8 |
| WNS | +12.893 ns |
| TNS | 0 |
| Achievable Frequency | 140.726 MHz |
50MHz制約には十分な余裕があります。
予想通り、問題固有の回路は非常に小さく、回路の大部分はSPI周辺です。
完成した.ffpgaプロジェクトファイルをForgeFPGA Workshopで開くと、いつもの合成結果画面やFloorplanを見ることができます。
小さな回路ですから、Shrike-Liteにも十分収まっていますね。
到達可能周波数も140MHz以上、タイミング制約にも大きな余裕があります。
実機テスト
生成したbitstreamをShrike-Liteへ書き込み、ThonnyのMicroPythonから実機テストしました。
公式3例に加えて、
- 長さ1
- 長さ100
- 全文字
A -
Aなし -
A複数 - 先頭だけ
A - 末尾だけ
A - A-Z全26文字
- 決定的ランダムケース
など17ケースを連続実行しています。
結果は、
SUMMARY PASS=17 FAIL=0 TOTAL=17 RESULT=PASS
でした。
FPGAは最初に1回だけreset / flashし、その後17ケースを連続実行しています。
したがって、別トランザクションの結果が混入しないことも実機で確認できています。
最大長100文字の実行時間
AtCoderの最大入力長100文字について、fpga_convert()の処理時間を20回測定しました。
測定対象には、
- RP2040側の入力文字チェック
- ASCII byte列への格納
- SPI 1バースト転送
- dummy / flushを含む応答回収
- 結果byte列の文字列化
を含みます。
bitstream書き込み、FPGA reset、SPI初期化、print出力は測定外です。
結果は、
BENCHMARK LEN=100 RUNS=20
MIN_US=3827
AVG_US=3849
MAX_US=3922
RESULT=PASS
でした。
最大ケース|S| = 100でも、実機処理時間は約3.8msです。
AtCoderの2秒制限に対しては十分な余裕があります。
ACがもらえそうですね。
まとめ
ABC472AをShrike-Liteへ実装しました。
今回の処理は、単純なストリーム変換でしたので、スムーズに実装テストまで完了しました。
また今回は、CodexにRTL実装とIcarusテストだけでなく、ForgeFPGA WorkshopのSynth / PNR / bitstream生成までお願いできることも確認できました。
おまけ：AtCoder提出用Verilogサンプル
せっかくなので、AtCoderへ提出できるVerilog版も考えてみます。
いつもの通り、クロックも遅延制約も配線面積も忘れて、ACをとることだけを目的にVerilog実装します。
module main;
integer c;
initial begin
while (!$feof(32'h80000000)) begin
c = $fgetc(32'h80000000);
if (c == 10 || c == -1) begin
// 改行またはEOFなら何も出力しない
end
else if (c == 8'h41) begin
$write("A");
end
else begin
$write(".");
end
end
$write("\n");
end
endmodule
AtCoder提出はしていませんので動作保証はありません。ご了承ください。
前回：
Shrike-LiteでAtCoder問題を解く(39)：Interlude - ABC472の各問題をFPGAなどの視点で見てみる
次回：
Shrike-LiteでAtCoder問題を解く(41)：ABC472B 前編 - DistRAMに100個の長さを覚える
）
コード全文と実装資料：(今回もコード実装やそのドキュメント化は生成AIの助けを借りています)
第40回コード全文と実装資料