Optimization Techniques for GPU-Based Parallel Programming Models in High-Performance Computing

This study embarks on a comprehensive examination of optimization techniques within GPU-based parallel programming models,pivotal for advancing high-performance computing(HPC).Emphasizing the transition of GPUs from graphic-centric processors to versatile computing units,it delves into the nuanced optimization of memory access,thread management,algorithmic design,and data structures.These optimizations are critical for exploiting the parallel processing capabilities of GPUs,addressingboth the theoretical frameworks and practical implementations.By integrating advanced strategies such as memory coalescing,dynamic scheduling,and parallel algorithmic transformations,this research aims to significantly elevate computational efficiency and throughput.The findings underscore the potential of optimized GPU programming to revolutionize computational tasks across various domains,highlighting a pathway towards achieving unparalleled processing power and efficiency in HPC environments.The paper not only contributes to the academic discourse on GPU optimization but also provides actionable insights for developers,fostering advancements in computational sciences and technology.

Scheduling Step-Deteriorating Jobs on Parallel Machines by Mixed Integer Programming

Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.

The parallel 3D magnetotelluric forward modeling algorithm

The workload of the 3D magnetotelluric forward modeling algorithm is so large that the traditional serial algorithm costs an extremely large compute time. However, the 3D forward modeling algorithm can process the data in the frequency domain, which is very suitable for parallel computation. With the advantage of MPI and based on an analysis of the flow of the 3D magnetotelluric serial forward algorithm, we suggest the idea of parallel computation and apply it. Three theoretical models are tested and the execution efficiency is compared in different situations. The results indicate that the parallel 3D forward modeling computation is correct and the efficiency is greatly improved. This method is suitable for large size geophysical computations.

基于Map-Reduce的自适应双语短语挖掘系统

对于跨语言信息检索,统计翻译等应用,双语短语都是极其重要的资源.提出了基于自适应模式的双语短语挖掘算法,该算法可以自动的学习当前Web页面的翻译模式,然后利用学习到的模式抽取当前页面中的双语短语.同时,将自适应双语短语挖掘算法与Map-Reduce并行编程模型融合起来,大大提高了系统的运行效率,并且通过实验验证了该方法的有效性.

Parallel Machine Scheduling Models with Fuzzy Parameters and Precedence Constraints: A Credibility Approach

A method for modeling the parallel machine scheduling problems with fuzzy parameters and precedence constraints based on credibility measure is provided. For the given n jobs to be processed on m machines, it is assumed that the processing times and the due dates are nonnegative fuzzy numbers and all the weights are positive, crisp numbers. Based on credibility measure, three parallel machine scheduling problems and a goal-programming model are formulated. Feasible schedules are evaluated not only by their objective values but also by the credibility degree of satisfaction with their precedence constraints. The genetic algorithm is utilized to find the best solutions in a short period of time. An illustrative numerical example is also given. Simulation results show that the proposed models are effective, which can deal with the parallel machine scheduling problems with fuzzy parameters and precedence constraints based on credibility measure.

Parallel Implementations of Modeling Dynamical Systems by Using System of Ordinary Differential Equations

First, an asynchronous distributed parallel evolutionary modeling algorithm (PEMA) for building the model of system of ordinary differential equations for dynamical systems is proposed in this paper. Then a series of parallel experiments have been conducted to systematically test the influence of some important parallel control parameters on the performance of the algorithm. A lot of experimental results are obtained and we make some analysis and explanations to them.

超大规模数据处理中并行计算技术的应用研究

随着人工智能和大数据时代的到来,超大规模数据处理成了一个重要的研究领域。该文主要探讨并行计算技术在超大规模数据处理中的应用,首先详细阐述并行计算和超大规模数据处理的基本理论与概念,特别是并行计算的编程模型与工具,最后通过分析并行计算在搜索引擎、气象预报和金融分析等中的实际案例,阐述并行计算技术在超大规模数据处理中的实际应用。

任务并行编程模型下排列熵算法的并行实现

