research-article

Optimal task assignment in multithreaded processors: a statistical approach

Authors:

Petar Radojković,

Vladimir Čakarević,

Miquel Moretó,

Francisco J. Cazorla,

Mario Nemirovsky,

Mateo ValeroAuthors Info & Claims

ACM SIGPLAN Notices, Volume 47, Issue 4

Pages 235 - 248

https://doi.org/10.1145/2248487.2151002

Published: 03 March 2012 Publication History

Abstract

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 thread assignment, one of the most promising ways to improve system performance. However, finding an optimal task assignment for a workload running on MMT processors is an NP-complete problem. Due to the fact that the performance of the best possible task assignment is unknown, the room for improvement of current task-assignment algorithms cannot be determined. This is a major problem for the industry because it could lead to: (1)~A waste of resources if excessive effort is devoted to improving a task assignment algorithm that already provides a performance that is close to the optimal one, or (2)~significant performance loss if insufficient effort is devoted to improving poorly-performing task assignment algorithms.

In this paper, we present a method based on Extreme Value Theory that allows the prediction of the performance of the optimal task assignment in MMT processors. We further show that executing a sample of several hundred or several thousand random task assignments is enough to obtain, with very high confidence, an assignment with a performance that is close to the optimal one. We validate our method with an industrial case study for a set of multithreaded network applications running on an UltraSPARC~T2 processor.

References

[1]

OpenSPARC™ T2 Core Microarchitecture Specification. Sun Microsystems, Inc, 2007.

[2]

OpenSPARC™ T2 System-On-Chip (SOC) Microarchitecture Specification. Sun Microsystems, Inc, 2007.

[3]

Netra Data Plane Software Suite 2.0 Update 2 Reference Manual. Sun Microsystems, Inc, 2008.

[4]

Netra Data Plane Software Suite 2.0 Update 2 User's Guide. Sun Microsystems, Inc, 2008.

[5]

Software. Hardware. Complete. http://www.oracle.com/ocom/groups/public/@ocom/documents /webcontent/044518.pdf, 2010.

[6]

C. Acosta, F. Cazorla, A. Ramirez, and M. Valero. Thread to Core Assignment in SMT On-Chip Multiprocessors. In SBAC-PAD '09: Proceedings of the 21st International Symposium on Computer Architecture and High Performance Computing, 2009.

Digital Library

[7]

A. V. Aho and M. J. Corasick. Efficient String Matching: An Aid to Bibliographic Search. Commun. ACM, 18, 1975.

Digital Library

[8]

A. Azzalini. Statistical Inference Based on the Likelihood. Chapman and Hall, London, 1996.

[9]

A. A. Balkema and L. de Haan. Residual life time at great age. Annals of Probability, 2: 792--804, 1974.

[10]

J. Beirlant, Y. Goegebeur, J. Segers, and J. Teugels. Statistics of Extremes: Theory and Applications. John Wiley and Sons, Ltd, 2004.

[11]

E. Castillo. Extreme value theory in engineering. Academic Press, Inc., 1988.

[12]

E. Castillo and A. Hadi. Fitting the Generalized Pareto Distribution to data. Journal of the American Statistical Association, 92, 1997.

[13]

S. Kim, and Y. Solihin}contention_predictD. Chandra, F. Guo, S. Kim, and Y. Solihin. Predicting inter-thread cache contention on a chip multi-processor architecture. In HPCA '05: Proceedings of the 11th International Symposium on High-Performance Computer Architecture, 2005.

Digital Library

[14]

S. J. Chapman. Essentials of MATLAB Programming. Cengage Learning, 2009.

[15]

H. Chernoff. On the distribution of the likelihood ratio. Annals of Mathematical Statistics, 25, 1954.

[16]

W. G. Cochran. Sampling techniques. Wiley, 1977.

[17]

K. J. Connolly. Law of Internet Security and Privacy. Aspen Publishers, 2003.

Digital Library

[18]

M. De Vuyst, R. Kumar, and D. Tullsen. Exploiting unbalanced thread scheduling for energy and performance on a CMP of SMT processors. In IPDPS '06: Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium, 2006.

Digital Library

[19]

D. Eckhoff, T. Limmer, and F. Dressler. Hash Tables for Efficient Flow Monitoring: Vulnerabilities and Countermeasures. In LCN '09: Proceedings of the 34th Conference on Local Computer Networks, 2009.

[20]

