swLLVM: 面向神威新一代超级计算机的优化编译器

异构众核架构具有超高的能效比, 已成为超级计算机体系结构的重要发展方向. 然而, 异构系统的复杂性给应用开发和优化提出了更高要求, 其在发展过程中面临好用性和可编程性等众多技术挑战. 我国自主研制的神威新一代超级计算机采用了国产申威异构众核处理器SW26010Pro. 为了发挥新一代众核处理器的性能优势, 支撑新兴科学计算应用的开发和优化, 设计并实现面向SW26010Pro平台的优化编译器swLLVM. 该编译器支持Athread和SDAA双模态异构编程模型, 提供多级存储层次描述及向量操作扩展, 并且针对SW26010Pro架构特点实现控制流向量化、基于代价的节点合并以及针对多级存储层次的编译优化. 测试结果表明, 所设计并实现的编译优化效果显著, 其中, 控制流向量化和节点合并优化的平均加速比分别为1.23和1.11, 而访存相关优化最高可获得2.49倍的性能提升. 最后, 使用SPEC CPU2006标准测试集从多个维度对swLLVM进行了综合评估, 相较于SWGCC的相同优化级别, swLLVM整型课题性能平均下降0.12%, 浮点型课题性能平均提升9.04%, 整体性能平均提升5.25%, 编译速度平均提升79.1%, 代码尺寸平均减少1.15%.     

分块内存的数据分布优化

为了提高访存效率,提供可以与计算流水线并行执行的多个独立的访存流水线,魂芯DSP片上存储器设计时采用分块内存结构,并在核内提供多个独立的地址生成单元用于访存操作.针对分块内存的结构特点,编译器对程序中的存储访问构建关于变量的冲突图,对分块内存进行存储块分配,优化数据在分块内存的分布.以数据在分块内存的优化分布为基础,指导程序中访存操作在地址生成单元的优化分配,使得编译器生成的代码可以最大程度地挖掘程序中数据访问的并行性.实验表明,基于分块内存的数据分配分布优化为其它优化如地址寄存器的分簇、访存向量化、软件流水等经典优化提供了良好基础,保证了编译器生成的代码可以充分发挥魂芯DSP提供的指令级并行能力.     

面向众核多级访存资源的静态数据布局优化模型

受功耗、面积的限制,高性能众核处理器倾向于将片上SRAM组织成SPM这种非cache形式,与片外主存构成多级存储架构.这种存储架构需要软件显示管理应用程序中的数据存储和传输.为此,提出了一种众核多级访存资源的静态数据布局优化模型.该模型首先选择应用程序中可进行访存优化的数组变量,对这些变量进行优化收益的评估,然后建立一个类0-1背包优化问题的目标模型,最后针对该优化模型提出了一个实用的近似算法.实验结果验证了该模型的有效性.     

SPM结构上冗余读延迟写优化的设计与实现

随着微处理器架构的发展,将片上SRAM组织成SPM这种软件管理的非cache结构成为众多处理器的选择。SPM结构的特点是实现简单,访问延迟低、带宽高。要有效利用有限的片上SPM空间提升程序性能,必须由用户显式进行数据的布局和传送,或者由编译器进行高效的自动访存优化。冗余读延迟写优化从循环中多个主存访问之间的关联性出发,自动进行了数据传送和缓存优化,提高了SPM上的数据重用率。经过测试,可以有效提升程序性能。     

一种加速访存地址计算的编译优化

在国产申威高性能多核服务器系统中,基础编译系统对应用程序中访存操作进行代码生成时,没有考虑国产处理器指令特征,导致编译器生成的访存地址计算代码效率较低,影响国产高性能处理器的性能。为充分发挥国产处理器高性能计算能力,提出一种加速访存地址计算的编译优化方法。加速访存地址计算编译优化基于处理器支持带扩展因子的运算指令,在编译器后端内存地址表达式合法性检查中,添加针对乘加模式的地址计算表达式合法性检查算法,自动识别地址表达式中存在的乘加运算并进行合法性检验,对符合条件的地址表达式在代码生成阶段匹配生成带扩展因子的运算指令来快速计算访存地址,从而加快访存指令的发射与执行以及应用程序中的访存地址生成,提升访存效率。使用行业标准性能测试集SPEC CPU2006对优化效果进行评测,结果表明,相比优化前SPECspeed Integer与SPECspeed Float Point两个子集,该优化方法平均性能分别提高了2.53%与1.50%。     