排列熵算法随着嵌入维数的增大,运算规模将会呈平方级数增大,计算时效性问题突出,亟待解决。为此,提出一种基于任务并行编程模型的线程级并行方法,通过任务并行运行系统(StarPU)将密集型计算划分为多个独立的任务,再由调度器将任务调度到不同的CPU上执行,实现排列熵算法的并行化。基于StarPU的排列熵并行算法与串行程序相比较,加速比为23.79倍,相较于OpenMP(一种用于共享内存并行系统的并行计算方案),在分配28个线程时,加速比为1.17倍,结果表明该方法能够有效实现排列熵算法的加速执行。

面向国产异构众核系统的Parallel C语言设计与实现

异构众核架构具有超高的性能功耗比,已成为超级计算机体系结构的重要发展方向.但众核系统更为复杂的并行层次和存储层次,给编程和优化带来了极大的挑战.因此,研究面向众核系统的并行编程技术,对于降低国产众核系统并行应用的编程难度、提升并行程序的性能都具有重要的意义.提出统一架构的多模式并行编程模型,包括异构融合的加速运算模型和按同构方式编程的自主运算模型,根据编程模型设计了Parallel C语言,能够有效地描述国产众核系统的异构并行性.与其他众核系统上MPI+X的使用模式相比,编程和系统优化都具有全局视角,在多级局部性描述、单边消息、兼容已有多核应用等方面具有特色;基于Open64构建了Parallel C编译系统,全面支持加速运算模型和自主运算模型,提出并实现了数据布局与自动DMA、编译指导的线程代理和拓扑位置感知的集合通信等优化.Micro Benchmark和实际应用在神威太湖之光计算机系统上的测试数据结果表明:Parallel C语言和编译系统具有良好的性能和可扩展性,能够有效支撑大型应用.

一类加工需要额外资源的平行机调度问题的算法设计

给出了一类加工需要额外资源的平行机调度问题的精确算法。针对在平行机上加工的工件,除需要机器资源外,还需要一个单位额外资源的问题,考虑额外资源的种类和数量有限,以给出问题的最优调度使工件的完工时间最小为目标。该问题源于地球观测卫星的数据下载,在智能制造和信息处理等领域亦有广泛应用。给出了该问题的整数规划模型、最优解下界和分支定界算法;给出了一种有效的分支策略以避免重复分支,设计了相应的定界方法以提高算法的收敛速度。通过小规模实例和大量的数值仿真实验,验证了算法的正确性和在不同参数配置下的有效性。

甩挂运输中牵引车与挂车数量配置优化仿真

牵引车与挂车数量合理配置是道路甩挂运输中的重要内容,对提高牵引车使用效率、降低车辆的购置费用具有重要意义。以牵引车购置费用、牵引车运行费用以及牵引车等待时间费用最小为目标,考虑甩挂运输任务时间窗约束和牵引车运行径路约束,构建了上述问题的数学规划模型。针对牵引车与挂车数量配比问题的组合爆炸特点,设计了结合模拟退火邻域搜索策略的并行蚁群搜索算法。最后以郑州市某个物流企业进行实例分析,结果表明所提方法能够在较短时间内获得满意解,有效地减少了整个甩挂运输系统的综合成本。

新型电力系统电磁暂态加速仿真技术

为解决新型电力系统电磁暂态仿真时由于系统拓扑结构复杂、电力电子开关器件较多以及仿真机单核计算能力不足导致的仿真效率低下、仿真难度大等问题,文中采用理想变压器模型分割算法将大规模新型电力系统模型分割成若干子系统,实现了大系统的解耦和降阶,有效减少了仿真时整个系统作为一个状态空间系统矩阵的运算量。为进一步减轻单个处理器的计算负担,利用CPU(Central Processing Unit)多核并行技术设计一款在裸机环境下高效并行运算的加速仿真平台UREP300。将分割后的模型载入UREP300进行加速仿真实验,同时与基于MATLAB/Simulink的原模型离线仿真进行对比。实验结果表明,融合理想变压器模型分割与多核并行运行的加速仿真技术能够在保障仿真精度的同时将仿真速度提升至原来的586倍,可显著提高仿真效率,适用于大规模新型电力系统的仿真工作。