A. El-Moursy, R. Garg, D. Albonesi, and S. Dwarkadas. Compatible phase co-scheduling on a CMP of multi-threaded processors. In IPDPS '06: Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium, 2006.

Digital Library

[21]

S. Eyerman and L. Eeckhout. Per-thread cycle accounting in SMT processors. In ASPLOS '09: Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, 2009.

Digital Library

[22]

S. Eyerman and L. Eeckhout. Probabilistic job symbiosis modeling for SMT processor scheduling. In ASPLOS '10: Proceeding of the 15th international conference on Architectural support for programming languages and operating systems, 2010.

Digital Library

[23]

A. Fedorova, M. Seltzer, C. Small, and D. Nussbaum. Performance of multithreaded chip multiprocessors and implications for operating system design. In ATEC '05: Proceedings of the annual conference on USENIX Annual Technical Conference, 2005.

Digital Library

[24]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.

Digital Library

[25]

M. Gilli and E. Kellezi. An application of extreme value theory for measuring financial risk. Computational Economics, 27, 2006.

Digital Library

[26]

R. Gioiosa, F. Petrini, K. Davis, and F. Lebaillif-Delamare. Analysis of system overhead on parallel computers. In ISSPIT '04: 4th IEEE International Symposium on Signal Processing and Information Technology, Rome, Italy, 2004.

[27]

M. Greenwood. The natural duration of cancer. Reports on Public Health and Medical Subjects, 33: 1--26, 1926.

[28]

S. Grimshaw. Computing the maximum likelihood estimates for the Generalized Pareto Distribution to data. Technometrics, 35, 1993.

[29]

F. Guo and T. Chiueh. Traffic Analysis: From Stateful Firewall to Network Intrusion Detection System. In RPE Report, 2004.

[30]

J. R. M. Hosking and J. R. Wallis. Parameter and quantile estimation for the generalised pareto distribution. Technometrics, 29, 1987.

Digital Library

[31]

Internet Engineering Task Force (IETF). Request for Comments (RFC), http://www.rfc-editor.org/.

[32]

R. Jain, C. J. Hughes, and S. V. Adve. Soft real-time scheduling on simultaneous multithreaded processors. In RTSS '02: Proceedings of the 23rd IEEE Real-Time Systems Symposium, 2002.

Digital Library

[33]

Y. Jiang, X. Shen, J. Chen, and R. Tripathi. Analysis and approximation of optimal co-scheduling on chip multiprocessors. In PACT '08: Proceedings of the 17th international conference on Parallel architectures and compilation techniques, 2008.

Digital Library

[34]

E. L. Kaplan and P. Meier. Nonparametric estimation from incomplete observations. Journal of the American Statistical Association, 52 (282): 457--481, 1958.

[35]

E. Kellezi and M. Gilli. Extreme value theory for tail-related risk measures. Fame research paper series, International Center for Financial Asset Management and Engineering, 2000.

[36]

J. Kihm, A. Settle, A. Janiszewski, and D. A. Connors. Understanding the impact of inter-thread cache interference on ILP in modern SMT processors. The Journal of Instruction Level Parallelism, 7, 2005.

[37]

Kunze, Mudigonda, Jason, and Vin}Kokku04CaseR. Kokku, T. L. Riché, A. Kunze, J. Mudigonda, J. Jason, and H. M. Vin. A case for run-time adaptation in packet processing systems. SIGCOMM Comput. Commun. Rev., 34 (1), 2004.

Digital Library

[38]

R. Kumar, D. M. Tullsen, P. Ranganathan, N. P. Jouppi, and K. I. Farkas. Single-ISA heterogenous multi-core architectures for multithreaded workload performance. In ISCA '04: Proceedings of the 31st Annual International Symposium on Computer Architecture, 2004.

Digital Library

[39]

R. L. McGregor, C. D. Antonopoulos, and D. S. Nikolopoulos. Scheduling algorithms for effective thread pairing on hybrid multiprocessors. In IPDPS '05: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, 2005.

Digital Library

[40]

M. Norton. Optimizing Pattern Matching for Intrusion Detection, http://docs.idsresearch.org/OptimizingPatternMatchingForIDS.pdf, 2004.

[41]

Probe network monitor. http://www.ntop.org.

[42]

F. Petrini, D. Kerbyson, and S. Pakin. The case of the missing supercomputer performance: Achieving optimal performance on the 8,192 processors of ASCI Q. In SC '03: Proceedings of the 2003 ACM/IEEE conference on Supercomputing, 2003.

