一个求一组数据最小值的问题

zebfff · 发表于 2015-4-24 20:07:18

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？注册

x

首先，数据本身假定已经存储在了寄存器类型中，reg[31：0] a[0:n-1]，其中n是一个parameter。然后我想实现log2(n)的方式找出其中的最小值，但是对FPGA的编程没有那么熟悉，不太清楚如何写出可综合的代码，希望给个代码思路。要求是可综合，给个大致上的写法就行。想了一天，没有想出可综合的写法，可能是我对verilog编程还是不太清楚，所以求助一下大家。 log2(n)找出最小值的方法，我想大家应该都知道，就是第一步并行求n/2组大小比较，然后n/4组，直到剩余1个。

zebfff · 发表于 2015-4-24 20:09:13

之前那个帖子发重复了，管理员可以删掉

xyd237529 · 发表于 2015-4-24 22:29:51

简单写下我的思路，
按你的例子，一个四位计数器1当地址，每次读取两个寄存器中的值。四位寻址32位，所以每次是两个地址。(第五位高位一个0,一个1)。比完大小再写回寄存器(比如写回高位为0的地址)。
计数器1依次递增。
再加一个计数器2，用来控制计数器1的有效位数。每次计数器1从全0增加到全1,计数器2增一(也可以减一)。由计数器2相当于一个数据选择器的控制位。控制地址是由计数器1的哪几位提供。
每次都是比较完大小，将小的写回寄存器保存起来。

就是简单写下思路，细节还得推敲。大概就是两个计数器一个mux一个存储空间的大小。
如果数据多了，用ram，在读取数据的时候就得优化下。
如果原始数据需要保留，需要写到新的空间，地址就得再斟酌下。

手机打的，不容易。。。。

polozpt · 发表于 2015-4-25 17:19:33

回复 1# zebfff

不一定非得用log2(n)找出最小值的方法，直接从ram中取数，两两比较，最小的留下即可。

zebfff · 发表于 2015-4-26 11:55:21

回复 3# xyd237529 十分抱歉这么晚才回。题目中，我有点没有说清楚，32是指数据宽度，n才是数据的个数。n虽然是parameter，但是可以从模块外部改变它的值，所以相当于n可以改变。我明白，我的题目实际上不怎么实用，毕竟如果值都存在了reg中，必然是先取了出来，不如取的时候就一一比较。所以，我这只是做一个理想的情况下的一个讨论。

zebfff · 发表于 2015-4-26 11:56:33

回复 4# polozpt
看我上面的留言。谢谢回复

glace12123 · 发表于 2015-4-26 21:37:29

本帖最后由 glace12123 于 2015-4-26 21:43 编辑

你说的就是先找邻近2个数的最小数，先排除掉一半，然后再剩余的数里又比较邻近2个数据大小，再排除掉一半，这样直到剩下2个数的比较吧？
这用FPGA很容易实现啊，但是要看你是什么方式，是一次并行把所有数据送完，还是串行送数据。

