Abstract

The compiler optimizations we enable and the order in which we apply them on a program have a substantial impact on the program execution time. Compilers provide default optimization sequences which can give good program speedup. As the default sequences have to optimize programs with different characteristics, they embed in them multiple subsequences which can optimize different classes of programs. These multiple subsequences may falsely interact with each other and affect the potential program speedup achievable. Instead of searching for a single universally optimal sequence, we can construct a small set of good sequences such that for every program class there exists a near-optimal optimization sequence in the good sequences set. If we can construct such a good sequences set which covers all the program classes in the program space, then we can choose the best sequence for a program by trying all the sequences in the good sequences set. This approach completely circumvents the need to solve the program classification problem. Using a sequence set size of around 10 we got an average speedup up to 14% on PolyBench programs and up to 12% on MiBench programs. Our approach is quite different from either the iterative compilation or machine-learning-based prediction modeling techniques proposed in the literature so far. We use different training and test datasets for cross-validation as against the Leave-One-Out cross-validation technique.

Abstract

When multiple virtual machines (VMs) are co scheduled on the same physical machine, they may undergo a performance degradation. The performance degradation is due to the contention for shared resources like last level cache, hard disk, network bandwidth etc. This can lead to service-level agreement violations and thereby customer dissatisfaction. The classical approach to solve the co scheduling problem involves a central authority which decides a co schedule by solving a constrained optimization problem with an objective function such as average performance degradation. In this paper, we use the theory of stable matchings to provide an alternate game theoretic perspective to the co scheduling problem wherein each VM selfishly tries to minimize its performance degradation. We show that the co scheduling problem can be formulated as a Stable Roommates Problem (SRP). Since certain instances of the SRP do not have any stable matching, we reduce the problem to the Stable Marriages Problem (SMP) via an initial approximation. Gale and Shapley proved that any instance of the SMP has a stable matching and can be found in quadratic time. From a game theoretic perspective, the SMP can be thought of as a matching game which always has a Nash equilibrium. There are distributed algorithms for both the SRP and SMP problems. A VM agent in a distributed algorithm need not reveal its preference list to any other VM. This allows each VM to have a private cost function. A principal advantage of this problem formulation is that it opens up the possibility of applying the rich theory of matching markets from game theory to address various aspects of the VM co scheduling problem such as stability, coalitions and privacy both from a theoretical and practical standpoint. We also propose a new workload characterization technique for a combination of compute and memory intensive workloads. The proposed technique uses a sentinel program and it requires only two runs per workload for characterization. VMs can use this technique in deciding their partner preference ranks in the SRP and SMP problems. The characterization technique has also been used in proposing two new centralized VM co scheduling algorithms whose performance is close to the optimal Blossom algorithm.

Abstract

In this work the authors propose a data coding protocol that leads to power reduction for block data transfer in off-chip buses. I/O pads driving off-chip buses contribute to a major portion of power dissipation in chips. Also, block data transfer is preferred in most systems like caches, DMA etc. In this proposed work, the prior knowledge of the block of data to be transmitted, when it is stored in the buffer, is exploited in a serial fashion to reduce transitions on every bus line. Statistical analysis shows up to 31.9% reduction in transitions. Benchmark results show that it leads to 29% reduction in power consumption. The technique provides added error detection on the lines of parity bit technique, with similar average error detection capability.

Abstract

In this work, the authors present the idea of inexact decision making, and its application to threshold voting of Hamming weights, used in bus coding schemes, N-modular redundancy (NMR), median filtering, and other pattern matching applications. Decision circuits can be tweaked, to perform in an inexact manner, in order to optimize in terms of delay and power, but still maintaining high system accuracy. One such circuit identified by the authors is the threshold voting of Hamming weights. A majority voter is a special case of this family of circuits. The proposed inexact voter consumes up to 8 times less power than the exact voter, with negligible reduction in system accuracy and performance. The leakage power is also reduced by a factor of 3. The inexact voter allows for a higher frequency of operation, by reducing the critical path delay by a factor of up to 3.4. The results obtained validate the application of inexact decision making, with respect to threshold voters.