Digital Library

[43]

J. I. Pickands. Statistical inference using extreme value order statistics. Annals of Statististics, 3: 119--131, 1975.

[44]

P. Radojković, V. Cakarević, J. Verdú, A. Pajuelo, F. J. Cazorla, M. Nemirovsky, and M. Valero. Thread to strand binding of parallel network applications in massive multi-threaded systems. In PPoPP-2010: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Bangalore, India, 2010.

Digital Library

[45]

A. Settle, J. Kihm, A. Janiszewski, and D. Connors. Architectural support for enhanced SMT job scheduling. In PACT '04: Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, 2004.

Digital Library

[46]

D. Shelepov, J. C. S. Alcaide, S. Jeffery, A. Fedorova, N. Perez, Z. F. Huang, S. Blagodurov, and V. Kumar. Hass: A scheduler for heterogeneous multicore systems. In ACM SIGOPS Operating Systems Review, 2009.

Digital Library

[47]

T. Sherwood, G. Varghese, and B. Calder. A Pipelined Memory Architecture for High Throughput Network Processors. In ISCA '03: Proceedings of the 30th Annual International Symposium on Computer Architecture, 2003.

Digital Library

[48]

E. Shmueli, G. Almasi, J. Brunheroto, J. Castanos, G. Dozsa, S. Kumar, and D. Lieber. Evaluating the effect of replacing CNK with Linux on the compute-nodes of Blue Gene/L. In ICS '08: Proceedings of the 22nd Annual International Conference on Supercomputing, 2008.

Digital Library

[49]

A. Snavely and D. M. Tullsen. Symbiotic job scheduling for a simultaneous multithreaded processor. In ASPLOS 2000: Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, 2000.

Digital Library

[50]

A. Snavely, D. M. Tullsen, and G. Voelker. Symbiotic jobscheduling with priorities for a simultaneous multithreading processor. In Proceedings of the 2002 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2002.

Digital Library

[51]

Snort network intrusion prevention and detection system. http://www.snort.org/.

[52]

N. Tajvidi. Design and implementation of statistical computations for Generalized Pareto Distributions. Technical Report, Chalmers University of Technology, 1996.

[53]

D. Tam, R. Azimi, and M. Stumm. Thread clustering: sharing-aware scheduling on SMP-CMP-SMT multiprocessors. In EuroSys '07: Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems, 2007.

Digital Library

[54]

TCPDUMP/LIBPCAP public repository. http://www.tcpdump.org/.

[55]

S. B. Vardeman. Statistics for Engineering Problem Solving. PWS publishing company, 1993.

[56]

V. Cakarević, P. Radojković, J. Verdú, A. Pajuelo, F. Cazorla, M. Nemirovsky, and M. Valero. Characterizing the resource-sharing levels in the UltraSPARC T2 processor. In MICRO-42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture, NY, USA, 2009.

Digital Library

[57]

J. Verdú. Analysis and Architectural Support for Parallel Stateful Packet Processing, PhD Thesis. Universitat Politècnica de Catalunya, 2008.

[58]

Vermont (VERsatile MONitoring Toolkit). http://vermont.berlios.de/.

[59]

S. S. Wilks. The large-sample distribution of the likelihood ratio for testing composite hypotheses. Annals of Mathematical Statistics, 9, 1938.

[60]

S. S. Wilks. Mathematical Statistics. Princeton University Press, 1943.

[61]

Wireshark network protocol analyzer. http://www.wireshark.org/.

[62]

T. Wolf, N. Weng, and C.-H. Tai. Design considerations for network processor operating systems. In ANCS '05: Proceedings of ACM/IEEE Symposium on Architectures for Networking and Communication Systems, Princeton, NJ, 2005.

Digital Library

Cited By

Kim YKim IChoi KAhn JPark JHuh J(2024)Interference-Aware DNN Serving on Heterogeneous Processors in Edge Systems2024 IEEE 42nd International Conference on Computer Design (ICCD)10.1109/ICCD63220.2024.00038(199-206)Online publication date: 18-Nov-2024
https://doi.org/10.1109/ICCD63220.2024.00038
Luan GPang PChen QXue SSong ZGuo M(2022)Online Thread Auto-Tuning for Performance Improvement and Resource SavingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.316941033:12(3746-3759)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3169410
Lai PFan RZhang XZhang WLiu FZhou J(2022)Utility Optimal Thread Assignment and Resource Allocation in Multi-Server SystemsIEEE/ACM Transactions on Networking10.1109/TNET.2021.312381730:2(735-748)Online publication date: Apr-2022
https://doi.org/10.1109/TNET.2021.3123817
Show More Cited By

