Advanced Wavelength Reservation Method Based on Deadline-Aware Scheduling for Lambda Grid Networks

A deadline-aware-scheduling scheme for the lambda grid system is proposed to support a huge computer grid system based on an advanced photonic network technology. The assignment of wavelengths to jobs in order to efficiently carry various services is critical in lambda grid networks. Such services have different requirements such as the job-completion deadlines, and wavelength assignment must consider the job deadlines. The conventional job scheduling approach assigns a lot of time slots to a call within a short period in order to finish the job as quickly as possible. This raises the blocking probability of short deadline calls. Our proposal assigns wavelengths in the lambda grid networks to meet quality-of-services guarantees. The proposed scheme assigns time slots to a call over time according to its deadline, which allows it to increase the system performance in handling short deadline calls, for example, lowering their blocking probability. Computer simulations show that the proposed scheme can reduce the blocking probability by a factor of 100 compared with the conventional scheme under the low load condition in which the ratio of long deadline calls is high. The proposed scheduling scheme can realize more efficient lambda grid networks.     

An agent‐based workflow scheduling mechanism with deadline constraint on hybrid cloud environment

Summary

With the advances of cloud computing, business and scientific‐oriented jobs with certain workflows are increasingly migrated to and run on a variety of cloud environments. These jobs are often with the property of deadline constraint and have to be completed within limited time. Therefore, to schedule a job with workflow (short for workflow) with deadline constraint is increasingly becoming a crucial research issue. In this paper, we, based on previous work, propose an agent‐based workflow scheduling mechanism to schedule workflows that are with deadline constraint into federated cloud environment.

Design and Methods

We add a workflow agent into the original framework to schedule the deadline‐constraint workflow. The workflow agent can smoothly schedule workflows to the cloud system according to their required resource and automatically monitor their execution. In order to accurately predict the execution time of each task to meet deadline constraint on certain VM with given resource, we inherit the use of rough set theory to estimate execution time of task in our previous work.

Result and Discussion

A heuristic algorithm that is embedded into the workflow agent is also proposed because the problem had been shown to be NP‐complete. The mechanism also adopts dynamic job dispatching method to reduce the usage of VM and to improve the resource utilization. We also conducted experiments to evaluate the efficiency and effectiveness.

Conclusion

The experimental results show that the prediction time is very close to the real execution time and can efficiently schedule multiple scientific workflows to meet the deadline constraints simultaneously.     

Multicriteria decision‐making techniques for avoiding similar task scheduling conflict in cloud computing

An efficient task scheduling approach shows promising way to achieve better resource utilization in cloud computing. Various task scheduling approaches with optimization and decision‐making techniques have been discussed up to now. These approaches ignored scheduling conflict among the similar tasks. The conflict often leads to miss the deadlines of the tasks. The work studies the implementation of the MCDM (multicriteria decision‐making) techniques in backfilling algorithm to execute deadline‐based tasks in cloud computing. In general, the tasks are selected as backfill tasks, whose role is to provide ideal resources to other tasks in the backfilling approach. The selection of the backfill task is challenging one, when there are similar tasks. It creates conflict in the scheduling. In cloud computing, the deadline‐based tasks have multiple parameters such as arrival time, number of VMs (virtual machines), start time, duration of execution, and deadline. In this work, we present the deadline‐based task scheduling algorithm as an MCDM problem and discuss the MCDM techniques: AHP (Analytical Hierarchy Process), VIKOR (VIseKriterijumska Optimizacija I Kompromisno Resenje), and TOPSIS (Technique for Order Preference by Similarity to Ideal Solution) to avoid similar task scheduling conflicts. We simulate the backfilling algorithm along with three MCDM mechanisms to avoid scheduling conflicts among the similar tasks. The synthetic workloads are considered to study the performance of the proposed scheduling algorithm. The mechanism suggests an efficient VM allocation and its utilization for deadline‐based tasks in the cloud environment.     

