etd@IISc Community:http://hdl.handle.net/2005/12018-02-18T00:02:08Z2018-02-18T00:02:08ZDesigning Energy-Aware Optimization Techniques through Program Behaviour AnalysisKommaraju, Ananda Varadhanhttp://hdl.handle.net/2005/31332018-02-17T21:32:12Z2018-02-17T18:30:00ZTitle: Designing Energy-Aware Optimization Techniques through Program Behaviour Analysis
Authors: Kommaraju, Ananda Varadhan
Abstract: Green computing techniques aim to reduce the power foot print of modern embedded devices with particular emphasis on processors, the power hot-spots of these devices. In this thesis we propose compiler-driven and profile-driven optimizations that reduce power consumption in a modern embedded processor. We show that these optimizations reduce power consumption in functional units and memory subsystems with very low performance loss. We present three new techniques to reduce power consumption in processors, namely, transition aware scheduling, leakage reduction in data caches using criticality analysis, and dynamic power reduction in data caches using locality analysis of data regions.
A novel instruction scheduling technique to address leakage power consumption in functional units is proposed. This scheduling technique, transition aware scheduling, is motivated by idle periods that arise in the utilization of functional units during program execution. A continuously large idle period in a functional unit can be exploited to place the unit in low power state. This novel scheduling algorithm increases the duration of idle periods without hampering performance and drives power gating in these periods. A power model defined with idle cycles as a parameter shows that this technique saves up to 25% of leakage power with very low performance impact.
In modern embedded programs, data regions can be classified as critical and non-critical. Critical data regions significantly impact the performance. A new technique to identify such data regions through profiling is proposed. This technique along with a new criticality based cache policy is used to control the power state of the data cache. This scheme allocates non-critical data regions to low-power cache regions, thereby reducing leakage power consumption by up to 40% without compromising on the performance.
This profiling technique is extended to identify data regions that have low locality. Some data regions have high data reuse. A locality based cache policy based on cache parameters like size and associativity is proposed. This scheme reduces dynamic as well as static power consumption in the cache subsystem. This optimization reduces 25% of the total power consumption in the data caches without hampering the execution time.
In this thesis, the problem of power consumption of a program is decoupled from the number of processor cores. The underlying architecture model is simplified to abstract away a variety of processor scenarios. This simplified model can be scaled up to be implemented in various multi-core architecture models like Chip Multi-Processors, Simultaneous Multi-Threaded Processors, Chip Multi-Threaded Processors, to name a few.
The three techniques proposed in this thesis leverage underlying hardware features like low power functional units, drowsy caches and split data caches. These techniques reduce power consumption of a wide range of benchmarks with low performance loss.2018-02-17T18:30:00ZVariants and Generalization of Some Classical Problems in Combinatorial GeometryBharadwaj, Subramanya B Vhttp://hdl.handle.net/2005/31342018-02-17T21:40:36Z2018-02-17T18:30:00ZTitle: Variants and Generalization of Some Classical Problems in Combinatorial Geometry
Authors: Bharadwaj, Subramanya B V
Abstract: In this thesis we consider extensions and generalizations of some classical problems
in Combinatorial Geometry. Our work is an offshoot of four classical problems in
Combinatorial Geometry. A fundamental assumption in these problems is that the
underlying point set is R2. Two fundamental themes entwining the problems considered
in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’ in P always occur. One of the first results was the Erd˝os-Szekeres Theorem which showed that there exists a f(n) such that if |P| ≥ f(n) then there exists a convex subset S ⊆ P, |S| = n i.e., a subset which is a convex polygon of size n. A considerable number of such results have been found since.
Avis et al. in 2001 posed the following question which we call the n-interior point
problem: Is there a finite integer g(n) for every n, such that, every point set P with
g(n) interior points has a convex subset S ⊆ P with n interior points. i.e. a subset
which is a convex polygon that contains exactly n interior points. They showed that
g(1) = 1, g(2) = 4. While it is known that g(3) = 9, it is not known whether g(n) exists for n ≥ 4. In the first part of this thesis, we give a positive solution to the n-interior point problem for point sets with bounded number of convex layers.
We say a family of geometric objects C in Rd has the (l, k)-property if every subfamily
C′ ⊆ C of cardinality at most l is k-piercable. Danzer and Gr¨unbaum posed
the following fundamental question which can be considered as a generalised version of
Helly’s theorem: For every positive integer k, does there exist a finite g(k, d) such that if any family of convex objects C in Rd has the (g(k, d), k)-property, then C is k-piercable? Very few results(mostly negative) are known.
Inspired by the original question of Danzer and Gr¨unbaum we consider their question
in an abstract set theoretic setting. Let U be a set (possibly infinite). Let C be a family of subsets of U with the property that if C1, . . . ,Cp+1 ∈ C are p + 1 distinct subsets, then |C1 ∩ · · · ∩Cp+1| ≤ l. In the second part of this thesis, we show in this setting, the first general positive results for the Danzer Grunbaum problem. As an extension, we show polynomial sized kernels for hitting set and covering problems in our setting.
In the third part of this thesis, we broadly look at hitting and covering questions
with respect to points and families of geometric objects in Rd. Let P be a subset of points(possibly infinite) in Rd and C be a collection of subsets of P induced by objects of a given family. For the system (P, C), let νh be the packing number and νc the dual packing number. We consider the problem of bounding the transversal number τ h and the dual transversal number τ c in terms of νh and νc respectively.
These problems has been well studied in the case when P = R2. We systematically
look at the case when P is finite, showing bounds for intervals, halfspaces, orthants,
unit squares, skylines, rectangles, halfspaces in R3 and pseudo disks. We show bounds for rectangles when P = R2.
Given a point set P ⊆ Rd, a family of objects C and a real number 0 < ǫ < 1, the
strong epsilon net problem is to find a minimum sized subset Q ⊆ P such that any
object C ∈ C with the property that |P ∩C| ≥ ǫn is hit by Q. It is customary to express
the bound on the size of the set Q in terms of ǫ.
Let G be a uniform √n × √n grid. It is an intriguing question as to whether we
get significantly better bounds for ǫ-nets if we restrict the underlying point set to be the grid G. In the last part of this thesis we consider the strong epsilon net problem for families of geometric objects like lines and generalized parallelograms, when the underlying point set is the grid G. We also introduce the problem of finding ǫ-nets for arithmetic progressions and give some preliminary bounds.2018-02-17T18:30:00ZPWM Techniques for Split-Phase Induction Motor DriveRakesh, P Rhttp://hdl.handle.net/2005/31362018-02-17T22:02:27Z2018-02-17T18:30:00ZTitle: PWM Techniques for Split-Phase Induction Motor Drive
Authors: Rakesh, P R
Abstract: A split-phase induction motor (SPIM) is obtained by splitting each of the three-phase stator windings of an induction motor into two equal halves. This results in two sets of three-phase windings with a spatial angle diﬀerence of 30◦ (electrical) between them. The two sets of windings are fed from two diﬀerent voltage-source inverters for speed control of the split-phase motor drive. Low dc bus voltage requirement and improved torque profile are some of the advantages of the split-phase motor, compared to the normal three-phase induction motor.
A pulse width modulation (PWM) technique is used to produce the gating signals for the power semiconductor devices in the two inverters. The PWM technique can either be a carrier comparison (CC) based method or a space-vector (SV) based scheme. The carrier based PWM methods employ six modulating waves, which are compared against a common triangular carrier to generate the gating pulses. In space-vector based PWM schemes, the voltage reference is specified in terms of a rotating reference vector. In each subcycle, a set of voltage vectors are applied for appropriate durations of time to produce an average vector equal to the reference vector. Unlike three-phase induction motor drives, where the voltage vectors are two dimensional, the voltage vectors in the case of SPIM drive are four dimensional. This thesis presents a detailed survey on carrier-comparison based and space-vector based PWM techniques for the SPIM drive.
In this thesis, sine-triangle PWM (STPWM) is analyzed from a space-vector perspective. The set of voltage vectors applied and the sequence of application of the voltage vectors in each half-carrier cycle are studied. The analysis shows that the set of voltage vectors and the switching sequence employed by STPWM are diﬀerent from those used by the well known SVPWM tech-niques.
Two other CC based PWM techniques, based on common mode injection, are considered for the SPIM drive. In one method, the common-mode signal is derived from all the six modulating signals, and is the same for both the inverters. In the second method, the common-mode signal is diﬀerent for the two inverters; each common-mode signal is derived from the three-phase sinusoidal signals of the respective inverter. The study shows that the latter method has the highest dc bus utilization and results in the lowest total harmonic distortion (THD) among the CC PWM techniques.
An experimental comparison of the three carrier-comparison techniques with three well known space-vector PWM techniques is presented. Total harmonic distortion (THD) of the line current is measured at diﬀerent modulation indices for all six techniques. The experimental results are obtained from a 6kW, 200V, 50Hz split-phase induction motor drive, with constant V /F ratio. The PWM techniques are implemented using an ALTERA cyclone II field programmable gate array (FPGA) digital controller.
One of the SV techniques, termed here as 4-dimensional 24-sector (4D24SEC) PWM is found to be the best in terms of line current THD among all the CC and SV based PWM techniques considered. However, compared to any carrier-based technique, implementation of the 4D24SEC PWM based on the space vector approach is found to be resource intensive. Hence, an equivalent carrier-based implementation of 4D24SEC PWM is proposed in this thesis. The feasibility of the proposed approach is verified experimentally, and is found to be consuming much less logical resources than the space-vector implementation (i.e. 4102 logical elements for the CC approach as against 33,655 logical elements for the SV approach).
A new space-vector PWM technique is also proposed in the thesis. This technique utilizes a new set of voltage vectors and a new switching sequence, which are motivated by the analyses of the carrier-based methods, presented earlier. The proposed technique is implemented, and is compared with other space-vector and carrier-based methods at diﬀerent modulation indices and switching frequencies. The proposed PWM technique is found to have the same dc-bus utilization as the existing 4-dimensional SV based PWM techniques. The performance of the proposed method is found to be not better than existing 4-dimensional SV PWM methods. The possibilities for new switching sequence is being explored here.2018-02-17T18:30:00ZBayes Optimal Feature Selection for Supervised LearningSaneem Ahmed, C Ghttp://hdl.handle.net/2005/31382018-02-17T22:26:00Z2018-02-17T18:30:00ZTitle: Bayes Optimal Feature Selection for Supervised Learning
Authors: Saneem Ahmed, C G
Abstract: The problem of feature selection is critical in several areas of machine learning and data analysis such as, for example, cancer classification using gene expression data, text categorization, etc. In this work, we consider feature selection for supervised learning problems, where one wishes to select a small set of features that facilitate learning a good prediction model in the reduced feature space. Our interest is primarily in filter methods that select features independently of the learning algorithm to be used and are generally faster to implement compared to other types of feature selection algorithms. Many common filter methods for feature selection make use of information-theoretic criteria such as those based on mutual information to guide their search process. However, even in simple binary classification problems, mutual information based methods do not always select the best set of features in terms of the Bayes error.
In this thesis, we develop a general approach for selecting a set of features that directly aims to minimize the Bayes error in the reduced feature space with respect to the loss or performance measure of interest. We show that the mutual information based criterion is a special case of our setting when the loss function of interest is the logarithmic loss for class probability estimation. We give a greedy forward algorithm for approximately optimizing this criterion and demonstrate its application to several supervised learning problems including binary classification (with 0-1 error, cost-sensitive error, and F-measure), binary class probability estimation (with logarithmic loss), bipartite ranking (with pairwise disagreement loss), and multiclass classification (with multiclass 0-1 error). Our experiments suggest that the proposed approach is competitive with several state-of-the art methods.2018-02-17T18:30:00Z