Index Terms

Optimal task assignment in multithreaded processors: a statistical approach
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling

Recommendations

Optimal task assignment in multithreaded processors: a statistical approach
ASPLOS XVII: Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems

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 thread assignment, one of the most promising ways to improve system ...
Optimal task assignment in multithreaded processors: a statistical approach
ASPLOS '12

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 thread assignment, one of the most promising ways to improve system ...
An evaluation of speculative instruction execution on simultaneous multithreaded processors

Modern superscalar processors rely heavily on speculative execution for performance. For example, our measurements show that on a 6-issue superscalar, 93% of committed instructions for SPECINT95 are speculative. Without speculation, processor resources ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 47, Issue 4

ASPLOS '12

April 2012

453 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2248487

Issue’s Table of Contents

ASPLOS XVII: Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems
March 2012
476 pages
ISBN:9781450307598
DOI:10.1145/2150976
General Chair:
Tim Harris
Microsoft Research
,
Program Chair:
Michael L. Scott
University of Rochester

Copyright © 2012 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: 03 March 2012

Published in SIGPLAN Volume 47, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
1,192
Total Downloads

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

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kim YKim IChoi KAhn JPark JHuh J(2024)Interference-Aware DNN Serving on Heterogeneous Processors in Edge Systems2024 IEEE 42nd International Conference on Computer Design (ICCD)10.1109/ICCD63220.2024.00038(199-206)Online publication date: 18-Nov-2024
https://doi.org/10.1109/ICCD63220.2024.00038
Luan GPang PChen QXue SSong ZGuo M(2022)Online Thread Auto-Tuning for Performance Improvement and Resource SavingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.316941033:12(3746-3759)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3169410
Lai PFan RZhang XZhang WLiu FZhou J(2022)Utility Optimal Thread Assignment and Resource Allocation in Multi-Server SystemsIEEE/ACM Transactions on Networking10.1109/TNET.2021.312381730:2(735-748)Online publication date: Apr-2022
https://doi.org/10.1109/TNET.2021.3123817
Mordacchini MConti MPassarella ABruno R(2020)Human-centric Data Dissemination in the IoPACM Transactions on Autonomous and Adaptive Systems10.1145/336637214:3(1-25)Online publication date: 10-Feb-2020
https://dl.acm.org/doi/10.1145/3366372
Popov MJimborean ABlack-Schaffer DEigenmann RDing CMcKee S(2019)Efficient thread/page/parallelism autotuning for NUMA systemsProceedings of the ACM International Conference on Supercomputing10.1145/3330345.3330376(342-353)Online publication date: 26-Jun-2019
https://dl.acm.org/doi/10.1145/3330345.3330376
Cheng YChen WWang ZXiang Y(2017)Precise contention-aware performance prediction on virtualized multicore systemJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2016.06.00672:C(42-50)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.sysarc.2016.06.006
Diener MCruz EAlves MNavaux PKoren I(2016)Affinity-Based Thread and Data Mapping in Shared Memory SystemsACM Computing Surveys10.1145/300638549:4(1-38)Online publication date: 5-Dec-2016
https://dl.acm.org/doi/10.1145/3006385
Wu WMeng WSu WZhou GChiang Y(2016)Q2PACM Transactions on the Web10.1145/287306110:2(1-29)Online publication date: 29-Apr-2016
https://dl.acm.org/doi/10.1145/2873061
Mu JShankar KLysecky R(2013)Profiling and online system-level performance and power estimation for dynamically adaptable embedded systemsACM Transactions on Embedded Computing Systems10.1145/2442116.244213512:3(1-20)Online publication date: 8-Apr-2013
https://dl.acm.org/doi/10.1145/2442116.2442135
Ost LMandelli MAlmeida GMoller LIndrusiak LSassatelli GBenoit PGlesner MRobert MMoraes F(2013)Power-aware dynamic mapping heuristics for NoC-based MPSoCs using a unified model-based approachACM Transactions on Embedded Computing Systems10.1145/2442116.244212512:3(1-22)Online publication date: 8-Apr-2013
https://dl.acm.org/doi/10.1145/2442116.2442125
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.

Figures

Tables

Media

View Issue’s Table of Contents