Predicting software performance in symmetric multi-core and multiprocessor environments [Elektronische Ressource] / by Jens Happe

Predicting software performance in symmetric multi-core and multiprocessor environments [Elektronische Ressource] / by Jens Happe

-

English
245 Pages
Read
Download
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

Fakut at II - Informatik, Wirtschafts- und RechtswissenschaftenDepartment fur InformatikPredicting Software Performancein Symmetric Multi-coreand Multiprocessor EnvironmentsPhD thesis to gain the degree of"Doktor der Ingenieurwissenschaften"by:Dipl.-Inform. Jens HappeReferees:Prof. Dr. Ralf H. ReussnerProf. Dr. Eike BestDate of Disputation: November 28th, 2008IIAbstractWith today’s rise of multi-core processors in the desktop market and in common server systems,concurrency becomes a ubiquitous challenge in software development. Concurrency allows theimprovement of software performance by exploiting available processor cores. However, possibleperformance gained by concurrency can be limited by software bottlenecks or inherently sequentialparts of the application. Performance prediction methods help software architects to nd softwarebottlenecks in multiprocessing environments during the design phase. Unfortunately, in highlyconcurrent systems, current prediction methods result in errors up to several orders of magnitude.They neglect important in uences of the operating system schedulers and middleware leading toerroneous predictions. Therefore, this thesis addresses the challenge of performance predictionin symmetric multiprocessing environments. It proposes a performance modelling framework foroperating system schedulers such as implemented in Windows or Linux.

Subjects

Informations

Published by
Published 01 January 2009
Reads 32
Language English
Document size 17 MB
Report a problem

