实时嵌入式异构环境下多优先级混合任务调度动态策略

针对现有异构环境下的调度策略,引入迫切密度和剩余价值密度,分析迫切密度和剩余价值密度调节任务执行紧急程度的影响、对优先级制定,通过构建单有向无环图（ DAG）系统模型实现了混合任务的动态调度。仿真实验结果表明：该调度策略在系统负载较高的情况下,仍有较优的任务执行效能和避免颠簸现象。     

异构分布系统的实时任务轮转式容错调度算法

建立了一个异构分布式系统实时调度模型,对异构分布式系统中的任务及不同处理机资源进行了形式化描述.结合基版本/副版本技术,给出了用于异构分布式系统的实时任务轮转式容错调度算法.实例分析表明,该算法有效提高了异构处理机环境下的资源利用率以及整体计算性能.     

异构环境下增强的自适应MapReduce调度算法

针对Hadoop默认调度算法和异构环境下LATE调度算法的不足,在SAMR调度算法的基础上提出了一种增强的自适应MapReduce调度算法。该算法记录了每个节点的历史信息,采用K-means聚类算法动态地调整阶段进度值以找到真正需要启动备份的落后任务。实验结果表明,增强自适应的MapReduce调度算法在提高任务执行时间的估算误差以及准确识别慢任务方面具有一定的有效性。     

Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment

In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. To maximize the performance of the system, it is essential to assign the resources to tasks (match) and order the execution of tasks on each resource (schedule) to exploit the heterogeneity of the resources and tasks. Dynamic mapping (defined as matching and scheduling) is performed when the arrival of tasks is not known a priori. In the heterogeneous environment considered in this study, tasks arrive randomly, tasks are independent (i.e., no inter-task communication), and tasks have priorities and multiple soft deadlines. The value of a task is calculated based on the priority of the task and the completion time of the task with respect to its deadlines. The goal of a dynamic mapping heuristic in this research is to maximize the value accrued of completed tasks in a given interval of time. This research proposes, evaluates, and compares eight dynamic mapping heuristics. Two static mapping schemes (all arrival information of tasks are known) are designed also for comparison. The performance of the best heuristics is 84% of a calculated upper bound for the scenarios considered.     

网格任务调度方法研究

网格计算中的关键问题之一是计算任务在各个资源之间的调度。提出了基于量子遗传算法（QGA）的网格任务调度算法,以减少调度时间为主要目标,增加资源利用率为次要目标。该算法采用量子比特间接编码的方式,通过有向无环图（DAG）来描述子任务间的依赖关系,根据深度值来给子任务的执行顺序进行排序。仿真结果显示,无论是任务完成时间还是资源利用率,此方法都明显优于基于遗传算法（GA）的网格调度算法。     

Adaptive energy-efficient scheduling for real-time tasks on DVS-enabled heterogeneous clusters

Developing energy-efficient clusters not only can reduce power electricity cost but also can improve system reliability. Existing scheduling strategies developed for energy-efficient clusters conserve energy at the cost of performance. The performance problem becomes especially apparent when cluster computing systems are heavily loaded. To address this issue, we propose in this paper a novel scheduling strategy–adaptive energy-efficient scheduling or AEES–for aperiodic and independent real-time tasks on heterogeneous clusters with dynamic voltage scaling. The AEES scheme aims to adaptively adjust voltages according to the workload conditions of a cluster, thereby making the best trade-offs between energy conservation and schedulability. When the cluster is heavily loaded, AEES considers voltage levels of both new tasks and running tasks to meet tasks’ deadlines. Under light load, AEES aggressively reduces the voltage levels to conserve energy while maintaining higher guarantee ratios. We conducted extensive experiments to compare AEES with an existing algorithm–MEG, as well as two baseline algorithms–MELV, MEHV. Experimental results show that AEES significantly improves the scheduling quality of MELV, MEHV and MEG.     

Multi-phase integrated scheduling of hybrid tasks in cloud manufacturing environment

Cloud manufacturing paradigm aims at gathering distributed manufacturing resources and enterprises to serve for more customized production. Production order which involving several tasks can be taken by distributed suppliers collaboratively at lower cost. The cloud manufacturing platform is responsible for not only arranging reasonable priorities, suitable suppliers, and production processes to multiple orders, but also scheduling hybrid tasks from different orders to manufacturing resources. To maximize the production efficiency and balance the trade-off among different production orders, this paper studies multi-phase integrated scheduling of hybrid tasks in cloud manufacturing environment, which containing order priority assignment, supplier and production process selection, and production line scheduling. Five key objectives are taken into account to analyze the interconnections among different resources and production processes. Six representative multi-objective evolutionary algorithms are adopted to solve the integrated scheduling problem. Experimental results on six production cases show that integrated scheduling is more effective than the traditional step-by-step decision, leading to less production cost and time. In addition, a comparison among the six algorithms is carried out to determine the one best suited for the integrated scheduling problem in different circumstances.     

