花间一壶酒

举杯邀明月，对影成三人

0%

数字IC八股

发表于 更新于
本文字数： 12k 阅读时长 ≈ 23 分钟
梳理一些数字IC面试的高频常见问题，以及一些手撕代码的题目。

基础知识

数字电路设计

数字IC设计流程

跨时钟域传输

静态时序分析STA

功耗

频率

面积

常见电路

加法器

乘法器

参考：《Computer arithmetic _ algorithms and hardware designs》Parhami, Behrooz， 第9章

移位乘法器

原理

首先考虑无符号的整数乘法，即：

不妨考虑一个最简单的4位乘法的情况：

乘数表示为a，被乘数x的每一位为$x_0,x_1,x_2,x_3$。一个很自然的想法是分别取出被乘数x的每一位，与a进行乘法(与操作)，之后乘以2的幂。

左移还是右移：
上述算法的流程，可以通过左移或者右移实现。右移看上去似乎比较自然，每次右移都是取出了x的最低位，并且与a相乘相加。右移可以将上述式子从上到下进行累加，其迭代公式如下：

需要注意的是，这个公式每次将总体结果右移了移位，k次之后相当于总体右移了k位，为了抵消这种操作，需要提前将a左移k位。这很容易实现，只需要将a的值放在一个2k宽度的寄存器的前k位即可。在经过k次迭代后，我们有：

可以看到，如果将部分和$p_0$初始化为0，计算得到的是一个简单的乘法:
$$p=ax$$

如果将其初始化为$y2^k$,则可以计算$ax+y$,也就是乘加操作。这样的好处是不需要额外的硬件资源。右移的计算过程如下：

我们可以写出如下算法流程：

对应的电路如下：

a的值一开始放在一个2k长度的部分积寄存器的左半边，每次取出其高k位，与经过x对应位选择的multiplicand相加，结果写回部分积寄存器的高k位。

右移乘法的好处是可以节省加法器的位宽，对应的加法器只需要k-bit,如果是左移计算，则需要2k位宽的加法器:

此外，我们可以将x放在部分积寄存器的后k位来进一步节约资源。考虑加法器的进位情况，最终的摆放如下：

另外值得注意的一点是图中的mux，其实可以用一系列的与门来代替，与门的一端连接shift后x的一位。

如果是后续有符号的乘法，则使用真的mux,通过x来选择a,a的补码或者0。

有符号的移位乘法

对于有符号数，一个办法是在计算前，对负数计算其补码，得到对应的正数，正数相乘得到相应的绝对值，之后再根据
结果决定是否转化为负数。

但是这样的3个过程太慢了，可以考虑直接在每次迭代的时候进行计算，一个示例流程如下：

当乘数为负的时候，一开始正常的相乘相加。最后的符号位则需要计算减法(2’s completion)。对应的电路结构如下：

因为符号位的存在，这里使用一个k+1位的加法器。

BOOTH编码

此外还可以使用booth编码，将{0，1}集合表示的数映射到{-1,1}的集合上去。

另外，一个数x乘以一个常数a的问题，如果常数a已知，可以转化为一系列移位加法。

例如8’b11010001,可以将1分别左移7，6，4位后求和，然后再+1。

这是因为加法和移位运算是图灵完备的。但这种方法的问题在于，一个数的二进制表达中的1越多，所需要的加法次数就越多，相应的周期也就越长。

而结合booth编码，可以同时引入加法，减法和移位运算，例如，C=23，其二进制表示为
10111而：
$$
23=2^4−2^2+2^1+2^0 $$

这样可以有效减少指令数目

因此，在无法乘法和除法并不是计算机的基础指令，而是可以通过编译器将其修改为一系列移位和加减法来间接实现。在乘以一个常数时，如果乘法占用的周期数过高，也可以通过编译器优化为移位和乘法来解决。
有趣的是，给定一个整数常数 $C$，如果允许使用移位、加法和减法的组合，找到最优的（最少操作数的）表达形式确实是一个NP 完全问题。这个问题在计算机科学中被称为最小移位加法问题（Minimum Addition-Subtraction Chains Problem）。

高基乘法器

上面的移位乘法器存在一个问题，就是每次只能计算1位，运算周期过长，这在现代处理器中往往是不可接受的。

一个自然的相反是一次计算多位，也就是采用高基乘法器。

