Back to search

Cornell University

SCALABLE DYNAMIC MULTI-RESOURCE ALLOCATION IN MULTICORE SYSTEMS

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Electrical and Computer Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor
Cornell University
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Xiaodong
Chair dc:contributor.chair
  • Martinez, Jose F.
Committee members dc:contributor.committeemember
  • Sirer, Emin G.
  • Albonesi, David H.

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
9905981
Dc Identifier Other
ProQuest Submission ID: 10114
ProQuest Publication ID: 10253243

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wang, Xiaodong. SCALABLE DYNAMIC MULTI-RESOURCE ALLOCATION IN MULTICORE SYSTEMS. Doctor of Philosophy thesis, Cornell University, 2017. https://hdl.handle.net/1813/47735