用FPGA實現雙調排序的方法（2）

在上篇文章中我們介紹了如何對雙調序列進行排序，操作過程如下圖所示。

其特征是每次分割都是將原始的序列分成兩個等長序列。

例如：原始序列長度為16，第1次分割將其分為2個長度為8的序列；第2次分割將第1次分割的排序結果（長度仍為16）分為4個長度為4的序列；第3次分割將第2次分割的排序結果分為8個長度為2的序列；第4次分割將第3次分割的排序結果分為16個長度為1的序列。

圖中相鄰的綠色標記和藍色標記序列構成一組進行比較。

為進一步說明，我們定義操作符?，如下圖所示。

兩個操作符?由雙向箭頭連接，表示彼此之間共享數據，即下方的?可接收上方的?對應操作數op1，同時上方的?可接收下方的?對應操作數op2。

位于上方的?輸出op1與op2中的較小者，位于下方的?輸出op1與op2的較大者，簡言之?表示對兩個輸入數據進行升序排序。

此外，還有一個關鍵點就是圖中虛線的含義。

可以看到op1與min(op1,op2)在一條直線上，op2與max(op1,op2)在一條直線上。

同一條直線上的兩個數據其位置是相同的。

即若op1是0號數據，那么min(op1,op2)也必須放到0號位置上，這就是所謂的原位（In-place）運算。

在?操作符的定義下，長度為16的雙調序列的排序過程如下圖所示。

圖中第1列為二進制數，表示序列中每個元素在序列中的位置也就是地址，用于體現原位運算的特征。

整個排序過程分為4個階段完成對應圖中的Stage 0~Stage3。

在Stage 0中，?的兩個操作數的地址間距為8（例如，3來自0號地址，95來自8號地址）；在Stage 1中間距為4；在Stage 2中間距為2；在Stage 3中間距為1。

審核編輯：劉清