Search

Fog computing is a novel, decentralized and heterogeneous computing environment that extends the traditional cloud computing systems by facilitating task processing near end‐users on computing resources called fog nodes. These diverse and resource‐constrained fog devices process a large volume of tasks generated by various fog applications. These tasks are generated by various applications, some of which may be latency‐sensitive, while others may tolerate some degree of delay in their normal functions. Task scheduling determines when a task should be allocated to a computing resource and how long that task can occupy the assigned resource. The majority of task scheduling algorithms focus on prioritizing the latency‐sensitive tasks only, which results in the long waiting time for the other type of tasks. Hence, these priority‐based schedulers cause task starvation for less important tasks while achieving delay‐optimal results for latency‐sensitive tasks. As a result, in this paper, we propose MQP, a multi‐queue priority‐based preemptive task scheduling approach that achieves a balanced task allocation for those applications that can tolerate a certain amount of processing delay and the latency‐sensitive fog applications. At run‐time, the MQP algorithm categorizes tasks as short and long based on their burst time. MQP algorithm maintains a separate task queue for each task category and dynamically updates the time slot value for preemption. The proposed technique's major purpose is to reduce response time for those data‐intensive applications in the fog computing environment, which include both latency‐sensitive tasks and tasks which are less latency‐sensitive, thereby addressing the starvation problem for less latency‐sensitive tasks. A smart traffic management case study is created to model a scenario with both latency‐sensitive short and less latency‐sensitive long tasks. We implement the MQP algorithm using iFogSim and confirm that it reduces the service latencies for long tasks. Simulation results show that the MQP algorithm allocates tasks to a fog device more efficiently and reduces the service latencies for long tasks. The average value of percentage reduction in the latency across all experimental configurations achieved is 22.68% and 38.45% in comparison to First Come‐First Serve and shortest job first algorithms. [ABSTRACT FROM AUTHOR]

Cloud computing is a technology that is being used by scientists for the execution of huge scale workflows as it has various features such as availability, faster, cheaper, elasticity, and high accessibility. In addition, the users are charged on a pay per use basis which makes it more efficient to be used by various clients. Scheduling workflows in the cloud is a difficult task as it takes into account the dependencies of workflows along with quality of service (QoS) demands. The problem becomes more challenging when there are multiple QoS objectives which are often disagreeing to each other. A lot of research has been done to minimize makespan and execution cost under deadline and budget constraints. This article presents a workflow scheduling algorithm based on Jaya to minimize them both and returns solutions according to the weights a user gives. The algorithm has been compared with Min‐Min, Max‐Min, Round Robin, heterogeneous earliest finish time first, first come first serve, minimum completion time, dynamic heterogeneous earliest finish time first in WorkflowSim. The results are compared based on both cost and time. In the end, a trade‐off between the objectives has been shown. Results show that Jaya performs much better than other algorithms when averaged over several iterations. [ABSTRACT FROM AUTHOR]

Summary: This paper introduces several budget‐aware algorithms to deploy scientific workflows on Infrastructure as a Service Cloud platforms, where users can request Virtual Machines (VMs) of different types, each with specific cost and computing resources. We use a realistic application/platform model with stochastic task weights, and VMs communicating through a Cloud storage. We extend two well‐known algorithms, MinMin and HEFT, and make scheduling decisions based upon machine availability and remaining budget. During the mapping process, the budget‐aware algorithms make conservative assumptions to avoid exceeding the initial budget; we further improve the results with refined versions that aim at rescheduling some tasks onto faster VMs, thereby spending any budget fraction leftover by the first allocation. These refined variants are much more time‐consuming than the former algorithms, so there is a trade‐off to find in terms of scalability. We report an extensive set of simulations with workflows from the Pegasus benchmark suite. Most of the time, our budget‐aware algorithms succeed in achieving efficient makespans while enforcing the given budget, and this despite the uncertainty in task weights. [ABSTRACT FROM AUTHOR]

Summary: Federated edge cloud (FEC) is an edge computing environment where servers in the same edge management domain could collaborate to handle latency‐sensitive services, thus better guaranteeing users' requirements on multiple quality of service (MQoS). Traditional scheduling methods only consider whether the server meets the resource requirements of the service, without paying attention to whether their resource characteristics match. In scenarios where server's resources are dynamically changing, this may reduce the resource utilization and the efficiency of service execution. To address this challenge, a dynamic resource adaptation‐multiple quality of service (DRA‐MQoS) algorithm is proposed for service scheduling in this environment. DRA‐MQoS could dynamically evaluate the resource characteristics of servers and services from the perspectives of "individual" and "overall" by combining the historical scheduling data of services and the utilization of different resources of server clusters. By scheduling the services to servers with the same resource characteristics for execution, the proposed policy fusion algorithm efficiently responds to the dynamically changing quality of service (QoS) demands of users by changing the weight parameters of policies. Simulation results in CloudSimSDN show that the energy consumption and execution time of DRA‐MQoS are reduced by 23% and 12%, respectively, compared with existing methods. [ABSTRACT FROM AUTHOR]

