多核机群上数据密集型应用并行程序性能优化

在异构多核机群系统上利用数据任务块的动态调度策略和全锁定技术,给出一种面向数据密集型应用的结点内主存和可用的共享二级缓存大小中动态调度数据块的多进程级和多线程级并行编程机制,给出了优化数据密集型应用并行程序性能的策略和技术。在多核计算机组成的异构机群上并行求解随机序列多关键字查找的实验结果表明,所给出的多核并行程序设计机制和性能优化方法可行和高效。     

异构机群上高效可扩展的Motif发现并行算法

在节点具有不同计算速度、不同通信能力的异构机群系统上,分别建立求解l≤16和l>16的Motif发现问题的最优序列分配模型,在此基础上设计实现融合投票和统一投影-邻居阈值思想的Motif发现并行算法。实验结果表明,给出的基于最优序列分配策略的Motif发现并行算法具有良好的加速和可扩展性,优于采用平均分配策略的Motif发现并行算法。     

RAPWBN模型上的快速高效并行排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了RAPWBN模型上的抽取压缩操作算法,并由此得到了RAPWBN模型上的两种快速高效并行排序算法,对长度为N的序列进行排序,在具有N2个处理器和N条行总线的RAPWBN模型上,若总线带宽ω＞logN字节,可以在O(1)时间完成排序.在具有N个处理器和N条行总线的RAPWBN模型上,最好情况下以O(logN)时间、最坏情况下以O(N)时间完成排序.     

基于机群架构的并行数据库实现技术研究

在总结了现有并行数据库实现模型的基础上,基于"半重写变换"模型[1]实现了一个并行数据库系统的原型.通过对数据划分/重划分、并行选择、并行排序、并行连接等关键操作的实验分析,指出了.半重写变换"模型存在的缺陷,并提出了一种混合式的改进模型.从理论上说,在机群架构下实现并行数据库系统,这种混合模型较单一模型更有优势.     

多核机群下基于神经网络的MPI运行时参数优化

多核处理器的新特性给MPI应用带来了新的优化空间,其中调优MPI运行时参数被证明是优化MPI应用的有效方法.然而最优的运行时参数不仅与多核机群的体系结构有关,也决定于MPI应用的程序特征.提出并分析了一种在给定多核机群下基于人工神经网络的优化模型,用于自动为未知的MPI程序预测接近最优的运行时参数.两个不同基准的实验证明了本方法的有效性.实验证明,基于本方法得到的运行时参数所产生的加速比平均达到了实际最大加速比的95%以上.     

多核环境下高效集合通信关键技术研究

随着高性能计算需求的日益增长,多核处理器在高性能计算中间得到了广泛的普及.为了保证高性能计算机系统的效率,需要保持计算和通信的平衡性,多核的广泛使用对通信系统的效率提出了更高的要求.集合通信作为通信系统中的重要组成部分,研究多核环境下的高效集合通信具有十分重要的意义.文中首先研究了多核对集合通信性能的影响,并根据多核处理器共享Cache以及内存竞争的特点,提出了层次化算法、限制并发、NUMA感知的优化方法和Cache友好的优化算法,并分别在MPI_Barrier、MPI_Bcast和MPI_Alltoall中进行了验证.实验结果表明优化方法能够有效地利用多核结构特点,降低竞争带来的影响,提高了多核环境下集合通信的性能和可扩展性.     

带有宽总线网络的可重构计算模型上的并行排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了RAPWBN模型上的抽取压缩操作算法,并由此得到了RAPWBN模型上的快速高效并行排序算法,在具有N个处理机和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,则对元素位数固定的N个元素可以在O(1)时间完成排序,对元素位数不固定的N个元素,可以在O(k)时间完成排序,这里k为元素的最大位数.     

基于多核平台并行K-Medoids算法研究

分析K-Medoids算法的内在并行性,设计一个适合多核平台的并行算法,并利用OpenMP进行实验。实验结果表明,并行算法对多核环境有很好的适应性,在双核及四核计算机上均获得了较好的加速比与运行效率。     

RAPWBN计算模型上的快速并行归并排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出该模型上的一种并行归并排序算法,在具有N~α(1＜α＜2)个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,对长度为N的序列进行归并排序,可以在O((loglogN)~2)时间完成.     

基于散列和归并技术的有效并行排序方法

本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法：将长度为ｎ的待排序数据划分成ｐ个长度为ｎ／ｐ的子序列,引入散列技术并行地对这ｐ个子序列的数据进行二次散列排序,这一阶段所需的平均时间为Ｏ（ｎ／ｐ）;最后并行地将ｐ个有序子序列归并成一个长度为ｎ的有序序列,归并阶段所需的时间为Ｏ（ｎ－ｎ／
／ｐ）。整个排序算法的并行执行代价为Ｏ（ｎｐ）。本排序方法可以拓以网络并行机群环境。     

