Search

The virtualization technology enhances resource utilization and scalability in the cloud environment. Multiple virtual machines with divergent specifications in terms of hardware and software can be run on a single physical machine. Performance of the applications degrades due to interference when multiple applications are executed simultaneously. This performance degradation affects the quality of service and service level agreement in a cloud environment. In this work, we design an interference-aware workload scheduling approach to execute latency-sensitive tasks in the cloud system. Here we built an interference prediction model to manage the interference efficiently and validated that model in a virtualized environment using Xen hypervisor. We further design a resource prediction model to predict the future resource requirement for the set of tasks using modified double exponential smoothing. This prediction model helps to deploy the required number of physical machines for each time duration. Using these two prediction models, we develop an interference-aware workload scheduling approach that minimizes the effect of interference to achieve a better quality of service in the cloud environment. The extensive simulations with Google cluster data show that our proposed approach improves task guarantee ratio and priority guarantee ratio by 3.32% and 3.63% respectively on average, while improving the resource utilization around 17.26% as compared to other state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

Many modern day cloud hosted applications such as virtual reality, real time games require low latency data access and computation to improve response time. So it is essential to bring the computation and data storage edge servers closer to the user's geographical location to improve response times and save bandwidth. In particulars, in online gaming and on demand video services, the required application data present at cloud servers need to be placed on the edge servers to provide low latency app-functionalities. The transfer of huge amount of data from cloud server to edge server incurs high cost and time penalties. Thus, we need an efficient way to solve edge data distribution (EDD) problem which distribute the application data to the edge servers that minimizes transfer cost. In this work, we provide a refined formulation of an optimal approach to solve the EDD problem using integer linear programming (ILP) technique. Due to the time complexity limitation of the ILP approach, we propose an O(k) approximation algorithm based on network Steiner tree estimation (EDD-NSTE) for estimating solutions to dense large-scale EDD problem. The proposed approach is analyzed to be 11/6 approximation which is better than the state-of-the-art 2 approximation EDD-A approach. The experimental evaluation through simulation using real world EUA data set demonstrate that the EDD-NSTE outperform state-of-the-art approach and other representative approaches. [ABSTRACT FROM AUTHOR]

In this paper, we proposed an effective approach for scheduling of multiprocessor unit time tasks with chain precedence on to large multiprocessor system. In this work, we considered splitable and non-splitable multiprocessor tasks, which is a new and interesting dimension to the generalized scheduling problem. The proposed longest chain maximum processor scheduling algorithm is proved to be optimal for uniform chains and monotone (non-increasing/non-decreasing) chains for both splitable and non-splitable multiprocessor unit time tasks chain. Scheduling arbitrary chains of non-splitable multiprocessor unit time tasks is proved to be NP-complete problem. But scheduling arbitrary chains of splitable multiprocessor unit time tasks is still an open problem to be proved whether it is NP-complete or can be solved in polynomial time. We have used three heuristics (a) maximum criticality first, (b) longest chain maximum criticality first and (c) longest chain maximum processor first for scheduling of arbitrary chains. We have also compared the performance of all three scheduling heuristics and found out that the proposed longest chain maximum processor first performs better in most of the cases. Also we have evaluated the performance of the mentioned heuristics by scheduling scientific work-flows on real multi-processor server platform and analyzed power and performance trade-off of the same scheduling policies. [ABSTRACT FROM AUTHOR]

