Search

3-D multiprocessor system-on-chip (MPSoC) systems can offer higher integration density, lower interaction cost, better bandwidth, and greater performance. However, vertically stacked silicon layers and limited heat dissipation paths result in high peak temperature and large temperature variation, which incur reliability reduction, lifetime decay, and performance degradation. In this article, we propose an offline augmented cross-entropy (CE)-based task scheduling strategy to jointly optimize peak temperature and temperature variation under the constraint of timeliness. Specifically, based on the conventional CE method, a heuristic iterative sampling method is designed to explore task-to-core assignment for balanced heat distribution between the top-layer and the bottom-layer cores. Subsequently, thermal characteristics of 3-D MPSoC systems are used to judiciously swap tasks between the two layers to improve the conventional CE-based task assignment and accelerate the iterative process. The peak temperature of individual cores is further reduced via sequencing, splitting, and slacking task execution. The experimental results demonstrate that compared to the existing state-of-the-art methods, the proposed scheme can reduce peak temperature by up to 8.02 °C and temperature variation by up to 24.78% without violating the timeliness of tasks. [ABSTRACT FROM AUTHOR]

The continuous growth in the demand for air transportation exceeds the capacity of existing infrastructure, usually leading to unreliable flight schedules, i.e., long flight delays and uncertainties in arrival/departure and taxi times. We tackle the problem in this paper by designing an air traffic control algorithm, which can accommodate both airport throughput and flight quality of service in terms of flight delay on a given runway. The flight scheduling problem is formulated as an integer linear programming, and then converted to a multiobjective optimization problem which enables the computation of tradeoff between scheduling resolution and time complexity. Based on the multiobjective optimization, a heuristic algorithm considering uncertainties in flight arrival/departure time and taxi time is designed to achieve an improvement in airport throughput and a reduction in flight delay. Extensive simulations show that compared to benchmarking schemes, the proposed uncertainty-aware flight scheduling algorithm can improve the airport throughput and flight delay by up to 12.02% and 31.4%, respectively. [ABSTRACT FROM AUTHOR]

With the advent of heterogeneous multiprocessor architectures, efficient scheduling for high performance has been of significant importance. However, joint considerations of reliability, temperature, and stochastic characteristics of precedence-constrained tasks for performance optimization make task scheduling particularly challenging. In this paper, we tackle this challenge by using an affinity (i.e., probability)-driven task allocation and scheduling approach that decouples schedule lengths and thermal profiles of processors. Specifically, we separately model the affinity of a task for processors with respect to schedule lengths and the affinity of a task for processors with regard to chip thermal profiles considering task reliability and stochastic characteristics of task execution time and intertask communication time. Subsequently, we combine the two types of affinities, and design a scheduling heuristic that assigns a task to the processor with the highest joint affinity. Extensive simulations based on randomly generated stochastic and real-world applications are performed to validate the effectiveness of the proposed approach. Experiment results show that the proposed scheme can reduce the system makespan by up to 30.1% without violating the temperature and reliability constraints compared to benchmarking methods. [ABSTRACT FROM AUTHOR]

Scientific workflow is a common model to organize large scientific computations. It borrows the concept of workflow in business activities to manage the complicated processes in scientific computing automatically or semi-automatically. The workflow scheduling, which maps tasks in workflows to parallel computing resources, has been extensively studied over years. In recent years, with the rise of cloud computing as a new large-scale distributed computing model, it is of great significance to study workflow scheduling problem in the cloud. Compared with traditional distributed computing platforms, cloud platforms have unique characteristics such as the self-service resource management model and the pay-as-you-go billing model. Therefore, the workflow scheduling in cloud needs to be reconsidered. When scheduling workflows in clouds, the monetary cost and the makespan of the workflow executions are concerned with both the cloud service providers (CSPs) and the customers. In this paper, we study a series of cost-and-time-aware workflow scheduling algorithms in cloud environments, which aims to provide researchers with a choice of appropriate cloud workflow scheduling approaches in various scenarios. We conducted a broad review of different cloud workflow scheduling algorithms and categorized them based on their optimization objectives and constraints. Also, we discuss the possible future research direction of the clouds workflow scheduling. [ABSTRACT FROM AUTHOR]

