【摘 要】
:
不规则任务指分解、映射以及运行过程中,在数据分割、流程控制、内存访问等方面表现出不规则性质的任务。不规则任务在并行平台上执行时,会引发控制流程分歧、负载不均衡、数据访问局部性差等问题,导致系统资源利用率下降。为了追求高性能和低成本,大量不规则任务需要在CPU-GPU异构平台上运行。因此研究不规则任务在CPU-GPU平台上的实现及优化,有着现实意义和价值。本文研究了动态计算量和数据划分不均匀类型的不
论文部分内容阅读
不规则任务指分解、映射以及运行过程中,在数据分割、流程控制、内存访问等方面表现出不规则性质的任务。不规则任务在并行平台上执行时,会引发控制流程分歧、负载不均衡、数据访问局部性差等问题,导致系统资源利用率下降。为了追求高性能和低成本,大量不规则任务需要在CPU-GPU异构平台上运行。因此研究不规则任务在CPU-GPU平台上的实现及优化,有着现实意义和价值。本文研究了动态计算量和数据划分不均匀类型的不规则任务在CPU-GPU平台上的并行分解、映射与运行过程。从并行算法设计和硬件平台改进的角度出发,采用线程任务合并、动态并行、流水线结构改进等手段,优化了不规则任务求解算法的性能。本文主要研究内容如下:(1)研究了具有动态计算量的不规则任务在CPU-GPU异构平台上的实现及优化。以图像区域填充算法为例,提出了基于连通图原理和并查集算法的多种子、多堆栈并行填充方案,采用合理的任务划分粒度对填充区域进行随机分割,通过线程间竞争和协作,完成整个区域的填充。针对并行算法中的填充和合并两个关键步骤,实现和对比了在CPU上的多线程并行方案与GPU上的CUDA方案;综合衡量这些方案的成本、收益以及数据传输代价,选择最佳方案组合为完整算法。对于批量填充任务,设计了 CPU-GPU两级流水线模型来进一步提升性能。实验证明,并行后算法在实际场景中具备实时性,针对该类型不规则任务的优化取得了明显收益。(2)在单节点CPU-GPU平台上,研究了数据划分不均匀类型不规则任务的并行实现。针对分解后子任务计算量存在较大差异的N皇后问题变体2候选解评价算法,在CPU和GPU上采用了改变任务分解粒度、子任务组合、CUDA动态并行等手段,探索了数据划分不均匀任务的优化方法,并通过模拟退火算法证实了优化手段的有效性。基于上述研究,在含有多个CPU-GPU节点的集群上,探索了 GPU集群上节点间和节点内任务划分和映射的方法。结合MPI技术构建了岛模型-主从模型的两级并行遗传算法用于求解N皇后问题变体2。与目前同类型的算法相比,本文算法不但提升了求解规模,还加快了求解速度。(3)探索了通过改进GPU流水线执行模型来提升不规则任务执行效率的方法。基于GPGPU-Sim模拟器观察了不规则任务运行时的缓存命中率、流水线空闲周期等微观指标,发现了 GPU执行过程中的流水线周期性停顿问题,并揭示问题产生原因是GPU中流式多处理器的指令缓存发生冷缺失。依据容量对Rodinia、ISPASS-2009、CUDA SDK中31个程序所包含的86个Kernel进行了分类,分析了 Kernel容量同缺失率的关系,设计了适合GPU执行模型的指令缓存预取机制。实验证明,预取机制可有效减少指令缓存冷缺失造成的访存长延迟和流水线停顿现象,相比基准模型提升了平均12.17%的性能。同大缓存方案相比,该机制具有硬件代价低、受益程序多的优势。
其他文献
本学位论文主要研究了类分数布朗运动高斯过程泛函的极限定理及其驱动随机微分方程的参数估计等问题.全文共分为四章.在第一章中,我们介绍了分数布朗运动、次分数布朗运动和双分数布朗运动这些类分数布朗运动高斯过程的基本概念,并给出了局部非确定性、维纳chaos分解和Malliavin分析等研究技术,还分析了类分数布朗运动高斯过程泛函的极限定理及其驱动随机微分方程参数估计的研究现状.在第二章中,我们研究了两个
本论文主要研究分形几何和测度论中的一些问题,这些问题包括一类具有完全重叠结构的自相似集合的唯一码集的维数及作用在该集合上的一些算术运算,填充测度的两种不同构造方法的等价性。首先,我们得到了一类具有完全重叠结构的自相似集合的唯一码集(Univoque set)U的 Hausdorff 维数公式。令A是由一些自相似集合所组成的集合族,A中的元素K为由满足下列条件(一)(二)(三)(四)的迭代函数系统(
随着特高压直流输电和可再生能源并网的纵深发展,因直流闭锁故障引发的大功率缺失导致受端电网低频风险陡然增加,由于新能源发电挤占了常规机组上网空间造成系统频率控制能力持续下降。两方面因素的相互作用,致使电力系统频率稳定态势愈发严峻、频率响应矛盾日益突出。若依然沿用静态观点审视频率响应运行,其结果简单粗略、容易误判。以动态为核心,聚焦电力系统运行所涉及的建模、监视、控制和评价环节,本文开展了动态频率响应
以地铁站为代表的城市地下结构是城市生命线工程的重要组成部分。当城市进行地下结构工程的建设过程中,地下结构物的选址选线有时将不可避免的穿越可液化土层。可液化场地地下结构在遭受强震作用下,土层的液化将对地下结构产生极大的破坏作用,包括地下结构因地基液化而导致的结构上浮、震后地基的不均匀沉降等。目前现有的预测方法大多是关于预测地震液化,而且现有方法的适用性有限、预测的精度不高。另外对于场地地震液化灾害的
密闭金属容器可以保证内部物体与外部环境相互不受影响,因此在许多条件严苛的环境中得到了专门应用。隔金属壁板实现非电气接触式电能传输(Contactless power transfer,CPT)是一项挑战性很强的研究课题,这是由于金属材料具有电磁屏蔽效应,电磁能量难以穿透金属壁板。但是,超声波却能在金属中有效传播。鉴于此种事实,本文研究了以超声波为间接能量且隔金属板传输电能的非电气接触式电能传输技术
群桩是一种主要的海上建筑物基础结构形式。群桩中桩之间的相互影响会使得不同桩上的波浪力产生差异,人们通常以群桩系数来描述这种差异。相关规范中给出了基于单向波作用下三桩并列和串列群桩的群桩系数。而事实上,群桩结构往往是由多桩组成的,同时海浪是多向的不规则波浪,波浪的方向分布对于波浪与海洋工程建筑物的作用具有重要的影响,因此,探究多向不规则波作用下多桩群桩结构的波浪力特性,不仅具有重要的理论价值,而且可
在建设“海洋强国”的时代背景下,我国港口、海岸与海洋工程迎来了巨大发展。随着海洋油气资源的勘探、开发和利用以及近海风机、海洋平台等海工构筑物的建造,海床稳定是确保施工安全和保障海洋工程长期服役的必要前提,海床稳定性评价方法逐渐成为岩土工程领域的研究热点。在海床稳定性评估过程中会涉及诸多不确定性因素,如沉积物参数的空间变异性以及外部荷载的随机性,而传统的确定性分析方法无法对这些不确定性进行定量表征。
全球化、信息化和网络化加快了国际资本的开放性和流动性,对外直接投资(OFDI)成为企业在全球市场配置资本的重要手段。截至2018年12月,中国已在全球设立境外企业4.3万家,投资范围覆盖全球80%以上的国家或地区,OFDI规模(流量)从2007年的265.1亿美元增长至1430.4亿美元,年均增长速度高达16.6%。与此同时,全球经济也处在深度调整之中,各国政府纷纷出台了多项经济政策刺激经济复苏,
高纬度沿海地区的冬季气温较低,沿岸表层海水与大气之间的温差相对较大,由于潮汐的周期性运动,近海桥梁的钢筋混凝土(Reinforced concrete,以下简称RC)桥墩长期遭受海水冻融循环作用的影响。结合现有的研究可知,混凝土材料在高盐环境下耐久性能和力学性能会显著地降低。混凝土材料耐久性能的降低会缩短桥梁的寿命,混凝土材料力学性能的降低会影响桥梁的抗震性能。目前为止,针对混凝土材料在海水冻融循
近年来,安全博弈模型已经广泛应用于城市基础设施、野生动植物保护以及网络安全等领域。安保部门的最优决策可通过求解博弈模型的均衡解得到。然而,复杂的现实生活场景往往需要建立为不同形式的安全博弈模型,从而求解不同形式的均衡解。为了研究不同场景安全博弈中的均衡解,使其适用于解决更多现实场景中的安保部门资源分配问题,具体地,本文做了如下工作:(1)研究了单防御者vs单攻击者安全博弈场景中的强斯塔克尔伯格均衡