Communications of the ACM

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.

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.