Fakut at II - Informatik, Wirtschafts- und Rechtswissenschaften
Department fur Informatik
Predicting Software Performance
in Symmetric Multi-core
and Multiprocessor Environments
PhD thesis to gain the degree of
"Doktor der Ingenieurwissenschaften"
by:
Dipl.-Inform. Jens Happe
Referees:
Prof. Dr. Ralf H. Reussner
Prof. Dr. Eike Best
Date of Disputation: November 28th, 2008IIAbstract
With today’s rise of multi-core processors in the desktop market and in common server systems,
concurrency becomes a ubiquitous challenge in software development. Concurrency allows the
improvement of software performance by exploiting available processor cores. However, possible
performance gained by concurrency can be limited by software bottlenecks or inherently sequential
parts of the application. Performance prediction methods help software architects to nd software
bottlenecks in multiprocessing environments during the design phase. Unfortunately, in highly
concurrent systems, current prediction methods result in errors up to several orders of magnitude.
They neglect important in uences of the operating system schedulers and middleware leading to
erroneous predictions. Therefore, this thesis addresses the challenge of performance prediction
in symmetric multiprocessing environments. It proposes a performance modelling framework for
operating system schedulers such as implemented in Windows or Linux. The modelling approach
re ects the performance-relevant features of operating system schedulers and can be customised
to represent the system under study. It can also be combined with other prediction methods to
increase their prediction accuracy. The in uence of the middleware on software performance is
addressed by a performance modelling approach to message-oriented middleware. The approach
combines abstract p models with measurements and, thus, can omit implementation
details of vendors. A series of case studies conducted in the scope of this thesis demonstrates
that both techniques reduce the prediction error to less than 5% to 10% in most cases.
Zusammenfassung
Mit der breiten Einfuhrung von Mehrkernprozessoren im Desktop- und Server-Markt wird Ne-
benl au gkeit zu einer allgegenw artigen Herausforderung fur die Software-Entwicklung. Neben-
au gkl eit erm oglicht es die verfugbaren Prozessoren und Kerne zu nutzen und so die Leis-
tungsf ahigkeit von Software-Systemen zu steigern. Allerdings kann der m ogliche Nutzen durch
Engp asse oder sequentielle Anteile der Anwendung beschr ankt sein. Performanz-Vorhersagen
zur Entwurfszeit k onnen Software-Architekten dabei unterstutzen solche Engp asse einer An-
wendung fruhzeitig zu identi zieren. Allerdings fuhren momentan ubliche Vorhersageverfahren
in hochgradig nebenau genl Systemen zu Fehlern von bis zu mehreren Gr o enordnungen. Sie
vernachl assigen wichtige Ein ussfaktoren des Betriebssystem-Schedulers und der Middleware
wodurch die fehlerhaften Vorhersagen entstehen. Durch diese Problemstellung motiviert, be-
sch aftigt sich die vorliegende Arbeit mit der Verbesserung von Performance-Vorhersageverfahren
in symmetrischen Mehrkern- und Mehrprozessorumgebungen. Die Arbeit fuhrt einen Ansatz zur
hierarchischen Modellierung von Betriebssystem-Schedulern (wie sie beispielsweise in Windows
oder Linux zu nden sind) ein. Die Modelle bilden die kritischen Ein usse der Betriebssystem-
Scheduler ab und k onnen an die Ausfuhrungsumgebung des untersuchten Systems angepasst wer-
den. Desweiteren lassen sie sich mit anderen existierenden Vorhersageverfahren integrieren, um
deren Vorhersagegenauigkeit zu verbessern. Um den Ein uss der Middleware zu beruc ksichtigen,
wird ein Ansatz zur Kombination abstrakter Performance-Modelle mit Messergebnissen vorge-
schlagen. Der Ansatz abstrahiert dabei von implementierungsspezi schen Details. Im Rahmen
dieser Arbeit wurde mit diesem Ansatz der Ein uss nachrichtenbasierter Kommunikation in
Unternehmensanwendungen vorhergesagt. Eine Reihe von Fallstudien, die im Rahmen dieser
Arbeit durchgefuhrt wurden, hat gezeigt, dass beide Ans atze den Vorhersagefehler in den meis-
ten F allen auf weniger als 5% bis 10% reduzieren k onnen.IVContents V
Contents
1. Introduction 1
1.1. Research Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Existing Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3. Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5. Executive Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2. Foundations 9
2.1. Software Performance Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1. P Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2. Open and Closed Workloads . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3. Model-driven Performance Engineering . . . . . . . . . . . . . . . . . . . . . 11
2.1.4. Performance Completions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2. Scheduling in Software Performance Evaluation . . . . . . . . . . . . . . . . . . . . 13
2.2.1. Scheduling Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2. Task Routing in Multi-Server Systems . . . . . . . . . . . . . . . . . . . . . 14
2.2.3. The Performance In uence of Workload Types and Scheduling Policies . . . 15
2.3. General Purpose Operating System Schedulers . . . . . . . . . . . . . . . . . . . . 17
2.3.1. Basic Concepts and Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2. Processes and Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3. Multilevel Feedback Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.4. Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.5. Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3. Basics of the Performance Modelling Framework for Operating System Schedulers 33
3.1. Experiment-based Derivation of Software Performance-Models . . . . . . . . . . . . 33
3.1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.1.2. A Method for Experiment-based Performance Model Derivation . . . . . . . 35
3.1.3. The Goal/Question/Metric-Approach for Experiment-based Performance
Model Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.4. Parametrisation of Performance Models . . . . . . . . . . . . . . . . . . . . 41
3.2. Overview of the Performance Modelling Framework . . . . . . . . . . . . . . . . . . 43
3.2.1. Performance-related Questions for GPOS Schedulers . . . . . . . . . . . . . 43
3.2.2. Categorisation of Performance-relevant Factors of GPOS Schedulers . . . . 44
3.2.3. MOSS { Overview of the Prediction Model . . . . . . . . . . . . . . . . . . 49
3.3. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4. Single Processor Scheduling 57
4.1. Time Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.1.1. Experiments { Overview and Motivation . . . . . . . . . . . . . . . . . . . . 57VI Contents
4.1.2. Answering the Questions { Scenarios, Metrics, Hypotheses, and Results . . 60
4.1.3. The MOSS Prediction Model for Scheduler Time Sharing . . . . . . . . . . 69
4.1.4. Validation of MOSS’ Prediction Accuracy . . . . . . . . . . . . . . . . . . . 74
4.2. Interactivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.2.1. Experiments { Overview and Motivation . . . . . . . . . . . . . . . . . . . . 78
4.2.2. Experiment Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2.3. Answering the Questions { Scenarios, Metrics, Hypotheses, and Results . . 81
4.2.4. Extending MOSS’ Prediction Model for GPOS Schedulers by Interactivity
Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.2.5. Validation of MOSS’ Prediction Accuracy . . . . . . . . . . . . . . . . . . . 99
4.3. Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.3.1. Evaluated Use Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.3.2. Architecture of HQ’s Application . . . . . . . . . . . . . . . . . . . . . . . . 107
4.3.3. Performance Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.3.4. Experimental Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3.5. Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.4. Discussion of Assumptions and Limitations . . . . . . . . . . . . . . . . . . . . . . 114
4.5. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5. Multiprocessor Scheduling 117
5.1. Multiprocessor Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.1.1. Experiments { Overview and Motivation . . . . . . . . . . . . . . . . . . . . 117
5.1.2. Expt Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.1.3. Answering the Questions { Scenarios, Metrics, Hypotheses, and Results . . 120
5.1.4. Extending MOSS to Symmetric Multiprocessor Systems . . . . . . . . . . . 132
5.1.5. Validation of MOSS’ Prediction Accuracy . . . . . . . . . . . . . . . . . . . 143
5.2. Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
5.2.1. Performance Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
5.2.2. Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
5.3. Discussion of Assumptions and Limitations . . . . . . . . . . . . . . . . . . . . . . 156
5.4. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
6. Message-based Communication 159
6.1. Performance Evaluation of Messaging Patterns . . . . . . . . . . . . . . . . . . . . 159
6.2. The Performance In uence of P . . . . . . . . . . . . . . . . . . . 161
6.3. PCM Completion Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.3.1. Messaging Completion Components . . . . . . . . . . . . . . . . . . . . . . 166
6.3.2. Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
6.4. Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
6.5. Discussion of Assumptions and Limitations . . . . . . . . . . . . . . . . . . . . . . 173
6.6. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
7. Related Work 175
7.1. Performance Evaluation of Scheduling Policies in Queueing Theory . . . . . . . . . 175
7.1.1. Performance Properties of Scheduling Policies in Single-Server Queues . . . 175
7.1.2. P Properties of Sc and Routing Policies for Multi-Server
Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.2. Performance Evaluation of Operating System Schedulers . . . . . . . . . . . . . . . 180
7.2.1. Multiprocessor Load Balancing of General Purpose Operating Systems . . . 180Contents VII
7.2.2. Interactivity and Processor Reservation in GPOS Schedulers . . . . . . . . 181
7.2.3. Real Time Operating Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.2.4. High Performance Computing . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.3. Infrastructure P Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.4. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
8. Conclusions 185
8.1. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
8.2. Bene ts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
8.3. Lessons Learned . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
8.4. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
A. The Palladio Component Model 193
A.1. CBSE Development Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
A.2. Component Speci cation (Component Developers) . . . . . . . . . . . . . . . . . . 193
A.3. Architecture Model (Software Architect) . . . . . . . . . . . . . . . . . . . . . . . . 195
A.4. Resource Model (System Deployer) . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
A.5. Usage Model (Domain Expert) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
B. Timed Coloured Petri Nets 197
B.1. Overview of the Structure of CPNs . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
B.2. Dynamic Behaviour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
B.3. Hierarchical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
B.4. Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
B.5. Data Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
B.6. CPN Modelling Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
C. Technological Background 207
C.1. Benchmark Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
C.1.1. Determining the Input Value for a Speci c Resource Demand . . . . . . . . 208
C.1.2. Resource Demand Break Down . . . . . . . . . . . . . . . . . . . . . . . . . 209
C.1.3. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
C.2. Workload Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
C.3. Resource Demand Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
C.4. Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
List of Figures 213
List of Tables 217
Bibliography 219VIII ContentsContents IX
Acknowledgements
This page is most likely one of the rst pages you are reading (and it’s actually the last one I
wrote). You want to know what you meant in a PhD-candidate’s life. A tough task for me.
However, this page gives me the possibility to re ect a long time of experimenting, discussing,
modelling, and writing. Many of you accompanied this work. We discussed ideas, gave feedback
to each others work, listened to talks and wrote papers together. I want you to know how much
I enjoyed that time!
First of all, I would like to thank Lucka for being an incredible girlfriend. Lucka, I love you
for your endless patience, your reassurance, and for showing me what is really important in life.
And, yes, I’m back now.
Furthermore, I would like to thank my parents for their absolute support which goes way
beyond my PhD-studies. I’m grateful for your motivation and your help. It is good to know that
there is someone you can rely on no matter how good or bad things go.
This thesis was accompanied by two great professors: Prof. Dr. Ralf Reussner and Prof. Dr.
Eike Best. Ralf, without your guidance and support, I would never have come this far. You gave
me a good feeling for what research is about. Your constructive feedback and advice helped me
to accomplish my goals, the large ones as well as the smaller ones. Furthermore, I would like to
thank Eike Best for supervising this thesis and for his detailed and constructive comments.
Moreover, this work would not have been possible with the continuous support of my PhD-
fellows Heiko Koziolek and Ste en Becker who accompanied my PhD-studies for the best part.
I really loved (and still love) the intensive and constructive discussions, the long days of paper
writing, and { not to forget { the beers we had (and the cocktails, by the way).
During the course of this thesis, I worked with many great people from various projects at the
University of Oldenburg and at the University of Karlsruhe (TH).
From the University of Oldenburg, I would like to thank Martin F anzle and Willhelm Hassel-
bring as well as my colleagues and TrustSoft fellows (note the alphabetic order): Marko Boskovic,
Abhishek Dhama, Viktoria Firus, Simon Giesecke, Andre van Hoorn, Henrik Lipskoch, Roland
Meyer, Karl-Heinz Pennemann, Astrid Rakow, Matthias Rohr, Christian Storm, Mani Swami-
nathan, Timo Warns, Daniel Winteler for their fruitful comments and constructive discussions.
Not to forget our secretaries Ira Wempe and Manuela Wuste feld: You have your heart in the
right place!
In Karlsruhe, the people of the Chair of Software Design and Quality strongly contributed
to this work. I would like to thank (again, in alphabetic order) Franz Brosch, Samuel Kounev
(Thanks for the very good atmosphere you brought to our o ce!), Klaus Krogmann, Michael
Kuperberg, Anne Martens, Christof Momm, Thomas Goldschmidt, Henning Groenda, Christoph
Rathfelder, Johannes Stammel for your constructive discussions, the great Dagstuhl sessions we
had, and the long nights in the wine-cellar. Furthermore, I would like to thank the good souls
of our institute, Elena Kienh ofer and Elke Sauer, who took the responsibility of nalising my
education and helped me out in any situation.
During the course of this work, I supervised the diploma theses of Henning Groenda and Holger
Friedrich whose contributions are also part of this work. Henning, you started the evaluation of
operating system schedulers and by this laid some of the fundamentals of this work. Holger, you
investigated message-based communication. Many thanks to both of you! I really enjoyed (andX Contents
still enjoy) working with you. I would also like to thank all students that worked with me during
the last years: Tobias Dencker, Ihssane El-Oudghiri, Rainer Scheuerer, and Wenyun Zhou. Your
work and your input helped me to keep things going.
Last but not least, I would like to thank my Czech and Slovak colleagues Barbora Zimmerova,
Jan Kofron, and Lucia Kapova for the great time we had together in Karlsruhe. I’m already
missing our (almost) Check/Czech evenings. It was great to have you here!
To all of you, who are not listed here but have the strong feeling that they actually should be:
Please let me know. I guess I won’t be able to change these acknowledgements, but I’m de nitely
able to buy you a beer.