FPGA實現雙調排序方法詳解

基于雙調排序算法的蝶形圖，我們可以得到地址的變化規律。這里以長度為16的雙調序列為例，其地址變化規律入下圖所示。由于長度為16，故總共需要4個Stage。圖中每個Stage顏色的個數表明該Stage可分為的組數。例如Stage 0可分為1組，Stage 1可分為2組，Stage 2可分為4組，Stage 3可分為8組。

每組的起始地址和對應的Stage緊密相關，例如Stage 1第0組起始地址為0，即(16/2^1)*0，第1組起始地址為8，即(16/2^1)*1。每組的地址個數也由Stage決定。例如Stage 1每組地址長度為4，即16/2^(1+1)，Stage 2每組地址長度為2，即16/2^(2+1)。同一組內，相鄰地址的間距為1，例如Stage 1第0組的4個地址為[0,1,2,3]，相鄰地址間距為1，第1組的4個地址為[8,9,10,11]，相鄰地址間距為1。

一旦確定了op1的地址就很容易確定op2的地址，因為兩者之差（用diff表示）也是由Stage決定的。例如：Stage 0兩者之差為8，即16/2^(0+1)，Stage 1兩者之差為4，即16/2^(1+1)。

我們將地址規律總結為如下圖所示形式。這里一個重要的數據是Stage，其與序列長度的關系可表示為Stage=log2(N)；另一個重要數據為diff，其與Stage關系可表示為diff=N/2^(Stage+1)。

在此基礎上我們就很容易借助C++或Matlab生成兩個操作數的地址。這里采用Matlab，相應的Matlab函數如下圖所示。代碼第5行用于判斷序列長度是否為2的整數次冪。

有了地址關系也就有了數據之間的關系。通常情況下，數據是按時間順序串行進入的，所以我們也期望每次排序之后也是串行輸出的。根據數據流的關系，我們可以采用單路徑延遲反饋（Single-pathDelay Feedback, SDF）運算單元流水結構，SDF單元如下圖所示。

圖中butterfly為蝶形運算單元，(2^P)D為延遲單元，延遲級數與所在Stage相關。仍以長度為16的雙調序列為例，Stage 為0時，延遲級數為8，Stage 為1時，延遲級數為4，Stage為2時，延遲級數為2，Stage為3時延遲級數為1。圖中sel為分頻信號，仍與Stage相關，Stage為0時，sel為時鐘的8分頻信號，不難看出，分頻系數與延遲級數是一致的。

在此基礎上，將4個SDF相連即可實現串行輸入/串行輸出的雙調排序。下圖給出了Stage 0對應的SDF結構。

下圖顯示了相應的仿真結果。

? 審核編輯：黃飛

?