PVM环境下SPMD程序模式探讨

介绍ＰＶＭ环境下的ＳＰＭＤ程序模式，并结合程序自动并行化模型ＡＰＭ，提出了克服ＳＰＭＤ不足之处的思想，描述了改进后的ＳＰＭＤ程序模式——ａＳＰＭＤ程序模式。该模式既有ＳＰＭＤ模式的特点，又有Ｍａｓｔｅｒ－Ｓｌａｖｅ模式的特点。文中还给出了一个用ＡＰＭ模型生成的ａＳＰＭＤ模式并行程序的实际运行效率以及ａＳＰＭＤ模式并行程序与ＳＰＭＤ模式并行程序运行时间。

针对共享内存SPMD程序的通信流依赖分析方法

传统数据流依赖分析方法在处理共享内存单指令多数据(SPMD)程序时,不能识别共享数据访问语句所属的处理节点,也不能消除执行顺序不定的控制流对共享数据流依赖造成的影响,从而在分析共享数据依赖时产生精度较低的结果。根据共享内存SPMD程序的共享数据别名特性,提出了一种可扩展的共享数据通信流依赖分析方法,并将其应用于一个编译后端分析器原型中。实验表明,该方法较传统分析方法可发现更多精确的共享数据通信流依赖。

基于多实体的矢量数据压缩改进算法

矢量数据压缩在地形环境仿真、制图综合、GIS等研究中具有重要作用,对增加移动设备的存储能力和提高矢量数据的网络传输效率来说是一项很重要的工作。根据动态规划算法理论、Douglas-Peucker算法和矢量数据的特点,提出了基于动态规划算法的矢量数据压缩的模型和改进方法,通过一条参考路径构造一条带形成最小误差搜索范围,同时条带宽度可自适应调整。并将单一实体的优化压缩算法扩展为基于多实体的压缩算法,解决了图层压缩的全局优化问题。实验结果表明,该方法具有较高的效率,能够得到较小的压缩误差。

面向单目标优化的集成粒子群算法

串行粒子群算法广泛应用于多个领域,出现了多个变种,但解决不同种类的优化问题时性能有差异。为提高串行粒子群算法对各种优化问题的适应能力,提出一种集成粒子群优化算法。新算法使用Matlab的单程序多数据并行结构发挥单节点多核计算能力,通过设置外部档案分享不同粒子群的全局最佳位置,促进不同串行粒子群算法之间的信息交流,综合利用不同串行粒子群算法在解决不同类型优化问题的优势。在广泛使用的测试函数集上开展仿真实验,结果验证了新算法的有效性,与多个知名的串行粒子群算法相比,新算法在寻优性能上优势明显。新算法不仅能够提高粒子群算法的适应能力,而且,所采用的算法框架也适应于其他群智能算法,改善了算法的性能。

并行实时测控数据存储系统设计与实现

随着测控设备数量增加、数据码率的不断提高,传统的测控中心实时存储系统采用的串行化处理逻辑已经难以适应高负载的测控任务需要。采用SPMD(Single Program Multiple Data)思想,基于OpenMP和Qt设计并实现了一套并行实时测控数据存储系统框架。该系统通过引入M/M/1模型的排队系统,设计了一种适合并行实时测控数据存储系统的静态负载均衡算法,基于互斥锁完成了线程间的细粒度通信同步机制,借助于事件循环机制将Qt的信号与槽特性成功地嵌入OpenMP线程,保留了Qt图形界面良好的人机交互性能。实验结果表明该系统在高负载的情况下,相比串行测控数据存储系统而言具有更好的扩展性和实时性,能更好地利用现行单机多核系统的计算资源,获得更好的实时性能。

一个新的线索KD树并行算法

KD树是三维场景渲染中常用的空间加速算法。由于SIMD计算平台不支持递归操作,导致KD树在GPU上的应用受到限制,因此提出了一个新的基于SIMD架构的并行KD树算法。通过创建时对KD树线索化,不仅省去堆栈使用,且因无需回溯到根节点而减少大量无效遍历操作,实现了基于GPU的高效并行加速。实验结果表明,线索KD树算法每秒计算的光线数与传统算法相比,提高3~8倍不等,最终显著提高光线跟踪渲染速度。

集装箱港口装卸同步作业模式下的协调调度研究

研究如何在单船舶多桥吊的条件下实现集装箱港口装卸同步作业,通过二阶段建模,引入混合车间调度模型,并采用多层编码遗传算法与0-1整数规划模型求解,最后用实例验证其可行性,得到装卸同步作业进出口集装箱装卸序列以及设备调度优化方案。结果证明,在此作业模式下作业时间减少17%,桥吊和集卡在一定程度上实现了"满去满回"状态,降低了设备空载率,提高了作业效率,缩短了船舶在港停留时间。

