はじめに
今回はABC472B「Break a Stick」をShrike-Liteに実装してみます。
CPUなら配列と累積和で素直に解ける問題ですが、Shrike-Liteで実装するには
・最大100個の入力をどこへ置くか
・SPIの256byte境界をどうまたぐか
・小さなFPGAへ収めたうえでTimingをどう満たすか
が問題になりそうです。
少しネタバレですが、今回の実装は想定外に長い冒険になったため、前後編に分けます。
前編では、設計 → Icarus → DistRAM推論 → Synth / PNR → Timing PASSまで進め、最後に実機テストで予想外のFAILに遭遇します。
※ 今回もコード実装、テスト、ForgeFPGA Workshopの操作にはCodexの全面的なサポートを受けています。
※ 今回のコードや実装資料はGithubに上げてあります。文末のリンクからご参照ください。
問題
棒がN個の部分に分かれていて、それぞれの長さが
L_1, L_2, ..., L_N
として与えられます。
N-1箇所ある切れ込みのどこか1箇所で折ったとき、左右2本の長さの差の絶対値を最小にします。
制約は、
2 <= N <= 100
1 <= L_i <= 100000
です。
例えば、
N = 4
L = 5 2 3 8
なら、
5 | 2 3 8 -> |5 - 13| = 8
5 2 | 3 8 -> |7 - 11| = 4
5 2 3 | 8 -> |10 - 8| = 2
なので答えは2です。
最後の要素まで読まないと全長が分からない
前回のA問題は1文字だけ見れば答えが決まりました。今回はそうはいきません。
ある切れ目までの左側をleft、棒全体をtotalとすると、
right = total - left
diff = |left - right|
です。
ところがtotalは最後のL_iを受信するまで確定しません。そこで今回は、
入力中
├─ L_iを保存
└─ total_sumへ加算
全入力後
└─ 切れ目を先頭から順番に評価
という構成にしました。
最後の評価回路は、99個の切れ目を99個の比較器で一気に調べるのではなく、同じ計算回路を使い回します。
prefix = 0
best = INF
for i = 0 .. N-2:
prefix += L_i
right = total_sum - prefix
diff = abs(prefix - right)
best = min(best, diff)
かなりCPU的な処理です。
100個の入力はdistributed RAMへ置く
L_iの最大値は100000なので17bitで表せます。
L_i : 17bit
100個 : 1700bit
1700bitはShrike-LiteのFFには収まりませんので、distributed RAMに格納します。
reg [16:0] mem_ram [127:0];
を用意し、そのうちaddress 0～99を使用します。
最後の集計時readは同期式です。最初の設計では、
CALC_READ
↓
CALC_EVALUATE
という2状態にしました。
CALC_READでaddressを与え、次のclockのCALC_EVALUATEでread結果を評価します。1候補あたり2clockなので、最大N=100では、
2 × (N - 1)
= 198 clocks
です。
小さいメモリ資源と同じ計算回路を、順番に使っていく設計です。
また、全長は最大100000 × 100 = 10000000なので、累積値や処理経過、回答は24bit幅で計算します。
全体構成
前回の完全なストリーム変換とは違い、入力を覚える → 全部そろったら計算 → 答えを返すという小さな計算機になりました。
SPI入力は最大301byte
今回もいつものSPIテンプレートV3を使います。
SPI clock : 4 MHz
Mode : 0
8bit / MSB first
MISO : 1byte遅延
RP2040から送る論理入力は、
byte 0 : N
byte 1..3 : L_1
byte 4..6 : L_2
byte 7..9 : L_3
...
です。
L_iはFPGA内部では17bitですが、SPIでは24bit big-endianとして送ります。
最大入力は、
1 + 100 × 3
= 301 byte
です。
SPIテンプレートV3の1パッケージ上限は256byteなので、最大ケースでは、
256 byte + 45 byte
の2バーストに分割して送信ですね。
回答は別の4byteバースト
全入力を受信するとFPGAはCALCステートへ入ります。
CALCが終了すると、4byteバーストでRP2040 / MicroPythonに24bitの答えを返します。
MOSI: dummy dummy dummy dummy
MISO: 0x00 answer[23:16] answer[15:8] answer[7:0]
SPI V3は1byte遅延なので、先頭MISOはレジスタロード待ちのdummyバイト送信です。
ただし、入力の最後のbyteを送った直後には、まだFPGA側のCALCが終わっていません。
今回はFPGAからRP2040へ「計算完了」を通知する信号を用意していないため、MicroPython側でCALCが終わるまで10us待つことにしました。
time.sleep_us(10)
FPGAクロック50MHz設計では最大CALCが198clockなので、198 / 50MHz = 3.96 usです。
そのため、最悪ケースより十分長い10usを待ってから回答を読みます。
このあたりはCPUのような割り込みやOSのスケジューリングを考えなくてよいFPGAの強みですね。
必ず決められたクロック数で処理が完了します。
Icarusで524ケーステスト
今回も仕様をWORKへまとめ、CodexへVerilog実装とIcarusでのSIMテスト、Synth/PNRをお願いしました。
人間はそれぞれの作業の境目で状況を確認するだけです。
生成されたVerilogファイルをIcarusでテストした結果は、
524 cases PASS / 0 FAIL
でした。
主な確認内容は、公式3例、N=2 / 100、L_i=1 / 100000、合計長最大、答え0、最適切れ目が先頭 / 末尾、256 / 259 / 301byte入力、CS境界、連続transaction、決定的ランダム512件です。
CALC処理の最大クロック数も198clockを確認しました。
ここまでは順調です。
Synthしてみる
まず50MHz設定でSynthします。
大きなチェックポイントは、100要素のL_iが想定通りdistributed RAMに配置されるか、です。
以前の記事で紹介したように、ForgeFPGAではdistributed RAMの利用を明示的に指定することができません。
Synth時に「これはdistributed RAMに置くべきだな」と合成器が推測するように回路を記述する、という、間接的な方法をとります。
結果は、128×17bitの配列が、34個の64bit distributed RAMブロックにマップされました。
今回も大成功ですね。
Resourceは、
| Resource | 使用量 |
|---|---|
| LUT5 | 786 / 1120 |
| DistRAM用LUT5 | 272 |
| FF | 189 |
| CLB | 134 / 140 |
| Type=M | 34 / 40 |
| BRAM | 0 / 8 |
でした。
ただし、CLBは134 / 140、95.71%。かなり面積はギリギリです。
PNRしてみる
次にPNR(Place and Route)を進めます。
残念ながら、最初の50MHz制約PNRでは、
| 項目 | 結果 |
|---|---|
| WNS | -3.588 ns |
| TNS | -147.114 ns |
| Achievable Frequency | 42.396 MHz |
となり、Timing FAILでした。
そこでPLLの設定を変更し、clockを下げます。
ABC468Bで使った40MHz PLL設定を適用して、再度PNRした結果は、
| 項目 | 結果 |
|---|---|
| WNS | -0.324 ns |
| TNS | -0.910 ns |
| Achievable Frequency | 39.490 MHz |
でした。あら、制約を変えて再PNRしたところ、Achievable Frequency自体も39.490MHzになりました......
40MHzでも324ps足りません。
PLL Configuratorも自動操作する
ここで人間がコツコツPLLを調整して再テストをするのも面倒になってきたので、Codexに「PLL周波数調整をしてみて」とお願いしました。
過去にCodexにPLL周りの調整を依頼したことはありませんでしたが、FPGA Editor内のPLL ConfiguratorをUI Automationで開き、
- Required / Actual Output Frequency
- REFDIV / FBDIV
- POSTDIV1 / POSTDIV2
- Apply
- Save All
まで自動操作を成功させてくれました。
これで、
Timing結果
↓
新しいclockを決定
↓
PLL Configurator
↓
推奨PLL分周設定を入手
↓
SDC更新
↓
再Synth / PNR
まで自動で回せます。
次のclockは39.490MHzから決める
40MHz時のAchievable Frequencyは39.490MHzでした。
次のtarget周波数は、Achievable Frequency × 0.95を計算し、0.5MHz単位で切り下げることにしました。
今回の場合、以下の計算になります。
39.490 × 0.95
= 37.5155 MHz
切り下げ
= 37.5 MHz
37.5MHzでもTiming違反が起こる場合は、再度到達可能周波数の95%から0.5MHz単位切り下げの周波数で、自動ループ実行する、というルールも、Codexに伝えます。
また、タイミング制約を記述するSDCファイルも、PLL周波数設定に合わせて書き換えを行うように指示します。
37.5MHzでTiming PASS
37.5MHzで再Synth / PNRした結果、
| 設定clock | WNS | TNS | Achievable Frequency | 結果 |
|---|---|---|---|---|
| 50 MHz | -3.588 ns | -147.114 ns | 42.396 MHz | FAIL |
| 40 MHz | -0.324 ns | -0.910 ns | 39.490 MHz | FAIL |
| 37.5 MHz | +1.343 ns | 0 | 39.490 MHz | PASS |
となりました。
37.5MHzで最初の試行がPASSしたため、周波数探索は終了。bitstreamも生成できました。
さらにForgeFPGA Workshopを人力で再起動し、画面上でPLL Configurator、Resource Report、Timing Analysis、Floorplanを表示できることも確認しました。
ここで完成……のはずだった
この時点の構成は、
| 項目 | 結果 |
|---|---|
| 内部clock | 37.5 MHz |
| SPI | 4 MHz |
| distributed RAM | RAM64X1D ×34 |
| LUT5 | 786 / 1120 |
| FF | 189 |
| CLB | 134 / 140 |
| WNS | +1.343 ns |
| TNS | 0 |
| Achievable Frequency | 39.490 MHz |
| 最大CALC | 198 clocks |
| 最大CALC時間 | 5.28 us |
| Icarus | 524 PASS / 0 FAIL |
です。
シミュレーションPASS。DistRAM推論成功。PNR PASS。Timing PASS。bitstream生成済み。
あとはShrike-Liteの実機テストだけですね。
実機テストでこけました......
Shrike-LiteへFPGA bitstreamを書き込み、ThonnyからMicroPythonのテストを起動します。
しかし、19テストケースを実行した結果は、
SUMMARY PASS=16 FAIL=3 TOTAL=19 RESULT=FAIL
でした。FAILとなったテストは、
| Case | N | bytes / bursts | Result | Expected |
|---|---|---|---|---|
| best_at_first_cut | 3 | 10 / 1 | 7573991 | 98 |
| burst_boundary_259 | 86 | 259 / 2 | 1737 | 1001 |
| deterministic_random_100 | 100 | 301 / 2 | 76912 | 11636 |
いちばん上の best_at_first_cutは入力3個、具体的には
N = 3
L = [100, 1, 1]
expected = 98
の小さなテストケースです。
98が返ってくるはずなのに、なぜか7573991。
こんな数字が返ってくる理由が全く分かりません。
Icarusでは524/524 PASS。TimingもPASS。しかし実機ではFAIL。
まだ完成していませんでした。
前編まとめ
ABC472Bの実装は、CLB使用率が95%とリソース的には厳しく、また最高動作周波数の調整に少し手間がかかりました。
しかし無事に実装を終え、実機テスト前のテストはすべてPASS。
ここで終わるはずでした。
しかし実機はいう事を聞いてくれません。
後編では、設計制約すべてPASS、SIM試験もすべてPASSなのに、なぜ実機はコケるのかを追いかけます。
Debug回です......
前回：
Shrike-LiteでAtCoder問題を解く(40)：ABC472A - 1文字ずつストリーム変換する
次回：
Shrike-LiteでAtCoder問題を解く(42)：ABC472B 後編 - Timing PASSしたのに実機で壊れた
コード全文と実装資料：