This thesis introduces performance and power optimization techniques for caches. Our optimization techniques target both conventional caches, which are implemented using six-transistor (6T) cells, and highly reliable caches implemented using eight-transistor (8T) cells. In 6T cell caches, we enhance leakage power dissipation by adapting a previous proposed technique, Drowsy Cache, according to the application behavior. We show that spatial locality in embedded applications is low and Drowsy Cache misses a significant leakage power saving opportunities. By taking a finer granularity approach, we achieve a significant leakage power reduction with minimal performance overhead. Although 6T cell caches are commonly used, we show that they are not proper choice for future designs due to poor stability. We investigate 8T cells as alternative reliable designs for implementing caches. However, Column Selection Issue limits efficiency of 8T cells during write operations. Previous solution, Read-Modify-Write (RMW), addressed column selection issue by requiring a read operation before each write operation, imposing significant overhead on performance, cache traffic, and power. We observe that a significant share of cache accesses in RMW is either redundant or unnecessary, consequently can be avoided without compromising program execution consistency. Based on our observations, we propose two techniques which exploit a buffering mechanism to detect and filter out unnecessary and redundant cache accesses. Our simulation results show that our techniques improve performance and cache traffic effectively in 8T cell caches. Furthermore, we propose a novel dual threshold 8T cell which reduces leakage power significantly with negligible impact on performance. Our proposed cell also improves stability and robustness to process variations compared to the conventional 8T cells. / Graduate / 0544 / farahani.mostafa@gmail.com

Graph partitioning is a fundamental optimization problem that has been intensively studied. Many graph partitioning formulations are important as building blocks for divide-and-conquer algorithms on graphs as well as to many applications such as VLSI layout, packet routing in distributed networks, clustering and image segmentation. Unfortunately such problems are notorious for the huge gap between known best known approximation algorithms and hardness of approximation results. In this thesis, we study approximation algorithms for graph partitioning problems using a strong hierarchy of relaxations based on semi-definite programming, called Lasserre Hierachy. Our main contribution in this thesis is a propagation based rounding framework for solutions arising from such relaxations. We present a novel connection between the quality of solutions it outputs and column based matrix reconstruction problem. As part of our work, we derive optimal bounds on the number of columns necessary together with efficient randomized and deterministic algorithms to find such columns. Using this framework, we derive approximation schemes for many graph partitioning problems with running times dependent on how fast the graph spectrum grows. Our final contribution is a fast SDP solver for this rounding framework: Even though SDP relaxation has nO(r) many variables, we achieve running times of the form 2O(r) poly(n) by only partially solving the relevant part of relaxation. In order to achieve this, we present a new ellipsoid algorithm that returns certificate of infeasibility.