基于OpenCL的直方图生成算法优化方法研究

随着GPU计算能力及可编程性的不断增强,采用GPU作为通用加速器对应用程序进行性能加速已经成为提升程序性能的主要模式。直方图生成算法是计算机视觉的常用算法,在图像处理、模式识别、图像搜索等领域都有着广泛的应用。随着图像处理规模的扩大和实时性要求的提高,通过GPU提升直方图生成算法性能的需求也越来越强。在GPU计算平台关键优化方法和技术的基础上,完成了直方图生成算法在GPU计算平台上的实现及优化。实验结果表明,通过使用直方图备份、访存优化、数据本地化及规约优化等优化方法,直方图生成算法在AMD HD7850 GPU计算平台上的性能相对于优化前的版本达到了1.8~13.3倍的提升;相对于CPU版本,在不同数据规模下也达到了7.2~210.8倍的性能提升。     

面向存储层次设计优化的GPU程序性能分析

图形处理器凭借着比传统CPU更高的峰值性能和能效,以及日渐成熟的软件环境,逐渐成为构建异构并行系统的最流行的加速器之一。虽然GPU依靠轻量级线程的灵活切换来隐藏访存延迟,但其超高的并发度仍然给存储系统带来了很大压力,其性能的有效发挥受访存效率的强烈影响。因此GPU程序的访存行为分析及优化一直是GPU相关领域的研究热点,但很少有工作从体系结构的角度分析存储层次的设计对性能的影响。为了更好地指导GPU存储层次的设计和访存优化,从实验的角度详细地分析了GPU各存储层次对程序性能的影响,并总结出若干指导性的优化策略,为未来类似体系结构的存储层次设计和程序优化提供建议。     

面向申威异构架构的并行代码自动生成

异构架构逐渐成为高性能计算领域的主流架构,但相较于同构多核架构,其硬件结构及存储层次更为复杂,程序编写更为困难.先进的优化编译器可以协助程序开发人员实现更为高效的代码,降低程序开发复杂度.多面体编译模型通过抽象分析将程序抽象成空间多面体表示形式,能够将多种循环变换与硬件映射相结合,并面向特定体系结构生成相应的代码.设计实现了一个面向国产申威异构架构的并行代码自动生成系统,采用“源-源”编译模式,基于多面体编译模型实现.系统针对申威异构架构特点将程序计算过程进行硬件部署,同时实现数据传输与内存空间的自动管理.实验基于Polybench测试集中线性代数相关用例进行测试.结果表明,利用代码自动生成系统生成的异构并行代码能够在申威异构平台上正确运行,并能够有效发挥申威异构平台的性能,基于申威异构平台利用64线程加速计算的平均加速比达到了539.16倍.     

动态二进制翻译中数据预取优化研究*

动态优化是动态二进制翻译研究中一个十分重要的课题,数据预取优化能提高现代处理器体系结构应用程序性能。基于超级块(Superblock)的动态数据预取优化采用软件插桩方式收集应用程序的load访存延迟信息并构造Superblock;然后根据延迟信息以及Superblock数据流分析得出的寄存器定值引用关系,对延迟load指令进行预取优化。通过在龙芯DigitalBridge动态二进制翻译系统上实验验证,数据预取优化可以提高翻译后SPEC2000浮点测试程序代码的平均性能3.3%,开销远小于0.5%。     

申威众核处理器访存与通信融合编译优化

申威众核片上多级存储层次是缓解众核“访存墙”的重要结构.完全由软件管理的SPM结构和片上RMA通信机制给应用性能提升带来很多机会,但也给应用程序开发优化与移植提出了很大挑战.为充分挖掘片上存储层次特点提升应用程序性能,同时减轻用户编程优化负担,本文提出了一种多级存储层次访存与通信融合的编译优化方法.该方法首先设计了融合编译指示,将程序高层信息传递给编译器.其次构建了编译优化收益模型并设计了启发式循环优化方案迭代求解框架,并由编译器完成循环优化方案的求解和优化代码的变换.通过编译生成的DMA和RMA批量数据传输操作,将较低存储层次空间中高访问延迟的核心数据批量缓冲进低访问延迟的更高存储层次空间中.在三个典型测试用例上进行了优化实验测试与分析,结果表明本文所提出的优化在性能上与手工优化相当,较未优化版程序性能有显著提升.     

