PARALLEL(M-N) SVD ALGORITHMS ON THE SIMD COMPUTERS

Let A be m by n matrix, M and N be positive definite matrices of order in and n respectively. This paper presents an efficient method for computing (M-N) singular value decomposition((M-N) SVD) of A on a cube connected single instruction stream-multiple data stream(SIMD) parallel computer. This method is based on a one-sided orthogonalization algorithm due to Hestenes. On the cube connected SIMD parallel computer with o(n) processors, the (M -- N) SVD of a matrix A requires a computation time of o(m3 log m/n).

面向SIMD指令集的SM4算法比特切片优化

SM4算法是中国自主设计的商用分组密码算法,其加解密计算性能成为影响信息系统数据机密性保障的重要因素之一.现有SM4算法优化主要面向硬件设计和软件查表等方向展开研究,分别存在依赖特定硬件环境、效率低下且易遭受侧信道攻击等问题.比特切片技术通过对输入数据重组实现了并行化高效分组密码处理,可以抵御针对缓存的侧信道攻击.然而现有切片分组密码研究对硬件平台相关性强、处理器架构支持单一,并且并行化处理流水启动较慢,面向小规模数据的加解密操作难以充分发挥单指令多数据(single instruction multiple data,SIMD)等先进指令集的优势.针对上述问题,首先提出了一种跨平台的通用切片分组密码算法模型,支持面向不同的处理器指令字长提供一致化的通用数据切片方法.在此基础上,提出了一种面向SIMD指令集的细粒度切片并行处理SM4优化算法,通过细粒度明文切片重组与线性处理优化有效缩短算法启动时间.实验结果表明,相比通用SM4算法,优化的SM4比特切片算法加密速率最高可达438.0 MBps,加密每字节所需的时钟周期最快高达7.0 CPB(cycle/B),加密性能平均提升80.4%~430.3%.

SIMD指令及其在C++编程语言中的应用

单指令多数据流指令是一种非常有效的单线程加速方法,通过使用SIMD指令集,计算机可以同时对多个数据执行相同的运算,从而实现程序加速。针对SIMD的具体应用,文章结合目前常用的C++语言进行加速过程讲解与代码编程,介绍了SIMD相关基本概念和指令集,然后基于C++编程语言测试SIMD的加速性能。实验结果表明,SIMD在单线程情况下可以显著加快代码运行速度。

基于QEMU的SIMD指令替换浮点指令框架

现在,几乎每个处理器架构都已经加入了对SIMD(single instruction multiple data)指令的支持,SIMD指令能同时对一组数据执行相同的操作,通过数据并行来提高处理器的处理性能.但是大部分动态二进制翻译器忽略了本地SIMD指令的利用,而是以软件语言实现来模拟浮点计算.本文提出了一种基于QEMU翻译系统的FP-QEMU框架,FP-QEMU框架采用SIMD指令来优化替换浮点计算指令,并在X86和ARM平台上完成了完整的浮点实现.该框架可以识别动态二进制翻译系统中的浮点计算优化机会并利用SIMD指令来提升系统翻译的性能.采用SPEC 2006作为测试基准,实验表明相比QEMU,FP-QEMU跨平台的ARM应用在X86计算机上运行的最高加速比可达51.5%,平均加速比达到37.42%.

利用SIMD向量化的数据流软错误检测算法

由于现代处理器不断缩减芯片上元件尺寸、速度不断提高,会导致严重的可靠性问题.针对现有基于冗余的数据流软检错算法效率低下问题,本文提出一种基于SIMD向量化的数据流软错误检测算法VBSED,利用单指令多数据流并行性来提高软件冗余算法的效率,将原代码与冗余代码转换为高效率的SIMD代码,生成具有检错能力的加固程序.对比实验结果表明本文提出的算法可降低加固代码的时空开销,该算法还具有现有算法一般不能检测缓存等部件软错误的优点,并通过故障注入实验验证本文算法在寄存器、缓存和主存部件具有更高的错误检错率.

基于SIMD指令集的SM2数字签名算法快速实现

