research-article

REF: resource elasticity fairness with sharing incentives for multiprocessors

Authors:

Seyed Majid Zahedi,

Benjamin C. LeeAuthors Info & Claims

ACM SIGPLAN Notices, Volume 49, Issue 4

Pages 145 - 160

https://doi.org/10.1145/2644865.2541962

Published: 24 February 2014 Publication History

Abstract

With the democratization of cloud and datacenter computing, users increasingly share large hardware platforms. In this setting, architects encounter two challenges: sharing fairly and sharing multiple resources. Drawing on economic game-theory, we rethink fairness in computer architecture. A fair allocation must provide sharing incentives (SI), envy-freeness (EF), and Pareto efficiency (PE).

We show that Cobb-Douglas utility functions are well suited to modeling user preferences for cache capacity and memory bandwidth. And we present an allocation mechanism that uses Cobb-Douglas preferences to determine each user's fair share of the hardware. This mechanism provably guarantees SI, EF, and PE, as well as strategy-proofness in the large (SPL). And it does so with modest performance penalties, less than 10\% throughput loss, relative to an unfair mechanism.

References

[1]

Luiz André Barroso and Urs Hölzle. The datacenter as a computer: An introduction to the design of warehouse-scale machines. Synthesis Lectures on Computer Architecture, 4(1):1--108, 2009.

[2]

Christian Bienia. Benchmarking Modern Multiprocessors. PhD thesis, Princeton University, January 2011.

Digital Library

[3]

Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh, and Kai Li. The parsec benchmark suite: Characterization and architectural implications. In Proc. International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 72--81, 2008.

Digital Library

[4]

Ramazan Bitirgen, Engin Ipek, and Jose F Martinez. Coordinated management of multiple interacting resources in chip multiprocessors: A machine learning approach. In Proc. International Symposium on Microarchitecture (MICRO), 2008.

Digital Library

[5]

Stephen Boyd, Seung-Jean Kim, Lieven Vandenberghe, and Arash Hassibi. A tutorial on geometric programming. Optimization and Engineering, 8(1):67--127, 2007.

[6]

Jeffrey S Chase, Darrell C Anderson, Prachi N Thakar, Amin M Vahdat, and Ronald P Doyle. Managing energy and server resources in hosting centers. In Proc. Symposium on Operating System Principles (SOSP), 2001.

Digital Library

[7]

Reetuparna Das, Onur Mutlu, Thomas Moscibroda, and Chita R Das. Application-aware prioritization mechanisms for on-chip networks. In Proc. International Symposium on Microarchitecture (MICRO), pages 280--291. IEEE, 2009.

Digital Library

[8]

Alan Demers, Srinivasan Keshav, and Scott Shenker. Analysis and simulation of a fair queueing algorithm. In ACM SIGCOMM Computer Communication Review, volume 19, pages 1--12. ACM, 1989.

Digital Library

[9]

Danny Dolev, Dror G Feitelson, Joseph Y Halpern, Raz Kupferman, and Nathan Linial. No justified complaints: On fair sharing of multiple resources. In Proc. Innovations in Theoretical Computer Science Conference, pages 68--75. ACM, 2012.

Digital Library

[10]

Eiman Ebrahimi, Chang Joo Lee, Onur Mutlu, and Yale N Patt. Fairness via source throttling: a configurable and high-performance fairness substrate for multi-core memory systems. In Proc. International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 335--346. ACM, 2010.

Digital Library

[11]

Francis Ysidro Edgeworth. Mathematical psychics: An essay on the application of mathematics to the moral sciences. Number 10. C. Kegan Paul & Company, 1881.

[12]

Stijn Eyerman and Lieven Eeckhout. System-level performance metrics for multiprogram workloads. Micro, IEEE, 28(3):42--53, 2008.

Digital Library

[13]

Ron Gabor, Shlomo Weiss, and Avi Mendelson. Fairness and throughput in switch on event multithreading. In Proc. International Symposium on Microarchitecture (MICRO), pages 149--160. IEEE, 2006.

Digital Library

[14]

Ron Gabor, Shlomo Weiss, and Avi Mendelson. Fairness enforcement in switch on event multithreading. ACM Transactions on Architecture and Code Optimization (TACO), 4(3):15, 2007.

Digital Library

[15]

Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: fair allocation of multiple resource types. In Proc. USENIX NSDI, 2011.

Digital Library

[16]

Michael Grant and Stephen Boyd. Cvx: Matlab software for disciplined convex programming, version 1.21, 2010.

[17]

Marisabel Guevara, Benjamin Lubin, and Benjamin C Lee. Navigating heterogeneous processors with market mechanisms. In Proc. International Symposium on High Performance Computer Architecture (HPCA), pages 95--106, 2013.

Digital Library

[18]

Avital Gutman and Noam Nisan. Fair allocation without trade. In Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 719--728, 2012.

Digital Library

[19]

Kazuhiko Hashimoto. Strategy-proofness versus efficiency on the cobb-douglas domain of exchange economies. Social choice and welfare, 31(3):457--473, 2008.

