Thread Migration Optimization for Chip Multiprocessors

Abstract

Chapter 1 is an introduction to this research. This chapter provides an overview about the problem of thread assignment under performance constraints, the hardware systems considered in the scope of this research and the potential applications of our proposed method. Chapter 2 provides the necessary background and explores recently-proposed related research work. Three main approaches for dealing with systems with power or per- formance constraints are discussed. Some studies propose algorithms to address the thread scheduling problem on heterogeneous multi-core systems. Others address power constraints using DVFS. Finally, several research studies propose recon gurable archi- tectures to deal with program variations and constraints. We discuss recent proposals for these three approaches and highlight the use cases for each one as well as the systems most suitable for utilizing these methods. Chapter 3 describes the proposed thread mapping framework. The formulation of the thread mapping problem, the system model used in this work and the proposed heuristic solution are shown. Furthermore, this chapter describes the means of applying our solution to systems with heterogeneous cores and systems with homogeneous cores with DVFS capabilities. Applying the proposed solution to two di erent schemes of DVFS algorithms for homogeneous chips and the bene ts of each is also detailed in this chapter. Chapter 4 shows the implementation details of the proposed framework. The prediction method utilized for estimation of power and performance values is presented, together with the associated prediction error percentage. Moreover, the data structures used in the implementation of the algorithm, to ensure that it can be brought online for hundred-core systems with minimal overhead, are described.