我试图在 verilog 中对 9 个随机数进行排序。我使用冒泡排序(嵌套循环)算法,但我遇到了挑战。我想在一个时钟周期内对它们进行排序,但它没有达到我想要的效果。至少需要9个周期才能对它们进行排序。
always @(posedge clk)
begin
if(m >= 68 && sort_valid == 0) begin
pool_sort[0] <= pool_buffer[66];
pool_sort[1] <= pool_buffer[65];
pool_sort[2] <= pool_buffer[64];
pool_sort[3] <= pool_buffer[34];
pool_sort[4] <= pool_buffer[33];
pool_sort[5] <= pool_buffer[32];
pool_sort[6] <= pool_buffer[2];
pool_sort[7] <= pool_buffer[1];
pool_sort[8] <= pool_buffer[0];
sort_valid <= 1;
end
if(sort_valid == 1) begin
for(k=0;k<8;k=k+1) begin
if(pool_sort[k] < pool_sort[k+1]) begin
pool_sort[k] <= pool_sort[k+1];
pool_sort[k+1] <= pool_sort[k];
end
end
if(sort_counter == 0) begin
sort_valid <= 0;
pool_out <= pool_sort[0];
end
end
end
always @(posedge clk)
begin
if(sort_valid == 1) begin
sort_counter <= sort_counter - 1;
end
if(sort_counter == 0) begin
sort_counter <= 8;
end
end
endmodule
这是我到目前为止的排序算法。
这是一个用于 Verilog 的可参数化 1 时钟周期排序器(受到here的启发,但我对模块进行了参数化,减少了周期数,并进行了一些清理)。
它会在模拟中实现您想要的效果,但当您合成它时,它可能会变得相当大且难看。
module sort #(
parameter NUM_VALS = 5,
parameter SIZE = 16
)( input wire clk,
input wire [NUM_VALS*SIZE-1:0] in,
output reg [NUM_VALS*SIZE-1:0] out
);
reg [NUM_VALS*SIZE-1:0] sorted_bus;
always @(posedge clk) begin
out <= sorted_bus;
end
integer i, j;
reg [SIZE-1:0] temp;
reg [SIZE-1:0] array [1:NUM_VALS];
always @* begin
for (i = 0; i < NUM_VALS; i = i + 1) begin
array[i+1] = in[i*SIZE +: SIZE];
end
for (i = NUM_VALS; i > 0; i = i - 1) begin
for (j = 1 ; j < i; j = j + 1) begin
if (array[j] < array[j + 1]) begin
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
end
end
end
for (i = 0; i < NUM_VALS; i = i + 1) begin
sorted_bus[i*SIZE +: SIZE] = array[i+1];
end
end
endmodule
还有测试台:
module sort_tb;
reg clk;
reg [16-1:0] in1, in2, in3, in4, in5;
wire [16-1:0] out1, out2, out3, out4, out5;
sort #(.NUM_VALS(5), .SIZE(16)) dut (
.clk(clk),
.in ({in1, in2, in3, in4, in5}),
.out({out1, out2, out3, out4, out5})
);
always @(posedge clk) begin
in1 <= $random;
in2 <= $random;
in3 <= $random;
in4 <= $random;
in5 <= $random;
end
always @(posedge clk) begin
$display("In: %0d %0d %0d %0d %0d", in1, in2, in3, in4, in5);
$display("Out: %0d %0d %0d %0d %0d", out1, out2, out3, out4, out5);
end
initial begin
#100;
$finish;
end
always begin
clk = 1'b0; #5;
clk = 1'b1; #5;
end
endmodule
如果您需要对多轮 9 个数字进行排序,请提前考虑。
您可以在 1 个周期内进行排序,但最高频率可能会受到很大限制。但是,如果您在低频下花费 1 个时钟周期,或者在更高频率下花费 9 个时钟周期,这并不重要。
如果您有很多轮,那么您可以对排序阶段进行管道化,在每个时钟周期获得新结果,第一个结果有一些时钟延迟。
另请参阅https://en.wikipedia.org/wiki/Bitonic_sorter,更适合在硬件中进行少量输入的并行排序。
创建一个简单地从一组数字中选取最大值的函数。它输出一个位图,其中最大值位置为 1,其余位置为零,因此如果第二个数字是最大值,则四个一组中的最大值可能看起来像 0100。现在让这个函数将排除位图作为输入,这将排除已经计数的数字。
此排除输入的第一位为 0。 第二名有第一名的结果 第三名有第一名+第二名的结果。 第四位有第一+第二+第三为排除项 所以你会得到排序中每个位置的位图。
您现在可以使用部分 select[position+:numbits] 根据每个结果的位图从输入向量创建一个新的排序向量。您可能需要制作一个小表来将位图转换为零件选择可以使用的整数。
`timescale 1ns/1ns
module sort #(parameter WIDTH=8) (
input logic [4*WIDTH-1:0]din,
output wire [4*WIDTH-1:0]dout
);
wire [3:0]First;
wire [3:0]Second;
wire [3:0]Third;
wire [3:0]Fourth;
assign First = MaxOf_Four(din,4'h0);
assign Second =MaxOf_Four(din,First);
assign Third = MaxOf_Four(din,First+Second);
assign Fourth = MaxOf_Four(din,First+Second+Third);
function automatic [3:0]MaxOf_Four; // no two numbers can be equal in din. Each byte is compared.
input [4*WIDTH-1:0]din;
input [3:0]exclude;
integer i;
reg [WIDTH-1:0]data;
integer MaxIndex;
data =0;
MaxIndex = 0;
for (i=0; i<4;i=i+1)
begin
if (exclude[i] == 1'b1)
begin
end
else
begin
if (data < din[i*WIDTH+:WIDTH])
begin
data = din[i*WIDTH+:WIDTH];
MaxIndex = i;
end
end
end
case (MaxIndex)
0:MaxOf_Four = 4'b0001;
1:MaxOf_Four = 4'b0010;
2:MaxOf_Four = 4'b0100;
3:MaxOf_Four = 4'b1000;
endcase
endfunction
function integer position;
input [3:0]map;
case (map)
4'b0001: position = 0;
4'b0010: position = 1;
4'b0100: position = 2;
4'b1000: position = 3;
default:
position = 4'hF;
endcase
endfunction
assign dout[4*WIDTH-1:0] = {din[position(First)*WIDTH+:WIDTH],
din[position(Second)*WIDTH+:WIDTH],
din[position(Third)*WIDTH+:WIDTH],
din[position(Fourth)*WIDTH+:WIDTH]};
endmodule