实时任务在异构集群中的自适应容错调度研究

异构集群由于良好的扩展性和可用性,逐渐成为当前并行计算的热点。在具有实时性要求的异构集群中,调度是提高系统性能的关键所在。在此提出了两种自适应调度算法SANOL和SAOL,在保证异构集群中任务的实时性和容错性的前提下,自适应地根据系统的负载情况动态地调整任务的服务级别,从而提高整个系统的灵活性、可调度性和资源利用率。通过实验将这两种算法与另外一种有效率的调度算法DYFARS算法进行比较,结果表明所提出的SAOL算法具有更好的性能。     

PASTA: a power-aware solution to scheduling of precedence-constrained tasks on heterogeneous computing resources

Power efficiency is one of the main challenges in large-scale distributed systems such as datacenters, Grids, and Clouds. One can study the scheduling of applications in such large-scale distributed systems by representing applications as a set of precedence-constrained tasks and modeling them by a Directed Acyclic Graph. In this paper we address the problem of scheduling a set of tasks with precedence constraints on a heterogeneous set of Computing Resources (CRs) with the dual objective of minimizing the overall makespan and reducing the aggregate power consumption of CRs. Most of the related works in this area use Dynamic Voltage and Frequency Scaling (DVFS) approach to achieve these objectives. However, DVFS requires special hardware support that may not be available on all processors in large-scale distributed systems. In contrast, we propose a novel two-phase solution called PASTA that does not require any special hardware support. In its first phase, it uses a novel algorithm to select a subset of available CRs for running an application that can balance between lower overall power consumption of CRs and shorter makespan of application task schedules. In its second phase, it uses a low-complexity power-aware algorithm that creates a schedule for running application tasks on the selected CRs. We show that the overall time complexity of PASTA is $O(p.v^{2})$ where $p$ is the number of CRs and $v$ is the number of tasks. By using simulative experiments on real-world task graphs, we show that the makespan of schedules produced by PASTA are approximately 20 % longer than the ones produced by the well-known HEFT algorithm. However, the schedules produced by PASTA consume nearly 60 % less energy than those produced by HEFT. Empirical experiments on a physical test-bed confirm the power efficiency of PASTA in comparison with HEFT too.     

Heuristics for scheduling file-sharing tasks on heterogeneous systems with distributed repositories

We consider the problem of scheduling an application on a computing system consisting of heterogeneous processors and data repositories. The application consists of a large number of file-sharing otherwise independent tasks. The files initially reside on the repositories. The processors and the repositories are connected through a heterogeneous interconnection network. Our aim is to assign the tasks to the processors, to schedule the file transfers from the repositories, and to schedule the executions of tasks on each processor in such a way that the turnaround time is minimized. We propose a heuristic composed of three phases: initial task assignment, task assignment refinement, and execution ordering. We experimentally compare the proposed heuristics with three well-known heuristics on a large number of problem instances. The proposed heuristic runs considerably faster than the existing heuristics and obtains 10–14% better turnaround times than the best of the three existing heuristics.     

异构环境下降低慢任务抖动的调度算法——DPST

为解决在异构计算环境中现有的云计算负载均衡算法存在的慢任务频繁抖动的问题,提出了一种能减低慢任务调度抖动概率的算法--DPST算法。首先通过定义一种异构计算节点中异构任务的能力度量,对执行异构任务的节点处理能力进行了归一化;然后通过引入节点能力预判机制,降低慢任务无效调度的次数;并且利用慢任务和慢节点双队列机制,提高了调度效率。实验结果表明,DPST相对于Hadoop平台在异构环境下任务调度的抖动次数下降了40%以上。由于有效降低了任务调度的抖动次数,在异构环境中DPST算法能明显地缩短任务的平均响应时间并提高系统的吞吐量。     

用于多核嵌入式环境的硬实时任务感功调度算法