Programming bare-metal accelerators with heterogeneous threading models:a case study of Matrix-3000

As the hardware industry moves toward using specialized heterogeneous many-core processors to avoid the effects of the power wall,software developers are finding it hard to deal with the complexity of these systems.In this paper,we share our experience of developing a programming model and its supporting compiler and libraries for Matrix-3000,which is designed for next-generation exascale supercomputers but has a complex memory hierarchy and processor organization.To assist its software development,we have developed a software stack from scratch that includes a low-level programming interface and a high-level OpenCL compiler.Our low-level programming model offers native programming support for using the bare-metal accelerators of Matrix-3000,while the high-level model allows programmers to use the OpenCL programming standard.We detail our design choices and highlight the lessons learned from developing system software to enable the programming of bare-metal accelerators.Our programming models have been deployed in the production environment of an exascale prototype system.

基于并行计算的电力系统状态估计算法分析

阐述通过引入OpenMP和CUDA并行计算编程模型和框架,能够充分利用多核处理器和GPU硬件资源,并行计算的电力系统状态估计算法大幅度提升计算速度,确保电网状态的评估准确度。

A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem

In this paper, we propose a multi-criteria machine-schedules decision making method that can be applied to a produc-tion environment involving several unrelated parallel machines and we will focus on three objectives: minimizing makespan, total flow time, and total number of tardy jobs. The decision making method consists of three phases. In the first phase, a mathematical model of a single machine scheduling problem, of which the objective is a weighted sum of the three objectives, is constructed. Such a model will be repeatedly solved by the CPLEX in the proposed Multi-Objective Simulated Annealing (MOSA) algorithm. In the second phase, the MOSA that integrates job clustering method, job group scheduling method, and job group – machine assignment method, is employed to obtain a set of non-dominated group schedules. During this phase, CPLEX software and the bipartite weighted matching algorithm are used repeatedly as parts of the MOSA algorithm. In the last phase, the technique of data envelopment analysis is applied to determine the most preferable schedule. A practical example is then presented in order to demonstrate the applicability of the proposed decision making method.

基于模型驱动的分治并行函数式程序生成及自动验证

并行计算作为人工智能发展的动力,使得并行算法的可解释性和安全性成为人工智能领域重要研究方向。形式化方法以数理逻辑为基础,已经成为复杂安全苛求系统可信构建的重要方法,而函数式编程则在算法领域中具有更强的数学表达性。本文旨在提出一种基于模型驱动的分治并行函数式程序生成及自动验证方法,融合形式化方法,以解决目前分治并行程序生成和验证中缺乏可解释性、易错、低可信度等问题。首先,采用分划递推法和循环不变式等新策略推导出串行算法;然后,利用辅助函数和算法连接函数将其提升为并行算法,并使用我们提出的并行算法设计语言Radl+进行描述;进而,采用同态定理验证框架在Isabelle中验证算法连接函数满足同态定理,即提升后的算法可并行化;最后,提出了Radl+→Haskell转换规则,设计了“Radl+→Haskell并行程序生成系统”软件原型。实验结果表明,本文能够生成和验证一系列算法的并行函数式程序,并且能够产生良好的加速比。本文方法不仅具有一定的可解释性,而且自动验证减少了传统手工验证易错性和繁琐的工作量,保证算法正确性和提高安全性,对大幅度提升高可信并行函数式程序的开发效率具有重要意义。

面向国产高性能众核处理器的编程模型

