基于移动平台的异构并行字符串匹配算法

针对信息处理中常见的字符串匹配问题,通过对经典的Brute Force算法和KnuthMorris-Pratt算法进行分析,根据GPU异构并行计算任务的分配特性,设计一种针对Knuth-Morris-Pratt算法的数据重叠划分并行方案,并提出一种基于移动平台的异构并行字符串匹配算法KMP_MOP.在PowerVR移动平台环境下使用千万级长度的字符串数据对算法的性能进行测试,同时对算法在其他平台的执行情况进行比较,验证了并行算法的性能可移植性.实验结果表明,KMP_MOP算法能充分利用移动平台中的GPU性能,有效提高具有GPU的移动平台设备的字符串匹配效率.     

分裂合并算法的优化及并行化方案

研究了分裂合并算法的优化方法,并提出相应的并行化方案.修改了图像在区域合并阶段中原有的最佳合并原则,增加了满足合并条件的相邻区域的匹配率,减少算法迭代次数.为解决合并阶段的负载不平衡提出了一种新方法;同时针对分裂阶段的负载不平衡,提出了一种新的分裂合并算法并行方案,并分析了两种并行方案在负载平衡,通信复杂度及可扩展性的差异.实验结果表明,对分裂合并算法的优化能有效提高算法的效率,其并行化方案切实可行.     

基于并行环境的模型检查技术研究与实现

针对实时系统模型检查中的突出问题：状态组合爆炸,提出一种基于并行环境的实时系统模型检查技术,用邻接表存储时钟带,用C＋＋和MPI设计并实现了一个并行实时系统模型检查器———PRAModelChecker,选择一个典型的实例对PRAModelChecker的性能进行分析.实验表明,随着系统复杂性的增加,不但能提高工作效率,而且能处理的系统规模可伸缩,从而为从根本上解决状态组合爆炸问题提供了一种新的途径.     

云平台下基因 基因相互作用识别算法

针对现有的快速方差分析算法进行并行可扩展性改进, 设计一种高效的并行计算模型, 并提出一种基于MapReduce模型的基因 基因相互作用识别算法--MRANOVA算法. 该算法有效解决了现有基因 基因相互作用识别算法在海量数据规模下普遍存在计算复杂度过高的问题. 实验结果表明, 该算法充分利用了云平台的并行计算能力, 随着数据量的增大, 加速比逐渐接近于集群数量, 可高效准确地完成基因 基因相互作用的识别.     

基于多核环境的并行性双向枚举连接

基于多核处理器, 结合自底向上和自顶向下两种算法, 提出一种图遍历驱动的双向优化算法, 该算法充分利用两种遍历算法的优点, 并发挥多核环境的优势, 实现了最优查询计划的高性能并行构建, 解决了并行双向枚举连接问题. 实验结果表明, 该算法的性能优于已有算法, 可明显提高数据库查询速度.     

基于多核环境的并行性双向枚举连接

基于多核处理器,结合自底向上和自顶向下两种算法,提出一种图遍历驱动的双向优化算法,该算法充分利用两种遍历算法的优点,并发挥多核环境的优势,实现了最优查询计划的高性能并行构建,解决了并行双向枚举连接问题.实验结果表明,该算法的性能优于已有算法,可明显提高数据库查询速度.     

基于深腾1800机群系统的分子动力学并行仿真研究

介绍了分子动力学并行仿真计算的软硬件环境,分析了现有的几种并行算法,确定采用区域分解法作为并行算法,并在此基础上提出了基于区域二次划分的分子动力学并行仿真算法.另外,阐述了原子链、原子近邻表和原子亲属表的概念,提出了基于永久序号的消息传递策略.最后,设计了分子动力学并行仿真程序,并分别在1、2、3、4台结点机上进行了实验,运行结果表明:加速比随着结点数的增加而增加,并行效率虽略有下降但都在87.5%以上,并行效率并没有随着结点数的增加有明显的降低,说明并行程序具有很好的扩展性.     

一种新型的制造元设计方案

建立了制造元设计问题的整数规划模型,设计了一种基于疫苗接种的免疫算法,构造了一种基于免疫计算的制造元设计问题解决方案。实验结果表明,本文方案优于已有方案,能够有效地解决大中等规模的制造元设计问题,具有较好的应用价值。     

大数据挖掘中的MapReduce并行聚类优化算法研究

为了有效解决云计算环境下海量数据的并行聚类问题,以典型的基于距离的Kmeans聚类算法为例,提出了一种MapReduce并行聚类优化算法.首先将差分进化算法与K-means算法相结合,从而利用差分进化算法的强大全局搜索能力克服典型K-means算法对初始中心较为敏感的缺点,利于增强全局最优解的稳定性.然后把优化后的算法在Hadoop的Map Reduce框架下做了并行化的设计.实验结果表明,与其他多种分布式设计相比,提出的并行聚类优化算法能够在保证聚类效果的前提下,大大减少了运算的时间,提高了大规模数据的聚类效率.     

基于双线性对的无证书并行多重签名方案

针对目前无证书多重签名方案在计算效率、通信成本和安全性等方面存在的问题,提出一种基于双线性对的无证书多重签名方案,并模拟3种不同类型的攻击者,分析新签名算法的不可伪造性.该方法基于无证书短签名的思想,构造签名长度较短的并行多重签名方案.仿真实验表明,与目前已有的方案相比,新方案降低了签名的通信成本和计算量,因此更适合于资源受限的网络环境.     

基于MapReduce的中文词性标注CRF模型并行化训练研究

