一种用于大数据分析服务的启发式云爆发算法

基于异构云联合的并行化大数据分析服务可以提升性能。然而由于大数据网络传输存在较大时延,原则上必须在并行化水平和大数据分析性能之间进行折衷。鉴于此,提出一种启发式云爆发算法用于并行化大数据分析服务。首先确定联合云中哪些计算结点应该用于大数据分析并行处理,然后将大数据妥善地分配给这些计算结点,确保处理同步完成且性能最优,最后,确定被分配的不同大小数据块在各个结点的计算次序,确保数据块传输尽量在结点上一数据块计算期间完成。与其他负载均衡算法做了对比,结果表明,使用该算法后性能可提升20%~60%。     

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

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

大规模生物网络马尔可夫聚类的并行化算法

马尔可夫聚类算法（MCL）是在大规模生物网络中寻找模块的一个有效方法，能够挖掘网络结构和功能影响力较大的模块。算法涉及到大规模矩阵计算，因此复杂度可达立方阶次。针对复杂度高的问题，提出了基于消息传递接口（MPI）的并行化马尔可夫聚类算法以提高算法的计算性能。首先，生物网络转化成邻接矩阵；然后，根据算法的特性，按照矩阵的规模判断并重新生成新矩阵以处理非平方倍数矩阵的计算；其次，并行计算通过按块分配的方式能够有效地实现任意规模矩阵的运算；最后，循环并行计算直至收敛，得到网络聚类结果。通过模拟网络和真实生物网络数据集的实验结果表明，与全块集体式通信（FCC）并行方法相比，平均并行效率提升了10个百分点以上，因此可以将该优化算法应用在不同类型的大规模生物网络中。     

H.264去块滤波算法在众核结构上的并行优化

在H.264视频解码中,去块滤波是运算量很大的一部分.由于去块滤波过程中,数据之间存在复杂的依赖性,现有的很多去块滤波并行方案存在着并行度小、同步互斥开销大的缺点.本文结合去块滤波算法及众核处理器Godson-T的结构特性,提出了一种可以减少数据依赖的去块滤波算法并行优化方案.相对于以前的很多方法,此并行方案首先在算法上增大了并行度,减少了同步开销,同时,我们通过片上众核处理器Godson-T的硬件支持,采用计算与通信重叠等优化策略,使得优化后的算法达到了数倍的性能提升.     

数据并行语言编译系统的处理机分配算法

处理机分配是数据并行语言编译系统的一项重要技术,原因是高效使用大规模并行计算机的关键在于将程序中的计算尽可能均匀地分布到各个处理机上去执行,并且将程序中的数据按照使通信量尽可能少的原则分布存放在各个节点上,而处理机分配直接影响着数据分布和并行循环这代分布的效果。文章讨论处理机分配的原则,给出了一个高效的处理机分配算法。     

并行J-变量块Cholesky分解算法的仿真研究

该文提出一个针对大型实对称正定稠密方程组或复对称非Hermitian稠密方程组线性求解器的并行分布式算法。它使用了不同于ScaLAPACK的J-变量块Cholesky分解算法和一维块循环列数据分配。该算法以MPI作为消息传递库，在最多可达16个处理器的集群上针对实对称正定稠密方程组可提供与ScaLAPACK近似的浮点操作性能，并可解决一些涉及复对称非Hermitian稠密方程组的电磁场散射问题。该算法的优点是执行Cholesky分解所需的存储量只是标准并行库ScaLAPACK的一半。仿真的数值结果表明该算法是正确、有效的。     

基于分布Maple系统下特征列相关算法的并行化研究

特征列算法是吴方法的核心算法,为了提高吴方法的计算效率,分析吴方法计算中的特征列计算和多项式因式分解,采用粗粒度并行计算的方法,给出基于分布Maple系下的吴方法计算的特征列计算以及多项式因式分解的并行化算法,为吴方法计算的并行化研究提供方法.     

基于规范划分集的并行循环计算划分