Summary: Energy optimization with time constraint has become a timely and significant challenge for the datacenters. In this paper, a hardware and software collaborative optimization strategy is implemented to minimize the energy cost while satisfying the time constraint of the datacenters. In the hardware aspect, a DVFS‐capable CPU/GPU/FPGA heterogeneous computing infrastructure is built. This infrastructure can adjust its hardware characteristics dynamically in terms of the software run‐time contexts so that the applications can be executed efficiently with less time and lower energy cost. In the software aspect, a deadline‐aware energy‐efficient task scheduling algorithm based on the Q‐learning approach is investigated. This algorithm can adjust its searching directions smartly in terms of the environment feedback so that it can achieve better optimization performance comparing with the traditional genetic algorithm. However, its convergence time is long due to the large amount of training work, making it inappropriate to be applied in the large‐scale datacenters. To ease this problem, we proposed another new algorithm named Rapid Local Convolution Optimization (RLCO) and combine it with the Q‐learning algorithm. By doing this, the convergence time of the Q‐learning mechanism can be decreased significantly. We conducted both the simulation and real‐world experiments to evaluate the performance of our approaches, and the results proved the proposed algorithm running on the DVFS‐capable heterogeneous hardware architecture could decrease the energy cost of the datacenter significantly even if the datacenter is in large scale. [ABSTRACT FROM AUTHOR]

Summary: This paper presents an efficient algorithm with performance guarantee to solve task scheduling problem on hybrid platforms with energy constraint and communication delays. The underlying platform architecture in this work is composed of two types of resources, CPU and GPU, often called hybrid parallel multicore platforms. We focus on finding a generic approach to schedule applications presented by Directed Acyclic Graph (DAG), which minimizes the makespan by considering communication delays and respecting an energy constraint. A two‐phase algorithm is proposed with a performance guarantee of 6 compared with the optimal solution; the first phase consists in solving the assignment problem to find the type of processor assigned to execute the tasks (CPU or GPU) using a linear program. In the second phase, we calculate the start execution time of each task to generate a feasible schedule. Finally, we test our algorithm on a large number of instances. These tests demonstrate that the proposed algorithm achieves a close‐to‐optimal performance. [ABSTRACT FROM AUTHOR]

A serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. In this paper, we formulate the static load-balancing problem in single class job distributed systems as a cooperative game among computers. The computers comprising the distributed system are modeled as M/M/1 queueing systems. It is shown that the Nash bargaining solution (NBS) provides an optimal solution (operation point) for the distributed system and it is also a fair solution. We propose a cooperative load-balancing game and present the structure of NBS. For this game an algorithm for computing NBS is derived. We show that the fairness index is always equal to 1 using NBS, which means that the solution is fair to all jobs. Finally, the performance of our cooperative load-balancing scheme is compared with that of other existing schemes. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Summary: Mobile agents are examples of distributed systems which may dispute for the same resources on their hosts. Treating such concurrency adequately is essential, particularly in real‐time applications. Due to intrinsic time restrictions, mobile agents in real‐time environments are only considered successful if they fulfill their mission by respecting their deadlines. Scheduling algorithms with different policies can be applied in these scenarios. However, the efficiency of these algorithms may deviate according to the missions and deadlines of the mobile agents. Also, these algorithms can be preemptive, or calculate the order of executions without interrupting an ongoing task. In this paper, we propose a middleware extension to the JADE platform that brings real‐time scheduling support with preemption to mobile agents. The proposed solution uses best effort scheduling policy in the context of soft real‐time applications. We evaluate the performance of the scheduling algorithms, with and without preemption, and the impact of the selected algorithms on mission fulfillment. The results of the proposed middleware showed a great improvement on mission accomplishment when compared to the FIFO algorithm provided by the JADE platform. [ABSTRACT FROM AUTHOR]

