一种基于异构系统的实时调度算法研究

高效调度是异构系统中实现高性能计算的关键.调度问题已经被证明是NP完全问题,由于其关键性,调度问题已经被国内外研究机构广泛研究,并提出了多种算法.尽管在一些文献中提出了异构多处理器的调度算法,但是这些算法的调度成本较高,并且在较低的调度成本下无法提供高质量的调度.本文提出一种最小评分优先算法(HMSF),该算法是一种适用于异构系统的高性能、快速调度算法,通过和传统的HEFT算法和DLS算法进行试验对比发现,HMSF算法可以使调度长度更短.     

冷冻电镜三维重构在CPU-GPU系统中的并行性

为了有效地发掘和利用异构系统在应用和体系结构上的并行性,以冷冻电镜三维重构为例展示如何利用应用程序潜在的并行性.通过分析重构计算所有的并行性,实现了将动态自适应的划分算法用于任务在异构系统上高效的分发.在曙光星云系统的部分节点系统(32节点)上评估并行化的程序性能.实验证明:多层次的并行化是CPU与GPU异构系统上开发并行性的有效模式;CPU-GPU混合程序在给定问题规模上相对单纯CPU程序获得2.4倍加速比.     

异构计算系统的表调度式任务映射与调度算法

研究了在异构计算系统（ＨＣＳ）中利用表调度式算法进行任务映射与调度．给出两种异构静态优先级表调度式任务映射算法（ＨＳＰ和ＧＨＳＰ）,以及一种异构动态优先级表调度式任务映射算法（ＢＨＤＰ）．实验结果表明,ＧＨＳＰ算法对于粗中粒度ＤＡＧ的调度效果稍好于ＨＳＰ算法,而ＢＨＤＰ算法对于粗粒度和细粒度ＤＡＧ的调度效果均明显优于ＨＳＰ和ＧＨＳＰ算法．     

求循环体相关图关键路径的算法

应用循环体相关图分析循环程序的并行性对于发掘程序的并行性有重要意义,求循环体相关图的关键路径则是作这一分析的关键步骤．由于求循环体相关图的关键路径不同于求一般ＡＯＥ网的关键路径,无法直接使用已有的有关算法．为此,本文给出了一个求循环相关图的关键路径的算法,并讨论了其应用价值．     

蚁群算法在车间调度问题中的应用

提出用蚁群算法求解车间调度问题.车间调度问题是典型的非确定性多项式时间难问题,蚁群算法是一种分布式进化计算方法,具有鲁棒性,正反馈,并行性等特点,而且算法简单.给出了用蚁群算法求解车间调度问题的流程,并且用经典的JSP的样例对算法进行了测试,实验结果表明用蚁群算法可以求解得到车间调度问题的最优解或近似最优解.     

并行编译中的区域调度问题

介绍指令级并行性(ILP)中和指令级计算(EPIC)中区域的直观概念和这些概念的形式化工作，并简单介绍区域的几个调度算法，为并行编译中的区域调度问题提供一个系统的、形式化的论述。     

异构任务图的实现模型

任意异构程序映射到任意异松系统上执行,是并行程序计算最复杂的情况,为此提出了异构任务图的定义,它是异构程度直观和有效描述方法,还研究了异构任务图的实现模型,它是异构计算环境中软件和硬件的桥梁,分别给出了任务图的分簇算法、系统图的分簇算法和映射算法及应用实例,利用该模型可设计出可移植的并行程序,然后调度到可动态配置的异构计算机组织上运行。     

基于网格任务调度的Monte Carlo仿真建模

网格系统是异构和动态分布系统,其节点的计算能力存在差异。在多个节点共同完成任务时,容易产生计算瓶颈,影响计算吞吐量和造成延迟,甚至导致整个任务失败。利用Monte Carlo仿真的自然并行性,解决了网格任务调度问题,设计了基于网格的Monte Carlo仿真流程框架和节点状态机模型。在此基础上,建立了“N-M”调度策略的二项式概率模型,并在不同的参数条件下对Monte Carlo仿真任务的性能进行了测试和分析,结果验证了设计方案的有效性。     

