http://hdl.handle.net/2005/18 2013-04-30T22:54:50Z http://hdl.handle.net/2005/1955 Title: Compiler Transformations For Improving The Performance Of Software Transactional Memory Authors: Mannarswamy, Sandya S Abstract: Expressing synchronization using traditional lock based primitives has been found to be both error-prone and restrictive. Hence there has been considerable research work to develop scalable and programmer-friendly alternatives to lock-based synchronization. Atomic sections have been proposed as a programming idiom for expressing synchronization at a higher-level of abstraction than locks. One way of supporting atomic sections in software is to rely on an underlying Software Transactional Memory (STM) implementation. While STM offers the promise of being a programming paradigm which is less error-prone and more programmer friendly compared to traditional lock-based synchronization, it also needs to be competitive in performance in order for it to be adopted in mainstream software. Unfortunately STMs do not meet the performance goals and are known to incur excessive performance overheads. Prior work by other researchers and our performance analysis of STM applications show that conflicts and the resulting aborts are a major performance bottleneck for STM applications. Second we find that, supporting fine-grained optimistic concurrency can have significant impact on the cache behavior of applications running on STM and hence can adversely affect STM performance. Our systematic quantitative analysis of the cache behavior of STM applications as well as prior work on qualitative analysis of STM overheads show that cache overheads constitute a major performance bottleneck for STM applications. Hence in this thesis, we focus on addressing these two major STM performance bottlenecks. Current STM implementations are typically application unaware in that they do not analyze the application and use that knowledge to improve the application performance on STM. Closer integration of transactions with the programming languages opens up the possibility of using the compiler to analyze STM applications and using that knowledge to perform application code transformations to improve the application performance on STM automatically and in a manner transparent to the programmer. This motivated us to address the two major STM performance bottlenecks namely poor cache performance and performance penalty due to aborts, by compiler transformations. In order to pinpoint the cache bottlenecks of STM, we perform a detailed experimental evaluation of the cache behavior of STM applications and quantify the impact of the different STM factors on the cache misses experienced by the applications. We propose a set of compiler transformations targeted to address the cache performance bottlenecks identified by our analysis. Next we turn our attention to compiler analysis and transformations targeted at reducing the performance overheads due to transactional aborts, effectively utilizing the compiler’s knowledge of the data access patterns of the application. Since not all applications are designed with optimistic concurrency in mind, real world applications typically contain certain atomic sections which are not amenable to STM’s optimistic concurrency control and hence suffer from excessive transactional abort overheads. We propose two compiler techniques for handling such atomic sections. Another major cause of transactional conflicts leading to unnecessary aborts is the uniform granularity access tracking scheme employed by STM implementations. Using a single uniform access tracking granularity leads to poor lock assignment by STM. We propose techniques which use compiler’s knowledge of an application to improve the application unaware lock assignment made by the STM. Last as transactional abort overheads impact STM performance adversely, we propose a compiler-based approach to reduce the transactional abort overheads by reconciling certain kinds of transactions instead of aborting them and then performing a complete re-execution. We show that our combined set of compiler transformations are effective in improving the performance of a set of STAMP benchmarks by reducing the execution time by 7.48% to 54.82%, aborts by 8.98% to 56.61% and the average D-cache miss latency by up to 33.51%. 2013-03-26T18:30:00Z http://hdl.handle.net/2005/1654 Title: Novel Mechanisms For Allocation Of Heterogeneous Items In Strategic Settings Authors: Prakash, Gujar Sujit Abstract: Allocation of objects or resources to competing agents is a ubiquitous problem in the real world. For example, a federal government may wish to allocate different types of spectrum licenses to telecom service providers; a search engine has to assign different sponsored slots to the ads of advertisers; etc. The agents involved in such situations have private preferences over the allocations. The agents, being strategic, may manipulate the allocation procedure to get a favourable allocation. If the objects to be allocated are heterogeneous (rather than homogeneous), the problem becomes quite complex. The allocation problem becomes even more formidable in the presence of a dynamic supply and/or demand. This doctoral work is motivated by such problems involving strategic agents, heterogeneous objects, and dynamic supply and/or demand. In this thesis, we model such problems in a standard game theoretic setting and use mechanism design to propose novel solutions to the problems. We extend the current state-of-the-art in a non-trivial way by solving the following problems: Optimal combinatorial auctions with single minded bidders, generalizing the existing methods to take into account multiple units of heterogeneous objects Multi-armed bandit mechanisms for sponsored search auctions with multiple slots, generalizing the current methods that only consider a single slot. Strategyproof redistribution mechanisms for heterogeneous objects, expanding the scope of the current state of practice beyond homogeneous objects Online allocation mechanisms without money for one-sided and two-sided matching markets, extending the existing methods for static settings. 2012-04-19T18:30:00Z http://hdl.handle.net/2005/1285 Title: Hard Drive Failure Prediction : A Rule Based Approach Authors: Agrawal, Vipul Abstract: The ability to accurately predict an impending hard disk failure is important for reliable storage system design. The facility provided by most hard drive manufacturers, called S.M.A.R.T. (self-monitoring, analysis and reporting technology), has been shown by current research to have poor predictive value. The problem of finding alternatives to S.M.A.R.T. for predicting disk failure is an area of active research. In this work, we present a rule discovery methodology, and show that it is possible to construct decision support systems that can detect such failures using information recorded from live disks. It is desired that any such prediction methodology should have high accuracy and must have ease of interpretability. Black box models can deliver highly accurate solutions but do not provide an understanding of events which explains the decision given by it. To this end we explore rule based classifiers for predicting hard disk failures from various disk events. We show that it is possible to learn easy to understand rules from disk events. Our evaluation shows that our system can be tuned either to have a high failure detection rate (i.e., classify a bad disk as bad) or to have a low false alarm rate (i.e., not classify a good disk as bad). We also propose a modification of MLRules algorithm for classification of data with imbalanced class distributions. The existing algorithm, assuming relatively balanced class distributions and equal misclassfication costs, performs poorly in classification of such datasets. The performance can be considerably improved by introducing cost- sensitive learning to the existing framework. 2011-07-11T18:30:00Z http://hdl.handle.net/2005/1384 Title: A Low-Complexity Algorithm For Intrusion Detection In A PIR-Based Wireless Sensor Network Authors: Subramanian, Ramanathan Abstract: This thesis investigates the problem of detecting an intruder in the presence of clutter in a Passive Infra-Red (PIR) based Wireless Sensor Network (WSN). As one of the major objectives in a WSN is to maximize battery life, data transmission and local computations must be kept to a minimum as they are expensive in terms of energy. But, as intrusion being a rare event and cannot be missed, local computations expend more energy than data transmission. Hence, the need for a low-complexity algorithm for intrusion detection is inevitable. A low-complexity algorithm for intrusion detection in the presence of clutter arising from wind-blown vegetation, using PIR sensors is presented. The algorithm is based on a combination of Haar Transform (HT) and Support Vector Machine (SVM) based training. The amplitude and frequency of the intruder signature is used to differentiate it from the clutter signal. The HT was preferred to Discrete Fourier Transform (DFT) in computing the spectral signature because of its computational simplicity -just additions and subtractions suffice (scaling coefficients taken care appropriately). Intruder data collected in a laboratory and clutter data collected from various types of vegetation were fed into SVM for training. The optimal decision rule returned by SVM was then used to separate intruder from clutter. Simulation results along with some representative samples in which intrusions were detected and the clutter being rejected by the algorithm is presented. The implementation of the proposed intruder-detection algorithm in a network setting comprising of 20 sensing nodes is discussed. The field testing performance of the algorithm is then discussed. The limitations of the algorithm is also discussed. A closed-form analytical expression for the signature generated by a human moving along a straight line in the vicinity of the PIR sensor at constant velocity is provided. It is shown to be a good approximation by showing a close match with the real intruder waveforms. It is then shown how this expression can be exploited to track the intruder from the signatures of three well-positioned sensing nodes. 2011-08-24T18:30:00Z