找回密码
 立即注册
LiveVideoStack 首页 资讯 查看内容
  • QQ空间
  • 回复
  • 收藏

从奔腾I的VCD播放到AI区块链播放器——程序优化的魔法(2)

2018-4-23 10:56

然后用一个简单的乘法, 可以乘64或者2.018*32直接就等于2 。



当然这个效果是非常粗糙的,但是这样节省了做乘法的次数,之前每个点要做5次乘法,现在只需要4次了,而用“SMID”技术只需做两次。



因为这段汇编语言很长,我摘取了一部分。这种情况基本采用了一般的汇编语言编写技巧,在读取的时候一次读四个字节进来,然后取中间的两个,这样数据打包的操作都不需要了;再一次并行做两个乘法,之后进行加点、移位等操作,后面的加法等操作是一个个做的。



这个代码如果相比于用编译器对C语言进行全程优化的版本,速度快一倍。那么将这个效果跟ARM的V6T2进行对比,如果大家写过ARM体系结构下的汇编语言便能了解,那时有SIMD但是其并行度只有2,也就是一次做两个乘法两个加法减法。它的提升幅度跟今天这个算法是类似的,并不能做到完全的倍速加速,基本上耗时降低到0.6,0.7就已经很显著了。但这个颜色跟精确解码还是有点差距的,如果你想要做得更好 一点,可以加一些简单的非常快速的DITHER。当然不用也可以,画面也能看。其精度相当于RGB555,但由于上面介绍的这种算法会损失部分精度,画面颜色会偏暖。


二、上古时代的机器学习



第二个话题的例子是一维IDCT。 如果算1个点,用一个标准的原始reference算法,需要做8个乘加运算,8个点的就64个乘加运算,这样非常慢;如果使用快速算法,快速算法用加法移位替换乘法,一般小于16个乘法,这样相当于每个点只做了2次乘法运算,所以说IDCT快速算法是非常有效的。


这时候我们思考,那时还没有SIMD技术,能不能做的更快一点呢?


1、统计分析



我们可以在解码器里加入一些统计代码来统计一下IDCT的系数。I帧的8*8dct矩阵平均有7个非零点,也就是64个点当中只有7非零点,至于P、B因为它的残差更小,平均只有2.8个非零点。这样平均到每个行上面非零点更少了不够一个。面对这种情况就可以用最简单的算法,一个非零点做一次乘法,8个点做8个乘法就可以解决。这比IDCT快速算法又快了很多,两个非零点的情况也是类似的。如果说两个以上系数不为0用快速算法就可以解决,因为用一个点算不如快速算法。面对这种情况,我们可以直接准备这三个类型的函数。


2、实施方案



当然这里有个问题值得我们探讨,这个算法和标准算法的区别是它需要判断非零点。判断非零点是一件很慢的事情,我们可以看到一些开源型代码,包括fast,IDCT或者AAN,或者是JREV IDCT,这些非常著名的算法里面都有进行判断的代码,这些代码自身带有很大的性能损失,我们能不能避免这件事呢?如果做DCT系数解码的时候,一个DCT系数如果都是零解可以不用编码,直接skip这个块。在做DCT解码时解非零系数的时候,只需填一个表就行了,填写unsinged chart dctinf[8],或者int64,一个比特代表一个非零点,这种处理对性能的损失是非常小的。那么这个函数应该怎么准备呢?我们可以使用一个256个入口的函数,因为一行IDCT有8个标志位,我们可以先找一个非零点有8个入口,两个非零点有56个入口,其余的优先解快速算法就可以了。调用的时候可以把这个8个比特位当成一个表的索引直接调用。下面就是一个测试结果。



这个测试同时做了MMX的实验,我们可以看到水平线是没有做统计分析的标准算法,这是恒定的值。我们可以看到,英特尔的IDCT  400多clock完成;精度更高的MMX技术接近800多clock;二维IDCT也就是FEIG大约900多clock。我们使用的这个加入统计分析的算法其测试结果是典型的增长曲线;最快的结果就是带MMX技术的,可以通过最下面的几条曲线看出。在常规的情况下,也就是非零点非常少的情况下,这种技术的速度远远超过了一般的MMX算法。



