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

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

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

简单写下我的思路，
按你的例子，一个四位计数器1当地址，每次读取两个寄存器中的值。四位寻址32位，所以每次是两个地址。(第五位高位一个0,一个1)。比完大小再写回寄存器(比如写回高位为0的地址)。
计数器1依次递增。
再加一个计数器2，用来控制计数器1的有效位数。每次计数器1从全0增加到全1,计数器2增一(也可以减一)。由计数器2相当于一个数据选择器的控制位。控制地址是由计数器1的哪几位提供。
每次都是比较完大小，将小的写回寄存器保存起来。
就是简单写下思路，细节还得推敲。大概就是两个计数器一个mux一个存储空间的大小。
如果数据多了，用ram，在读取数据的时候就得优化下。
如果原始数据需要保留，需要写到新的空间，地址就得再斟酌下。
手机打的，不容易。

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

看我上面的留言。谢谢回复

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

1. module comp #(
   
2.     parameter                       U_DLY = 1
   
3. )
   
4. (
   
5. input                           sys_clk,
   
6. input                           rst_n,
   
7. 
   
8. input           [31:0]          num1_i,
   
9. input           [31:0]          num2_i,
   
10. input           [31:0]          num3_i,
    
11. input           [31:0]          num4_i,
    
12. 
    
13. input                           cmp_en,
    
14. 
    
15. output  reg                     res_vld,
    
16. output  reg                     min_num
    
17. 
    
18. );
    
19. 
    
20. 
    
21. reg     [31:0]                  stg1_res1_o;
    
22. reg     [31:0]                  stg1_res2_o;
    
23. reg                             cmp_en_r;
    
24. 
    
25. always @(posedge sys_clk or negedge rst_n)
    
26. begin
    
27.     if(rst_n == 1'b0)
    
28.         begin
    
29.             cmp_en_r <= #U_DLY 1'b0;
    
30.             res_vld <= #U_DLY 1'b0;
    
31.         end
    
32.     else
    
33.         begin
    
34.             cmp_en_r <= #U_DLY cmp_en;
    
35.             res_vld <= #U_DLY cmp_en_r;
    
36.         end
    
37. 
    
38. end
    
39. 
    
40. 
    
41. // compare stage1
    
42. always @(posedge sys_clk or negedge rst_n)
    
43. begin
    
44.     if(rst_n == 1'b0)
    
45.         stg1_res1_o <= #U_DLY 32'h0;
    
46.     else if(cmp_en == 1'b1)
    
47.         begin
    
48.             if(num1_i >= num2_i)
    
49.                 stg1_res1_o <= #U_DLY num2_i;
    
50.             else
    
51.                 stg1_res1_o <= #U_DLY num1_i;
    
52.         end
    
53.     else         ;
    
54. end
    
55. 
    
56. 
    
57. always @(posedge sys_clk or negedge rst_n)
    
58. begin
    
59.     if(rst_n == 1'b0)
    
60.         stg1_res2_o <= #U_DLY 32'h0;
    
61.     else if(cmp_en == 1'b1)
    
62.         begin
    
63.             if(num3_i >= num4_i)
    
64.                 stg1_res2_o <= #U_DLY num4_i;
    
65.             else
    
66.                 stg1_res2_o <= #U_DLY num3_i;
    
67.         end
    
68.     else         ;
    
69. end
    
70. 
    
71. // compare stage2
    
72. always @(posedge sys_clk or negedge rst_n)
    
73. begin
    
74.     if(rst_n == 1'b0)
    
75.         min_num <= #U_DLY 32'h0;
    
76.     else if(cmp_en_r == 1'b1)
    
77.         begin
    
78.             if(stg1_res1_o >= stg1_res2_o)
    
79.                 min_num <= #U_DLY stg1_res2_o;
    
80.             else
    
81.                 min_num <= #U_DLY stg1_res1_o;
    
82.         end
    
83.     else                 ;
    
84. end
    
85. 
    
86. endmodule

复制代码

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

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

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

    题目没有说得很清楚，我这里补充一些。    首先，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)个周期里找到了最小值。
    不知道这样算不算是，软件思维搞硬件。

    我明白你的意思了，我认为这种分治的思维方式是对的，尤其在软件上，而在硬件上可能需要再多考虑几个因素，因为：
软件：金钱成本=运行机时。所以用运行时间来衡量算法优劣。
硬件：金钱成本=芯片面积。另外还要考虑频率等等。
以上二者是有些区别的，所以我的观点是，似乎问题需要进一步地考虑

刚刚忘记了你是在fpga中实现，那么我觉得只要fpga能装下就不存在面积的考量。
fpga中需要考虑什么呢?

    你说得和我想法一致，就是在于我想实现的并不只是4个数的比较，还是不确定的N个，假定N可以很大。    仔细想想，我的这个问题在实际中根本没有实用度。毕竟，只有当N个数据能同时给出并输入到模块(假定这个找最小这个问题被我写成一个模块)，这样就要求模块能输入N个数据，而且我还得有足够多的寄存器来存储这些数据，这个问题才能像我题目中那样思考。不然，如果数据是存在片内ram、rom或是ddr3中，直接依次取出依次比较就行了。
    虽然，知道这个问题实际上基本不成立，但是还是想讨论一下，参数化的实现方式。

我理解小编的意思是他这种比较方法，所需要的电路拍数，如当输入为16时，需要log2n=4拍，但我感觉还有比这更快的，不知有高手可以支招吗?

    不过其实都属于Log(n)这个级别，估计再降不下去了，再低一个级别就是O(c)了,c为常数。
    而且数据量少的话，logn级别的优势也体现不出来，只有数据有个几千上万个，logn才明显远小于n。