SM2数字签名算法是国家密码管理局发布的首个数字签名标准,已广泛应用于网上银行、电子政务等领域.本文提出一种基于高级矢量扩展指令集(advanced vector extension 512,AVX512)的SM2数字签名算法实现方案,有效提升了SM2数字签名算法的性能.结合单指令多数据集(single instruction multiple data,SIMD)运算特性,设计了一种新的冗余基数表示形式与数据排列方式,利用3比特冗余空间减少进位传播的次数,构建高效的并行素域运算模块.进而提出一种可变基点标量乘法的并行优化算法,在算法分支加入虚拟操作,按需存储点加与倍点的计算结果,结合底层数据表示形式消除8路分支的差异性.利用AVX512指令与分步点加方法加速固定基点标量乘法.签名与验签算法的性能比最新的SIMD实现分别提升了196%和69%.

基于SIMD思想的SM4流水线优化设计

SM4算法是我国商用密码标准,广泛应用于信息安全领域.由于SM4实现需要多次迭代和循环,所以SM4算法适合用硬件来实现.提出了一种基于ROM的并行S盒设计,面向SM4 ECB模式轮密钥更新的流水线结构,并且在此流水线基础上基于SIMD思想,对流水线结构进一步优化,减少了轮密钥生成的任务开销,实现了单轮密钥生成,多加解密数据流同时运算.提出的ROM流水线结构相比LUT流水线结构、BRAM流水线结构,降低了硬件资源使用,吞吐量分别提高了1.33倍和1.46倍;相比BRAM+寄存器流水线结构,节省了大量寄存器资源,而吞吐量没有明显下降.SIMD流水线结构当为1轮密钥生成4路加解密结构时,资源消耗仅为ROM流水线结构的2.5倍,效率提高了4倍.

SIMD自动向量化编译优化概述

SIMD扩展部件是集成到通用处理器中的加速部件,旨在发掘多媒体程序和科学计算程序的数据级并行.首先介绍SIMD扩展部件的背景和研究现状,然后从发掘方法、数据布局、多平台向量化这3个角度介绍了SIMD自动向量化的研究问题、困难和最新研究成果,最后展望了SIMD编译优化未来的研究方向.

SIMD技术与向量数学库研究

首先,结合Intel,AMD和IBM处理器,介绍了单指令流多数据流(SIMD)向量化技术及其各自的特点。其次,在3种平台上对各自开发的函数库中的部分向量数学函数进行了测试。结果表明,相对传统的标量计算,向量化技术带来的加速比较高,特别是Cell SDK函数,因其独特的体系结构,多个向量处理单元带来的平均加速比为10。最后,通过测试结果的对比,发现不同数学库中的向量函数之间在性能方面也存在着差异,并对差异原因进行了分析,得出性能差异主要是处理器架构和向量计算单元个数和访存等因素造成的。

龙芯3B的SIMD编译优化及分析

根据龙芯3B处理器特有的SIMD运算部件和指令集,在GCC编译器中实现了SIMD访存和SIMD运算的自动向量化.针对SIMD访存,给出了现有的访存方法,并详细介绍了适合龙芯3B的SIMD访存方法.对于不能自动向量化的其他SIMD运算,在GCC编译器中增加了Builtin函数的支持,用户可以根据标准函数接口调用SIMD运算函数,完成向量操作.通过对SPEC-CPU2000、DSPstone等大量benchmark的测试和分析,给出了龙芯3B SIMD运算的各项性能指数.对于性能表现不同的测试函数,均给出了详细分析数据和结论.测试表明,龙芯3B的SIMD运算在实际应用中有着良好的性能表现.

基于SIMD技术的锥束ART算法快速并行图像重建

ART(algebraic reconstruction technique)算法是一种迭代图像重建方法,适合于大型工业构件的无损检测,其缺点是计算量大、重建时间长。为了提高锥束ART算法的重建速度,本文提出一种快速并行图像重建方法。首先根据锥束CT扫描方式下三维射线的对称性提出一种权因子和体素索引的并行计算方法,通过一次计算可同时得到两条射线的权因子和体素索引;然后采用Intel处理器的单指令多数据(single instruction multiple data,SIMD)技术,一次性加载多个打包数据,利用SSE(streamingSIMD extension)指令实现了投影、计算图像校正和反投影的并行运算。实验结果表明本文提出的方法非常有效,在保证图像重建精度的同时取得了约1.5倍的重建加速比。

