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

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

基于人工免疫算法的推测多线程线程划分参数的优化（英文）

目的:用人工免疫算法优化线程划分过程的主要影响因素,使不同应用获得最优划分方案。创新点:将智能算法应用到推测多线程技术,实现该技术在线程划分过程中的优化。方法:首先,根据启发式规则提取影响线程划分的五个参数,分别是DT,TSL,TSU,SDL,SDU。五个参数根据启发式规则确定取值范围,步长变化是随机的。将加速比设定为目标,五个参数变化形成解空间,优化目标是在解空间中寻找最优解(图6),即找出各个应用最优的划分策略。利用人工免疫算法搜索解空间,找到最优解(表4)。结论:针对Olden测试集中每个测试函数获得最优划分参数值(图10-20),测试集中的函数在四核平台上的测试性能较之机器学习方法线程划分算法提高3.00%,较之启发式规则线程划分方法性提高8.92%。     

基于启发式搜索的移动机器人主动定位

提出了一种基于启发式搜索的主动定位算法.首先利用自适应粒子聚类算法对粒子进行聚类;然后分别构造路径规划树和解空间树,并根据优先级评估函数计算解空间树中所有节点的优先级,利用优先队列式分支限界法解决路径搜索问题;最后针对单个粒子簇分散问题提出了一种定位精度主动提升方法.仿真实验验证了所提出方法的有效性.     

基于CUDA的并行布谷鸟搜索算法设计与实现

布谷鸟搜索（cuckoo search,CS）算法是近几年发展起来的智能元启发式算法,已经被成功应用于多种优化问题中。针对CS算法在求解大数据、大规模复杂问题时,计算时间过长的问题,提出了一种基于统一计算设备架构（compute unified device architecture,CUDA）的并行布谷鸟搜索算法。该算法的并行实现采用任务并行与数据并行相结合的方式,利用图形处理器（graphic processing unit,GPU）线程块与线程分别映射布谷鸟个体与个体的每一维数据,并行实现CS算法中的鸟巢位置更新、个体适应度评估、鸟巢重建、寻找最优个体操作。整个CS算法的寻优迭代过程完全通过GPU实现,降低了算法计算过程中CPU与GPU的通信开销。对4个经典基准测试函数进行了仿真实验,结果表明,相比标准CS算法,基于CUDA架构的并行CS算法在求解收敛性一致的前提下,在求解速度上获得了高达110倍的计算加速比。     

一种变维搜索的量子粒子群优化聚类算法

针对PSO聚类算法需要预定聚类中心个数的问题,提出一种变维搜索解空间的量子粒子群优化聚类算法.该算法采用量子编码的方式实现双链并行搜索,加速寻优过程,避免了粒子在解空间边界过分聚集;设计了幅角相位旋转算子和变异算子,使幅角相位依变概率进行变异,提高了粒子群的多样性;在迭代过程中,动态更新了聚类中心的数量,使算法能够在不同维度的解空间中寻优.仿真实验表明,该算法的收敛速度和聚类精度得到一定的改善.     

求解线性SVM的非精确步长搜索割平面方法

割平面方法可高效求解线性支持向量机问题,其主要思路是通过不断添加割平面并利用精确线性搜索实现算法的加速和优化.针对其中的非光滑线性搜索问题,文中提出一种基于非精确步长搜索的加速割平面方法.该方法使用较少的迭代次数就能确定最优步长所在的子区间.在此基础上,用二点二次插值的闭式解逼近最优步长,从而较精确线性搜索方法速度更快、开销更小,且保持同样的收敛边界.大量实验表明,文中方法效率优于基于精确线性搜索的优化割平面方法,在一些数据库上的收敛速度甚至提升50%.     

程序缺陷自动修复研究进展及关键问题

程序缺陷自动修复是指针对程序中存在的缺陷,自动生成相应的程序补丁,进而使程序恢复正常运行.首先,根据补丁生成方式的不同,将程序缺陷自动修复方法划分为4类,分别为基于搜索的、基于语义的、基于机器学习的以及基于错误报告驱动的程序缺陷自动修复方法.基于搜索的程序缺陷自动修复方法运用启发式算法在搜索空间内通过搜索生成程序补丁;...     

基于分组和IGSA的并行密度聚类算法

针对并行密度聚类算法在处理大数据集时存在伸缩困难、参数寻优能力不佳、并行化效率较低等问题,提出一种基于分组和重力搜索优化算法(improve gravitational search algorithm,IGSA)的并行密度聚类算法(densi-ty-based clustering algorithm based on groups and improve gravitational search,MR-GDBIGS).首先,该算法设计了基于图形的分组策略(grouping strategy based on pattern,GSP)来有效划分数据,加速邻域搜索,解决了处理大数据集时伸缩困难的问题;其次,在局部聚类中提出基于位置更新函数(position update function,PUF)的重力搜索优化算法,动态寻找局部聚类中的最优参数,提升了局部聚类的效果;最后,提出基于覆盖树的并行局部簇合并策略(cluster merging strategy by using MapReduce,MR-CTMC),在实现局部簇并行化合并的同时加快了合并局部簇的收敛速度,提升了算法整体的并行化效率.实验结果表明,MR-GDBIGS算法在处理大数据时的聚类效果更佳,且并行化性能更好.     

