课题基金基金详情
多核机群系统上并行排序和选择算法研究
结题报告
批准号:
60963001
项目类别:
地区科学基金项目
资助金额:
22.0 万元
负责人:
钟诚
依托单位:
学科分类:
F0204.计算机系统结构与硬件技术
结题年份:
2012
批准年份:
2009
项目状态:
已结题
项目参与者:
陈宁江、刘峻、杨锋、尹梦晓、黄毅然、瞿增燕、李霞、黄华林、鹿中龙
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
客服二维码
微信扫码咨询
中文摘要
排序和选择是计算机科学中一个重要的基本问题,具有广阔的应用前景和重要的理论意义。多核技术是构造高效能计算机平台的有效手段。机群系统具有较好的性价比、可靠性、可扩展性、可管理性和应用支持性等优势,采用机群结构的并行计算机系统已成为绝对主流。在由多核处理器(CMP)数目不同、处理核数目不同的计算结点组成的多核机群系统上,对于给定的数据(任务),综合考虑处理核数、各级缓存以及主存大小、并行线程数、结点内CMP数、结点数以及结点的计算能力、通信能力和通信延迟等参数,采取优化结点内多核处理器之间、处理核之间通信与优化结点之间通信并重的方法,研究建立多核机群系统上最优/渐近最优的数据分配策略和任务调度模型;研究设计缓存高效、通信高效、加速比高、扩展性好、线程级并行的排序和选择算法,并运用MPI和OpenMP混合编程测试分析算法的实验性能。
英文摘要
提出动态适应节点具有不同计算、通信和存储能力的多核机群可分负载多轮调度模型和多级缓存数据分配方法;将一小部分负载发送到各个从节点探测系统参数,依据从节点返回信息的时间来估算各节点的核心数目、通信速率和主存容量等参数,利用探测到的参数来分发余下的负载,提出了系统参数未知的多核异构机群上带返回信息的可分负载多轮调度算法。针对Multisets特殊序列,给出极值的极值思想,利用筛选原理在递归过程中不断挑选出具有相同关键字值的数据,并行归并关键字相同的那些数据,提出非周期性多轮分配策略,设计了多核系统上存储和通信高效的Multisets排序并行算法。分析抽样方式、抽样规模、核心数、线程数、缓存大小和数据分布对并行排序性能的影响,采用线程绑定和并行搜索方法,设计实现了多核系统上缓存高效的并行抽样排序算法。利用整数可以划分成多段任意比特位的特性,依据整数的取值范围,自适应地求出映射基数,使得既能满足排序所需的映射桶数,确保L2 Cache有足够空间存储被映射的数据,避免缓存缺失,同时使映射轮数达到最少,高效地并行排序整数序列;采取主节点两轮分发数据与接收有序子序列的方法,设计实现了多核异构机群上通信高效的整数序列并行排序算法。给出变形的分组思想以使得分组筛选能有效利用多级缓存机制,提出多级存储并行划分数据、并行筛选选择元素方法,设计了多核系统上缓存高效的(m,n)-选择并行算法。建立k个有序序列的多级存储划分模型,运用SIMD指令、数据预取和线程绑定技术,提出高效的线程级与数据级并行多路归并算法。提出主节点并发发送数据给从节点的共享L3 cache多CMP节点异构机群可分负载多轮调度模型,设计实现高效的k-选择并行算法。采取将匹配多级缓存容量的负载块划分成头部分、主部分和尾部分的方法,设计处理核心出现永久与瞬态故障时的多核系统容错调度算法。提出二次归并和双线程容错查找方法,设计实现错误模型无关的多核系统并行归并容错算法。给出了多核异构机群上计算密集型应用并行程序性能优化方法。以非递归方式调度矩阵基本块,按基本块连续存储,提出延迟隐藏模型,设计多核系统上高效的矩阵乘积并行算法。利用数据局部性原理,采用多级分块和循环并行优化方法,设计实现多核系统上两序列公共元素并行查找算法。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
DOI:--
发表时间:--
期刊:Proceedings of the Second International Symposium on Parallel Architectures, Algorithms and Programming. University of Science and Technology of China Press
影响因子:--
作者:Hualin Huang(黄华林);Cheng Zhong(钟诚);Zhonglong Lu(鹿中龙)
通讯作者:Zhonglong Lu(鹿中龙)
DOI:--
发表时间:--
期刊:合肥工业大学学报(自然科学版)
影响因子:--
作者:蔡德霞;钟诚;韦兴柳;林孔升
通讯作者:林孔升
Efficient and Scalable Thread-level Parallel Algorithms for Sorting Multisets on Multi-core Systems
用于在多核系统上排序多重集的高效且可扩展的线程级并行算法
DOI:10.4304/jcp.7.1.30-41
发表时间:2012
期刊:Journal of Computers
影响因子:--
作者:Cheng Zhong(钟诚);Zeng-Yan Qu(瞿增燕);Feng Yang(杨锋);Meng-Xiao Yin(尹梦晓);Xia Li(李霞)
通讯作者:Xia Li(李霞)
Scheduling Divisible Loads with Return Messages on Multi-core Heterogeneous Clusters with Unknown System Parameters
系统参数未知的多核异构集群上带返回消息的可分割负载调度
DOI:10.4156/ijact.vol4.issue7.12
发表时间:2012-04
期刊:International Journal of Advancements in Computing Technology
影响因子:--
作者:ZHONG Cheng(钟诚);LI Xia(李霞);YANG Feng(杨锋);LIU Jun(刘峻);YIN Meng-xiao(尹梦晓);HUANG Yi-ran(黄毅然)
通讯作者:HUANG Yi-ran(黄毅然)
DOI:10.1109/paap.2010.31
发表时间:2010-12
期刊:Proceedings of 3rd International on Parallel Architectures, Algorithms and Programming, IEEE Computer Society Press
影响因子:--
作者:Cheng Zhong(钟诚);Zeng-yan Qu(瞿增燕);Feng Yang(杨锋);Meng-xiao Yin(尹梦晓)
通讯作者:Meng-xiao Yin(尹梦晓)
多源生化数据的药物作用预测并行算法研究
  • 批准号:
    62362004
  • 项目类别:
    地区科学基金项目
  • 资助金额:
    33万元
  • 批准年份:
    2023
  • 负责人:
    钟诚
  • 依托单位:
含有Indel和结构变异错误的生物序列比对并行算法
  • 批准号:
    61962004
  • 项目类别:
    地区科学基金项目
  • 资助金额:
    38.0万元
  • 批准年份:
    2019
  • 负责人:
    钟诚
  • 依托单位:
CPU和GPU混合体系结构上生物网络比对并行算法研究
  • 批准号:
    61462005
  • 项目类别:
    地区科学基金项目
  • 资助金额:
    45.0万元
  • 批准年份:
    2014
  • 负责人:
    钟诚
  • 依托单位:
异构机群系统上近似串匹配并行算法研究与实现
  • 批准号:
    60563003
  • 项目类别:
    地区科学基金项目
  • 资助金额:
    22.0万元
  • 批准年份:
    2005
  • 负责人:
    钟诚
  • 依托单位:
牛瘤胃液的物理学,生物学和生物化学指标的分析
  • 批准号:
    38970575
  • 项目类别:
    面上项目
  • 资助金额:
    3.5万元
  • 批准年份:
    1989
  • 负责人:
    钟诚
  • 依托单位:
国内基金
海外基金