面向众核结构的并行Comba乘法研究

为发挥众核处理器性能优势及求解更大规模问题,针对大整数乘法在众核处理器上的并行化进行研究。在对笔算乘法和Comba乘法并行性进行分析的基础上,针对Comba乘法并行化时面临的负载均衡问题提出了多种解决方法;然后针对SW26010的结构特征,选择借鉴笔算乘法改进的Comba乘法,并且实现过程使用了向量化、寄存器通信等优化方法。测试结果说明改进后的并行Comba算法具有较好的并行性,能够很好地利用SW26010众核处理器的性能优势。     

基于多核并行的海量数据序列模式挖掘*

为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的并行序列模式挖掘算法。该算法采用数据并行与任务并行相结合的策略,在各处理器核生成局部序列模式后,再与其他处理器核协同,以最终获得所有的全局序列模式。算法通过并行局部归约技术消除了局部序列的重复生成与计算,并可结合静态与动态任务分配机制解决处理器的负载不均衡问题。理论分析和实验都证实了该算法可有效利用多核计算平台及多核体系结构优势,具有较高的运行效率和加速比。     

CPU/GPU异构混合并行的栅格数据空间分析研究——以地形因子计算为例

海量数据背景下传统GIS栅格数据空间分析计算效率已经不能满足快速计算的需求,为此以地形因子计算为例,分析并测试了基于共享内存模型的CPU多核并行模式与基于流处理器模型的GPU众核并行模式的计算性能,在此基础上详细实现了负载均衡的设备间任务划分,进行CPU与GPU异构混合的并行技术改良研究。实验结果表明,基于相同的单机硬件环境,与多核共享内存模型或众核流处理器的单一计算平台并行方案相比,CPU/GPU异构混合并行计算方法对于栅格数据分析具有更好的加速效果。     

LU分解在Godson-Tvl众核体系结构上的半行化研究

随着集成电路工艺的发展,众核体系结构成为人们日益关注的计算平台.LU分解是科学和工程计算中被广泛使用的核心算法之一,尽管在传统的并行体系结构上已有大量的并行化研究工作,但是结合新犁众核体系结构特征的工作还不多.文章从负载均衡、延迟容忍和性能分析模型3个方面系统研究了LU分解在众核体系结构上的并行化问题.该文的贡献在于:首先,针对二维卷帘负载分配方案难以达到良好负载均衡的缺点,提出一种新的"之"字形分配方案,实验表明不经任何优化的情况下性能比前者提高20%,优化后达到了40%;其次,提出了一个性能加速比的分析模型,并用实验定量研究了实测性能加速比和理论值之间的差距,发现在合理利用片上存储优化访存延迟,并恰当选择矩阵分块参数的情况下,实测加速效果能比较接近理论值;通过实验还证明实测性能难以达到理论预测值的两个主要原因:访存带宽有限和片上网络的资源竞争.     

负载平衡技术在油藏数值模拟模型并行化中的应用

对胜利油区广泛采用的多层二维二相油藏模拟模型开展了并行化研究，提出并采用按层粗粒度并行方法实现软件的并行化。在此基础上，为解决各处理器负载不平衡的缺陷，结合软件的特点设计了多种负载平衡方案进行对比研究，优化后的负载平衡方案有效地提高了软件的并行效率，半进行了多种实用性影响因素分析。     

基于网络处理器的负载均衡算法的研究与实现

针对高速环境下转发决策困难的问题,提出一种由多个网络处理器组成的并行转发引擎结构。为解决负载分配问题,提出一种基于映射表的自适应负载分配算法AIHDA。AIHDA算法根据各网络处理器的负载状况和网络流量特性调整负载分配方式,折衷考虑了负载均衡和报文保序要求,具有较好的综合性能。     

一种面向异构众核处理器的并行编译框架

异构众核处理器是面向高性能计算领域处理器发展的重要趋势,但其更为复杂的体系结构使得编程难的问题更加突出.针对这一问题,基于开源编译器Open64,提出了一种面向异构众核处理器的并行编译框架,将程序自动转换为异构并行程序.该框架主要包括4个模块：任务划分模块用来识别适合进行加速计算的程序段,实现了嵌套循环的多维并行识别方法;数据布局模块完成数据在主存和SPM之间的布局,实现了数组边界分析和指针范围分析;传输优化模块实现了数据传输合并、传输外提、打包传输、数组转置等多种数据传输优化方法;收益评估模块在构建代价模型的基础上实现了一种动静结合的收益评估方法.并且,基于SW26010处理器,对该编译框架进行了实现,测试结果表明,该编译框架能够实现一些程序以面向异构众核结构的并行变换,且获得较好的加速效果.     

H.264并行编码中负载平衡方法

