面向多核集群的数据流程序层次流水线并行优化方法

数据流编程语言是一种面向领域的编程语言,它能够将计算与通信分离,暴露应用程序的并行性.多核集群中计算、存储和通信等底层资源的复杂性对数据流程序的性能提出了新的挑战.针对数据流程序在多核集群上执行存在资源利用低和扩展性差等问题,利用同步数据流图作为中间表示,文中提出并实现了面向多核集群的层次性流水线并行优化方法.方法包含任务划分与调度、层次流水线调度和数据局部性优化,经过编译优化后生成基于MPI的可并行执行的目标代码.其中任务划分与调度是利用程序中数据和任务并行性将任务映射到计算核上,实现负载均衡和低通信同步开销;层次性流水线调度是利用程序中的并行性构造低延迟流水线调度;数据局部性优化是针对数据访问存在的Cache伪共享做面向存储的优化.实验以X86架构多核处理器组成的集群为平台,选取媒体处理领域的典型应用算法作为测试程序,对层次流水线优化进行实验分析.实验结果表明了优化方法的有效性.     

基于GPU/CPU混合架构的流程序多粒度划分与调度方法研究

数据流编程语言简化了相关领域的编程,很好地把任务计算和数据通信分开,从而使应用程序分别在任务级和数据级均具有可并行性。针对GPU/CPU混合架构中存在的大量数据并行、任务并行和流水线并行等问题,提出并实现了面向GPU/CPU混合架构的数据流程序任务划分方法和多粒度调度策略,包括任务的分类处理、GPU端任务的水平分裂和CPU端离散任务的均衡化,构造了软件流水调度,经过编译优化生成OpenCL的目标代码。任务的分类处理根据数据流程序各个任务的计算特点和任务间的通信量大小,将各任务分配到合适的计算平台上;GPU端任务的水平分裂利用GPU端任务的并行性将其均衡分裂到各个GPU,以避免GPU间高额的通信开销影响程序整体的执行性能;CPU端离散任务的均衡化通过选择合适CPU核,将CPU端各任务均衡分配给各CPU核,以保证负载均衡并提高各CPU核的利用率。实验以多块NVIDIA Tesla C2050、多核CPU为混合架构平台,选取多媒体领域典型的算法作为测试程序,实验结果表明了划分方法和调度策略的有效性。     

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

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

一种面向数据流程序的软件流水并行化方法

数据流编程被广泛应用于多媒体、图像处理和信号处理等领域.多核处理器为数据流程序提供了强大并行计算资源,如何利用多核处理器的并行性以提高数据流程序性能,对满足媒体处理等实时性需求具有重要意义.基于多核处理器提出了一种面向数据流程序的软件流水并行化方法,利用整数线性规划理论对软件流水中的计算、通信资源和流水线执行阶段等进行...     

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

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

基于Storm的海量数据实时聚类

针对现有平台处理海量数据实时响应能力普遍较差的问题,引入Storm分布式实时计算平台进行大规模数据的聚类分析,设计了基于Storm框架的DBSCAN算法。该算法将整个过程分为数据接入、聚类分析、结果输出等阶段,在框架预定义的组件中分别编程实现,各组件通过数据流连通形成任务实体,提交到集群运行完成。通过对比分析和性能监测,验证了所提方案具有低延迟和高吞吐量的优势,集群运行状况良好,负载均衡。实验结果表明Storm平台处理海量数据实时性较高,能够胜任大数据背景下的数据挖掘任务。     

基于Storm的变压器PRPD参数提取与模式构造

随着局部放电数据增多,为了提高放电数据的参数提取和模式构造的效率,将放电数据参数分析与Storm相结合,设计并使用Storm平台下双阈值过滤参数提取算法.该算法在框架组件中分别对各个阶段进行编程实现,通过数据流连通,将其产生的任务提交至集群完成,有效提取基本参数并且绘制图谱.实验结果表明,该算法与Storm框架结合具有...     

面向异构多核架构的自适应编译框架