[20]

Mark D Hill and Michael R Marty. Amdahl's law in the multicore era. Computer, 41(7):33--38, 2008.

Digital Library

[21]

Carlee Joe-Wong, Soumya Sen, Tian Lan, and Mung Chiang. Multi-resource allocation: Fairness-efficiency tradeoffs in a unifying framework. In Proc. INFOCOM, pages 1206--1214. IEEE, 2012.

[22]

Yoongu Kim, Dongsu Han, Onur Mutlu, and Mor Harchol-Balter. Atlas: A scalable and high-performance scheduling algorithm for multiple memory controllers. In Proc. International Symposium on High Performance Computer Architecture (HPCA), pages 1--12. IEEE, 2010.

[23]

Benjamin Lee and David Brooks. Accurate and efficient regression modeling for microarchitectural performance and power prediction. In Proc. International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2006.

Digital Library

[24]

Benjamin Lubin, Jeffrey O Kephart, Rajarshi Das, and David C Parkes. Expressive power-based resource allocation for data centers. In Proc. International Joint Conferences on Artificial Intelligence (IJCAI), pages 1451--1456, 2009.

Digital Library

[25]

Jason Mars, Lingjia Tang, Robert Hundt, Kevin Skadron, and Mary Lou Soffa. Bubble-up: Increasing utilization in modern warehouse scale computers via sensible co-locations. In Proc. International Symposium on Microarchitecture (MICRO), pages 248--259. ACM, 2011.

Digital Library

[26]

Hervé Moulin. Fair division and collective welfare. MIT press, 2004.

[27]

Abhinay Muthoo. Bargaining theory with applications. Cambridge University Press, 1999.

Digital Library

[28]

Onur Mutlu and Thomas Moscibroda. Stall-time fair memory access scheduling for chip multiprocessors. In Proc. International Symposium on Microarchitecture (MICRO), pages 146--160. IEEE Computer Society, 2007.

Digital Library

[29]

Onur Mutlu and Thomas Moscibroda. Parallelism-aware batch scheduling: Enhancing both performance and fairness of shared dram systems. In Proc. International Symposium on Computer Architecture (ISCA), pages 63--74. IEEE Computer Society, 2008.

Digital Library

[30]

John F Nash Jr. The bargaining problem. Econometrica: Journal of the Econometric Society, pages 155--162, 1950.

[31]

Kyle J Nesbit, Nidhi Aggarwal, James Laudon, and James E Smith. Fair queuing memory systems. In Proc. International Symposium on Microarchitecture (MICRO), pages 208--222. IEEE, 2006.

Digital Library

[32]

David C Parkes, Ariel D Procaccia, and Nisarg Shah. Beyond dominant resource fairness: extensions, limitations, and indivisibilities. In Proc. Conference on Electronic Commerce (EC), pages 808--825. ACM, 2012.

Digital Library

[33]

