异构系统功耗感知的并行循环调度方法

以类OpenMP的并行程序为研究对象,在满足性能约束的条件下,结合异构系统并行循环调度和处理器动态电压调节技术优化系统功耗.首先建立了异构系统功耗感知的并行循环调度问题基本模型;然后,通过分析方法给出异构系统并行循环调度的能耗下界,该下界可用于评估功耗优化方法的实际效率;进而将异构系统并行循环调度问题归纳为整数规划问题,在此基础上,提出了处理器内循环再调度方法进一步降低功耗.最后,以CPU-GPU异构系统为平台评测了10个典型kernel程序.实验结果表明,该方法可以有效降低系统功耗,提高系统效能.     

一种面向异构并行系统的最大功耗管理方法

高功耗已成为制约高性能计算机发展的重要问题之一.近年来,大量研究关注于如何在满足系统功耗约束的条件下优化系统执行性能.然而,已有方法大都针对同构系统,未考虑异构处理器之间的功耗或速度差异,难以高效应用于基于加速器的异构系统.对当前异构并行系统执行模型进行了抽象,并提出了融合两级功耗控制机制的系统功耗管理框架,自顶向下依次为系统级功耗控制器和异构处理引擎功耗控制器.在异构处理引擎功耗控制中,针对类OpenMP 并行循环,首先分析了异构多处理器在满足功耗约束条件下达到性能最优的条件.基于该结果,给出了功耗受限的并行循环划分算法,该方法通过协调并行循环调度和动态电压频率调节技术以优化异构并行处理.在系统级功耗控制中,建立了异构处理引擎效能评估方法,以此作为功耗划分的依据,在兼顾并发应用公平性的同时,提高系统整体执行效能.最后,基于典型CPU-GPU 异构系统验证了方法的有效性.     

基于多核处理器的K线程低能耗的任务调度优化算法

针对具有独立DVFS的多核处理器系统,提出了一种K线程低能耗模型的并行任务调度优化算法(Tasks Optimization based on Energy-Effectiveness Model,TO-EEM)。与传统的并行任务节能调度相比,该算法的主要目标是不仅通过降低处理器频率来减少处理器瞬时功耗,而且结合并行任务间的同步互斥所造成的线程阻塞情况,合理分配线程资源来减少线程同步时间,优化并行性能;保证任务在一定的并行加速比性能前提下,提高资源利用率,减少能耗,达到程序能耗和性能之间的折衷。文中进行了大量模拟实验,结果证明提出的任务优化模型算法节能效果明显,能有效降低处理器的功耗,并始终保持线性加速比。     

云计算中相似驱动的并行任务划分方法

云计算是并行计算、分布式计算和网格计算等高性能计算的进一步发展,它的异构性、按需等特征对高性能计算提出了新的挑战。针对云计算的典型特征,提出了基于并行任务和云环境相似驱动的任务划分方法。首先用图刻画了并行任务和云环境,建立了图的相似关系及其相似度计算方法;其次给出云计算中拟解决的问题,通过图局部相似和全局相似度偏差最小来实现并行任务和体系结构的异构匹配及按需要求;接着利用F度标号方法给出相似驱动的任务划分算法;最后通过实验和其他划分方法进行比较,阐明了该方法的优点。     

异构集群下的任务调度算法研究

针对异构集群下高效节能的任务调度算法进行了研究, 提出了一种基于复制的任务调度算法, 在任务初始分配的基础上, 分别从能源感知和性能—能源平衡两个角度考虑任务的复制。建立了由计算和通信造成的能源消耗的数学模型, 并进行了大量的实验。实验结果表明, 与已有的BEATA算法相比, 该算法能明显地减少异构集群处理并行应用的调度长度和能耗。分析结果发现, 任务复制的方法在减少调度长度的同时会增加相应的能耗, 能同比优化调度长度和能耗的任务调度方法是今后的研究方向。     

异构计算中的时间和能耗优化执行方法

