OPTIMIZATION AND MATHEMATICAL MODELING IN COMPUTER ARCHITECTURE

In the last few decades computer systems and the underlying hardware have steadily become larger and more complex. The need to increase their efficiency through architectural innovation has not abated, but quantitatively evaluating the effect of various choices has become more difficult. Performance and resource consumption are determined by complex interactions between many modules, each with many possible alternative implementations. We need powerful computer programs to explore large design spaces, but the traditional approach of developing simulators, building prototypes, or writing heuristic-based algorithms in traditional programming languages is often tedious and slow. Fortunately mathematical optimization has made great advances in theory, and many fast commercial and academic solvers are now available. In this book we motivate and describe the use of mathematical modeling, specifically optimization based on mixed integer linear programming (MILP) as a way to design and evaluate computer systems. The major advantage is that the architect or system software writer only needs to describe what the problem is, not how to find a good solution. This greatly speeds up their work and, as our case studies show, it can often lead to better solutions than the traditional approach. In this book we give an overview of modeling techniques used to describe computer systems to mathematical optimization tools. We give a brief introduction to various classes of mathematical optimization frameworks with special focus on mixed integer linear programming which provides a good balance between solver time and expressiveness. We present four detailed case studies -- instruction set customization, data center resource management, spatial architecture scheduling, and resource allocation in tiled architectures -- showing how MILP can be used and quantifying by how much it outperforms traditional design exploration techniques. This book should help a skilled systems designer to learn