国产SW26010-Pro处理器上3级BLAS函数众核并行优化

BLAS (basic linear algebra subprograms)是最基本、最重要的底层数学库之一.在一个标准的BLAS库中,BLAS 3级函数涵盖的矩阵-矩阵运算尤为重要,在许多大规模科学与工程计算应用中被广泛调用.另外, BLAS 3级属于计算密集型函数,对充分发挥处理器的计算性能有至关重要的作用.针对国产SW26010-Pro处理器研究BLAS 3级函数的众核并行优化技术.具体而言,根据SW26010-Pro的存储层次结构,设计多级分块算法,挖掘矩阵运算的并行性.在此基础上,基于远程内存访问(remote memory access, RMA)机制设计数据共享策略,提高从核间的数据传输效率.进一步地,采用三缓冲、参数调优等方法对算法进行全面优化,隐藏直接内存访问(direct memory access, DMA)访存开销和RMA通信开销.此外,利用SW26010-Pro的两条硬件流水线和若干向量化计算/访存指令,还对BLAS 3级函数的矩阵-矩阵乘法、矩阵方程组求解、矩阵转置操作等若干运算进行手工汇编优化,提高了函数的浮点计算效率.实验结果显示,所提出的并行优化技术...     

一种面向软件管理内存层次的简易数据分块方法

考虑到硬件管理Cache 多级存储结构在功耗和面积方面的开销过大,众核处理器倾向于采用软件管理的多级存储结构,这就需要软件规划好程序的数据在各级存储上的布局和传输.尝试了一种依赖程序原有循环结构和问题规模的简易数据自动分块方法,根据循环层内的数据访存范围进行相应的分块,避免数据复杂的依赖关系分析,使得该方法易于在编译器中实现.同时可根据需要进一步结合程序变换如循环交换、循环联合和循环分裂等方法得到更佳的分块参数.实验结果表明,在大多数问题规模下与一般分块方法的优化性能相当,但在某些特定问题规模下能够获得较高的优化性能.     

基于可变步长的访存延迟测量模型的研究与实现

评测访存延迟对于优化应用访存模式和数据放置有重要的指导意义,然而数据Cache、多线程、数据预取等技术却严重干扰了访存延迟测量的精度。设计并实现了基于可变步长的访存延迟测量模型,在一块空间内根据用户指定的步长创建访问序列环,循环访问这个序列得出平均时间,即为访存延迟。最后对Intel的通用处理器和飞腾处理器在不同数据大小、步长、线程数等情况下的访存延迟进行了测量比较,该模型能够显示存储层次并精确显示测量延迟。     

基于可变步长的访存延迟测量模型的研究与实现

评测访存延迟对于优化应用访存模式和数据放置有重要的指导意义,然而数据Cache、多线程、数据预取等技术却严重干扰了访存延迟测量的精度。设计并实现了基于可变步长的访存延迟测量模型,在一块空间内根据用户指定的步长创建访问序列环,循环访问这个序列得出平均时间,即为访存延迟。最后对Intel的通用处理器和飞腾处理器在不同数据大小、步长、线程数等情况下的访存延迟进行了测量比较,该模型能够显示存储层次并精确显示测量延迟。     

面向E级超算系统的众核片上存储层次研究