计算环境的异构性以及应用任务的复杂多样性导致异构计算的必要性。异构计算的目的是重视并行处理系 统和计算任务的差异,寻求系统和任务的有效匹配,从而获得并行任务在系统上执行的最佳效果。当前,异构计算中 的时间优化执行方法较成熟,但同时将时间和能耗联合起来作为异构计算优化执行目标方面的研究很少。以高性能 计算和绿色计算为总目标,针对异构计算环境中并行任务分配调度执行问题,提出了异构任务模型、异构计算速率矩 阵、异构计算功率矩阵,利用能耗时间归一思想,给出并行任务在异构处理机上时间与能耗启发式优化执行算法,并通 过实例分析证实算法的可行性和有效性。     

移动设备中异构处理器平台的能量优化设计

由于移动设备含有多个传感器,系统往往需要运行连续的感知任务。移动设备中的应用处理器能有效地运行计算密集型任务,而对于连续的感知任务将消耗大量的能量。为了提高移动设备的能量利用率,在包含应用处理器和低功耗处理器的异构处理器上提出了一种异构处理器平台能量优化方法。首先,根据处理器平台的实际能耗和理想能耗提出了能量比例因子。其次,提出了含有两个异构处理器平台的应用程序划分方法。最后,通过模拟器实验验证了该方法的有效性。模拟实验表明,由于将感知任务迁移到低功耗处理器上运行,所提出的优化方法能大大提高移动设备的能量利用效率。     

网格环境下基于复制的能耗有效依赖任务调度研究

随着能耗管理成为可靠和绿色计算的重要课题,能耗感知调度方法以其低成本和可行性引发关注.目前,网格环境下依赖任务的能耗感知调度研究具有极大的挑战性,其需要平衡应用的优先约束性、海量数据传输、系统的异构性和不同性能指标的冲突性的关系.提出的网格依赖任务的能耗有效调度(energy-efficient scheduling of grid dependent tasks,ESGDT)算法旨在优化应用执行时间的前提下降低应用执行能耗,能有效解决上述问题.通过任务复制和渐进比例因子减少通信时间和通信能耗,同时兼顾应用复杂的数据依赖关系;适应芯片微型化和多核技术的发展趋势,采用动态电源管理技术减少任务执行的静态能耗;任务复制条件、渐进比例因子和微调原则均适时兼顾时间和能耗两个相互冲突的调度指标,并提出自适应和动态映射方法适应异构计算环境.模拟实验表明,较HEFT,EETDS和HEADUS算法,ESGDT算法不仅没有影响调度的时间性能,还可进一步降低应用执行能耗.     

异构并行系统能耗优化分析模型

随着处理器功耗不断增大,功耗问题逐渐成为高性能计算机系统设计与实现的首要问题.当前,异构系统已成为高性能计算机的发展趋势之一.与传统同构体系结构相比,异构体系结构具有更高的理论峰值性能和能效,但是如何在满足应用性能的条件下充分发掘异构系统的能效优势,仍是一个挑战性问题.通过将应用程序抽象为由串行段和并行段组成的一般程序模型,建立了异构并行系统能耗优化模型通过分析方法依次给出并行段以及全程序(多程序段)能耗最优时处理器间满足的关系,分别给出了时间约束下能耗最优的处理器频率选择算法.最后,以CPU-GPU异构系统为平台,通过8个典型应用程序验证了方法的有效性.     

国产异构系统上的HPCG并行算法及高效实现

HPCG基准测试程序是一种新的超级计算机排名度量标准.该测试基准主要用于衡量超级计算机解决大规模稀疏线性系统的能力,更贴近实际应用,近年来广受关注.基于国产超级计算机研究异构众核并行HPCG软件具有非常重要的意义,其不仅可以提升国产超级计算机HPCG的排名,还对很多应用提供了并行算法、优化技术等方面的参考.面向某国产复杂异构超级计算机开展研究,首先采用了分块图着色算法对HPCG进行并行,并提出一种适用于结构化网格的图着色算法.该算法并行性能高于传统的JPL、CC等算法,且着色质量高,运用于HPCG后,迭代次数减少了3次,整体性能提升了6%.分析了复杂异构系统各个部件传输的开销,提出一套更适用于HPCG的任务划分方法,并从稀疏矩阵存储格式、稀疏矩阵重排、访存等角度开展了细粒度的优化.在多进程计算时,还采用内外区划分算法将核心函数SpMV、SymGS中的邻居通信操作进行了隐藏.最终整机测试时,性能达到了国产超级计算机峰值性能的1.67%,与单节点相比,整机弱可扩展性并行效率达到了92%.     