由此我们可以得出结论:一般来说,只有在十个以上零点的时候,统计分析型IDCT,速度明显的下降,跟MMX技术持平,这也是统计分析的代价。但是当在常规应用时,因为平均只有七八个零点,最严重情况下也不过如此,所以还是快很多的。也就是说在I-block时,性能提升幅度大概是180%至200%;如果是P、B-block时性能提升幅度可达270%以上,这是一个相当惊人的结果,历史上从未有过这样一个快速算法能一步提升如此巨大,一般来说少一个乘法少两个乘法就可以发表一篇论文了,但这个提升如此巨大确实令人惊叹。可奇怪的是,这种快速算法一直没有被人们整理与描述,而是作为一个传说在程序员中流传,大家认为不可能存在查表。我们需要注意的是,查表不是查运算,而是查一个函数指针表。


三、快速开平方与并行查表


第三个话题是快速开平方和并行查表。很早以前也就是在Windows图形化窗口普及之前出现的一些3D游戏就要大量的浮点运算,即使做一个开方也无法避免。但这之中有几个奇迹般的开方函数,这个函数原理究竟是怎样的,我一直没有研究透彻。这是一个很神奇的代码,你可以看到它里面有一个魔法系数,也就是这个0x5f3759df。这是一个很神奇的系数,其运算也很诡异,最后通过一个从整数到浮点的强制转换就可以使这个结果返回,相当于牛顿迭代法迭代了三次。它的速度比标准的math.lib.sqrt的函数快了3倍,这在当初也是个奇迹,一直没有人能对此进行合理解释,大家有兴趣可以自己研究一下。



我还想分享另外一个想法。当数值动态范围太大时我们可以调用FastSQRT来算;但是动态小的时候,我们可以不算而是先算好然后查表。紧接着随着SIMD的出现,我们也可以用SIMD、SQRTPS这样的来做4个查表甚至8个16个查表,这些都比一次查一个更快。在此之后大家就改用SQRTPS了。但是随着指令的发展,大家发现可以进行并行查表,并行查表出现使得处理速度再上一个台阶。


这里讲两个例子:


1、ARM-neon,VTBX指令



第一是ARM-neon、VTBX指令。VTBX指令几乎是为我们量身打造的,以上是原代码。首先声明Table并加载到相应的计算器里去;之后直接调用VTBX.8一条指令就可以完成。这比开放快了许多。


2、SSSE3代码


第二是SSSE3代码。在英特尔的SSSE3之前,并行查表还是不可能的。但是在SSSE3出现之后,它提供了一个被称为pshufb的指令。这实际上是一个根据索引改变自己顺序的排列组合指令,我们可以用它拿来查表,下面是用它来查表的一个例子: 



如果是AVX1代或者以前的代码,寄存器有效长度是16个字节,所以当做32字节的时需要进行两次,中间进行切换。这个代码是最早的代码,但如果是AVX2,或者AVX512代码更短,一次查表就能查完。


四、使用动态代码做重采样



第四是利用动态代码做重采样。以图形拉伸为例,图形拉伸采用不同的算法会产生抖动,例如比较粗糙的临近点法、双线性法。而性价比较高的是双三次b样条,质量好而且速度也能够接受。一般的情况下,按照算法原理来说是一次变换上面的参数矩阵, 4×4也就是16个乘加。当我们做一次拉伸的时候,可以看出来是目的像素总数乘以16,总体来说计算量还是非常庞大。



如果是快速变化的话需要进行两次,先进行水平变化再进行垂直变化。这使得运算量被大幅减小,同时预先生成的参数表体积小很多。这些改进带来的实际性能提升可达到3倍以上,可以说是巨大提升了。一般我们现在看到的,不论哪里的代码,做一个拉伸都是做两次而不是做一次;当然也有特殊情况下迫不得已做一次的,比如当我们进行旋转或者一些特殊变换时,做两次变化实在不方便。最后面的例子会讲做两次变化会有多么复杂。


文章点评
相关文章