针对条件随机场模型面对大规模数据传统训练算法单机处理性能不高的问题, 提出一种基于MapReduce框架的条件随机场模型训练并行化方法, 设计了条件随机场模型特征提取及参数估计的并行算法, 实现了迭代缩放算法的并行。实验表明, 所提出的并行化方法在保证训练结果正确性的同时, 大大减少了训练时间, 效率得到较大提升。     

并行计算机与并行算法述评

并行计算是大规模科学工程计算和数据处理的一个重要工具和必然趋势，本文从并行计算机系统和并行算法两个方面论述了并行处理的基本原理和方法。     

PDM:基于Hadoop的并行数据分析系统

提出了一款基于Hadoop的并行数据分析系统——PDM.该系统拥有大量以MapReduce为计算框架的并行数据分析算法,不仅包括传统的ETL、数据挖掘、数据统计和文本分析算法,还引入了基于图理论的SNA(社会网络分析)算法.详细阐述了并行多元线性回归算法和"多源最短路径"算法的原理和实现,其中,提出的"消息传递模型"能有效解决MapReduce难以处理邻接矩阵的问题;介绍了基于电信数据的典型应用,如采用并行k均值和决策树算法实现的"套餐推荐",利用并行PageRank算法实现的"营销关键点发现"等;最后通过性能测试,说明该系统适合高效地处理大规模数据.     

电特大天线增益的高效求解

为解决电特大天线辐射特性计算效率低的问题,提出并实现了一种基于多极子的聚集思想快速求解远场信息的高效并行算法.根据目标在并行多层快速多极子中几何树的特征,提出高层远场模式直接聚集,并且按行并行插值的混合MPI-OpenMP并行计算方案.将该算法应用于大射电天文望远镜FAST（five-hundred-meter aperture spherical telescope）的远场方向图和增益的计算,通过与等效电流直接积分法计算对比展示其计算精度与效率.结果验证该算法的远场辐射特性计算精度,且同等远场计算任务量下,平均单方向计算效率提高近万倍.      

基于MPI电力系统潮流P-Q分解法的并行算法

为了更快更有效地提高大规模电力系统潮流计算的速度,引入并行处理技术,文中提出了一种基于MPI的电力系统潮流P-Q分解法的并行算法,将潮流计算问题分解为多个子任务在基于MPI消息传递模式的多处理机中同时进行计算.运用该并行算法,针对不同规模的网络进行潮流计算,结果表明,该并行算法能有效地提高电力系统计算的速度,具有广阔的应用前景.     

基于OpenCL的图像灰度化并行算法研究

随着图像数据量的增加,传统单核处理器或多处理器结构的计算方式已无法满足图像灰度化实时处理需求.该文利用图像处理器(GPU)在异构并行计算的优势,提出了基于开放式计算语言(OpenCL)的图像灰度化并行算法.通过分析加权平均图像灰度化数据处理的并行性,对任务进行了层次化分解,设计了2级并行的并行算法并映射到“CPU+GPU”异构计算平台上.实验结果显示:图像灰度化并行算法在OpenCL架构下NVIDIA GPU计算平台上相比串行算法、多核CPU并行算法和CUDA并行算法的性能分别获得了27.04倍、4.96倍和1.21倍的加速比.该文提出的并行优化方法的有效性和性能可移植性得到了验证.     

用于粗糙集约简的并行算法

通过对数据挖掘粗糙集约简算法的研究, 提出一种基于区分能力指数的信息系统数据划分思想. 先将系统按属性区分能力分成若干子表, 再由子表的约简求原系统的约简, 这种思想较好地简化了布尔函数的化简过程. 根据该思想设计了一个属性约简并行算法, 并利用Petri网模拟工具CPN Tools对算法的负载平衡进行了分析, 通过实验与相应的串行算法在时间上进行了对比, 实验结果显示, 该算法对于对象较多的大规模系统具有较高的效率.     

并行机优化调度问题的新算法

将调度规则的简洁性与遗传算法的强大搜索能力相结合,提出一种能用于最小化拖期任务数并行机调度问题的基于遗传的新的调度算法,并用计算实例表明了该调度算法优于迄今最好的启发式算法,并能适用于大规模并行机调度问题,本算法计算量小,具有很强的鲁棒性。提出的基于遗传的调度算法不仅能用于生产调度领域,在大规模数值计算及计算机网络技术等方面都有很好的应用前景。     

Implicit Parallel FEM Analysis of Shallow Water Equations

The velocity field in the Wu River at Chongqing was simulated using the shallow water equation implemented on clustered workstations. The parallel computing technique was used to increase the computing power. The shallow water equation was discretized to a linear system of equations with a direct parallel generalized minimum residual algorithm (GMRES) used to solve the linear system. Unlike other parallel GMRES methods, the direct GMRES method does not alter the sequential algorithm, but bases the parallelization on basic operations such as the matrix-vector product. The computed results agree well with observed results. The parallel computing technique significantly increases the solution speed for this largescale problem.     

网格环境下期权定价BSDE模型的并行实现

提出了一种在CNGrid网格服务环境下解决期权定价问题的并行应用方法.这种方法基于BSDE(backward stochastic differential equation)模型.根据异构计算资源的特点,使用CUDA和MPI分别在GPU计算节点和CPU计算节点上实现并行算法,比较不同编程在异构计算节点上的实现效率.通过监控计算节点上计算任务的负载状况,利用CNGrid所提供的计算服务,灵活地在异构计算节点上完成期权定价计算任务.