A framework for partitioning parallel computations in heterogeneous environments

In the paper we present a framework for partitioning data parallel computations across a heterogeneous metasystem at runtime. The framework is guided by program and resource information which is made available to the system. Three difficult problems are handled by the framework: processor selection, task placement and heterogeneous data domain decomposition. Solving each of these problems contributes to reduced elapsed time. In particular, processor selection determines the best grain size at which to run the computation, task placement reduces communication cost, and data domain decomposition achieves processor load balance. We present results which indicate that excellent performance is achievable using the framework. The paper extends our earlier work on partitioning data parallel computations across a single-level network of heterogeneous workstations.     

异构计算平台上列存储系统的并行连接优化策略

GPU以及集成式的CPU-GPU架构凭借其强大的并行处理能力和可编程流水线方式,已经成为数据库领域的研究热点。为充分利用异构平台的并行计算能力,提升列存储系统的查询性能,在研究异构平台结构特性的基础上,首先提出了GPU多线程平台上进行连接的数据划分策略--ICMD（Improved CMD）,利用GPU流处理器并行处理各个子空间上的连接,然后利用任务评估分配模型实现查询负载的动态分配,使得查询操作能在多核CPU、GPU上高效并行执行。同时利用片上全局同步机制、局部内存重用技术优化ICMD连接算法。最后采用SSB基准测试集测试,结果表明：Intel? HD Graphics 4600平台上并行连接查询相比于CPU版本获得了35%的性能提升,较GPU查询引擎的Ocelot性能上提升了18%。     

Degree-of-Node Task Scheduling of Fine-Grained Parallel Programs on Heterogeneous Systems

Processor specialization has become the development trend of modern processor industry. It is quite possible that this will still be the main-stream in the next decades of semiconductor era. As the diversity of heterogeneous systems grows, organizing computation efficiently on systems with multiple kinds of heterogeneous processors is a challenging problem and will be a normality. In this paper, we analyze some state-of-the-art task scheduling algorithms of heterogeneous computing systems and propose a Degree of Node First (DONF) algorithm for task scheduling of fine-grained parallel programs on heterogeneous systems. The major innovations of DONF include:1) simplifying task priority calculation for directed acyclic graph (DAG) based fine-grained parallel programs which not only reduces the complexity of task selection but also enables the algorithm to solve the scheduling problem for dynamic DAGs; 2) building a novel communication model in the processor selection phase that makes the task scheduling much more efficient. They are achieved by exploring finegrained parallelism via a dataflow program execution model, and validated through experimental results with a selected set of benchmarks. The results on synthesized and real-world application DAGs show a very good performance. The proposed DONF algorithm significantly outperforms all the evaluated state-of-the-art heuristic algorithms in terms of scheduling length ratio (SLR) and efficiency.     

Static and Dynamic Processor Scheduling Disciplines in Heterogeneous Parallel Architectures

Most parallel jobs cannot be fully parallelized. In a homogeneous parallel machine-one in which all processors are identical-the serial fraction of the computation has to be executed at the speed of any of the identical processors, limiting the speedup that can be obtained due to parallelism. In a heterogeneous architecture, the sequential bottleneck can be greatly reduced by running the sequential part of the job or even the critical tasks in a faster processor. This paper uses Markov chain based models to analyze the performance of static and dynamic processor assignment policies for heterogeneous architectures. Parallel jobs are assumed to be described by acyclic directed task graphs. A new static processor assignment policy, called Largest Task First Minimum Finish Time (LTFMFT), is introduced. The analysis shows that this policy is very sensitive to the degree of heterogeneity of the architecture, and that it outperforms all other policies analyzed. Three dynamic assignment disciplines are compared and it is shown that, in heterogeneous environments, the disciplines that perform better are those that consider the structure of the task graph, and not only the service demands of the individual tasks. The performance of heterogeneous architectures is compared with cost-equivalent homogeneous ones taking into account different scheduling policies. Finally, static and dynamic processor assignment disciplines are compared in terms of performance.     

