数字IC面试手撕代码(一)

问题描述:给定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_max1g2_max2,g2_max1>g1_max1>g1_max2
    if(g2_max2>g1_max1)
        max2g2_max2,g1_max1>g1_max2
    max1