例如，一个k位的二进制数，也可以看成是k/2位基数(radix)为4的数（即k/2位4进制数），或k/4位，基数为8的数。

除法器

移位除法器

无符号除法

一个典型的二进制整数除法的流程如图，2kbit的被除数z除以除数d,商为q,余数为s。

由于结果q的每一位不是0就是1，其与d的乘积不是0就是d本身。所有问题转化为z对d或d的移位结果的一系列减法。

在一系列右移减法的过程中，除法的问题在于，一开始不知道商q的每一位是0还是1，需要一次额外的估计(比较)操作来得到商的一位，然后再执行减法。

此外除法与乘法的另一个不同在于，虽然2个k位数的乘积不会超过2k位，但是一个2k位的数除以k位的数，其结果可能超过K位(这很好理解，除数为1的极端情况下，结果不变还是2k位)。因此在计算之前，需要进行溢出检测：

如果要得到一个k位的商q，那么q一定小于$2^k$,而余数s一定小于d,估算z的最大值，有：
$$z < (2^k-1)d + d < 2^kd$$

也就是说d左移k位后一定大于被除数z,换言之，z的最高k位必须小于d,才能保证商的位数小于等于k。

图13.1可以用下面的迭代公式来表示：

除法是一个左移迭代算法，因为商q的每一位结果是从高到底获得的，q乘以2^d是为了这一点。在k次迭代后，有：

一个例子如下：

对应的算法为：

需要注意的是，当且仅当每次被除数的前k位大于除数时，才执行减法操作，否则应当保持被除数不变，下一次移位后再计算(对应该位的商为0时的情况)。

而被除数前k位大于除数，有以下2种可能：

  1. 加法器的进位 cout = 1;
  2. 余数寄存器的最高位为1(因为移位后可以获得$2^{k+1}$,而任何一个k bit的数小于$2^{k+1}$)

只有这种情况满足时，商的对应位才为1，同时执行减法。

