Recently, there are many applications using coflow-based scheduling to improve performance in a cluster. However, most applications implement coflow-based scheduling by modifying their API. These applications also nee...
详细信息
Recently, there are many applications using coflow-based scheduling to improve performance in a cluster. However, most applications implement coflow-based scheduling by modifying their API. These applications also need to modify the third-party libraries. This is very complicated and inefficient. Therefore, prior work has proposed a coflow-based scheduling algorithm CODA, which can automatically identify coflows. CODA does not have to design the API for each application and it is transparent for the application. But CODA performs poorly on the unstable traffic and rapid traffic in datacenter. In this paper, we propose a coflow scheduling algorithm named CS-DP to solve this problem. First, we employ the density peak clustering algorithm to implement a fast, application-transparent coflow identifier. Then we employ MLFQ (multi-level feedback scheduling queues) for scheduling. Moreover, we add a threshold calculation module on MLFQ The key point of threshold calculation is to get the appropriate threshold by historical traffic. Thus, CS-DP can accommodate the current traffic quickly and effectively. Finally, the simulation results show CS-DP enabling communication stages to complete 1.11x (1.17 x ) and 2.6x(3.0x) faster on average(95-th percentile) compared to CODA algorithm and per-flow fairness on normal traffic. (C) 2019 Elsevier B.V. All rights reserved.
Concurrent workflow scheduling algorithm works in three phases, namely rank computation, tasks selection, and resource selection. In this paper, we introduce a new ranking algorithm that computes the rank of a task, b...
详细信息
Concurrent workflow scheduling algorithm works in three phases, namely rank computation, tasks selection, and resource selection. In this paper, we introduce a new ranking algorithm that computes the rank of a task, based on its successor rank and its predecessors average communication time, instead of its successors rank. The advantage of this ranking algorithm is that two dependent tasks are assigned to the same machine and as a result the scheduled length is reduced. The task selection phase selects a ready task from each workflow and creates a task pool. The resource selection phase initially assigns tasks using min-min heuristic, after initial assignment, tasks are moved from the highly loaded machines to the lightly loaded machines. Our resource selection algorithm increases the load balance among the resources due to tasks assignment heuristic and reassignment of tasks from the highly loaded machines. The simulation results show that our proposed scheduling algorithm performs better over existing approaches in terms of load balance, makespan and turnaround time.
In this paper a Hydrothermal scheduling algorithm (HSA) for deterministic inflows is presented. A nonlinear network flow model representing the hydrothermal scheduling problem is used. By exploiting the special networ...
详细信息
In this paper a Hydrothermal scheduling algorithm (HSA) for deterministic inflows is presented. A nonlinear network flow model representing the hydrothermal scheduling problem is used. By exploiting the special network structure, a temporally expanded arborescence [1], the HSA code attains important computational savings in processing time and memory requirements allowing the use of microcomputers even for large scale problems. The main feature of the HSA code is a dynamic base choice that enables the decision maker to improve the convergence of the optimization procedure by the use of his practical experience. The performance of the algorithm is tested on the Southeast Brazilian Power System.
Cloud computing is extensively used in a variety of applications and domains, however task and resource scheduling remains an area that requires improvement. Put simply, in a heterogeneous computing system, task sched...
详细信息
Cloud computing is extensively used in a variety of applications and domains, however task and resource scheduling remains an area that requires improvement. Put simply, in a heterogeneous computing system, task scheduling algorithms, which allow the transfer of incoming tasks to machines, are needed to satisfy high performance data mapping requirements. The appropriate mapping between resources and tasks reduces makespan and maximises resource utilisation. In this contribution, we present a novel scheduling algorithm using Directed Acyclic Graph (DAG) based on the Prediction of Tasks Computation Time algorithm (PTCT) to estimate the preeminent scheduling algorithm for prominent cloud data. In addition, the proposed algorithm provides a significant improvement with respect to the makespan and reduces the computation and complexity via employing Principle Components Analysis (PCA) and reducing the Expected Time to Compute (ETC) matrix. Simulation results confirm the superior performance of the algorithm for heterogeneous systems in terms of efficiency, speedup and schedule length ratio, when compared to the state-of-the-art Min-Min, Max-Min, QoS-Guide and MiM-MaM scheduling algorithms.
In a Grid computing system, many distributed scientific and engineering applications often require multi-institutional collaboration, large-scale resource sharing, wide-area communication, etc. Applications executing ...
详细信息
In a Grid computing system, many distributed scientific and engineering applications often require multi-institutional collaboration, large-scale resource sharing, wide-area communication, etc. Applications executing in such systems inevitably encounter different types of failures such as hardware failure, program failure, and storage failure. One way of taking failures into account is to employ a reliable scheduling algorithm. However, most existing Grid scheduling algorithms do not adequately consider the reliability requirements of an application. In recognition of this problem, we design a hierarchical reliability-driven scheduling architecture that includes both a local scheduler and a global scheduler. The local scheduler aims to effectively measure task reliability of an application in a Grid virtual node and incorporate the precedence constrained tasks' reliability overhead into a heuristic scheduling algorithm. In the global scheduler, we propose a hierarchical reliability-driven scheduling algorithm based on quantitative evaluation of independent application reliability. Our experiments, based on both randomly generated graphs and the graphs of some real applications, show that our hierarchical scheduling algorithm performs much better than the existing scheduling algorithms in terms of system reliability, schedule length, and speedup. (C) 2011 Elsevier Inc. All rights reserved.
Most existing commercial video servers are designed for a single server. Consequently, the capacity of the system in terms of maximum sustainable concurrent sessions is limited by the performance of the video server h...
详细信息
Most existing commercial video servers are designed for a single server. Consequently, the capacity of the system in terms of maximum sustainable concurrent sessions is limited by the performance of the video server hardware. This paper proposes and analyzes the performance of a novel parallel video server architecture where video data are striped across an array of autonomous servers. The architecture allows one to build incrementally scalable video servers without video data replication. The proposed concurrent-push scheduling algorithm allows the system to integrate with quality of service guarantees provided by today's switching networks. In this paper, the striping policy, the service model, and the concurrent-push scheduling algorithm are presented. A system model is constructed to quantify three performance metrics, namely, server buffer requirement, client buffer requirement, and system response time. Results show that a simple extension of the server-push service model does not perform well under the parallel video server architecture. To improve system performance, a novel extension of the grouped sweeping scheme called the asynchronous grouped sweeping scheme (AGSS) is introduced. To further increase the scalability of the architecture, a new subschedule striping scheme (SSS) is introduced. With the proposed AGSS and SSS, our parallel video server architecture can be scaled up to more than 10 000 concurrent users.
Security is a major concern of modern real-time applications, besides requiring stringent latency bound. However, encryption algorithms are computation intensive task which impacts the timeliness of the real-time appl...
详细信息
Security is a major concern of modern real-time applications, besides requiring stringent latency bound. However, encryption algorithms are computation intensive task which impacts the timeliness of the real-time applications. Therefore, there exists a trade-off between the desired level of security and the service guarantee. In this paper, we propose a security-aware dynamic scheduling algorithm (SADSA) using a grid of computational elements (CEs) which performs this trade-off and tries to maximize the instantaneous average security level of the packets besides providing a guaranteed service. As packets arrive, we first assign them to the CEs based on the utilization value of a CE, which is the ratio of completion time and a deadline of the last packet in a CE. The security level of all the packets is then dynamically adjusted to meet the minimum required security level while maximizing the average security level of all the packets in that CE. We first show that the proposed assignment algorithm is NP-hard, is 2-competitive to the optimal solution, and that the proposed algorithm provides a sub-optimal solution. Further, using extensive simulation, we show that the proposed SADSA algorithm performs better in terms of guarantee ratio, average security level and overall performance compared to the existing algorithms.
The problem of designing a high-performance robot controller with multiple arithmetic processing units (APUs) is addressed. One attractive feature of the controller is that a minimum number of special-purpose hardware...
详细信息
The problem of designing a high-performance robot controller with multiple arithmetic processing units (APUs) is addressed. One attractive feature of the controller is that a minimum number of special-purpose hardware components are needed, and off-the-shelf components can be used. One main processor unit (MPU) schedules a number of APUs to produce the computational throughput. The depth-first/initial-heuristic-search (DF/IHS) algorithm is an efficient algorithm that solves the difficult nonpolynomial- (NP-) complete problem of scheduling a set of ordered computational tasks onto a multiprocessor system. When interprocessor communication overheads are appreciable, however it is not very effective in providing a practical near-optimum schedule, it fails to consider the problem of contention for shared resources. A multiprocessor scheduling algorithm which minimizes the effects of overhead and thus reduces the effect of contention is presented. The algorithm is used to derive the operational instructions for the APUs and the MPU for a multiple-APU-based robot controller. Simulations show that six MC68881 APUs can be used to generate the robot control computations in approximately 2.5 ms.< >
Cyber-physical system (CPS) is the core technology of Industry 4.0. The deterministic behaviors of the CPS require real-time deterministic guarantee. Therefore, this paper improves the ant colony optimization (ACO) in...
详细信息
Cyber-physical system (CPS) is the core technology of Industry 4.0. The deterministic behaviors of the CPS require real-time deterministic guarantee. Therefore, this paper improves the ant colony optimization (ACO) into a scheduling algorithm for time-triggered flows in time-sensitive network (TSN), a standard developed by the IEEE 802.1 Working Group that fully satisfies the strict end-to-end delay requirements of industrial applications. Simulation results show that the improved ACO (IACO) can schedule the time-triggered flows in the TSN excellently, and outperform the traditional ACO in convergence speed, optimization ability and the proneness to local optimum trap. To sum up, this paper provides an effective real-time guarantee for the TSNs. (C) 2020 The Authors. Published by Elsevier B.V. on behalf of Faculty of Engineering, Alexandria University.
Although link scheduling has been used to improve the performance of data gathering applications, unfortunately, existing link scheduling algorithms are either centralized or they rely on specific assumptions that are...
详细信息
Although link scheduling has been used to improve the performance of data gathering applications, unfortunately, existing link scheduling algorithms are either centralized or they rely on specific assumptions that are not realistic in wireless sensor networks. In this paper, we propose a distributed and concurrent link scheduling algorithm, called DICSA, that requires no specific assumption regarding the underlying network. The operation of DICSA is managed through two algorithms: (i) Primary State Machine (PSM): Enables each node to perform its own slot reservation;(ii) Secondary State Machine (SSM): Enables each node to concurrently participate in the slot reservation of its neighbors. Through these algorithms and a set of forbidden slots managed by them, DICSA provides concurrent and collision-free slot reservation. Our results show that the execution duration and energy consumption of DICSA are at least 50% and 40% less than that of DRAND, respectively. In terms of slot assignment efficiency, while our results show higher spatial reuse over DRAND, the maximum slot number assigned by DICSA is at least 60% lower than VDEC. In data-gathering applications, our results confirm the higher performance of DICSA in terms of throughput, delivery ratio and packet delay. We show that the network throughput achievable by DICSA is more than 50%, 70%, 90% and 170% higher than that of DRAND, SEEDEX, NCR and FPS, respectively. (C) 2014 Elsevier B.V. All rights reserved.
暂无评论