Game-Theoretic Analysis of Decentralized Core Allocation Schemes on Many-core Systems

Wildermann S, Ziermann T, Teich J (2013)

Publication Type: Conference contribution

Publication year: 2013

Publisher: IEEE Press

Edited Volumes: Proceedings -Design, Automation and Test in Europe, DATE

City/Town: New York, NY, USA

Pages Range: 1498-1503

Conference Proceedings Title: Proc. Design, Automation and Test in Europe

Event location: Grenoble FR

ISBN: 978-1-4503-2153-2

DOI: 10.7873/DATE.2013.305

Abstract

Many-core architectures used in embedded systems will contain hundreds of processors in the near future. Already now, it is necessary to study how to manage such systems when dynamically scheduling applications with different phases of parallelism and resource demands. A recent research area called invasive computing proposes a decentralized workload management scheme of such systems: applications may dynamically claim additional processors during execution and release these again, respectively. In this paper, we study how to apply the concepts of invasive computing for realizing decentralized core allocation schemes in homogeneous many-core systems with the goal of maximizing the average speedup of running applications at any point in time. A theoretical analysis based on game theory shows that it is possible to define a core allocation scheme that uses local information exchange between applications only, but is still able to provably converge to optimal results. The experimental evaluation demonstrates that this allocation scheme reduces the overhead in terms of exchanged messages by up to 61.4% and even the convergence time by up to 13.4% compared to an allocation scheme where all applications exchange information globally with each other. © 2013 EDAA.

Authors with CRIS profile

Stefan Wildermann Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design) Tobias Ziermann Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design) Jürgen Teich Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)

How to cite

APA:

Wildermann, S., Ziermann, T., & Teich, J. (2013). Game-Theoretic Analysis of Decentralized Core Allocation Schemes on Many-core Systems. In Proc. Design, Automation and Test in Europe (pp. 1498-1503). Grenoble, FR: New York, NY, USA: IEEE Press.

MLA:

Wildermann, Stefan, Tobias Ziermann, and Jürgen Teich. "Game-Theoretic Analysis of Decentralized Core Allocation Schemes on Many-core Systems." Proceedings of the Design, Automation and Test in Europe (DATE), Grenoble New York, NY, USA: IEEE Press, 2013. 1498-1503.

BibTeX: Download