RISCV乘法硬件加速算法原理/单精度规格化与非规格化最小正数问题/F/D标准扩展与I问题

乘法算法的一般算法的演变和使用硬件加速算法原理分析

乘法算法与纸笔算法是一样的.二进制乘法,由于二进制的特殊型(只有1或0),当乘数的某一位是1时,就将被乘数复制到合适的位置,如果是0时,就将0复制到合适的位置,然后全部加起来.计算机的乘法算法与之同源.
一般算法就是上述算法,只不过在"复制到合适的位置"这里,就是将每一次的被乘数左移一位,使其扩大2的幂.
进制由什么定义?我们也可以根据这个2进制转10进制公式就可以看出端倪:
1010 = 12^3 + 02^2 + 12^1 + 02^0
1与0决定是否是数值0,2的幂决定移位的位数,然后最后全部相加.
乘法与之类似:
1010 * 1001
110102^0 + 010102^1 + 010102^2 + 110102^3
硬件处理这个结果就是:
3.加法器将结果累加.
2.2的幂是将1010左移
1.1与0决定这个值是否"存在"(为0)
需要加法器,移位器,逻辑判断组件三个
现在只有一个加法器,一个移位器,一个逻辑判断组件.使用这个简陋的硬件条件我们自然就可以慢慢的,一步一步一个加法的将结果算出来,这就是计算机乘法算法的一般算法.每一次迭代,需要3个时钟(这是显而易见,每一个加法的操作数都需要3步才能得来).
我们使用并行计算,将移位与逻辑判断/加法并行执行,这样每一次迭代就是1个时钟.这就是优化算法.
但是不管怎么样,我们需要计算的乘数是多少(n位)位的,加法就得执行n-1次.即使使用优化算法,也需要n-1个时钟.
摩尔定律使我们有了更多的硬件资源来加速乘法:这里的加法原理主要是体现在多个加法的同时相加,上诉有4个操作数需要相加,我们就在其中放三个加法器,一个加法器计算:110102^0 + 010102^1
一个加法器计算:010102^2 + 110102^3
这两个加法器是并行计算的,然后将结果传输到第三个加法器,这样本来需要3个时钟周期的加法加算,现在缩短为只需要log(2)4个时钟周期,当位数很大时(64),这里节省的时钟周期数是很多的.(这里建立的就是一个并行树,每一个树的节点的执行结果都是中间结果)
这里的前提条件是所有的乘数位数都已经分析完毕,并且知道了对应位的被乘数是本身还是0.
很容易将这个设计流水化.

除法算法的最简单设计

除法算法与纸币算法一样,需要一步一步计算,不能跳转,与乘法算法不同的时,由于我们在做除法算法时,人是可以一瞬间看出两个数的大小关系,而计算机不能,所以在除法算法中需要额外的"比较操作".
在纸笔算法中,除法是从左到右的顺序依次进行计算,由于上述的二进制特殊型,当商中某一位被填写为1时,表示剩余的中间结果可以减去除数.我将这个剩余的中间结果称为伪余数,当执行到最后时,这个伪余数就成了余数.
除法与乘法不同的是,乘法中的每一步的中间结果是可以由与门并行计算得出,最后由并行树相加,除法中的每一步有必须依赖与上一步的结果,所以这里除法的加速运算很难,目前通过预测多位商再纠正错误的预测方法来加速除法,我并不知道具体算法是怎么做的.
有符号除法算法:简单设计就是将符号记住,然后进行无符号除法,商与被除数和除数的符号共同决定,余数由被除数决定.

RISC-V关于除法溢出和除数为0的处理

RISC-V软件层面来检查除数0和除法溢出情况.
在被处数和除数,商的硬件表示位数都一致的情况下,我想不到有什么情况会导致除法溢出
现象:RISC-V计算机在发生上/下溢时不会引发中断
这里需要软件来读取浮点控制和状态寄存器(fcsr)

单精度规格化最小正数与非规格化最小正数问题

IEEE 754标准:
指数 尾数 表示对象
0 0 0
0 非0 非规格化数
1-254 任意 规格化数
255 0 无穷
255 非0 NaN
由IEEE 754标准可知,最小规格化正数
0 | 0000 0001 | 0000 0000 0000 0000 0000 000
表示2^(-126)
则单精度最小非规格化正数:
0 | 0000 0000 | 0000 0000 0000 0000 0000 001
表示2^(-127 + -23) = 2^(-150)
然而给出的就是,由于最小指数是-126,所以最小非规格化正数就是2^(-149)
即:
0 | 0000 0001 | 0000 0000 0000 0000 0000 001
这里被解读成0.0000 0000 0000 0000 0000 001 * 2^(-126) = 2^(-149)