Most algorithms developed for scheduling applications on global Grids focus on a single Quality of Service (QoS) parameter such as execution time, cost or total data transmission time. However, if we consider more than one QoS parameter (e.g. execution cost and time, which may be in conflict) then the problem becomes more challenging. To handle such scenarios, it is convenient to use heuristics rather than a deterministic algorithm. In this paper, we have proposed a workflow execution planning approach using Multiobjective Differential Evolution (MODE). Our goal was to generate a set of trade-off schedules according to two user specified QoS requirements (time and cost), which will offer more flexibility to users when estimating their QoS requirements. We have compared our results with a well-known baseline algorithm ‘Pareto-archived Evolutionary Strategy (PAES)’. Simulation results show that the modified MODE is able to find significantly better spread of compromise solutions compared with that of PAES. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

One of the main challenges of scheduling algorithms in Grid environment is the autonomy of sites, which makes it difficult for the grid scheduler to estimate the exact cost of a task execution on different sites. In this paper, we present a solution for this problem based on data history (workload traces) and time series techniques. The main focus of this work is devoted to forecasting the task waiting time in a resource queue, which is under the control of a local scheduler with distinctive scheduling policy. The main contribution of this work is the consideration of a special property of the grid resources, the dynamic membership, i.e. a resource may exit and then come back to the grid environment repeatedly. When the resource belongs to the grid environment, its workload trace (log file) is considered as a correct log. On the other hand, when the resource leaves the grid, the log file during this period is considered as a defective part of the trace. As the defective parts contain some useful information, after repairing these defective parts, they can be used for forecasting purposes. Of this, we employ state-space model along with the associated Kalman recursions in conjunction with the Expectation-Maximization algorithm to repair the defective waiting time series such as a correct log file by which the resource seems never to have left the grid. The experimental results on a number of workload logs demonstrated that this approach can achieve an average prediction error, between 22 and 64% less than those incurred by other rival methods. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Summary: Cloud computing as of late is a rising innovation for giving various administrations through internet to fulfil the requisites of clients dependent on needs with minimal expense. The client can benefit all kind of administration without building, observing, and keeping up the assets. Researchers developed distinctive asset planning calculation to satisfy the client requisites as per their condition. This article proposes a Water Wave Algorithm (WWA) for resource scheduling in cloud environment. The results for throughput, Response time, Turnaround time, Migration time, Resource utilization, Fault tolerance, and scalability over FCFS, MCT, MET, and OLB algorithms and the results prove that WWA provides better results for throughput, response time, resource utilization, and scalability. [ABSTRACT FROM AUTHOR]

SUMMARY We consider a task graph to be executed on a set of processors. We assume that the mapping is given, say by an ordered list of tasks to execute on each processor, and we aim at optimizing the energy consumption while enforcing a prescribed bound on the execution time. Although it is not possible to change the allocation of a task, it is possible to change its speed. Rather than using a local approach such as backfilling, we consider the problem as a whole and study the impact of several speed variation models on its complexity. For continuous speeds, we give a closed-form formula for trees and series-parallel graphs, and we cast the problem into a geometric programming problem for general directed acyclic graphs. We show that the classical dynamic voltage and frequency scaling (DVFS) model with discrete modes leads to an NP-complete problem, even if the modes are regularly distributed (an important particular case in practice, which we analyze as the incremental model). On the contrary, the Vdd-hopping model that allows to switch between different supply voltages ( V DD) while executing a task leads to a polynomial solution. Finally, we provide an approximation algorithm for the incremental model, which we extend for the general DVFS model. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Summary: Hadoop is a typical framework for processing big data. Task scheduling algorithms have a significant impact on the processing performance of Hadoop clusters. Existing scheduling algorithms of Hadoop fail to consider the performance differences between nodes in heterogeneous Hadoop clusters, causing problems such as uneven task allocation and low resource utilization. Aiming to solve this problem, we propose a spider monkey optimization‐based scheduling algorithm (SMOSA) for heterogeneous Hadoop. First, the cluster heartbeat mechanism is used to obtain information such as memories and CPUs of nodes to comprehensively consider the actual load capacity of each node. Then, the spider monkey optimization algorithm is adopted to find the optimal mapping relationship between tasks and resources by taking the task completion time as the objective function and updating the position of the spider monkey. Finally, we calculate the remaining rate of node hardware resources, and according to the task type, the node with the higher remaining rate of resource will give priority to the task. Data are compressed for I/O type tasks to reduce disk operations and increase the speed of task execution. Experimental results show that, compared with existing scheduling algorithms, the SMOSA can effectively reduce task execution time and can significantly improve scheduling efficiency and task execution speed especially in heterogeneous Hadoop clusters. For different types of tasks, the execution time can be reduced by up to 19%. [ABSTRACT FROM AUTHOR]

