问题描述:给定32个32bit的数，求出这32个数中的最大值以及次大值。
相似问题:给定32个数，求最大值。
首先，相似问题的解法相信大家都比较熟悉，有两种，第一种就是挨个比较，第1个和第二个比较得到最大值max,下一个周期，max和第三个比较得到最大值，更新max…。这种方法需要O(N)个时钟周期，性能较差。
另一种方法就是采用分治的思路，将32个数求最大值，看成前16个数求最大值max1、后16个数求最大值max2、求max1,max2最大值这三个问题，继续递归下去，就能得到第二种方法，体现在硬件结构上，就是加法树，同时，为了增大时钟频率，同时增大吞吐量，我们可以在加法树的每一级后面用寄存器打一拍，最终形成一个 O ( l o g 2 N ) O(log_2^N) O(log2N?)深度的树，如下图所示。
文章图片
类似的，对于本文所描述的问题，我们也可以采用分治的思路，下面这个图就很好的展示了对于本文中题目的解法。
文章图片
入上图所示，右上角是我们的基本模块，其中g1_*信号分别是上一级的最大值和次大值，g2_*信号也是上一级的最大值和次大值，这四个信号作为当前基本模块的输入，得到这4个数的最大值max1和次大值max2。为了满足基本模块输入的约束，我们在第一级中引入了一个二输入二输出的模块，其功能是输出两个输入值的最大值和次大值，这是很容易实现的。
RTL代码实现
基本模块代码:
`timescale 1ns / 1ps
//
// Company:
// Engineer:
//
// Create Date: 2022/02/24 20:58:22
// Design Name:
// Module Name: compare
// Project Name:
// Target Devices:
// Tool Versions:
// Description:
//
// Dependencies:
//
// Revision:
// Revision 0.01 - File Created
// Additional Comments:
//
//module compare(
input logic clk,
input logic [31:0] g1_max1,
input logic [31:0] g1_max2,
input logic [31:0] g2_max1,
input logic [31:0] g2_max2,
output logic [31:0] max1,
output logic [31:0] max2
);
always_ff@(posedge clk)
if(g1_max1g1_max2,g2_max1>g2_max2,g2_max1>g1_max1>g1_max2
if(g2_max2>g1_max1)
max2<=g2_max2;
else
max2<=g1_max1;
end
else
begin
//g1_max1>g2_max1>g2_max2,g1_max1>g1_max2
max1<=g1_max1;
if(g2_max1 顶层模块
`timescale 1ns / 1ps
//
// Company:
// Engineer:
//
// Create Date: 2022/02/24 21:07:43
// Design Name:
// Module Name: top
// Project Name:
// Target Devices:
// Tool Versions:
// Description:
//
// Dependencies:
//
// Revision:
// Revision 0.01 - File Created
// Additional Comments:
//
//module top(
input logic clk,
input logic start,
input logic [31:0] data [0:31],
output logic [31:0] max1,
output logic [31:0] max2,
output logic done
);
logic [31:0] stage1 [0:31];
logic [31:0] stage2 [0:15];
logic [31:0] stage3 [0:7];
logic [31:0] stage4 [0:3];
logic [31:0] stage5 [0:1];
logic start_ff1;
logic start_ff2;
logic start_ff3;
logic start_ff4;
//start
always_ff@(posedge clk)
{start_ff4,start_ff3,start_ff2,start_ff1}<={start_ff3,start_ff2,start_ff1,start};
//done
assign done=start_ff4;
//stage1
always_ff@(posedge clk)
begin
for(int i=0;
i<16;
i++)
if(data[2*i]>data[2*i+1])
begin
stage1[2*i]<=data[2*i];
stage1[2*i+1]<=data[2*i+1];
end
else
begin
stage1[2*i]<=data[2*i+1];
stage1[2*i+1]<=data[2*i];
end
end
//stage2,32-->16
genvar i;
generate
for(i=0;
i<8;
i++)
begin
compare U1
(
.clk(clk),
.g1_max1(stage1[4*i]),
.g1_max2(stage1[4*i+1]),
.g2_max1(stage1[4*i+2]),
.g2_max2(stage1[4*i+3]),
.max1(stage2[2*i]),
.max2(stage2[2*i+1])
);
end
endgenerate
//stage3,16-->8
generate
for(i=0;
i<4;
i++)
begin
compare U2
(
.clk(clk),
.g1_max1(stage2[4*i]),
.g1_max2(stage2[4*i+1]),
.g2_max1(stage2[4*i+2]),
.g2_max2(stage2[4*i+3]),
.max1(stage3[2*i]),
.max2(stage3[2*i+1])
);
end
endgenerate
//stage4,8-->4
generate
for(i=0;
i<2;
i++)
begin
compare U3
(
.clk(clk),
.g1_max1(stage3[4*i]),
.g1_max2(stage3[4*i+1]),
.g2_max1(stage3[4*i+2]),
.g2_max2(stage3[4*i+3]),
.max1(stage4[2*i]),
.max2(stage4[2*i+1])
);
end
endgenerate
//stage5,4-->2
generate
for(i=0;
i<1;
i++)
begin
compare U4
(
.clk(clk),
.g1_max1(stage4[4*i]),
.g1_max2(stage4[4*i+1]),
.g2_max1(stage4[4*i+2]),
.g2_max2(stage4[4*i+3]),
.max1(stage5[2*i]),
.max2(stage5[2*i+1])
);
end
endgenerate
//
assign max1=stage5[0];
assign max2=stage5[1];
endmodule【IC相关|数字IC面试手撕代码(一)】测试平台
`timescale 1ns / 1ps
//
// Company:
// Engineer:
//
// Create Date: 2022/02/24 21:30:57
// Design Name:
// Module Name: test_tb
// Project Name:
// Target Devices:
// Tool Versions:
// Description:
//
// Dependencies:
//
// Revision:
// Revision 0.01 - File Created
// Additional Comments:
//
//module test_tb();
logic clk;
logic start;
logic [31:0] data [0:31];
logic [31:0] max1;
logic [31:0] max2;
logic done;
//logic [31:0] ref_max1;
//logic [31:0] ref_max2;
always_ff@(posedge clk)
begin
for(int i=0;
i<32;
i++)
begin
data[i]=$urandom % 100;
//$display("%d\n",data[i]);
end
end
//start
initial
begin
start=0;
#20
start=1;
#10
start=0;
end
//clk
initial
begin
clk=0;
forever begin
#5 clk=~clk;
end
end//inst
top U(.*);
endmoduleRTL视图如下，可以看到，的确是一个树形的结构：
文章图片
推荐阅读
- FPGA|基于FPGA的Winograd CNN加速器
- FPGA|基于System Verilog的序列检测器
- FPGA|基于FPGA的MobileNet V2卷积神经网络加速器
- FPGA|DDR3原理总结
- Altera|quartus生成的各文件含义