Quartz 4

图灵完备乘法器的构建

5 min read

最近玩Tulin Complete,由于之前没有任何硬件设计的经验，在编程的第二关卡了一个多小时，通关要求实现任意一个数乘6的效果，我最终通过给ALU模块补全了对输入值进行左移、右移这两个功能，最终是以比较取巧的方式实现了这个效果。但这一关也启发我设计通用的乘法器

原理：朴素的逐位相乘法与十进制相同，列竖式计算。思考二进制下对这个”列竖式“的计算，启发我重新审视这个看起来很自然的过程。

列竖式的分解：列竖式在实际实现中，对两个被乘数的处理是不一样的。对任意乘法形式，具体可以依次序分解为

  1. “提取”出b的个位，记为c
  2. 将a与c相乘得到结果
  3. a整体进一位，b整体退一位以更新原来的“个位”
  4. 将与之前所有相加，得到局部乘法结果
  5. 重复1～4过程，直到b归零，循环终止

其中，第4步是出于存储空间的需要（只有deg4,deg5两个不参与运算和立即数暂存的备用寄存器）。我们列竖式时由于计算开销的问题，喜欢将第4步移动到循环终止之后，也就是求总和。

可以看出，这里竖式乘法是一个典型的按位遍历过程，无法在单个时钟周期里完成，时间复杂度与a的位数成线性关系。

实现：只考虑unsign情形，由于不知道b何时“归零”，而总位数有限（8位），可以直接将b右移的次数设成8，相应的，a也左移8次。先在reg2写进一个1，用reg0放a，而b放在reg1中，局部乘法结果暂存位置为reg4。b每次和reg2中的1按位与即可得到c（计算结果存在reg3），此时可以直接对reg3应用条件跳转，若c=0，不进行运算；若c=1，那么就说明这次的a需要保留，将a加到局部乘法结果中，最后更新a、b即可。

代码形式：

mov input reg0 #a     1
mov input reg1 #b     2
mov 1 reg2            3
and                   4
cond Equal0 11        5
mov reg1 reg5 #save b 6
mov reg0 reg1         7
mov reg4 reg2         8
add                   9
mov reg3 reg4 #update 10
mov reg0 reg1         11
Mov_Left #update a    12
mov reg3 reg0         13
mov reg5 reg1         14
Mov_right #update b   15
mov reg3 reg1         16

重复该代码第3～16行八次，即可实现unsign乘法器。

补充：这个乘法器对于一个8位无符号运算，每次循环要执行12个周期，总共算次，效率远低于实际乘法器效率。不幸的是，在现有架构下，它无法进一步优化了。这是由于目前我的计算机架构有如下限制：

  1. 左移/右移只能对reg1操作
  2. 所有ALU运算结果只能存到reg3
  3. 寄存器总共只有6个 此外第3点、第2点还导致我难以维护一个控制8次循环的flag，对于乘法操作只能复制粘贴了，代码复杂度进一步增加。 结论：学习这个乘法器不但摸清了计算机实现乘法的机制，还帮助我理解计算机架构和性能会怎样限制代码和速度。写成博客是一个很好的思维锻炼。

Graph View