OpenVX与三维渲染在多态GPU上的并行实现

针对图像处理与机器视觉以及三维图形渲染等所具有的大规模并行处理特征,通过充分利用面向图形图像处理的多态阵列架构(PAAG)处理器的可编程性以及灵活的并行处理方式,采用操作级并行与数据级并行相结合的并行化设计方法,实现了OpenVX中Kernel函数以及3D图形渲染.实验结果表明,在OpenVX标准图像处理Kernel函数以及图形渲染的并行实现中,采用PAAG处理器中的多指令多数据(MIMD)并行处理方式可以获得斜率为1的线性加速比,比传统图形处理器(GPU)中单指令多数据(SIMD)并行处理方式所得到的斜率值小于1的非线性加速比效率更高.     

容错处理器阵列的多逻辑列并行重构算法

处理器阵列的容错重构技术是片上网络多核、众核高性能体系结构的可靠性技术之一。现有的最大逻辑阵列并行重构技术仅对单条逻辑列的构造实现了并行化,而对多条逻辑列的同步并行仍未见可行算法。依据处理器阵列的潜在并行性,在分治策略的基础上,提出了一种阵列分块的并行重构算法。算法对处理器阵列实施横向分块划分,对每个阵列块进行并行重构,并对所得逻辑子阵列进行归并,实现了多条逻辑列的同步并行重构。与现有的并行算法相比,新算法同样能够生成最大逻辑列,并且减少了通信开销与计算中的数据冗余,有效提高了运行速度。实验结果表明,在物理阵列大小为64×64的处理器阵列上,运行速度比现有并行算法提高39.55%,并且具有良好的可扩展性。     

一种基于互联处理器网络的并行分类算法

文中提出一个IPBPS(Interconnected Processor-Based Parallel Sorting)并行分类算法，运行在由独立处理器构成的计算机网络上，以解决网络分布式数据库的分类计算问题。基于并行算法应与并行计算的拓扑结构相匹配的思想，设计了一种旨在减小处理器间通信开销的网络结构。在此并行计算环境中，每个处理器执行同样的程序，计算负载均匀分布在每个处理器中，具有较高的加速比。同时，这种基本的处理器互联结构可灵活扩展，且随着网络的扩大，算法的并行加速比更高。     

基于PAAG系统的编译器移植技术设计与实现

针对西安邮电大学自主设计的一款面向图形、图像应用的阵列处理器PAAG系统（polymorphic array architecture for graphics and image processing）多核处理器并行编译问题,提出一种基于GCC编译器框架的可实现并行编译的移植技术。结合图像处理器并行处理要求和硬件特点,通过一种底层中间表示———寄存器传输语言 RTL （register transfer lan‐guage）进行模式匹配,完成指令选择,实现编译器移植;使用堆栈管理方式解决 PAAG系统没有寄存器文件的问题和函数调用问题。该技术的实现打破了PAAG系统只能手工编译的局面,有效提高了单个处理器的编译效率,使PAAG系统的性能得到提升;对于并行处理的图形图像处理器,该技术是一种正确可行的实施方案。     

基于最优解收集的扩展式并行遗传算法

在扩展分布式遗传算法(EDGA)的基础上提出了一种新的基于最优解收集的扩展式并行遗传算法(EPGA)。在该算法中，群体被划分为子群分配给各子处理单元(PE)计算，根处理器则在采用全局搜索策略进行搜索的同时，不断地从各子处理单元上收集局部最优解替换当前群体以获取较好的最优解。该算法采用子群的概念去获得较好的加速比，采用全局搜索策略的概念去获得较好的最优解，同时具有EDGA不具有的许多优点。给出了该算法针对经典的TSP问题的非阻塞MPI实现。实验表明该算法可以有效地提高遗传算法的加速比及增加获得最优解的概率。     

基于DHT快速插值并行算模的研究