在国产高性能众核处理器上编程时,需要直接使用最底层的接口开发软件,这使编程和调试非常困难;并且各自平台的高性能软件编程模型较为基础,计算软件不能通用,造成了重复性开发。针对以上问题,实现了通用编程模型以及所对应的支撑库:一方面基于消息队列机制开发国产高性能众核处理器的线程级并行机制;另一方面基于单指令多数据流(SIMD)编程模型开发从核上的数据级并行性。首先,对国产高性能众核处理器体系结构进行抽象;其次,设计模型的消息队列机制,并为程序员提供一套异构并行编程接口,如系统参数接口、从核线程控制接口、消息队列接口、SIMD抽象接口;最后,在上述基础上形成全新的高性能计算软件开发模型和方法,方便用户开发基于国产高性能众核处理器的并行计算软件。性能传输测试结果表明,在国产众核处理器上,当启动核数较少时,所提模型的传输带宽普遍达到了峰值直接内存访问(DMA)带宽的90%;当启动的核数较多时,消息队列模型的传输带宽普遍达到了峰值DMA带宽的70%。在矩阵乘法实验中,与系统原语传输矩阵并计算的性能相比,所提模型的性能达到前者的90%;在口令猜测系统中,所提模型的代码性能与直接使用最底层的接口开发的代码性能基本持平。所提通用编程模型和支撑框架使高性能计算(HPC)软件开发更简易,并且具有更好的可移植性,可为促进国产自主HPC软件研发提供帮助。

基于SYCL的多相流LBM模拟跨平台异构并行计算研究

异构并行体系结构是当前高性能计算的重要技术趋势。由于各种异构平台通常支持不同的编程模型,跨平台性能可移植异构并行应用开发非常困难。SYCL是一个基于C++语言的单源跨平台并行编程开放标准。目前针对SYCL的研究主要集中于与其他并行编程模型的性能比较,对SYCL中提供的不同并行内核实现及其性能优化研究得较少。针对这一现状,基于SYCL编程模型对开源多相流数值模拟软件openLBMmflow实现跨平台异构并行模拟,通过对比基础并行版本、细粒度调优的ND-range并行版本以及计算到工作项多对一映射方法,系统总结了SYCL并行应用的性能优化方法。测试结果表明,在Intel Xeon Platinum 9242 CPU以及NVIDIA Tesla V100 GPU上,相比优化后的OpenMP并行实现,在不需要额外调优的情况下,基础并行版本在CPU上获得了2.91的加速比,表明了SYCL的开箱即用性能具备一定优势。以基础并行版本为基准,ND-range并行版本通过改变工作组大小及形状,在CPU与GPU上分别取得了最高1.45以及2.23的加速比。通过优化计算到工作项的多对一映射改变每个工作项处理的格子数量以及形状,与基础并行版本相比,在CPU与GPU上分别取得了最高1.57以及1.34的加速比。结果表明,SYCL并行应用在CPU上更适合采用计算到工作项多对一映射的优化方法,在GPU上更适合采用ND-range并行内核,以提高性能。

申威处理器上数据流运行时系统的设计与实现

我国自主研发的新一代神威异构众核计算平台主要采用athread异构编程方法,athread异构编程属于大同步并行模型,难以充分挖掘程序中的细粒度并行性,其采用的同步方式难以实现众核上的任务负载均衡。数据流并行编程模型因其天然并行性、点对点同步的特点能够很好地解决上述问题。基于Codelet程序执行模型和申威主从核架构特点,设计并实现面向申威处理器的数据流运行时系统swTasklet,通过对Codelet功能的进一步细化和对Codelet机器模型到主从核的映射,避免从核阵列上的同步操作,减少同步开销;由主核完成从核计算任务的调度分配,将计算和同步操作分离,保证运行时系统可以和从核计算库的共用。实验以NPB LU程序和向量-向量加作为测试用例,采用相同的优化方法分别对swTasklet和athread实现进行并行化。实验结果表明:在规模较大情况下,LU程序的swTasklet实现版本比athread版本快16%,向量-向量加swTasklet实现版本比athread版本快1倍;使用swTasklet实现的LU并行版本较主核本取得了平均8倍以上的加速,而向量-向量加swTasklet版本较主核版本取得30倍左右的加速。