利用Java的多线程技术实现并行多任务的管理

多线程是编程社会中一个相当新的结构,它非常强大,可以提高程序的运行效率。Java虚拟机允许一个应用程序同时运行多个线程,Java编程环境和Runtime库最关键的一个特征就是多线程结构,并且Java是第一个在语言的核心中支持线程的编程语言。利用多线程编程技术,可以在Java中方便地实现任务的并行处理。限于篇幅,本文对于Java中与线程有关的类和接口的构造器和方法没有深入地讨论,演示程序中所有代码都有详尽的注释。     

面向X10的数据流程序编译优化算法

数据流编程作为一种编程模式已被广泛应用到各个领域.然而,多核体系结构的不同使得数据流程序在不同平台上移植困难.X10作为一种新型并行编程语言,为不同的多核体系结构提供了统一的并行计算环境.如何利用X10语言的特性来提高数据流程序的效率已成为目前研究工作的一大难点.本文设计并实现了一个面向X10的编译优化系统,该系统确立了三种优化算法:针对X10语言的代码生成优化减少了生成的X10代码量;针对同步数据流图的任务划分优化在负载均衡的基础上,避免了死锁的产生,同时减少了通信开销;针对底层硬件资源的通信优化在机器间通信、机器内部线程间通信、线程内部通信方面进行了区分和优化,减少了通信开销.实验结果表明,设计的三种编译优化算法都获得了较大的性能提升.     

TensorFlow中OpenCL核函数的实现与优化

目前,异构计算技术已经被广泛应用于人工智能领域,旨在利用以GPGPU为主的并行加速设备和CPU协同工作,更高效地完成大规模的并行计算.深度学习模型的构建、训练以及推理离不开机器学习框架的支持,但目前主流的机器学习框架基本仅支持CUDA异构编程模型.CUDA的私有性和封闭性导致机器学习框架严重依赖于英伟达GPGPU.众多其它厂商的硬件加速器,尤其是国产加速器难以充分发挥其在深度学习中的潜力.使用开源统一异构编程标准OpenCL代替私有的CUDA编程模型,是打破这一技术壁垒的有效方法.本文提出了TensorFlow中CUDA到OpenCL核函数的代码转换方案,总结整理了核函数转换的基本规则、典型难点问题的解决方法以及OpenCL核函数的性能优化等关键技术.本文首次完成了TensorFlow 2.2版本中135个OpenCL核函数的实现.经一系列测试验证,转换生成的135个OpenCL核函数能够在多种支持OpenCL标准的加速器上正确运行,优化后,近八成的OpenCL核函数在英伟达Tesla V100S上达到了与CUDA核函数相当的计算性能.测试结果验证了本文提出的CUDA到OpenCL核函...     

面向节点异构GPU集群的编程框架

基于异构GPU集群的主流编程方法是MPI与CUDA的混合编程或者其简单变形。因为对底层的集群架构不透明,程序员对GPU集群采用MPI与CUDA编写应用程序时需要人为考虑硬件计算资源,复杂度高、可移植性差。为此,基于数据流模型设计和实现面向节点异构GPU集群体系结构的新型编程框架分布式并行编程框架(DISPAR)。 DISPAR框架包含2个子系统：(1)代码转换系统StreamCC,是DISPAR源代码到MPI+CUDA代码的自动转换器。(2)任务分配系统StreamMAP,具有自动发现异构计算资源和任务自动映射功能的运行时系统。实验结果表明,该框架有效简化了GPU集群应用程序的编写,可高效地利用异构GPU集群的计算资源,且程序不依赖于硬件平台,可移植性较好。     

一种移动Agent数据保护机制的研究