文中所研究的这种快速插值并行算模，是一种基于DHT（Discrete Hartley Transform）的流水型模块式（即把若干个插值模块形序列全部变换为一条“流水线长龙状”序列）算模。这种算模的计算过程既不需要数据记录设施，亦不需要缓冲暂存环节，而且插值运算时间的复杂性同插值模块因子的复杂性独立无关。这种快速插值并行算模的每个计算周期持续时间相当于执行一个累积运算（加法运算和乘法运算）时间，运算简便迅速，因此对于实施高速计算应用非常有用。     

多核机群上通信高效的整数序列并行排序方法

建立一个适用于整数序列排序的数据分配模型,在多核计算节点组成的异构机群上设计通信高效的整数序列并行算法。所提出的数据分配模型依据机群中各节点不同的计算能力、通信速率和存储容量,动态计算出调度分配给各节点的数据块的大小以平衡各个节点的负载。所设计的并行排序算法利用整数序列的特性,主节点采取两轮分发数据与接收结果的方法,从节点运用分桶打包方式返回有序的整数子序列给主节点,主节点采用桶映射方法将各个有序子序列直接整合成最终有序序列,以减少需要耗费较多通信时间的数据归并操作。分析与实验测试结果表明,给出的多核机群上的整数序列并行排序算法高效,具有良好的可扩展性。     

面向异构架构的传递闭包并行算法

传统求图传递闭包的方法存在计算量大与计算时间长的问题。为加快处理大数据量的传递闭包算法的计算速度,结合算法密集计算和开放式计算语言（OpenCL）框架的特征,采用本地存储器优化的并行子矩阵乘和分块的矩阵乘并行计算,提出一种基于OpenCL的传递闭包并行算法。利用本地存储器优化的并行子矩阵乘算法来优化计算步骤,提高图形处理器（GPU）的存储器利用率,降低数据获取延迟。通过分块矩阵乘并行计算算法实现大数据量的矩阵乘,提高GPU计算核心的利用率。数据结果表明,与CPU串行算法、基于开放多处理的并行算法和基于统一设备计算架构的并行算法相比,传递闭包并行算法在OpenCL架构下NVIDIA GeForce GTX 1070计算平台上分别获得了593.14倍、208.62倍和1.05倍的加速比。     

异构机群系统上并行计算双序列的最长公共子序列*

针对处理机节点具有不同计算速度、不同通信能力的情况,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,提出一种存储受限异构机群系统的序列串最优分配线性规划模型,给出相应的序列串最优分配方法。实验结果表明,基于最优序列串分配方法的双序列最长公共子序列并行算法优于平均分配序列串算法,获得了较好的加速,并具有良好的可扩展性。     

基于GPU的多层次并行QR分解算法研究

QR分解作为一个基本计算模块,广泛应用在图像处理、信号处理、通信工程等众多领域.传统的并行QR分解算法只能挖掘计算过程中的数据级并行.在分析快速Givens Rotation分解特征的基础上,提出了一种多层次并行算法,能够同时挖掘计算过程中的任务级并行和数据级并行,非常适合于以图形处理器(GPU)为代表的大规模并行处理器.同时,采用GPU的并行QR分解算法可以作为基本运算模块被GPU平台上的众多应用程序直接调用.实验结果显示,与CPU平台上使用OpenMP实现的算法相比,基于GPU的多层次并行算法能够获得5倍以上的性能提升,而调用QR分解模块的奇异值分解(SVD)应用可以获得3倍以上的性能提升.     

异构机群系统上双序列全局比对并行算法

对于处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,基于可分负载理论,提出一种双序列全局比对问题并行处理的最优分配策略,利用该策略确定出并行迭代次数和分配给各个从处理机的子序列长度。异构PC机群系统上的实验结果表明,提出的双序列全局比对并行算法优于基于平均分配策略的并行比对算法,获得良好的加速和可扩展性。     

一个改进的并行关联规则算法研究

在研究关联规则挖掘算法的基础上,对并行关联规则算法进行了比较全面的分析,并给出了并行数据挖掘的计算框架。提出了一个以计算服务器为中心节点的并行挖掘算法,可以发挥各局部节点的优势,无需各局部节点进行通信,减少了各局部节点的通信负荷。通过理论分析和实验数据验证,该算法具有较好的可扩展性和海量处理能力,特别是在节点数目较多的情况下更显示出优势。     

