电路设计中的分治法 —— 以 Chisel 实现优先编码器为例

在实现我的毕业设计时,遇到了这么一个需求:找出一组数字中最低(高)位的 1 的位置 —— 换句话说,就是一个优先编码器。显然最基本的版本实现起来很简单,尤其是我们还是在使用 Chisel 这么个懒人神器的情况下,初代代码如下(仅作为例子,下同),一行就解决了问题。

1
2
3
4
5
6
7
class Example extends Module {
val io = IO(new Bundle() {
val i = Input(UInt(64.W))
val o = Output(UInt(log2Ceil(64).W))
})
io.o := PriorityEncoder(io.i)
}

但是我们看生成的 Verilog 以及 yosys 的报告,发现资源消耗比较大,时序算下来也能把我血压给拉满。

以下是生成的 Verilog 的一部分,可以发现就是一组串联的 Mux,时序绝对会爆炸。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
module Example(
input clock,
input reset,
input [63:0] io_i,
output [5:0] io_o
);
wire [5:0] _io_o_T_64 = io_i[62] ? 6'h3e : 6'h3f; // @[Mux.scala 47:69]
wire [5:0] _io_o_T_65 = io_i[61] ? 6'h3d : _io_o_T_64; // @[Mux.scala 47:69]
wire [5:0] _io_o_T_66 = io_i[60] ? 6'h3c : _io_o_T_65; // @[Mux.scala 47:69]
wire [5:0] _io_o_T_67 = io_i[59] ? 6'h3b : _io_o_T_66; // @[Mux.scala 47:69]
...
wire [5:0] _io_o_T_121 = io_i[5] ? 6'h5 : _io_o_T_120; // @[Mux.scala 47:69]
wire [5:0] _io_o_T_122 = io_i[4] ? 6'h4 : _io_o_T_121; // @[Mux.scala 47:69]
wire [5:0] _io_o_T_123 = io_i[3] ? 6'h3 : _io_o_T_122; // @[Mux.scala 47:69]
wire [5:0] _io_o_T_124 = io_i[2] ? 6'h2 : _io_o_T_123; // @[Mux.scala 47:69]
wire [5:0] _io_o_T_125 = io_i[1] ? 6'h1 : _io_o_T_124; // @[Mux.scala 47:69]
assign io_o = io_i[0] ? 6'h0 : _io_o_T_125; // @[Mux.scala 47:69]
endmodule

分治法

后来我意识到,可以把分治思想应用到我们的电路中,也就是把输入分为左右两部分,分别处理,这样应该能把之前的串联的 $O(N)$ 层 Mux 串起来的电路转化为 $O(log N)$ 层的电路,以此可以获得更好的时序。话不多说,直接看代码,相信大家都可以看懂。

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
object BinaryPriorityEncoder {
def apply(in: Bits): Valid[UInt] = {
require(in.getWidth > 0)
val roundedInputWidth = 1 << log2Ceil(in.getWidth)
print(roundedInputWidth)
val roundedInput = Wire(UInt(roundedInputWidth.W))
roundedInput := in
checkedApply(roundedInput, roundedInputWidth)
}

def checkedApply(in: UInt, width: Int): Valid[UInt] = {
val outputWidth = log2Ceil(width)
val result = Wire(Valid(UInt(outputWidth.W)))

if (width == 2) {
val idx = in(1) && (~in(0)).asBool
val valid = in.orR()
result.bits := idx
result.valid := valid
} else {
val leftWidth = width >> 1
val leftResult = checkedApply(in(leftWidth - 1, 0), leftWidth)
val rightResult = checkedApply(in(width - 1, leftWidth), leftWidth)

result.valid := leftResult.valid || rightResult.valid
result.bits := Mux(leftResult.valid, leftResult.bits, Cat(rightResult.valid, rightResult.bits))
}
result
}
}

经过验证,结果一致。