Horde:面向多核集群的并行编程框架

并行程序可以充分发掘硬件计算能力并提高程序性能,但是在多核集群环境中编写并行程序十分复杂。该文提出了面向多核集群的并行编程框架,Horde。Horde提供了一组简单易用的消息传递接口和事件驱动(event-driven)编程模型,用以帮助程序员表达算法逻辑中潜在的并行性,将计算分解与底层硬件结构去耦合,从而简化编写并行程序的复杂度,灵活地在不同的底层结构的集群上进行映射并能保持良好的性能。此外,Horde也提供了有效的任务对象迁移机制,可以实现动态负载均衡与在线容错。在128核集群上的实验表明:Horde可以有效执行并行程序,并且可以实现高效的任务对象迁移。     

多核构架下基于OpenMP 的Huffman压缩算法并行设计

本文是对多核程序设计的一种探索,在OpenMP模型下以赫夫曼算法为基础设计并行压缩程序.首先对传统的串行程序进行分析,使应用程序开发人员了解程序行为、发现性能瓶颈、明确优化方向.再用OpenMP的基本结构进行并行程序的设计之后,借助开发工具对并行程序进行优化和调试,得到改进方案.然后在双核处理器上分别运行并行程序与串行程序,将两者进行性能上的比较,实验结果证明性能得到很大程度地提高。     

采用改进PSO的LU循环分块优化算法

首先研究了LU循环分块算法,然后讨论了传统粒子群优化算法并针对用于循环分块方面的不足加以改进,最后把优化的粒子群优化算法用于LU分解算法之中,从而提出了1个PSO-LU循环分块算法.仿真实验结果表明,和原始基准测试程序相比,所提循环分块算法的性能有所提升,其更充分地提高高速缓存运算效率.     

并行程序实现ABEEM σπ模型电荷分布计算

对以密度泛函理论和电负性均衡原理为基础发展的原子-键电负性均衡方法中的σπ模型(ABEEM σπ模型)进行分析得出,利用该模型计算分子体系的电荷分布时,最耗费时间的部分是求解线性方程组.根据解线性方程组的串行程序,我们提出在并行环境下不带平方根的Cholesky分解方法.结果表明,利用改编后的并行程序能快速而准确地计算分子的电荷分布,算法随着矩阵规模的增大,并行效率也随之增高,即分子体系越大结果越理想.因此本算法适用于大规模问题的计算.     

基于优化PSO的LU循环分块方法

循环分块技术可以提高Cache的命中率,而循环分块的规模是该技术的决定性因素。利用粒子群优化算法可以优化循环分块的规模,获取合适规模的分块,提高循环分块的效率。首先研究了LU分解算法,然后讨论了传统粒子群优化算法并针对用于循环分块方面的不足加以改进,最后把优化的粒子群优化算法用于LU分解算法之中,从而提出了一个PSO-LU循环分块算法。仿真实验结果表明,和原始基准测试程序相比,所提循环分块算法比性能有所提升,更充分地提高高速缓存运算效率。     

平面波谱-表面积分法的快速算法

针对平面波谱-表面积分法计算效率严重依赖于天线口径的问题,提出谱域积分预设方案,提取出谱域积分插值点,建立天线口径平面波角谱密度函数数据库,避免了大量重复计算,并将平面波谱理论的近场计算由四重积分弱化为二重积分.然后,根据平面波谱-表面积分法关于带罩天线远场电性能计算的思想,提出了基于等效源区域分解的并行平面波谱-表面积分算法.开发并在集群系统中实测了基于MPI环境的并行程序,作为应用计算了弹载天线-罩系统远场方向图,结果表明该程序高效准确.     

关于串行程序并行化

并行程序设计主要有两种途径,即使用并行程序设计语言编写并行程序,或将串行程序并行化.串行程序并行化是一种比较有效的并行程序设计的途径.通过介绍并行技术的现状及相关分析的一些定义,给出了一个关于在串行程序中识别可并行执行语句的算法,论述了这一算法的意义.     

浅水流动的并行计算

针对大规模水环境预测的需要,建立了网络并行机群系统(COW),进行浅水流动的并行计算研究。并行计算实现过程中引进了一种基于图论的区域分解算法,同时提出了一种针对并行计算的网格重新编号算法。作为浅水流动并行程序的验证,计算了较低Reynolds数情况下(Re≤300)圆柱绕流的流态,将各种特征物理量如Strouhal数、回流区长度等与前人的结果进行了比较。计算结果表明:浅水流动计算程序及相应的并行算法具有计算效率高、收敛速度快以及计算精度高等优点,可进一步应用于天然河道流场的并行模拟。     

基于矩阵分解和聚类的协同过滤算法

基于矩阵分解和聚类提出一种协同过滤推荐算法. 先利用交替最小二乘（ALS)算法进行矩阵分解, 再利用改进的k-均值聚类算法弥补单一ALS算法在后期协同过滤阶段产生的大计算量问题, 解决了由于减小原始矩阵高维度、 高稀疏性带来的推荐准确度较低的问题, 极大提高了计算速度和推荐精度. 实验结果表明, 改进算法在推荐准确性上有明显提高.     

ABEEMσπ/MM模型中静电相互作用能的并行化

ABEEMσπ/MM模型程序中,计算静电相互作用能非常耗费机时.针对原串行程序中多个循环相互嵌套的求解部分,进行循环带状划分并行化处理.经测试表明,利用新编制的并行程序进行动力学模拟,并行加速比以线性趋势提高、求解静电相互作用能速度大幅度加快、尤其是针对原子数较多的分子体系效果比较理想.利用36个CPU,对于位点数为10 000左右的蛋白质体系,进行1ns的动力学模拟,至少可以节省1年左右的时间,明显地提高了研究蛋白质体系性质的效率.     

