SHF: Small: Coalitional Game Theory for Co-Locating Software on Shared Hardware

Duke University, Durham NC

Investigators

Abstract

As computing capability grows and computation becomes increasingly task parallel, many small tasks will co-locate on a few big machines. No single computational task can utilize a machine's resources completely, yet all of these resources become available when a machine is powered up. This mismatch leads to the well-known problem of energy disproportionality, when a server is under-utilized and its fixed power costs are amortized over little work. Managing task co-location to ensure performance, to improve power efficiency, and to incentivize desired behavior from strategic users requires new perspectives. Computing resources increasingly fall into economists? definition of a commons. A commons is a technology used jointly by a set of agents and the problem of the commons is to organize the joint exploitation of this technology. By mapping shared hardware architectures into this problem formulation, the investigators adapt systems management mechanisms to accommodate strategic user behavior. This microeconomic perspective leads to incentives that encourage users to adopt cloud computing for greater performance and efficiency. The investigators are committed to integrating research and education. Successes include strong teaching evaluations for classes in energy-efficient computing and classes that rapidly prepare Masters students with weaker backgrounds in computing fundamentals. Successes also include fostering research participation from undergraduates and under-represented minorities. The investigators study game-theoretic mechanisms for co-locating tasks and mitigating contention between strategic users who share high-performance hardware architectures. First, these mechanisms estimate performance by inferring statistical models for contention penalties that arise from users? behavior combinations. Then, these mechanisms attribute penalties to tasks by using coalitional game theory to determine the extent that each task contributes to system contention. Finally, these mechanisms optimize software co-location for strategic users and ensure game-theoretic desiderata, such as sharing incentives and fairness. The project is interdisciplinary, linking previously disparate studies in computer architecture, resource management, and algorithmic economics. The research draws on rigorous, analytical frameworks to reason about users' interactions within shared systems and their contributions to overall system outcomes. Moreover, the research translates rigor into operational mechanisms for systems management and task co-location.