一个verilog实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
module divider #(
    K = 32
) (
    input [2*K-1:0]  dividend,
    input [K-1:0]    divisor,

    output [K-1:0]  qoutient, 
    output [K-1:0]  remainder,

    input  valid_i,
    input  ready_i,
    output busy, // the divider is busy in computing
    output valid_o,
    output ready_o,
    input clk,
    input rst_n 
);
    localparam WIDTH = $clog2(K);
    reg [K-1:0] Rp; // rp is initialized to  high k bits of dicidend
    reg [K-1:0] Rq; // rq is initialized to  low  k bits of dicidend
    reg [WIDTH:0] Rc; // shift counter, initialized to K
   
    reg valid;
    // combinational logic

    wire [K-1:0] neg_divisor  = ~divisor;
    wire cout;
    wire [K-1:0] adder_result;
    wire zero_flag;
    wire overflow_flag;
    wire load_en = Rp[K-1] | cout;
    
    wire [K-1:0] Rp_shift = {Rp[K-2:0],Rq[K-1]};
    wire [K-1:0] Rp_next = load_en ? adder_result : Rp_shift;
    wire [K-1:0] Rq_next = {Rq[K-2:0],load_en};

     adder #(.N(K)) u_adder(
        .A             (Rp_shift             ),
        .B             (neg_divisor             ),
        .carry_in      (1'b1      ),
        .result        (adder_result        ),
        .zero_flag     (zero_flag     ),
        .overflow_flag (overflow_flag ),
        .carry_out     (cout     )
    );

    always @(posedge clk or negedge rst_n) begin
        if(!rst_n)begin
            Rc <= {(WIDTH+1){1'b0}};
        end
        else if (~busy & valid_i)begin
            Rc <= K;
        end
        else begin
            Rc <= Rc - 1'b1;
        end
    end

    always @(posedge clk or negedge rst_n) begin
        if(!rst_n)begin
            Rp <= {K{1'b0}};
        end
        else if (~busy & valid_i)begin
            Rp <= dividend[2*K-1:K];
        end
        else begin
            Rp <= Rp_next;
        end
    end

    always @(posedge clk or negedge rst_n) begin
        if(!rst_n)begin
            Rq <= {K{1'b0}};
        end
        else if (~busy & valid_i)begin
            Rq <= dividend[K-1:0];
        end
        else begin
            Rq <= Rq_next;
        end
    end

    always @(posedge clk or negedge rst_n) begin
        if(!rst_n)begin
            valid <= 1'b0;
        end
        else if ( valid_i & (Rc == {{WIDTH{1'b0}}, 1'b1}))begin
            valid <= 1'b1;
        end
    end


    assign busy = (Rc != {(WIDTH+1){1'b0}});
    assign ready_o = ~busy & ready_i;
    assign valid_o = valid & ~busy;
    assign qoutient = Rq;
    assign remainder = Rp;
    
endmodule

alt text

事实上，这种实现叫做restoring的算法，每次需要判断加法器的结果，才能决定寄存器需要更新的值。

如果进行时序分析，则每个时钟周期需要做到以下事情：

如果想要优化这个时序，可以使用non-restoring的算法。

在 non-restoring算法种，每个周期都减去一个被除数，而如果当时的余数小于被除数而错误的剪掉了一个被除数，则可以在下一个周期加回来。
这是因为下一个周期会进行shift left的操作，相当于已经提前减去了2个被除数，因此只需要再加上一个被除数，仍然能达到减去一个被除数的效果。

有符号除法

在上述的restoring 算法中，每个周期总是减去一个被除数或是不减，也就是说被除数的系数为{0,-1},而在non-restoring的算法中，没周期总是
减去或加上一个被除数，也即其系数为{-1,1}。而在除法结束时，余数的符合总是与被除数相同(这是有符号除法的定义决定的)。

因此，可以考虑直接处理有符号除法：

若当前的余数与被除数的符合相同，则q对应的位为1，否则为-1。

而在计算结束后，还需进行如下步骤：

即

  1. 先将商的表示由{-1,1}的二进制空间映射回标准的{0,1}空间。
  2. 如果余数的符合与商的不一致，说明多减去/加上了一个被除数。需要对结果进行矫正。

对于1，做法应该是：

即将所以的对应位置的-1变为0，然后将最高位取反，整体左移一位后最低位补1。这种转化很简单，可以通过硬件，在计算出商的同时完成。

在初始化时先设置商的符号位，然后根据之后每次是加法还是减法操作来生成对应位的0,1,最后在商的末尾补1.

对于2：

矫正时需要将商加上或减去1，同时将余数减去或加上被除数。由于1的变化算法使得商的最后一位为1，导致商总是奇数，因此当商为偶数时，矫正不可避免。

该算法的一个示例过程如下：

对应的电路为：

根据上述思路实现的移位除法器代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
//=====================================================================
//
// Designer   : wenkai_sjtu@163.com
//
// Description:
//  an signed left shift divider, using nonerestoring algrithm
//  no overflow and zero  divisor check
// Revision History: 
// ====================================================================

module signed_divider #(
    K = 32
) (
    input [2*K-2:0]  dividend,
    input [K-1:0]    divisor,

    output [K-1:0]  qoutient, 
    output [K-1:0]  remainder,

    input  valid_i,
    input  ready_i,
    output busy, // the divider is busy in computing
    output valid_o,
    output ready_o,
    input clk,
    input rst_n 
);

    //   use state machine 
    localparam IDEL = 2'b00, SHIFT=2'b01, CORRECT = 2'b10, OUTPUT = 2'b11;

    localparam WIDTH = $clog2(K) + 1; // expand 1 bit to avoid overflow 

    reg [K-1:0] Rp; // rp is initialized to  high k bits of dicidend
    reg [K-1:0] Rq; // rq is initialized to  low  k bits of dicidend
    reg [WIDTH-1:0] Rc; // shift counter, initialized to K
    reg [1:0]   state; // the state of divider
    reg [1:0]  state_next;

    wire sign_dividend = dividend[2*K-2]; // sign bit of dividend
    wire sign_divisor = divisor[K-1]; // sign bit of divisor 
    wire sign_remainder = Rp[K-1];//  sign bit of remainder

    wire [K-1:0] divisor_neg = ~divisor;  // 1's complement of divisor
    wire shift_sub = ~(sign_remainder ^ sign_divisor); // sign of remainder equal to sign of divisor, sub ,otherwise add
    wire need_correct;
    wire correct_sub;
    reg  sub;   // substract flag of adder

    wire cout;
    wire [K-1:0] adder_result;
    wire zero_flag;
    wire overflow_flag;


    wire [K-1:0] Rp_shift = {Rp[K-2:0],Rq[K-1]};
    wire [K-1:0] Rq_shift =  {Rq[K-2:0],shift_sub};
    wire [K-1:0] Rq_con = {~Rq[K-2],Rq[K-3:0],1'b1};

    reg [K-1:0] addend1;  // operand 1 of adder, net
    reg [K-1:0] addend2;  // operand 2 of adder, net
    reg [WIDTH-1:0] Rc_next;
    reg [K-1:0] Rq_next ;
    reg [K-1:0] Rp_next ;



    adder #(.N(K)) u_adder(
        .A             (addend1             ),
        .B             (addend2             ),
        .carry_in      (sub      ),
        .result        (adder_result        ),
        .zero_flag     (zero_flag     ),
        .overflow_flag (overflow_flag ),
        .carry_out     (cout     )
    );

    // when shift finish, the result needs correct if sign of remainder is different to sign of dividend
    assign   need_correct = (Rc == {WIDTH{1'b0}})  & (sign_remainder ^ sign_dividend);

    assign   correct_sub =  need_correct & (  
            (sign_remainder  & sign_divisor) // remainder < 0, divisor < 0 but dividend > 0
        |   (~sign_remainder & ~sign_divisor)); // remainder > 0, divisor > 0 but dividend < 0
        // in this 2 case we need to substract another divisor to correct the result otherwise we need to add

    always @(*) begin
        // default value
        Rp_next = dividend[2*K-2:K-1];
        Rq_next = {dividend[K-2:0],1'b0};
        Rc_next = K-2;
        sub = shift_sub;
        addend1 =  Rp_shift;
        addend2 =  shift_sub ? divisor_neg : divisor;
        case (state)
        IDEL : begin
            if(valid_i)begin
                state_next = SHIFT;
            end
            else begin
                state_next = IDEL;
                Rp_next = Rp;
                Rq_next = Rq;
                Rc_next = Rc;
            end
        end 
        SHIFT:begin
            Rp_next =  adder_result;
            Rq_next =  Rq_shift;            
            sub = shift_sub;
            addend1 =  Rp_shift;
            addend2 =  shift_sub ? divisor_neg : divisor;
            if(Rc != {WIDTH{1'b0}})begin
                state_next = SHIFT;     
                Rc_next =  Rc-1'b1;     
            end
            else begin
                state_next = CORRECT;
                Rc_next = Rc;  // keep rc=0
            end
        end
        CORRECT:begin
            state_next = OUTPUT;
            Rp_next = need_correct ? adder_result : Rp;
            Rq_next = need_correct ? (correct_sub ? Rq_con + 1'b1 : Rq_con - 1'b1) : Rq_con;
            Rc_next = Rc;
            addend1 = Rp;
            addend2 = correct_sub ? divisor_neg : divisor;
            sub = correct_sub;
        end
        OUTPUT:begin
            if(ready_i & ~valid_i)begin // wait next data 
                state_next = IDEL;
            end
            else if (ready_i & valid_i)begin // begin next computation
                state_next = SHIFT;
            end
            else begin  // wait result to be stored
                state_next = OUTPUT;
                Rp_next = Rp;
                Rq_next = Rq;
                Rc_next = Rc;
            end
        end
        endcase
    end

    always @(posedge clk or negedge rst_n) begin
        if(!rst_n)begin
            state <= IDEL;
            Rp    <= {K{1'b0}};
            Rq    <= {K{1'b0}};
            Rc    <= {WIDTH{1'b0}};
        end
        else begin
            state <= state_next;
            Rp    <= Rp_next;
            Rq    <= Rq_next;
            Rc    <= Rc_next;
        end
    end

    assign busy = ((state == SHIFT) | (state == CORRECT));
    assign valid_o = (state== OUTPUT);
    assign ready_o =  ~busy & ready_i;
    assign qoutient = Rq;
    assign remainder = Rp;

endmodule

上述实现采用状态机进行控制，在移位完成后的一个周期内进行结果矫正，之后输出。使用时需要自行保证除数非0以及无溢出。
(即前面讨论的,被除数的高K位必须小于除数，有一个简单的做法是对被除数进行符号扩展，比如32位的有符号除法，先将被除数扩展为63位再进行计算，可以避免溢出)。

{width=300 height=200 align=center}

体系结构

经典5级流水线

cache

GPGPU架构

NPU架构

代码

SV

UVM

经典题型

时钟分频

波形检测

异步FIFO

面试真题

词频检测

题目描述： 使用verilog设计实现一个模块，对长度为byte(8 bits)的单词进行词频检测。假设每周期输入一个单词，共4096个单词,统计每个单词的出现次数，可以不考虑电路的输出。面试时不要求写出代码，只要求给出思路，口头描述电路的构成。

当时初步回答是，不同单词的编码本身可以看作单词的地址，用这个地址可以将单词分开，不考虑面积的情况下，可以在一个256to1的mux后接256个counter,每收到一个单词，将对应位置的counter+1。面试官进一步追问，如果考虑面积开销，应该怎样优化。回答：counter换成memory或register file），然后增加一级流水线，每收到一个单词将对应位置的数据读出，然后将该数据+1，下个周期将该数据写回，同时读入一个新的数据。如果连续2个周期出现同一个单词的地址冲突，考虑数据的forwarding,将来不及写回的数据作为读数直接+1。

参考设计代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
module wordcounts (
    input [7:0] data_in,
    input   clk,
    input   rst_n
);
    reg [12:0]    word_counts;
    wire [12:0]  read_data[255:0];
    wire [255:0]   write_en;
    genvar  i;
   
    generate
        for (i=0 ;i<256;i=i+1 ) begin
            assign write_en[i] = (data_in == i[7:0]);
            sim_dfflr #(13) counter(word_counts+ 1'b1,  read_data[i] ,write_en[i],clk,rst_n);
        end
    endgenerate
    assign word_counts = read_data[data_in];
    
endmodule



module sim_dfflr #(
    N=8
) (
    input[N-1:0] din,
    output reg[N-1:0] qout,
    input load_en,
    input clk,
    input rst_n
);
    always @(posedge clk or negedge rst_n) begin
        if(!rst_n)
            qout <= {N{1'b0}};
        else if (load_en)
            qout <= din;
    end
endmodule

思路是先定义寄存器，然后使用generate语句生成一个寄存器堆。对应的data_in作为load_en信号使能对应位置寄存器进行写操作。这里不需要考虑地址冲突时的bypass问题，因为事实上并不是先读后写，而是第一种，计数器加上mux的思路（读操作并没有耗费一个周期的时间）。
因此下面这种写法更直观：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
module wordcounts (
    input [7:0] data_in,
    input   clk,
    input   rst_n
);
    wire [12:0]  read_data[255:0];
    wire [255:0]   write_en;
    genvar  i;
   
    generate
        for (i=0 ;i<256;i=i+1 ) begin
            assign write_en[i] = (data_in == i[7:0]);
            sim_dfflr #(13) counter( read_data[i]+ 1'b1,  read_data[i] ,write_en[i],clk,rst_n);
        end
    endgenerate
    
endmodule

对应的testbench如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
module tb_top;

    `define CLK_PERIOD  10
    logic clk;
    logic rst_n;
    logic[7:0] data_in;
    class word;
        rand byte data;
        logic [12:0]  counts[256];

        function counts_init;
            foreach (this.counts[i])begin
                counts[i] = 13'b0;
            end
        endfunction

        task  data_gen(input clk, output[7:0] data_out);
            this.randomize();
            data_out = this.data;
            $display("generate ramdom words：%c ",this.data);
            counts[data_out] += 13'b1;
        endtask //
    endclass 

    word test_word = new();

    initial begin
        clk=1'b0;
        rst_n = 1'b0;
        #1 rst_n = 1'b1;
        # (4097*`CLK_PERIOD)
        for (int i = 0;i<256 ;i++ ) begin
            if (test_word.counts[i]==u_wordcounts.read_data[i])
                $display("word %2h count right,number:%d",i,test_word.counts[i]);
            else $display("word %2h count wrong! generate %d, counts %d",i,test_word.counts[i],u_wordcounts.read_data[i]);
        end
        $finish();
    end

    initial begin
            forever #(`CLK_PERIOD/2) clk = ~clk;  
    end

    initial begin
        test_word.counts_init();  
        $display("wait for reset");
        @(posedge rst_n);  
        $display("reset success");
        fork
        forever begin
            @(posedge clk);
            test_word.data_gen(clk, data_in);
        end
        join_none
        
    end

    initial begin
        $fsdbDumpfile("tb_top.fsdb");
        $fsdbDumpvars(0, tb_top, "+mda");
    end

    wordcounts u_wordcounts(
        .data_in (data_in ),
        .clk     (clk     ),
        .rst_n   (rst_n   )
    );

endmodule

测试结果如下：