高效并行算法的设计和分析.pdf

高效并行算法的设计与分析 论 文 摘 要 本文首先全面系统地回顾和总结了并行计算的历史、分析了其发展现状并预 测了其发展趋势，从而论证了开展高效并行算法设计与分析的研究的重要意义。 接着简要地介绍了几种常用和流行的并行算法设计所依据的计算模型以及一些并 行算法的基本概念。然后着重总结和探讨了高效并行算法设计的方法和原则，包 括提出了一些新的方法和原则，并把它们应用到多个研究领域，包括一些具有重大 挑战意义的科学工程计算问题，得到了一些具有重要价值的新结果，如高效并行排 序算法、并行数值计算方法、并行数据库算法以及并行人工智能与知识工程算法。 论文还特别地对分治法、回溯法和分枝限界法等的并行处理作了深刻的研究，提出 了并行回溯算法和并行分枝限界算法这两种适合于并行机上使用的一般算法设计 方法，并把它们应用到诸如人工智能、知识工程等领域中的问题，获得了一些重 要的高效并行算法。一般化的并行算法设计方法的提出丰富和发展了并行算法的 设计方法与技术，使许多原来在并行机上难以设计算法求解的问题现在可以容易 地得到解决，这无疑是并行算法研究中的一项创新成果。 关键词:、行tix、并行处理、、行爵、行计算模型、串行计算:，磊法 并行分治法、 并行回溯法、J并行分枝限界法、 并行数值计算方法 并行排序算法、 并行数据库算法、 并行人工智能与知识工程算法 A bstract Thethesisfirstreviewsthehistoryofparallel computation, analysesitscurrentsituationandpredictsitsdevelopment tendency, thus proves the significance of tarring out the research into designingandanalysinghighlyefficientparallelalgorithm.Following this,itintroudcesbrieflyseveralpopularcomputationmodelsonwhich thedesignofparallelalgorithm dependsaswellassomebasic conceptsabout parallelalgorithm. Then the thesis emphatically summarizesand goes furtherinto the methods and principals of designinghighlyefficientparallelalgorithms,includingproposingsome new methodsandprincipals,andthen itappliesthem tomanyresearch fieldsincludingsometopicsofchallengingsignificance, thisyields manynew valuableresultssuchashighly efficient parallel sorting algoritme,parallelalgorithms for numeric computations,parallel databasealgorithmsaswellasparallelartificial intelligence and knowledgeengineeringalgorithms. In addition, the thesis studies specially theparallelprocessingofDivide-and_Conquer,Backtracking andBranch-and-Bound,consequentlyproposesparallelBacktrackingand parallelBranch-and-bound whichare general algoritms for shared memoryMIMD computers.Italsoapplies them to the problems in artificialintelligence,knowledgeengneering and other fields, this