The Experts below are selected from a list of 49668 Experts worldwide ranked by ideXlab platform
Dawei Sun - One of the best experts on this subject based on the ideXlab platform.
-
state and runtime aware Scheduling in elastic stream computing systems
Future Generation Computer Systems, 2019Co-Authors: Shang Gao, Dawei Sun, Xunyun Liu, Xinqi Zheng, Rajkumar BuyyaAbstract:Abstract State and runtime-aware Scheduling is one of the problems that is hard to resolve in elastic big data stream computing systems, as the state of each vertex is different, and the arrival rate of data streams fluctuates over time. A state and runtime-aware Scheduling Framework should be able to dynamically adapt to the fluctuation of the arrival rate of data streams and be aware of vertex states and resource availability. Currently, there is an increasing number of research work focusing on application Scheduling in stream computing systems, however, this problem is still far from being completely solved. In this paper, we focus on the state of vertex in applications and the runtime feature of resources in a data center, and propose a state and runtime-aware Scheduling Framework (Sra-Stream) for elastic streaming computing systems, which incorporates the following features: (1) Profiling mathematical relationships between the system response time and the arrival rate of data streams, and identifying relevant resource constraints to meet the low response time and high throughput objectives. (2) Classifying vertex into stateless vertex or stateful vertex from a quantitative perspective, and achieving vertex parallelization by considering the state of the vertex. (3) Demonstrating a proposed stream application Scheduling scheme consisting of a modified first-fit based runtime-aware data tuple Scheduling strategy at the initial stage, and a maximum latency-sensitive based runtime-aware data stream Scheduling strategy at the online stage, by considering the current Scheduling status of the application. (4) Evaluating the achievement levels of low response time and high throughput objectives in a real-world elastic stream computing system. Experimental results conclusively demonstrate that the proposed Sra-Stream provides significant performance improvements on achieving the low system response time and high system throughput.
Lantz Moore - One of the best experts on this subject based on the ideXlab platform.
-
SmartNet: A Scheduling Framework for heterogeneous computing
Proceedings of the International Symposium on Parallel Architectures Algorithms and Networks I-SPAN, 1996Co-Authors: Rudolf Freund, Taylor Kidd, Debbie Hensgen, Lantz MooreAbstract:SmartNet is a Scheduling Framework for heterogeneous systems. Preliminary conservative simulation results for one of the optimization criteria, show a 1.21 improvement over Load Balancing and a 25.9 improvement over Limited Best Assignment, the two policies that evolved from homogeneous environments. SmartNet achieves these improvements through the implementation of several innovations. It recognizes and capitalizes on the inherent heterogeneity of computers in today's distributed environments; it recognizes and accounts for the underlying non-determinism of the distributed environment; it implements an original partitioning approach, making runtime prediction more accurate and useful; it effectively schedules based on all shared resource usage, including network characteristics; and it uses statistical and filtering techniques, making a greater amount of prediction information available to the Scheduling engine. In this paper, the issues associated with automatically managing a heterogeneous environment are reviewed, SmartNet's architecture and implementation are described, and performance data is summarized.
Rajkumar Buyya - One of the best experts on this subject based on the ideXlab platform.
-
state and runtime aware Scheduling in elastic stream computing systems
Future Generation Computer Systems, 2019Co-Authors: Shang Gao, Dawei Sun, Xunyun Liu, Xinqi Zheng, Rajkumar BuyyaAbstract:Abstract State and runtime-aware Scheduling is one of the problems that is hard to resolve in elastic big data stream computing systems, as the state of each vertex is different, and the arrival rate of data streams fluctuates over time. A state and runtime-aware Scheduling Framework should be able to dynamically adapt to the fluctuation of the arrival rate of data streams and be aware of vertex states and resource availability. Currently, there is an increasing number of research work focusing on application Scheduling in stream computing systems, however, this problem is still far from being completely solved. In this paper, we focus on the state of vertex in applications and the runtime feature of resources in a data center, and propose a state and runtime-aware Scheduling Framework (Sra-Stream) for elastic streaming computing systems, which incorporates the following features: (1) Profiling mathematical relationships between the system response time and the arrival rate of data streams, and identifying relevant resource constraints to meet the low response time and high throughput objectives. (2) Classifying vertex into stateless vertex or stateful vertex from a quantitative perspective, and achieving vertex parallelization by considering the state of the vertex. (3) Demonstrating a proposed stream application Scheduling scheme consisting of a modified first-fit based runtime-aware data tuple Scheduling strategy at the initial stage, and a maximum latency-sensitive based runtime-aware data stream Scheduling strategy at the online stage, by considering the current Scheduling status of the application. (4) Evaluating the achievement levels of low response time and high throughput objectives in a real-world elastic stream computing system. Experimental results conclusively demonstrate that the proposed Sra-Stream provides significant performance improvements on achieving the low system response time and high system throughput.
Insup Lee - One of the best experts on this subject based on the ideXlab platform.
-
removing abstraction overhead in the composition of hierarchical real time systems
Real Time Technology and Applications Symposium, 2011Co-Authors: Sanjian Chen, Insup Lee, Linh Thi Xuan Phan, Jaewoo Lee, Oleg SokolskyAbstract:The hierarchical real-time Scheduling Framework is a widely accepted model to facilitate the design and analysis of the increasingly complex real-time systems. Interface abstraction and composition are the key issues in the hierarchical Scheduling Framework analysis. Schedulability is essential to guarantee that the timing requirements of all components are satisfied. In order for the design to be resource efficient, the composition must be bandwidth optimal. Associativity is desirable for open systems in which components may be added or deleted at run time. Previous techniques on compositional Scheduling are either not resource efficient in some aspects, or cannot achieve optimality and associativity at the same time. In this paper, several important properties regarding the periodic resource model are identified. Based on those properties, we propose a novel interface abstraction and composition Framework which achieves schedulability, optimality, and associativity. Our approach eliminates abstraction overhead in the composition.
-
A Compositional Scheduling Framework for Digital Avionics Systems
2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2009Co-Authors: Arvind Easwaran, Insup Lee, Oleg Sokolsky, Steve VestalAbstract:ARINC specification 653-2 describes the interface between application software and underlying middleware in a distributed real-time avionics system. The real-time workload in this system comprises of partitions, where each partition consists of one or more processes. Processes incur blocking and preemption overheads and can communicate with other processes in the system. In this work we develop compositional techniques for automated Scheduling of such partitions and processes. At present, system designers manually schedule partitions based on interactions they have with the partition vendors. This approach is not only time consuming, but can also result in under utilization of resources. In contrast, the technique proposed in this paper is a principled approach for Scheduling ARINC-653 partitions and therefore should facilitate system integration.
-
hierarchical Scheduling Framework for virtual clustering of multiprocessors
Euromicro Conference on Real-Time Systems, 2008Co-Authors: Insik Shin, Arvind Easwaran, Insup LeeAbstract:Scheduling of sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good utilization bounds. These algorithms can be broadly classified into two categories: partitioned Scheduling in which tasks are statically assigned to individual processors, and globalScheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based Scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster areglobally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based Scheduling algorithms, and also consider properties that minimize processor utilization of individual clusters. Since neither partitioned nor global strategies dominate over the other, cluster-based Scheduling is a natural direction for research towards achieving improved utilization bounds.
-
compositional real time Scheduling Framework with periodic model
ACM Transactions in Embedded Computing Systems, 2008Co-Authors: Insik Shin, Insup LeeAbstract:It is desirable to develop large complex systems using components based on systematic abstraction and composition. Our goal is to develop a compositional real-time Scheduling Framework to support abstraction and composition techniques for real-time aspects of components. In this paper, we present a formal description of compositional real-time Scheduling problems, which are the component abstraction and composition problems. We identify issues that need be addressed by solutions and provide our Framework for the solutions, which is based on the periodic interface. Specifically, we introduce the periodic resource model to characterize resource allocations provided to a single component. We present exact schedulability conditions for the standard Liu and Layland periodic task model and the proposed periodic resource model under EDF and RM Scheduling, and we show that the component abstraction and composition problems can be addressed with periodic interfaces through the exact schedulability conditions. We also provide the utilization bounds of a periodic task set over the periodic resource model and the abstraction bounds of periodic interfaces for a periodic task set under EDF and RM Scheduling. We finally present the analytical bounds of overheads that our solution incurs in terms of resource utilization increase and evaluate the overheads through simulations.
-
compositional real time Scheduling Framework
Real-Time Systems Symposium, 2004Co-Authors: Insik Shin, Insup LeeAbstract:Our goal is to develop a compositional real-time Scheduling Framework so that global (system-level) timing properties can be established by composing independently (specified and) analyzed local (component-level) timing properties. The two essential problems in developing such a Framework are: (1) to abstract the collective real-time requirements of a component as a single real-time requirement and (2) to compose the component demand abstraction results into the system-level real-time requirement. In our earlier work, we addressed the problems using the Liu and Layland periodic model. In this paper, we address the problems using another well-known model, a bounded-delay resource partition model, as a solution model to the problems. To extend our Framework to this model, we develop an exact feasibility condition for a set of bounded-delay tasks over a bounded-delay resource partition. In addition, we present simulation results to evaluate the overheads that the component demand abstraction results incur in terms of utilization increase. We also present utilization bound results on a bounded-delay resource model.
Hai Jin - One of the best experts on this subject based on the ideXlab platform.
-
Spatial Locality Aware Disk Scheduling in Virtualized Environment
IEEE Transactions on Parallel and Distributed Systems, 2015Co-Authors: Xiao Ling, Shadi Ibrahim, Hai JinAbstract:Exploiting spatial locality, a key technique for improving disk I/O utilization and performance, faces additional challenges in the virtualized cloud because of the transparency feature of virtualization. This paper contributes a novel disk I/O Scheduling Framework, named Pregather, to improve disk I/O efficiency through exposure and exploitation of the special spatial locality in the virtualized environment, thereby improving the performance of disk-intensive applications without harming the transparency feature of virtualization. The key idea behind Pregather is to implement an intelligent model to predict the access regularity of spatial locality for each VM. Moreover, Pregather embraces an adaptive time slice allocation scheme to further reduce the resource contention and ensure fairness among VMs. We implement the Pregather disk Scheduling Framework and perform extensive experiments that involve multiple simultaneous applications of both synthetic benchmarks and MapReduce applications on Xen-based platforms. Our experiments demonstrate the accuracy of our prediction model and indicate that Pregather results in the high disk spatial locality and a significant improvement in disk throughput and application performance.
-
Exploiting Spatial Locality to Improve Disk Efficiency in Virtualized Environments
2013Co-Authors: Xiao Ling, Shadi Ibrahim, Hai Jin, Songqiao TaoAbstract:Virtualization has become a prominent tool in data centers and is extensively leveraged in cloud environments: it enables multiple virtual machines (VMs) -- with multiple operating systems and applications -- to run within a physical server. However, virtualization introduces the challenging issue of preserving the high disk utilization (i.e., reducing the seek delay and rotation overhead) when allocating disk resources to VMs. Exploiting spatial locality, a key technique for improving disk utilization and performance, faces additional challenges in the virtualized cloud because of the transparency feature of virtualization (hypervisors do not have the information about the access patterns of applications running within each VM). To this end, this paper contributes a novel disk I/O Scheduling Framework, named Pregather, to improve disk I/O efficiency through exposure and exploitation of the special spatial locality in the virtualized environment (regional and sub-regional spatial locality corresponds to the virtual disk space and applications' access patterns, respectively), thereby improving the performance of disk-intensive applications without harming the transparency feature of virtualization (without a priori knowledge of the applications' access patterns). The key idea behind Pregather is to implement an intelligent model to predict the access regularity of sub-regional spatial locality for each VM. We implement the Pregather disk Scheduling Framework and perform extensive experiments that involve multiple simultaneous applications of both synthetic benchmarks and a MapReduce application on Xen-based platforms. Our experiments demonstrate the accuracy of our prediction model and indicate that Pregather results in the high disk spatial locality and a significant improvement in disk throughput and application performance.