1.研究背景移动Agent系统是一个分布式的计算平台,在移动A-gent系统中移动Agent是由代码、数据和控制信息(如线程状态)组成的一段可以自动迁移程序,该程序能自动执行计算任务,同时也可以与其它移动Agent通信进行协同计算。在移动Agent系统中,移动Agent可以在当前主机(Host)上暂停现有的计算,迁移到系统中其他的主机上并继续执行计算任务,实现计算的移动。     

基于OpenCL的连续数据无关访存密集型函数并行与优化研究

连续的数据无关是指计算目标矩阵连续的元素时使用的源矩阵元素之间没有关系且也为连续的,访存密集型是指函数的计算量较小,但是有大量的数据传输操作。在OpenCL框架下,以bitwise函数为例,研究和实现了连续数据无关访存密集型函数在GPU平台上的并行与优化。在考察向量化、线程组织方式和指令选择优化等多个优化角度在不同的GPU硬件平台上对性能的影响之后,实现了这个函数的跨平合性能移植。实验结果表明,在不考虑数据传输的前提下,优化后的函数与这个函数在OpenCV库中的CPU版本相比,在AMD HD 5850 GPU达到了平均40倍的性能加速比;在AMD HD 7970 GPU达到了平均90倍的性能加速比;在NVIDIA Tesla 02050 CPU上达到了平均60倍的性能加速比;同时,与这个函数在OpenCV库中的CUDA实现相比,在NVIDIA Tesla 02050平台上也达到了1.5倍的性能加速。     

基于GPU的压缩感知重构算法的设计与实现

针对大尺度压缩感知重构算法实时性应用的需要,探讨了基于图形处理器(GPU)的正交匹配追踪算法(OMP)的加速方法及实现。为降低中央处理器与GPU之间传输的高延迟,将整个OMP算法的迭代过程转移到GPU上并行执行。其中,在GPU端根据全局存储器的访问特点,改进CUDA程序使存储访问满足合并访问条件,降低访问延迟。同时,根据流多处理器(SM)的资源条件,增加SM中共享存储器的分配,通过改进线程访问算法来降低bank conflict,提高访存速度。在NVIDIA Tesla K20Xm GPU和Intel(R) E5-2650 CPU上进行了测试,结果表明,算法中耗时长的投影模块、更新权值模块分别可获得32和46倍的加速比,算法整体可获得34倍的加速比。     

Solving very large instances of the scheduling of independent tasks problem on the GPU

In this paper, we present two new parallel algorithms to solve large instances of the scheduling of independent tasks problem. First, we describe a parallel version of the Min–min heuristic. Second, we present GraphCell, an advanced parallel cellular genetic algorithm (CGA) for the GPU. Two new generic recombination operators that take advantage of the massive parallelism of the GPU are proposed for GraphCell. A speedup study shows the high performance of the parallel Min–min algorithm in the GPU versus several CPU versions of the algorithm (both sequential and parallel using multiple threads). GraphCell improves state-of-the-art solutions, especially for larger problems, and it provides an alternative to our GPU Min–min heuristic when more accurate solutions are needed, at the expense of an increased runtime.     

CPU/FPGA混合架构上的硬件线程加速方法

CPU/FPGA混合架构是可重构计算的普遍结构,为了简化混合架构上FPGA的使用,提出了一种硬件线程方法,并设计了硬件线程的执行机制,以硬件线程的方式使用可重构资源.同时,软硬件线程可以通过共享数据存储方式进行多线程并行执行,将程序中计算密集部分以FPGA上的硬件线程方式执行,而控制密集部分则以CPU上的软件线程方式执行.在Simics仿真软件模拟的混合架构平台上,对DES,MD5SUM和归并排序算法进行软硬件多线程改造后的实验结果表明,平均执行加速比达到了2.30,有效地发挥了CPU/FPGA混合架构的计算性能.     

Efficient data management for incoherent ray tracing