Summary: Field Programmable Gate Arrays (FPGAs) are preferred in the modern embedded system to accelerate the performance of the entire system. However, the FPGAs are liable to suffer from reconfiguration overheads. These overheads are mainly because of the configuration data being fetched from the off‐chip memory at run‐time and due to the improper management of tasks during execution. To reduce these overheads, two algorithms are proposed. Both the algorithms focus on the prefetch heuristics, reuse technique, and an optimal mapping of tasks over the available memories. However, in terms of reusing technique, algorithm‐1 uses least recently used (LRU) policy and algorithm‐2 uses the optimal replacement policy (considering the vitality of the reconfigurable units (RUs)). Simulation results are obtained for both the algorithms. It is evident from the result that most of the reconfiguration overheads are eliminated when the applications are managed and executed based on the proposed algorithms. Also, the two algorithm results are compared and analyzed. For this purpose, the experiments included smaller and larger task graphs. In the case of smaller task graphs, algorithm‐2 outperforms algorithm‐1 in reducing reconfiguration overheads. In larger task graphs, algorithm‐1 produces better results compared to algorithm‐2. [ABSTRACT FROM AUTHOR]

Large-scale scientific problems are often modeled as workflows. The ever-growing data and compute requirements of these applications has led to extensive research on how to efficiently schedule and deploy them in distributed environments. The emergence of the latest distributed systems paradigm, cloud computing, brings with it tremendous opportunities to run scientific workflows at low costs without the need of owning any infrastructure. It provides a virtually infinite pool of resources that can be acquired, configured, and used as needed and are charged on a pay-per-use basis. However, along with these benefits come numerous challenges that need to be addressed to generate efficient schedules. This work identifies these challenges and studies existing algorithms from the perspective of the scheduling models they adopt as well as the resource and application model they consider. A detailed taxonomy that focuses on features particular to clouds is presented, and the surveyed algorithms are classified according to it. In this way, we aim to provide a comprehensive understanding of existing literature and aid researchers by providing an insight into future directions and open issues. [ABSTRACT FROM AUTHOR]

This work presents a method for predicting resource availability in opportunistic grids by means of use pattern analysis (UPA), a technique based on non-supervised learning methods. This prediction method is based on the assumption of the existence of several classes of computational resource use patterns, which can be used to predict the resource availability. Trace-driven simulations validate this basic assumptions, which also provide the parameter settings for the accurate learning of resource use patterns. Experiments made with an implementation of the UPA method show the feasibility of its use in the scheduling of grid tasks with very little overhead. The experiments also demonstrate the method's superiority over other predictive and non-predictive methods. An adaptative prediction method is suggested to deal with the lack of training data at initialization. Further adaptative behaviour is motivated by experiments which show that, in some special environments, reliable resource use patterns may not always be detected. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Summary: We study the problem of executing an application represented by a precedence task graph on a parallel machine composed of standard computing cores and accelerators. Both off‐line and on‐line settings are addressed by proposing generic scheduling approaches. In the first case, we establish strong lower bounds on the worst‐case performance of a known approach based on Linear Programming and replace the greedy List Scheduling policy used in this approach by a better task ordering. Although this modification leads to the same approximability guarantees, it performs much better in practice. We also extend this algorithm to more types of computing units, achieving an approximation ratio which depends on the number of different types. In the on‐line case, tasks arrive in any order which respects the precedence relations and the scheduler has to take irrevocable decisions about their allocation and execution. We propose the first on‐line scheduling algorithm taking into account precedences, which is based on adequate rules for selecting the type of processor where to allocate the tasks. Finally, all the previous algorithms have been experimented on a large number of simulations built on actual libraries, assessing their good practical behavior with respect to the state‐of‐the‐art solutions and baseline algorithms. [ABSTRACT FROM AUTHOR]

Bias in the performance evaluation of scheduling heuristics has been shown to undermine the scope of existing studies. Improving the assessment step leads to stronger scientific claims when validating new optimization strategies. This article considers the problem of allocating independent tasks to unrelated machines such as to minimize the maximum completion time. Testing heuristics for this problem requires the generation of cost matrices that specify the execution time of each task on each machine. Numerous studies showed that the task and machine heterogeneities belong to the properties impacting heuristics performance the most. This study focuses on orthogonal properties, the average correlations between each pair of rows and each pair of columns, which measure the proximity with uniform instances. Cost matrices generated with 2 distinct novel generation methods show the effect of these correlations on the performance of several heuristics from the literature. In particular, EFT performance depends on whether the tasks are more correlated than the machines and HLPT performs the best when both correlations are close to one. [ABSTRACT FROM AUTHOR]