针对应用在移植到异构多核高性能计算机系统中所面临的可移植性差以及性能优化难度大的问题,文中提出一种面向异构多核架构的自适应编译框架.通过源到源编译解决传统并行编程模型应用向异构多核架构的映射问题;同时利用动态剖分信息,自适应地调整插桩并配置优化策略,形成迭代式的自动优化过程.文中自适应编译框架将软硬件映射机制与优化策略结合,有效地解决了同构并行应用向异构多核架构的移植问题并提高了应用的整体性能.实验结果表明,文中基于Cell架构实现的原型系统,很好地解决了异构多核架构下应用移植性等问题,同时应用性能有所提高.     

基于Storm拓扑结构热边的调度算法

Storm分布式实时计算系统采用轮询调度算法达到任务均衡分配的目的,但Storm默认调度算法未考虑计算节点间的网络通信开销,可能造成topology处理时延高、集群吞吐量低等问题。为此,引入Storm topology热边的概念,通过减少网络传输的tuple数量,将热边关联的源executor和目标executor调度到同一工作节点执行,提升Storm集群的计算性能。实验结果表明,该调度算法能够有效降低Storm处理时延及集群节点间的通信量,提高系统吞吐量,并且有利于集群的负载均衡。     

Storm环境下基于权重的任务调度算法

大数据流式计算平台Apache Storm默认采用轮询的方式进行任务调度,未考虑到拓扑中各任务计算开销的差异以及任务之间不同类型的通信模式,在负载均衡和通信开销方面存在较大的优化空间。针对这一问题,提出一种Storm环境下基于权重的任务调度算法（TSAW-Storm）。该算法首先根据各任务的CPU资源占用情况以及任务间的数据流大小,分别确定拓扑的点权和边权;并利用最大化边权增益的思想,逐步构建起各工作节点中承载的任务集合,在保证集群负载均衡的同时,尽可能将边权较大的节点间数据流转化为节点内数据流,从而降低网络传输开销。实验结果表明,在包含有8个工作节点的WordCount基准测试中,TSAW-Storm的系统延迟和节点间数据流大小相比Storm默认调度算法分别降低了30.0%和32.9%,且各工作节点的CPU负载标准差仅为Storm默认调度算法的25.8%;此外,在与在线调度算法的对比实验中,TSAW-Storm在系统延迟、节点间数据流大小和CPU负载标准差方面分别降低了7.76%、11.8%和5.93%,且算法的执行开销明显降低,有效提高了Storm系统的运行效率。     

面向边缘计算的Storm边缘节点调度优化方法

边缘计算有高实时性和大数据交互处理的需求,边缘异构节点间的调度时耗长、通信时延高以及负载不均衡是影响边缘计算性能的核心问题,传统的云计算平台难以满足新的要求。文中研究了在边缘计算环境下Storm边缘节点的调度优化方法,建立了面向边缘计算的Storm任务卸载调度模型。针对拓扑任务在边缘异构节点间的实时动态分配问题,提出了一种启发式动态规划算法(Inspire Dynamic Programming,IDP),通过改变Storm的Task实例的排序分配方式以及Task实例和Slot任务槽的映射关系实现全局的优化调度;同时,针对拓扑任务的并发度受限于JVM栈深度的缺陷,提出了一种基于蝙蝠算法的调度策略。实验结果表明,与Storm调度算法相比,所提算法在边缘节点CPU利用率指标上平均提升了约60%,在集群的吞吐量指标上平均提升了约8.2%,因此能够满足边缘节点之间的高实时性处理要求。     

Exploiting Distributed-Memory and Shared-Memory Parallelism on Clusters of SMPs with Data Parallel Programs

Clusters of SMPs are hybrid-parallel architectures that combine the main concepts of distributed-memory and shared-memory parallel machines. Although SMP clusters are widely used in the high performance computing community, there exists no single programming paradigm that allows exploiting the hierarchical structure of these machines. Most parallel applications deployed on SMP clusters are based on MPI, the standard API for distributed-memory parallel programming, and thus may miss a number of optimization opportunities offered by the shared memory available within SMP nodes. In this paper we present extensions to the data parallel programming language HPF and associated compilation techniques for optimizing HPF programs on clusters of SMPs. The proposed extensions enable programmers to control key aspects of distributed-memory and shared-memory parallelization at a high-level of abstraction. Based on these language extensions, a compiler can adopt a hybrid parallelization strategy which closely reflects the hierarchical structure of SMP clusters by automatically exploiting shared-memory parallelism based on OpenMP within cluster nodes and distributed-memory parallelism utilizing MPI across nodes. We describe the implementation of these features in the VFC compiler and present experimental results which show the effectiveness of these techniques.     

