はじめに
前回までに、Shrike-Liteのボード上でRP2040とFPGAを接続する4bitパラレル通信を実装し、MicroPythonからPIOとDMAを使って送受信できるようにしました。
現時点では、4MHz SPIに比べると、相当見劣りする通信速度です。
ただし、通信そのものは安定して使える状態になっています。
そこで今回は通信の高速化からいったん離れ、ABC469のA問題とB問題を4bitパラレル通信で実装してみます。
どちらも問題自体は簡単なので、記事も軽めに進めます。
開発環境
今回使用した環境は次のとおりです。
- Shrike-Lite
- ForgeFPGA Workshop 6.54
- MicroPython
- Phase 5-A4版User C Module
- 4bitパラレル通信
- PIO clock 4MHz
MicroPython firmwareには、第28回で公開したA4 production版を使用しました。
shrike_parallel_c.version() == 0.1.0-a4
完全なsource codeと実機試験logは、GitHubで公開します。
ABC469A - Train Car
問題
N両編成の電車について、前からK両目の車両が、後ろから何両目かを求めます。
回答は次の式です。
N - K + 1
FPGAで実装する処理としては、かなり小さいものです。
通信形式
RP2040からFPGAへ、command、N、Kを送信します。
request = [0x03, N, K]
response = [STATUS, ANSWER]
たとえば、
N = 5
K = 2
なら、
request = [0x03, 0x05, 0x02]
response = [0x00, 0x04]
となります。
FPGA側の処理
FPGA側では、NとKを1byteずつ受信し、入力範囲を確認したあと、
ANSWER = N - K + 1
を計算します。
今回の計算回路は小さく、回路面積の大部分は4bitパラレル通信側です。
ABC469A コード全文
合成結果
合成結果は以下のようになりました。
到達可能周波数は65.643MHz、50MHz制約に対して、十分な余裕があります。
単純な引き算と加算だけでもCLBを半分以上使用していますが、ほとんどは問題を解く回路ではなく、4bitパラレル通信の制御回路です。
実機試験
次を確認しました。
- 公式sample 3件
- 境界case 2件
- 不正入力
- SOFT_RESET後の復帰
- 通信終了後のidle状態
結果は次のとおりです。
ABC469A_SUMMARY COUNT=17 PASS=17 FAIL=0 RESULT=PASS
4MHzで問題なく動作しました。ACがとれそうですね。
ABC469B - Isolated Seats
問題
長さNの文字列Sが与えられます。
o : 人が座っている
x : 人が座っていない
次の条件を満たす空席の数を求めます。
- その席が
x - 左隣が存在しない、または
x - 右隣が存在しない、または
x
文字列全体は保存しない
この問題では、各文字を判定するために必要なのは、現在位置と左右の3文字だけです。
そこで文字列全体を保存せず、3文字分の状態だけを保持します。
left
center
right
新しい文字を受信するたびに、
left == x
center == x
right == x
を確認し、すべて空席なら回答を1増やします。
判定後は窓を1文字右へ移動します。
left = center
center = right
端の扱い
左端と右端の外側には椅子がありません。
今回は、文字列の両側に仮想的なxがあるものとして処理しました。
x + S + x
最初は左側をxとして初期化し、すべての文字を受信したあと、右側にも仮想的なxを追加して最後の文字を判定します。
これにより、N=1も同じ流れで処理できます。
通信形式
ABC469Bは独立したprojectとして作成したため、問題専用commandにはABC469Aと同じ0x03を使用しています。
request = [0x03, N, S...]
response = [STATUS, ANSWER]
文字列はASCII codeで送信します。
'o' = 0x6F
'x' = 0x78
最大入力では、requestは102byteになります。
1byte command
1byte N
100byte S
ABC469B コード全文
合成結果
合成結果は以下のようになりました。
ABC469Aと比べると、3文字窓、文字数管理、回答counter、不正文字検出が追加されたため、CLB使用率は約10ポイント増えました。
到達可能周波数は68.639MHzで、50MHz制約を満たしています。
実機試験
次を確認しました。
- 公式sample
N=1- 左端と右端
- 連続する空席
N=100- 不正な
N - 不正文字
- SOFT_RESET後の復帰
- 通信終了後のidle状態
結果は次のとおりです。
ABC469B_SUMMARY COUNT=17 PASS=17 FAIL=0 RESULT=PASS
最大入力の、
N = 100
S = xxxxxxxxxx...（100文字）
でも正常に動作しました。
RESULT=100
TIME_US=1345
PARALLEL_CLK_HZ=4000000
こちらもACが取れますね。
A問題とB問題の比較
| 項目 | ABC469A | ABC469B |
|---|---|---|
| request長 | 3byte | 最大102byte |
| 主な処理 | N-K+1 |
3文字窓 |
| LUT | 519 | 571 |
| FF | 72 | 91 |
| CLB | 78 | 92 |
| CLB使用率 | 55.71% | 65.71% |
| Achievable Frequency | 65.643MHz | 68.639MHz |
| BRAM | 0 | 0 |
| 実機試験 | 17/17 PASS | 17/17 PASS |
A問題は演算回路が非常に小さく、ほぼ通信回路の面積です。
B問題では少し問題らしい処理が増えましたが、それでも文字列全体を保存せず、少数のregisterだけで処理できました。
今回のまとめ
今回は、第27・28回で作成した4bitパラレル通信を使い、ABC469AとABC469Bを実装しました。
ABC469Aは、受信した2つの値から回答を計算する小さな回路です。
ABC469Bは、文字列全体を保存せず、3文字窓を左から右へ流して空席を数えました。
どちらも4MHzで実機試験を行い、すべてPASSしました。
4bitパラレル通信はまだ速度面で改善の余地がありますが、AtCoder問題を載せる通信基盤としては使える状態になりました。
前回：
Shrike-LiteでAtCoder問題を解く(28)：4bitパラレル通信を作る(2) - Cで高速化する
次回：
Shrike-LiteでAtCoder問題を解く(30)：Interlude - ABC470の各問題をFPGA目線で見てみる
今回の全コード：
第29回 ABC469A コード全文
第29回 ABC469B コード全文