针对在多核处理器上Slice并行编码H.264高清视频中的负载不平衡问题,首先利用已编码帧的编码统计信息,根据帧间时间相关性预测下一帧各宏块的编码负载,然后据此预测的编码负载划分Slice,使各个处理器核上编码的Slice具有相接近的计算负载,从而达到动态负载平衡目的。在Tile64多核平台上的实际测试结果表明,与传统的基于宏块区域的动态数据分配算法相比,该方法可以将编码并行加速比和并行效率提高5%左右。     

三维FDTD众核算法的设计与实现

在电磁学中,时域有限差分算法(FDTD)能够精确地模拟空间中电磁场的变化,在电介质器件设计领域得到了广泛的应用。众核(many-core)处理器片上计算资源丰富,对于计算密集型课题有较好的适应性。通过对麦克斯韦方程FDTD仿真算法的分析,并根据众核处理器的特性,实现了FDTD算法的众核并行。实验结果表明,FDTD算法在众核处理器平台上具有较好的计算效率,能够很好地发挥众核结构的优势。     

高精度湍流直接数值模拟程序的异构并行优化分析

在众核处理器应用中,主要难点在于异构并行应用模式和负载均衡的策略,对于计算流体力学,需要针对相关应用设计相应的方案。我们针对湍流直接数值模拟中串行程序含有部分并行度较高的子程序或函数的特点,设计了一种新的并行计算模式,给出了一种异构平台优化方案,并在中科院超级计算系统"元"上进行了测试和分析,对领域内的典型算例进行了性能测试,着重讨论了不同规模下采用offload模式的CPU和MIC异构并行的扩展性能。     

Parallelism and Scalability in an Image Processing Application

The recent trends in processor architecture show that parallel processing is moving into new areas of computing in the form of many-core desktop processors and multi-processor system-on-chips. This means that parallel processing is required in application areas that traditionally have not used parallel programs. This paper investigates parallelism and scalability of an embedded image processing application. The major challenges faced when parallelizing the application were to extract enough parallelism from the application and to reduce load imbalance. The application has limited immediately available parallelism and further extraction of parallelism is limited by small data sets and a relatively high parallelization overhead. Load balance is difficult to obtain due to the limited parallelism and made worse by non-uniform memory latency. Three parallel OpenMP implementations of the application are discussed and evaluated. We show that with some modifications relative speedups in excess of 9 on a 16 CPU system can be reached.     

Towards Efficient Short-Range Pair Interaction on Sunway Many-Core Architecture

The short-range pair interaction consumes most of the CPU time in molecular dynamics(MD)simulations.The inherent computation sparsity makes it challenging to achieve high-performance kernel on the emerging many-core ar-chitecture.In this paper,we present a highly efficient short-range force kernel on the Sunway,a novel many-core architecture with many unique features.The parallel efficiency of this algorithm on the Sunway many-core processor is strongly limited by the poor data locality and write conflicts.To enhance the data locality,we adopt a super cluster based neighbor list with an appropriate granularity that fits in the local memory of computing cores.In the absence of a low overhead locking mechanism,using data-privatization force array is a more feasible method to avoid write conflicts,but results in the large overhead of data reduction.We adopt a dual-slice partitioning scheme for both hardware resources and computing tasks,which utilizes the on-chip data communication to reduce data reduction overhead and provide load balancing.Moreover,we exploit the single instruction multiple data(SIMD)parallelism and perform instruction reordering of the force kernel on this many-core processor.The experimental results show that the optimized force kernel obtains a performance speedup of 226x compared with the reference implementation and achieves 20％of peak flop rate on the Sunway many-core processor.     

众核处理器和众核集群的并行模拟

模拟器是计算机体系结构研究的重要工具.近年来并行计算机体系结构的发展给计算机模拟带来了巨大的挑战.一方面,随着体系结构朝着多核以及众核处理器发展,模拟的目标系统规模随着模拟核数以摩尔定律的速度增加而不断增大;另一方面,串行模拟的速度因为模拟器运行所在宿主机主频提速减缓而停滞不前.上述两方面的原因使得传统的串行模拟方式无法满足对新兴体系结构模拟规模和速度的需求.以众核处理器和众核集群这两种体系结构为例,并行模拟技术在并行计算机体系结构模拟中是必要而且可行的.对于众核处理器的模拟,使用并行离散事件模拟对其进行加速,在模拟精度不变的前提下,提高模拟速度10.9倍.对于众核集群的模拟,模拟的目标系统总规模达到1024核,并且支持MPI/Pthreads混合编程的运行环境.     

BFS算法与众核处理器的适应性研究

以图计算为代表的数据密集型应用获得越来越广泛的关注,而传统的高性能计算机处理这类应用的效率较低.面向未来高性能计算机体系结构要有效支持数据密集型计算,深入研究以广度优先搜索(breadth-first search, BFS)算法为代表的图计算的典型特征,设计实现轻量级启发式切换BFS算法,该算法通过基本搜索方式的自动切换,避免冗余内存访问,提高搜索效率;针对BFS算法的离散随机数据访问特征以及众核处理器执行机制,建立面向BFS算法的众核处理器体系结构分析模型;全面、深入研究了BFS算法在典型众核处理器上的运行特征和性能变化趋势.测试结果表明：Cache命中率、内存带宽、流水线利用效率等相关参数均处于较低水平,无法完全满足BFS算法的需求,因此需要能够支持大量离散随机访问和简单执行机制的新型众核处理器体系结构.     