面向规则DOACROSS循环的流水并行代码自动生成

发掘DOACROSS 循环中蕴含的并行性,选择合适的策略将其并行执行,对提升程序的并行性能非常重要.流水并行方式是规则DOACROSS 循环并行的重要方式.自动生成性能良好的流水并行代码是一项困难的工作,并行编译器对程序自动并行时常常对DOACROSS 循环作保守处理,损失了DOACROSS 循环包含的并行性,限制了程序的并行性能.针对上述问题,设计了一种选择计算划分循环层和循环分块层的启发式算法,给出了一个基于流水并行代价模型的循环分块大小计算公式,并使用计数信号量进行并行线程之间的同步,实现了基于OpenMP 的规则DOACROSS 循环流水并行代码的自动生成.通过对有限差分松弛法（finite difference relaxation,简称FDR）的波前（wavefront）循环和时域有限差分法（finite difference time domain,简称FDTD）中典型循环以及程序Poisson,LU 和Jacobi 的测试,算法自动生成的流水并行代码能够在多核处理器上获得明显的性能提升,使用的流水分块大小计算公式能够较为精确地计算出循环流水并行时的最佳分块大小.自动生成的流水并行代码与基于手工选择的最优分块大小的流水并行代码相比,加速比达到手工选择加速比的89%.     

空间平滑搜索CLARANS算法

CLARANS是一种有效且广泛应用于空间数据挖掘的聚类算法,非常适合发现多边形的聚类结果.CLARANS的实质是随机重启搜索优化算法.由于搜索空间的表面粗糙不平,布满了局部最优解的"陷阱",因此CLARANS算法易受局部最优解的影响.空间平滑技术允许启发式搜索有效地避开局部最优解的"陷阱".本文给出了基于空间平滑搜索的CLARANS算法(CLARANS algorithm based on Search Space Smoothing - CLARANS-SSS),设计合理的噪声法空间平滑策略能够移除搜索空间中大部分的局部最优解.实验结果表明空间平滑搜索对于CLARANS算法非常有效.     

任务并行编程模型下排列熵算法的并行实现

排列熵算法随着嵌入维数的增大,运算规模将会呈平方级数增大,计算时效性问题突出,亟待解决。为此,提出一种基于任务并行编程模型的线程级并行方法,通过任务并行运行系统(StarPU)将密集型计算划分为多个独立的任务,再由调度器将任务调度到不同的CPU上执行,实现排列熵算法的并行化。基于StarPU的排列熵并行算法与串行程序相比较,加速比为23.79倍,相较于OpenMP(一种用于共享内存并行系统的并行计算方案),在分配28个线程时,加速比为1.17倍,结果表明该方法能够有效实现排列熵算法的加速执行。     

排挤小生态遗传算法的改进方法

提出了基于搜索空间聚类分析的聚类排挤小生态遗传算法.通过分析适应值曲面的拓扑结构和扩大相似个体的搜索范围,聚类排挤可确定搜索空间的局部性,减少排挤的替换错误并抑制种群的遗传漂移;通过结合确定性替换和概率替换策略,聚类排挤提高了并行局部爬山能力和并行子种群维持能力.对不同多峰问题的仿真优化结果表明,聚类排挤小生态遗传算法的有效峰数量、平均峰值比和全局最优解比等综合性能一致地优于适应值共享、简单确定性排挤和概率排挤等小生态遗传算法.     

基于改进属性约简的细粒度并行AP聚类算法

Affinity Propagation(AP)聚类算法将所有数据点作为潜在的聚类中心,在相似度矩阵的基础上通过消息传递进行聚类.与传统聚类方法相比,对于规模很大的数据集,AP是一种快速、有效的聚类方法.正是这样,属性约简对于AP算法非常重要.另外,在大规模并行系统的设计中,细粒度并行是实现高性能的基本策略.提出了一种基于改进属性约简的细粒度并行AP聚类算法(IRPAP),将粒度思想引入到并行计算中.首先分析了并行计算中的粒度原理.然后用改进的属性约简算法对数据集预处理.此算法并行计算并选择差别矩阵元素,降低了时间空间复杂度,最后用AP算法聚类.整个IRPAP算法将任务划分到多个线程同时处理.实验证明,对于大规模数据集的聚类,IRPAP算法比AP算法效率更高.     

模型驱动的开发异构多核多级并行的方法

