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

Jens Happe

Sujets

• Informatik

Informations

• Publié par: carl_von_ossietzky_universitat_oldenburg
• Publié le: 01 janvier 2009
• Nombre de lectures: 32
• Langue: English
• Poids de l'ouvrage: 17 Mo

Extrait

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 { Scen