计算划分问题是并行编译中最为重要的问题之一.针对并行循环,在数据分布确定的情况下,提出了基于规范集的计算划分算法,具体讨论了规范集的获取方法及综合通信与负载均衡的最优方案选取算法.实验表明,在并行循环处理方面,这一算法与以前几种算法相比更加简单、有效;采用这一算法的p_HPF编译器对数据并行应用问题可以获得良好的加速比和效率.该编译器已在石油领域得到应用.     

基于块分类的深度图运动估计及其并行实现

针对三维高效视频编码(3D high efficiency video coding,3D-HEVC)深度图在运动估计过程中没有充分利用平坦区域数据特性而导致的计算量大、编码时间长等问题,提出一种基于块分类的深度图运动估计优化方法.依据编码块像素分布特征,将其分类为平坦或者边缘区域,自适应地为不同类型编码块分配不同的搜索算法,减少整体计算开销.实验结果表明,优化后的算法相比于全搜索算法,平均峰值信噪比(peak signal to noise ratio,PSNR)的损耗仅为0.0870 dB;相比于TZSearch(test zone search)算法,运动搜索次数平均减少12.04％.为进一步提升编码速度,基于视频阵列处理器对优化后的算法设计并行实现方案.实验结果表明,所设计的并行方案串/并平均加速比达到2.8940.     

基于反馈机制的动态负载平衡算法研究*

动态负载平衡是提高多处理器系统资源利用率和并行计算性能的重要途径。为了解决变化负载系统中子任务可并行计算的双重循环(PTM-NL)问题,提出一种基于反馈机制的动态负载平衡算法。该算法以处理器作业速度为负载指标,在循环计算中根据反馈的负载指标分配计算任务,动态适应负载变化。实验结果表明,该算法在变化负载的系统中能有效提高PTM-NL问题并行效率。     

A multilevel parallel solver for block tridiagonal and banded linear systems

This paper describes an efficient algorithm for the parallel solution of systems of linear equations with a block tridiagonal coefficient matrix. The algorithm comprises a multilevel LU-factorization based on block cyclic reduction and a corresponding solution algorithm.

The paper includes a general presentation of the parallel multilevel LU-factorization and solution algorithms, but the main emphasis is on implementation principles for a message passing computer with hypercube topology. Problem partitioning, processor allocation and communication requirement are discussed for the general block tridiagonal algorithm.

Band matrices can be cast into block tridiagonal form, and this special but important problem is dealt with in detail. It is demonstrated how the efficiency of the general block tridiagonal multilevel algorithm can be improved by introducing the equivalent of two-way Gaussian elimination for the first and the last partitioning and by carefully balancing the load of the processors. The presentation of the multilevel band solver is accompanied by detailed complexity analyses.

The properties of the parallel band solver were evaluated by implementing the algorithm on an Intel iPSC hypercube parallel computer and solving a larger number of banded linear equations using 2 to 32 processors. The results of the evaluation include speed-up over a sequential processor, and the measure values are in good agreement with the theoretical values resulting from complexity analysis. It is found that the maximum asymptotic speed-up of the multilevel LU-factorization using p processors and load balancing is approximated well by the expression (p +6)/4.

Finally, the multilevel parallel solver is compared with solvers based on row and column interleaved organization.     

基于主对角线的分形图像并行压缩算法

本文针对传统分形压缩算法耗费时间长的缺点,提出一种基于定义域块主对角线的并行压缩算法。文中讨论了并行系统的最优构架模式及任务分配方案,从而保证系统运行时负载平衡。定义并设计出了一种新型的MPICH数据结构,用于提高系统效率,使用了MPICH中的包传输技术,完成了节点间的高性能数据传输。用该算法取代传统算法,因采样方法的改进而简化了计算的复杂度,因并行而极大的缩短了压缩时间,取得了非常好的加速比。实验结果表明,该算法在压缩时间和峰值信噪比(PSNR)两个方面都取得了很好的效果,同时也显示出并行计算在分形领域的重要应用价值。     

Improvement of workload balancing using parallel loop self-scheduling on Intel Xeon Phi

