Quality and utility [Elektronische Ressource] : on the use of time-value functions to integrate quality and timeliness flexible aspects in a dynamic real-time scheduling environment / Thomas Schwarzfischer
315 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Quality and utility [Elektronische Ressource] : on the use of time-value functions to integrate quality and timeliness flexible aspects in a dynamic real-time scheduling environment / Thomas Schwarzfischer

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

Informations

Published by
Published 01 January 2005
Reads 36
Language English
Document size 5 MB

Exrait

Quality and Utility
On the Use of Time-Value Functions to
Integrate Quality and Timeliness Flexible
Aspects in a Dynamic Real-Time
Scheduling Environment
Thesis
in partial fulfillment of the requirements of the degree of
Doctor of Science (Dr. rer. nat.)
at the
Faculty of Mathematics and Informatics
of the
University of Passau
Thomas Schwarzfischer
October 2004
Day of Oral Exam: 21 January 2005Abstract
Scheduling methodologies for real-time applications have been of keen interest to diverse research com-
munities for several decades. Depending on the application area, algorithms have been developed that are
tailored to specific requirements with respect to both the individual components of which an application
is made up and the computational platform on which it is to be executed. Many real-time scheduling algo-
rithms base their decisions solely or partly on timing constraints expressed by deadlines which must be met
even under worst-case conditions. The increasing complexity of computing hardware means that worst-
case execution time analysis becomes increasingly pessimistic. Scheduling hard real-time computations
according to their worst-case execution times (which is common practice) will thus result, on average,
in an increasing amount of spare capacity. The main goal of flexible real-time scheduling is to exploit
this otherwise wasted capacity. Flexible scheduling schemes have been proposed to increase the ability
of a real-time system to adapt to changing requirements and nondeterminism in the application behav-
iour. These models can be categorised as those whose source of flexibility is the quality of computations
and those which are flexible regarding their timing constraints. This work describes a novel model which
allows to specify both flexible timing constraints and quality profiles for an application. Furthermore, it
demonstrates the applicability of this specification method to real-world examples and suggests a set of
feasible scheduling algorithms for the proposed problem class.
Zusammenfassung
Einplanungsverfahren fu¨r Echtzeitanwendungen stehen seit Jahrzehnten im Interesse verschiedener For-
schungsgruppen. Abha¨ngig vom Anwendungsgebiet wurden Algorithmen entwickelt, welche an die spe-
zifischen Anforderungen sowohl hinsichtlich der einzelnen Komponenten, aus welchen eine Anwendung
besteht, als auch an die Rechnerplattform, auf der diese ausgefu¨hrt werden sollen, angepasst sind. Viele
Echtzeit-Einplanungsverfahren gru¨nden ihre Entscheidungen ausschließlich oder teilweise auf Zeitbe-
dingungen, welche auch bei Auftreten maximaler Ausfu¨hrungszeiten eingehalten werden mu¨ssen. Die
zunehmende Komplexita¨t von Rechner-Hardware bedeutet, dass die Worst-Case-Analyse in steigendem
Maße pessimistisch wird. Die Einplanung harter Echtzeit-Berechnungen anhand ihrer maximalen Aus-
fu¨hrungszeiten (was die ga¨ngige Praxis darstellt) resultiert daher im Regelfall in einer frei verfu¨gbaren
Rechenkapazita¨t in steigender Ho¨he. Das Hauptziel flexibler Echtzeit-Einplanungsverfahren ist es, diese
ansonsten verschwendete Kapazita¨t auszunutzen. Flexible Einplanungsverfahren wurden vorgeschlagen,
welche die Fa¨higkeit eines Echtzeitsystems erho¨hen, sich an vera¨nderte Anforderungen und Nichtdeter-
minismus im Verhalten der Anwendung anzupassen. Diese Modelle ko¨nnen unterteilt werden in solche,
deren Quelle der Flexibilita¨t die Qualita¨t der Berechnungen ist, und jene, welche flexibel hinsichtlich ihrer
Zeitbedingungen sind. Diese Arbeit beschreibt ein neuartiges Modell, welches es erlaubt, sowohl flexible
Zeitbedingungen als auch Qualita¨tsprofile fu¨r eine Anwendung anzugeben. Außerdem demonstriert sie
die Anwendbarkeit dieser Spezifikationsmethode auf reale Beispiele und schla¨gt eine Reihe von Einpla-
nungsalgorithmen fu¨r die vorgestellte Problemklasse vor.Acknowledgements
The best way to become acquainted with a
subject is to write a book about it.
Benjamin Disraeli
Gratitude is merely the secret hope of fur-
ther favours.
Franc¸ois de La Rochefou-
cauld
As is the case in most circumstances in life, achievements are not normally possible with-
out the assistance of numerous well-meaning people. The same was true for the undertaking of
carrying out my PhD research.
Representing so many who contributed to the successful completion of this work either
through active help or by mental support, I would like to thank the following persons by name.
I thank Prof. Dr.-Ing. Werner Grass for his long lasting assistance and guidance, numerous im-
pulses to gain new insights and especially for helping me place my work into a bigger context.
I am grateful to Prof. Dr.-Ing. Ju¨rgen Teich of Friedrich-Alexander University in Erlangen for
acting as an external referee, and to Prof. Dr. Gottlieb Leha, Prof. Christian Lengauer, PhD,
and Prof. Dr. Volker Weispfenning to sit on the committee for the oral examination. The advice
of Prof. Dr. Niels Schwartz was essential for coming to terms with formal requirements of the
graduation process. I say my thanks to all the people in our group, especially to Dr. Bernhard
Sick for his cooperation, Martin Grajcar for various spontaneous ideas and Markus Ramsauer for
numerous fruitful discussions while working on the same project. I extend my thanks to Franz
Rautmann for keeping our technical equipment running most of the time and Eva Kapfer for her
constant effort to establish a hearty and welcoming climate at the institute.
I thank our students for their participation in the PaSchA project: Christian Ju¨nger, Klaus
Ehrnbo¨ck, Jakob Flierl, Kerstin Meyerhofer, Selc¸uk Demirci, Robert Schiller, Katrin Limpo¨ck,
Diana Lucic, Matthias Weindler, Peter Zach, Bettina Riedmann, Barbara Busse, Christian Mu¨ller,
Ralf Zimmermann and others I might have forgotten to mention.
I also greatly appreciated the comments of Prof. Dr. Hiroshi Nagamochi, Dr. Koji Nonobe
and Dr. Mutsunori Yagiura of the University of Kyoto during the final stages of my PhD project,
when I could spend interesting months at their institute.I thank all those who encouraged me to carry on with endless patience every time I had
lost the necessary confidence, first of all Michiko Araseki for all her love. Finally, I am deeply
indebted to my parents, Agnes and Karl Schwarzfischer, who gave me the opportunity to pursue
my studies, and to God for providing me with the abilities to do so.
Passau, January 2005
Thomas SchwarzfischerContents
1 Introduction 1
1.1 The Relationship between Planning and Scheduling . . . . . . . . . . . . . . . . 2
1.2 Basic Real-Time Scheduling Terminology . . . . . . . . . . . . . . . . . . . . . 3
1.3 The Quality of Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 The Run-to-Completion Assumption . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Quality-Flexible Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 The Timeliness of Computations . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 Traditional Timing Constraints in Scheduling . . . . . . . . . . . . . . . 8
1.4.2 Timeliness-Flexible Scheduling . . . . . . . . . . . . . . . . . . . . . . 9
1.5 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Aims of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.8 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.9 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 The Basic Quality / Utility Scheduling Problem 15
2.1 Basic Quality / Utility Scheduling Problem . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Application Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.2 Quality and Utility Functions . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.3 Local Time Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.4 Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Dynamic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Time-Variant Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Properties of Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Example Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.1 Pointwise Sum of Product of Utility and Quality Functions with Outer
Hold Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
v2.5.2 Pointwise Sum of Product of Utility and Quality Functions with Inner
Hold Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.3 Pointwise Sum of Product of Quality and Utility Functions with Addi-
tional Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.3.1 Background Anytime Tasks . . . . . . . . . . . . . . . . . . . 35
2.5.3.2 Tasks with Mandatory and Optional Service Times . . . . . . . 35
2.5.4 Pointwise Maximum of Product of Utility and Quality Functions . . . . . 36
3 Scheduling Algorithms 37
3.1 Reactive Unconditional Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.1 Determining the Task Set . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.2 Local-Search Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.2.1 Calculation of Elementary Intervals . . . . . . . . . . . . . . . 42
3.1.2.2 Allocations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1.2.3 Optimisation of Resource Allocation . . . . . . . . . . . . . . 50
3.1.2.3.1 Simulated Annealing . . . . . . . . . . . . . . . . . 51
3.1.2.3.2 Tabu Search . . . . . . . . . . . . . . . . . . . . . . 54
3.1.2.4 Search Guidance . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.1.3 Lagrange Multiplier Approach . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Proactive Conditional Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.3 Experimental Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4 General Quality / Utility Scheduling Problem 69
4.1 Extended Model for Quality / Utility Scheduling Problems . . . . . . . . . . . . 70
4.2 Processors, Methods and Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 Hardware Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2.2 Library Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2.3 Application Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.4 Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3 Task Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.1 Hierarchy Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.2 Instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.3.3 Local Time Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.3.4 And/or Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.3.5 Implications on Scheduling Algorithms . . . . . . . . . . . . . . . . . . 87
vi4.3.5.1 And/or Graph . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.5.2 Instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3.6 Caching Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.4 Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.4.1 Dependencies on the Task / Method Level . . . . . . . . . . . . . . . . . 100
4.4.2 Dependencies on the Instance Level . . . . . . . . . . . . . . . . . . . . 102
4.4.3 Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4.4 Interpreting Edge Weights . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.4.5 Limiting the Scope of Value Dependencies . . . . . . . . . . . . . . . . 107
4.5 Dynamic Scheduling Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5 The Cost of Scheduling and Adaptivity 111
5.1 Adaptive Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.2 The Scheduling / Execution Problem . . . . . . . . . . . . . . . . . . . . . . . . 113
5.3 Meta Scheduling Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.3.1 Real-Time Scheduling Approach . . . . . . . . . . . . . . . . . . . . . . 118
5.3.2 Artificial Intelligence Approach . . . . . . . . . . . . . . . . . . . . . . 120
5.3.3 Meta Scheduling for the Quality / Utility Problem . . . . . . . . . . . . . 121
5.4 Closed-Loop Meta Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.4.1 Distributed vs Centralised Adaptation . . . . . . . . . . . . . . . . . . . 123
5.4.2 Feedback Mechanism for Meta Scheduler . . . . . . . . . . . . . . . . . 124
6 Case Studies 131
6.1 Eye Movement Tracking in Laser-Optical Surgery . . . . . . . . . . . . . . . . . 132
6.1.1 Task Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.1.2 Dependency Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.1.3 Quality Flexibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.1.4 Alternative Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.1.5 Spatial Referencing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.1.6 Safety Subsystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.1.7 Timeliness Flexibility . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.1.8 Application Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6.2 Adaptive Video Streaming Applications . . . . . . . . . . . . . . . . . . . . . . 141
6.2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.2.2 Live Video Streaming Applications . . . . . . . . . . . . . . . . . . . . 144
6.2.3 Filter-Based Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . 144
vii6.2.3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.2.3.2 Flexibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.2.3.3 Application Graph . . . . . . . . . . . . . . . . . . . . . . . . 146
6.2.4 Compression-Based Adaptation . . . . . . . . . . . . . . . . . . . . . . 148
6.2.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.2.4.2 Flexibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.2.4.3 Application Graph . . . . . . . . . . . . . . . . . . . . . . . . 149
7 Simulation Environment 153
7.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.2 Application Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
7.2.1 Hardware Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
7.2.2 Software Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7.2.2.1 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7.2.2.2 Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.2.2.3 Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.3 I/O Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
7.3.1 Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
7.3.2 Graph Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.3.3 Application Graph Files . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.4 Simulation Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.4.1 Configuration Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.4.2 Simulator User Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 160
7.4.3 Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
7.5 Log Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.6 Visualisation Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.6.1 Log View Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.6.2 Time View Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.6.3 Graph View Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.6.4 Statistics View Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.7 Scheduler Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.8 Benchmark and External Components . . . . . . . . . . . . . . . . . . . . . . . 166
8 Experimental Results 167
8.1 Application Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.1.1 Method Execution Times . . . . . . . . . . . . . . . . . . . . . . . . . . 169
viii