はじめに
前回は、4組パック＋Prefix XOR版に残っていたタイミング違反を、Timing Analysis、Floorplan、合成後ネットリスト、元のVerilogコードから調べました。
その結果、最悪パスはPrefix XORや加算処理そのものではなく、残り組数や受信個数を管理し、最終判定へ続く回路であることが分かりました。
この管理回路だけを短くしても、Prefix XOR、XOR比較、加算を行うメイン処理はそのまま残ります。
そこでAIに検討を依頼したところ、次の構成を推奨してきました。
管理回路
-> 計算方法を見直し、残数計算から最終判定までの論理チェーンを短縮
最終パッケージの処理
-> 集計値の更新と、回答作成・異常検知・返信準備を別クロックへ分離
当初は、4組のデータを受信した後に行うPrefix XOR、XOR比較、加算の処理チェーンが、タイミング違反の主な原因だと想像していました。
しかし、実際のRTLと合成後ネットリストを確認すると、4組分の集計処理だけでなく、最終パッケージで続けて行っていた回答作成、受信個数の異常検知、SPI返信データの準備が、経路のかなりの長さを占めていました。
そこで、4組分の集計処理そのものは一つのクロックに残し、その結果をレジスタへ保存したうえで、最終回答と通信状態の確定を次のクロックへ分けます。
今回は、この提案内容を順番に確認し、RTLの変更、Timing Analysis、実機試験まで進めます。
今回も記事とコードの草稿作成にはAIを使用しています。
管理回路の論理チェーンを短くする
変更前は、総組数や残り組数を組合せ回路で毎回計算していました。
組合せ回路なので、処理に追加のクロックは必要ありません。
その一方で、信号は一つのクロック内に、減算、条件判定、加算、比較といった複数の回路を順番に通過する必要があります。
この論理チェーンが長くなり、今回のクリティカルパスを作っていました。
そこで、同じ計算を毎回繰り返さないように管理方法を変更します。
ストリーム中に変化しない値を事前に保存する
ABC467Cでは、Nを受信した後、データストリームを処理している間はNが変化しません。
したがって、次の値もストリーム中は変化しません。
total_pair_count = N - 1
expected_package_count = ceil((N - 1) / 4)
total_pair_countは処理する組の総数、expected_package_countは受信するデータパッケージの予定数です。
これらを、最後のAを受信するSEND_A1時に一度だけ計算して、その値をレジスタへ保存することにします。
total_pair_count_reg <= n_value - 1
expected_package_count_reg <= ceil((n_value - 1) / 4)
これにより、各パッケージを処理するたびに、Nから同じ値を作り直す必要がなくなります。
残り組数を状態として保存する
残り組数の管理方法も変更します。
変更前は、各パッケージを受信するたびに、次の減算で残り組数を求めていました。
remaining_pairs = total_pair_count - pair_count
この計算は、その後に続く有効組数の決定、処理済み組数の更新、最終パッケージ判定へつながっていました。
変更後は、残り組数そのものをremaining_pairs_regへ保存します。
SEND_A1時には、処理対象の総組数で初期化します。
remaining_pairs_reg <= n_value - 1
その後、データパッケージを処理するたびに、使用した組数だけ減らします。
remaining_pairs_regが5以上
-> 4組処理を行うはず
-> remaining_pairs_regを4減らす
remaining_pairs_regが1～4
-> 今回の処理が最終回のはず
-> remaining_pairs_regを0にする
毎回「総組数－処理済み組数」を計算するのではなく、残数そのものを状態として覚えておく方式です。
これによって、残数を求めるための広い減算回路を、管理回路のクリティカルパスから外せます。
また、remaining_pairs_regを処理の途中に挟むことで、残数計算から最終判定まで続いていた論理チェーンを切り、メイン処理側で想定している2段構成と処理のタイミングをそろえます。
メイン処理側も2クロックへ分ける
メイン処理側の処理も二つのクロックへ分けます。
当初は、1byteから4組を取り出し、Prefix XOR、XOR比較、加算を行う部分が、メイン処理側の長い論理チェーンになっていると考えていました。
しかしAIの解析では、その後に続く処理も、処理チェーンの長さに大きく影響していることが示されました。
確かに既存の回路では、最終パッケージを受信したクロックで、次の処理まで続けて行っていました。
受信した4組の処理 (Prefix XOR、XOR比較、加算)
↓
最終回答を作成
↓
受信した組数とパッケージ数を確認
↓
protocol_errorとcount_okを確定
↓
SPI返信データを準備
そこで、Prefix XORから累積値の更新までを第1段として、最終回答と通信状態の確定を第2段へ分けます。
途中のパッケージでは第1段だけを繰り返し、最終パッケージを受信したときだけ、第1段の次のクロックで第2段を実行することになります。
SEND_A1時：ストリーム設定
total_pair_count_regを設定
expected_package_count_regを設定
remaining_pairs_regを初期化
4組ごとの受信データ処理を開始する前に、ストリーム中に変化しない値と、残り組数の初期値を保存します。
第1段：4組分の集計と状態更新
データパッケージのrx_data_strobeが成立したクロックで、次の処理を行います。
rx_dataから4組を取り出す
↓
Prefix XOR
↓
diffの生成と無効位置のマスク
↓
package_cost
↓
answer_countを更新
pair_countを更新
package_countを更新
value_regを更新
remaining_pairs_regを更新
Prefix XOR、XOR比較、加算を含む4組分の主要演算は、この第1段で実行します。
また、remaining_pairs_regの更新と、最終パッケージかどうかの判定も、この段で行います。
更新後の残り組数が0になる場合は、最終パッケージの集計が完了したことを示すfinal_pendingを1にします。
第1段では、集計結果をレジスタへ保存するところまでを行い、最終回答や返信状態はまだ確定しません。
第2段：回答作成、異常検知、返信準備
次の内部クロックでは、第1段で更新したレジスタから処理を開始します。
まず、第1段で保存されたfinal_pendingの値を確認し、値が1であれば、最終回答を作成します。
answer_count
-> answer1 = n_value - answer_count
-> 小さい方を選択
-> answer_reg
これと並行して、受信した組数とパッケージ数が予定どおりだったかを確認します。
pair_count == total_pair_count_reg
package_count == expected_package_count_reg
その結果から、次のレジスタを確定します。
answer_reg
count_ok
protocol_error
answer_ready
tx_data
変更前後の違いを整理すると、次のようになります。
変更前
4組分のPrefix XORと集計
-> 最終回答の作成
-> 組数とパッケージ数の確認
-> 異常検知
-> SPI返信データの準備
変更後
第1段
-> 4組分のPrefix XORと集計
-> 各カウンタと残り組数を更新
-> レジスタへ保存
第2段
-> 更新済みレジスタから最終回答を作成
-> 受信個数の異常を確認
-> 通信状態とSPI返信データを確定
今回の改善の中心は、4組分の演算を細かくパイプライン化したことではありません。
最終パッケージ受信時に集計処理の後ろへ連結されていた、回答作成、異常検知、返信準備を次のクロックへ切り離したことです。
パイプライン化による副作用を確認する
処理を2クロックへ分けたことで、最終パッケージの集計結果が得られてから、その結果を返信用のtx_dataへ保存するまでに、内部クロック1クロック分の間が生じます。
この1クロックが何か問題を起こす可能性はあるでしょうか。
SPI通信部の動作タイミングを考える
SPI通信部の動作タイミングとFPGAの内部クロックについて情報を整理しましょう。
SPIクロック
-> 4MHz
-> RP2040からFPGAへ入力される外部信号
FPGA内部クロック
-> 50MHz
-> FPGA内部の各回路を動作させるクロック
SPI通信部が、SPIクロックをそのまま動作クロックとして使用しているわけではありません。
共通SPI回路のspi_target.vは、SPIクロックやCSなどの外部信号の変化をFPGA内部クロックで検出し、その検出結果に従って受信処理や送信処理を進めます。
RP2040
-> SPIクロックやCSを変化させる
↓
spi_target.v
-> 外部信号の変化を内部クロックで検出
↓
-> 受信bitを取り込む
-> 受信byteを確定する
-> 次の送信データを取り込む
-> 送信bitを更新する
SPIクロックはFPGA内部クロックとは独立して変化するため、その変化が内部クロックのどの周期で検出されるかは固定されません。
そのため、SPI回路が次の送信データを取り込む処理と、メイン処理側がtx_dataを更新する処理の前後関係を、内部クロックだけから単純に決めるのは難しそうです。
この1クロックでSPI側の送信準備が始まる可能性がある
SPI側の送受信動作タイミングと受信データ処理回路の動作タイミングは厳密に決まっているわけではない、ということは、新しく追加したパイプライン処理の途中でSPI側が送信用データの取り込みを行うかもしれません。
そのとき、何が起こるでしょうか。
第1段の結果を第2段のレジスタに取り込むクロックでSPI側が送信データの取り込みを行った場合を考えましょう。
送信用データの取り込み元は第2段の結果保存レジスタです。
そのクロックの直前では、第2段レジスタの入力までは結果が届いていますが、まだレジスタの値は古いままです。
つまりクロックの瞬間にSPI側から見えている第2段レジスタ出力は、それ以前に第2段レジスタに保存されていた何らかの値になります。
そのままでは、その「何らかの値」を答えとして返送してしまうかもしれない、ということになります。
第1段終了後には返信内容が分かっている
このような想定外動作を防ぐためには何をすればいいでしょうか。
大きなヒントは、第2段レジスタの更新前に、すでに正しい答えは第2段レジスタの入力まで届いている、ただ、レジスタの更新が間に合っていないだけ、ということです。
つまり、第2段レジスタの更新が間に合っていない1クロックの間だけ、正しい答えをバイパスしてSPI側に示せれば、いつSPI側で取り込みが行われても大丈夫になるはずです。
では、具体的にはどのような実装にすればいいでしょうか。
final_pending中は返信ヘッダを直接渡す
問題の1クロックの間だけ有効になる信号があれば、簡単に実装できそうです。
探してみると第1段にちょうどいいレジスタが見つかります。final_pendingです。
このレジスタは名前の通り、「最終パッケージを受信して第1段処理まで完了した」ことを第2段に伝えるためのレジスタです。
そこで、final_pendingが1になっている間だけ、第2段のtx_dataレジスタを迂回し、すでに得られているfinal_reply_headerをSPI回路へ直接渡すルートを開通させればいいはずです。
assign spi_tx_data =
(final_pending && !rx_data_strobe) ?
final_reply_header : tx_data;
正常動作では、final_pendingが1の間にrx_data_strobeが立つことはありません。!rx_data_strobeは、両方が同時に立つ異常時に、安全策としてバイパスを遮断するための追加条件です。
さて、この仕組みで、SPI回路が送信データを取り込む正確なタイミングがわからなくても、取り込まれる可能性がある期間には常に正しいデータを見せることができるはずです。
main.v側だけでの対応ができますから、共通SPI回路であるspi_target.vの変更も不要です。
AIへ2クロック版の実装を依頼する
設計方針が決まったため、集計処理と最終確定処理を別クロックへ分けるRTL変更をAIへ依頼しました。
主な依頼内容は次の通りです。
先ほどのタイミング調査結果に基づき、
ABC467C Prefix XORバースト版のRTLを2段構成へ変更してください。
ForgeFPGA Workshopでの合成、配置配線、bitstream生成は私が行います。
SEND_A1時に、次の値をレジスタへ保持してください。
- total_pair_count
- expected_package_count
- remaining_pairs
第1段では、受信した1byteに対して次の処理を行い、
結果を各レジスタへ保存してください。
- Prefix XOR
- diffの計算
- package_costの計算
- answer_countの更新
- pair_countの更新
- package_countの更新
- value_regの更新
- remaining_pairs_regの更新
最終パッケージを処理した場合は、final_pendingをセットしてください。
第2段では、次のクロックで更新済みレジスタだけを使用し、
次の値を確定してください。
- 最終回答
- pair_countとpackage_countの一致判定
- answer_reg
- count_ok
- protocol_error
- answer_ready
- tx_data
第1段の組合せ値を、第2段の処理へ直接渡さないでください。
また、処理を2クロックへ分けたことで、
最終結果が得られてからtx_dataが更新されるまでに
1クロックの間が生じます。
この間にSPI通信部が送信データを取り込んでも、
最初の返信byteから正しい値を返せるようにしてください。
final_pendingが1で、rx_data_strobeが0の間は、
tx_dataを迂回してfinal_reply_headerを
spi_tx_dataへ直接渡すバイパスを設けてください。
rx_data_strobeが同時に立った場合は、
安全策としてバイパスを遮断してください。
外部SPIプロトコルは変更しないでください。
共通SPI回路のspi_target.vも変更せず、
main.v側だけで対応してください。
SystemVerilog固有構文を使用せず、
Verilog-2001で記述してください。
既存コメントを削除せず、
追加部分には日本語コメントを入れてください。
Git操作は行わないでください。
生成されたVerilogコードを確認する
変更したのはmain.vです。
コード全文は以下のリンクにあります。
ここでは、生成されたコードのうち、2段化に関係する主要な変更箇所を確認します。
ストリーム中に変化しない値を保存する
最初に、総組数、予定パッケージ数、残り組数を保持するレジスタと、第2段の実行を指示するfinal_pendingが追加されています。
reg [17:0] total_pair_count_reg;
reg [16:0] expected_package_count_reg;
reg [17:0] remaining_pairs_reg;
reg final_pending;
これらの初期値は、最後のAを受信するSEND_A1で保存します。
SEND_A1: begin
// A_1の最終値を0と仮定する候補を開始する。
value_reg <= 1'b0;
answer_count <=
rx_data[0] ? 18'd1 : 18'd0;
pair_count <= 18'd0;
package_count <= 17'd0;
answer_reg <= 18'd0;
reply_index <= 2'd0;
answer_ready <= 1'b0;
count_ok <= 1'b0;
protocol_error <=
(n_value < 18'd2);
stream_active <=
(n_value >= 18'd2);
tx_data <= 8'h00;
total_pair_count_reg <=
stream_total_pair_count;
expected_package_count_reg <=
stream_expected_package_count_wide[16:0];
remaining_pairs_reg <=
stream_total_pair_count;
final_pending <= 1'b0;
end
これにより、データパッケージを受信するたびに、Nから総組数や予定パッケージ数を作り直す必要がなくなります。
第1段で集計結果をレジスタへ保存する
ストリーム処理中にデータパッケージを受信すると、Prefix XORや不一致数の集計結果を各レジスタへ保存します。
// 第1段：1byte分を集計して既存レジスタへ格納する。
answer_count <= answer_count_next;
pair_count <= pair_count_next;
package_count <= package_count_next;
value_reg <= last_value_next;
remaining_pairs_reg <= remaining_pairs_next;
if (final_package) begin
// 最終回答と個数整合判定は次クロックへ渡す。
final_pending <= 1'b1;
end
途中のパッケージでは、この第1段だけを繰り返します。
最終パッケージでは、集計結果を保存すると同時にfinal_pendingを1にします。最終回答や通信状態は、このクロックではまだ確定しません。
final_pendingの次のクロックで最終結果を確定する
次の内部クロックでは、更新済みの集計レジスタを使って第2段を実行します。
end else if (final_pending) begin
if (rx_data_strobe) begin
// pending中の次byteは余分なデータとして明示的に拒否する。
count_ok <= 1'b0;
protocol_error <= 1'b1;
answer_ready <= 1'b0;
stream_active <= 1'b0;
tx_data <= 8'h00;
final_pending <= 1'b0;
end else begin
// 第2段：更新済みの集計レジスタから最終結果を確定する。
answer_reg <= final_answer;
reply_index <= 2'd0;
answer_ready <= 1'b1;
count_ok <= final_count_match;
protocol_error <= protocol_error | ~final_count_match;
stream_active <= 1'b0;
tx_data <= final_reply_header;
final_pending <= 1'b0;
end
end
正常時には、最終回答、受信個数の一致判定、通信状態、返信ヘッダをここで確定します。
一方、final_pending中に新たな受信byteが来た場合は、余分なデータとして拒否し、protocol_errorを1にします。
第2段の完了前は返信ヘッダを直接渡す
第1段と第2段の間にSPI回路が送信データを取り込む場合に備えて、SPI回路へ渡す信号にはバイパスが追加されています。
assign spi_tx_data =
(final_pending && !rx_data_strobe) ?
final_reply_header : tx_data;
final_pending中は、第2段のtx_dataを迂回し、更新済みの集計レジスタから作成したfinal_reply_headerを直接渡します。
次のクロックで第2段が完了すると、同じ返信ヘッダがtx_dataへ保存され、final_pendingは0に戻ります。
これにより、SPI回路が送信データを取り込むタイミングにかかわらず、最初の返信byteから正しいヘッダを返せる構成になっています。
生成されたコードを確認すると、管理回路の再構成、第1段と第2段の分離、SPI返信データのバイパスが、依頼した方針どおりに実装されています。
また、変更はmain.v内に収まり、共通SPI回路のspi_target.vや外部SPIプロトコルは変更されていません。
2段版のTiming Analysis
2段版をForgeFPGA Workshopで再合成し、配置配線まで実行しました。
先ほどと同じようにTiming Analysisを開き、PNR_TIMING.logの先頭を確認します。
Timing Summaryは次の通りです。
WNS +573ps
TNS 0ps
TNS Endpoints 0
Constrained Period 20000ps
Achievable Period 19426ps
Achievable Frequency 51.477MHz
最悪パスの詳細は次の通りです。
Propagation time 19231ps
Logic / Route 48.0% / 52.0%
Logic stage 11
Slack +573ps
変更前と比較すると、次のようになります。
| 項目 | 変更前 | 2段化後 |
|---|---|---|
| Achievable Period | 32.888ns | 19.426ns |
| Achievable Frequency | 30.406MHz | 51.477MHz |
| WNS | -12.889ns | +0.573ns |
| TNS | -909.280ns | 0ns |
| 違反Endpoint | 123 | 0 |
| 最悪パスの論理段数 | 17 | 11 |
WNSが正の値になり、TNSと違反Endpointは0になりました。
これは、確認対象となったすべての経路が50MHzの期限に間に合ったことを示します。タイミング違反は解消しました。
ただし、最小の余裕を示すWNSは573psです。
当初の目標としていた2ns程度の余裕には届かず、かなりぎりぎりです。
それでも、すべてのendpointで50MHz制約を満たし、TNS=0となったので、これでヨシとします。
CLB使用率は97.14%になった
2段版のResource Reportは次の通りです。
LUT使用率は46.88%、CLB FF使用率は16.07%ですが、CLB使用率は97.14%です。
LUTやFFは個々の回路資源の数です。一方、CLBは、それらの回路資源と配線をまとめて収容する物理的な区画です。
そのため、LUTとFFの総数に余裕があっても、必要な組み合わせを各CLBへ配置できず、CLB使用率が先に高くなる場合があります。
残りは4 CLBしかありません。
タイミング制約には届きましたが、回路規模の面でもShrike-Liteの限界にかなり近づきました。
Shrike-Lite実機で確認する
生成したbitstreamをShrike-Liteへ書き込み、前回と同じMicroPythonテストを実行しました。
[shrike_fpga] flashing: abc467c_prefix_xor_burst.bin
[shrike_flash] FPGA programming done.
CONFIG SPI_BAUDRATE=4000000 PACKAGE_SIZE=256 TIME_LIMIT_US=2000000 MAX_N=262143 PROTOCOL_BITS=18
公式サンプル、末尾の有効組数、転送パッケージ境界、疑似乱数を含む12件は、すべてPASSしました。
FUNCTION_SUMMARY PASS=12 FAIL=0 TOTAL=12
主な境界ケースも正常です。
NAME=tail_valid_2 N=3 ... PASS
NAME=tail_valid_3 N=4 ... PASS
NAME=tail_valid_4 N=5 ... PASS
NAME=second_package_tail_valid_1 N=6 ... PASS
NAME=package_boundary_n1005 N=1005 ... PASS
NAME=package_boundary_n1006 N=1006 ... PASS
すべてのケースで、通信状態は次の値でした。
VALID=1
COUNT_OK=1
最初の返信byteも0xC0となり、2段化で懸念していた返信データの取り違えは発生しませんでした。
18bit通信上限まで再確認する
拡大試験もすべてPASSしました。
EXPAND N=1024 PACKAGES=2 TIME_US=910 PASS
EXPAND N=2048 PACKAGES=3 TIME_US=1534 PASS
EXPAND N=4096 PACKAGES=5 TIME_US=2799 PASS
EXPAND N=8192 PACKAGES=9 TIME_US=5333 PASS
EXPAND N=16384 PACKAGES=17 TIME_US=10411 PASS
EXPAND N=32768 PACKAGES=33 TIME_US=20568 PASS
EXPAND N=65536 PACKAGES=65 TIME_US=40880 PASS
EXPAND N=131072 PACKAGES=129 TIME_US=81500 PASS
EXPAND N=262143 PACKAGES=257 TIME_US=162739 PASS
最大値でも通信状態は正常でした。
VALID=1
COUNT_OK=1
ANSWER=0
探索の終了理由は2秒制限ではありません。
SEARCH_BOUNDARY PASS_N=262143 FAIL_N=NONE LIMIT_REASON=18BIT_PROTOCOL_MAX
BENCHMARK_ESTIMATE TIME_LIMIT_US=2000000 AT_LEAST_N=262143 PROTOCOL_MAX_REACHED=1
2段版でも、N=262,143を約0.163秒で処理できました。
最終パッケージの処理に内部クロック1周期が追加されましたが、4MHz SPIの1byte間隔は2µs、内部クロックは20nsです。
追加された20nsは全体の処理時間から見れば非常に小さく、測定結果への影響は見えませんでした。
最終的な上限は、処理速度ではなく18bit通信形式で表現できるNの最大値になりました。
今回のまとめ
今回は、4組パック＋Prefix XOR版に残っていたタイミング違反へ対応しました。
管理回路の計算方法を見直し、4組分の集計と、最終回答・異常検知・返信準備を別クロックへ分けた結果、50MHz制約を満たすことができました。
WNS -12.889ns -> +0.573ns
TNS -909.280ns -> 0ns
Logic stage 17 -> 11
実機試験は12件すべてPASSし、18bit通信上限のN=262,143も約0.163秒で処理できました。
一方、CLB使用率は97.14%となり、タイミングだけでなく回路規模もShrike-Liteの限界に近づいています。
実機で動作することと、Timing Analysisで動作が保証されることは別です。今回はタイミング、回路規模、実機動作を確認し、ABC467Cの4組パック＋Prefix XOR版を完成させることができました。
ようやく胸を張って「ACです」と言い切れるところにたどり着けました。
ABC467C、想定していたより手ごたえがありましたね。
次回は、ABC468の問題を見ていく予定です。お楽しみに。
前回：
Shrike-LiteでAtCoder問題を解く(17)：ABC467C - Adjacent Sums (easy)（タイミング違反解消編・前編）
次回：
Shrike-LiteでAtCoder問題を解く(19)：Interlude - ABC468の各問題をFPGA目線で見てみる
今回の最終コード：
第17～18回コード全文