一种优化BITONIC算法:并行-优化-串行合并和分类向量算法

串行算法并行化是发挥各种巨型机的效率的关键技术之一。“并行－优化－串行”归并向量算法（OSVM）,是一种串行算法并行化的优化方法,它用O（N／p)时间把总长为N的两个有序序列归并或把总长为N的一个Bitonic序列排序。“并行－优化－串行”排序向量算法（POSVS）用O（NlogN)/p）时间在实际SIMD机上把N个数排序,这些是第1个满足以下两个条件的向量Optimal算法（加速比＝O（p)),（1）它能在实际SIMD计算机上实现,处理机的台数p的范围很宽1≤N^1-ε,这里,ε是任意的小的正数。（2）它统一了3种不同类的合并算法：Batcher的Bitonic算法（最快但效率随参数变大而向于0）,优化(Optimal)算法（效率为常数的算法）和最佳的串行算法。而且综合了3个算法的优点,“并行－优化－串行”（POS）方法是一个通用方法,它还可以应用到其它类型问题上。     

并行机器学习算法基础体系前沿进展综述

大数据环境下,机器学习算法受到前所未有的重视。总结和分析了传统机器学习算法在海量数据场景下出现的若干问题,基于当代并行机分类回顾了国内外并行机器学习算法的研究现状,并归纳总结了并行机器学习算法在各种基础体系下存在的问题。针对大数据环境下并行机器学习算法进行了简要的总结,并对其发展趋势作了展望。     

多核处理器机群Memory层次化并行计算模型研究

多核处理器机群点对点通信同时具有memory纵向层次化特征和横向层次化的新特征.纵向层次化特征揭示了对不同大小和步长的消息进行点对点通信时消息通信中间件对其性能的影响;横向层次化的新特征由intra-CMPi、nter-CMP和inter-node消息通信性能的显著差异引起,目前缺少有效的分析模型.文中提出一种新的memory层次化并行计算模型,对多核处理器机群memory横向、纵向层次化特征进行了统一的抽象.在对多核处理器机群点对点通信和集合通信的开销进行模型分析和实际测试中,新模型的精确性优于现有的未引入memory横向层次化特征的模型.     

一种新的并行归并排序算法

文章提出了一种新的并行归并排序算法。算法充分利用并行系统中各个处理机中数据排序后序列长度相等的特点,计算出归并段对中的一个元素和最后一个元素的位置,然后再从相应的位置进行归并排序。该算法可使排序后的数据分布完全达到平衡,具有较高的负载平衡性、可扩展性和排序稳定性。文章最后给出了基于PC集群的实验结果,并把该结果与PSRS算法作了比较。     

基于多核的Rijndael算法的并行优化与实现

为提高Rijndael算法的执行效率,从对Rijndael算法的核心部分-轮变换的分析入手,在多核平台下提出了一种基于数据流分解的方式对Rijndael算法进行并行优化.采用的主要方法是将轮变换的各构成变换对整个状态的作用分割成对状态的每个组成单元的作用,使得各构成变换可以并行进行.实验结果表明,采用基于数据流的分解方式对Rijndael算法分解可有效的提高其执行效率.     

多核技术在数据结构课程中的引入与探讨

多核技术是当前计算机学科发展的热门方向,针对将多核技术融入到操作系统、编译原理等课程中出现的学生对基础算法并行化了解甚少的问题,文章提出将多核技术引入到前导课程数据结构中的实施方案,包括课堂教学内容的扩展,多核技术实践大纲及实例,并引入基于多核的课程设计。实践证明,新的教学方法增进了学生对多核技术和并行算法的了解。     

划分点定位并行排序算法

提出并分析了划分点定位并行排序（parallel sorting by divide-point locating)算法。在算法中,输入数据被平均划分并分配给所有处理机,因此每个处理机具有相同的工作负载。给出了网络分布计算环境下PSDL算法的实验结果,并与PSRS算法进行了对比。理论分析和实验结果表明,PSDL算法是一种高效率、高扩展性的并行排序算法。     

多核平台PAML并行算法研究

PAML是一款利用最大似然法进行系统发育分析的软件包,被广泛使用.然而,由于模型复杂、参数众多,PAML的计算过程非常耗时.对PAML中最重要的codeml程序进行了并行算法研究,通过算法分析和程序Profiling确定程序瓶颈.在此基础上,利用现代CPU的多核并行能力和SIMD并行机制优化程序瓶颈,从而提高了程序整体的运行速度.实际数据集和人工数据集上的实验表明并行算法有效提高了codeml的计算速度,加速比最高达7.94倍.