将异构多核处理器的资源分配问题抽象为一个三维优化空间,空间中的每个元素对应多任务程序的一个并行策略,确定程序有效并行策略的问题转化为优化空间的搜索问题。为了加速搜索,提出一种基于遗传算法的智能搜索方法。实验表明,模型驱动的并行策略选择方法能够在极短的时间内为程序生成较好的并行策略。     

基于PVM的启发式搜索的并行计算模型设计

通过分析人工智能中的A和A^*启发式搜索,提出了通过PVM工具包,设计和实现A和A^*启发式搜索的并行计算模型。在启发搜索过程中同时进行评估函数计算,使计算的速度加快。解决了在搜索解空间庞大,评估函数计算复杂的情况下,使用单计算机计算速度慢的问题。该文实现了基于PVM的启发式搜索过程,该模型可应用于一般性启发式搜索问题的并行计算模型。     

基于PAM和均匀设计的并行粒子群优化算法

聚类技术是数据挖掘中的一个重要方法,PAM（Partitioning Around Medoids）是基于分区的聚类算法的一种,它试图将[n]个数据对象分成[k]个部分。在并行粒子群PSO（Particle Swarm Optimization）算法中,需要划分整个种群为几个相互不重叠的子种群。因此,引入PAM来划分整个种群。通过聚类,相同子种群的粒子相对集中,从而能够较容易地相互学习。这使得有限的时间能够花费在最有效的搜索上,以便提高算法的搜索效率。为了均匀地探测整个解空间,引入均匀设计来产生初始种群,使种群成员均匀地分散在可行解空间中。进化过程中,均匀设计也被引入来替换种群中的较差个体。提出基于PAM和均匀设计的并行粒子群算法,它结合并充分利用了二者的优点。对几个测试问题的实验结果证明,提出的算法比传统的并行粒子群算法具有更高的性能和更好的收敛准确性。     

基于多尺度并行免疫克隆优化聚类算法

针对无监督分类问题,提出一种多尺度并行免疫克隆优化聚类算法.算法中,进化在多个子群之间并行进行,不同子群的抗体根据子群适应度采用不同变异尺度.进化初期,利用大尺度变异子群实现全局最优解空间的快速定位,同时变异尺度随着适应值的提升逐渐降低;进化后期,利用小尺度变异子群完成局部解空间的精确搜索.将新算法与其他聚类算法进行比较,所得结果表明新算法具有较好的聚类性能和鲁棒性.     

基于人工蜂群和最近邻原则的无监督聚类方法

针对聚类划分问题,提出一种基于改进人工蜂群和最近邻原则的无监督聚类方法。该方法将每个蜜源作为聚类问题的一个可行解,设计了蜜蜂的多维编码结构。为了有效执行聚类,依据采蜜蜂和跟随蜂局部搜索阶段选择的较优聚类中心,利用k均值算法中的最近邻原则划分聚类空间的所有模式。为了使蜜蜂有较强的局部和全局搜索能力,根据聚类问题特点,提出了新的局部和全局搜索方法。仿真实验结果表明了新方法的可行性和高效性。     

基于MapReduce和改进密度峰值的划分聚类算法

对于基于划分的聚类算法随机选取初始聚类中心导致初始中心敏感,聚类结果不稳定、集群效率低等问题,提出一种基于MapReduce框架和改进的密度峰值的划分聚类算法(based on MapReduce framework and im-proved density peak partition clustering algorithm,MR-IDPACA).首先,通过自然最近邻定义新的局部密度计算方式,将搜索样本密度峰值点作为划分聚类算法的初始聚类中心;其次针对算法在大规模数据下运行时间复杂,提出基于E2LSH(exact Euclidean locality sensitive hashing)的一种分区方法,即KLSH(K of locality sensitive hashing).通过该方法对数据分区后结合MapReduce框架并行搜寻初始聚类中心,有效减少了算法在搜索初始聚类中心时的运行时间;对于MapReduce框架中的数据倾斜问题,提出ME(multistage equilibrium)策略对中间数据进行多段均衡分区,以提升算法运行效率;在MapReduce框架下并行聚类,得到最终聚类结果.实验得出MR-IDPACA算法在单机环境下有着较高的准确率和较强的稳定性,集群性能上也有着较好的加速比和运行时间,聚类效果有所提升.     

自适应谱聚类算法并行实现及优化

谱聚类算法是基于谱图分割理论的聚类方法,其对高维、非凸数据分布问题有很好的聚类效果。但对大规模数据问题的聚类,该方法存在着计算时间和存储空间等方面的瓶颈。本文给出了一个自适应的谱聚类并行算法,通过局部计算和异步循环通信并行方法,最大限度减少了并行谱聚类中数据通信次数,并通过计算与通信重叠策略,进一步降低了并行算法的通信开销。在并行算法实现中,将自主开发的最优预条件共轭梯度法并行求解器 PLOBPCG 用于谱聚类的特征降维。在中科院的“元”超级计算机上,通过对两类大规模数据聚类的测试表明,在 2048 核上的加速比接近线性加速,并行效率达到96%以上。