Optimal Task Assignment in Multithreaded Processors: A Statistical Approach

TitleOptimal Task Assignment in Multithreaded Processors: A Statistical Approach
Publication TypeConference Paper
Year of Publication2012
AuthorsRadojković, P., Cakarevic V., Moretó M., Verdú J., Pajuelo A., Cazorla F. J., Nemirovsky M., & Valero M.
Other Numbers3259

The introduction of massively multithreaded (MMT) processors,comprised of a large number of cores with many shared resources,has made task scheduling, in particular task to hardware threadassignment, one of the most promising ways to improve systemperformance. However, finding an optimal task assignment for aworkload running on MMT processors is an NP-complete problem.Due to the fact that the performance of the best possible taskassignment is unknown, the room for improvement of current taskassignmentalgorithms cannot be determined. This is a major problemfor the industry because it could lead to: (1) A waste of resourcesif excessive effort is devoted to improving a task assignmentalgorithm that already provides a performance that is close tothe optimal one, or (2) significant performance loss if insufficienteffort is devoted to improving poorly-performing task assignmentalgorithms.In this paper, we present a method based on Extreme Value Theorythat allows the prediction of the performance of the optimaltask assignment in MMT processors. We further show that executinga sample of several hundred or several thousand random taskassignments is enough to obtain, with very high confidence, an assignmentwith a performance that is close to the optimal one. Wevalidate our method with an industrial case study for a set of multithreadednetwork applications running on an UltraSPARC T2 processor.


This work was partially supported by funding provided to ICSI by the Department of Universities, Research and Information Society (DURSI) of the Catalan Government (grant 2010-BE-00352).

Bibliographic Notes

Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVII), pp. 235-248, London, United Kingdom.

Abbreviated Authors

P. Radojkovic, V. Cakarevic, M. Moretó, J. Verdu, A. Pajuelo, F. J. Cazorla, M. Nemirovsky, and M. Valero

ICSI Research Group


ICSI Publication Type

Article in conference proceedings