In recent years, Intel promotes its new product Xeon Phi coprocessor, which is similar to the x86 architecture coprocessor. It has about 60 cores and can be regarded as a single computing node, with the computing power that cannot be ignored. This work aims to improve the workload balance by parallel loop self-scheduling scheme performed on Xeon Phi-based computer cluster. The proposed concept is implemented by hybrid MPI and OpenMP parallel programming in C language. Since parallel loop self-scheduling composes of static and dynamic allocation, weighting algorithm is adopted in the static part, while the well-known loop self-scheduling is adopted in dynamic part. The loop block is partitioned according to the weighting of MIC and HOST nodes. Accordingly, Xeon Phi with many-core is adopted to implement parallel loop self-scheduling. Finally, we test the performance in the experiments by four applicable problems: matrix multiplication, sparse matrix multiplication, Mandelbrot set and circuit meet. The experimental results indicate how to do the weight allocation and which scheduling method can achieve the best performance.     

一种基于VxWorks的内存分配算法

研究了VxWorks系统内存分配算法,指出了常用内存管理算法的局限性,在此基础上,提出了一种改进的内存分配算法.改进的内存分配算法包括优化的内存块分配算法和快速高效的动态内存分配算法,两者结合使用将会有效提高嵌入式系统的性能.对改进内存算法的实现作了详细的介绍.     

一种基于并行遗传算法的网格资源分配方法

提出了基于并行遗传算法的网格资源分配方法，并采用粗粒度模型设计了该并行算法。为了评估该并行算法的性能，在PC集群上实现了该并行算法和一个串行遗传算法。通过比较两个算法的执行时间和解的质量，说明了并行算法极大地提高了求解的速度和质量，是一种高效的资源分配方法。     

基于优先级的TDMA动态时隙分配算法

根据帧结构的不同对现有的时隙分配算法进行分类,分析其特点及综合性能。根据二叉树块内均分法,提出一种改进的时分多址动态时隙分配算法,地面主控站可根据用户的紧急或优先级高低的预约请求进行实时分配,能满足用户占用时隙块发送较长报文的需求。仿真结果表明,该算法能减少报文的平均延误时间,适合突发应急报文的传输需要。     

关联规则挖掘算法的多核并行优化

分析了并行关联规则挖掘算法存在的不足,提出了一种改进的关联规则挖掘的多核并行优化算法。该算法对Apriori算法的压缩矩阵进行了改造,并在多核平台下利用OpenMP技术和TBB技术对串行程序进行循环并行化和任务分配的并行化设计,最大限度地实现并行关联规则挖掘。     

A fully parallel block independent set algorithm for distributed sparse matrices

We present a fully parallel algorithm for constructing block independent set for general sparse matrices in a distributed environment. The block independent set is used in the construction of parallel multilevel preconditioners in solving large sparse matrices on distributed memory parallel computers. We compare a few implementations of the parallel multilevel ILU preconditioners with different block independent set construction strategies. Numerical experiments indicate that the parallel block independent set algorithm is effective in reducing both the parallel multilevel preconditioner construction time and the size of the last level reduced system.     

信号实时采集系统的最佳并行线程数的研究

为解决多核环境下,信号采集系统的数据处理实时性问题,提高波形数据采集和数据显示速度,提出使用裸线程构建数据采集模块和数据处理模块的最佳线程分配数量的最优线程分配算法,其目的在于合理分配线程给各个模块,达到系统的最佳性能。该算法基于生产者-消费者模式、操作系统多线程时间片轮转调度策略,根据各模块的工作量酌情调节线程比例,使应用程序达到最高加速比。实验表明,在双核环境下,该最佳线程数算法计算出最佳线程组合,使采集波形数据和数据显示合理并行化,相对于其他的线程组合分配方式完成程序花费的时间更少,提高了系统加速比、运算性能以及实时性。通过最优线程分配算法,提供了最优的线程数量分配方案,提高并行程序执行效率,减少了不必要的线程开销,提高了波形信号采集实时性。