向量并行度指导的循环SIMD向量化方法

SIMD扩展部件是集成到通用处理器中的加速部件,旨在发掘多媒体和科学计算等领域程序的数据级并行.当前,两种基本的向量发掘方法分别是发掘迭代间并行的Loop-based方法和发掘迭代内并行的SLP方法.Loopaware方法是对SLP方法的改进,其思想是:首先,通过循环展开将迭代间并行转换为迭代内并行,使循环体内的同构语句条数足够多;再利用SLP方法进行向量发掘.但当循环展开不合法或者并行度低于向量化因子时,Loop-aware方法无法实现程序向量并行性的发掘.因此提出了向量并行度指导的循环向量化方法,依据迭代间并行度、迭代内并行度和向量化因子构建循环向量化方法选择方案,同时提出了不充分向量化方法发掘并行度低于向量化因子的循环向量并行性,最后,依据向量并行度对生成的向量循环进行展开.经过标准测试集测试,向量并行度指导的循环SIMD向量化方法比Loop-aware方法的识别率提升了107.5%,性能提升了12.1%.

基于Intel SIMD指令的二维FFT优化算法

在基于频域的大数据量图像处理算法中,最为耗时的步骤就是对图像数据进行二维FFT变换的过程。论文针对这一问题,提出一种基于Intel SIMD指令的二维FFT优化算法。通过将数据按照便于SIMD指令计算的方式进行组织,利用SSE3指令加速复数乘法,在二维处理中针对处理器缓存进行优化等方法,实现了很高的性能。实验结果表明:描述的算法比目前使用最广泛的公共域FFT程序包FFTW快30%左右。达到了对大数据量图像进行快速处理的要求,具有较大的工程实用价值。

基于“方证对应”理论辨治脓毒症心肌损伤的研究进展

脓毒症是由感染反应失控引起的多器官功能障碍的异常状态,具有高发病率和高死亡率的特点,而且容易引起各种器官损伤。在脓毒症继发的众多器官损伤中,心肌损伤是最常见的并发症之一,也是脓毒症患者死亡的重要原因之一。“方证对应”理论是中医学传承千年的核心辨治思路,在此思路的指导下,中医药在脓毒症心肌损伤的治疗中发挥了重要作用,为脓毒症心肌损伤的治疗提供了新的道路。文章将基于“方证对应”辨治思路,在中医古文献、基础实验和临床观察证据的基础上,对中医药治疗脓毒症心肌损伤的病因病机、辨证分型、经典方剂、中药注射液以及中药自拟方的研究进展进行综述。

基于SIMD技术的图像卷积处理器体系结构研究

SIMD处理机特别适合于要求大量高速向量或矩阵计算的场合,数据缓存系统和对准网络是它的关键部件。而图像卷积是图像处理技术中最基本也是最重要的一项技术,文章根据数字图像的卷积定理对数字图像的卷积运算进行了分析,在此基础上提出了一种基于SIMD处理机的可变卷积模板的图像卷积处理器的体系结构。该处理器内部包含有接口部件、控制部件、数据缓存系统、对准电路和执行部件等。它的极高效率的数据缓存系统和对准电路成为该处理器最有特色的部分,它从根本上解决了图像卷积中的数据复用带来的CPU重复访问主存储器的问题。实现了3×3、5×5、7×7、9×9、11×11、13×13和15×15卷积模板的图像卷积运算的变换而无需另行更改硬件电路的特点。最后,对这个图像卷积处理器体系结构的性能进行了缜密的分析。

x86处理器向量条件访存指令安全脆弱性分析

