多核机群系统上并行排序和选择算法研究

排序和选择是计算机科学中一个重要的基本问题，具有广阔的应用前景和重要的理论意义。多核技术是构造高效能计算机平台的有效手段。机群系统具有较好的性价比、可靠性、可扩展性、可管理性和应用支持性等优势，采用机群结构的并行计算机系统已成为绝对主流。在由多核处理器（CMP）数目不同、处理核数目不同的计算结点组成的多核机群系统上，对于给定的数据（任务），综合考虑处理核数、各级缓存以及主存大小、并行线程数、结点内CMP数、结点数以及结点的计算能力、通信能力和通信延迟等参数，采取优化结点内多核处理器之间、处理核之间通信与优化结点之间通信并重的方法，研究建立多核机群系统上最优/渐近最优的数据分配策略和任务调度模型；研究设计缓存高效、通信高效、加速比高、扩展性好、线程级并行的排序和选择算法，并运用MPI和OpenMP混合编程测试分析算法的实验性能。

提出动态适应节点具有不同计算、通信和存储能力的多核机群可分负载多轮调度模型和多级缓存数据分配方法；将一小部分负载发送到各个从节点探测系统参数，依据从节点返回信息的时间来估算各节点的核心数目、通信速率和主存容量等参数，利用探测到的参数来分发余下的负载，提出了系统参数未知的多核异构机群上带返回信息的可分负载多轮调度算法。针对Multisets特殊序列，给出极值的极值思想，利用筛选原理在递归过程中不断挑选出具有相同关键字值的数据，并行归并关键字相同的那些数据，提出非周期性多轮分配策略，设计了多核系统上存储和通信高效的Multisets排序并行算法。分析抽样方式、抽样规模、核心数、线程数、缓存大小和数据分布对并行排序性能的影响，采用线程绑定和并行搜索方法，设计实现了多核系统上缓存高效的并行抽样排序算法。利用整数可以划分成多段任意比特位的特性，依据整数的取值范围，自适应地求出映射基数，使得既能满足排序所需的映射桶数，确保L2 Cache有足够空间存储被映射的数据，避免缓存缺失，同时使映射轮数达到最少，高效地并行排序整数序列；采取主节点两轮分发数据与接收有序子序列的方法，设计实现了多核异构机群上通信高效的整数序列并行排序算法。给出变形的分组思想以使得分组筛选能有效利用多级缓存机制，提出多级存储并行划分数据、并行筛选选择元素方法，设计了多核系统上缓存高效的(m,n)-选择并行算法。建立k个有序序列的多级存储划分模型，运用SIMD指令、数据预取和线程绑定技术，提出高效的线程级与数据级并行多路归并算法。提出主节点并发发送数据给从节点的共享L3 cache多CMP节点异构机群可分负载多轮调度模型，设计实现高效的k-选择并行算法。采取将匹配多级缓存容量的负载块划分成头部分、主部分和尾部分的方法，设计处理核心出现永久与瞬态故障时的多核系统容错调度算法。提出二次归并和双线程容错查找方法，设计实现错误模型无关的多核系统并行归并容错算法。给出了多核异构机群上计算密集型应用并行程序性能优化方法。以非递归方式调度矩阵基本块，按基本块连续存储，提出延迟隐藏模型，设计多核系统上高效的矩阵乘积并行算法。利用数据局部性原理，采用多级分块和循环并行优化方法，设计实现多核系统上两序列公共元素并行查找算法。