充分考虑当前CMOS多核嵌入式处理器片上仅提供全局动态电压缩放(DVS)支持以及亚纳米时代后CMOS处理器泄露功耗不可忽视的现状,提出一种新的多核嵌入式环境中的硬实时任务感功调度算法GRR&CS。算法通过基于贪心法的静态任务划分,基于全局资源回收利用和任务迁移的动态负载均衡,以及动态核缩放三个步骤实现整体能耗的降低,并同时保证实时任务的可调度性约束。实验表明,提出的算法相比较现有算法多节省14.8%~41.2%的能耗。     

异构环境中Fork-Join任务图的调度算法

目前已有的Fork-Join任务图的调度算法大多假定处理机为同构的,而没有考虑实际应用中处理机的异构性以及节省处理机的问题,导致算法在具体应用中效率较低.因此,对Fork-Join任务图的调度问题进行研究,提出了一个基于异构环境的贪心调度算法,该算法具有高的加速比和总体效率,其时间复杂度为O(v~2),其中,v表示任务集中任务的个数.实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性.     

Energy-aware scheduling algorithm for time-constrained workflow tasks in DVFS-enabled cloud environment

Energy consumption in cloud data centers is increasing as the use of such services increases. It is necessary to propose new methods of decreasing energy consumption. Green cloud computing helps to reduce energy consumption and significantly decreases both operating costs and greenhouse gas emissions. Scheduling the enormous number of user-submitted workflow tasks is an important aspect of cloud computing. Resources in cloud data centers should compute these tasks using energy efficient techniques. This paper proposed a new energy-aware scheduling algorithm for time-constrained workflow tasks using the DVFS method in which the host reduces the operating frequency using different voltage levels. The goal of this research is to reduce energy consumption and SLA violations and improve resource utilization. The simulation results show that the proposed method performs more efficiently when evaluating metrics such as energy utilization, average execution time, average resource utilization and average SLA violation.     

异构环境下MapReduce动态任务调度技术研究

针对MapReduce在异构环境下各节点性能不均衡,导致整体计算效率低下的问题进行了研究。为此,从节点与任务两方面入手,提出了一种将节点性能量化并排序与将任务按相似度划分相结合的算法。该方法首先根据历史日志以及实时回传的日志信息将节点按照性能高低排序;然后根据任务执行完成的信息,将其与新任务进行比对得到相似度,从而推测出新任务的执行时间,执行时间长的认为是复杂的任务;最后进行动态调度,使高性能节点处理更复杂的任务。在随机生成数据集上的实验结果表明,所提出的动态调度算法与默认调度算法相比,数据集为20G大小时执行速度提高27.4%,数据集为100G大小时执行速度提高了74.1%。     

基于人工鱼群遗传算法的异构多核系统任务调度研究

异构多核系统的任务调度问题已经被证明是一个NP完全问题。人工鱼群算法在算法初期具有较快的收敛速度,后期收敛较慢,而遗传算法的种群初始化具有较强的鲁棒性,初始化种群的质量直接影响着遗传算法的性能。本文提出了一种将人工鱼群算法与遗传算法相结合的任务调度算法,首先分析了异构多核系统的任务调度问题的本质,使用改进的人工鱼群算法来构建遗传算法的初始化种群,并使用改进的遗传算法进行迭代进化,从而提高了算法的收敛速度。     

A security and cost aware scheduling algorithm for heterogeneous tasks of scientific workflow in clouds

Security is increasingly critical for various scientific workflows that are big data applications and typically take quite amount of time being executed on large-scale distributed infrastructures. Cloud computing platform is such an infrastructure that can enable dynamic resource scaling on demand. Nevertheless, based on pay-per-use and hourly-based pricing model, users should pay attention to the cost incurred by renting virtual machines (VMs) from cloud data centers. Meanwhile, workflow tasks are generally heterogeneous and require different instance series (i.e., computing optimized, memory optimized, storage optimized, etc.). In this paper, we propose a security and cost aware scheduling (SCAS) algorithm for heterogeneous tasks of scientific workflow in clouds. Our proposed algorithm is based on the meta-heuristic optimization technique, particle swarm optimization (PSO), the coding strategy of which is devised to minimize the total workflow execution cost while meeting the deadline and risk rate constraints. Extensive experiments using three real-world scientific workflow applications, as well as CloudSim simulation framework, demonstrate the effectiveness and practicality of our algorithm.     

Authentication in a heterogeneous environment

This paper considers how a mechanism might be set up to provide authentication of users and servers. The scheme proposed aims to deal with simple processors which are unmanaged, as well as managed timesharing systems. It would provide authentication tokens which can be included in the applications protocols. Much of the difficulty of the scheme is concerned with building a distributed secure database for private keys.