面向GPU异构集群的自学习负载均衡调度算法

由于GPU的高性能计算能力,越来越多地被用于集群系统中,但同时也给集群带来节点级的异构问题,使原来适用于同构集群的调度算法在异构集群中性能大大降低。为使异构节点间的负载均衡,降低总的作业执行时间,提出了一个面向GPU异构集群的自学习负载均衡调度算法。首先对Torque调度器进行扩展,使其支持GPU作业调度,然后将提出的自学习调度算法在Rocks操作系统及Torque调度器软件中实现。真实物理集群上的实验结果表明,扩展后的Torque调度器很好地支持GPU任务的调度,自学习调度算法较原来的Torque调度算法能达到更好的负载均衡。     

星载计算机系统高优先级恢复容错调度算法

为了在星载异构容错计算机上调度星载任务，在给出了星载计算机系统的容错调度模型的基础上，提出了一种星载计算机系统高优先级恢复容错调度算法（OHFSA），该算法通过引进可靠性代价量化了容错系统在维护容错调度时所需要的开销，并在调度过程中充分考虑了容错调度的实时性和低可靠性代价．同时，采用高优先级恢复机制可及时响应紧急时限下的恢复任务，从而提高了星载任务的整体实时性能．实验验证表明，OHFSA随着计算时间的增加，其所需的可靠性代价也相应增大．仿真结果表明，在任务负载不断增加的情况下，OHFSA的执行时间比目前算法减少20%～30%，特别是在恢复任务优先级比其主任务提高1个级别时，响应时间可减少近8．7%．     

An improvement on algorithm of grid-workflow based on QoS

With the emergencc of grid computing. new challenges have arisen in workflow tasks scheduling. The goal of grid-workflow task scheduling is to achieve high system throughput and to match the application needs with the available computing resources. This matching of resources in a non-deterministically share heterogeneous environment leads to concerns on quality of service (QoS). Grid concept is presented in this paper, coupled with the QoS requirement of workflow task and an improved algorithm-ILGSS algorithm. has been brought out. The complexity of the improved sched uling algorithm has been analyzed. The experiment results show that the improved algorithm can lead to significant performance gain in various applicatkms. An important research domain adaptive workflow transaction in grid computing environment, has been explored and a new solution for the scheduling of distribute workflow has been hring forward in grid environment.     

云计算下多源异构大数据跨源调度算法研究

针对云计算下的多源异构大数据,需要耗费大量时间对其进行传输,当前调度算法大多通过启发式算法实现大数据调度,加速比和吞吐量较低,负载均衡性不佳。为此,提出一种新的云计算下多源异构大数据跨源调度算法,为了降低计算开销,在调度前首先进行预取操作。在此基础上,对全部变量进行更新处理,将所有待调度多源异构子流的质量看作子流权重进行排列,从传输窗口中还存在剩余待调度多源异构子流中选择质量最佳的子流传输数据,直至全部待调度多源异构子流均被处理过。实验结果表明,所提算法加速比和吞吐量高,且负载均衡性好。     

一种可调节动态任务调度算法

提出了适于异构环境独立任务调度的可调节动态调度算法(AS算法)。该算法以任务与处理机的执行时间和完成时间作为参数共同构造任务调度顺序的衡量值,其中二者所占的比重能进行适当调整。AS算法克服了Min-min算法单纯追求局部最优的局限性,更适合异构环境。实验结果表明AS算法可以有效地降低调度跨度,其性能比Min-min算法有所提高。     

粗粒度异构预编译器的设计与实现

提出了一种基于用户指导法的异构计算的动态实现工具,称为粗粒度异构预编译器（ＣＨＰ）,定义了５种用户在并行编程时需显式说明的代码段的类型,以及用户对代码段的输入和输出参数需进行的说明。     

