随机算法异步并行化的效率分析

随机算法的执行时间具有不确定性,这种不确定性为随机算法的异步并行提供了良好的基础,已有许多计算实验表明了随机算法的异步并行可以达到线性甚至超线性的加速.对于求解SAT问题的随机算法RDP,研究了异步并行效率与运行时间分布和处理器数目之间的关系.应用一种单峰分布──分段线性分布模型来模拟随机算法的运行时间分布.理论分析和计算结果均表明:当处理器数目k较小和单峰位于分布的前部时,随机算法的异步并行具有近线性加速.     

共享信息素矩阵:一种新的并行ACO方法

提出并实现了一种新的蚁群优化(ACO)并行化策略SHOP(Sharing one pheromone matrix). 主要思想是基于多蚁群在解的构造过程和信息素更新过程中共享同一个信息素矩阵. 以ACS和MMAS的SHOP并行实现为例, 简要描述了SHOP 设计思想和实现过程, 尝试了ACS和MMAS并行混合. 以对称TSP测试集为对象, 将SHOP的实现与相应串行算法在相同计算环境下的实验结果比较, 以及与现有的并行实现进行比较, 结果表明SHOP并行策略相对于串行ACO及现有的并行策略具有一定的优势.     

一种基于路径优化的推测多线程划分算法

推测多线程(speculative multithreading,简称SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,基于控制流图和分支预测技术的线程划分方法,不可避免地会受到划分路径上所存在的控制依赖和数据依赖的制约.目前,在传统的线程划分算法中存在的一个重要问题是,在对划分路径进行选取时只考虑了控制依赖影响却不能有效地综合考虑数据依赖的影响,进而导致不能选取最佳的划分路径.因此,针对传统方法中这种依赖评估方法效率低下的问题,设计并实现了一种基于路径优化的线程划分算法.该算法通过引入基于程序切片技术的预计算方法,建立一种路径评估方法来评估程序间的控制和数据依赖.同时,引入控制线程体大小的启发式规则,以便有效地解决负载不平衡的问题.基于Olden测试集的测试结果表明,所提出的算法可以有效地对非规则程序进行划分,其平均加速比可以达到1.83.     

面向CFD的程序自动并行化工具APFC

针对并行处理的热点问题,本文介绍了面向CFD的程序自动并行化工具APFC。APFC实现了数组共享变量的识别和相关性分析,能够自动搜索帧内同步和通信点,并自动生成并行划分后的节点源程序。经APFC处理的程序有很好的可移植性和较高的并行效率。     

一种并行多目标遗传邻域搜索算法

现有的多目标遗传算法在解决大规模多目标生产调度问题时虽然有效,但往往非常耗时,难以应用于实际.为了提高求解效率,提出了一种并行多目标遗传邻域搜索算法来求解Pareto边界.该算法将多目标遗传算法的进化方向划分为若干范围,然后同时对每个进化方向的范围使用多目标遗传邻域搜索算法,并行地搜索各方向范围内的Pareto边界;在各进化方向范围内进化的子种群会定期交流各自进化成果.多目标遗传邻域搜索算法的并行化在不增加求解时间的前提下,提高了求解精度,加快了算法的收敛速度.仿真实验结果验证了算法的可行性与有效性.     

用于太赫兹通信的双向全并行相位估计算法

在太赫兹通信的超宽带应用场景下,太赫兹载波是通过多次倍频实现,因而导致相噪严重恶化。基于太赫兹频率下的多极/零相位噪声模型,在传统的盲相位估计算法的基础上,提出了一种全并行化的相位估计算法。该算法通过在每个并行数据中插入导频,将导频相噪信息作为初始相位对并行数据进行相位扩展及旋转鉴相。借鉴传统盲相位估计算法的最佳相位估计值的判决选择思路,同时利用前一时刻导频和当前时刻导频,对当前并行数据从前后两个方向进行相位估计并对前后两个估计相位基于距离前后导频的位置进行加权求和以获得最佳相位估计信息。经过仿真验证,通过该算法后残余相噪在1 MHz和10 MHz处分别降低10 dBc/Hz和25 dBc/Hz。     

Locality‐Conscious Nested‐Loops Parallelization

To speed up data‐intensive programs, two complementary techniques, namely nested loops parallelization and data locality optimization, should be considered. Effective parallelization techniques distribute the computation and necessary data across different processors, whereas data locality places data on the same processor. Therefore, locality and parallelization may demand different loop transformations. As such, an integrated approach that combines these two can generate much better results than each individual approach. This paper proposes a unified approach that integrates these two techniques to obtain an appropriate loop transformation. Applying this transformation results in coarse grain parallelism through exploiting the largest possible groups of outer permutable loops in addition to data locality through dependence satisfaction at inner loops. These groups can be further tiled to improve data locality through exploiting data reuse in multiple dimensions.     

A few bad ideas on the way to the triumph of parallel computing

Parallelism has become mainstream, in the multicore chip, the GPU, and the internet datacenter running MapReduce. In my field, large-scale scientific computing, parallelism now reigns triumphant.     

Development and analysis of a tool for speed up of EnergyPlus through parallelization

This paper describes how the EPparallel tool splits a single annual simulation into 12 simulations of one month each and runs them in parallel. The paper also describes the methodology to prepare input files, enable file sharing between nodes, collate results generated by the nodes, and ensure quality check on the simulations. The EPparallel tool uses Message Passing Interface library and runs on Linux. The tool has been tested on 16 commercial reference buildings over 16 US weather files. The results of these 256 runs which include the run times, computing time overheads, speed gains and accuracy of results are presented in this paper. The speed gain ranged from 2.9×to 7.8×and deviation (percentage of output values obtained in parallel simulation which were off by more than 1% as compared to output values obtained in annual simulation) ranged from 0% to 4%.