module comp #(
parameter U_DLY = 1
)
(
input sys_clk,
input rst_n,
input [31:0] num1_i,
input [31:0] num2_i,
input [31:0] num3_i,
input [31:0] num4_i,
input cmp_en,
output reg res_vld,
output reg min_num
);
reg [31:0] stg1_res1_o;
reg [31:0] stg1_res2_o;
reg cmp_en_r;
always @(posedge sys_clk or negedge rst_n)
begin
if(rst_n == 1'b0)
begin
cmp_en_r <= #U_DLY 1'b0;
res_vld <= #U_DLY 1'b0;
end
else
begin
cmp_en_r <= #U_DLY cmp_en;
res_vld <= #U_DLY cmp_en_r;
end
end
// compare stage1
always @(posedge sys_clk or negedge rst_n)
begin
if(rst_n == 1'b0)
stg1_res1_o <= #U_DLY 32'h0;
else if(cmp_en == 1'b1)
begin
if(num1_i >= num2_i)
stg1_res1_o <= #U_DLY num2_i;
else
stg1_res1_o <= #U_DLY num1_i;
end
else ;
end
always @(posedge sys_clk or negedge rst_n)
begin
if(rst_n == 1'b0)
stg1_res2_o <= #U_DLY 32'h0;
else if(cmp_en == 1'b1)
begin
if(num3_i >= num4_i)
stg1_res2_o <= #U_DLY num4_i;
else
stg1_res2_o <= #U_DLY num3_i;
end
else ;
end
// compare stage2
always @(posedge sys_clk or negedge rst_n)
begin
if(rst_n == 1'b0)
min_num <= #U_DLY 32'h0;
else if(cmp_en_r == 1'b1)
begin
if(stg1_res1_o >= stg1_res2_o)
min_num <= #U_DLY stg1_res2_o;
else
min_num <= #U_DLY stg1_res1_o;
end
else ;
end
endmodule

复制代码

上面我写这段代码，代表4个输入，比较输出最小值，应该就是你的那个所谓log2(n)方法。
里面有2阶的处理，第一阶，计算出2个值，第二阶，从2个中选最小的那个，输出。
输入和输出都有使能信号，指示输入和输出的数据何时有效。
其中内部第二阶的使能，以及输出使能，都是根据输入使能来推导的，卡准了那个时钟。
我随意写的，应该没什么问题，就是给你演示下如何用FPGA实现你那个比较算法。

tmfjek · 发表于 2015-4-27 10:08:40

回复 7# glace12123

楼上没理解楼主的意思，不是确定个数比较大小，重点在实现参数化。

sjtusonic · 发表于 2015-4-27 15:45:10

首先，数据本身假定已经存储在了寄存器类型中，reg[31：0] a[0:n-1]，其中n是一个parameter。然后我想实现l ...
zebfff 发表于 2015-4-24 20:07

登录/注册后可看大图

log2(n)是指什么复杂度呢？
一般讲算法复杂度是指时间复杂度。
但verilog是写电路，这个是指某种“电路复杂度”吗？
我对这块也不很熟，纯探讨

zebfff · 发表于 2015-4-27 16:59:01

回复 9# sjtusonic
题目没有说得很清楚，我这里补充一些。首先，log2(N)是指算法复杂度。比较一组值之中的最小值，最简单的方法就是遍历一遍，这样复杂度就是O(N)。
下面我说得都是软件上并行算法的考虑，对硬件由于最近接触，所以不太明白，是否也能这样实现。
比较一组值中的最小值，可以把问题分解为，比较前N/2个值中的最小值和比较后N/2个值中的最小值，然后将2个值比较，这样就求出的答案。接着前N/2个值和后N/2个值的比较也这样分解，直到分解为一个比一个。递归表达式为T(N)=2T(N/2)+O(1)
这样复杂度仍是O(N)，只不过用的是分治的方法。但是如果是并行编程的思想，理论上T(N/2)前面的系数2是可以去掉的，递归表达式就是
T(N)=T(N/2)+O(1)，这样算法复杂度就是O(log2(n)).
简单来说，相当于第一个时钟周期，比较了N/2组值的大小(一次比较是比较两个值,所以是N/2组比较)，这样我剩下的问题就是在N/2个值里找最小。然后第二个时钟周期，进行N/4比较，这样剩下问题就是在N/4个值中找最小。
例如数据(1,2,4,5,7,8,9,-2)
第一个时钟周期，比较了(1,2) (4,5) (7,8) (9,-2) ，剩余值 1 ,4 ,7 ,-2
第二个时钟周期，比较了(1,4) (7,-2) ，剩余值1，-2
第三个时钟周期，比较了(1,-2) ，剩余值-2
这样就在log2(8)个周期里找到了最小值。
不知道这样算不算是，软件思维搞硬件。

[求助] 一个求一组数据最小值的问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

相关帖子

浏览过的版块

站长推荐 /2