To obtain good performance on the GPU hardware, it is necessary to design algorithms to manage data, access memory under GPU memory hierarchy, and schedule more efficient threads. In this paper, we propose an efficient data management and task management designed for GPU based ray tracing. Due to the dynamic and uncertainty in ray tracing, we design data-management layer and task-management layer combined with fuzzy spatial analysis, use the two-level ray sorting and a ray bucket structure to reorganize ray data, then a warp's threads can be scheduled to access coherent geometry and nodes data, reduce memory bandwidth, and dispatch the data locally. We schedule tasks in data-driven execution according to coherent data, propose an adaptive ray compaction to eliminate inactive threads, maintain task efficiency of threads in a warp, and design two heuristics to decrease the compaction cost. On the basis of it, we also introduce a memory-optimized dynamic traversal management to reduce incoherent memory access, and avoid frequent sorting computation and compaction operations. Our experiments demonstrate all of these work combined can achieve good performance.     

High Level Data Structures for GPGPU Programming in a Statically Typed Language

To increase software performance, it is now common to use hardware accelerators. Currently, GPUs are the most widespread accelerators that can handle general computations. This requires to use GPGPU frameworks such as Cuda or OpenCL. Both are very low-level and make the benefit of GPGPU programming difficult to achieve. In particular, they require to write programs as a combination of two subprograms, and, to manually manage devices and memory transfers. This increases the complexity of the overall software design. The idea we develop in this paper is to guarantee expressiveness and safety for CPU and GPU computations and memory managements with high-level data-structures and static type-checking. In this paper, we present how statically typed languages, compilers and libraries help harness high level GPGPU programming. In particular, we show how we added high-level user-defined data structures to a GPGPU programming framework based on a statically typed programming language: OCaml. Thus, we describe the introduction of records and tagged unions shared between the host program and GPGPU kernels described via a domain specific language as well as a simple pattern matching control structure to manage them. Examples, practical tests and comparisons with state of the art tools, show that our solutions improve code design, productivity, and safety while providing a high level of performance.     

一种高效直方图生成算法在GPU上的实现

直方图生成算法(Histogram Generation)是一种顺序的非规则数据依赖的循环运算,已在许多领域被广泛应用。但是,由于非规则的内存访问,使得多线程对共享内存访问会产生很多存储体冲突(Bank Conflict),从而阻碍并行效率。如何在并行处理器平台,特别是当前最先进的图像处理单元(Graphic Processing Unit,GPU)实现高效的直方图生成算法是很有研究价值的。为了减少直方图生成过程中的存储体冲突,通过内存填充技术,将多线程的共享内存访问均匀地分散到各个存储体,可以大幅减少直方图生成算法在GPU上的内存访问延时。同时,通过提出有效可靠的近似最优配置搜索模型,可以指导用户配置GPU执行参数,以获得更高的性能。经实验验证,在实际应用中,改良后的算法比原有算法性能提高了42%～88%。     

LU分解和Laplace算法在GPU上的实现

随着图形处理器(GPU)性能的大幅度提升以及可编程性的发展,已经有许多算法成功地移植到GPU上.LU分解和Laplace算法是科学计算的核心,但计算量往往很大,由此提出了一种在GPU上加速计算的方法.使用Nvidia公司的统一计算设备架构(CUDA)编程模型实现这两个算法,通过对CPU与GPU进行任务划分,同时利用GP...     

Supporting real-world network-oriented mesoscopic traffic simulation on GPU

Mesoscopic traffic simulation is a promising technology for handling large-scale dynamic traffic assignment problems. Meanwhile, GPU has been a research hotspot in the last decade because of its massive parallel performance compared with CPU. Although several works deal with GPU-based parallel performance, few have addressed the issue of real-world network applications. Thus, the performance of GPU on realistic road networks is still not clear. In this paper, an ideal grid network and a realistic Singapore expressway network are implemented and compared. The former gets a speedup of 10.00 while the latter only get a speedup of 2.37. The two main reasons for this lower efficiency of a real network are the more complex data structure caused by network topology and fewer numbers of threads due to the scale of the expressway network. Future works need more effort to develop a system with better data structure and better designed concurrent threads.