UMA模型上不均匀循环的自适应混合调度

不均匀循环的调度分配是并行计算中最经常遇到的问题。采用动态调度势必增加额外开销,纯采用静态调度又很难保证各处理器的负载平衡。本通过引入静态块和动态块的概念,提出了在ＵＭＡ（Ｕｎｉｆｏｒｍ Ｍｅｍｏｒｙ Ａｃｃｅｓｓ）模型上把静态调度和动态调度结合起来使用的自适应混合调度ＡＨＳ（Ａｄａｐｔｉｖｅ Ｈｙｂｒｉｄ Ｓｃｈｅｄｕｌｉｎｇ）算法,并给出了在曙光一号多处理机上的一些实验结果。     

异构任务图在网格环境中的调度实现

并行分布计算环境的任务调度一直是并行计算研究的热点问题，网格技术的发展则对任务调度提出了新的要求。本文采用带参数的有向超图表达异构任务图，为具有一般性、异构性、分布性、动态性等特点的任务请求提供了通用描述方法。通过设计网格异构任务图描述语言GHDL，实现了网格任务请求的统一封装以及任务请求在异构环境下的计算机理解和识别。通过设计自适应调度策略库，为分布异构动态网格环境下的任务调度提供有效解决方案，实现了在考虑网格任务间优先约束与数据关联的同时，采取异构宿主机识别、异构客户端自动创建等方式开发利用环境异构性与任务异构性，采取实时网格状态信息采集与任务迁移屏蔽了资源动态性。异构任务图在网格环境中的调度效果由树生长的仿真实验进行了展示。     

异构环境下基于任务交互图的调度算法

针对异构环境下任务图为TIG（task interaction graph）的问题，利用松弛标记法善于利用邻居属性处理大量约束的特点，提出一种任务调度算法．算法把任务看作目标对象，处理器单元看作待分配标记，根据对象间所有可能关系，逐渐排除不相关的处理器单元，选择计算和通信综合性能较好的处理器单元．在兼顾任务执行的计算和通信需求的情况下，能够合理分配资源、提高处理速度、缩短整个应用程序的执行时间．实验结果与用穷举法得出的最优结果比较显示，本算法能较理想地解决异构环境下基于任务交互图的调度问题．     

An Energy-Saving Task Scheduling Strategy Based on Vacation Queuing Theory in Cloud Computing

High energy consumption is one of the key issues of cloud computing systems. Incoming jobs in cloud computing environments have the nature of randomness, and compute nodes have to be powered on all the time to await incoming tasks. This results in a great waste of energy. An energy-saving task scheduling algorithm based on the vacation queuing model for cloud computing systems is proposed in this paper. First, we use the vacation queuing model with exhaustive service to model the task schedule of a heterogeneous cloud computing system.Next, based on the busy period and busy cycle under steady state, we analyze the expectations of task sojourn time and energy consumption of compute nodes in the heterogeneous cloud computing system. Subsequently, we propose a task scheduling algorithm based on similar tasks to reduce the energy consumption. Simulation results show that the proposed algorithm can reduce the energy consumption of the cloud computing system effectively while meeting the task performance.     

Research on logistics domain-oriented cloud resource management model and architecture

To address the challenges posed by resource shortage or surplus to enterprises productivity,Internet platforms have been widely used,which can balance shortage and surplus in broader environments.However,the existing resource management models lack openness,sharing ability and scalability,which make it difficult for many heterogeneous resources to co-exist in the same system.It is also difficult to resolve the conflicts between distributed self-management and centralized scheduling in the system.This paper analyzes the characteristics of resources in the distributed environment and proposes a new resource management architecture by considering the resource aggregation capacity of cloud computing.The architecture includes a universal resource scheduling optimization model which has been applied successfully in double-district multi-ship-scheduling multi-container-yard empty containers transporting of international shipping logistics.Applications in all these domains prove that this new resource management architecture is feasible and can achieve the expected effect.