根据我的理解:由于浮点数表示法建立之初所能正规表示的最小正数是
0 | 0000 0000 | 0000 0000 0000 0000 0000 000
被计算机自动解读为:1.0 * 2^(-127)
这里是隐藏了最高有效位1,展开后就是这个值.
由于尾数字段没有更完全的利用好,并且我们想要表示比2^(-127)更小的数,我们便定义了一种非规格化表示法:
当指数全部是0后,并且尾数非0,则隐藏位不再是1,而是0,于是最小的单精度表示的正数诞生:
0 | 0000 0000 | 0000 0000 0000 0000 0000 001
计算机识别出来指数字段为0,尾数字段非0,于是隐藏位为0,展开后就是:
0.0000 0000 0000 0000 0000 001 * 2 ^ (-127) = 2 ^ (-150)
这里便缩短了在0与最小的规格化正数之间的差距.它们具有与零相同的指数,但是有效位非零(尾数字段).并且允许尾数字段逐渐变小,直到变为0(逐步下溢)
故原书给出为2^(-149),我无法理解.

十进制小数转换为二进制小数(怎么简单怎么来)

小数->分数->分母化为2的幂/分子化为二进制
将小数的每一位拆分出来,然后再合并更简单

IEEE的浮点表示的初衷以及指数字段的变化

浮点表示采用的不是补码表示法,而是符号和数值表示法.
浮点比较是比较难的,所以我们在安排浮点表示法的时候,应该尽可能的想到如果比较两个浮点数,怎么更快?
1.正数一定比负数大
这就是浮点表示法将符号位放置第一位的原因
2.指数更大的数,一定更大
所以浮点中的指数字段放在符号位之后
3.指数有正有负,比较大小比较费事,采用移码
所谓的移码:8位指数字段表示的范围是0-255,要想一眼看出哪个更大,所以我们定义以127为界限,127以上的数用来表示正数,127以下的数用来表示负数.127就是偏移值
真正指数值+127 = 指数字段值

浮点数加减法和乘法

浮点数的算术运算不过是对对应的字段进行对应的不同处理而已.
在加减法中,就是先处理指数对齐问题,然后相加,规格化,舍入,检查,写入
乘法中,对指数先处理,然后将有效数进行乘法运算,然后规格化,舍入,检查,写入
由于浮点数表示法的本质是符号与数值表示法,所以在加减法的时候,要将符号与数值进行转换为补码
而乘法则不需要,在最后,进行分析符号位就行了

RISC-V的I基本体系结构的直接比较指令和F/D标准扩展的分支比较指令问题

在I基本体系结构中,不存在直接的比较指令,需要使用的比较指令都是隐藏在分支指令中.
在F/D标准扩展中,比较指令是真实存在的,feq.s/feq.d,flt.s/flt.d,fle.s/fle.d
如果结果为假,指令将整点寄存器设为0,反之为1.
也就说明,F/D标准扩展中,不再需要浮点分支指令,而是将比较指令和整数分支指令结合,来创建出浮点分支.

F/D标准扩展的额外添加

除了上述一些技术,还有设计者们为了浮点专门添加了32个浮点寄存器f0到f31和专门的浮点加载/存储指令fld/fsd,flw/fsw.
当然了,使用浮点加载/存储指令时涉及到的基址寄存器都是整点寄存器.
这些寄存器与整点寄存器的区别就是,f0没有硬连线到0.
同时呢,这些浮点指令格式并没有离开整点指令的格式,算术使用R型,加载使用I型,存储使用S型.

为何要增加一组专用的浮点寄存器而不是使用整点寄存器,尽管两者的位数都是64位

1.程序通常会在不同的数据上分别执行整点运算和浮点运算.
2.增加专用寄存器的开销大吗:不大,无非是让程序多了一些所需的指令数,这个影响主要来源于浮点寄存器的创建,伴随而来的是需要浮点专用的数据传输指令,以便于浮点寄存器和内存之间传输指令.
3.好处:在不增加指令字段位长的情况下,获得了倍增的寄存器数目.同时拥有了整点和浮点寄存器,获得倍增的寄存器带宽,还能为浮点定制寄存器.一些计算机将寄存器中的所有类型的操作数2都转换为单一的内部格式.

加速除法的另一些技术

除了前文提到的SRT之外,还有利用快速乘法器的牛顿迭代法,它将除法变为寻找函数的零点来计算倒数1/c,然后在乘以另一个操作数.

另外:c语言的数组存储和java的数组存储区别

首先c语言是行存储,这对于矩阵运算并不友好,因为通常是列来表示一个向量,当计算一个向量时,当然是列存储的数组更块,这也是Fortran语言在线性计算领域的优势.
java并不显式支持多维语言,这与c不同,java是允许数组嵌套,每个数组都可以有自己的长度,这提供了很大的灵活性,但同时也牺牲掉了很多的性能:大量的数组边界检查代码

---

• ← Previous Post
• Next Post →

---

---