In the current chip-multiprocessor era, 3D-stacked DRAM became an attractive alternative to mitigate the DRAM bandwidth wall problem. In a chip-multiprocessor, the 3D-stacked DRAM is architect either (a) to cache both local and remote data or (b) to cache only the local data. Caching only local data into the 3D-stacked DRAM enforces the chip-multiprocessors to suffer inter-node latency overhead while accessing remote data. However, caching both local and remote data onto the 3D-stacked DRAM requires a large coherence directory (tens of MBs) to ensure correctness. In this paper, we consider a 3D-stacked DRAM based chip-multiprocessor and perform a comparative study between (a) high level adaptive run-time data page mapping onto DRAM with an auxiliary small SRAM buffer as a performance booster, and (b) DRAM used as coherent cache. Our experiment on a 64 core chip-multiprocessor system with 4GB of 3D-stacked DRAM shows that our adaptive run-time data page mapping on DRAM along with an SRAM buffer outperforms the base-case (where DRAM caches only local data) by an average of 48%. Moreover, our method shows a performance improvement by an average of 40% when compared with a recent state-of-art work (where DRAM caches both local and remote data). [ABSTRACT FROM AUTHOR]

Software‐based self‐test (SBST) method is one of the widely used test techniques in processors. SBST scheme provides high fault coverage but incurs long detection latencies in case of intermittent faults (IFs) in online testing mode, due to large size and longer execution time of the test codes. A study of fragmented SBST testing approaches is conducted to select the most efficient fragmented testing strategy. For the selected fragmented SBST method, a reliable set of SBST code fragments with minimal fault detection latency is determined. However, it incurs inconsiderable overall fault coverage drop, compared to the coverage of the complete SBST test code. From experimental results on MIPS Processor, a set of 20 fragments of test tasks with 80% individual fault coverage was observed to have the highest reliability of all sets of fragments. A larger test task (i.e. complete SBST test code) with 96.3% coverage and a test period of 8 ms was replaced by these 20 fragments, which provided an overall coverage of 96% with an individual test period of 0.4 ms, to detect the same set of IFs. [ABSTRACT FROM AUTHOR]

The extensive use of cloud services in different domains triggers the efficient use of cloud resources to achieve maximum profit. The heterogeneous nature of data centers and the heterogeneous resource requirement of user applications create a scope of improvement in task scheduling. The resource requirements in terms of task constraints must be fulfilled for the tasks to be admitted to the system. Once a task admitted to the system, it may violate service level agreement and incurs penalty due to the disproportionate resource allocation at run time. The latency-sensitive and short-lived workloads need effective scheduling to gain more profit. In this work, we propose Heuristic of Ordering and Mapping for Constraint Aware Profit Maximization (HOM-CAPM) problem for efficient scheduling of tasks with constraints and deadlines to gain maximum profit. The HOM-CAPM approach considers estimation of task execution time in a heterogeneous environment, efficient task ordering, and profit-based task allocation to maximize the overall profit of the cloud system. To gain maximum profit the proposed heuristic considers two cases, (a) not allowing the tasks for execution if it expected to miss its deadline and (b) allowing the task which earns substantial profit even though it is expected to miss its deadline. The results of the extensive simulation using Google trace data as input show that our proposed HOM-CAPM approach generates more profit than other state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

Cloud environment uses data center with a huge number of computational resources, and the probability of failing any of the resources increases with scale. Failures cause unavailability of services, which affects the reliability of the system. It is essential to consider the reliability issue for application deployment in the cloud, considering the failure of the resources. In this work, we address the reliability aware scheduling of tasks with hard deadlines in the cloud environment. We design, analyze and provide solutions for two special cases of the problem where (a) tasks have a common deadline on the machines with equal failure rate, and (b) tasks with equal execution time. For the general case of the problem, we propose two-phase heuristic approaches, one is the task ordering, and other is tasks mapping to machines. The performance of different task orderings and task mapping approaches is evaluated through simulation using synthetic and real traces. Based on the simulation result, the earliest due date ordering of tasks and mapping of the current task to the most reliable machine along with long task dropping performs better in general settings. We observe that task repetition and replication further improve the performance of the heuristics. [ABSTRACT FROM AUTHOR]