非定常Monte Carlo输运问题的并行算法

文中给出了非定常MonteCarlo(下文简写为MC)输运问题的并行算法 ,对并行程序的加载运行模式进行了讨论和优化设计 .针对MC并行计算设计了一种理想情况下无通信的并行随机数发生器算法 .动态MC输运问题有大量的I/O操作 ,特别是读取剩余粒子数据文件需要大量的I/O时间 ,文中针对I/O问题 ,提出了三种并行I/O算法 .最后给出了并行算法的性能测试结果 ,对比串行计算时间 ,使用 6 4台处理机时的并行计算时间缩短了 30倍     

基于Cortex嵌入式多处理器系统的图像中值滤波算法并行化的研究

嵌入式系统在图像处理、空间计算等领域越来越广泛,如何在功耗、成本和计算能力三个主要方面取得平衡,利用多核和多处理器系统以并行计算方式提高嵌入式系统计算能力是一种有效的解决方案.讨论了基于Cortex嵌入式多处理器系统的基本结构,并在该系统上进行图像中值滤波算法的并行化研究.实验结果分析表明,在该嵌入式多处理器平台上配合并行算法能够成倍提高图像中值滤波的运行性能.     

基于可重构处理器的并行优化算法

为挖掘可重构处理器的内在并行性,需要编译器通过分析程序的并行性来决定可重构处理器硬件最好的执行模式。为此,提出一种基于可重构处理器的并行优化算法。将有向无环图的并行计算部分映射到可重构处理器上,对任务实现3个不同层次的并行性(指令级并行、循环级并行、线程级并行)。测试结果表明,该算法使得可重构处理器在处理任务时比未用并行优化算法的性能提升1.2倍左右。     

三角网格表面任意两点间并行近似测地线算法

为降低求解三角网格表面任意两点间近似测地线长度和路径问题的时间开销,提出一种基于局部细分法的并行近似测地线算法。采用类矩阵乘最短路径并行算法求解点对间初始最短路径,并用源分割法映射子网格数据;所有处理器并行执行,对其所拥有点对之间的初始最短路径周围三角面片上的边进行细分操作;最后基于局部细化后的细分图并行,求得所有点对间的近似测地线长度和路径。实验结果表明,该并行近似测地线算法能够有效降低求解该类问题的计算时间,计算效率大大提高。     

基于多核处理器的网络内容并行还原系统

研究现有网络信息内容还原系统实现原理及各种改进策略。根据现有网络信息内容还原系统未充分利用运算资源以及当前多核处理器高度普及的现状,提出基于多核处理器的网络信息内容并行还原系统,将高流量数据包分流到多个处理进程,利用多核处理器的运算资源,从而达到在不添加额外硬件资源的情况下提高处理能力的目的。实验结果表明,该系统可以有效提高网络信息内容还原系统的处理流量。     

基于平衡划分的并行投影算法

基于DL算法,提出并分析了平衡划分并行投影算法PROJECT-DL。在PROJECT-DL算法中,数据被平均划分并分配给所有处理机,因而每个处理机具有相同的工作负载。给出了网络并行计算环境下的实验结果,并与PROJECT-S、PROJECT-NS算法进行了对比。理论分析和实验结果表明,PROJECT-DL算法是一种高并行效率、高扩展性的并行投影算法。     

串匹配算法的简单并行实现

结合BM模式匹配算法和并行计算的思想,提出了一种快速的串匹配并行实现策略,该策略将文本串划分成一定长度的子串,将子串分配到不同的处理器中,在各个处理器中分别并行执行BM模式匹配,即便是在最坏的情况下也能达到较好的时间复杂度。     

串匹配算法的简单并行实现

结合BM模式匹配算法和并行计算的思想,提出了一种快速的串匹配并行实现策略,该策略将文本串划分成一定长度的子串,将子串分配到不同的处理器中,在各个处理器中分别并行执行BM模式匹配,即便是在最坏的情况下也能达到较好的时间复杂度。