本项目为使用Chisel实现的基4-Booth乘法器，其目标是能够生成参数化的乘法器。
对于任意的一个有符号数B， 假设位宽
那么将偶数位拆开得到：
对于任意的数
将
对于任意一个部分积
其中
| 0 | 0 | 0 | +0 | 0 |
| 0 | 0 | 1 | +1 | |
| 0 | 1 | 0 | +1 | |
| 0 | 1 | 1 | +2 | |
| 1 | 0 | 0 | -2 | |
| 1 | 0 | 1 | -1 | |
| 1 | 1 | 0 | -1 | |
| 1 | 1 | 1 | -0 | 0 |
在这8种情况种，只会产生5种结果。其中为正数（和0）的部分计算非常容易，即
以5位数
然而可以发现，如第一个部分积
因此，拓展到任意位数的乘法，最多只需要
部分积的相加使用两种压缩器，分别为3-2压缩器与4-2压缩器。
3-2压缩器即全加器，只不过不计算s与ca的和，而是将s与ca均视为输出，ca比s高一位。
4-2压缩器为5-3压缩器的变形，通过级联cin和cout端口，可以实现由5-3压缩器到4-2压缩器的实现，同时由于实际结构，并不会因为级联而影响速度。
本项目参考玄铁C910上的乘法器结构，通过加入参数化，实现可以随开发者需要生成不同位数、结构的乘法器。
为实现不同位数和不同结构（主要是压缩树）的乘法器，项目采用带有偏移量的数据类型Value。采用偏移量可以尽最大程度减少压缩时压缩器需要的位宽。
class Value(val w: Int) extends Bundle {
val value: UInt = UInt(w.W)
var offset: Int = 0
}
object Value {
def apply(w: Int, value: UInt, offset: Int): Value = {
val v = new Value(w)
v.value := value
v.offset = offset
v
}
def apply(value: UInt, offset: Int): Value = {
apply(value.getWidth, value, offset)
}
}对于每一个Booth编码，输入只有固定的3位code
class BoothCodeUnit(val w: Int) extends Module {
val io = IO(new Bundle {
val A : UInt= Input(UInt(w.W))
val code : UInt = Input(UInt(3.W))
val boothCodeOutput: BoothCodeOutput = Output(new BoothCodeOutput(w))
})
// function
}因此使用递归的方式实现全部Booth编码：
object BoothCode{
def apply(w: Int, A: UInt, code: UInt): Vec[BoothCodeOutput] = {
val codewidth = code.getWidth
if(codewidth == 2){
VecInit(BoothCodeUnit(w, A, Cat(code, 0.U(1.W))))
}else if(codewidth % 2 == 0){
VecInit(apply(w, A, code(codewidth - 3, 0)) :+
BoothCodeUnit(w, A, code(codewidth - 1, codewidth - 3)))
}else{
VecInit(apply(w, A, code(codewidth - 2, 0)) :+
BoothCodeUnit(w, A,
Cat(code(codewidth - 1), code(codewidth - 1, codewidth - 2))))
}
}
}Booth编码模块的输出为Vec[BoothCodeOutput]。
class BoothCodeOutput(val w: Int) extends Bundle {
val product : UInt= UInt((w+1).W)
val h : UInt = UInt(2.W)
val sn : UInt = UInt(1.W)
}由这些输出可以进行组合形成部分积
Booth编码模块的输出需要转换称Value类型，送入压缩树中进行压缩。
如前文所示，部分积个数为 product与其之前的几位数和前一个Booth输出的h组合形成部分积PP 。
但是由于会剩余最后一个输出的h，所以将之前所有部分积前的1与最后的h组合成一个新的部分积。
同时，为满足玄铁C910特有的指令
因此对于16位的乘法器来说共有
将所有部分积转换为Value类，其偏移量代表部分积最低位和第0位的偏移大小。
实现一个固定位数的4-2压缩器。
class Compressor42(val w: Int) extends Module {
val io = IO(new Bundle() {
val p: Vec[UInt] = Input(Vec(4, UInt(w.W)))
val s: UInt = Output(UInt(w.W))
val ca: UInt = Output(UInt(w.W))
})
val xor0: UInt = Wire(UInt(w.W))
val xor1: UInt = Wire(UInt(w.W))
val xor2: UInt = Wire(UInt(w.W))
val cout: UInt= Wire(UInt(w.W))
val cin: UInt = Wire(UInt(w.W))
cin := Cat(cout(w - 2, 0), 0.U(1.W))
xor0 := io.p(0) ^ io.p(1)
xor1 := io.p(2) ^ io.p(3)
xor2 := xor1 ^ xor0
cout := xor0 & io.p(2) | ((~xor0).asUInt & io.p(0))
io.s := xor2 ^ cin
io.ca := xor2 & cin | ((~xor2).asUInt & io.p(3))
}对于不同结构的压缩树来说，每个压缩器自动判断位宽是极其重要的。因此，设计一个可以自动推算位宽并能自行连接的压缩器会大大减少开发效率。对于4-2压缩器来说，输入需要满足一个要求：
p0、p1、p2三者中至少有两者的最高位为0，以此确保最高位的cout输出为0，因而可以将其忽略。
为方便起见，将输入的数据首先进行排序，依照偏移量的大小，p0-p3由小到大。最终输出的偏移量和输入中最小的偏移量一致；同时输出位宽与输入的最大位宽一致。
object Compressor42 {
def apply(p: Seq[Value]): CompressorOutput = {
require(p.length == 4)
// Calculate the minimum offset
val offsets: Seq[Int] = for (l <- p) yield l.offset
val offsetMin: Int = offsets.min
// Get the used width of every value
val width: Seq[Int] = for (w <- p) yield w.value.getWidth
// Calculate the actual length of every value
val length: Seq[Int] = for (l <- offsets.zip(width)) yield l._1 + l._2
// Calculate the width need to be used
val lengthSorted: Seq[Int] = length.sorted
val widthMax: Int = if (lengthSorted(3) > lengthSorted(0)
&& lengthSorted(3) > lengthSorted(1)) {
lengthSorted(3) - offsetMin
} else {
lengthSorted(3) - offsetMin + 1
}
// Sort p by length
val pSorted: Seq[(Value, Int)] = p.zip(length).sortBy(p0 => p0._2)
// Instantiate Compressor42
// ***
// Code
// ***
compressorOutput
}
}事实上，如果将压缩器的位宽设置为最大位宽，如2倍数据宽度，并不影响最后的结果，因为综合时，编译器会自动进行优化，将未用到的门电路删除。
以65位乘法器为例，部分积共有35个部分积产生，序号由0至34。因此该矩阵为1维向量，共有35个元素，分别代表每个部分积输入的压缩器。
val connectCompressor: Seq[Int] = Seq(
0, 0, 0,
1, 1, 1, 1,
2, 2, 2, 2,
3, 3, 3, 3,
4, 4, 4, 4,
5, 5, 5, 5,
6, 6, 6, 6,
7, 7, 7, 7,
13, 13, 13,
0)如connectCompressor(3)=1，即
该矩阵为稀疏矩阵，表征压缩器之间的连接方式：1代表输入为s，2代表输入为ca，3代表输入为s与ca。
val outArray: Seq[Int] = Seq(
0, 1, 1, 2, 3, 4,
4, 5, 6, 7, 7,
8, 9, 10, 11, 12, 13,
14, 15, 15, 16, 17, 18)
val inputArray: Seq[Int] = Seq(
8, 8, 9, 9, 10, 10,
11, 11, 12, 12, 13,
14, 14, 15, 15, 16, 16,
17, 17, 18, 18, 19, 19)
val sOrCaOutArray: Seq[Int] = Seq(
3, 1, 2, 3, 3, 1,
2, 3, 3, 1, 2,
3, 3, 3, 3, 3, 3,
3, 1, 2, 3, 3, 3)
// ((from where, connect type), to where)
val topologyArray: Seq[((Int, Int), Int)] =
outArray.zip(sOrCaOutArray).zip(inputArray)
val layer: Seq[Seq[Int]] = Seq(
Seq(0, 1, 2, 3, 4, 5, 6, 7),
Seq(8, 9, 10, 11, 12, 13),
Seq(14, 15, 16),
Seq(17, 18),
Seq(19))由于后续有流水线的需求，因此采用一层一层生成压缩器。
在第一层中，输入为35个部分积，因此将部分积连接矩阵进行变换，将每个部分积的需要
对于每个压缩器的输出，均将其与压缩器序号进行绑定，即压缩器1输出的s的值为(Value = s, Int = 1)。
在每一层生成的过程中，同样采用递归的方式，直至Layer(i)中的每个压缩器均被生成。
class Compressor extends Topology {
val layerNum: Int = layer.length
def genLayer(l: Int, input: Seq[(Value, Int)]): Seq[(Value, Int)] = {
// Code
}
def genCompressor(a: Int, b: Int, input: Seq[(Value, Int)], topology:
Seq[((Int, Int), Int)]): Seq[(Value, Int)] = {
// topology -> ((from where, connect type), to where)
// input -> (value, from where)
// return -> (value, from where) require(a <= b)
if (a == b) {
// Instantiate Compressor a
// t0 -> ((from where, connect type), to where)
// Find all the connections that output is Compressor a
val t0 = for (c <- topology if c._2 == a) yield c
val inputIndex: Seq[((Value, Int), Int)] = input.zipWithIndex
var in: Seq[Value] = Seq()
var inIndex: Seq[Int] = Seq()
// The inputs that do not be used
var inRemains: Seq[(Value, Int)] = Seq()
// ***
// Code
// ***
// Instantiate Compressor
val outs = Compressor(in)
// Output all the values that remained
inRemains = for(i <- inputIndex if !inIndex.contains(i._2)) yield i._1
(for (i <- outs.toSeq) yield (i, a)) ++ inRemains
} else {
val inRemains = genCompressor(b, b, input, topology)
genCompressor(a, b - 1, inRemains, topology)
}
}
}最终每一层的输出为尚未进行连接的输出。最后的输出只会剩余2个。
加数是进行
流水线的加入相对比较简单，由于每个压缩层的输出均可以获得，只要将每个输出经过一次寄存器即可。
// Pipeline
def apply(down: Vec[Bool], in: Seq[(Value, Int)]): Seq[(Value, Int)] = {
val compressorLayer = new Compressor
var outputs: Seq[(Value, Int)] = in
for (i <- 0 until compressorLayer.layerNum) {
val pipeLayer = for (k <- compressorLayer.pipeline if k._1 == i) yield k._2
if (pipeLayer.isEmpty) {
outputs = compressorLayer.genLayer(i, outputs)
} else {
val layerDown: Bool = down(pipeLayer.head)
val outputsWire = compressorLayer.genLayer(i, outputs)
var outputsReg: Seq[(Value, Int)] = Seq()
for (c <- outputsWire) {
val regC = RegInit(0.U(c._1.value.getWidth.W))
val v = Wire(new Value(c._1.value.getWidth))
when (layerDown) {
regC := c._1.value
} .otherwise {
regC := regC
}
v.offset = c._1.offset
v.value := regC
outputsReg = outputsReg ++ Seq((v, c._2))
}
outputs = outputsReg
}
}
outputs
}而在最后一层（带有加数）加入流水线，由于只有3个数，因此可以直接在相加电路中将其经过寄存器。
输入随机数进行测试。
class MultiplierTest extends AnyFreeSpec with ChiselScalatestTester with BaseData {
"Calculate should pass" in {
val sub: Boolean = (Random.nextInt % 2 == 1)
println(s"sub = ${sub}")
val multiplier: Long = Random.nextInt
println(s"multiplier = ${multiplier}")
val multiplicand: Long = Random.nextInt
println(s"multiplicand = ${multiplicand}")
val addend: Int = Random.nextInt
println(s"addend = ${addend}")
val product: Long =
if(!sub)
multiplier * multiplicand + addend
else
addend - multiplier * multiplicand
println(s"product = ${product}")
test(new Multiplier()){ c =>
c.io.multiplier.poke(multiplier.asSInt(w.W))
c.io.multiplicand.poke(multiplicand.asSInt(w.W))
c.io.sub_vld.poke(sub.B)
c.io.addend.poke(addend.asSInt((w-1).W))
if (c.isPipeline) {
c.clock.step(1)
c.io.down(0).poke(true.B)
c.clock.step(1)
c.io.down(1).poke(true.B)
c.clock.step(1)
}
c.clock.step(1)
c.io.product.expect(product.asSInt((2*w).W))
}
}
(new ChiselStage).emitVerilog(
new Multiplier(),
Array("-td", "generated", "--full-stacktrace"))
}