优化能耗的可变电压禁忌任务调度算法

能耗是影响异构式并行和分布式系统性能的一个重要因素,动态电压缩放(DVS)技术通过将处理器降低到不同频率来达到有效地节约能耗的目标。通常DVS技术包含任务调度及空闲时间片分配两阶段。当前绝大部分研究均针对时间片分配阶段,而在此考虑的是任务分配与空闲时间片间的关系。为了降低异构分布式系统的能耗,提出了一个利用禁忌(Tabu)策略进行调度的DVS算法。此算法首先调度用有向无环图(DAG)表示的任务集到处理器上,再应用禁忌策略来改进它,通过禁止任务再调度到特定处理器,从而增加时间片,分配阶段可用的空闲时间片达到进一步减少能耗的目标。仿真结果表明,本算法能有效地减少计算机系统的能耗。     

混合粒子群算法的异构多核处理器间任务调度

针对异构多核处理器间的任务调度问题,为了更好地发挥异构多核处理器间的平台优势,提出一种基于将有关联的且不在同一处理器上的任务进行复制的思想,从而使每个异构多核的处理器能独立执行任务,来减少不同处理器之间的通信开销,并且通过混合粒子群算法(HPSO)来调度异构多核处理器中的任务,避免由于当任意一个异构多核处理器由于任务分配过多而导致计算机不能及时且准确地得出结果.最后实验证明,对比传统的启发式分配方案和常见的遗传算法(GA),基于任务复制思想分配方案和混合粒子群算法(HPSO)具有更好的求解能力,并且可以提供执行时间更少的调度分配方案,具有较好的应用价值.     

Energy-optimal Batching periods for asynchronous multistage data processing on sensor nodes: foundations and an mPlatform case study

This paper derives energy-optimal batching periods for asynchronous multistage data processing on sensor nodes in the sense of minimizing energy consumption while meeting end-to-end deadlines. Batching the processing of (sensor) data maximizes processor sleep periods, hence minimizing the wakeup frequency and the corresponding overhead. The algorithm is evaluated on mPlatform, a next-generation heterogeneous sensor node platform equipped with both a low-end microcontroller (MSP430) and a higher-end embedded systems processor (ARM). Experimental results show that the total energy consumption of mPlatform, when processing data flows at their optimal batching periods, is up to 35% lower than that for uniform period assignment. Moreover, processing data at the appropriate processor can use as much as 80% less energy than running the same task set on the ARM alone and 25% less energy than running the task set on the MSP430 alone.     

异构多核上多级并行模型支持及性能优化

低功耗及廉价性使得异构多核在超级计算机计算资源中占有重要比例.然而,异构多核具有高带宽及松耦合一致性等特点,获得理想的存储及计算性能需要更多地考虑底层硬件细节.实现了一种针对典型的异构多核Cell BE 处理器的多级并行模型CellMLP,通过C 语言扩展编译指导语句,实现了对数据并行、任务并行以及流水并行编程模型的支持,提高了并行程序生产率.运行支持优化方面,数据并行采用SPE 并行数据传输、双缓冲等优化手段来提高数据传输带宽;任务并行使用一种新式混合任务队列以支持异步任务窃取,降低SPE 线程间竞争,提高了任务并行的可扩展性;流水并行首次使用阻塞信号传输机制实现SPE 线程间的低开销同步操作.实验对Stream,NASBenchmark 及BOTS 等应用进行了测试,结果表明,CellMLP 可对多种典型并行应用进行高效支持.与目前同类编程模型SARC 及CellSs 进行性能对比,其结果表明,CellMLP 实际数据传输带宽以及非规则应用的支持方面具有明显优势.