当前众核已成为构建高性能计算（HPC）超级计算机的主流微处理器架构，为HPC领域E级超算提供强大的算力。随着众核处理器片上集成的运算核心数量不断增加，众多核心对存储资源竞争愈加激烈，“访存墙”问题越来越突出。众核片上存储层次是缓解“访存墙”问题并帮助HPC应用更好地发挥众核处理器的计算优势以提升实际应用性能的重要结构。众核片上存储层次的设计对众核片上系统性能、功耗和面积具有重要影响，是众核结构设计中的重要环节，也是业界的研究热点。由于众核芯片发展历史和片上微体系结构设计技术的不同，以及所面向的应用领域需求不同等原因，目前的HPC主流众核片上存储层次结构并不单一，但从横向比较和各处理器自身纵向发展趋势，以及从HPC与数据科学、机器学习不断融合发展带来的应用需求变化来看，SPM+Cache的混合结构最可能成为今后HPC E级超算系统众核处理器片上存储层次设计的主流选择。在面向E级计算的软件和算法层面，开展针对众核存储层次特点的设计与优化，可以帮助HPC应用更好地发挥众核处理器的计算优势，从而有效提升实际应用性能，因此面向众核片上存储层次特点的软件及算法设计与优化技术也是业界的研究热点之一。...     

GPU矩阵乘法的性能定量分析模型

性能评价和优化是设计高效率并行程序必不可少的重要工作,存储系统的性能高低直接影响到处理器的整体性能。利用GPGPU-Sim对GPU的存储层次结构进行了模拟,找出了SM数量与存储控制器数量之间最佳配置关系。矩阵乘法是科学计算领域中的基本组成部分,是一种具有计算和访存密集特点的典型应用,其性能是GPU高性能计算的一个重要指标。性能模型作为并行系统性能评价的新的技术解决方案,具有许多其它性能评价方法无法比拟的优势。建立了一个性能模型,模型通过对指令流水线、共享存储器访存、全局存储器访存进行定量分析,找到了程序运行瓶颈,提高了执行速度。实验证明,该模型具有实用性,并有效地实现了矩阵乘法的优化。     

OpenMDSP: Extending OpenMP to Program Multi-Core DSPs

Abstract Multi-core digital signal processors （DSPs） are widely used in wireless telecommunication, core network transcoding, industrial control, and audio/video processing technologies, among others. In comparison with general-purpose multi-processors, multi-core DSPs normally have a more complex memory hierarchy, such as on-chip core-local memory and non-cache-coherent shared memory. As a result, efficient multi-core DSP applications are very difficult to write. The current approach used to program multi-core DSPs is based on proprietary vendor software development kits （SDKs）, which only provide low-level, non-portable primitives. While it is acceptable to write coarse-grained task-level parallel code with these SDKs, writing fine-grained data parallel code with SDKs is a very tedious and error-prone approach. We believe that it is desirable to possess a high-level and portable parallel programming model for multi-core DSPs. In this paper, we propose OpenMDSP, an extension of OpenMP designed for multi-core DSPs. The goal of OpenMDSP is to fill the gap between the OpenMP memory model and the memory hierarchy of multi-core DSPs. We propose three classes of directives in OpenMDSP, including 1） data placement directives that allow programmers to control the placement of global variables conveniently, 2） distributed array directives that divide a whole array into sections and promote the sections into core-local memory to improve performance, and 3） stream access directives that promote big arrays into core-local memory section by section during parallel loop processing while hiding the latency of data movement by the direct memory access （DMA） of a DSP. We implement the compiler and runtime system for OpenMDSP on PreeScale MSC8156. The benchmarking results show that seven of nine benchmarks achieve a speedup of more than a factor of 5 when using six threads.     

Array Organization in Parallel Memories

