Designing chip multiprocessors (CMPs) that scale to more than a handful of cores is an important goal for the upcoming technology generations. A challenge to scalability is the fact that these cores will inevitably share hardware resources, whether it be on-chip storage, memory bandwidth, the chip’s power budget, etc. Efficiently allocating those shared resources across cores is critical to optimize CMP executions. Techniques proposed in the literature often rely on global, centralized mechanisms that seek to maximize system throughput. Global optimization may hurt scalability: as more cores are integrated on a die, the search space grows exponentially, making it harder to achieve optimal or even acceptable operating points at run-time without incurring significant overheads.In this thesis, we present XChange, a framework for scalable resource allocation in large-scale CMPs. Inspired by market mechanisms, which are widely used in real life to allocate social resources at scale, we propose to address the resource allocation problem in large-scale CMPs as a purely dynamic, largely distributed market framework. Each shared resource is assigned a virtual price, which changes over time to reflect its supply-demand relationship. Cores in the CMP act as market players: they seek to maximize their own utilities by bidding for shared resources within their budgets. Because each core works largely independently, the resource allocation becomes a scalable, mostly distributed decision-making process. Cores in the system are able to dynamically monitor and learn their own resource-performance relationship and bid accordingly—no prior knowledge of the workload characteristics is assumed.We show our market-based resource allocation mechanism delivers superior system efficiency and fairness against existing proposals. This approach is purely empirical, however, and thus it does not provide any guarantees on the loss of efficiency and fairness. It is well known, for example, that market mechanisms in equilibrium can sometimes be highly inefficient—this is known as Tragedy of Commons. Therefore, we study the theoretic properties of our market-based approach, and establish a bound on the loss of efficiency and fairness in the market-based resource allocation, by introducing two new metrics, market utility range (MUR) and market budget range (MBR). Further, guided by such theoretic foundations, we propose ReBudget, a budget re-assignment technique that is able to systematically trade off efficiency and fairness in an adjustable manner.In the process of formulating our XChange framework, we propose novel mechanisms to support fine-grain resource management. Specifically, we propose SWAP, a scalable and fine-grain cache management technique that seamlessly combines set and way partitioning. By cooperatively managing cache ways and sets, SWAP (“Set and WAy Partitioning”) can successfully provide hundreds of fine-grained cache partitions for the manycore era. We implement SWAP as a user-space management thread on Cavium’s ThunderX, a real server-grade 48-core processor, and we show that SWAP significantly improves system throughput by twice as much speedup as what we can obtain by using only ThunderX’s way partitioning mechanism. This was a collaboration with Cavium engineers.
展开▼
