はじめに
前回は、ABC467Cの入力を1byteに4組詰め、FPGA側でPrefix XORを使ってまとめて処理しました。
4MHz SPIのバースト転送と組み合わせることで、18bit通信形式の上限であるN=262,143を約0.163秒で処理できました。
機能テストはすべてPASSしましたが、Timing Analysisを確認すると、FPGAの50MHzの内部クロックに対して大きなタイミング違反が残っていました。
このままでは50MHzでの動作は保証されませんよ、という警告を受けている状態です。
そこで今回は、回路合成やBitstream生成時に出力されるログや各種ファイルを調べ、タイミング違反の原因と改善方針を確認します。
今回も記事とコードの草稿作成にはAIを使用しています。
50MHzのタイミング制約を追加する
まずは前回作成したプロジェクトをプロジェクトフォルダごとコピーし、フォルダ名・ffpgaファイル名をリネームします。
今回はabc467c_prefix_xor_burst_pipelineとしました。
ffpgaファイルを開き、ForgeFPGA WorkshopのTiming Analysisを確認すると、前回同様に次の結果が表示されるはずです。
Achievable Period 32.888ns
Achievable Frequency 30.406MHz
ただし、前回の終了時点では、50MHzクロックであることをプロジェクトへ設定していませんでした。
そこで、まずはForgeFPGA Workshopに、clkが50MHzで動作するという制約を設定します。
具体的には、制約ファイル（SDCファイル）をプロジェクトに追加します。
ForgeFPGA Workshop画面左下のSources画面上で右クリック、New Timing Constraintを選択します。
Timing Constraints Name画面が開きますので、名前を付けてCreateします。
Sources画面のツリーにsdcファイルが作成されるはずなので、ダブルクリックして編集画面を開き、以下の制約を入力して保存します。
create_clock -name clk {clk} -period 20.000
これは、clkへ周期20ns (= 50MHz)のクロック制約を設定する記述です。
ここまででタイミング制約の追加は完了です。
再配置・再配線を行う
制約ファイルを編集すると、Generate Bitstreamインジケーターが未完了ステータスに戻っています。
再度Bitstream生成を行いましょう。ボタンを押すと "変更をセーブしますか" の確認メッセージが表示されるので"Yes"で進めます。
これで、ForgeFPGA Workshopは50MHzの制約を満たすことを目標に、回路の配置や配線をやり直してくれます。
Timing Analysis結果の読み方
Bitstreamの再生成が完了したら、ForgeFPGA WorkshopのTiming Analysisを開きます。
画面には、配置配線後のタイミング解析結果であるPNR_TIMING.logが表示されます。
PNR_TIMING.logには多くの情報が記録されていますが、まずは先頭付近のTiming Summaryを確認します。
Timing Summary
==============
POST-ROUTE
Group No. Clocks No. Clock Pairs WNS(ps) TNS(ps) TNS Endpoints
----------- ---------- --------------- ------- ------- -------------
<DEFAULT> 1 1 -12889 -909280 123
ここで注目するのは、次の三つです。
| 項目 | 今回の値 | 意味 |
|---|---|---|
WNS |
-12889ps |
最も厳しい経路で、期限にどれだけ間に合わなかったか |
TNS |
-909280ps |
タイミング違反があるEndpointの不足時間を合計した値 |
TNS Endpoints |
123 |
タイミング違反が見つかった終点の数 |
psはピコ秒です。1000ps = 1nsなので、今回のWNSは次の値です。
-12889ps = -12.889ns
WNSはWorst Negative Slackの略です。
Slackは、信号が次のクロックまでに到着する期限に対して、どれだけ余裕があるかを表します。
- 正の値：期限より早く到着した
- 0：ちょうど期限に到着した
- 負の値：期限に間に合わなかった
今回はWNSが負の値です。
50MHzの制約を指定して再配置・再配線しても、最も厳しい経路では期限に間に合わなかったことが分かります。
Endpointは、組合せ回路を通ってきた信号が、次のクロックまでに到着しなければならない経路の終点です。多くの場合は、レジスタの入力などが該当します。
この時点では総Endpoint数は表示されていませんが、123個のEndpointでタイミング違反が見つかったことが分かります。
続いて、Clocksを確認します。
Clocks
======
Clock Constrained Period(ps) Achievable Period(ps) Achievable Frequency(MHz)
clk 20000 32888 30.406
各項目の意味は次の通りです。
| 項目 | 今回の値 | 意味 |
|---|---|---|
Constrained Period |
20000ps |
SDCで指定した目標周期20ns |
Achievable Period |
32888ps |
配置配線後の回路で必要と見積もられた周期約32.888ns |
Achievable Frequency |
30.406MHz |
約32.888nsから換算した到達可能周波数 |
目標は50MHzですが、配置配線後の見積もりは約30.4MHzです。
前回、制約を追加する前のTiming Analysisに表示されていた数値と同じ結果になりました。
今回は20nsの制約を与えているため、50MHzに対してどれだけ不足しているかが、WNSやTNSとして明確に表示されています。
次に、Clock Relationshipsを確認します。
Clock Relationships
===================
From Clock To Clock Group Endpoints WNS(ps) TNS(ps) TNS Endpoints
-------------- -------------- ------------------ ----------- ---------- --------- -------------
clk clk <DEFAULT> 593 -12889 -909280 123
ここには、これまで確認したWNSやTNSに加えて、解析したEndpointの総数も表示されています。
| 項目 | 今回の値 | 意味 |
|---|---|---|
Endpoints |
593 |
解析した終点の総数 |
TNS Endpoints |
123 |
タイミング違反が見つかった終点の数 |
今回のTiming Analysisでは、593個のEndpointが解析され、そのうち123個のEndpointでタイミング違反が見つかっています。
さらに下へ進むと、最も厳しい経路の詳細が表示されています。
Path 2709:
Slack (not met): -12889ps
Path type: SETUP
Requested period: 20000ps
+ Delay of the capturing clock: 2305ps
- Clock uncertainty: 150ps
= Required time: 22155ps
- Propagation time: 32726ps (52.8% logic, 47.2% route, logic stage 17)
- Delay of the launching clock: 2318ps
= Slack: -12889ps
Path 2709は、今回の解析でSlackが最も小さい経路です。
このような、回路全体の動作周波数を制限している最も遅い経路をクリティカルパスと呼びます。
この経路では、信号が出発側のレジスタから組合せ回路を通り、到着側のレジスタへ届くまでに、32726ps、約32.7nsかかっています。
内訳は次の通りです。
Logic / Route 52.8% / 47.2%
Logic stage 17
-
Logic：LUTや加算・比較回路などを通過する時間 -
Route：回路ブロック間の配線を通過する時間 -
Logic stage：この経路で通過する論理段数
約32.7nsのうち、52.8%が17段の論理回路を通過する時間で、47.2%が回路ブロック間の配線を通過する時間だと解析されています。
多くの論理回路を連続して通過し、それらを結ぶ配線にも時間がかかることで、全体として遅い経路になっているようです。
この結果から、一部の論理や配線だけを少し改善しても、約12.9nsの不足を解消するのは難しそうです。
そこで、長い組合せ経路の途中にレジスタを追加し、複数のクロックへ分割する方法を考えます。
クリティカルパスを分割する
今回は、クリティカルパスの途中にパイプラインレジスタを追加し、長い処理を複数のクロックへ分割する方法を検討します。
経路は短くなりますが、後段のレジスタへ結果が届くまでには、これまでより追加のクロックが必要になります。
このレイテンシ増加は問題にならないでしょうか。
数クロック使ってもSPI通信には間に合う
長い組合せ経路を分割すると、1byteの処理に使うFPGA内部クロック数は増えます。
ここで、SPI通信とFPGA内部クロックの速さを比較します。
SPIクロックは4MHzです。
SPIでは1byteを8bitで転送するため、1byteの転送時間は次の通りです。
8bit / 4,000,000bit/s = 2µs
一方、FPGA内部クロックは50MHzなので、1クロックは20nsです。
2µs / 20ns = 100
SPIで次の1byteが到着するまでに、FPGA内部では約100クロック進みます。
現在は、受信した1byteに対する計算を1クロックで終わらせようとしています。しかし、SPI通信が次のデータを送ってくるまでには、100クロック分の処理時間があります。
たとえば、処理を2クロックに分けても、必要な時間は40nsです。
20ns × 2クロック = 40ns
これは、次のSPI byteが到着する2µsより十分に短い時間です。
つまり、1byteを受信してから結果が確定するまでのレイテンシを数クロック増やしても、2µsごとに次のbyteを受け取る通信スループットは維持できます。
今回はこの余裕を使い、長い処理を複数クロックへ分けます。
クリティカルパスを詳しく調べる
クリティカルパスの途中へパイプラインレジスタを追加する方針は決まりました。
次に考える必要があるのは、具体的にどこへ、どのようなレジスタを、何段追加するかです。
適切な位置へレジスタを追加するには、まず現在のクリティカルパスを詳しく調べる必要があります。
せっかくTiming Analysisを開いているので、最初からAIへ任せるのではなく、この画面とFloorplanから人間が確認できるところまで追ってみます。
最も遅い配線をFloorplanで確認する
Timing Analysisでは、クリティカルパスを構成するLUT、CARRY4、Netと、それぞれの区間の遅延を確認できます。
Path 2709の全経路はかなり長いため、ここでは概要と、配線遅延が最も大きかったNet 698の前後だけを抜粋します。
Path 2709:
Slack (not met): -12889ps
Propagation time: 32726ps
(52.8% logic, 47.2% route, logic stage 17)
...
RBB_16/CMUX [TILE 0 0, RBB 22 6] Delay 1082ps
Net 698 (fanout=3) Delay 1983ps
RBB_86/D4 [TILE 0 0, RBB 7 6]
RBB_86/D [TILE 0 0, RBB 7 6] Delay 1062ps
...
色々調べましたが、RBBの正確な意味や定義は見つかりませんでした。
ただし、実用上はRBBをCLBに読み替えても、大きな問題にはならないようですから、この先はCLB表記で説明します。
さて、Net 698の前後には、RBB_16、RBB_86とともに、22 6、7 6という数値が表示されています。
配置座標のように見えるため、Floorplanで確認してみます。
ForgeFPGA WorkshopのFloorplanを開き、Position 22 6を確認します。
この位置のブロックを選択すると、画面右側のBlocks TreeにCLB 16と表示されました。
仮説は当たりのようですね。
さらに拡大すると、CLB内部の回路と配線が表示されます。
CLB 16の内部にはCRY 51が配置されています。
CRYは、加算や減算などで桁上がりを伝えるキャリー回路を表していると考えられます。画面左側にも、CARRY4を構成するMUXCYやXORCYが表示されています。
Net 698は、このCRY 51の出力O2からCLB外部へ引き出されていました。
もう一方のPosition 7 6を確認すると、Net 698はCLB 86内部のLUTへ接続されていました。
ここまでで、Net 698がキャリー回路の出力から、別のCLB内にあるLUTへ接続されていることが分かりました。
一方、Net 698に付けられた信号名は次のように長く、元のVerilogコード上の処理を読み取る手掛かりにはなりそうにありません。
a3_LUT3_I0_O_LUT5_I0_O_CARRY4_S_CO_CARRY4_CI_CO_
CARRY4_CI_CO_CARRY4_CI_O_CARRY4_O_O[2]
最後にFloorplanの拡大率を下げ、二つのCLBの位置関係を確認します。
Position 22 6とPosition 7 6は横方向に大きく離れており、Net 698はチップの右下側から左下側へ引き回されています。
この物理的な距離が、Net 698の配線遅延が大きくなった原因の一つだと推測できます。
AIの助けを借りて解析を進める
ここまでの情報は、Timing AnalysisとFloorplanを照合することで確認できました。
つまり、タイミング違反が発生している経路と、その中で物理的に長い配線がどこにあるかまでは、初心者でもある程度は追うことができます。
しかし、この配線一本だけを短くすれば解決するわけではありません。
クリティカルパス全体では17段の論理回路を通過しており、その間に複数の配線があります。
また、物理的な経路が分かっても、それが元のVerilogコードのどの計算に対応しているのか、どこへレジスタを追加すればよいのかまでは分かりません。
さらに、レジスタを追加すると、その計算結果と同じタイミングで使うデータ、カウンタ、判定結果、制御信号なども、必要なクロック数だけ同期させる必要があります。
ここから先は、Timing Analysis、Floorplan、合成後の回路情報、元のVerilogコードを対応付けて考える必要があります。
初心者が独力で追うには難しくなってきたため、ここからAIとの共同作業を開始します。
AIとクリティカルパスを元のVerilogコードへ対応付ける
Timing AnalysisとFloorplanから、物理的に遅い経路までは確認できました。
次は、この経路が元のVerilogコードのどの処理に対応しているのかを調べます。
しかし、合成や配置配線を終えた後の回路名は、元のVerilogコードに書かれている変数名とは大きく異なります。
そこで、プロジェクトフォルダ全体をAIへ渡し、PNR_TIMING.logに表示されたクリティカルパスと、元のVerilogコードとの対応を調べてもらいました。
この段階では回路の変更案は求めず、現在のクリティカルパスがどの処理で構成されているのかだけを確認します。
主な依頼内容は次の通りです。
ABC467C Prefix XORバースト版について、
現在のクリティカルパスを分析してください。
PNR_TIMING.logを起点として、
必要に応じて合成後ネットリスト、EDIF、配置配線ログ、
元のVerilogコードも参照してください。
クリティカルパスが、Verilogコード上の
どの信号と処理に対応しているのかを確認してください。
この段階ではファイル変更、回路修正、
再合成、配置配線、Git操作を行わないでください。
ここでいう合成後ネットリストは、VerilogコードをFPGA内のLUTやFFなどへ変換した後の回路一覧です。
読者がネットリストを手作業で読む必要はありません。今回は、PNR_TIMING.logに記録された物理的な経路を、元のVerilogコードへ対応付ける手掛かりとしてAIに調べてもらっています。
AIは、合成後の回路情報に残っているsrc属性をたどり、クリティカルパスと元のVerilogコードとの対応を調べてくれました。
src属性は、合成後の回路が元のソースコードのどこから作られたかを示す手掛かりです。
最悪パスは残数と個数判定へ続いていた
最初は、4組分のPrefix XOR、AとのXOR比較、回答値の加算が、クリティカルパスの中心ではないかと考えていました。
しかし、AIの解析結果は予想と異なっていました。
最悪パス上のCARRY4は、主に次のRTL処理に対応していました。
remaining_pairsの生成
valid_countの判定
pair_count_nextの生成
pair_count_next == total_pair_count
package_count_next == expected_package_count
CARRY4は、加算や減算、大小比較などを高速に処理するための回路です。
RTL上の処理を、信号が伝わる順番に並べると、おおむね次のようになります。
Nから処理対象の総組数を求める
N - 1
↓
処理済み組数を引いて、残り組数を求める
↓
今回受信したbyteのうち、何組を有効データとして扱うか決める
残りが4組以上なら4組、1～3組なら残っている組数
↓
今回処理した組数を、累積の処理済み組数へ加える
↓
累積の処理済み組数と総組数を比較し、すべての組を処理したか判定する
↓
予定された回数のパッケージを受信したか判定する
↓
組数とパッケージ受信回数の両方が正しければ、最終パッケージであると判定する
↓
最終結果と通信状態をレジスタへ保存する
AIの解析では、最悪パスの開始点は、当初想定していたSPI受信シフトレジスタではなく、SEND_N_9_5受信時に保持されたn_value[9]に対応している可能性が高いという結果でした。
事前の想定と異なり、最悪パスは、Prefix XORや回答値の計算そのものではありませんでした。
ストリームの進行状況を管理し、最後のパッケージであることを判定するまでの、補助的な処理が長い経路になっていました。
この経路だけを直しても本命の計算は残る
当初は、現在のクリティカルパスへレジスタを追加すれば、50MHz制約を満たせるのではないかと考えていました。
しかし、見つかったのは残り組数や受信個数を管理する経路です。
この経路だけを短くしても、本来の計算である次の処理はそのまま残ります。
4組分のPrefix XOR
↓
AとのXOR比較
↓
4組分の加算
現在の最悪パスを改善した後、今度はこちらが新しいクリティカルパスになる可能性があります。
それでは、特定された経路だけへ局所的にレジスタを追加しても、回路全体のタイミング違反を解決できるとは限りません。
そこで、現在のクリティカルパスだけでなく、回路全体を見渡してパイプラインの分割位置を検討することにしました。
回路全体を見渡して分割位置を検討する
もう一度AIへ依頼し、Prefix XOR、XOR比較、加算、残数計算、個数判定、最終処理を含む回路全体から、効果的なパイプライン構成を検討してもらいました。
主な依頼内容は次の通りです。
先ほどのクリティカルパス解析結果を踏まえて、
回路全体のパイプライン分割案を検討してください。
目的は、50MHzの20ns制約をPnR後も満たすことです。
現在の最悪パスだけでなく、
Prefix XOR、XOR比較、加算、残数計算、
個数判定、最終処理を含む回路全体を確認してください。
どこへ、どのようなレジスタを、何段追加するのが
最も効果的かを提案してください。
レジスタ追加によって同期が必要になるデータ、
カウンタ、判定結果、制御信号についても確認してください。
まずは構成案を提示し、
この段階ではファイル変更、再合成、
配置配線、Git操作を行わないでください。
人間側では3段構成を予想していた
AIへ分割案を依頼する時点では、回路を3段程度へ分ける必要があるのではないかと考えていました。
たとえば、次のような構成です。
第1段
4組分のPrefix XOR
第2段
AとのXOR比較
4組分の加算
第3段
残り組数と受信個数の判定
最終結果と通信状態の確定
単純に考えれば、処理を細かく分けるほど、1クロックで通過する組合せ回路は短くなります。
50MHz制約を確実に満たすには、このくらい分割する必要があるのではないか、というのが事前の予想でした。
しかし、AIが推奨したのは、このような3段構成ではありませんでした。
AIは回路変更と2段構成を推奨した
AIの提案は、大きく次の二つに分かれていました。
1. 現在のクリティカルパスを作っている管理回路を組み替える
2. Prefix XORを中心とするメイン処理を2段へ分割する
人間側では、回路全体を3段程度へ分割する必要があるのではないかと予想していました。
しかし、AIが推奨したのは、単純にパイプライン段数を増やす方法ではありませんでした。
現在の最悪パスを単純に二つへ分割すると、各段は約17～18nsとなり、20nsに対する余裕は約2nsしかありません。
さらに、その経路だけを分割しても、Prefix XOR、XOR比較、加算を行うメインラインはそのまま残ります。
そこで、残り組数や受信個数を管理する回路では、計算方法を見直して組合せ回路の論理チェーンを短くし、更新処理と最終判定の間へパイプラインレジスタを挿入します。
一方、Prefix XOR、XOR比較、加算を行うメイン処理は、途中結果をレジスタへ保存して2段へ分割します。
つまり、今回の方針は次の組み合わせです。
管理回路
-> 計算方法の見直しとパイプラインレジスタの挿入
メイン処理回路
-> パイプラインレジスタの挿入
予想していた3段構成とは異なる提案でした。
今回のまとめ
今回は、4組パック＋Prefix XOR版で生じたタイミング違反を詳しく調べました。
Timing AnalysisとFloorplanを使うことで、クリティカルパスと、その中で特に配線遅延が大きい場所までは人間でも確認できました。
しかし、合成後の回路を元のVerilogコードへ対応付ける作業は難しかったため、途中からAIと共同で解析を進め、AI推しの改善案を提示してもらうところまで進みました。
次回
最終的にAIが提示した推奨改善案は次の通りでした。
管理回路
-> 計算方法の見直しとパイプラインレジスタの挿入
メイン処理回路
-> パイプラインレジスタを挿入して2段化
次回は、この提案内容を詳しく確認し、実際にRTLを変更します。
前回： Shrike-LiteでAtCoder問題を解く(16)：ABC467C - Adjacent Sums (easy)（4組パック＋Prefix XOR編）
次回： Shrike-LiteでAtCoder問題を解く(18)：ABC467C - Adjacent Sums (easy)（タイミング違反解消編・後編）(https://qiita.com/bit_otter/items/e3b74f85e1a47996f23b)