1.原理
傳統(tǒng)的排序方式是兩兩之間順序進(jìn)行比較，而全并行算法是基于序列中隨意兩個(gè)數(shù)進(jìn)行比較，所以會(huì)消耗比較多的比較器。這正詮釋了FPGA技巧里面積換取速度的思想。
原理如下：
（1）第一個(gè)時(shí)鐘周期，將其中一個(gè)數(shù)據(jù)和其他數(shù)據(jù)在一個(gè)周期中比較。
（2）第二個(gè)時(shí)鐘周期，將每個(gè)數(shù)據(jù)和其他數(shù)據(jù)比較后的結(jié)果進(jìn)行累加。
（3）第三個(gè)時(shí)鐘周期，將每個(gè)數(shù)據(jù)根據(jù)自己的得分賦值給新的數(shù)組。
2.優(yōu)缺點(diǎn)
2.1優(yōu)點(diǎn)
并行比較排序方式在實(shí)時(shí)性上有明顯的優(yōu)勢(shì)，只需要三個(gè)時(shí)鐘周期就可以完成排序。
2.2缺點(diǎn)
由于并行比較消耗FPGA的LUT資源，而且在第二個(gè)階段需要大量的加法器級(jí)聯(lián)，考慮到路徑延遲、建立和保持時(shí)間的Slack以及時(shí)鐘的Jitter，一個(gè)時(shí)鐘周期的多個(gè)加法器級(jí)聯(lián)會(huì)產(chǎn)生問(wèn)題
代碼的可移植性有所欠缺，比如序列大小改變，在第二和第三階段就需要認(rèn)為修改多處代碼。
3.傳統(tǒng)的排序例程
如下圖所示，不僅需要多個(gè)比較器，而且時(shí)序路徑過(guò)長(zhǎng)，造成布線的數(shù)據(jù)路徑過(guò)長(zhǎng)，產(chǎn)生建立時(shí)間違例。
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個(gè)需要比較的數(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;
//下面定義的變量用于存儲(chǔ)比較結(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，進(jìn)入相加模塊
reg assignm_start; //該變量作用在于判斷相加模塊執(zhí)行是否結(jié)束，結(jié)束后賦值為1，進(jìn)入下一個(gè)輸出模塊
//下面定義的變量用于存儲(chǔ)上述中間變量累加結(jié)果，（9個(gè)1位2進(jìn)制數(shù)相加最多4位）2的（0,1,2,3）次方的累加，那么4個(gè)1位的2進(jìn)制數(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)進(jìn)行，實(shí)現(xiàn)過(guò)程主要有以下幾個(gè)步驟：
//1、第一個(gè)clk，數(shù)據(jù)的全比較程序，4個(gè)數(shù)據(jù)排序，輸入數(shù)據(jù)為in0~in3;
//2、第二個(gè)clk，比較值累加，mid0,mid1,mid2,mid3;
//3、第三個(gè)clk，把輸入值賦給相對(duì)應(yīng)的排序空間；
//4、第四個(gè)clk，把排序結(jié)果輸出；
//并行比較模塊（第一個(gè)時(shí)鐘）
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ù)比較，大于則標(biāo)志置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ù)比較，大于標(biāo)志位置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é)束標(biāo)志，相加開(kāi)始標(biāo)志
end
end
//相加模塊，mid（i）的值代表著in（i）所在輸出數(shù)組中的位置，（第二個(gè)時(shí)鐘）
always @ (posedge clk)
begin
if(add_start == 1)
begin
mid0 <= a0 + a1 + a2; //標(biāo)志位相加，所得結(jié)果就是其所在位置
mid1 <= b0 + b1 + b2;
mid2 <= c0 + c1 + c2;
mid3 <= d0 + d1 + d2;
end
assignm_start <= 1;//相加結(jié)束，賦值開(kāi)始標(biāo)志
end
//輸出模塊，將排序好的數(shù)據(jù)放入輸出數(shù)組中（第三個(gè)時(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é)束，輸出開(kāi)始標(biāo)志位
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個(gè)數(shù)據(jù)進(jìn)行排序的輸出結(jié)果。
Verilog實(shí)現(xiàn)全并行比較算法.zip
(813.6 KB, 下載次數(shù): 8)
| 歡迎光臨 (http://www.denmoz.com/bbs/) | Powered by Discuz! X3.1 |