截止期限约束的实例密集型云服务流调度算法

针对商业云计算中存在大量实例密集型服务流的问题,提出一种新的云环境下两阶段服务流调度算法。该算法先将用户自定义的全局截止期限分配到系统中的每个实例,再将每个实例的截止期限分配到实例中的每个任务中,最后在服务流执行阶段,动态调整后续任务的截止期限,解决了任务可能存在的未能在其截止期限内完成的时间异常问题。CloudSim仿真结果表明,与现有的算法相比,该算法能满足用户定义的截止期限,节约了执行成本,并减少了资源的竞争率,提高了调度的成功率。     

Reward-based voltage scheduling for dynamic-priority hard real-time systems

Reward-based scheduling has been investigated for flexible applications in which an approximate but timely result is acceptable. Meanwhile, significant research efforts have been made on voltage scheduling which exploits the tradeoff between the processor speed and the energy consumption. In this paper, we address the combined scheduling problem of maximizing the total reward of hard real-time systems with a given energy budget. We present an optimal off-line algorithm and an efficient on-line algorithm for jobs with their own release-times/deadlines under Earliest-Deadline-First (EDF) scheduling. Experimental results show that the solution computed by the on-line algorithm is no more than 14% worse than the theoretical optimal solution obtained by the optimal off-line algorithm. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment). A preliminary version of this article was presented at Real-Time and Embedded Computing Systems and Applications (RTCSA’04).     

最早截止期优先算法在CAN FD网络中的改进

针对应用于CAN FD网络中的调度算法,平均分区编码方式的最早截止期算法对报文进行非抢占调度时,其对大范围的截止期编码能力有限,报文易出现较大概率优先级反转以及总线负载较高等问题。通过分析造成报文传递延迟的各种原因并结合之前相关分区调度算法的不足,文中提出了基于指数–幂函数分区的最早截止期优先算法对报文进行调度的改进方式,即在对报文的截止期进行指数分区的基础上,进一步采用幂函数分区细分。文中对该算法的可调度性进行了分析,并使用CANoe进行了仿真验证。实验表明,与现有的平均分区调度算法相比,改进后的算法扩大了截止期的表示范围,降低了总线负载,优化了优先级反转问题,达到了更好的调度效果。     

数字阵列雷达波束驻留调度间隔分析算法

针对数字阵列雷达波束驻留调度问题,研究了基于调度间隔分析的调度算法。该算法综合分析了1个调度间隔内申请执行的波束驻留任务,且调度过程中进行了脉冲交错。调度准则充分考虑了任务的工作方式优先级和截止期,并以任务丢失率、实现价值率、系统时间利用率作为评估指标。仿真结果表明修正截止期准则主要强调任务的紧迫性,修正工作方式优先级主要强调任务的重要性,而截止期—工作方式优先级和工作方式—截止期调度准则可以在二者间更好地折中,在总体性能上要优于其他调度准则。     

Evaluation of Level of Confidence and Optimization of Roll-back Recovery with Checkpointing for Real-Time Systems