面向国产高性能众核处理器的编程模型

在国产高性能众核处理器上编程时,需要直接使用最底层的接口开发软件,这使编程和调试非常困难;并且各自平台的高性能软件编程模型较为基础,计算软件不能通用,造成了重复性开发。针对以上问题,实现了通用编程模型以及所对应的支撑库:一方面基于消息队列机制开发国产高性能众核处理器的线程级并行机制;另一方面基于单指令多数据流(SIMD)编程模型开发从核上的数据级并行性。首先,对国产高性能众核处理器体系结构进行抽象;其次,设计模型的消息队列机制,并为程序员提供一套异构并行编程接口,如系统参数接口、从核线程控制接口、消息队列接口、SIMD抽象接口;最后,在上述基础上形成全新的高性能计算软件开发模型和方法,方便用户开发基于国产高性能众核处理器的并行计算软件。性能传输测试结果表明,在国产众核处理器上,当启动核数较少时,所提模型的传输带宽普遍达到了峰值直接内存访问(DMA)带宽的90%;当启动的核数较多时,消息队列模型的传输带宽普遍达到了峰值DMA带宽的70%。在矩阵乘法实验中,与系统原语传输矩阵并计算的性能相比,所提模型的性能达到前者的90%;在口令猜测系统中,所提模型的代码性能与直接使用最底层的接口开发的代码性能基本持平。所提通用编程模型和支撑框架使高性能计算(HPC)软件开发更简易,并且具有更好的可移植性,可为促进国产自主HPC软件研发提供帮助。

锥束CT仿真投影快速计算

针对离散体素模型仿真投影数据计算,提出了一种快速并行计算方法。首先从射线的对称性分析了投影数据的并行计算,然后通过Siddon算法来进行射线与体素的求交;结合SIMD技术实现了离散体素模型投影数据的快速并行计算。实验结果表明,在保持投影数据精度的同时,较之Siddon方法能够取得约1.9倍的加速比。

区域优化分割的数学模型及其算法

针对一些实际问题提出区域优化分割问题并建立数学模型,综合应用数据分类法、多目标非线性规划理论等数学理论和方法,获得了区域优化分割模型的近似最优解及算法。

媒体处理器视频哈夫曼解码快速算法

为了提高视频处理中哈夫曼解码的性能,从减少比特操作、提高处理器内存利用率的角度出发,设计了2种不同的数据结构进行哈夫曼码表的组织,提出了一种新的并行分步查表算法,对Ishii的并行查表法进行了改进.实验结果表明,采用新算法及其内存优化策略,以哈夫曼解码性能较少下降的代价,内存开销得到大幅降低.新算法比常用的分步查表算法的解码效率有较大提升,对MPEG系列、H.26X系列等视频压缩标准具有普适性.

共享指令缓存XOR散列索引的研究与设计

SPMD(Single Program Multiple Data)是高性能领域的主要工作模式之一,该模式下邻近核心执行相同的程序块,但根据处理数据或控制流的差异,临近核心的指令流并不完全相同.L1 ICache(Instruction Cache)共享技术通过将邻近核心的L1 ICache共享,能有效利用众核处理器SPMD工作模式的特点,同时能缓解片上资源紧张的问题.但共享结构会带来访问冲突,对性能有不利影响.本文基于排队网络对共享ICache的访问冲突进行了理论分析,该理论分析依据核心对共享ICache体的访问特性进行建模,避免了直接抽象物理节点导致的模型访存特性模糊问题.根据理论推导的指令缓存性能损失原因,本文设计了面向共享L1 ICache的低访问冲突XOR散列函数.函数的设计综合考虑搜索了代价和工程实现复杂性,在保证散列线性空间随机散列能力的前提下,对附加延迟、功耗开销进行控制.该散列函数基于异或操作,通过调整ICache排队网络模型的节点转换概率,降低了共享L1 ICache的访问冲突.实验结果表明,在指令缓存总容量为32 KB的四核心簇上,使用XOR散列的共享L1 ICache结构较私有L1 ICache结构性能平均优化11%,较使用低位交错策略的共享L1 ICache结构性能平均优化8%,较使用面向跨步访存散列策略的共享L1 ICache结构性能平均优化3.2%.

单程序多数据并行程序优化规律分析

在并行程序开发过程中,对并行程序的有效优化能够充分发挥软硬件的执行效率。在进一步探讨Amdahl定律的基础上,针对数据密集型问题的单程序多数据(SPMD)并行计算,分析并行程序被有效优化后其计算时间及并行效率的变化规律,并给出了公式证明,有利于充分利用Amdahl定律指导并行程序的优化。实验结果表明了论证的有效性。

面向神威高性能多核处理器的并行编译优化方法