异构任务图的实现模型

任意异构程序映射到任意异松系统上执行,是并行程序计算最复杂的情况,为此提出了异构任务图的定义,它是异构程度直观和有效描述方法,还研究了异构任务图的实现模型,它是异构计算环境中软件和硬件的桥梁,分别给出了任务图的分簇算法、系统图的分簇算法和映射算法及应用实例,利用该模型可设计出可移植的并行程序,然后调度到可动态配置的异构计算机组织上运行。     

质因数分解算法及其程序设计

给出并证明质因数分解计算方法,算法计算量为n1/2次求余数计算,最后给出一质因数分解的精品程序.     

共享存储器多处理机并行计算编译及调度机制

引入并行程序段标记、程序段归并构造并行程序编译思想,设立并行计算调度状态字构造并行计算调度表,提出了一种有效的共享存储器多处理机程序、作业级并行计算编译调度思想及相应的算法。     

基于单元分解的改进D?lite路径规划算法

障碍物分隔搜索空间会隐藏D?lite算法正确的搜索方向,增加算法的计算次数,进而影响搜索效率,针对这一问题提出一种基于单元分解的改进D?lite路径规划算法.在原有Boustrophedon单元分解法的基础上加入了新的分解规则,对环境地图进行单元分解并构建了以单元为节点的图.设计了双向图搜索算法,能够快速计算出最短路径需要依次经过哪些单元.在这些单元中设置核心网格并依照顺序构建搜索链表,引导正确的搜索方向,使规划速度提高.在仿真平台上将算法与其他路径规划算法进行对比实验,实验结果表明,算法规划出的路径长度与其他算法几乎没有差别,并且减少了计算次数、降低了规划时间,验证了算法提高路径规划效率的有效性.     

基于GA和过完备原子库划分的MP信号稀疏分解算法

信号稀疏分解计算量大是阻碍其实时应用的主要因素.研究基于匹配追踪(Matching Pursuit)方法实现的信号稀疏分解算法,提出了基于过完备原子库集合划分的、分两阶段搜索的、遗传算法快速寻找MP过程中每一步分解的最佳原子,在稀疏分解重建信号质量不变的条件下,提高了稀疏分解的速度.算法的有效性为实验结果所证实.     

一种实用快速非负矩阵分解算法

提出了一种基于快速非负矩阵分解算法的实用新算法.该实用快速非负矩阵分解算法扩展了快速非负矩阵分解算法的约束条件,并且保持了较高的收敛速度,更具一般性和实用性.然后对该新算法进行了一些稀疏非负矩阵分解的扩展应用.数值实验显示该实用快速非负矩阵分解算法和快速非负矩阵分解算法具有相近的收敛速度,与其他经典非负矩阵分解算法相比其收敛速度有明显的提高,同时对添加稀疏性约束条件的实验也有很好的效果.     

一种面向并行程序的代码调试分析工具设计实现

并行程序的应用在提高程序运行效率的同时,也带来了不确定性的错误.这种错误往往难以复现,传统的调试工具越发难以满足并行程序的调试需求.据此提出了一种面向并行程序错误检测以及确定性回放的方法,针对并行程序中容易发生的数据竞争、死锁、原子性违反这几类错误进行检测判断;对并行程序的运行进行插桩以保证程序重复执行时的次序一致.在此理论基础上设计实现了Eclipse插件.通过试验,该工具可以对并行程序易发的错误进行有效的检测判断,较大程度地减少程序调试的工作量.     

基于改进的PASTd子空间跟踪的半盲多用户检测

研究和分析了多种子空间跟踪算法.直接特征值分解和奇异值分解复杂度高,不利于工程实现,针对低复杂度的PASTd算法由于估计的特征向量不正交,从而导致收敛速度极慢的问题,提出一种改进的PASTd子空间跟踪算法,并将其应用于基于子空间的半盲多用户检测.该算法保证了特征向量的正交性,因此提高了算法的收敛速度.仿真结果表明,提出的算法收敛速度快,输出信干噪比和误码率性能优于PASTd半盲检测算法和OPAST半盲检测算法,逼近SVD半盲检测算法,并保持了较低的计算复杂度.     

面向高光谱影像分类的改进局部切空间排列降维

提出多策略提升的局部切空间排列算法来解决常规局部切空间排列降维在高光谱影像分类中计算复杂度高的问题.通过引入随机映射来预先减少高光谱影像波段数,降低后续k-邻域和局部切空间构建的计算复杂度;采用递归兰索斯切分算法快速构建近似k-邻域,降低常规k-邻域构建的计算时间;采用快速近似奇异值分解算法提高全局排列矩阵的本征分解计算速度.利用两个不同的高光谱数据集,设计4组实验来分析多策略速度提升的局部切空间排列算法的计算性能和分类效果.实验证明,相比常规局部切空间排列方法,多策略提升的局部切空间排列方法损失约1%左右的总体分类精度却能够提高至少3倍的计算速度.     

向量式有限元桁架结构并行程序节点分配技术

结合向量式有限元(VFIFE)的计算规则以及桁架结构的特点,提出了一种并行程序节点分配机制.通过对桁架结构模型数据的分析,定义模型数据的分解规则,动态实现对模型数据的分解.依据分解的结果来动态划分并行计算的数据集,并且基于特定的并行计算框架完成并行计算.实例验证表明,该节点分配机制是有效的,并且极大地提高了计算效率.