Benefiting from rich resources and virtualization technologies, hybrid cloud has emerged as a promising solution to processing large-scale scientific workflow applications for users in a pay-as-you-go manner. However, considering the complexity of resource configuration and deployment in hybrid clouds, existing workflow scheduling strategies designed for traditional distributed computing systems are limited and powerless. Therefore, for profit-driven infrastructure-as-a-service (IaaS) cloud providers, minimizing makespan and monetary cost of scheduling scientific workflows is an imperative concern. In this paper, we propose two efficient workflow scheduling approaches for hybrid clouds that both consider makespan and monetary cost. Specifically, we first propose a single-objective workflow scheduling optimization approach called DCOH (deadline-constrained cost optimization for hybrid clouds) for minimizing the monetary cost of scheduling workflows under deadline constraint. Based on DCOH, we further propose a multi-objective workflow scheduling optimization approach called MOH (multi-objective optimization for hybrid clouds) for optimizing makespan and monetary cost of scheduling workflows simultaneously. Extensive simulation experiments have been conducted to validate the effectiveness of DCOH and MOH. Simulation results show that our DCOH approach can reduce up to 100.0% monetary cost for users as compared to the competing algorithms under the same deadline constraint and our MOH approach can achieve better cost-makespan trade-off solutions as compared to the competing algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes a cost-minimization scheduling algorithm for the joint optimization of task offloading and resource allocation for workflow applications in a mobile edge computing (MEC)-supported cyber–physical system. We model this scheduling problem as an integer program that minimizes the total communication and computation cost under resources and deadline constraints upon workflow applications. To cope with this complicated optimization problem, we develop an efficient heuristic method to dispatch the workflow tasks onto MEC servers with sufficient resources. By using the task dispatching heuristic to evaluate the quality of each candidate solution, we construct a novel gene-inspired metaheuristic algorithm (GIMA) that incorporates an offspring-production operator and a conditional insertion scheme into the improvement strategy to explore high-quality solutions. Specifically, the offspring-production operator can enhance the scheduling quality by generating improved offspring solutions based on existing solutions. The conditional insertion scheme is further incorporated to reduce the computational overhead involved in solution exploration. We perform extensive simulations to justify the performance of the proposed GIMA in solving the scheduling problem studied in this work. Experimental results on real-world and synthetic workflow applications show that GIMA outperforms other metaheuristics in terms of cost reduction and computational efficiency. [ABSTRACT FROM AUTHOR]

Edge computing enables users to offload certain computation loads in complex applications to a nearby network consisting of multiple mobile devices such that the mobile devices' resources can be integrated to afford these complex applications. Due to the social relationships among the owners of mobile devices, networks in edge computing are always complex and consist of multiple sub-networks intersecting at several joint devices. In such complex networks, a joint device can communicate with all devices belonging to all sub-networks that intersect at this joint device while a general device can only communicate with the devices belonging to the same sub-network. This paper studies the makespan-minimization workflow scheduling problem for the aforementioned complex networks in edge computing environments, and formulates the problem as an integer program. Due to the limited energy capacity of each device, the dependence among workflow tasks, as well as network complexity, it is challenging to achieve feasible scheduling solutions for the concerned problem. Therefore, we propose a family of task allocation strategies to cope with different types of tasks in the workflow. These strategies are further integrated with a greedy strategy to construct an improved greedy search (IGS) algorithm which is capable of generating feasible solutions satisfying all constraints. In addition, we propose an improved composite heuristic (ICH) algorithm that employs IGS to initialize a feasible solution and uses a two-layer improvement scheme to further enhance the quality of the initial solution. Simulation results show that our proposed IGS achieves an 100% probability of generating feasible solutions, as compared to a 2.3% probability achieved by using the general round-robin scheduling algorithm. Furthermore, IGS and ICH outperform the counterpart scheduling algorithms in terms of makespan reduction. [ABSTRACT FROM AUTHOR]