Storm流处理平台中负载均衡机制的实现

Storm流处理平台解决了传统的基于Hadoop的批处理系统实时性不高的问题,为多源异构大数据处理提供了高效、快速、实时的数据处理框架。然而Storm平台在任务分配过程中只考虑了不同节点之间可用Slot的排序,并没有充分考虑节点的实际负载情况,从而容易产生负载不均衡的问题。针对以上问题,本文在Storm分布式流处理系统上实现对可用Slot和节点负载情况的加权排序改进Storm调度算法,通过数据结构设计,保证rowkey的随机性和唯一性,确保RegionServer的负载平衡;同时通过批量写入的机制,提高Hbase数写入速度,从而提高流数据存储效率。通过与原生Storm系统的对比实验,表明本文算法的改进和机制优化保证了数据的快速写入,提高了集群资源的利用率,改进后的系统在实用性与效率上具有明显的优势。     

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

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

软件流水的低功耗编译技术研究

对具有可动态独立调整运行频率/电压的多功能部件配置结构M,基于全局调度的循环依赖关系,使用ILP形式化框架,研究了对给定循环L进行动态频率/电压调整的低功耗软件流水调度的编译优化技术.提出了一种合理而有效的低功耗最优化软件流水调度方法,使其在运行时保持性能不变而消耗的功耗/能量最小.     

基于GCC的VLIW编译系统研究

VLIW机器在单个机器周期中同时发射并执行多个的并行操作,从而获得较高的指令级并行度,这些操作之间的依赖分析和调度工作则被完全交给相应的编译器执行,因此VLIW的并行性能能否充分发挥取决于VLIW体系结构相关编译器的质量。GNU开发的GCC是被最广泛使用的编译系统之一,它具有多语言、多平台支持的能力和开放的结构,能够运用各种成熟的常规编译优化技术生成高效的代码。文章分析了VLIW及GCC的结构特点,提出了一种基于GCC的VLIW编译系统设计方案,利用GCC进行RTL中间代码一级的体系结构无关优化和少量体系结构相关优化,在汇编代码一级针对VLIW结构进行体系结构相关的优化,从而充分利用GCC的成熟编译技术快速开发高效的VLIW多语言编译系统。     

一种多线程计算程序的机群移植方法

机群并行化应用程序的用户接口和编程方式多种多样，常常令用户望而却步，该文详细了一种从程序的目标代码着手，以ELF格式可执行文件PLT表项重定位为基础，利用多线程程序自身的并发和同步特征，让线程中的计算负载分布到机群各节点的移植技术，为用户提供透明的机群并行机制，提出并讨论了相应的Master-Worker(Task-Farming)计算通信模型以及调度策略，最后，通过实现该移植技术，分析基于BLAS库多线程矩阵乘法程序移植后的运行结果，验证了该模型的可行性和效率。     

Supporting OpenMP on Cell

The Cell processor is a heterogeneous multi-core processor with one power processing engine (PPE) core and eight synergistic processing engine (SPE) cores. There is a significant amount of ongoing research in programming models and tools that attempts to make it easy to exploit the computation power of the Cell architecture. In our work, we explore supporting OpenMP on the Cell processor. It is attractive to support OpenMP because programmers can continue using their familiar programming model, and existing code can be re-used. We base our work on IBM’s XL compiler, and developed new components in the XL compiler and a new runtime library. Three major issues are addressed: (1) synchronization support on heterogeneous cores; (2) code generation targeting the different instruction sets; (3) data transfers and implement the OpenMP memory model. We present experimental results for some SPEC OMP 2001 and NAS benchmarks to demonstrate the effectiveness of this approach. A visualization tool based on Paraver is also used to provide some insights into actual thread and synchronization behaviors.