Increasing soft error rates for semiconductor devices manufactured in later technologies enforce the usage of fault tolerant techniques such as Roll-back Recovery with Checkpointing (RRC). As RRC introduces time overhead that increases the completion (execution) time, time constraints (deadlines) might be violated. This is a drawback for a class of computer systems where the correct operation is defined not only by providing the correct outcome of an operation but also by ensuring that the deadlines are met. These computer systems are referred to as real-time systems (RTSs). In general RTSs are classified as soft and hard RTSs depending on the consequences of violating the deadlines. For soft RTSs, where consequences of violating the deadlines are not very severe, research have focused on optimizing RRC and shown that it is possible to find the optimal number of checkpoints such that the average execution time (AET) is minimal. While minimal AET is important for soft RTSs, it is more important to provide a high probability that deadlines are met for hard RTSs, where consequences of violating the deadlines may be catastrophic. Hence, there is a need of probabilistic guarantees that jobs employing RRC complete before a given deadline. Traditionally, AET analysis have been used for soft RTSs and worst case execution time (WCET) analysis along with schedule feasibility have been used for hard RTSs. In this paper we introduce a reliability metric, Level of Confidence (LoC), which is equally applicable to both soft and hard RTS. LoC is used as a metric to evaluate to what extent a deadline is met. The main contributions of this paper are as follows. First, we present a mathematical framework for the evaluation of LoC when RRC is employed. Second, we provide a proof to verify the correctness of the proposed expression. Third, in the context of hard RTSs, we provide a method to obtain the optimal number of checkpoints that maximizes the LoC. Fourth, in the context of soft RTSs where the maximal LoC may not be needed, but instead some LoC requirement is needed, we present an optimization method for RRC that finds the number of checkpoints that results in the minimal completion time while the minimal completion time satisfies a given LoC requirement. Fifth, we use the proposed framework to evaluate and compare probabilistic guarantees when RRC is optimized towards soft RTSs.     

Component-placement optimization for convectively cooledelectronics

A discussion is presented of the optimum positioning of a sequence of convectively cooled electronic devices in order to reduce failures due to thermal factors. A set of equations is developed for optimizing the positioning of the devices. This problem is analogous to the classical operations research problem of the optimum time scheduling of several jobs on a single machine, where for each job there is a time-dependent completion penalty. Several solution techniques for solving the simplified problem are formulated and compared with respect to their accuracy and computational speed     

Guaranteed Dynamic Priority Assignment Schemes for Real‐Time Tasks with (m,k)‐Firm Deadlines

We present guaranteed dynamic priority assignment schemes for multiple real‐time tasks subject to (m, k)‐firm deadlines. The proposed schemes have two scheduling objectives: providing a bounded probability of missing (m, k)‐firm constraints and maximizing the probability of deadline satisfactions. The second scheduling objective is especially necessary in order to provide the best quality of service as well as to satisfy the minimum requirements expressed by (m, k)‐firm deadlines. We analytically establish that the proposed schemes provide a guarantee on the bounded probability of missing (m, k)‐firm constraints. Experimental studies validate our analytical results and confirm the effectiveness and superiority of the proposed schemes with regard to their scheduling objectives.     

基于蚂蚁算法的网格作业调度研究

网格环境下的作业调度是一个NP难问题,蚂蚁算法内在的并行性和可扩充性使其非常适合网格作业调度。将蚂蚁算法应用于网格环境作业调度,提出一种通过作业代理的移动进行网格作业调度的方案,该蚂蚁算法不仅在分配网格计算资源时进行信息素的局部更新,还在网格计算资源完成作业后进行信息素的整体更新。通过模拟实验测试和选取蚂蚁算法的各种影响参数,取得了比较理想的实验结果。实验证明该算法能够有效地实现作业的合理调度和网格系统的负载平衡。     

Instruction scheduling with k-successor tree for clustered VLIW processors

Clustering is a well-known technique for improving the scalability of classical VLIW (Very Long Instruction Word) processors. A clustered VLIW processor consists of multiple clusters. Each cluster has a local register file and a set of functional units. This paper proposes a novel phase coupled, priority-based heuristic for scheduling a set of operations in a basic block on a clustered VLIW processor. Our heuristic converts the instruction scheduling problem to the problem of scheduling a set of operations with a common deadline. The priority of each operation v _i is the l _max (v _i )-successor-tree-consistent deadline. This deadline is the upper bound on the latest completion time of v _i in any feasible schedule for a relaxed problem where the precedence-latency constraints only between v _i and all its successors are considered. We have simulated our heuristic and the Integrated heuristic on the 808 basic blocks taken from the MediaBench II benchmark suite using three processor models. On average, for the three processor models, our heuristic improves over the Integrated heuristic by 13 %, 18 %, 16 %, respectively.     

An Efficient Packet Scheduling Algorithm With Deadline Guarantees for Input-Queued Switches