单指令多数据流(Single Instruction stream,Multiple Data streams,SIMD)是一种利用数据级并行提高处理器性能的技术,旨在利用多个处理器并行执行同一条指令增加数据处理的吞吐量.随着大数据、人工智能等技术的兴起,人们对数据并行化处理的需求不断提高,这使得SIMD技术愈发重要.为了支持SIMD技术,Intel和AMD等x86处理器厂商从1996年开始在其处理器中陆续引入了MMX(MultiMedia Extensions)、SSE(Streaming SIMD Extensions)、AVX(Advanced Vector eXtensions)等SIMD指令集扩展.通过调用SIMD指令,程序员能够无需理解SIMD技术的硬件层实现细节就方便地使用它的功能.然而,随着熔断、幽灵等处理器硬件漏洞的发现,人们逐渐认识到并行优化技术是一柄双刃剑,它在提高性能的同时也能带来安全风险.本文聚焦于x86 SIMD指令集扩展中的VMASKMOV指令,对它的安全脆弱性进行了分析.本文的主要贡献如下:(1)利用时间戳计数器等技术对VMASKMOV指令进行了微架构逆向工程,首次发现VMASKMOV指令与内存页管理和CPU Fill Buffer等安全风险的相关性;(2)披露了一个新的处理器漏洞EvilMask,它广泛存在于Intel和AMD处理器上,并提出了3个EvilMask攻击原语:VMASKMOVL+Time(MAP)、VMASKMOVS+Time(XD)和VMASKMOVL+MDS,可用于实施去地址空间布局随机化攻击和进程数据窃取攻击;(3)给出了2个EvilMask概念验证示例(Proof-of-Concept,PoC)验证了EvilMask对真实世界的信息安全危害;(4)讨论了针对EvilMask的防御方案,指出最根本的解决方法是在硬件层面上重新实现VMASKMOV指令,并给出了初步的实现方案.

一种改进的控制流SIMD向量化方法

SIMD扩展部件是近年来集成到通用处理器中的加速部件,旨在发掘多媒体和科学计算等程序的数据级并行.控制依赖给发掘程序中的数据级并行带来了阻碍,当前,无论基于loop-based还是SLP的控制流向量化方法都需要if转换,而没有考虑循环内蕴含的向量并行度,导致生成的向量代码效率较低.此外,不精确的代价模型指导控制流向量化,同样导致生成的向量代码效率较低.为此,提出了改进的控制流SIMD向量化方法.首先,提出了含有控制依赖的循环分布算法,分离循环的可向量化部分和不可向量化部分,同时考虑分布时数据的局部性;其次,提出了一种直接向量化控制流的方法,该方法考虑了基本块间的向量重用;最后,利用精确的代价模型指导超字选择指令和超字条件分支指令的生成.实验结果表明:与现有的控制流向量化方法相比,改进方法生成的向量代码性能提高了24%.

面向非多媒体程序的SIMD向量化算法的研究及改进

利用微处理器的多媒体扩展对非多媒体程序的向量化已成为提高程序性能的一个重要手段,然而目前几乎所有的商业编译器对非多媒体程序的向量化的结果,都无法说明其编译器有效的向量能力.本文通过分析典型的非多媒体程序--SPECCPU2000浮点程序,归纳出非多媒体程序的SIMD向量化特征,并依此提出局部数据重组的向量化方法、针对外层循环的向量化方法、部分语句SLP的向量化方法几种新的向量化方法和相关的向量化优化技术.通过对比Intel编译器对SPECCPU2000的向量化性能测试,可以发现本文提出的改进方法有效的提高了程序的向量化.

基于SIMD指令的柔性物体并行碰撞检测

复杂场景中柔性物体间的碰撞检测依然难以满足交互设计的要求.为了提高处理速度,文中给出了一种充分利用现代CPU的并行处理能力的碰撞检测算法.算法基于两方面的并行处理:即基于SIMD指令的指令级并行处理和基于多线程的任务级并行处理.算法给出了一种针对SIMD指令特别优化的k-DOP模型——SIMD-DOP,从理论上分析了该包围盒的高效性,并与常规的16-DOP和24-DOP进行了运行效率对比.通过使用SIMD-DOP同时在多核间进行负载均衡,算法获得了优化的并行加速.文中算法已经在一台16核工作站上针对一组复杂测试场景进行了验证.

LSSIMD阵列微处理器的控制逻辑设计

首先介绍了 L S SIMD阵列微处理器的三种并行性 :数据并行、流水线并行和指令的并行执行 .针对这三种并行性 ,阐述了控制逻辑的设计 .