Cloud computing has emerged to be a promising computing paradigm of the recent time. As the high energy consumption in the cloud system creates several problems, the cloud service providers need to focus on the energy consumption along with providing the required service to their users. Cloud system needs to efficiently execute various real-time applications and designing energy-efficient scheduling algorithms for these applications has gained the research momentum. In this paper, we consider scheduling of real-time tasks for a virtualized cloud system which provides VMs with discrete compute capacities. Depending on the characteristics of the tasks, we divide the problem into four subproblems and propose solution for each subproblem. For the subproblem with arbitrary execution time and deadline of tasks, we use four different methods to cluster the tasks depending on their deadline values. Experiment is performed in CloudSim tool to make a comparison among the clustering methods and results show that the clustering method can be chosen based on the specification of the cloud system. We also made a comparison of our approach with standard energy-efficient scheduling technique both for the synthetic data sets and for the real world trace and we observed an average energy reduction of around 17 % and 15 % for the synthetic data sets and for the real world trace respectively (as compared to the baseline policy). [ABSTRACT FROM AUTHOR]

Software-based test (SBST) techniques are increasingly being used for testing of modern processors because of the ease of synthesis using evolutionary approaches, coverage for difficult to test faults, non-intrusive nature, low hardware overhead, etc. However, the test synthesis time required by SBST is high. In this paper, an advanced SBST technique, termed as Rapid SBST (RSBST) is proposed that reduces the overall test synthesis time by reusing the simulation responses of existing test programs of identical observability. The test codes, developed using the evolutionary process, that produce similar fault simulation results are reused for the fault evaluation. We exploit this reusability to enhance the speed of the test synthesis process. The efficacy of the proposed scheme is demonstrated on a 32-bit MIPS processor and on a minimal configuration of 7-stage SPARC V8 Leon3 soft processor. The traditional SBST synthesis requires 122 hours for the MIPS processor and 142 hours for the Leon3 processor to develop test program sets that cover 93.9% and 92.9% of the behavioral-level faults of these processors, respectively. An existing enhanced greedy-cover method, that also detects the hard-to-test faults, improves the coverage towards 96.3% for the MIPS processor and 95.8% for the Leon3 processor, but this slower test development consumes 168 hours and 172 hours, respectively. In the proposed RSBST scheme, the synthesized test codes achieve an adequate fault coverage of 96.1% for the MIPS processor and 95.5% for the Leon3 processor. This accelerated test pattern generation takes 90 hours and 98 hours for these two processors. So it may be concluded that the proposed RSBST technique speeds up the traditional SBST synthesis by a factor of 1.35 while maintaining the fault coverage above 95.5%. To validate the test quality evaluation using behavioral fault models, a strong correlation (94.8%) between the behavioral faults and gate-level faults of MIPS processor is demonstrated and verified for the proposed RSBST scheme. Also, the simulation responses of the test programs synthesized by RSBST scheme consumes only 14.25% of storage space when compared with the storage consumption of the actual simulation used by the existing test code generation methods. [ABSTRACT FROM AUTHOR]

Software-based self-testing (SBST) is introduced for at-speed testing of processors, which is difficult with any of the external testing techniques. Evolutionary approaches are used for the automatic synthesis of SBST programs. However, a number of hard-to-detect faults remain unidentified by these autogenerated test programs. Also, these approaches have considered fault models which have low correlation with the gate-level fault models. This paper presents a greed-based strategy, where the instruction sequences that detect the freshly identified faults are preserved throughout the evolutionary process to identify the hard-to-test faults of the processor. Subsequently, the overall coverage is also improved. A selection probability is estimated from the testability properties of the processor components and assigned to every instruction to accelerate the test synthesis. The range of performance and scalability are comprehensively evaluated on a configurable MIPS processor and a full-fledged 7-stage pipeline SPARC V8 Leon3 soft processor using behavioral fault models. The efficacy of our approach was explained by demonstrating the correlation between behavioral faults and gate-level faults of MIPS processor for the proposed scheme. Experimental results show that improved coverages of 96.32% for the MIPS processor and 95.8% for the Leon3 processor are achieved in comparison with the conventional methods, which have about 90% coverage on the average. [ABSTRACT FROM AUTHOR]