Input-queued (IQ) switches overcome the scalability problem suffered by output-queued switches. In order to provide differential quality of services (QoS), we need to efficiently schedule a set of incoming packets so that every packet can be transferred to its destined output port before its deadline. If no such a schedule exists, we wish to find one that allows a maximum number of packets to meet their deadlines. Recently, this problem has been proved to be NP-complete if three or more distinct deadlines (classes) are present in the set. In this paper, we propose a novel algorithm named Flow-based Iterative Packet Scheduling (FIPS) for this scheduling problem. A key component in FIPS is a non-trivial algorithm that solves the problem for the case where two classes are present in the packet set. By repeatedly applying the algorithm for two classes, we solve the general case of an arbitrary number of classes more efficiently. Applying FIPS to a frame-based model effectively achieves differential QoS provision in IQ switches. Using simulations, we have compared FIPS performance with five well-known existing heuristic algorithms including Earliest-Deadline-First (EDF), Minimum-Laxity-First (MLF) and their variants. The simulation results demonstrate that our new algorithm solves the deadline guaranteed packet scheduling problem with a much higher success rate and a much lower packet drop ratio than all other algorithms     

进化规划方法在最小化拖期任务数并行机调度问题中的应用

随着ＣＩＭＳ技术的发展,生产线调度问题的研究显得日益重要,最小化拖用期任务数并行机调度问题是一类重要的生产线调度问题,但迄今为止,在解决工件和机器数较多的大规模并行机调度问题还存在着许多困难,进化规划方法与遗传算法一样是一种重要的进化计算方法,它具有描述简单,使用灵活,运行效率高,鲁棒性强,较少受初始条件限制等优点,这使得它有很高的实用价值,但与遗传算法相比,进化规划方法的应用还刚刚开始,特别是在     

Resource allocation for real-time traffic in unreliable wireless cellular networks

Providing reliable transmission for real-time traffic in wireless cellular networks is a great challenge due to the unreliable wireless links. This paper concentrates on the resource allocation problem aiming to improve the real-time throughput. First, the resource allocation problem is formulated as a Markov Decision Process and thus the optimal resource allocation policy could be obtained by adopting the value iteration algorithm. Considering the high time complexity of the optimal algorithm, we further propose an approximate algorithm which decomposes the resource allocation problem into two subproblems, namely link scheduling problem and packet scheduling problem. By this method, the unreliable wireless links are only constrained in the link scheduling problem, and we can focus on the real-time requirement of traffic in packet scheduling problem. For the link scheduling problem, we propose the maxRel algorithm to maximize the long-term network reliability, and we theoretically prove that the maxRel algorithm is optimal in scenarios with dynamic link reliabilities. The Least Laxity First algorithm is adopted for the packet scheduling problem. Extensive simulation results show that the proposed approximate resource allocation algorithm makes remarkable improvement in terms of time complexity, packet loss rate and delay.     

Optimal Semi-Partitioned Scheduling in Soft Real-Time Systems

Semi-partitioned real-time scheduling algorithms extend partitioned ones by allowing a (usually small) subset of tasks to migrate. The first such algorithm to be proposed was directed at soft real-time (SRT) sporadic task systems where bounded deadline tardiness is acceptable. That algorithm, called EDF-fm, has the desirable property that migrations are boundary-limited, i.e., they can only occur at job boundaries. However, it is not optimal because per-task utilization restrictions are required. In this paper, a new optimal semi-partitioned scheduling algorithm for SRT sporadic task systems is proposed that eliminates such restrictions. This algorithm, called EDF-os, preserves the boundary-limited property. In overhead-aware schedulability experiments presented herein, EDF-os proved to be better than all other tested alternatives in terms of schedulability in almost all considered scenarios. It also proved capable of ensuring very low tardiness bounds, which were near zero in most considered scenarios.     

基于松弛时间与累计发送量的数据中心网络混合流调度机制