The bandwidth mismatch between processor and main memory is one major throughput limiting problem. Although streamed computations have predictable access patterns their references have little temporal locality and are generally too long to cache. A memory and compiler co-optimization aimed at reducing low-level memory accesses using software and hardware locality optimizations is presented. We propose a scalable and predictable parallel memory based on a compiler synthesis of storage schemes for multi-dimensional arrays that are accessed by an arbitrary but known set of data access patterns. Using algebra of non-singular Boolean matrices, we present analysis of conflict-free access to (1) parallel memories, and (2) alignment networks. Finding a multi-pattern storage scheme is one NP-complete problem. An effective compiler heuristic is proposed for finding a storage matrix that minimizes overall memory access time. This applies to arbitrary linear patterns and arbitrary alignment networks. It is shown that the proposed storage scheme finds an optimal storage scheme for parallel (1) FFT, and (2) bitonic sorting. The proposed storage scheme outperforms statically optimized storages in the case of power-of-2 multi-stride access. The case of non power-of-2 strides is also addressed. The performance and scalability of the proposed parallel memory and its predictable access time are presented using numerical and multimedia algorithms. It is shown that a memory utilization above 83% is achieved by our storage scheme for 64 memories, which largely outperforms previous proposals. Our approach provides a tool for matching the storage pattern with the data access patterns needed for embedded systems running streamed computations with predictable data access patterns.     

Static Coarse Grain Task Scheduling with Cache Optimization Using OpenMP

Effective use of cache memory is getting more important with increasing gap between the processor speed and memory access speed. Also, use of multigrain parallelism is getting more important to improve effective performance beyond the limitation of loop iteration level parallelism. Considering these factors, this paper proposes a coarse grain task static scheduling scheme considering cache optimization. The proposed scheme schedules coarse grain tasks to threads so that shared data among coarse grain tasks can be passed via cache after task and data decomposition considering cache size at compile time. It is implemented on OSCAR Fortran multigrain parallelizing compiler and evaluated on Sun Ultra80 four-processor SMP workstation using Swim and Tomcatv from the SPEC fp 95. As the results, the proposed scheme gives us 4.56 times speedup for Swim and 2.37 times on 4 processors for Tomcatv respectively against the Sun Forte HPC Ver. 6 update 1 loop parallelizing compiler.     

基于域的编译框架

传统的基于函数范围的后端编译框架是一种方便的程序划分方法，然而，考虑到编译过程中的资源需求（例如编译时间和内存使用），代码性能以及编译功能，函数的范围大小以及结构并不是最适合进行程序分析和优化的程序划分，在现代编译器为了尽可能地发掘指令级并行机会而寻求更复杂和时空复杂性更高的算法和情况下，这种不适应性变得更加突出，当函数的范围很大时，时空复杂性很高的算法以函数为基本编译单位通常会导致编译时间太长和（或）内存消耗太多，Hank提,出了一种编译框架，使得优化的范围和结构可以得到一定的控制，基于编译时间和优化机会的考虑，本文提出了一种新的基于域的编译框架，同时，允许一些基于域的优化制导属性在不同的优化阶段之间被传递和观察，这个基于域的编译框架已经在目标码为安腾（Itanium)处理器的编译器ORC（Open Research Compiler)中实现，实验结果表明，此框架在控制编译的时空复杂性方面是成功的。     

基于经验搜索的多级存储层次优化

存储墙是影响单机性能优化的重要因素,其缓解依赖于对程序进行存储优化。论文提出基于经验搜索的多级存储层次优化方法,将优化多级存储层次问题转化为对优化参数的经验搜索问题,并基于遗传算法选择全局最优解。实验表明,该技术可以自适应不同应用程序,大大降低存储访问时间,降低存储因素对程序性能的影响,从而有效地缓解存储墙问题。     

基于申威GCC编译器的间接预取算法

对间接存储器的访问延迟往往会影响应用程序的执行性能, 一种有效的解决方案是使用预取技术. 国产申威平台中支持常规访问模式的软件预取和硬件预取机制, 但是其GCC编译器中缺少为间接存储器访问模式自动插入预取的方法. 为了解决这个问题, 基于申威GCC开发了一个完整间接预取优化遍, 它利用深度优先搜索算法查找引用循环归纳变量的间接内存引用并为之生成合适的软件预取. 在一组内存受限的基准测试中, 自动预取遍对SW1621处理器的平均加速比达到1.16倍.