模型指导的多维GPU软件低功耗优化方法

作为众核体系结构的典型代表,GPU(Graphics Processing Units)芯片集成了大量并行处理核心,其功耗开销也在随之增大,逐渐成为计算机系统中功耗开销最大的组成部分之一,而软件低功耗优化技术是降低芯片功耗的有效方法.文中提出了一种模型指导的多维低功耗优化技术,通过结合动态电压/频率调节和动态核心关闭技术,在不影响性能的情况下降低GPU功耗.首先,针对GPU多线程执行模型的特点,建立了访存受限程序的功耗优化模型;然后,基于该模型,分别分析了动态电压/频率调节和动态核心关闭技术对程序执行时间和能量消耗的影响,进而将功耗优化问题归纳为一般整数规划问题;最后,通过对9个典型GPU程序的评测以及与已有方法的对比分析,验证了该文提出的低功耗优化技术可以在不影响性能的情况下有效降低芯片功耗.     

SUPPLE: An efficient run-time support for non-uniform parallel loops

This paper presents SUPPLE (SUPort for Parallel Loop Execution), an innovative run-time support for the execution of parallel loops with regular stencil data references and non-uniform iteration costs. SUPPLE relies upon a static block data distribution to exploit locality, and combines static and dynamic policies for scheduling non-uniform iterations. It adopts, as far as possible, a static scheduling policy derived from the owner computes rule, and moves data and iterations among processors only if a load imbalance actually occurs. SUPPLE always tries to overlap communications with useful computations by reordering loop iterations and prefetching remote ones in the case of workload imbalance. The SUPPLE approach has been validated by many experimental results obtained by running a multi-dimensional flame simulation kernel on a 64-node Cray T3D. We have fed the benchmark code with several synthetic input data sets built on the basis of a load imbalance model. We have compared our results with those obtained with a CRAFT Fortran implementation of the benchmark.     

SSearch基于众核加速的并行模型分析

介绍SSearch核心算法的特点,分析该算法的并行性,并以GPU以及类Cell处理器为例分析算法对众核系统的适用性。在此基础上提出众核系统下的SSearch并行模型。     

Tree-based parallel load-balancing methods for solution-adaptivefinite element graphs on distributed memory multicomputers

To solve the load imbalance problem of a solution-adaptive finite element application program on a distributed memory multicomputer, nodes of a refined finite element graph can be remapped to processors or load of a refined finite element graph can be redistributed based on the current load of each processor. For the former case, remapping can be performed by some fast mapping algorithms. For the latter case, a load-balancing algorithm can be applied to balance the computational load of each processor. In this paper, three tree-based parallel load-balancing methods, the MCSTLB method, the BTLB method, and the CBTLB method, were proposed to deal with the load imbalance problems of solution-adaptive finite element application programs. To evaluate the performance of the proposed methods, we have implemented those methods along with three mapping methods, the AE/ORB method, the AE/MC method, and the MLkP method, on an SP2 parallel machine. Three criteria, the execution time of mapping/load-balancing methods, the execution time of a solution-adaptive finite element application program under different mapping/load-balancing methods, and the speedups achieved by mapping/load-balancing methods for a solution-adaptive finite element application program, are used for the performance evaluation. The experimental results show that 1) if the initial mapping is performed by a mapping method and the same mapping method and load-balancing methods were used in each refinement to balance the load of processors, the execution time of an application program under a load-balancing method is always shorter than that of the mapping method, and 2) the execution time of an application program under the CBTLB method is shorter than that of the BTLB method and the MCSTLB method     

How many cores do we need to run a parallel workload: A test drive of the Intel SCC platform?

As semiconductor manufacturing technology continues to improve, it is possible to integrate more and more transistors onto a single processor. Many-core processor design has resulted in part from the search to utilize this enormous transistor real estate. The Single-Chip Cloud Computer (SCC) is an experimental many-core processor created by Intel Labs. In this paper we present a study in which we analyze this innovative many-core system by running several workloads with distinctive parallelism characteristics. We investigate the effect on system performance by monitoring specific hardware performance counters. Then, we experiment on varying different hardware configuration parameters such as number of cores, clock frequency and voltage levels. We execute the chosen workloads and collect the timing, power consumption and energy consumption information on such a many-core research platform. Thus, we can comprehensively analyze the behavior and scalability of the Intel SCC system with the introduced workload in terms of performance and energy consumption. Our results show that the profiled parallel workload execution has a communication bottleneck on the Intel SCC system. Moreover, our results indicate that we should carefully choose the number of cores to execute different workloads in order to yield a balance between execution performance and energy efficiency for different applications.