数据中心网络中同时存在截止时间流（deadline flow）和非截止时间流（non-deadline flow）,为降低非截止时间流的平均完成时间（Average Flow Complete Time,AFCT）同时维持低截止时间错失率（Deadline Miss Rate,DMR）,本文提出了一种基于松弛时间与累计发送量的混合流调度机制（Slack Time and Accumulation based Mix-flow Scheduling,STAM）.首先通过引入松弛时间的概念,衡量截止时间流对非截止时间流在传输时延上的宽容度;然后根据松弛时间,通过使截止时间流尽可能接近其规定截止时间完成,降低非截止时间流的完成时间;最后,利用最小累计发送量优先策略进一步降低非截止时间流的平均完成时间.仿真结果表明,该机制能有效降低非截止时间流的平均完成时间,同时保证较低的截止时间错失率.     

A Multi-objective Optimal Task Scheduling in Cloud Environment Using Cuckoo Particle Swarm Optimization

In cloud computing, varied demands are placed on the constantly changing resources. The task scheduling place very vital role in cloud computing environments, this scheduling process needs to schedule the tasks to virtual machine while reducing the makespan and cost. The task scheduling problem comes under NP hard category. Efficient scheduling method makes cloud computing services better and faster. In general, optimization algorithms are used to solve the scheduling issues in cloud. So, in this paper we combined two optimization algorithms namely called as Cuckoo Search (CS) and Particle Swarm Optimization (PSO).The new proposed hybrid algorithm is called as, CS and particle swarm optimization (CPSO). Our main purpose of the proposed paper is to reduce the makespan, cost and deadline violation rate. The performance of the proposed CPSO algorithm is evaluated using cloudsim toolkit. From the simulation results our proposed works minimize the makespan, cost, deadline violation rate, when compared to PBACO, ACO, MIN–MIN, and FCFS.

     

A distributed utility‐based scheduling for peer‐to‐peer video streaming over wireless networks

Interactive multimedia applications such as peer‐to‐peer (P2P) video services over the Internet have gained increasing popularity during the past few years. However, the adopted Internet‐based P2P overlay network architecture hides the underlying network topology, assuming that channel quality is always in perfect condition. Because of the time‐varying nature of wireless channels, this hardly meets the user‐perceived video quality requirement when used in wireless environments. Considering the tightly coupled relationship between P2P overlay networks and the underlying networks, we propose a distributed utility‐based scheduling algorithm on the basis of a quality‐driven cross‐layer design framework to jointly optimize the parameters of different network layers to achieve highly improved video quality for P2P video streaming services in wireless networks. In this paper, the quality‐driven P2P scheduling algorithm is formulated into a distributed utility‐based distortion‐delay optimization problem, where the expected video distortion is minimized under the constraint of a given packet playback deadline to select the optimal combination of system parameters residing in different network layers. Specifically, encoding behaviors, network congestion, Automatic Repeat Request/Query (ARQ), and modulation and coding are jointly considered. Then, we provide the algorithmic solution to the formulated problem. The distributed optimization running on each peer node adopted in the proposed scheduling algorithm greatly reduces the computational intensity. Extensive experimental results also demonstrate 4–14 dB quality enhancement in terms of peak signal‐to‐noise ratio by using the proposed scheduling algorithm. Copyright © 2015 John Wiley & Sons, Ltd.     

Scheduling Integrated Circuit Assembly Operations on Die Bonder

Solving the integrated circuit (IC) assembly scheduling problem (ICASP) is a very challenging task in the IC manufacturing industry. In the IC assembly factories, the jobs are assigned processing priorities and are clustered by their product types, which must be processed on groups of identical parallel machines. Furthermore, the job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. Therefore, the ICASP is more difficult to solve than the classical parallel machine scheduling problem. In this paper, we describe the ICASP in detail and formulate the ICASP as in integer programing problem to minimize the total machine workload. An efficient heuristic algorithm is also proposed for solving large-scale problems.