Avadh Patel, Furat Afram, Shunfei Chen, and Kanad Ghose. MARSSx86: A Full System Simulator for x86 CPUs. In Design Automation Conference 2011 (DAC'11), 2011.

Digital Library

[34]

Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary Bradski, and Christos Kozyrakis. Evaluating MapReduce for multi-core and multiprocessor systems. In Proc. International Symposium on High Performance Computer Architecture (HPCA), pages 13--24. IEEE, 2007.

Digital Library

[35]

Paul Rosenfeld, Elliott Cooper-Balis, and Bruce Jacob. Dramsim2: A cycle accurate memory system simulator. Computer Architecture Letters, 10(1):16--19, 2011.

Digital Library

[36]

Alejandro Toriello and Juan Pablo Vielma. Fitting piecewise linear continuous functions. European Journal of Operational Research, 219(1):86--95, 2012.

[37]

Hal Varian. Equity, envy, and efficiency. Journal of economic theory, 9(1):63--91, 1974.

[38]

Carl A Waldspurger and William E Weihl. Lottery scheduling: Flexible proportional-share resource management. In Proc. USENIX Conference on Operating Systems Design and Implementation (OSDI), page 1. USENIX Association, 1994.

Digital Library

Cited By

Guo XWang HZhou KJiang HHan YXing G(2024)FLOWS: Balanced MRC Profiling for Heterogeneous Object-Size CacheProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650078(421-440)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650078
Tang SZhou ZGou JYu CLi YFu HSun CXiao J(2024)Fairness-Efficiency Scheduling for Pay-as-You-Go Shared Caching Systems With Long-Term Fairness GuaranteesIEEE Transactions on Services Computing10.1109/TSC.2023.333504817:5(2417-2431)Online publication date: Sep-2024
https://doi.org/10.1109/TSC.2023.3335048
Liu YDeng XZhou JChen MBao Y(2024)Suppressing the Interference Within a Datacenter: Theorems, Metric and StrategyIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.335441835:5(732-750)Online publication date: May-2024
https://doi.org/10.1109/TPDS.2024.3354418
Show More Cited By

Index Terms

REF: resource elasticity fairness with sharing incentives for multiprocessors
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Multiple instruction, multiple data
2. Hardware
  1. Integrated circuits
    1. Semiconductor memory

Recommendations

REF: resource elasticity fairness with sharing incentives for multiprocessors
ASPLOS '14: Proceedings of the 19th international conference on Architectural support for programming languages and operating systems

With the democratization of cloud and datacenter computing, users increasingly share large hardware platforms. In this setting, architects encounter two challenges: sharing fairly and sharing multiple resources. Drawing on economic game-theory, we ...
REF: resource elasticity fairness with sharing incentives for multiprocessors
ASPLOS '14

With the democratization of cloud and datacenter computing, users increasingly share large hardware platforms. In this setting, architects encounter two challenges: sharing fairly and sharing multiple resources. Drawing on economic game-theory, we ...
Vertically Differentiated Simultaneous Vickrey Auctions: Theory and Experimental Evidence

We study settings where a number of sellers simultaneously offer vertically differentiated Vickrey auctions for imperfect substitute goods to unit-demand buyers. Vertical differentiation can arise from differences in item quality, item value certainty, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 49, Issue 4

ASPLOS '14

April 2014

729 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2644865

Editors:
Mark W. Bailey
Hamilton College, Clinton, NY
,
Rajeev Balasubramonian
University of Utah
,
Al Davis
University of Utah
,
Sarita Adve
University of Illinois at Urbana-Champ

Issue’s Table of Contents

ASPLOS '14: Proceedings of the 19th international conference on Architectural support for programming languages and operating systems
February 2014
780 pages
ISBN:9781450323055
DOI:10.1145/2541940
General Chairs:
Rajeev Balasubramonian
University of Utah
,
Al Davis
University of Utah
,
Program Chair:
Sarita Adve
University of Illinois at Urbana-Champ

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 February 2014

Published in SIGPLAN Volume 49, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
669
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guo XWang HZhou KJiang HHan YXing G(2024)FLOWS: Balanced MRC Profiling for Heterogeneous Object-Size CacheProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650078(421-440)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650078
Tang SZhou ZGou JYu CLi YFu HSun CXiao J(2024)Fairness-Efficiency Scheduling for Pay-as-You-Go Shared Caching Systems With Long-Term Fairness GuaranteesIEEE Transactions on Services Computing10.1109/TSC.2023.333504817:5(2417-2431)Online publication date: Sep-2024
https://doi.org/10.1109/TSC.2023.3335048
Liu YDeng XZhou JChen MBao Y(2024)Suppressing the Interference Within a Datacenter: Theorems, Metric and StrategyIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.335441835:5(732-750)Online publication date: May-2024
https://doi.org/10.1109/TPDS.2024.3354418
Yang TChen RLi YLiu XWang G(2023)CoTuner: A Hierarchical Learning Framework for Coordinately Optimizing Resource Partitioning and Parameter TuningProceedings of the 52nd International Conference on Parallel Processing10.1145/3605573.3605578(317-326)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3605573.3605578
Acun BLee BKazhamiaka FMaeng KGupta UChakkaravarthy MBrooks DWu CAamodt TJerger NSwift M(2023)Carbon Explorer: A Holistic Framework for Designing Carbon Aware DatacentersProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575754(118-132)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575754
Meskar ELiang B(2023)Fair Multi-Resource Allocation in Heterogeneous Servers With an External Resource TypeIEEE/ACM Transactions on Networking10.1109/TNET.2022.321342631:3(1244-1262)Online publication date: Jun-2023
https://doi.org/10.1109/TNET.2022.3213426
Zhao L(2023)A Two-Level Multi-task Fair Allocation Mechanism in Cloud Computing2023 8th International Conference on Computer and Communication Systems (ICCCS)10.1109/ICCCS57501.2023.10150636(1158-1162)Online publication date: 21-Apr-2023
https://doi.org/10.1109/ICCCS57501.2023.10150636
Li RTang YShi QMao HChen LJin JLu PCheng ZBolchini CO'Connor IVerbauwhede IWille R(2022)Accurate probabilistic miss ratio curve approximation for adaptive cache allocation in block storage systemsProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3540131(1197-1202)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3540131
Li RTang YShi QMao HChen LJin JLu PCheng Z(2022)Accurate Probabilistic Miss Ratio Curve Approximation for Adaptive Cache Allocation in Block Storage Systems2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE54114.2022.9774516(1197-1202)Online publication date: 14-Mar-2022
https://doi.org/10.23919/DATE54114.2022.9774516
Choi WUrgaonkar BKandemir MKesidis GBellavista PZhang KGherbi ABagchi SPatiño MDi Modica GGascon-Samson J(2022)Multi-resource fair allocation for consolidated flash-based caching systemsProceedings of the 23rd ACM/IFIP International Middleware Conference10.1145/3528535.3565245(202-215)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3528535.3565245
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents