0.0 0.2 0.4 0.6 0.8 1.0
0
.0
0
.
4
0
. 8
Pr
E
ffi
c
ien
c
y
o
f
e
qu
il
ib
r
ium
Figure 9. Efficiency of equilibrium thresholds.
performance lost exceeds performance gained. In our example, punishments would allow the system to escape inefficient
equilibria as agents are compelled to increase their thresholds
and ensure Ptrip remains zero. The coordinator could monitor
sprints, detect deviations from assigned strategies, and forbid
agents who deviate from ever sprinting again. Note that threat
of punishment is sufficient to shape the equilibrium.
7. CONCLUSION
Economics and game theory have proven effective in data-center power and resource management. Game-theoretic
notions of fairness can incentivize strategic users when sharing hardware.
6, 12, 19, 20 Markets and price theory can allocate and
manage heterogeneous servers.
8, 9, 17 Demand response models can handle power emergencies.
3, 11
We link system architecture and algorithmic economics
to decentralize the allocation of shared resources to strategic users. The computational sprinting game is a management architecture that governs how independent chip
multiprocessors share a power supply. The approach generalizes beyond datacenters and is relevant to systems that are
distributed, heterogeneous, and dynamic. The game’s
approach to sprinting applies to any mechanism that briey
accelerates performance using additional resources be they
processor, memory, network, or power. The game’s equilibrium highlights a path to scalable management because
mean field analysis provides tractability when the number
of system components is large. However, finding the equilibrium requires statistical distributions of agent behaviors
and further research is needed to reduce offline profiling
costs and accelerate online utility prediction.
Acknowledgments
This work is supported by National Science Foundation grants
CCF-1149252, CCF-1337215, SHF-1527610, and AF-1408784.
This work is also supported by STARnet, a SRC program,
sponsored by MARCO and DARPA.
© 2019 ACM 0001-0782/19/2 $15.00
References
1. Adlakha, S., Johari, R. Mean
field equilibrium in dynamic
games with strategic
complementarities. Oper. Res. 61, 4
(2013), 971–989.
2. Brooks, D. Martonosi, M. Dynamic
thermal management for
high-performance microprocessors.
In Proceedings of the 7th IEEE
International Symposium on High
Performance Computer Architecture
(HPCA) (Monterrey, Nuevo Leon,
Mexico, 2001), 171–182.
Songchun Fan† (songchun.fan@duke.
edu), Duke University, California, USA.
Seyed Majid Zahedi† and Benjamin C. Lee
({ seyedmajid.zahedi, benjamin.c.lee}@duke.
edu), Duke University, Durham, NC, USA.
3. Chase, J.S., Anderson, D.C., Thakar, P.N.,
Vahdat, A.M., Doyle, R.P. Managing
energy and server resources in
hosting centers. In Proceedings of the
18th Symposium on Operating
Systems Principles (SOSP) (Banff,
Alberta, Canada, 2001), 103–116.
4. Fan, X., Weber, W.-D., Barroso, L. A.
Power provisioning for a warehouse-sized computer. In Proceedings of the
34th Annual International
Symposium on Computer
Architecture (ISCA) (San Diego, CA,
USA, 2007), 13–23.
5. Fu, X., Wang, X., Lefurgy, C. How much
power oversubscription is safe and
allowed in data centers. In Proceedings
of the 8th ACM International
Conference on Autonomic Computing
(ICAC) (Karlsruhe, Germany, 2011),
21–30.
6. Ghodsi, A., Zaharia, M., Hindman, B.,
Konwinski, A., Shenker, S., Stoica, I.
Dominant resource fairness: Fair
allocation of multiple resource types.
In Proceedings of the 8th USENIX
Conference on Net worked Systems
Design and Implementation (NSDI)
(Boston, MA, USA, 2011), 323–336.
7. Govindan, S., Sivasubramaniam, A.,
Urgaonkar, B. Benefits and limitations
of tapping into stored energy for
datacenters. In Proceeding of the
38th Annual International
Symposium on Computer
Architecture (ISCA) (San Jose, CA,
USA, 2011), 341–351.
8. Guevara, M., Lubin, B., Lee, B. C..
Navigating heterogeneous processors
with market mechanisms. In
Proceeding of the 19th IEEE
International Symposium on High
Performance Computer Architecture
(HPCA) (Shenzhen, China, 2013),
95–106.
9. Guevara, M., Lubin, B., Lee, B. C.
Strategies for anticipating risk in
heterogeneous system design. In
Proceeding of the 20th IEEE
International Symposium on High
Performance Computer Architecture
(HPCA) (Orlando, FL, USA, 2014),
154–164.
10. Hindman, B., Konwinski, A.,
Zaharia, M., Ghodsi, A., Joseph, A.D.,
Katz, R., Shenker, S., Stoica, I. Mesos:
A platform for fine-grained resource
sharing in the data center. In
Proceedings of the 8th USENIX
Conference on Net worked Systems
Design and Implementation (NSDI)
(Boston, MA, USA, 2011), 295–308.
11. Liu, Z., Wierman, A., Chen, Y., Razon,
B., Chen, N. Data center demand
response: Avoiding the coincident
peak via workload shifting and local
generation. Perform. Eval. 70, 10
(2013), 770–791.
12. Llull, Q., Fan, S., Zahedi, S.M.,
Lee, B.C. Cooper: Task colocation with
cooperative games. In Proceedings of
the 23rd IEEE International
Symposium on High-Performance
Computer Architecture (HPCA)
(Austin, TX, USA, 2017), 421–432.
13. Raghavan, A., Emurian, L., Shao, L.,
Papaefthymiou, M., Pipe, K.P.,
Wenisch, T.F., Martin, M. M.
Computational sprinting on a
hardware/software testbed. In
Proceedings of the 18th International
Conference on Architectural Support
for Programming Languages and
Operating Systems (ASPLOS)
(Houston, TX, USA, 2013), 155–166.
14. Raghavan, A., Luo, Y., Chandawalla, A.,
Papaefthymiou, M., Pipe, K.P.,
Wenisch, T.F., Martin, M. M. K.
Computational sprinting. In
Proceedings of the 18th IEEE
International Symposium on High
Performance Computer Architecture
(HPCA) (New Orleans, LA, USA,
2012), 1–12.
15. Shao, L., Raghavan, A., Emurian, L.,
Papaefthymiou, M.C., Wenisch, T. F.,
Martin, M.M., Pipe, K.P. On-chip phase
change heat sinks designed for
computational sprinting. In
Proceedings of the 30th Annual
Semiconductor Thermal
Measurement and Management
Symposium (San Jose, CA, USA,
2014), 29–34.
16. Skach, M., Arora, M., Hsu, C.-H., Li, Q.,
Tullsen, D., Tang, L., Mars, J.
Thermal time shifting: Leveraging
phase change materials to reduce
cooling costs in warehouse-scale
computers. In Proceedings of the
42nd Annual International
Symposium on Computer
Architecture (ISCA) (Portland, OR,
USA, 2015), 439–449.
17. Somu Muthukaruppan, T., Pathania, A.,
Mitra, T. Price theory based power
management for heterogeneous
multi-cores. In Proceedings of the
19th International Conference on
Architectural Support for Programming
Languages and Operating Systems
(ASPLOS) (Salt Lake City, UT, USA,
2014), 161–176.
18. Wang, X., Chen, M., Lefurgy, C., Keller, T. W.
Ship: A scalable hierarchical power
control architecture for large-scale
data centers. IEEE Trans. Parallel
Distrib. Syst. 23, 1 (2012), 168–176.
19. Zahedi, S. M., Lee, B. C. Sharing
incentives and fair division for
multiprocessors. IEEE Micro 35, 3
(2015), 92–100.
20. Zahedi, S.M., Llull, Q., Lee, B.C.
Amdahl’s Law in the datacenter
era: A market for fair processor
allocation. In Proceedings of the 24rd
IEEE International Symposium on
High-Performance Computer
Architecture (HPCA) (Vienna,
Austria, 2018).
21. Zheng, W., Wang, X. Data center
sprinting: Enabling computational
sprinting at the data center level. In
Proceedings of the 35th International
Conference on Distributed Computing
Systems (ICDCS) (Columbus, OH,
USA, 2015), 175–184.