在神威高性能多核服务器上,自动并行化编译系统为识别和申明程序中的并行性,产生的OpenMP程序没有经过充分的优化,其采用简单的fork-join模型,存在大量的并行循环嵌套,导致运行效率低。为提升自动并行化编译系统产生的OpenMP程序的运行效率,提出一种并行域重构优化技术。并行域重构技术通过合并程序中的并行域和扩展嵌套循环中的并行域范围,减少OpenMP程序的并行域数目,降低线程组频繁创建和合并等控制开销,将简单fork-join模型的OpenMP程序转换为性能更为高效的单程序多数据模型的OpenMP程序。实验结果表明,在新一代神威高性能多核服务器SW1621平台上,并行域重构技术在NPB3.3-OMP测试集和SPEC OMP2012测试集上的运行效率分别提高了10.77%和7.94%的,可有效提升自动并行化编译系统OpenMP程序的执行效率。

MPEG-2音频解码算法优化

以PC机为硬件平台对MPEG-2的音频解码算法进行优化,实现MPEG-2全软件的系统、视频、音频3个部分实时解码。在IDCT和IMDCT中应用了新的快速算法;结合PC机本身的特点及解码过程中有大量的乘加运算采用SIMD(single-instructionmultiple-data)来对程序优化,并在实际运算中也对数据结构进行了优化。通过以上的优化使MPEG-2层II解码的运算量减少了40%以上,在奔腾3/450计算机上只占用不到5%的系统资源。这些优化算法已经应用于奔腾3/800为硬件平台的MPEG-2实时解码器中。

基于多核CPU的脑网络拓扑属性并行分析方法

针对脑网络研究中需计算的网络数目过多造成执行时间过长的问题,提出一种基于多核CPU(central processing unit)的并行计算方法。通过SPMD(single program multiple data)机制利用CPU的多核同时执行,实现并行计算多个网络的属性,利用循环打包方法降低SPMD机制中循环控制的时间,得到并行计算多个网络指标的时间,同串行计算时间相比,可得到此方法的并行计算效果。与传统并行单个算法的策略相比,该方法利用不同脑网络之间计算的独立性,采取同时计算多个网络的策略。在一台多核CPU的主机上,分析CPU核数、网络节点规模这两个因素对网络指标计算并行效果影响。在利用12个CPU核并行计算网络节点规模为3000的指标时,加速比均达到2以上,其中效果最好的是网络同配系数的计算,加速比达到6倍以上。实验结果表明,基于SPMD机制和循环打包方法的并行计算架构对脑网络指标计算的并行效果显著,加速比随着CPU核数、网络节点规模的增长呈上升趋势。

面向嵌入式应用的数据并行语言设计

根据基于PIM(Processor-In-Memory)技术的数据并行计算机体系结构的特点和面向多媒体计算的应用需求,提出了面向嵌入式SIMD(Single Instruction Multiple Data)计算的数据并行语言PIMC。简单讨论了PIMC语言的形式化定义,并以数据并行图像处理的均值滤波算法为例对语言的使用作了说明。结合其他大量的数据并行编程实例,说明了该语言能够在基于PIM技术的SIMD并行计算机上正确描述基本多媒体处理算法的数据并行实现。

ATD4MA:多属性数据的联合真值发现方法

目前已提出的真值发现方法无法解决对象由多个单值属性与多值属性共同组成的情况,若将这些属性拆分后分别处理则会破坏属性间原有的关联,导致计算结果不准确。为此提出一种多属性数据的联合真值发现方法 ATD4MA,将对象各观察值通过遗传算法中的染色体进行建模,针对问题特性对群体初始化算法和染色体基本动作进行改进,控制染色体的演化行为对各属性进行约束,以各对象的真值染色体与各数据源提供的观察值染色体间的差异加权和达到最小为目标建立优化模型,解决了对象包含多个属性的真值发现问题。在两个真实数据集上的实验证明了提出方法的正确性和有效性。

基于ARM V8平台的向量算法库实现与优化

基于ARMV8架构的VecOp向量算法库,提出一种基础向量算法在ARMV8平台上实现和优化的方案。从访存对界优化、指令集优化、基本块优化以及向量分支优化4个方面进行精细调优,提升向量算法函数在ARMV8平台上的性能,以实现VecOp算法库在ARMV8平台上的优化。实验结果表明,该方案在ARMV8计算平台上实现的向量算法库性能提升可达到10%~300%。

基于SIMD结构的矩形行列式并行算法研究

在运用行列式Schur余子式算法的理论基础上,提出了对SIMD结构的并行机,可适用于对行列式按行分块并行处理算法,把一个n阶行列式的求值过程分解成相对独立的若干个二阶行列式的求值过程,而且它们的求值过程是相对独立的,具有并行性,从而设计出n阶行列式求值的并行算法。给出了该算法的实现步骤,分析了算法的加速比;对算法进行了模拟实验,结果说明了其性能。