|
1.原理 傳統(tǒng)的排序方式是兩兩之間順序進行比較，而全并行算法是基于序列中隨意兩個數(shù)進行比較，所以會消耗比較多的比較器。這正詮釋了FPGA技巧里面積換取速度的思想。
原理如下：
（1）第一個時鐘周期，將其中一個數(shù)據(jù)和其他數(shù)據(jù)在一個周期中比較。
（2）第二個時鐘周期，將每個數(shù)據(jù)和其他數(shù)據(jù)比較后的結(jié)果進行累加。
（3）第三個時鐘周期，將每個數(shù)據(jù)根據(jù)自己的得分賦值給新的數(shù)組。 2.優(yōu)缺點 2.1優(yōu)點 并行比較排序方式在實時性上有明顯的優(yōu)勢，只需要三個時鐘周期就可以完成排序。 2.2缺點 由于并行比較消耗FPGA的LUT資源，而且在第二個階段需要大量的加法器級聯(lián)，考慮到路徑延遲、建立和保持時間的Slack以及時鐘的Jitter，一個時鐘周期的多個加法器級聯(lián)會產(chǎn)生問題
代碼的可移植性有所欠缺，比如序列大小改變，在第二和第三階段就需要認為修改多處代碼。 3.傳統(tǒng)的排序例程 如下圖所示，不僅需要多個比較器，而且時序路徑過長，造成布線的數(shù)據(jù)路徑過長，產(chǎn)生建立時間違例。 
從下面的timing報告中可以明顯的看出，該數(shù)據(jù)過長。
也可以從芯片布線的情況上明顯看出。
4.全并行比較例程
module sort_paralell(clk, rst, in0, in1, in2, in3, out0, out1, out2, out3);
input clk;
input rst;
input [7:0] in0, in1, in2, in3;//輸入的4個需要比較的數(shù)字
reg [7:0] out_temp[3:0];//輸出數(shù)據(jù)放入此數(shù)組中
output [7:0] out0, out1, out2, out3;//輸出的比較后的結(jié)果
reg [7:0] out0, out1, out2, out3;
//下面定義的變量用于存儲比較結(jié)果，如in0 > in1,則a0 <= 1,否則a0 <= 0;
reg a0, a1, a2;
reg b0, b1, b2;
reg c0, c1, c2;
reg d0, d1, d2;
reg add_start; //該變量的作用是判斷比較是否結(jié)束，比較結(jié)束后賦值為1，進入相加模塊
reg assignm_start; //該變量作用在于判斷相加模塊執(zhí)行是否結(jié)束，結(jié)束后賦值為1，進入下一個輸出模塊
//下面定義的變量用于存儲上述中間變量累加結(jié)果，（9個1位2進制數(shù)相加最多4位）2的（0,1,2,3）次方的累加，那么4個1位的2進制數(shù)相加最多3位，2的（0,1,2）的累加
reg out_start;
//reg [3:0] mid0, mid1, mid2, mid3, mid4, mid5, mid6, mid7, mid8, mid9;
reg [2:0] mid0, mid1, mid2, mid3;//4 input numbers
//排序算法在FPGA內(nèi)進行，實現(xiàn)過程主要有以下幾個步驟：
//1、第一個clk，數(shù)據(jù)的全比較程序，4個數(shù)據(jù)排序，輸入數(shù)據(jù)為in0~in3;
//2、第二個clk，比較值累加，mid0,mid1,mid2,mid3;
//3、第三個clk，把輸入值賦給相對應(yīng)的排序空間；
//4、第四個clk，把排序結(jié)果輸出；
//并行比較模塊（第一個時鐘）
always @ (posedge clk)
begin
if(rst)
begin
{a0, a1, a2} <= 3'b0000_0000_0;
{b0, b1, b2} <= 3'b0000_0000_0;
{c0, c1, c2} <= 3'b0000_0000_0;
{d0, d1, d2} <= 3'b0000_0000_0;
{mid0, mid1, mid2, mid3} <=
30'b0000_0000_0000_0000_0000_0000_0000_0000_0000_0000;
out0 <= 0; out1 <= 0; out2 <= 0; out3 <= 0;
add_start <= 0;
assignm_start <= 0;
out_start <= 0;
end
else
begin
if(in0 > in1) a0 <= 1'b1; //in0和所有除自己外的其他數(shù)據(jù)比較，大于則標志置1
else a0 <= 1'b0;
if(in0 > in2) a1 <= 1'b1;
else a1 <= 1'b0;
if(in0 > in3) a2 <= 1'b1;
else a2 <= 1'b0;
if(in1 > in0) b0 <= 1'b1;//in1和所有除自己外的數(shù)據(jù)比較，大于標志位置1，否則為0
else b0 <= 1'b0;
if(in1 > in2) b1 <= 1'b1;
else b1 <= 1'b0;
if(in1 > in3) b2 <= 1'b1;
else b2 <= 1'b0;
if(in2 > in0) c0 <= 1'b1;
else c0 <= 1'b0;
if(in2 > in1) c1 <= 1'b1;
else c1 <= 1'b0;
if(in2 > in3) c2 <= 1'b1;
else c2 <= 1'b0;
if(in3 > in0) d0 <= 1'b1;
else d0 <= 1'b0;
if(in3 > in1) d1 <= 1'b1;
else d1 <= 1'b0;
if(in3 > in2) d2 <= 1'b1;
else d2 <= 1'b0;
add_start <= 1; //比較結(jié)束標志，相加開始標志
end
end
//相加模塊，mid（i）的值代表著in（i）所在輸出數(shù)組中的位置，（第二個時鐘）
always @ (posedge clk)
begin
if(add_start == 1)
begin
mid0 <= a0 + a1 + a2; //標志位相加，所得結(jié)果就是其所在位置
mid1 <= b0 + b1 + b2;
mid2 <= c0 + c1 + c2;
mid3 <= d0 + d1 + d2;
end
assignm_start <= 1;//相加結(jié)束，賦值開始標志
end
//輸出模塊，將排序好的數(shù)據(jù)放入輸出數(shù)組中（第三個時鐘）
always @ (posedge clk)
begin
if(assignm_start == 1)
begin
out_temp[mid0] <= in0;
out_temp[mid1] <= in1;
out_temp[mid2] <= in2;
out_temp[mid3] <= in3;
out_start <= 1;//賦值結(jié)束，輸出開始標志位
end
end
always @ (posedge clk)
begin
if(out_start == 1)
begin
out0 <= out_temp[0];
out1 <= out_temp[1];
out2 <= out_temp[2];
out3 <= out_temp[3];
end
end
endmodule 上述代碼僅供參考，下圖仿真結(jié)果為9個數(shù)據(jù)進行排序的輸出結(jié)果。
可以看到只需要四個時鐘周期就可以得到排序結(jié)果。
以上的Word格式文檔51黑下載地址： | 
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
