Clustered checkpointing: Maximizing the level of confidence for non-equidistant checkpointing

Employing fault tolerance often introduces a time overhead, which may cause a deadline violation in real-time systems (RTS). Therefore, for RTS it is important to optimize the fault tolerance techniques such that the probability to meet the deadlines, i.e. the Level of Confidence (LoC), is maximized. Previous studies have focused on evaluating the LoC for equidistant checkpointing. However, no studies have addressed the problem of evaluating the LoC for non-equidistant checkpointing. In this work, we provide an expression to evaluate the LoC for non-equidistant checkpointing. Further, we detail an exhaustive search approach to find the distribution of a given number of checkpoints that results in the maximal LoC. Since the exhaustive search approach is very time-consuming, we propose the Clustered Checkpointing method, a heuristic that distributes checkpoints in a number of clusters with the goal to maximize the LoC. The results show that the LoC can be improved when non-equidistant checkpointing is used. Further, the results indicate that the proposed Clustered Checkpointing method is capable to find the distribution that results in the maximal LoC in much shorter time than the exhaustive search approach, while considering only few clusters.     

Dynamic scheduling and analysis of real time systems with multiprocessors

This research work considers a scenario of cloud computing job-shop scheduling problems. We consider m realtime jobs with various lengths and n machines with different computational speeds and costs. Each job has a deadline to be met, and the profit of processing a packet of a job differs from other jobs. Moreover, considered deadlines are either hard or soft and a penalty is applied if a deadline is missed where the penalty is considered as an exponential function of time. The scheduling problem has been formulated as a mixed integer non-linear programming problem whose objective is to maximize net-profit. The formulated problem is computationally hard and not solvable in deterministic polynomial time. This research work proposes an algorithm named the Tube-tap algorithm as a solution to this scheduling optimization problem. Extensive simulation shows that the proposed algorithm outperforms existing solutions in terms of maximizing net-profit and preserving deadlines.     

Application-directed voltage scaling

Clock (and voltage) scheduling is an important technique to reduce the energy consumption of processors that support voltage scaling. It is difficult, however, to achieve good results using only statistics from the operating system level when applications show bursty (unpredictable) behavior. We take the approach that such applications must be made power-aware and specify their average execution time (AET) and the deadline to the scheduler controlling the clock speed and processor voltage. This paper describes our energy priority scheduling (EPS) algorithm supporting power-aware applications. EPS orders tasks according to how tight their deadlines are and how often tasks overlap. Low-priority tasks are scheduled first, since they can be easily preempted to accommodate for high-priority tasks later. The EPS algorithm does not always yield the optimal schedule, but has a low complexity. We have implemented EPS on a StrongARM-based variable-voltage platform. We conducted experiments with a modified video decoder that estimates the AET of each frame. Measurements show that application-directed voltage scaling reduces processor power consumption with 50% for the bursty video decoder without missing any frame deadlines.     

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

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

An optimal checkpointing-strategy for real-time control systemsunder transient faults

Real-time computer systems are often used in harsh environments, such as aerospace, and in industry. Such systems are subject to many transient faults while in operation. Checkpointing enables a reduction in the recovery time from a transient fault by saving intermediate states of a task in a reliable storage facility, and then, on detection of a fault, restoring from a previously stored state. The interval between checkpoints affects the execution time of the task. Whereas inserting more checkpoints and reducing the interval between them reduces the reprocessing time after faults, checkpoints have associated execution costs, and inserting extra checkpoints increases the overall task execution time. Thus, a trade-off between the reprocessing time and the checkpointing overhead leads to an optimal checkpoint placement strategy that optimizes certain performance measures. Real-time control systems are characterized by a timely, and correct, execution of iterative tasks within deadlines. The reliability is the probability that a system functions according to its specification over a period of time. This paper reports on the reliability of a checkpointed real-time control system, where any errors are detected at the checkpointing time. The reliability is used as a performance measure to find the optimal checkpointing strategy. For a single-task control system, the reliability equation over a mission time is derived using the Markov model. Detecting errors at the checkpointing time makes reliability jitter with the number of checkpoints. This forces the need to apply other search algorithms to find the optimal number of checkpoints. By considering the properties of the reliability jittering, a simple algorithm is provided to find the optimal checkpoints effectively. Finally, the reliability model is extended to include multiple tasks by a task allocation algorithm     

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

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

Enhanced EDCA with Deterministic Transmission Collision Resolution for Real-Time Communication in Vehicular Ad Hoc Networks

The collision prevention system is one of most important research issues on vehicle safety technology. Sending worming messages within the right time and reliable transmission will get prevention of a possible vehicle accident. The communication standards of vehicular networks (VANET) are unable to guarantee the delivery of critical messages within tight deadlines. Indeed, the transmission collisions are handled with probabilistic manner that can reduce the transmission latency; however, it is inept to predict an upper bound value of this delay to verify the deadline. In this paper, we propose a medium access protocol that ensures the delivery of critical messages within a deadline. It is a hard real-time system with delay constant guarantee. We are focusing on improving the EDCA medium access protocol to prioritize critical messages and to get access to the transmission channel within a predictable communication delay. We create a new enhanced access protocol that is compatible with the IEEE 802.11p VANET standards and adapted to real-time communication requirements related to the vehicle collision avoidance problem.     

On real-time databases: concurrency control and scheduling

In addition to maintaining database consistency as in conventional databases, real-time database systems must also handle transactions with timing constraints. While transaction response time and throughput are usually used to measure a conventional database system, the percentage of transactions satisfying the deadlines or a time-critical value function is often used to evaluate a real-time database system. Scheduling real-time transactions is far more complex than traditional real-time scheduling in the sense that (1) worst case execution times are typically hard to estimate, since not only CPU but also I/O requirement is involved; and (2) certain aspects of concurrency control may not integrate well with real-time scheduling. In this paper, we first develop a taxonomy of the underlying design space of concurrency control including the various techniques for achieving serializability and improving performance. This taxonomy provides us with a foundation for addressing the real-time issues. We then consider the integration of concurrency control with real-time requirements. The implications of using run policies to better utilize real-time scheduling in a database environment are examined. Finally, as timing constraints may be more important than data consistency in certain hard realtime database applications, we also discuss several approaches that explore the nonserializable semantics of real-time transactions to meet the hard deadlines     

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.     

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.     

Energy management for battery-powered reconfigurable computing platforms

We define portable reconfigurable computing platforms as those which have some form of configurable logic coupled with other on-chip or off-chip processing units such as soft processors, embedded processors, and voltage-scalable processors. In the first part of this paper, we present and test a unique methodology where we dynamically change the active area of a field programmable gate array (FPGA) to vary the battery usage and lifetime of the system, by running it on several different taskgraph structures and report an average of 14% and as high as 21%, less battery capacity used, as compared to nonoptimal execution. In the second part of this paper, we integrate the above methodology with more traditional voltage and frequency scaling techniques for portable systems and present a heuristic iterative algorithm for single and multiple processing units. The iterative heuristic algorithm finds a sequence of tasks along with an appropriate design point (implementation option) for each task, such that a deadline is met and the amount of battery energy used is as small as possible. We have used several real-world benchmarks to test the effectiveness of this methodology and we will present the results.     

一种基于风险感知策略的多节点任务调度方法

为解决无人机(UAV)集群任务调度时面临各节点动态、不稳定的情况,该文提出一种面向多计算节点的可尽量避免任务中断且具有容错性的任务调度方法。该方法首先为基于多计算节点构建了一个以最小化任务平均完成时间为优化目标的任务分配策略;然后基于任务的完成时间和边缘计算节点的存留时间两者的概率分布,将任务计算节点上的执行风险量化成额外开销时间;最后以任务的完成时间与额外开销时间之和替换原本的完成时间,设计了风险感知的任务分配策略。在仿真环境下将该文提出的任务调度方法与3种基准调度方法进行了对比实验,实验结果表明该方法能够有效地降低任务平均响应时间、任务平均执行次数以及任务截止时间错失率。证明该文提出的方法降低了任务重调度和重新执行带来的额外开销,可实现分布式协同计算任务的调度工作,为复杂场景下的无人机集群网络提供新的技术支持。     

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.     

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     

Reliable real-time task scheduler based on Rocket Queue architecture

This paper presents the design of an improved task scheduler for real-time and safety-critical systems, where it is important to deal with real-time requirements and reliability requirements simultaneously. The proposed scheduler implements EDF algorithm for the optimal scheduling of hard real-time tasks, which is essential for real-time operating systems. The proposed task scheduler allows removing any task from the queue according to task ID and regardless of the actual position of the task within the queue, which is important for flexibility of the scheduler for its future extensions. Both operations of the scheduler, i.e. task adding and task killing take always constant time (two clock cycles) to execute regardless of the actual or the maximum number of tasks within the scheduler. The scheduler was verified using simplified version of UVM and applying millions of instructions with randomly generated sort values. The scheduler, implemented in a form of a coprocessor, was synthesized into Intel FPGA Cyclone V with 100 MHz clock frequency. There are two improvements proposed that can significantly reduce resource costs of the scheduler, which is achieved by replacing static deadlines with dynamic deadlines and using a new Rocket Queue architecture for sorting of the tasks according to their deadline values. When both improvements are applied simultaneously, the total ALM cost savings are in the range from 42,59% to 60,18% and the total amount of registers is reduced by 73,74% to 74,87%, depending on the scheduler capacity. The spared resources are then used for implementation of two different variations of TMR in order to increase fault tolerance of the scheduler. The resource cost reductions achieved also indirectly increase the reliability of such scheduler because of reduced probability that a fault occurs.     

Scientific Workflow Makespan Minimization in Edge Multiple Service Providers Environment

The edge computing model offers an ultimate platform to support scientific and real-time workflow-based applications over the edge of the network. However, scientific workflow scheduling and execution still facing challenges such as response time management and latency time. This leads to deal with the acquisition delay of servers, deployed at the edge of a network and reduces the overall completion time of workflow. Previous studies show that existing scheduling methods consider the static performance of the server and ignore the impact of resource acquisition delay when scheduling workflow tasks. Our proposed method presented a meta-heuristic algorithm to schedule the scientific workflow and minimize the overall completion time by properly managing the acquisition and transmission delays. We carry out extensive experiments and evaluations based on commercial clouds and various scientific workflow templates. The proposed method has approximately 7.7% better performance than the baseline algorithms, particularly in overall deadline constraint that gives a success rate.

     

Safe and efficient power management of hard real-time networks-on-chip

The power overhead of Networks-on-Chip (NoCs) becomes tremendous in high density Multiprocessor Systems-on-Chip (MPSoCs). Especially in hard real-time and safety-critical systems, power management mechanisms must be developed and efficiently adhered to real-time requirements. However, state-of-the-art solution typically induces a high timing overhead, thus challenging safety, or has limited power saving capabilities. Additionally, current power-gating mechanisms do not provide an upper bound of the latency overhead, and thus no timing guarantees. We propose a safe and enhanced approach for power-gating that allows a global and dynamic power management under timing guarantees, i.e., all deadlines of critical tasks are met. It introduces a control-layer to save power on the NoC data layer using multiple Power-Aware Traffic-Monitor (PATM) units, which apply knowledge of the global state of the system to efficiently save power on NoC routers even at high NoCs utilizations. To safely apply the PATMs in hard real-time systems while meeting the deadlines, we provide a formal worst-case timing analysis to derive PATMs upper bound latency overhead. Experimental results show that our approach efficiently reduces static power consumption, and provides scalability inducing very small area overhead.     

Sensitivity analysis of handoff algorithms on CDMA forward link

We analyze the performance of different handoff algorithms on the forward link or downlink of a code-division multiple-access (CDMA) cellular system. Unlike the reverse link, soft handoff on the forward link requires additional resources such as CDMA codes and transmit power and also causes additional interference. If handoff requests can be processed and completed instantaneously, transmission from the base station with the best link to the user would achieve a significant fraction of the macrodiversity gain without utilizing additional resources. However, in practical systems, there is a nonzero handoff completion delay and soft handoff provides the required robustness to delays, although it comes at the expense of additional network resources. Thus, there is a tradeoff between the extent of soft handoff required and the handoff execution delay. We compare the performance of hard and soft handoff schemes and study their sensitivity to the delay in the execution of the handoff. Outage probability and the total average power required are used as performance metrics. We present an analytical framework to study this tradeoff and also discuss simulation results with field data. The results provide insights on the conditions under which soft handoff can be eliminated and on the effect of relevant handoff thresholds on the performance.     

Optimal Rate Control for Delay-Constrained Data Transmission Over a Wireless Channel

We study energy-efficient transmission of data with deadline constraints over a time-varying channel. Specifically, the system model consists of a wireless transmitter with controllable transmission rate, time-varying and stochastic channel state, and strict delay constraints on the packets in the queue. While the transmitter can control the rate, the transmission power required depends on the chosen rate and the prevailing channel condition. The objective is to obtain a rate control policy that serves the data within the deadline constraints while minimizing the total energy expenditure. Toward this end, we first introduce the canonical problem of transmitting $B$ units of data by deadline $T$ over a Markov fading channel, and obtain the optimal policy for it using continuous-time stochastic control theory. Using a novel cumulative curves methodology and a decomposition approach, we extend the above setup to consider extensions involving variable deadlines on the packets. Finally, utilizing the analysis we present a heuristic policy for the case of arbitrary packet arrivals to the queue with individual deadline constraints, and give illustrative simulation results for its performance.      

Energy-Efficient Mobile Data Uploading from High-Speed Trains

Recent decades have witnessed the fast development of high-speed railway systems in many countries, which have significantly shortened the travel time between distant cities. Accompanied with this convenience is the challenge for cell phone vendors to provide broadband Internet access for passengers, particularly considering the fast changing channel conditions in high-speed trains and the limited battery of cell phones, which often cannot be re-charged in trains. In this paper, inspired by the unique spatial-temporal characteristics of wireless signals along high-speed railways, we propose a novel energy-efficient scheduling approach for uploading data from cell phones, both with soft deadlines (e.g., documents) and hard deadlines (e.g., video streaming). Our solution effectively predicts the signal strength through its spatial-temporal periodicity in this new application scenario, and smartly adjusts the transmission rate to maximize the overall data transmission rate and yet conserves the energy consumption. Performance evaluation based on realistic railway scenarios and H.264 video traces demonstrate the effectiveness of our solution and its superiority as compared to the existing solutions.