Leistungsbewertung bei Computersystemen: Praktische Performance-Analyse von Rechnern und ihrer Kommunikation [1 ed.] 3540710531, 9783540710530, 9783540710547 [PDF]

Zitiervorschau

X. systems.press X.systems.press ist eine praxisorientierte Reihe zur Entwicklung und Administration von Betriebssystemen, Netzwerken und Datenbanken.

Hans Günther Kruse

Leistungsbewertung bei Computersystemen Praktische Performance-Analyse von Rechnern und ihrer Kommunikation

123

Hans Günther Kruse Universität Mannheim Rechenzentrum 68131 Mannheim [email protected]

ISBN 978-3-540-71053-0

e-ISBN 978-3-540-71054-7

DOI 10.1007/978-3-540-71054-7 X.systems.press ISSN 1611-8618 Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar. © 2009 Springer-Verlag Berlin Heidelberg Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte, insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Einbandgestaltung: KünkelLopka, Heidelberg Gedruckt auf s¨aurefreiem Papier 987654321 springer.de

Inhaltsverzeichnis

1

Vorbemerkungen zur Last mit der Leistung.........................................

1

2

Einfache Leistungsmaße.......................................................................... 2.1 Takt, CPI und Ablaufzeit .................................................................. 2.2 Durchsatz, MIPS und MFLOPs ........................................................

5 5 10

3

Die Gesetze von Amdahl und Gustafson................................................ 3.1 Das Gesetz von G. Amdahl............................................................... 3.2 Amdahl und das Vektor-Pipeline-Prinzip ......................................... 3.3 Das skalierte Gesetz von Gustafson.................................................. 3.4 Befehlsverarbeitung nach dem Pipeline-Prinzip ............................... 3.5 Zusammenfassung ............................................................................

15 15 18 22 24 26

4

Die Gesetze von Little .............................................................................. 27 4.1 Voraussetzungen ............................................................................... 27 4.2 Die Herleitung der Gesetze ............................................................... 31 4.3 Zusammenfassung ............................................................................ 35

5

Benchmarks oder die Last mit der Last................................................. 5.1 Historie und Voraussetzung .............................................................. 5.2 Ein explizites Benchmark-Beispiel ................................................... 5.3 Vergleich von Benchmarks............................................................... 5.4 Einige statistische Standardmethoden...............................................

6

Messbare Leistungsgesetze...................................................................... 53 6.1 Herleitung des globalen Auslastungsgesetzes................................... 53 6.2 Lokale Auslastungsgesetze und die Flaschenhals-Analyse............... 55 6.3 Die Segmentierung von Systemen .................................................... 57 6.4 Das Central-Server-System............................................................... 61 6.5 Das verallgemeinerte Antwortzeit-Gesetz ........................................ 64 6.6 Dialogsysteme................................................................................... 67

37 37 39 45 48

VI

Inhaltsverzeichnis

7

Einfache stochastische Modellvorstellungen ......................................... 73 7.1 Voraussetzungen ............................................................................... 73 7.2 Ableitung der Zeit-Dynamik und Skizze der Lösung ....................... 75 7.3 Zeitunabhängige Lösungen im Gleichgewicht.................................. 77 7.4 Weitere Leistungsgrößen .................................................................. 80 7.5 Endliche Modelle .............................................................................. 83

8

Die Chapman-Kolmogoroff-Gleichungen.............................................. 8.1 Der Übergang 0→0........................................................................... 8.2 Der Übergang 1→1........................................................................... 8.3 Der Übergang 0→1........................................................................... 8.4 Der Übergang 1→0........................................................................... 8.5 Zusammenfassung und Ableitung der Zustandsgleichungen............ 8.6 Zur Lösung der Zustandsgleichungen............................................... 8.7 Zwei konkrete Modelle über Reserve ...............................................

87 88 89 90 91 91 93 96

9

Von der Lust am Modellieren ................................................................. 9.1 M/M/1/∞ und die Skalierung ........................................................... 9.2 Das Modell M/M/1/B mit endlichem Wartepool .............................. 9.3 Ein weiteres Verlust-Modell mit p Prozessoren................................ 9.4 Der Fall unendlich vieler Prozessoren .............................................. 9.5 Modelle mit variabler Last................................................................ 9.6 Komposition von Submodellen......................................................... 9.7 Leistungsunterschiede....................................................................... 9.8 Modell eines File-Servers .................................................................

103 103 104 107 111 112 116 118 123

10 Leistungsanalyse auf Modellbasis........................................................... 131 10.1 Die Diskussion des offenen Modellsystems ..................................... 132 10.2 Über die Analyse von geschlossenen Systemen ............................... 139 11 Konzepte zur Analyse von Kommunikationssystemen......................... 11.1 Allgemeine strukturelle Überlegungen ............................................. 11.2 Analyse des ALOHA-Protokolls ...................................................... 11.3 Eine Verbesserung mit Slotted ALOHA........................................... 11.4 Eine anspruchsvollere Analyse von Slotted ALOHA .......................

149 149 153 158 161

12 Modell und Wirklichkeit ......................................................................... 12.1 Bemerkungen zu den Modellvoraussetzungen.................................. 12.2 Ein explizites Beispiel....................................................................... 12.3 Modelle des G/M/1/∞-Typs mit nicht bekannter Ankunftsverteilung............................................ 12.4 Modell mit deterministischer Ankunftszeit....................................... 12.5 Allgemeine Bedienzeiten .................................................................. 12.6 Beispiel zu einem Modellvergleich...................................................

165 165 167 170 173 176 177

Inhaltsverzeichnis

13 Über die Gültigkeit von Gesetzen ........................................................... 13.1 Die Skalierung nach Amdahl und Gustafson .................................... 13.2 Verallgemeinerte Durchsatzskalierung ............................................. 13.3 Ein möglicher Ansatz über Prozessorkonfigurationen...................... 13.4 Die Effizienz von p Prozessoren....................................................... 13.5 Über eine mögliche Einbeziehung der Kommunikation ...................

VII

181 181 184 186 188 191

Literaturverzeichnis ........................................................................................ 195 Index ................................................................................................................. 197

1 Vorbemerkungen zur Last mit der Leistung

Die Leistungsanalyse von Rechnern und Rechnernetzen ist im Prinzip aus der Notwendigkeit entstanden, vorhandene Systeme auf Schwachstellen hin zu untersuchen, um anschließend Verbesserungen konzipieren zu können. Voraussetzung ist natürlich, dass man eine genaue Vorstellung von Leistung hat, und dies ist leider nicht immer gewährleistet. Im Rahmen eines nahe liegenden Ansatzes wäre es natürlich möglich, sich auf die Physik zu besinnen und Leistung als Arbeit pro Zeit zu definieren. Für viele Situationen und Systeme trifft diese einfache Vorgehensweise auch zu und wir werden sie auch später ausgiebig nutzen, jedoch immer die Grenzen aufzeigen. Will man jedoch die Leistungsfähigkeit eines hochkomplexen Systems wie das eines heutigen Computers oder Rechnernetzes bewerten, so muss man sich genau überlegen, welche Größen bzw. Variablen die Leistung beschreiben. Besteht die Leistung in einer möglichst schnellen Verarbeitung von Befehlen oder im Befehlsumfang, besteht sie aus der Größe der Speicherkapazitäten oder der Organisationsform wie SingleUser/SingleTask, MultiUser/MultiTask, Dialogund Batch-Betrieb? Auch hier wird es auf die Gründe der Leistungsanalyse ankommen, welche letztlich die Auswahl der entsprechenden Variablen oder Messgrößen festlegen. So wird es einen großen Unterschied ausmachen, ob die Geschwindigkeit beim Übersetzen von Programmen oder die Verarbeitung einer großen Anzahl von Gleitkommaoperationen im Vordergrund steht. Beide Male sind Maschinenbefehle zu analysieren, wobei aber Organisation und Ablauf völlig verschieden sind. Bei Übersetzern/Compilern kommt es auf die effiziente Nutzung von Befehlen auf Zeichenketten und zum Lesen/Schreiben des Hauptspeichers an. Bei den Gleitkommaoperationen ist es häufig nur eine Addition, die gleichförmig über eine große Anzahl von Operanden abläuft. Oder betrachten wir eine andere Anwendung, welche sehr stark vom Zugriff auf Datenbanken Gebrauch macht. Die dazugehörigen Transaktionen hängen von den Speicher- und I/O-Zugriffen ab, auch die Cache-Organisation spielt eine Rolle, numerische oder Zeichenkettenoperationen wie bei unseren beiden ersten Beispielen treten völlig in den Hintergrund. Natürlich kann man argumentieren, dass

2

1 Vorbemerkungen zur Last mit der Leistung

die Laufzeit zcpu [sec] aller drei Anwendungen die entscheidende Leistungsgröße ist – je kürzer, desto effizienter und leistungsfähiger –, die Ursache dafür sind jedoch so verschieden, dass kein Leistungsvergleich auf dieser Ebene einen Sinn macht. Wir werden uns daher in den folgenden Ansätzen bemühen, solche Widersprüchlichkeiten zu vermeiden, und beginnen mit der Darstellung der grundsätzlichen Situation bei der Leistungsanalyse (s. Abb. 1.1).

Erzeugung einer Last

Messung einer Last

Verarbeitung der Last

Leistungsanalyse Abb. 1.1 Last/Leistungsmodell

Zentral sind hierbei die Begriffe Leistung, dessen Problematik schon skizziert wurde, und Last. Im einfachsten Fall wird dies – die Last – ein typisches Anwendungsprogramm sein, welches von einem Compiler in Maschineninstruktionen umgewandelt, in der Verarbeitungseinheit abläuft. Genauso denkbar ist aber ein Datenpaket mit definiertem Aufbau und Länge, welches in einem Router an eine bestimmte Adresse (forwarding) geschickt wird. In beiden Fällen besteht die Last aus einem Objekt, an welchem z. B. die Ablaufzeit (CPU-Zeit) bestimmt wird – man misst einen individuellen Auftrag. Der weitaus schwierigere Fall besteht darin, die Last aus mehreren Programmen oder vielen Datenpaketen zu gestalten, die untereinander kein einheitliches Verhalten zeigen. So enthalten sie mal mehr, mal weniger I/O-Anweisungen oder Gleitkommaoperationen – auch können die Datenpakete im Routerbeispiel unterschiedlich lang sein, ähnlich ist es bei den Datenbanktransaktionen. Wenn es Variablen gibt, die eine gewisse statistische Gesetzmäßigkeit aufweisen, kann man diese zur Beschreibung der Gesamtlast heranziehen – allerdings sind dabei häufig gewisse vereinfachende Modellvorstellungen nicht zu vermeiden. Als Leistungskenngröße bietet sich hier der Durchsatz an, d. h. die Anzahl der bearbeiteten Aufträge oder Datenpakete pro Zeiteinheit. Interessanterweise kommen wir mit diesem Begriff „Durchsatz“ auch an die physikalische Definition Arbeit pro Zeit nahe heran. Bei den vorausgegangenen Ausführungen war immer von den DV-Systemen als Ganzes ausgegangen und die entsprechenden Leistungsmaße wie Systemzeit oder Durchsatz definiert worden. Nun kann man die Komponenten wie E/A-Subsystem,

1 Vorbemerkungen zur Last mit der Leistung

3

Bus, Caches oder Platten entsprechend behandeln und Leistungsmaße wie Bandbreite (Mbit/sec), Hitraten oder Umdrehungen pro Sekunde (rps) einführen – aber es wird sehr schwierig, Maße für das Zusammenwirken solcher Komponenten zu finden. Dies verkompliziert sich noch, wenn zur Hardware noch Software wie Betriebssysteme oder Netzprotokolle treten. Aus diesem Grund verzichten wir in den folgenden Analysen und Diskussionen weitgehend auf die Berücksichtigung von Details und bleiben bei der bereits anfangs konzipierten „Black-Box“. Das bedeutet die Lastdefinition und Lastmessung „vor“ der Box und die Leistungsmessung „hinter“ der Box. Dabei beachten wir folgende Grundsätze: 1. Last- und Leistungsmaß müssen miteinander korrespondieren, z. B. wird man ein interaktives System anders als ein Batch-System ausmessen. 2. Sorgfältige Auswahl geeigneter statistischer Techniken, um die Messungen zu validieren und zu vergleichen. 3. Vergleich der gemessenen Werte mit entsprechenden Ergebnissen analytischer oder simulativer Modelle. Der letzte Punkt mag vor dem Hintergrund der reinen Messung nicht ganz einsichtig erscheinen, tatsächlich zeigt aber die praktische Erfahrung, wie wichtig gut strukturierte und validierte Modelle für das Verständnis von Systemleistung sind. Die Leistungsanalyse und Modellierung haben ihren Ursprung in der Telefonie, erst nach dem Zweiten Weltkrieg und vor allem zu Beginn der 70er-Jahre des letzten Jahrhunderts wurden sie mit Erfolg auf dem Feld der Rechner und Netze angewandt. Da die analytischen Methoden für die immer komplexer werdenden Systeme bald nicht mehr ausreichten, entstanden umfangreiche und leistungsfähige numerisch orientierte Algorithmen und Programme. Vor allem die Entwicklung der Internettechnologie und der Druck, eine effiziente Steuerung der Mainframes/Großrechner, die damals die Hauptstütze der Datenverarbeitung darstellten, zur Verfügung zu haben, hatten einen entscheidenden Anteil daran. In dieser Zeit entstand auch das klassische Werk von L. Kleinrock [1], welches bis in die heutige Zeit ein Standard hinsichtlich der grundsätzlichen analytischen Methodik geblieben ist. Wir werden uns in den Ausführungen der anschließenden Kapitel, vor allem bei der Modellierung häufig darauf beziehen. In den letzten 20 Jahren sind zahlreiche Lehrbücher zur Thematik „Leistungsanalyse“ erschienen, wir werden häufig Bezug nehmen auf die Werke von Raj Jain [2], von M. Haas und W. Zorn [3], die ausgezeichneten Werke von Tran-Gia [4] und G. Bolch [5]. Eine herausragende Rolle spielt das Lehrbuch von Hennessy & Patterson [6], dem viele moderne Anregungen und instruktive Beispiele entnommen wurden. Gerade dieses Buch zeigt, wie man analytisch-mathematische Methoden zum Verständnis sinnvoll nutzen kann, ohne die Methodik und Mathematik als Selbstzweck (l’art pour l’art) darzustellen. Ein ähnliches Ziel, allerdings ohne Berücksichtigung von Hardware-Details, ist hier auch ins Auge gefasst. Meinen Kollegen Dr. Erich

4

1 Vorbemerkungen zur Last mit der Leistung

Strohmaier in Berkeley und Dr. Heinz Kredel in Mannheim verdanke ich ebenfalls in dieser Richtung viele wertvolle Diskussionsbeiträge sowie Herrn Prof. Effelsberg/Mannheim die günstigen Rahmenbedingungen. Ich habe mich, zumindest in den ersten Kapiteln, bemüht, mit einer elementaren Mathematik auszukommen, bis auf einige „Ausrutscher“ bei Statistik-Problemen im Kap. 5 über Benchmarks sollte dies im Großen und Ganzen gelungen sein. In den folgenden Ausführungen des Kap. 6 über messbare Leistungsgesetze kommt die Technik der linearen Gleichungssysteme zum Einsatz, während ab Kap. 7 einfache Differenzialgleichungen 1. Ordnung in der Zeit eine Rolle spielen. Hier wurden einmal bei der Lösung einer speziellen Gleichung etwas ausführlicher als notwendig mathematische Details skizziert, diese können jedoch ohne Probleme übersprungen werden. Die Theorie der Markoff ’schen Prozesse, welche der sogenannten stochastischen Modellierung zugrunde liegt, wird nur in Ansätzen aufgezeigt und darüber hinaus auf jede mathematische Strenge verzichtet – der Schwerpunkt liegt eindeutig auf der Nachvollziehbarkeit der Beispiele. Dies gilt auch für die Skizze der Chapman-Kolmogoroff-Gleichungen und ihrer Herleitung, welche mir nicht nur wegen der Vollständigkeit, sondern wegen ihrer praktischen Anwendung unverzichtbar erscheint. Im Kap. 10 über Leistungsgesetze und Modellierung wird der Versuch unternommen, Messung und Theorie in Einklang zu bringen, die Beschränkung auf den Algorithmus der Mittelwertanalyse (MVA) ist vor dem Hintergrund eines Einstiegs in diese Art von Verfahren zu sehen. Der an mehr und detaillierteren Informationen interessierte Leser sei an dieser Stelle auf das ausgezeichnete Buch von G. Bolch [5] verwiesen. Das folgende Kap. 11 beschäftigt sich mit einigen Ideen und Konzepten zur Leistungsanalyse von Kommunikationssystemen, wobei zunächst weitgehend auf bereits diskutierte Schemata zurückgegriffen wird. Da die stochastische Modellierung für Protokolle sehr viel an mathematischer Technik verlangt, wurde zunächst ein relativ simpler Ansatz gewählt, der anschließend verfeinert wird, und deshalb etwas aufwendiger ist. Auch hier können die mathematischen Details aber ohne Probleme übergangen werden. Die beiden letzten Kap. 12 und 13 beschäftigen sich mit dem Spannungsverhältnis von Modell und Wirklichkeit sowie der Gültigkeit von zwei wichtigen Leistungsgesetzen bei modernen Clusterarchitekturen. Da es sich gezeigt hat, dass in vielen Fällen die diskutierten Modellierungstechniken nicht ausreichen, möchte ich hier Hinweise geben, wie man in diesen Fällen zu verfahren hat, aber auch nicht verschweigen, dass ab jetzt doch Einiges mehr an Mathematikkenntnissen notwendig ist. An der schriftlichen Form dieser Ausarbeitung waren eine Reihe von Studierenden als Hilfskräfte beteiligt. Erwähnen möchte ich Florian Strasser, Julia Doll, Bernhard Kusch und besonders Sabrina Hauser – ihnen allen gilt mein Dank für ihre Geduld und ihre Mühe.

2 Einfache Leistungsmaße

In diesem Kapitel geht es um einfache, direkt messbare Leistungsgrößen oder -maße, welche eine erhebliche Bedeutung über alle Systemklassen und Größenordnungen hinweg haben.

2.1 Takt, CPI und Ablaufzeit Das am leichtesten zugängliche Leistungsmaß einer Hardware, um genauer zu sein, eines Prozessors, ist das diskrete feste Zeitraster, nach dem sich alle Aktionen ausrichten – der Takt! So entspricht der 100-MHz-Takt längst Vergangenheit gewordener Maschinen einem Zeitabstand zwischen zwei Ereignissen – der Basistaktzeit bzeit – von 10 nsec, das sind 10*10–9 sec. Die heutigen Gigahertz-Prozessoren entsprechen einem Abstand von 1 nsec. Zählen wir die Takte, welche eine vorgegebene Last benötigt, mit der Variable #takte (# bezeichnet immer eine Anzahl), dann ergibt sich die Ablaufzeit zcpu der Last zu zcpu = # takte * bzeit =

# takte # takte = 1 takt bzeit

denn klarerweise ist takt = 1/bzeit. Hierbei ist die Variable #takte zwar unmittelbar einsichtig, aber schlecht einer direkten Messung zugänglich, weiterhin ist damit die Last nicht vor, sondern nach der Verarbeitung definiert – eine zu große Abweichung von unserem Konzept. Deshalb wird wie folgt verfahren. Die Zahl der Instruktionen der Last #last lässt sich im Prinzip vor der Verarbeitung bestimmen. Wir messen die Zahl der benötigten Takte #takte und bestimmen mit der Größe cpi, wie viel Takte für eine Instruktion benötigt werden:

6

2 Einfache Leistungsmaße

cpi =

# takte # last

Für die Ablaufzeit folgt danach: zcpu =

# takte # takte # last = * takt # last takt

zcpu = cpi *

# last = # last * cpi * bzeit takt

Diese Umformungen sind keine überflüssige Spielerei, sondern widerspiegeln die drei wichtigsten Ebenen in einem DV-System: • #last = Zahl der Instruktionen, hängt von der Anwendung und Compilertechnologie ab; • cpi = Zahl der Basistakte, die für eine Instruktion benötigt wurde, hängt von der Maschinenarchitektur ab; • bzeit = Basistakt, ist direkt von der eingesetzten Hardware- Technologie abhängig.

So verkürzt eine steigende Taktrate die Basiszeit bzeit und damit in der Theorie die Ablaufzeit zcpu. Eine RISC-Architektur versucht, cpi auf den Wert 1 zu drücken, also einen Takt pro Instruktion – in superskalaren Maschinen liegt dieser Wert sogar darunter –, und hochoptimierende Compiler versuchen die Anzahl der Maschineninstruktionen #last zu minimieren. Die Größe cpi muss noch etwas genauer analysiert werden. Hintergrund ist die Tatsache, dass Maschinenbefehle unterschiedliches Zeitverhalten von den Hardware-Ressourcen her haben, und es daher kein exaktes globales cpi geben kann. Vielmehr muss man die Maschinenbefehle in Gruppen von Instruktionen einteilen, welche dann innerhalb der Gruppe k alle die gleiche Taktzahl pro Befehl besitzen:

{Instruktionen}k =1...n = > cpik =1...n Kennt man dann das prozentuale Gewicht pk jeder Gruppe mit p1 + p2 + p3 +... + pn = 1 (n ist die Gruppenanzahl), dann gilt für die globale Größe n cpi = ∑ p k * cpi k k =1

Das folgende Beispiel soll dies etwas verdeutlichen.

2.1 Takt, CPI und Ablaufzeit

7

B1 Wir betrachten eine Modell-RISC-Maschine mit den Befehlsgruppen

cpik

pk

Arithmetisch-logisch

ALU

1

0,4 (40%)

Speicher

LOAD/STORE

2

0,4 (40%)

Test & Verzweigung

JMP

3

0,2 (20%)

cpi = 1*0,4 + 2*0,4 + 3*0,2 =1,8

An der Größe cpi kann man jetzt sehr schön den Einfluss verschiedener Maßnahmen analysieren. Angenommen wir ändern durch den Einsatz eines besseren Compilers das Gewicht pn = In / I der n-ten Gruppe In → α*In, wobei 0 ≤ α ≤ 1. Aus dem alten Wert n

cpi =

⎛I ⎞ cpi k ⎜ k ⎟, I = ⎝ I ⎠ k =1

∑

n

∑I

k

k =1

wird dann

⎞ ⎛ ⎞ ⎛ I ⎟ ⎜ ⎟ ⎜ n -1 α * In k ⎟ ⎜ ⎟ ⎜ + cpin * cpi’ = ∑ cpik ⎟ ⎜ ⎟ ⎜ k =1 ⎜ I − ⎛⎜ I − αI ⎞⎟ ⎟ ⎜ I − ⎛⎜ I − αI ⎞⎟ ⎟ n⎠⎠ n⎠⎠ ⎝ ⎝ ⎝ n ⎝ n ⎛I ⎞ ⎛ α * p * cpi ⎞ n −1 1 n⎟ n = ∑ cpi * ⎜⎜ k ⎟⎟ * + ⎜⎜ k I ⎜ 1 - (1 - α) * p ⎟⎟ ⎜ ⎟ 1 − (1 − α) * p k =1 ⎝ ⎠ n ⎝ n⎠

(

)

⎛

⎞

⎟ ⎜ n −1 1 ⎟ ⎜ * * = + − * + α * * ∑ p cpi p cpi p cpi p cpi k n n n n n n⎟ 1 − (1 − α)pn ⎜ k =1k ⎟ ⎜ cpi ⎠ ⎝

Also folgt cpi’=

1 (cpi − (1 − α ) * p n * cpi n ) 1 − (1 − α) * p n

Da 0 ≤ pn, 1 – α ≤ 1, ist der Vorfaktor 1/(1 – (1 – α) pn) ≥ 1 und signalisiert damit erst einmal eine Verschlechterung des neuen cpi-Wertes. Diese kann nur durch die Subtraktion in der Klammer kompensiert werden.

8

2 Einfache Leistungsmaße

Diese Formel können wir jetzt benutzen, um Änderungen im Instruktionsumfang abzuschätzen.

B2 In der Beispielmaschine von B1 wird pALU um die Hälfte auf 0,2 reduziert, wie ändert sich cpi?

pALU = 2/5; p’ALU = 1/5 d.h α = 1/2 cpi’ =

1 9 1 2 5 8 ( − (1 − ) * *1) = * = 2 1 2 5 2 5 4 5 1 − (1 − ) * 2 5

Dieses Beispiel zeigt, dass eine an sich positive Maßnahme sogar einen schlechten cpi-Wert zur Folge haben kann. Dies ist aber klar, weil die größeren Werte (cpiLS = 2, cpiJMP = 3) stärker gewichtet werden. Reduzieren wir etwa in der Gruppe der Sprungbefehle um die Hälfte (0,2 Æ 1 9 1 1 10 15 5 * ( − (1 − ) * * 3) = * = und die Ver0,1), folgt cpi = 1 1 5 2 5 9 10 3 1 - (1 - ) * 2 5 besserung beträgt immer hin ca. 8%.

Der andere Parametertyp, den man verändern kann, ist cpik von einzelnen Gruppen, ohne dass der Umfang der Maschineninstruktionen verändert wird. Im Prinzip bedeutet dies eine Architekturänderung im Leitwerk (μ-Programm). Wir greifen wieder die n-te Gruppe heraus und reduzieren über cpin’ = α*cpin, 0 ≤ α ≤ 1: n −1

= ∑ p k * cpi k + p n * α * cpi n

k =1 n −1

= ∑ p k * cpi k + p n * cpi n − p n * cpi n + p n * α * cpi n

k =1   cpi

= cpi- (1- α)*pn*cpin Hier fehlt der vergrößernde Faktor 1/(1 – (1 – α) pn), sodass deutlich höhere Chancen bestehen, den cpi-Wert mit dieser Maßnahme zu verkleinern.

2.1 Takt, CPI und Ablaufzeit

9

B2’ Wir setzen die Situation wie in B1 und B2 voraus, schaffen es durch eine Änderung des Mikroprogramms, den Wert von cpiJMP von 3 auf 1,5 zu reduzieren. Dann folgt

cpi = cpi ALU * p ALU * cpi LS * p LS + cpi JMP * p JMP = 1 * 0,4 + 2 * 0,4 + 1,5 * 0,2 = 1,5 Dies bedeutet eine 20-prozentige Verbesserung und liegt damit deutlich über den Anstrengungen von B2!

Das dritte Beispiel zu der cpi-Thematik ist etwas ausführlicher und diskutiert auch die Abhängigkeit der Ablaufzeit.

B3 In zwei Maschinen A und B braucht die Verzweigung zwei Zyklen und alle anderen Befehle einen Zyklus. In der auszumessenden Last sind 20% Verzweigungen. Die Taktzeit (Basiszeit) von A ist 25% günstiger als die von B. Welche Maschine ist hinsichtlich dieses Benchmarks günstiger, wenn ein optimierender Compiler 20% der Instruktionen auf B in der Gruppe der Einzyklusbefehle einspart?

zcpuA

= #lastA * cpiA * bzeitA

cpiA

= 2 * pJMP + 1 * pRest = 2*0,2 + 1*0,8 = 1,2 =

6 6 => zcpuA= * #lastA * bzeitA 5 5

Für die Maschine B schließen wir analog zcpuB = #lastB * cpiB * bzeitB cpiB bzeitB =

= 2 * pJMP + 1 * pRest = 1,2 =

6 5

5 * bzeitA nach Voraussetzung 4

10

2 Einfache Leistungsmaße

Damit folgt ohne optimierenden Compiler (#lastB = #lastA): 6 5 5 )* #lastB* ( ) * bzeitB= ( ) zcpuA 5 4 4 Der Gewinn (Speed-Up) Sp(B/A) = (zcpuB/zcpuA) berechnet sich zu 5/4, d. h. die Maschine B ist um 25% langsamer.

zcpuB = (

Der Einsatz des optimierenden Compilers bringt #lastB = 0,8 * lastA, allerdings muss cpiB neu berechnet werden. Wie in B2 folgt cpi'B =

1 ⎛6 ⎞ 5 ⎜ − 0,2 *1⎟ = 1 − 0,2 ⎝ 5 ⎠ 4

5 5 ) * ( ) bzeitA 4 4 5 5 4 = ( ) * ( ) * ( ) * #lastA * bzeitA 5 4 4

zcpuB = 0,8 #lastA * (

Damit können wir wie oben die Rechner A und B vergleichen: ⎛5⎞ ⎜ ⎟ * # last A * bzeit A zcpu B ⎝ 4 ⎠ 25 = = >1 Sp(B/A)= zcpu A ⎛ 6 ⎞ 24 ⎜ ⎟ * # last A * bzeit A ⎝5⎠

Rechner B wird also um ca. 5% langsamer sein, obwohl er 20% weniger Instruktionen verarbeiten muss. Konzentriert man sich statt der eben diskutierten Maßnahme auf eine 20%ige Verbesserung von cpiREST, dann resultiert ein neuer cpiB-Wert von 26/25. Der Instruktionsumfang bleibt gleich, sodass ein Vergleich der zcpu-Zeiten 13/12 ergibt, d. h. die Maschine ist um 8% langsamer.

2.2 Durchsatz, MIPS und MFLOPs Unter dem Aspekt, die Leistung direkt aus der Taktzeit und der Anzahl der Takte pro Instruktionen zu erschließen und das physikalische Leistungsmaß „Arbeit pro Zeiteinheit“ möglichst gut abzubilden, sind zwei Begriffe entwickelt worden, die

2.2 Durchsatz, MIPS und MFLOPs

11

ein gewisses Renommee erworben haben und damit etwas eingehender diskutiert werden sollen. Das eine Maß ist MIPS (Millionen Instruktionen Pro Sekunde) und das heißt, wenn man ein Programm als mögliche Last vorgibt (#last ist die Zahl der Instruktionen), dann folgt: MIPS=

=

# last *10 −6 zcpu # last *10 − 6 # last * cpi * bzeit

10 −6 takt = *10 −6 1 cpi cpi * takt takt = *10 − 6 cpi =

Dies sieht als Leistungsmaß sehr vernünftig aus, es wächst mit dem Takt (der Taktrate) und fällt mit der Komplexität der Architektur – dann nämlich, wenn ich im Mittel immer mehr Takte für einen Maschinenbefehl verbrauche (z. B. CISCMaschinen). Von Hennessy & Patterson [6] werden eine Reihe von Einwänden gegenüber diesem Maß angeführt, die wichtigsten sind: • MIPS ist abhängig von der Menge der Instruktionen, also der Architektur. • MIPS ist extrem lastabhängig. • MIPS kann invers zur gemessenen Leistung sein. Während die beiden ersten Punkte eigentlich nur eine Reflexion des Standardproblems beim Benchmarking darstellen, muss der dritte Punkt wesentlich ernster genommen werden. Betrachten wir Gleitkommaoperationen, diese können in Hardware oder Software realisiert sein. Nehmen wir zunächst die Hardware-Variante; im Allgemeinen bedeuten sie ein komplexeres Mikroprogramm, d. h. der Wert von cpi wird größer und damit MIPS kleiner – obwohl die Ausführungszeit sinkt. Bei der Software-Variante werden einfache Instruktionen mit kleinerem cpi verwendet, dieses bewirkt ein Anwachsen von MIPS – obwohl die Ausführungszeit zcpu ansteigt.

12

2 Einfache Leistungsmaße

B4 Wir greifen auf unsere RISC-Maschine von Beispiel B1 zurück, unterstellen eine Taktrate von 1 GHz = takt. Der Einsatz eines optimierenden Compilers bringt eine 50-prozentige Reduktion der ALU-Operationen. Man berechne den Effekt auf MIPS und Ablaufzeit!

cpinormal

= 1,8

MIPSnormal

=

takt 1*10 9 *10 − 6 = *10 − 6 1,8 cpi normal

=

1000 10000 5000 = = 1,8 18 9

0,4 ) *1 + 0,4 * 2 + 0,2 * 3 = 2 1 − (0,4 / 2) 0,2 + 0,8 + 0,6 1,6 = = =2 0,8 0,8 (

cpiopt

MIPSopt

=

takt 1 *109 1000 *10 − 6 = *10 − 6 = = 500 cpi opt 2 2

MIPSopt MIPSnormal

=

500 1 9 =1− = 500 10 10 1 1− 10

Die optimierte Version hat also eine um 10% kleinere MIPS-Rate! Wie sieht es bei den Ausführungszeiten aus? zcpunormal = #last * cpinormal * bzeit [sec] = #last * 1,8 * 1,0 * 10–9 = 1,8 * 10–9 * #last [sec] zcpuopt

= 0,8 * #last * cpiopt * bzeit = 0,8 * #last * 2 * 1 * 10–9= 1,6 * 10–9 * #last [sec]

D. h. obwohl die optimierende Version mehr als 10% schneller läuft, hat sie eine kleinere MIPS-Rate → Widerspruch im Leistungsmaß!

2.2 Durchsatz, MIPS und MFLOPs

13

Das zweite populäre Maß, welches eingeführt wurde, um die Leistungsfähigkeit von Maschinen zu beurteilen, ist MFLOPS (Million Floating Point Operations per Second) und in ähnlicher Weise wie MIPS definiert: MFLOPS =

# FLOPS *10− 6 zcpu

Es hängt jedoch noch weit mehr als MIPS von der Hardware und dem Anwendungsprogramm ab. Enthält dies keine oder wenig Gleitkommaoperationen (FLOPS), so wird die gemessene Leistung ziemlich irrelevant sein. Es wird mit MFLOPS/GFLOPS/TFLOPS halt nur eine einzige Komponente eines Rechnersystems ausgemessen und hinsichtlich dieser kann man die Leistung vergleichen. Für wissenschaftliche Anwendungen mit stark numerischem Charakter, z. B. aus der Flüssigkeits- und Gasdynamik der Theoretischen Chemie und Theoretischen Physik, der Astronomie und der Gentechnik, sind TFLOPS allerdings ein geeignetes Maß. Standard-Last ist der sogenannte Linpack-Benchmark, ein Paket zur Lösung linearer Gleichungssysteme, welches von Jack Dongarra/Knoxville-Tennessee geschrieben wurde. Es erlaubt nicht nur die maximale Leistung Rmax, sondern auch die Leistung Nmax bei der halben Problemgröße (Matrixdimension) zu messen; die Implementierung muss so erfolgen, dass die Zahl der Gleitkommaoperationen sich wie (2/3) n3 + 0 (n2) verhält. Wir führen einige Beispiele aus der Liste von November 2004 an:

1.

IBM BlueGene/L (32768 * PowerPC)

70,72 TFLOPS

2.

SGI Columbia (10160 * SGI Altix)

51,87 TFLOPS

3.

NEC Earth Simulator (5120 * NEC)

35,86 TFLOPS

10.

NCSA Tungsten (2500 * Dell PowerEdge/Xeon)

9,819 TFLOPS

85.

MPI Garching (822 * IBM p Serie 690 Turbo)

2,198 TFLOPS

168.

Hitachi Leibniz-RZ München (168 * Hitachi)

1,653 TFLOPS

Um unter die Top 10 zu kommen, brauchte eine Installation zu diesem Zeitpunkt mehr als 3 TERAFLOPS = 3*1012 Gleitkommaoperationen pro Sekunde. Im Frühsommer 2008 waren ca. neun TFLOPS nötig, um überhaupt in die Liste zu kommen, und das IBM-Roadrunner-System durchbrach die Peta-FLOP-Schranke.

14

2 Einfache Leistungsmaße

FLOPS

Man muss sich aber stets vor Augen halten, dass dies kein allgemeingültiges Leistungsmaß darstellt – die Gründe sind ähnlich wie bei MIPS gelagert. Abbildung 2.1 zeigt die MFLOP-Raten der jeweils leistungsfähigsten Gleitkommamaschinen (auch Supercomputer genannt) im Zeitraum 1982–2002. Man beachte den logarithmischen Maßstab auf der vertikalen Achse und somit den Technologiesprung um drei Zehnerpotenzen in einer Dekade.

1,E+13

NEC (Earth Simulator)

1,E+12 1,E+11

CLUSTER

1,E+10 1,E+09 1,E+08 1,E+07 1,E+06

CM 5 TMC (60 GFLOPS)

Cray 1 Cyber 205

1982

1992

2002

Abb. 2.1 Leistungsentwicklung von Supercomputern

Ohne auf Einzelheiten einzugehen, widerspiegelt diese Entwicklung auch die Veränderung von einer monolithischen klassischen Architektur wie die Cray 1 oder Cyber 205 über die einheitliche Vernetzung einer großen Zahl identischer Prozessoren wie in der CM 5 von Thinking Machines bis hin zur aktuellen Clusterung kompletter Systeme wie bei NEC Earth Simulator oder IBM SP2 Power3 in Livermore (über 6000 Knoten). Damit einher geht auch eine Veränderung in der Herstellerlandschaft. Waren es zu Beginn der 1980er-Jahre noch Konstrukteure, die aus dem Großrechnerbereich kamen, änderte sich dies zu Beginn der 1990er fundamental. Eine Reihe junger innovativer Firmen und Designer erschien auf der Bühne und löste mit neuen Architekturkonzepten einen Leistungsboom aus. Viele von diesen sind Ende der Dekade schon wieder verschwunden; durchgesetzt hat sich das Cluster-Prinzip, nach dem eine große Anzahl konventioneller Billigprozessoren oder Standardsysteme (dazu zählt auch der α-Prozessor von DEC, später Compaq bzw. hp) durch ein Hochleistungsnetz verbunden wird. Einen sehr schönen Überblick der Szene gibt die www.top500.org

Website, welche zweimal jährlich die 500 leistungsfähigsten Maschinen listet und vergleicht – wie bereits erwähnt auf der Basis des Linpack-Benchmarks.

3 Die Gesetze von Amdahl und Gustafson

Die Diskussion um das Leistungsmaß MIPS bzw. MFLOPS/TFLOPS sollte aufgezeigt haben, wie schwer es ist, aus der Leistung einer Komponente auf die Leistung des Gesamtsystems zu schließen.

3.1 Das Gesetz von G. Amdahl Sehr nützlich ist in diesem Zusammenhang das Gesetz von Amdahl (Gene Amdahl, Konstrukteur der IBM360-Serie und Gründer einer erfolgreichen Großrechnerfirma 1970–90), das auf einem sehr allgemeinen Niveau entsprechende Rückschlüsse erlaubt. Dazu zerlegen wir die Ablaufzeit zcpu einer Last in zwei Anteile (s. Abb. 3.1).

zcpu (I) tn

ta

tn

t’a (II) zcpu’

Abb. 3.1 Ableitung des Amdahl’schen Gesetzes

In der Zeitspanne ta soll eine spezielle Komponente genutzt werden, z. B. eine Gleitkommaeinheit, die durch den Einsatz einer Beschleunigung oder Verbesserung zu einer Verkürzung auf die neue Zeitspanne t’a < ta führt. Dies entspricht

16

3 Die Gesetze von Amdahl und Gustafson

einem Übergang vom oberen Diagramm (I) zum unteren (II) und hat natürlich eine neue Ablaufzeit zcpu’ zur Folge. Die Berechnung von zcpu’ beruht auf folgenden Überlegungen: ta ist der prozentuale Zeitanteil von zcpu, in welchem die Verbesserung tn + ta genutzt werden kann ta ist der prozentuale Normalnutzungsanteil • 1− tn + ta

•

• es gilt zcpu = t n + t a trivialerweise • die technische Verbesserung der entsprechenden Komponente entspricht einer Beschleunigung b der Verarbeitung, dies entspricht einer zeitlichen Verkürzung t’a = ta / b t • zcpu' = t n + t 'a = t n + a b • alles zusammen ergibt tn + ta 1 zcpu t n + t a = = = t t t 1 ta zcpu ' a t n + ta − ta + a 1− tn + a + tn + ta b tn + ta b b

Wir definieren mit a = ta/(tn + ta) den prozentualen Anteil der ursprünglichen Ablaufzeit, in dem die Verbesserung stattfinden kann, und erhalten dann mit zcpu 1 = ≥1 zcpu' 1 − a + a b

das berühmte Amdahl’sche Gesetz. Der Quotient (zcpu/zcpu’) heißt üblicherweise Speed-Up und hat für b ≥ 1 (eine Verbesserung findet statt) und a ≤ 1 (der Zeitrahmen ist nicht größer als die ursprüngliche Ablaufzeit) den Wert ≥ 1. B1 Ein Programm kann in 40% seiner Laufzeit eine Gleitkommaeinheit nutzen, die eine Beschleunigung um den Faktor b = 8 bewirkt. Wie groß ist der Gewinn/Speed-Up des ganzen Programms?

40% der Laufzeit bedeutet a = 0,4.

3.1 Das Gesetz von G. Amdahl

Speed-Up =

1 a 1− a + b

=

1 0,4 1 − 0,4 + 8

=

17

20 21 3 ≈ ≈ 13 14 2

Das bedeutet, die achtfache Beschleunigung wirkt sich lediglich in einer 50%igen Verminderung der Ablaufzeit aus.

Ein gutes Verständnis von Speed-Up und den bestimmenden Parametern a, b erhält man, wenn der Speed-Up gegen a bei festem b geplottet wird (s. Abb. 3.2).

4

b=4

3

b=3 b=2

2 1

b=1

0 1,0 0,5 Abb. 3.2 Speed-Up in Abhängigkeit von der Beschleunigung b

2,0 1,0

Man erkennt, dass bei kleinem a, also relativ kleinen Laufzeiten der Verbesserung, auch eine starke Beschleunigung b keinen relevanten Anstieg des GesamtSpeed-Ups zur Folge hat. Das Amdahl’sche Gesetz ist von fundamentaler Bedeutung für die Leistungsanalyse und wird uns noch in vielen Beispielen begegnen. Eine besonders relevante Rolle spielt es bei der Leistungsanalyse von Multiprozessorsystemen. Eine der direktesten und einfachsten Anwendungen des Amdahl’schen Gesetzes besteht in der Abschätzung der Leistungsfähigkeit eines Cache-Systems. Der Speicher benötige die Zeit tM zum Laden der Operationen, der Cache ist n-mal schneller tC = tM/n, wobei n > 1: 0

tM a*tM

18

3 Die Gesetze von Amdahl und Gustafson

a*tM ist das nutzbare Zeitintervall für den Cache, a < 1. Nach Amdahl können wir den Speed-Up S direkt angeben S=

1 (1 − a ) +

a n

welcher im Idealfall a = 1 (alles im Cache) in den maximalen Speed-Up Smax = n übergeht. Für a = 1/2, d. h. in der Hälfte der Zeit kann auf den Cache zugegriffen werden, folgt ⎛ 1⎞ ≤ 2 ⎜1 − ⎟ ⎛ 1⎞ ⎝ n⎠ ⎜1 + ⎟ ⎝ n⎠ und somit erreicht man noch nicht einmal eine Verdopplung der Leistung, obwohl der Cache beliebig schnell sein kann. S=

2

3.2 Amdahl und das Vektor-Pipeline-Prinzip Eine weitere Leistungsabschätzung nach Amdahl erhält man sehr transparent für das Daten- oder Vektor-Pipeline-Prinzip. Sollen z. B. für i = 1...n die Additionen ai + bi durchgeführt werden, wobei ai und bi Gleitkommazahlen, z. B. des Typs 1,2345*10–4, sind, dann setzt sich ai + bi aus vier Basisoperationen zusammen. c lade ai, bi

d normalisiere ai, bi

=>

addiere ai, bi, r e

=>

speichere r f

Dies entspricht einem cpi-Wert von 4. Lässt man jedoch die Phasen 1–4 überlappen nach dem in Abb. 3.3 dargestellten Schema,

c (lade)

1

d (norm) e (add) f (sp)

0

2

3

4

5

1

2

3

4

1

2

3

1

2

tF

Abb. 3.3 Pipeline-Prinzip und Anlauf-/Füllphase

t

3.2 Amdahl und das Vektor-Pipeline-Prinzip

19

so erhält man nach der Füllphase t > tF bei jedem Takt ein Ergebnis (d. h. cpi – pip ~ 1). Die benötigten Zeiten für beide Arbeitsweisen tunpip bzw. tpip sind leicht abzuschätzen tpip

~ 4*bzeitpip+(n – 1)*bzeitpip

tunpip

~ n*4*bzeitpip

wobei n die Anzahl der zu addierenden Zahlen und bzeitpip die Taktzeit darstellt. Für ihr Verhältnis gilt t unpip 4 * n 4 = = t pip n + 3 1+ 3 n und wenn n >> 3, kann man maximal eine Beschleunigung um den Faktor 4 erreichen. Im Folgenden wollen wir diese Überlegungen am Beispiel verallgemeinern und einige wichtige, gebräuchliche Begriffe einführen, bevor wir dann das Amdahl’sche Gesetz anwenden. Der Pipeline-Durchsatz D ergibt sich zu n/tv (Arbeit pro Zeit), wobei tV = tF + n*bzeitpip D(n) =

n 1 = * t F + n * bzeit pip bzeit pip

1 tF 1+ n * bzeit pip

Haben wir sehr oft die Pipeline-Operation durchzuführen, gilt n ∞ und somit Dasympt = lim D(n ) = n →∞

1 = takt pip bzeit pip

d. h. der Pipeline-Takt ist der maximal erreichbare Durchsatz. Es folgt damit: D(n ) = Dasympt

1 1 tF 1+ * n bzeit pip

Kleinere Vektorlängen verringern die Leistung. Die Abhängigkeit des PipelineDurchsatzes (der Leistung) von Technologie und Architektur (Organisation) wird transparenter, wenn n1/2 eingeführt wird. Dies ist die Vektorlänge, bei welcher der halbe asymptotische Durchsatz 0,5*Dasympt erreicht wird:

20

3 Die Gesetze von Amdahl und Gustafson

D(n1/2 ) = (1/2)Dasympt = Dasympt

1 1 tF 1+ * n bzeit pip

Auflösen ergibt n1/2 = tF/bzeitpip = taktpip*tF und damit

D(n ) = Dasympt

Technologie

*

1 n 1 + 1/ 2 n Architektur

Obwohl diese Form sehr transparent die Abhängigkeit von den beiden Faktoren Technologie (takt) und Architektur/Organisation (n1/2) wiedergibt, ist sie mit außerordentlicher Vorsicht zu behandeln. Der Grund dafür liegt darin, dass sie nur für eine einzelne Pipeline-Operation auf Maschinenebene gilt, wobei die Daten aus den Registern kommen und wieder dorthin gespeichert werden. Im Fall verketteter Pipelines, z. B. LOAD-Pipe

COMPUTE-Pipe

STORE-Pipe

sieht das schon ganz anders aus, zumal dann die Speicherverzögerung (latency) eine erhebliche Rolle spielt. Ähnlich muss man im Fall von Algorithmen vorgehen, denn nur dann kann man die zum Teil sehr hohen n1/2-Messwerte bei manchen Parallel- und Vektormaschinen verstehen (www.top500.org). Wie erwähnt sind dies Messwerte, ihrer Bestimmung liegt folgende Argumentation zugrunde: Die Taktfrequenz taktpip = Dasympt als maximal möglicher Durchsatz wird in der Praxis meist nicht einmal annähernd erreicht und das Leistungs(Durchsatz)-Verhalten in Abhängigkeit von der Vektorlänge n hat folgendes Verhalten (s. Abb. 3.4), D(n)

Dasympt

Dmax 1

0 1,0

2,0

3,0

Abb. 3.4 Durchsatzverlauf D(n) und Vektorlänge n

4,0

n5,0 max

6,0n

3.2 Amdahl und das Vektor-Pipeline-Prinzip

21

d. h. zwischen Dasympt und D(nmax) = Dmax besteht eine erhebliche Differenz. Wir ersetzen daher Dasympt durch Dmax und bestimmen n1/2 über ⎛D ⎞ n1/2 ≈ n ⎜⎜ max − 1⎟⎟ ⎝ D(n) ⎠

für n < nmax. Das folgende Beispiel reicht zwar fast in die Steinzeit der Datenverarbeitung zurück, hat aber den Vorteil der Einfachheit [7]. B2 Die Cray-1 und Cyber205 waren die ersten erfolgreichen Vektorrechner zu Beginn der 80er Jahre des letzten Jahrhunderts mit folgenden Leistungsdaten der Additionspipelines: bzeitpip Dasympt D(n=10) D(n=100) D(n=1000) n1/2 n1/2 n1/2 (sec) (Mflops) = Dmax (n=10) (n=100) (exakt) Cray-1

12,5 10–9

80

6

19

23

30

20

21

Cyber205 20,0 10–9

50

9

33

48

40

45

52

n1/2 (n = 10, 100) wurde über die obige Näherungsformel bestimmt.

Als grundsätzliche Regel können wir festhalten, dass n >> n1/2 eine effiziente Nutzung der Vektorpipeline gestattet, aber für n > nmax, D(n = nmax) = Dmax, keine Durchsatzsteigerung mehr möglich ist. Die bisherigen Analysen bezogen sich auf die Leistung einer einzelnen Pipeline, in der Realität müssen wir jedoch die Einbettung in das ganze DV-System betrachten und hier kommt das Gesetz von Amdahl ins Spiel. Denn ein gewisser Anteil der zu verarbeitenden Daten wird nicht durch die Pipeline geschleust werden können – dies ist der sogenannte skalare Anteil. Die Gesamtzeit t, welche eine Anwendung im Gesamtsystem verbringt, wird sich daher in einen skalaren Anteil tS und eine Pipeline tpip aufteilen. Wir setzen tpip = α*tv mit 0 ≤ α ≤ 1 und wollen annehmen, dass tpip die Pipeline-Durchlaufzeit ohne Einschalten des PipelineMechanismus darstellt. Die Einschaltung bewirkt eine Verkürzung auf t'pip =

t pip b

=

αt v b

22

3 Die Gesetze von Amdahl und Gustafson

wobei b ≥ 1 die Beschleunigung ist. Damit haben wir die Situation à la Amdahl

tV tS

tpip

tS

t’pip

und für den Speed-Up gilt S=

t S + t pip t S + t ' pip

=

tV

αt (1 − α ) t V + V b

=

1 (1 − α) +

α b

ein bereits ausführlich diskutiertes Ergebnis (s. Abb. 3.3).

3.3 Das skalierte Gesetz von Gustafson Nun sind Durchlauf/Verweilzeiten keine eigentlichen Leistungsgrößen, im Sinne unserer Diskussion zu Beginn dieses Kapitels sind dies Durchsätze. Ist nS der skalare Datenanteil und npip der entsprechende Pipeline-Beitrag, so ist der Durchsatz des Gesamtsystems ohne eingeschaltete Pipeline DS = (nS + npip) / (tS + tpip). Der Durchsatz D bei aktiver Pipeline, die eine Zeitverkürzung um den Faktor (1/b) bewirkt, ist D = (nS + npip) / (tS + tpip/b). Der Speed-Up im Sinne des Gesetzes von Amdahl ergibt sich als Quotient S A (α ) =

D DS

=

t S + t pip t S + t pip / b

=

tV

αt (1 − α) t V + V b

=

1 (1 − α) +

α b

und reproduziert unser Resultat der Zeitanalysen. Durch das nichtlineare Verhalten des Speed-Ups mit dem Vektorisierungsgrad α wird eine schlechte Skalierung in dieser Variablen impliziert, deshalb ist von Gustafson eine Modifikation vorgeschlagen worden. Deren Basisidee besteht darin, nicht die Zeit t’pip = tpip/b bei Verwendung der Pipeline zu skalieren, sondern die Gesamtzeit tV = tS + tpip konstant zu lassen und das Problem zu skalieren n’pip = b*npip. Für den Durchsatz des Gesamtsystems folgt dann:

3.3 Das skalierte Gesetz von Gustafson

D=

n S + n 'pip tV

=

23

n S + b * n pip tV

Vor dem Einschalten der Pipeline ist der Durchsatz D unpip =

n S + n pip tV

und damit tV = (nS + npip)/Dunpip. Da tV als Gesamtverweilzeit konstant ist, kann D bei funktionierender Pipeline umgeschrieben werden D=

n S + b * n pip n S + b * n pip n pip ⎞ ⎛n ⎟ = D unpip = D unpip ⎜⎜ S + b n S + n pip n n ⎟⎠ ⎝ n D unpip

Mit npip/n = β und nS/n = 1 – β ergibt sich somit SG(β) = D/Dunpip = (1 – β) + b*β = 1 + (b – 1)*β. Dieser Speed-Up SG(β) ist eine lineare Funktion von β und stellt somit den Idealfall einer Skalierung dar (s. Abb. 3.5).

4 b=4

3

SG(β)

2

SA(α) b=2

1

b=1

0 0,5 1,0 Abb. 3.5 Speed-Up nach Amdahl SA(α) und Gustafson SG(β)

2,01,0

Im ersten Moment kann man den Eindruck gewinnen, dass durch eine kleine mathematische Spielerei ein völlig anderes Skalierungsverhalten folgt, ohne dass sich an dem zu untersuchenden System etwas geändert hat. Eine genauere Analyse, welche allerdings den Rahmen unserer Betrachtungen sprengt, zeigt, dass sich dahinter ein Wechsel des Anwendungs-/Programmiermodells verbirgt. Wir werden an einer späteren Stelle, bei der Diskussion des Verhältnisses von Modell und Realität noch einmal auf beide Gesetze zurückkommen.

24

3 Die Gesetze von Amdahl und Gustafson

3.4 Befehlsverarbeitung nach dem Pipeline-Prinzip Das Pipeline-Prinzip zur Ausführung von Vektoroperationen kann ebenfalls auf die Verarbeitung von Befehlen übertragen werden. So könnte etwa die normale Abarbeitung von add a, b, r in folgende Teil/Mikro-Befehle aufgelöst werden: →

add a, b, r

lade dek add lade a, b exec add store r

und diese würden fünf Maschinenzyklen/Takte benötigen. Nach dem PipelineKonzept würde man folgendermaßen vorgehen (s. Abb. 3.6),

lade

1

dek

2

3

4

5

6

1

2

3

4

5

1

2

3

4

1

2

3

lade exec store

1 1

2

3

4

2 5

Takt 6

Abb. 3.6 Taktschema beim Befehl-Pipelining

d. h., nach einer Füllphase wird in jedem Takt ein Befehl fertig. Natürlich setzt dies eine sehr homogene Befehlsstruktur voraus – eine Gleichförmigkeit wie bei den Data-Pipelines wird man jedoch nie erreichen, Verzweigungen und Sprungbefehle sind die Hauptursachen dafür. Die Abschätzung der Leistungsfähigkeit des Pipeline-Konzepts erhält man durch einen direkten Vergleich der Ablaufzeiten: zcpu = #instr *cpi * bzeit:

S=

# instr * cpi unpipe * bzeit unpipe # instr * cpi pipe * bzeit pipe

=

cpi unpipe cpi pipe

*

bzeit unpipe bzeit pipe

Mit der Annahme gleicher Taktzeiten, bzeitunpipe = bzeitpipe, reduziert sich der Beschleunigungsfaktor auf S = cpiunpipe/cpipipe. Wir folgen jetzt der Argumentation von Patterson & Hennessy [6]: cpipipe = 1 im Idealfall, denn nach der Füllphase folgt in jedem Takt ein abgearbeiteter Befehl

3.4 Befehlsverarbeitung nach dem Pipeline-Prinzip

25

cpiunpipe = #pstufen, denn die Zahl der PipelineStufen bestimmt auch die Taktanzahl im normalen Betriebsmodus S ≤ #pstufen Natürlich ist der Idealfall, cpi = 1, doch sehr realitätsfern, sodass wir eine Korrektur anbringen, deren Grundkonzeption im Folgenden skizziert wird. Eine der Ursachen für die notwendige Korrektur liegt in der Existenz von auftretenden Speicherkonflikten. Diese können durch die Hardware-Architektur bedingt sein, so z. B., wenn nur ein Speicherzugang vorhanden ist (1-memory-port). Dann haben wir im Takt 3 von Abb. 3.7 einen doppelten Zugriff lade(instruktion) und lade(daten), der aufgelöst werden muss. Standard ist hier inzwischen die eigentliche Trennung von Daten- und Instruktionspfaden, also eine Änderung der Hardware. Dies alleine ist natürlich keine Garantie für eine Konfliktfreiheit, da auch Sprung- und Verzweigungsbefehle den Pipeline-Modus (Betrieb) unterbrechen können. Im Prinzip sind dies Situationen, in denen sich der Programmzähler um einen von 1 verschiedenen Wert ändert. Ähnlich verhält es sich in den Fällen, bei denen zur Ausführung einer Operation ein Wert benötigt wird, der noch nicht zur Verfügung steht. Hier findet die Lösung standardmäßig auf der Compilerebene durch das Einfügen von Leerzyklen statt, um so den effizienteren Pipeline-Betrieb aufrecht zu erhalten. Zur Verdeutlichung dieser Technik betrachten wir ein kleines Beispiel in Abb. 3.7.

Op1(R1, R2) →R3 lade(Op1) dek(Op1) lade(R1, R2) ex(Op1) Op2(R3, R5) →R4 lade(Op2) dek(Op2) lade(R3, R5) ex(Op2)

store(R3) store(R4)

Konflikt, da R3 noch nicht verfügbar! Auflösen durch Leerzyklen lz

lade(Op2)

dek(Op2)

lz1

lz2

lade(R3,R5)

Abb. 3.7 Konfliktlösung in einer Pipeline durch Leerzyklen

Eine detaillierte Diskussion der sehr ausgefeilten Technik würde den Rahmen der Leistungsanalyse bei Weitem überschreiten, es wird daher z. B. auf das entsprechende Kapitel „Computer Architecture“ von Patterson & Hennessy [6] verwiesen. Im Grunde läuft es dabei darauf hinaus, Pipeline-Unterbrechungen (stalls) durch Einführung von Leerzyklen zu vermeiden.

26

3 Die Gesetze von Amdahl und Gustafson

Für die Analyse der Leistung heißt dies den idealen Wert von cpipipe = 1 durch 1 + corr zu ersetzen und den Wert von corr abzuschätzen. Am einfachsten geht dies über den Ansatz n

corr =

∑ p * lz i

i

i =1

wobei pi das Gewicht der Befehlsgruppe i = 1…n und lzi die Anzahl von benötigten Leerzyklen in dieser Gruppe darstellt. Die Korrektur ist damit nichts anderes als die mittlere Anzahl von Leerzyklen über alle Befehlsgruppen einer Anwendung. Damit ergibt sich der Speed-Up S zu S≤

# pstufen 1+ < lz >

Diese Korrektur lz, der Leer/(stall)-Zyklen kann beträchtliche Auswirkungen auf die Leistungsfähigkeit des Pipeline-Konzepts haben und es sogar unwirksam werden lassen. Dies unterscheidet es erheblich vom Daten-Pipelining.

3.5 Zusammenfassung Damit sind eigentlich die wichtigsten Basisbegriffe und Zusammenhänge für eine transparente Leistungsanalyse skizziert – wir fassen noch einmal zusammen und favorisieren in diesem Rahmen ein Schichtenmodell:

• das Amdahl’sche Gesetz zur globalen Leistungsvorhersage bei Verbesserung einzelner Komponenten, • die MFLOP-TFLOP-Rate zur Messung der numerischen Leistungsfähigkeit, • die MIPS-Rate zur anwendungsorientierten Messung auf der Basis von Maschineninstruktionen, • der cpi-Wert als Ausdruck der Befehlsstruktur und Verarbeitung, • die Taktrate oder Basiszeit als hardwareorientiertes Technologiemaß. Die Voraussetzung für diese fünf Schichten ist eine Last, die aus einem einzelnen Programm als Repräsentanz der zugrunde liegenden Maschineninstruktionen besteht. Man misst die Ablaufzeit dieses Programms und analysiert diese mithilfe der beschriebenen Zusammenhänge.

4 Die Gesetze von Little

In den Vorbemerkungen haben wir schon die Problematik angeschnitten, dass bei vielen Systemen die Messung einer einzigen Last keine vernünftige Leistungsanalyse zulässt. Es handelt sich dabei z. B. um Client-Server-Systeme, um den IPVerkehr über Router und Switches sowie um die Dialog- und Batch-Verarbeitung.

4.1 Voraussetzungen In allen diesen Fällen besteht die reale Last aus einer Menge in etwa ähnlicher Teillasten, z. B. DB-Transaktionen, Client-Anforderungen von Remote-Procedure-Calls (rpc), Datenpaketen vom TCP/IP-Typ oder Benutzerkommandos auf Windows- oder Linux-Servern. Zu der Schwierigkeit, diese Lastmenge zu beschreiben, kommt die Komplikation des zeitlichen Bezugs, wir versuchen dies, durch folgende Annahmen in den Griff zu bekommen. Das Black-Box-Modell von Abb. 1.1 aus Kap. 1 hat sich in der Diskussion von Ablaufzeit zcpu und dem damit zusammenhängenden Amdahl’schen Gesetz bewährt – wir behalten es daher bei. Als Leistungsmaß werden wir aber nicht diese Größe, sondern den Durchsatz D, d. h. die Anzahl komplett erledigter Aufträge/Teillasten/Datenpakete pro Zeiteinheit, betrachten (s. Abb. 4.1).

28

4 Die Gesetze von Little

einlaufende Aufträge

I N P U T

Verarbeitung

O U T P U T

auslaufende Aufträge

taus

tein

t

Abb. 4.1 Zeitlicher Ablauf der Auftragsverarbeitung

Auf der Input-Seite können wir die Zahl der einlaufenden Aufträge #einlfd zum Zeitpunkt tein messen und die Ankunftsrate λ = #einlfd/Zeit[1/sec] bestimmen. Entsprechend ist auf der Output-Seite die Verarbeitungsrate μ = #auslfd/Zeit [1/sec] V

definiert. Die Verweilzeit t k eines Auftrags k ist durch die Differenz

t Vk = taus (k) – tein (k) festgelegt. V

Trägt man die Verweilzeiten t k =1...n gegen ihre Häufigkeiten hk auf – eventuell muss man Klassen nach dem Muster Klasse i:= {t k : ˆt i −1 ≤ t k ≤ ˆt i , # t k := h i } i = 1...m, m ≤ n, ˆt 0 = 0 ˆt 0...m wird so gewählt, dass die h i genügend groß werden. V

bilden – erhält man eine Verteilung der stochastischen Variablen t k (s. Abb. 4.2).

4.1 Voraussetzungen

29

h

 t1

t

 t3

 t2

Abb. 4.2 Histogrammbeispiel für die Verweilzeit

Das Attribut „stochastisch“ ist deshalb gerechtfertigt, weil für einen externen Beobachter, welcher die Struktur der einzelnen Aufträge nicht kennt, die unterschiedlichen Verweilzeiten ein Zufallsprodukt sein müssen. Über die Verteilung kann man den Mittel- oder Erwartungswert bilden < t v >=

1 n

n

∑t

V k

k =1

Natürlich kann er auch näherungsweise über die Verteilung der Häufigkeiten hi=1…m ausgedrückt werden: m

h=

∑

m

h i , < t v >≈

i =1

∑ i =1

(

  h i ti + ti −1 )( ) h 2

Der Einfachheit halber entscheiden wir uns für gleichmäßige Intervallklassen, es sind natürlich auch andere Auswahlen möglich. B1 An 10 TCP/IP-Datenpaketen wird die mittlere Verweilzeit in einem Router gemessen; es ergeben sich folgende Werte in msec: k

1

2

3

4

5

6

7

8

9

10

t Vk

4

6

14

14

10

4

8

18

12

10

30

4 Die Gesetze von Little

Der direkt berechnete Mittelwert ergibt sich zu 10

< t V >=

∑

1 tV k = 100 : 10 = 10 [msec] 10 k =1

Wir führen jetzt folgende Klassengrenzen ein i

1

2

3

4

 ti

0

8

16

24

hi

4

5

1

und erhalten daraus das Verteilungshistogramm 5

h

4 3 2 1 0 4

8

12

16

12

24

Der Mittelwert, den wir darüber berechnen stimmt nur näherungsweise mit dem exakten Wert überein, 1 5 4 * 4 + *12 + * 20 10 10 10 96 1 = [16 + 60 + 20] = = 9,6 10 10

< tH V >=

sodass entsprechend berechnete Größen immer mit einer gewissen Skepsis zu betrachten sind.

Der Aufwand der Klassenbildung und Häufigkeitsdarstellung wird durch eine größere Anschaulichkeit und Transparenz mehr als wettgemacht – statistische Ge-

4.2 Die Herleitung der Gesetze

31

setzmäßigkeiten sind auf diese Weise einfach leichter zu erkennen. Durch die Verteilung der Verweilzeiten wird klar, dass die Anzahl von Aufträgen oder Prozessen keine Konstante darstellt. Die zugrunde liegenden zeitlichen Abhängigkeiten sind aber sehr komplex, sodass dem Gedankengang von Little, die Zeitkomponente durch Mittelwertsbildungen zu ersetzen, eine besondere Bedeutung zukommt.

4.2 Die Herleitung der Gesetze Wir beginnen mit der einfachen Feststellung, dass sich, zusammen mit dem Wartepool der einlaufenden Aufträge, eine Anzahl n(t) von Prozessen zu einem Zeitpunkt t ≥ 0 im System befinden wird. Sieht man von Schwankungen zu Beginn des Messprozesses ab und beobachtet das System über sehr lange Zeit, so wird lim n (t ) = < k >

t →∞

eine zeitunabhängige Konstante, welche den Mittelwert der aktiven Aufträge darstellt. Die Verknüpfung zwischen diesen beiden Mittelwerten liefert das 1. Little’sche Gesetz λ * = < k > welches völlig unabhängig von einer besonderen Verteilung der Ankunftszeiten oder Bearbeitungszeiten ist. Einzige Voraussetzung ist die Existenz eines Gleichgewichts zwischen einlaufenden und auslaufenden Prozessen bei sehr großen Zeiten. Im Prinzip bedeutet dieses Gleichgewicht, dass kein Prozess/Auftrag verloren geht und dass auch kein neuer Prozess innerhalb der Black-Box entsteht. Die Begründung für dieses Gesetz soll hier aus den bekannten Gründen nur über Plausibilitätsargumente geliefert werden (s. Abb. 4.3): • im System kommen zum Zeitpunkt t a(t) Aufträge zur Verarbeitung an, f(t) erledigte Aufträge verlassen es; • die Zahl n(t) von Aufträgen, welche sich zum Zeitpunkt t im System befinden, ist n(t) = a(t) – f(t); tM

• wir beobachten das System im Zeitintervall [0, tM], dann ist SA ( t M ) =

∫ n(t)dt 0

die Summe aller Auftragsverweilzeiten im System bis zum Zeitpunkt tM; • beziehen wir SA(tM) auf das Messintervall [0, tM], dann stellt = SA(tM)/tM die mittlere Anzahl von Aufträgen im System dar;

32

4 Die Gesetze von Little

5

n

4

3

2

SA(tM)

a(t)

f(t)

1

t

0 t1

t2

t1

t2 t3 t3

t1’ t1't2’

t2'

t3’t3'

tM

Abb. 4.3 Herleitung des Little’schen Gesetzes

• ist tk der Ankunftszeitpunkt des k-ten Auftrags, tk’ der Zeitpunkt seiner Beendigung, dann ist tV(k) = tk’ – tk seine Verweilzeit; • SA(tM) ist nichts anderes als die Fläche zwischen Ankunfts- und Fertigstellungskurve, also m

SA ( t M ) = 1 * ( t1 '− t1 ) + 1* ( t 2 '− t 2 ) + 1 * ( t 3 '− t 3 ) + ... + 1 * ( t m '− t m ) =

∑t

V (k )

k =1

wobei m für die Gesamtzahl der Ankünfte in [0, tM] steht; • wir dividieren durch tM m

SA ( t M ) / t M = (1 / t M )

∑ k =1

t v (k ) =

m 1 * tM m

m

∑t k =1

v (k )

=

m * < tv > tM

• da = SA(tM)/tM und λ = (m/tM) die Ankunftsrate, folgt = λ*. Wie bereits anfangs erwähnt ist diese Ableitung weit von den üblichen mathematischen Standards entfernt, aber ein wichtiger Punkt sollte klar geworden sein. Dieses Gesetz ist völlig unabhängig von einer Statistik bezüglich der Ankunft oder Verarbeitung bzw. der Verweilzeit – einzig die Vorgabe des Gleichgewichts zwischen ankommenden und fertiggestellten Aufträgen bei großen Zeiten (tM ∞) ist entscheidend für seine Gültigkeit.

4.2 Die Herleitung der Gesetze

33

B2 Ein Router benötigt zum Weiterschicken eines IP-Pakets 10 msec und es kommen im Schnitt 500 Pakete/sec an. Wie viele Pakete sind im Mittel im Router?

λ = 500 P/sec = 10 msec = 10*10–3 sec = λ * = 500*10*10–3 = 5*103*10–3 = 5 d. h., wenn ein Paket verarbeitet wird, muss man mindestens 4 Warteplätze für die anderen vorsehen.

Es hat sich als zweckmäßig für die Analyse solcher Systeme herausgestellt, auch die auslaufenden Prozesse zu berücksichtigen und den Begriff der Auslastung ρ = λ/μ einzuführen, welche das Verhältnis von einlaufenden Prozessen zu auslaufenden bearbeiteten Prozessen beschreibt. B3 Hat z. B. eine Platte eine Verarbeitungskapazität von 200 IO/sec und schickt der Prozessor im Mittel 100 I/O-Anforderungen/sec, dann ist die Auslastung

λ = 100 IO/sec μ = 200 IO/sec ρ = λ/μ = 0,5 d. h. 50 Prozent und damit im akzeptablen Bereich. ρ-Werte in der Gegend von 1 führen beim Auftreten temporärer Spitzen zum Systemzusammenbruch, denn man muss sich immer das Gleichgewicht und das zeitliche Mittel vergegenwärtigen. Wir haben in unserem Router-Beispiel schon angedeutet, dass die mittlere Verweilzeit in zwei Teile zerfällt als mittlere Wartezeit als mittlere Bearbeitungszeit

34

4 Die Gesetze von Little

d. h. ein Prozess kommt in das System, und wenn die Verarbeitungseinheit nicht frei ist, wird er in einen Wartepool eingereiht. Damit gilt natürlich = + und für die mittlere Wartezeit können wir das 2. Little’sche Gesetz formulieren: = λ *

wobei die mittlere Anzahl von Prozessen in der Warteschlange bezeichnet. Betrachten wir wieder unser Router-Beispiel. Die mittlere Anzahl ist = 5, davon ist einer in Arbeit und somit ist = 4. Für die mittlere Wartezeit folgt: = / λ = 4/λ; λ = 500 P/sec =

4 40 40 = = 10−3 = 8 msec 500 5000 5

Wegen = + , also 10 = 8 + folgt die mittlere Bearbeitungszeit = 2 msec. Ihr Kehrwert μ = 1 / ist die Bearbeitungsrate und ergibt sich zu 0,5*103 = 500 Pakete/sec. Die Auslastung ρ = λ/μ = 500/500 = 1 ist 100%, ein nicht akzeptabler Betriebszustand! Damit haben wir für das Vorhaben, möglichst einfach das Leistungsverhalten eines Systems zu beschreiben, welches durch einen Strom von Aufträgen charakterisiert ist – und nicht durch einen Auftrag bzw. ein Programm –, eine Lösung in Form von gemittelten Größen gefunden. Diese < tV>, , , , sind durch die Little’schen Gesetze untereinander verknüpft λ * =

λ * =

und geben die Dynamik des Systems in aggregierter Form wieder.

4.3 Zusammenfassung

35

4.3 Zusammenfassung Die Relevanz der Little’schen Gesetze besteht einmal in ihrer Einfachheit und damit auch in einer hohen Transparenz sowie zum anderen in den äußerst schwachen Voraussetzungen, die sie benötigen – mehr als das asymptotische, statistische Gleichgewicht ist nicht notwendig. Mit der leicht zu messenden Ankunftsrate λ und den durch Modellierung relativ einfach abzuschätzenden Größen bzw. sind die mittlere Verweilzeit bzw. die mittlere Wartezeit direkt bestimmbar. Man muss sich jedoch immer vor Augen halten, dass sie für eine einzelne Last keinen Sinn ergeben. Wie am Anfang dieses Abschnitts erwähnt steht für uns als Leistungsgröße der Durchsatz im Vordergrund. Von der Definition her ergibt er sich als die Anzahl erledigter Aufträge pro Zeiteinheit, also z. B. D = /. Nach dem ersten Little’schen Gesetz folgt D = λ, denn im statistischen Gleichgewicht wird, alles was angeboten wird, auch verarbeitet. Es besteht aber auch die Möglichkeit, D über die mittlere Bearbeitungszeit und die Auslastung ρ zu bestimmen: • die Auslastung ρ ergibt sich aus dem Verhältnis einlaufender zu bearbeiteter Prozesse, • in der zur Verfügung stehenden mittleren Bearbeitungszeit kann nicht mehr als der ρ-Anteil verarbeitet werden, ⎤ ρ ⎡ Auslastung • Durchsatz = ⎢ ⎥. < t B > ⎣ mittlere Bearbeitungszeit ⎦ So ist beim Router-Beispiel ρ = 1 und = 2 msec. Damit ergibt sich der Durchsatz D = ρ/ = 1/2 msec = (1/2)*103 [sec–1] = 500 [Pakete/sec] Dies entspricht der Zahl der einlaufenden Pakete, wegen der Auslastung ρ = 1 kommen natürlich auch alle zur Verarbeitung. In unserem Beispiel B3, Disk-I/O, ist ρ = (1/2) und = (1/200) [sec] = (1/2)*10–2 [sec]. Der Durchsatz ergibt daher zu D = ρ / = (1/2)/((1/2)*10–2) = 100 (IO/sec). Weitere Beispiele sollen an dieser Stelle nicht verfolgt werden, da wir später noch ausführlich den Durchsatz-Begriff behandeln werden. Jedoch hat letztere Auffassung viele Vorteile. Einmal, weil sie in der Praxis in der Form *D = ρ durch Messung überprüft werden kann, und zum anderen, weil sie sich unkompliziert im Rahmen von Modellen anwenden lässt. In den Kap. 6 und 7 wird dies deutlicher.

5 Benchmarks oder die Last mit der Last

Im Prinzip müsste das Ausmessen der Leistung durch Ablaufen der Maschineninstruktionen, welche die Last exakt repräsentieren, geschehen – ohne Beeinflussung durch die Ablaufumgebung, etwa einem Betriebssystem. Einem derartigen Unterfangen werden sich jedoch nur Idealisten und Puristen unterziehen. In der Praxis wird man versuchen, durch simple Vergleichsmessungen entsprechende Einflüsse zu eliminieren oder zu minimieren.

5.1 Historie und Voraussetzung Damit gehen wir ab jetzt davon aus, dass unsere Last um Betriebssystemkommandos ergänzt wird, auf welche wir relativ wenig Einfluss haben, im üblichen Jargon redet man von einer „workload“ (s. Abb. 5.1).

t

Start Workload

Unterbrechungen durch das Betriebssystem, wie etwa Caching, I/O, usw.

Ende Workload

Abb. 5.1 Ablauf einer „workload“

In modernen Hochleistungs-Clustern gleichartiger Maschinen (s. Abb. 5.2) kann die durch das Betriebssystem verursachte Koordination sogar eine Kommunikationslast hervorrufen, welche die eigentliche Lastmessung so empfindlich beeinflusst, dass diese praktisch wertlos ist (siehe Abschnitt 13.5).

38

5 Benchmarks oder die Last mit der Last

Cluster

Cluster

-Rechner

-Rechner Kommunikationskanal zum Datenaustausch

Abb. 5.2 Cluster-Modell

Man wird daher diese zusätzliche „Lasten“ gesondert ausmessen und bei der Leistungsberechnung explizit berücksichtigen. Vor diesem Hintergrund sind künstliche Zusammenstellungen von Maschineninstruktionen, sogenannte Mixe oder Kernels entstanden, die von jeglichen Interrupts frei sind. So hatte der berühmte Gibson-Mix in etwa den folgenden Aufbau (s. Abb. 5.3): Load/Store Vergleiche, Verzweigungen Logical Integer-Arithmetik Gleitkomma Rest

30% 20% 05% 05% 20% 20%

Abb. 5.3 Häufigkeiten von Maschinenbefehlen

Durchgesetzt haben sich heute Benchmarks auf der Ebene einer höheren Programmiersprache, so etwa FORTRAN für numerische Anwendungen wie im Linpack oder Livermore Loops, C, C++ und Java sind genauso vertreten. Ältere synthetische Benchmarks wie Whetstone wurden sogar über mehrere Programmiersprachen hinweg weiterentwickelt; von Dhrystone – entwickelt bei Siemens 1984 – ist heute nur noch die C-Version in Gebrauch. Sehr bekannt ist die SPEC-Benchmark-Initiative führender Computerhersteller (SPEC – Systems Performance Evaluation Cooperative), die versucht, die relevantesten Anwendungen in einem weiten Spektrum zu erfassen. Dieses Spektrum deckt ab: • • • •

die Laufzeit eines C-Compilers für verschiedene Quell-Codes, ingenieurwissenschaftliche Anwendungen aus dem Bereich der Simulationen, Anwendungen der symbolischen Datenverarbeitung wie LISP und LOGIK, numerische Anwendungen auf Linpack-Basis, welche auch für Vektorisierung und Parallelisierung geeignet sind.

5.2 Ein explizites Benchmark-Beispiel

39

Mit einer Erweiterung auf Ein-/Ausgabe-Operationen, was einer Einbeziehung von Datenbankanwendungen entspricht, würde es sich als Basis für einen allgemein akzeptierten Standard eignen.

5.2 Ein explizites Benchmark-Beispiel Wir wollen im Folgenden an einem sehr simplen Beispiel erst das Grundmuster eines Benchmarks aufzeigen und im Anschluss daran die Auswertungsmethodik skizzieren. Anwendung: Auswertung einfacher arithmetischer Ausdrücke für eine feste Anzahl von Wiederholungen – es wird klar zwischen integer und real/float Ausdrücken unterschieden Realisierung: Java mit Benutzung der Hardware-Arithmetik Windows 2000 Professional Pentium III, (3/4) GHz Messungen: Abschätzen der Anzahl der Maschineninstruktionen anhand des Byte-Codes => #last Ablaufzeit zcpu Programm: public class Schleife0{ static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static int xInt, yInt; static double xRea, yRea; static final int MAXN = 1 000 000; public static void printEingabe(){ System.out.print("\nGeben Sie die erste Zahl ein: "); setZahl('x'); System.out.print("\nGeben Sie die zweite Zahl ein: "); setZahl('y'); } public static void setZahl(char c){. . .} public static void berechneErgebnis(){ int Ergebnis=0; long zeitStart,zeitEnde; for (int i=1; i D = 1/5

und für die Auslastungen ρ = ^tS*D = (1/3, 4/5, 3/5, 2/5) In diesem System sind Platte A zu 80% und Platte B zu 60% ausgelastet und damit im Engpass-Bereich.

Sehr einfach lassen sich mit dieser Methode die Auswirkungen von Konfigurationsänderungen abschätzen, wir zeigen dies an einem Beispiel B5 System = {Server, Disk-A, Disk-B}, wobei ts(A) = k*ts(B); k > 0, d. h. B ist das schnellere Plattensystem. Vonseiten des Servers gibt es weniger Zugriffe auf A, d. h. vA = αvB mit α < 1. vS = 1 + vA + vB = 1 + αvB + vB = 1 + (α + 1) vB ~ (α + 1) vB

G

Auslastungssvektor ρ = (ρS, ρA, ρB) = (tS(S)*vS*D, tS(A)*vA*D, tS(B)*vB*D) G ρ = ((1 + α) tS(S), k*αtS(B), tS(B))*vB*D

D. h. wenn α*k < 1, α < 1/k, dann ist B trotz der größeren Geschwindigkeit ein Engpass! Was würde die Verlagerung auf B bringen? v’A = 0, v’B = vA + vB= αvB + vB= (α + 1) vB v’S = 1 + v’A + v’B ~ (1 + α) vB ρ' = [(1 + α) tS(S), 0, (1 + α) tS(S)]*vB*D

d. h. die Auslastung von B erhöht sich um α < 1. Analysieren wir die Verlagerung auf A mit v’’B = 0, v’’A = (α + 1) vB v’’S = 1 + v’’A + v’’B ~ (α + 1) vB:

6.4 Das Central-Server-System

61

ρ' ' = [(α + 1) tS(S), (α + 1) k tS(B), 0]*vB*D

Die Auslastung dieser Konfiguration ist bezüglich der Platten um den Faktor k größer und deshalb ungeeignet!

Wenn #last = (#last0, #last1,..., #lastn) den Vektor der Teillasten in den Komponenten/Subsystemen darstellt, dann ist das eben diskutierte Verfahren nichts anderes als die Lösung eines linearen Gleichungssystems n

# last j =

∑p

ij * last i

, j = 0,1,...n

i =0

Wir dividieren durch #last0 und erhalten # last j # last 0

n

=

vj =

∑p

ij *

∑p

ij * vi

i =0 n

# last i # last 0 mit v0 = 1

i =0

G Wenn v =(1, v1, v2,..., vn) der Vektor der relativen Besuchshäufigkeiten und P die Matrix der Übergangswahrscheinlichkeiten, dann hat man die elegantere Form G G v = vP , d. h. man sucht zu P den Eigenvektor mit dem Eigenwert 1.

6.4 Das Central-Server-System Eines der am häufigsten verwandten Konzepte ist in diesem Zusammenhang das sogenannte „Central-Server-Modell“, bei dem die zu erledigenden Aufträge von einer Quelle S0 in einem Server S1 laufen, welcher sie anschließend an Arbeitsstationen (Clienten) S2….Sn verteilt. Die dort erledigten Aufträge werden dann wieder an den Server zurückgegeben (s. Abb. 6.5).

62

6 Messbare Leistungsgesetze

S2 p21 = 1

p12 P31 = 1

p01

S0

S1

p13

S3

pn1 = 1

p1n Sn Abb. 6.5 Struktur des Central-Server-Modells

Die Übergänge Si Æ Sk sind mit Wahrscheinlichkeiten pik „belegt“ und können damit in folgender Matrix P zusammengefasst werden: 0

1

2

3

…

n

0

0

1

0

0

0

1

p10

p11

p12

p13

p1n

2

0

1

0

0

0

3

0

1

0

0

0

0

1

0

0

0

… n

G

Der Vektor v = (v0, v1, v2, …, vn)= (1, v1, v2, …, vn) bestimmt sich nach den G G obigen Ausführungen über v = v * P; wir demonstrieren das Prinzip an einem kleinen Beispiel mit n = 2:

6.4 Das Central-Server-System

63

B6 Modell p10 = 1/2

p21 = 1

Terminal (0) Disk (2)

Server (1) p01 = 1

p12 = 1/4 p11 = 1/4

1 0 ⎞ ⎛0 ⎛ 0 ⎜ ⎟ ⎜1 Matrix P ⎜ p01 p11 p12 ⎟ = ⎜ ⎜2 ⎜ 0 1 0 ⎟⎠ ⎜⎝ 0 ⎝

1 1 4 1

0⎞ 1⎟ ⎟ 4⎟ 0 ⎟⎠

G G v = v*P ⎛ 0 ⎜ (1, v1, v2)= (1, v1, v2) ⎜ p10 ⎜ 0 ⎝

1 p11 1

0 ⎞ ⎟ p12 ⎟ 0 ⎟⎠

1 = 1*0 + v1*p10 + v2*0 = v1*p10 Æ v1 = 1/ p10 = 1/(1/2) = 2 v1 = 1*1 + v1*p11 + v2*1 = 1 + p11*v1 + v2 v2 = 1*0 + v1*p12 + v2*0 = v1*p12 Æ v2 = (p12/p10) = (1/4)/(1/2) = 1/2 Bei vorgegebenem Gesamtdurchsatz D folgt D1(Server) = v1*D = 2*D und D2(Disk) = v2*D = (1/2)*D, sodass die Auslastung sich zu ρ1 = 2*ts(1)*D, ρ2 = (1/2)*ts(2)*D G ρ = (4*ts(1), ts(2))*D/2

ergeben. Da eine Terminaltransaktion hardwarebedingt mehr Servicezeit ts(2) auf der Platte benötigt, wird diese, trotz des Vorfaktors 4 beim Server, die Auslastung des Systems bestimmen.

64

6 Messbare Leistungsgesetze

6.5 Das verallgemeinerte Antwortzeit-Gesetz Eine interessante Variante des gerade beschriebenen Analysekonzepts erhält man unter Einbeziehung der Little’schen Gesetze: = λ *

und

= λ *

wobei λ die Ankunftsrate der Aufträge, und die mittlere Verweil- bzw. Wartezeit sowie und die Anzahl der Aufträge im System bzw. im Wartezustand darstellen. Diese Gesetze sind zunächst für das ganze System gültig, aber es gibt keinen Grund, sie geeignet auf Subsysteme zu übertragen und dabei das Konzept der Übergangswahrscheinlichkeiten pij (von Subsystem i nach Subsystem j) beizubehalten. Wir führen die Idee an einem sehr einfachen Beispiel aus: B7 λ1

• 1

•

λ2

2

p12 λ1 = Rate der Aufträge nach Subsystem 1 λ2 = Rate der Aufträge nach Subsystem 2 λ1 kann nur die Gesamtlast E der externen Aufträge pro Zeiteinheit sein, λ1 = E + 0*λ1 + 0*λ2 λ2 hat keinen externen Zufluss und nur einen Betrag von Subsystem 1, also λ2 = 0 + 1*λ1 + 0*λ2, denn p12 = 1 in Vektor- und Matrixschreibweise: (λ1, λ2) = (E,0) + (λ1, λ2) 0

1

0

0

klarerweise sind die Lösungen λ1 = λ2 = E und wir können „Little“ auf Subsystem 1, 2 anwenden:

6.5 Das verallgemeinerte Antwortzeit-Gesetz

= λ1* = E

65

; = λ2 ; = E

G Das Prinzip der Verallgemeinerung liegt auf der Hand. Ist λ = (λ1, λ2, λ3,...λn) G der Vektor der internen Zuflussraten (λi Rate auf den Knoten i), E = (E1, E2, E3,...En) der Vektor der externen Zuflussraten (Ei Zahl der externen Aufträge pro Zeiteinheit auf Knoten i) und P die n*n-Matrix der Übergangswahrscheinlichkeiten, so folgt: G G G λ = E + λ *P

d. h. wir haben im Gleichgewicht, das ist die einzige Voraussetzung für „Little“, ein einfaches inhomogenes lineares Gleichungssystem. Zur Demonstration greifen wir auf das Beispiel B4 zurück: B8 p12 =2/5

p24 =1 A(2)

p41 =199/200 E

S(1)

C(4)

B(3) p13 =3/5

p34 =1

G Wir haben 4 Komponenten und damit 4 Zuflussraten λ = (λ1, λ2, λ3, λ4), nur auf Komponente S(1) haben wir den Zufluss der externen Aufträge G E = (E, 0, 0, 0). Die Matrix P der Übergangswahrscheinlichkeiten ist

0

p12

1-p12

0

0

0

0

1

0

0

0

1

p41

0

0

0

G G G und somit ist λ = E + λ * P zu lösen.

66

6 Messbare Leistungsgesetze

λ1 = E + λ 4 * p 41 =

E = 200E 1 − p 41

λ 3 = 0 + λ1 * (1 − p12 ) =

λ 2 = 0 + λ1 * p12 =

p12 E = 80E 1 − p 41

1 − p12 E = 120E λ 4 = 0 + λ 2 + λ 3 = 200E 1 − p 41

Vergleichen wir die Koeffizienten von E für λ1...λ4, so sind diese nichts anderes als die relativen Besuchshäufigkeiten von B4, E ist der Gesamtdurchsatz D und λ1...λ4 die Durchsätze D1...D4 der Subsysteme. Das liegt daran, dass im Gleichgewicht der maximale Durchsatz erreicht wird und dieser per se nicht größer als das Angebot sein kann. Gelingt es uns, (ki) (i = 1...4), die mittlere Anzahl von Aufträgen im Subsystem i, zu messen, kann über Little = λi * leicht die mittlere Verweilzeit in der Subkomponente i bestimmt werden.

Die Verallgemeinerung dieses Beispiels auf n Teil-/Subsysteme liegt auf der Hand. Die mittlere Zahl von Aufträgen im Gesamtsystem ist natürlich die Summe der Aufträge in den Teilsystemen = + +... + Andererseits ist = λ* = D* (Letzteres im Gleichgewicht) und = λi*. Eingesetzt in die obige Summe folgt λi = Di: D* < t V >= D1 < t (V1) > + D 2 < t (V2) > +... + D n < t (Vn ) >

< t V >=

D1 D D < t (V1) > + 2 < t (V2) > +... + n < t (Vn ) > D D D

Nach dem zweiten Auslastungsgesetz ist Di = vi*D und somit Di/D = vi. Damit erhalten wir das Antwortzeit-Gesetz < t V >= v1 < t (V1) > + v 2 < t (V2) > +... + v n < t (Vn ) > ,

welches in der englischsprachigen Literatur als “General Response Law“ bekannt ist.

6.6 Dialogsysteme

67

Bei den bisher behandelten Leistungsgesetzen vom operationalen Typ für Systeme, welche aus Subsystemen i = 1...n aufgebaut sind, lassen sich drei Ausrichtungen feststellen: lokale Gültigkeit auf Teilsystemen • Auslastung

ρ i = t S(i ) * D i , i = 1...n

• Antwortzeit

< k i > =< t (Vi ) > * D i , i = 1...n

globale/lokale Gültigkeit, d. h. Verknüpfung von lokalen Größen und globalen • Flussgesetz

D i = v i * D i bzw. ρi = ˆt S(i ) * D

• Antwortzeit

< t V >=

n

∑v *< t i

(i ) v

>

i =1

globale Gültigkeit für das ganze System • Auslastung

ρ = tS * D

• Antwortzeit

< k > = < t V > * D wobei D = λ

6.6 Dialogsysteme Zur Abrundung dieses Analysespektrums sollen noch ein weiteres globales Leistungsgesetz und einige Abschätzungen vorgestellt werden. Das noch fehlende Gesetz ergänzt die Analyse der Antwortzeit und bezieht sich hauptsächlich auf interaktive Systeme wie wir sie bei Server/Client-Architekturen finden. Es soll nach dem bereits öfter erprobten Schema schrittweise abgeleitet werden: • Server N Clienten • der Client schickt eine Forderung (req), das System braucht im Mittel die Antwortzeit , über diese Zeit wollen wir eine Aussage • hat der Client eine Antwort auf die Forderung (req) erhalten, denkt er die mittlere Zeitspanne , bevor er eine weitere Forderung startet • die Gesamtzeit für eine Forderung ist also + • in der Beobachtungszeit tM hat man damit pro Benutzer im Mittel tM # req = < t V > + < t idle > Forderungen, bei N Clienten sind es N*#req • der Durchsatz D des Gesamtsystems in der Beobachtungszeit tM ist somit N*# req N D= = < t M > < t V > + < t idle >

68

6 Messbare Leistungsgesetze

• ist der Durchsatz D schon bekannt, etwa über D = Dk/vk im k-ten Subsystem, können wir nach auflösen und erhalten mit N < t V >= − < t idle > D das gesuchte Antwortzeit-Gesetz. Man muss dabei berücksichtigen, dass es hierbei um Mittelwerte geht, die eine entsprechende Statistik voraussetzen. Die Abhängigkeiten vom Durchsatz D und der Nutzerzahl N dürften unmittelbar einsichtig sein – hinsichtlich der Denkzeit ist klar, dass eine Abnahme/Verminderung die Belastung erhöht und damit die mittlere Antwortzeit verlängert. Die Verknüpfung mit dem Gesetz von Little λ * = = D * , wobei die mittlere Anzahl von Aufträgen (req) im System ist, erhellt diesen Sachverhalt vielleicht etwas besser: = D * = D*(N/D - ) = N – D* d. h. die obere Schranke für die mittlere Anzahl von Prozessen ist N und D* gibt den Wegfall durch die Denkzeit an. B9 Terminal-Beispiel von B4 mit folgenden Ergänzungen: D = 2/5; N = 20; = 5 [sec] < t V >=

20 − 5 = 45 [sec] 2/5

< k >= N − D* < t idle >= 20 − (2 / 5) * 5 = 18

Aufgrund der doch etwas einfachen Argumentation bei der Ableitung dieses Antwortzeit-Gesetzes vom globalen Typ, kann natürlich die Abhängigkeit D(N), also des Durchsatzes von der Nutzerzahl, nicht eingebracht werden. Einige wichtige Abschätzungen in dieser Richtung liefert jedoch die folgende Analyse: (k )

• für die Auslastung ρk jeder Komponente k = 1...n gilt ρk ≤ 1; ρk = t S * D k (k )

also Dk* t S

≤ 1; da der Durchsatz des Gesamtsystems durch das Maximum

6.6 Dialogsysteme

69

der Durchsätze der Subsysteme k festgelegt wird – dies impliziert eine minima(k )

le Service-Zeit t S

D max ≤

–, folgt

1 min(t s(1) ,..., t s( n ) )

Die Existenz eines solchen maximalen Durchsatzes entspricht der Beobachtung an realen Systemen, dass mit wachsendem N keine wesentliche Durchsatzsteigerung mehr zu beobachten ist. • das Antwortzeit-Gesetz

D( N ) =

< t V >=

N − < t idle > wird umgeformt D

N N ; ≤ < t V ( N) > + < t idle > < t V (1) > + < t idle >

die Abschätzung tV(1) ≤ tV(N) ist intuitiv klar, eine wachsende Zahl von Nutzern bedingt eine steigende Antwortzeit bei gleichbleibender Systemleistung. Die Größe tV(1) kennen wir bereits, es gilt tV(1) = v1 * t v + ... + v n t v (1)

(n )

(ge-

neral response law). • die gemeinsame Betrachtung der Ungleichungen D(N) ≤ Dmax und D(N) ≤ aN, wobei a = 1/( + ), so erhält man den in Abb. 6.6 dargestellten Verlauf 4 D(N) 3,5 3 2,5 Dmax 2 1,5 1 0,5 0 Jan

a*N

D(N)

Feb

Mrz

Apr

N* Mai

Abb. 6.6 Verhalten des Durchsatzes von der Clientenzahl N

Jun

N

70

6 Messbare Leistungsgesetze

• der Punkt N*, D(N*) = Dmax definiert den Sättigungspunkt, von dem an keine wesentliche Durchsatzsteigerung mehr zu erwarten ist. Dmax = aN* => N* = Dmax/a N* =

< t V (1) > + < t idle > min(t s(1) ... t s( n ) )

Zur Illustration des Ablaufs greifen wir auf die Werte von B4 und B8 zurück:

B10 = 5 [sec]; ts = (2, 2, 1, 0,02), da der Controller keine relevante Rolle spielt, wird sein Beitrag vernachlässigt: min(2, 2, 1) = 1 und damit Dmax = 1 [req/sec].

= 2 + 2 + 1 = 5 N* = (5 + 5) / 1 = 10, d. h. für N* > 10 ist keine Durchsatzsteigerung mehr zu beobachten und die Antwortzeit wird steigen!

Dieses Sättigungsverhalten des Durchsatzes auf Kosten der Antwortzeit legt es nahe, für letztere in ähnlicher Weise Abschätzungen zu finden (s. Abb. 6.7). Eine untere Schranke konnten wir schon angeben: ( ≤ ) für alle N ≥ 1. Eine N weitere erhalten wir über das Antwortzeit-Gesetz < t V ( N) >= − < t idle > . D( N ) Da D(N) ≤ Dmax folgt in der Kombination

≥ (N/Dmax) - ≥ N*min(tS(1)... tS(n)) -

und somit: ≥ max(, N*min(tS(1)... tS(n)) - )

6.6 Dialogsysteme

15

71

10 5

0

N N**

-5

- Abb. 6.7 Antwortzeit in Abhängigkeit von der Clientenzahl N

Der Punkt N** kennzeichnet die Menge von Nutzern/Terminals, ab der die Antwortzeit überproportional ansteigt und die Bildung von Warteschlangen signalisiert. Es gilt = min(tS(1)... tS(n))* N** – und damit N ** =

< t V (1) > + < t idle > min(t s(1) ... t s( n ) )

= N*

d. h. N** entspricht dem Sättigungspunkt beim Durchsatz. Dies entspricht einer dualen Situation in der linearen Optimierung, ein duales Min/Max-Problem hat genau einen solchen gemeinsamen Punkt. B11 Wir nehmen die Situation wie in B9 und B10 an und fragen wie viel Terminals N wir zulassen können, damit die Antwortzeit ≤ 20 sec?

= 5 [sec]; = 5 [sec] min(2, 2, 1) = 1

≥ max(5, 1*N - 5) N – 5 ≥ 20 => N ≥ 25

≤ 20

72

6 Messbare Leistungsgesetze

Damit können wir unser Programm abschließen, mit einfachen und messbaren Größen solche Analysegesetze lokalen und globalen Typs zu entwickeln, die ein Verständnis von offenen Systemen – aufgebaut aus Teilsystemen – hinsichtlich der Leistungsgrößen Durchsatz und Antwortzeit ermöglichen. Die Basis dafür bilden die Gesetze von Little, da sie ein komplexes Verhalten bezüglich der Zeit in Mittelwerten aggregieren.

7 Einfache stochastische Modellvorstellungen

Die Zerlegung eines komplexen DV-Systems in n Subeinheiten (Si, i = 1…n) wie im vorangegangenen Kapitel ist natürlich schon eine Modellierung, und zwar eine, welche der Realität ziemlich nahe kommt. Daran ändert auch die Einführung von Übergangswahrscheinlichkeiten pij zwischen den Teilsystemen Si und Sj nichts, weil von einem virtuellen „externen“ Standpunkt die vielen Aufträge im System sich stochastisch verhalten. Trotzdem gelingt es mit dieser Methode recht gute quantitative Aussagen zu gewinnen. Häufig ist man aber daran gar nicht interessiert, sondern möchte mit einem sehr einfachen und durchschaubaren Vorgehen qualitative Verhaltensweisen des untersuchten Systems bestimmen. Unter diesem Gesichtspunkt bieten die Gesetze von Little und das bereits diskutierte Black-BoxModell einen wesentlich günstigeren Ansatzpunkt.

7.1 Voraussetzungen Bei dem Black-Box-Modell haben wir die Gesamtheit der ankommenden Aufträge [req] durch eine Rate λ [req/Zeit] beschrieben, die Bearbeitung in der Black-Box durch die Rate μ [erlreq/Zeit]. Damit einher ging die Vorstellung, dass die einlaufenden Aufträge in einen Wartepool wandern, dem sie dann für die Verarbeitung entnommen werden. Der innere Zustand ist dann im Prinzip durch die Anzahl k der Aufträge im System gekennzeichnet, allerdings kann man wegen der stochastischen Ankunft und Bearbeitung nur eine Wahrscheinlichkeit pk dafür angeben; natürlich wird diese von der Zeit abhängen pk = pk(t), wobei 0 ≤ pk(t) ≤ 1 für alle k = 0, 1, 2,... n und t ≥ 0 (s. Abb. 7.1).

74

7 Einfache stochastische Modellvorstellungen

λ

μ

pk(t)

Abb. 7.1 Definition der Zustandswahrscheinlichkeit

Gehen wir davon aus, dass das System zum Zeitpunkt t = 0 leer ist p0(t = 0) = 1, dann muss man sich überlegen, wie man von diesem sicheren Zustand zu k > 0 mit pk(t) kommt (s. Abb. 7.2)

? p0(0)=1

pk(t)

0

t

Abb. 7.2 Zeitliche Entwicklung der Zustandswahrscheinlichkeit

Wir engen die vielen Möglichkeiten deutlich ein und beschränken uns auf folgende Systemdynamik, λ

k–1

λ

k μ

k+1

...

μ

Abb. 7.3 Markoff’sches Zustandsmodell

d. h. Übergänge können nur zwischen unmittelbaren Nachbarn stattfinden. Da dies gleichbedeutend damit ist, dass • nur der gegenwärtige Zustand den nächsten beeinflusst – also so eine Art Gedächtnislosigkeit, • die Zeiten zwischen zwei Ankünften exponentiell verteilt sind, ebenso die Bearbeitungszeiten, sind die Bedingungen für einen Markoff-Prozess [8, 9] gegeben und man kann für diese Modelle das ganze Rüstzeug der entsprechenden mathematischen Theorie einsetzen (s. Abb. 7.3). Wir benötigen für unsere Zwecke davon allerdings nur einen sehr bescheidenen Anteil, der im Folgenden skizziert werden soll (s. Abb. 7.4).

7.2 Ableitung der Zeit-Dynamik und Skizze der Lösung

75

Die exponentiell verteilten Zwischenankunftszeiten

0

t2

t1

t

Ankünfte Auftrag 1 und 2 t2 – t1 = tZ Zwischenankunftszeit Abb. 7.4 Definition der Zwischenankunftszeit tZ

genügen der Verteilungsfunktion p (tZ ≤ t) = 1 – e–λt mit den Werten 0 für t = 0 und 1 bei t → ∞ . Die Ableitung nach t ist die Verteilungsdichte

f λ ( t ) :=

dp( t Z ≤ t ) = λ e − λt dt

die wir zur Berechnung des Erwartungswertes brauchen (mittlere Zwischenankunftszeit): ∞

∞

0

0

∫

∫

= dtf λ ( t ) t = dtλte − λt =

1 . λ

Ähnliches gilt für die Verteilung der Bearbeitungszeit: p(tB ≤ t) = 1 – e–μt =

1 μ

7.2 Ableitung der Zeit-Dynamik und Skizze der Lösung Damit können wir zur Dynamik von Abb. 7.3 zurückkehren. Sie besagt, dass die Wahrscheinlichkeiten zwischen den Zuständen k – 1, k und k + 1 mit λ und μ zu jedem Zeitpunkt t miteinander verbunden werden müssen: • die Änderung der Wahrscheinlichkeiten pk(t) ist nichts anderes als die Ableitung pk’(t), • die Beiträge, welche zu einem Anwachsen von pk(t) führen, sind λ*pk–1(t) + μ*pk+1(t), wobei λ, μ die Übergangsraten darstellen, und • die Beiträge, welche zur Abnahme von pk(t) führen, sind -λ*pk(t) – μ*pk(t) = -(λ + μ) pk(t);

76

7 Einfache stochastische Modellvorstellungen

• fassen wir zusammen, so folgt: pk’(t) = λ*pk–1(t) + μ*pk+1(t) – (λ + μ) pk(t); k = 1, 2, 3,... p0’(t) = μ*p1(t) – λ*p0(t) ∞

p0(0) = 1 und

∑ p (t) = 1 für t ≥ 0. k

k =0

Diese Zusammenstellung beschreibt ein rekursives Differenzialgleichungssystem 1. Ordnung, für welches eine vollständige Lösung angegeben werden kann. Solche Gleichungen enthalten immer einen exponentiellen Anteil, den man herauszieht: pk(t) = e–(λ+μ)t qk(t). Setzt man dies in die Differenzialgleichung ein, erhält man für die neue Funktion qk(t) qk’(t) = μ qk+1(t) + λ qk–1(t); k = 1, 2, 3,... k

⎛ λ ⎞2 Mit dem Standardansatz q k ( t ) = ⎜⎜ ⎟⎟ rk ( t ) ⎝μ⎠

entfernt man die Koeffizienten λ und μ:

1 λμ

*

drk ( t ) = rk +1 ( t ) + rk −1 ( t ) dt

Den verbleibenden Koeffizienten λμ dt = μ

1 λμ

schaffen wir durch die Substitution

1 λ λ dt = * 2μ ρdt; wobei ρ = : 2 μ μ 2

drk (t Z ) = rk +1 (t Z ) + rk −1 (t Z ) dt Z

t Z = 2μt ρ

Dies ist die Rekursionsgleichung für die gutmütigen modifizierten BesselFunktionen Ik(tZ).

7.3 Zeitunabhängige Lösungen im Gleichgewicht

77

Damit folgt für das zeitliche Verhalten der Wahrscheinlichkeiten (ohne Berücksichtigung der Normierung):

pk

k (t) ≈ ρ 2 I

− k (t Z )e

1+ ρ 2 ρ

τ

ρ = λ/μ, t Z = 2μt ρ

,

und man kann dann zeigen, dass diese für große Zeiten praktisch konstant sind: lim p k (t) = πk (unabhängig von t); k = 0, 1, 2,... t →∞

lim p' k (t) = 0 ; k = 0, 1, 2,... t →∞

7.3 Zeitunabhängige Lösungen im Gleichgewicht Die obige Situation entspricht einem Gleichgewicht, die Zeitabhängigkeit ist verschwunden p k ( t ) → π k , p' k ( t ) = 0 , so dass die Differenzialgleichungen in einfache Rekursionen bzw. ein lineares Gleichungssystem übergehen 0 = λπk–1 + μπk+1 – (μ + λ)πk ∞

0 = μπ1 – λπ0

∑π

und

k

=1

k =0

Ohne große Schwierigkeiten, schon allein durch Probieren, findet man die Lösungen λ πk = ( ) k π0 = ρk π0 ; k = 1, 2, ... μ ρ := λ / μ

Die noch unbekannte Wahrscheinlichkeit π0 für ein leeres System ergibt sich durch Ausnutzung der Normierungsbedingung 1=

∞

∑ k =0

πk =

∞

∑ k =0

π 0ρ k = π 0

∞

∑ρ

k

k =0

wenn 0 ≤ ρ < 1 π0 = 1 – ρ πk = (1 – ρ)ρk k = 1, 2,...

=

π0 1− ρ

78

7 Einfache stochastische Modellvorstellungen

Diese Wahrscheinlichkeiten πk bilden die Basis, um die Leistungsgrößen des Systems/Modells abzuleiten – interessanterweise hängen sie nur von einem Parameter ρ ab und nicht von den absoluten Größen λ, μ. In Abhängigkeit vom Parameter ρ zeigen die Zustandswahrscheinlichkeiten πk folgendes Verhalten (s. Abb. 7.5):

Abb. 7.5 Verhalten der Zustandswahrscheinlichkeiten

k und wandert gegen 1 bei wachsendem k +1 k, die Wahrscheinlichkeit selber verschwindet. Daraus resultiert, dass Zustände mit hohem k sehr unwahrscheinlich sind. Als erste Leistungsgröße bestimmen wir die mittlere Anzahl von Aufträgen im System:

Das Maximum von πk ist bei ρmax = k

∞

∞

< k >= ∑ k * π k = (1 − ρ ) ρ ∑ k ρ k − 1 k=0

k =1

∞

d k d ∞ k ρ = (1 − ρ ) ρ (∑ρ ) d ρ k =1 k =1 d ρ d 1 < k >= (1 − ρ ) ρ ( − 1) dρ 1 − ρ < k >= (1 − ρ ) ρ ∑

< k >=

ρ ; 0 ≤ ρ haben wir sofort eine Möglichkeit, die mittlere Verweilzeit eines Auftrags im System auszurechnen < t V >=

1 1 ρ * < k >= * λ λ 1− ρ

natürlich gilt dies auch für die Subsysteme. B1 Ein Gateway zwischen zwei Netzen erfülle die Voraussetzungen für unser theoretisches Modell. Der Strom der einlaufenden Datenpakete wird durch λ = 250 [Pakete/sec] beschrieben, im Mittel werden = 2 msec zum Weiterleiten benötigt.

= 2*10–3 [sec] => μ = 1/ = 500 [Pakete/sec] als Verarbeitungsrate ρ = λ/μ = 250/500 = 1/2, also 50% Auslastung < k >=

ρ 1/ 2 = = 1 ; im Mittel ist also ein Paket im Gateway λ − ρ 1 − 1/ 2

= (1/λ)* = (1/250)*1 = 4 msec Ein Datenpaket verbringt also im Mittel 4 msec im Gateway, da 2 msec zum Weiterleiten benötigt werden, beträgt die mittlere Wartezeit 2 msec. Der Verlauf von in Abhängigkeit von ρ zeigt ein starkes Anwachsen bei ρ ≈ 1 (s. Abb. 7.6),

80

7 Einfache stochastische Modellvorstellungen

Abb. 7.6 Verlauf von in Abhängigkeit von ρ

welches natürlich durch den Pol bei ρ = 1 bewirkt wird, so steigt um 100% von 3 auf 6 beim Wechsel von ρ = 3/4 auf 6/7. Dies bedeutet: Wird ein System schon mit einer hohen Auslastung ρ ≥ 3/4 (75%) betrieben, so genügen schon kleine Schwankungen, um die Last im System deutlich zu erhöhen. Da sich die mittlere Bearbeitungszeit nicht ändert, ist eine Verlängerung der Antwortzeit oder sogar ein vollständiger Stillstand die Folge, da der gleichen Gesetzmäßigkeit folgt.

7.4 Weitere Leistungsgrößen Die nächste abgeleitete Leistungsgröße ist die mittlere Anzahl von Aufträgen, die im System auf die Verarbeitung wartet; wir gehen wie folgt vor: • k Aufträge warten im System der Prozessor wird frei und nimmt sich 1 Auftrag • k – 1 Prozesse warten, 1 ist in Verarbeitung • dann ist der Mittelwert über alle Zustände, außer Ø – denn dann braucht nicht gewartet zu werden, mit dem Gewicht k – 1 < q >= < q >=

∞

∑

(k − 1)π k =

∑

kπ k −

k =1 ∞

∑ k =1

k =0

• < q >=

∞

ρ2 1− ρ

∞

∑π k =0

k

kπ k −

∞

∑π

k

k =1

+π0 =< k > −1 + (1 − ρ)

7.4 Weitere Leistungsgrößen

81

Wegen des Nenners haben wir das gleiche Verhalten bei ρ ≈ 1 wie , da im Zähler aber ρ2 statt ρ und 0 ≤ ρ ≤ 1, ist der Verlauf für ρ ≤ 3/4 insgesamt deutlich flacher und somit der Anstieg für ρ > 3/4 erheblich stärker. Um die mittlere Wartezeit auszurechnen, benutzen wir das zweite Little’sche Gesetz = λ * und erhalten < t W >=

< q > 1 ρ2 1 λ ρ = * = * * λ λ 1− ρ λ μ 1− ρ

< t W >=

1 ρ 1 * = μ 1− ρ μ

Dies ist ein unmittelbar einleuchtendes Ergebnis, denn die Wartezeit bestimmender Faktoren sind die Verarbeitungsrate μ und die mittlere Anzahl von Aufträgen im System.

B2 Wir können jetzt unser Beispiel B1 erweitern, es galt ja ρ = 1/2, = 1, μ = 500 Pakete/sec Länge der Warteschlange = ρ2/(1 – ρ)=(1/4)/(1/2) = 1/2 mittlere Wartezeit = (1/μ)* = (1/μ)*1 = 2 [msec] Ein Ergebnis, dass wir vorher in B1 über = + berechnet hatten.

B3 Ein Prozessor schickt 10 I/Os pro Sekunde an eine Platte, die für eine I/OOperation im Mittel 20 msec benötigt. Da die Zeitverteilungen der einlaufenden I/Os und der Bearbeitung vom exponentiellen Typ sind, kann unser theoretisches Modell für das Plattensubsystem als gültig angesehen werden. Wir bestimmen die Leistungsgrößen: λ = 10 [IO/sec] = 1/μ = 20 [msec] = 20*10–3 [sec] –3 ρ:= λ/μ = λ*1/μ = 10*20*10 = 2*10–1 = 1/5, d. h. die Auslastung beträgt 20%; = ρ/(1 – ρ) = (1/5)/(1 – 1/5) = 1/4; die mittlere Verweilzeit einer IOOperation ist = (1/λ)* = (1/10)*(1/4) = 1/40 [sec] = 25 [msec]; und die mittlere Wartezeit

82

7 Einfache stochastische Modellvorstellungen

= (1/μ)* = 20*10–3*1/4 = 5 [msec]; der Durchsatz D = ρ/ = (1/5)/(1/50) beträgt 10 I/O-Operationen pro Sekunde, was im Gleichgewicht zu erwarten ist.

Zur Analyse des Wartezeitverhaltens genügt es nicht, nur und zu kennen, häufig ist es auch wichtig zu wissen, mit welcher Wahrscheinlichkeit pW(ρ) ein ankommender Auftrag warten muss. Nun, das trifft immer dann zu, wenn das System nicht im Zustand k = 0 (π0) ist. p w (ρ) =

∞

∑ k =1

πk =

∞

∑π

k

− π0 = 1 − π0 = 1 − (1 − ρ) = ρ

k =0

p w (ρ) = ρ

Dies impliziert einen linearen Zusammenhang

0,6

1 0,5 pw(ρ)

0,4 0,3 0,2 0,1 0 1

0

2

1

3

4

ρ

Abb. 7.7 Verlauf der Wahrscheinlichkeiten

zwischen dem Systemparameter ρ und der Wartewahrscheinlichkeit (s. Abb. 7.7). Eine andere, mehr intuitive Ableitung der Wartewahrscheinlichkeit erhält man über den Ansatz pW(ρ) = / mit ≤ . Setzen wir die analytischen Ausdrücke für und ein, erhalten wir das bekannte Ergebnis. Zur Vermeidung von Verwechslungen und Fehleinschätzungen sollen noch drei weitere Wahrscheinlichkeiten skizziert werden:

7.5 Endliche Modelle

83

• πk = (1 – ρ)ρk: es sind genau k Prozesse im System • πk(q): es sind genau k Prozesse/Aufträge in der Warteschlange πk(q) = πk+1 = (1 – ρ)ρk+1, denn ein Auftrag wird sofort bedient • πk(n) ist die Wahrscheinlichkeit, dass mehr als n Aufträge im System sind π(n ) =

∞

∑π

k

k =n

=1−

n −1

∑π

k

= 1 −(1 − ρ)

k =0

1 − ρk 1− ρ

π k = (1 − ρ)ρ k

π( n ) = ρ n Die Nützlichkeit dieser Größen, vor allem von π(n) wird in dem folgenden Beispiel deutlich: B4 Wir nehmen unser Gateway von den vorangegangen Beispielen und ρ = 1/2. Es kann einen Verlust von einem auf 220 Pakete (≈ 1 000 000) tolerieren. Wie viele Pakete dürfen sich maximal im Gateway befinden?

Die Wahrscheinlichkeit für den Verlust ist pV = 1/220 und diese muss gleich der Wahrscheinlichkeit π(n ) = ρ n sein: pV = 1/220 = (1/2)20 = π(n ) = ρ n = (1/2)n

=> n = 20

d. h. für n > 20 tritt der Verlustfall ein => die maximale Paketanzahl darf den Wert 20 nicht überschreiten.

Damit kann die Skizze und Analyse eines der einfachsten Modelle vorläufig abgeschlossen werden. Die analytischen Ausdrücke für und erlauben transparente und rasche Schlüsse auf das Verhalten des Modells – allerdings muss man sich sorgsam über die Gültigkeit der Voraussetzungen – exponentiell verteilte Zwischenankunfts- und Bearbeitungszeiten – Gewissheit verschaffen.

7.5 Endliche Modelle Ein Problem der vorangegangenen Diskussion könnte auch die unendliche Zahl von Modellzuständen sein (es rechnet sich aber in diesem Fall leichter) oder ihre Anordnung in einer aufsteigenden linearen Kette. Darauf soll noch kurz eingegan-

84

7 Einfache stochastische Modellvorstellungen

gen werden, in einem späteren Kapitel werden wir noch einmal explizit darauf zurückkommen, hier wollen wir uns mit einem einfachen Beispiel begnügen. Betrachten wir ein redundantes Datenbanksystem, welches aus zwei Servern A, B besteht, die jeweils mit der Rate λ ausfallen und mit der Rate μ wieder gestartet werden. Dann gibt es folgende Zustände 1.: kein Server ist ausgefallen, 2.: Server A ausgefallen, B arbeitet, 3.: Server B ausgefallen, A arbeitet, 4.: A und B sind ausgefallen. Bevor wir die Übergänge zwischen den Zuständen k = 1…4 bestimmen, müssen wir uns über den Charakter von 4 klar werden. Entweder es besteht die Möglichkeit des Neustarts von A und B, dann kann das System weiterlaufen (4 ist ein reflektierender Zustand, s. Abb. 7.8)

1

λ

λ μ

μ

2

3 λ

λ

μ

μ

4

Abb. 7.8 Reflektierende Systemkonfiguration

oder das Wiederanlaufen von A, B kann nicht mehr stattfinden (4 ist ein absorbierender Zustand, s. Abb. 7.9). Dann ist der Zustandsgraph 1

λ

λ μ

μ

2

3

λ

λ

4 Abb. 7.9 Absorbierende Systemkonfiguration

7.5 Endliche Modelle

85

und da dieser Fall etwas weniger Aufwand erfordert, behandeln wir ihn explizit. π1…π4 sind die Zustandswahrscheinlichkeiten im stationären Gleichgewicht und es gilt 2λπ1 = μπ2 + μπ3 => 2ρπ1 = π2 + π3 (μ + λ) π2 = λπ1 = (μ + λ) π3 => π2 = π3 = ρπ1 π4 = ρπ2 + ρπ3 = 2ρπ2 = 2ρπ3 = 2ρ2π1 Es muss gelten π1 + π2 + π3 + π4 = 1 und somit N(ρ) = 1 + 2ρ + 2ρ2 ergeben sich die Wahrscheinlichkeiten zu π1 = 1/ N(ρ), π2 = π3 = ρ/N(ρ), π4 = 2ρ2/N(ρ) deren Verlauf Abb. 7.10 zeigt

Abb. 7.10 Zustandswahrscheinlichkeit in Abhängigkeit von ρ

Man sieht sofort, dass π1 (beide Systeme/Server sind funktionsfähig) immer mit wachsendem ρ abnimmt, d. h. der optimale Zustand 1 wird immer unwahrscheinlicher. Die Zustände 2 und 3 haben ihre maximale Wahrscheinlichkeit π2max ,3 bei (√2/2), d. h. die Ausfallrate beträgt dann ca. 75% der Reparaturrate. Der Zustand 4 wird mit wachsendem ρ (der Ausfallrate λ) immer wahrscheinlicher und dominiert alle anderen – er ist absorbierend. Dies zeigt sich auch bei einer Analyse des Mittelwertes = 1*π1 + 2*π2 + 3*π3 + 4*π4, wenn die π’s explizit eingesetzt werden =

1 + 7ρ + 8ρ2 1 + 2ρ + 2ρ2

86

7 Einfache stochastische Modellvorstellungen

Dieser verhält sich für große ρ wie bei ≈ 4, welches allerdings für ρ = 2 schon zu 90% der Fall ist. Es mag zunächst erstaunen, dass ρ = λ/μ auch Werte größer 1 annehmen kann, aber dies ist eine fundamentale Eigenschaft endlicher Modelle des diskutierten Typs. Wir werden später sehen, dass für ρ ≤ 1 der Unterschied zwischen endlich und unendlich vielen Zuständen vernachlässigt werden kann, sodass wir immer letztere annehmen können, da leichter mit ihnen umzugehen ist. Endliche Modelle von der Art des letzten Beispiels finden häufig Anwendung in der Zuverlässigkeitsanalyse.

8 Die Chapman-Kolmogoroff-Gleichungen

Die Modellierung von Computersystemen mit wahrscheinlichkeitstheoretischen Methoden basiert auf ganz einfachen Prinzipien, welche letztlich in den ChapmanKolmogoroff-Gleichungen münden, die die zeitliche Dynamik des entsprechenden Modells beschreiben. Um die Basis zu vermitteln, verzichten wir auf die übliche mathematische Strenge und beschränken uns auf ein sehr simples Modell mit zwei Zuständen 0 und 1. In Zustand 0 ist das Modell (die Maschine) ohne Auftrag (leer), in Zustand 1 wird ein Auftrag bearbeitet. Die Aufträge kommen mit einer festen Auftragsrate λ an und werden mit der Rate μ bearbeitet. Folgende Übergänge sind zwischen den beiden Zuständen möglich: 0→0: es wird kein neuer Auftrag akzeptiert, 0→1: ein Auftrag wird angenommen, 1→1: ein Auftrag wird bearbeitet, 1→0: der bearbeitete Auftrag verlässt das System, und werden durch eine Übergangswahrscheinlichkeit pij(i, j = 0, 1) charakterisiert. Diese bilden die Übergangsmatrix

p ( t ) p01 ( t ) ⎞ P(t) = ⎛⎜ 00 ⎜ p ( t ) p ( t ) ⎟⎟ 11 ⎝ 10 ⎠ für welche wir jetzt das Gesetz der zeitlichen Entwicklung, die ChapmanKolmogoroff-Gleichungen, ableiten wollen. Dabei setzen wir jeden Übergang i→j aus elementaren Schritten zusammen. Wir demonstrieren die Vorgehensweise für den Übergang 0→0 ganz ausführlich, für die Übergänge 0→1, 1→1, 1→0 verlaufen die Argumentationen völlig analog.

88

8 Die Chapman-Kolmogoroff-Gleichungen

8.1 Der Übergang 0→0 Das System startet zum Zeitpunkt t = 0 und wir setzen die Kenntnis von pij(0) (i, j = 0, 1) voraus. Zur Zeit t beobachten wir pij(t) und fragen nach der Änderung zum Zeitpunkt t + ∆t, ∆t > 0 (s. Abb. 8.1).

1

Pfad2 Pfad1

0

Z t + Δt

t Abb. 8.1 Pfade für den Übergang 0→0

Der Übergang 0→0 kann über zwei Pfade laufen, d. h. diese Wahrscheinlichkeiten müssen schon einmal aufsummiert werden w(Pfad1) + w(Pfad2); gleichzeitig sind auf einem Pfad alle Wahrscheinlichkeiten zu multiplizieren: w(Pfad1) = p00(t – 0) * p00(t + ∆t – t) = p00(t) * p00(∆t) w(Pfad2) = p01(t – 0) * p10(t + ∆t – t) = p01(t) * p10(∆t) p00(t + ∆t) = w(Pfad1) + w(Pfad2) = p00(t) * p00(∆t) + p01(t) * p10(∆t) Die Änderungen von p00 gegenüber dem Zeitpunkt t ist einfach die Differenz p00(t + ∆t) – p00(t) und bezogen auf ∆t folgt:

p00 ( t + Δt ) − p00 ( t ) p (Δt ) −1 p (Δt ) = p00 ( t ) 00 + p01 ( t ) 10 Δt Δt Δt Mit dem Grenzübergang ∆t → 0 wird die linke Seite zu p′00 ( t ) , während lim

Δt →0

p00 (Δt ) − 1 , Δt

lim

Δt → 0

p10 (Δt ) Δt

sich zu Konstanten q00 bzw. q10 reduzieren, welche nicht mehr von der Zeit abhängen, da ∆t → 0: p′00 (t) = p00(t) * q00 + p01(t) * q10

Wir erhalten eine Differenzialgleichung erster Ordnung in der Zeit.

8.2 Der Übergang 1→1

89

8.2 Der Übergang 1→1

Pfad2 1 0

Pfad1

Zeit t

t + ∆t

Abb. 8.2 Pfade zum Übergang 1→1

Wir haben die gleiche Situation wie in Abb. 8.1, nur die Rolle von 0, 1 muss konsequent getauscht werden (s. Abb. 8.2). ′ (t) p11

q11 = lim

Δt → 0

= q11 * p11(t) + q01 * p10(t) p11 (Δt ) − 1 Δt

q01 = lim

Δt → 0

p 01 ( Δt ) Δt

90

8 Die Chapman-Kolmogoroff-Gleichungen

8.3 Der Übergang 0→1

1

Pfad2

0 Pfad1 Zeit t

t + ∆t

Abb. 8.3 Pfade zum Übergang 0→1

Pfad1: p00(t) * p01(∆t) Pfad2: p01(t) * p11(∆t) p01(t + ∆t) = w(Pfad1) + w(Pfad2) = p00(t) * p01(∆t) + p01(t) * p11(∆t) Wir bilden wieder lim (p01 ( t + Δt ) − p 01 ( t )) / Δt = p′01 ( t )

Δt → 0

und erhalten p′01 ( t ) = p00(t) * q01 + p01(t) * q11

8.5 Zusammenfassung und Ableitung der Zustandsgleichungen

91

8.4 Der Übergang 1→0

1

0

Pfad2

Pfad1 Zeit

t + Δt

t Abb. 8.4 Pfade zum Übergang 1→0

Wir haben die gleiche Situation wie in Abb. 8.3, nur die Rolle von 0, 1 muss konsequent getauscht werden (s. Abb. 8.4). ′ ( t ) = p11(t) * q11 + p10(t) * q00 p10

8.5 Zusammenfassung und Ableitung der Zustandsgleichungen Jetzt können wir unsere Ergebnisse elegant und übersichtlich in einem linearen Gleichungssystem zusammenfassen:

q 01 ⎞ ⎛ p′00 ( t ) p′01 ( t ) ⎞ ⎛ p ( t ) p 01 ( t ) ⎞ ⎛q ⎜⎜ ⎟⎟ = ⎜⎜ 00 ⎟⎟ * ⎜⎜ 00 ⎟ ′ ( t ) p11 ′ (t) ⎠ p10 p10 ( t ) p11 ( t ) ⎠ q10 q11 ⎟⎠ ⎝ ⎝ ⎝  

 

 

P’(t)

P(t)

Q

In Matrixschreibweise folgt kürzer P’(t) = P(t)*Q(t) wobei P(0) und Q vorgegeben sein müssen.

92

8 Die Chapman-Kolmogoroff-Gleichungen

Die Übergänge i→j sind sehr interessant, aber in der Praxis sind die Wahrscheinlichkeiten für die Zustände 0, 1: p0(t) und p1(t) mit ihrem zeitlichen Verlauf noch interessanter (s. Abb. 8.5): p0(0) → p0(t) p1(0) → p1(t)

und p0(t) + p1(t) = 1

,t≥0

Gemäß unserer Pfadvorstellung haben wir

p0(t) = p00(t)p0(0) + p10(t)p1(0) p1(0)

p10(t)

p0(0)

0

p00(t)

t

p11(t) p1(0)

1

p0(0)

p01(t)

p1(t) = p01(t)p0(0) + p11(t)p1(0) t

Abb. 8.5 Zur Berechnung der Zustandswahrscheinlichkeiten

Also pi(t) =

∑ p (t)p (0) i = 0, 1 ji

j

j=1, 2

was leicht verallgemeinerbar ist.

G

Wir bilden den Vektor p(t) = (p 0 (t), p1 (t)) der Zustandswahrscheinlichkeiten, und sei P(t) die Matrix der Übergangswahrscheinlichkeiten, folgt damit: G G p(t) = p(0)*P(t)

8.6 Zur Lösung der Zustandsgleichungen

93

Differenzieren nach der Zeit ergibt: G G G G G p'(t) = p(0)*P'(t) = p(0)*P(t) * Q → p' (t) = p(t) * Q  

G p(t)

wobei Q die zeitunabhängige Matrix der Übergangsraten darstellt.

8.6 Zur Lösung der Zustandsgleichungen Wir haben ein Differenzialgleichungssystem erster Ordnung in der Zeit mit dem G Input p(0) = (p1 (0), p 2 (0),...p n (0)) und Q = (qij) (i,j = 0,1…n), [qij] = t–1. Wir gehen noch einmal auf ihre ursprünglichen Definitionen zurück: p ii ( Δt) − 1 Δt → 0 Δt

q ii = lim

q ij = lim

Δt → 0

p ij ( Δ t) Δt

und versuchen eine explizite Berechnung. Dazu müssen wir eine weitere Voraussetzung für die Zahl #ank der Ankünfte im Zeitintervall [0, t] machen; diese soll der Poisson-Verteilung gehorchen, also (λt) k − λt prob [#ank= k] = e k! wobei λ die übliche konstante Ankunftsrate darstellt. Wir diskutieren zunächst p00(Δt), die Wahrscheinlichkeit, dass in Δt kein Auftrag ankommt und somit der Zustand des Modells unverändert bleibt, d. h. aber #ank = k = 0 (λΔt ) (λΔt)) 2 (λΔt))3 p 00(Δt ) = e-λΔt = 1+ + + ... 1! 2! 3! Damit ist p 00(Δt ) − 1 λ λ 2Δt λ 3Δt 2 =- + + ... Δt 1! 2! 3!

und q 00 = lim

Δt → 0

p00(Δt ) − 1 = −λ Δt

da alle Terme O(Δt) verschwinden. Für die Berechnung von q01 können wir ähnlich vorgehen – wir müssen nur berücksichtigen, dass mindestens ein Auftrag ankommt. Dies ist aber das komplementäre Ereignis zu 0→0 und dann folgt einfach

94

8 Die Chapman-Kolmogoroff-Gleichungen

p01(Δt ) = 1-p00(Δt ) = 1-e-λΔt λΔt λ 2Δt 2 λ 3Δt 3 − + − ... 1! 2! 3! p (Δt ) q 01 = lim 01 =λ Δt → 0 Δt =

Für die möglichen Zustandsänderungen von 1 spielt die Abarbeitungsrate μ die Rolle von λ, d. h. bei 1→1, ein Auftrag wird bearbeitet, und es passiert nichts: p11(Δt ) = e-μΔt

→ q11 = -μ

Der Übergang 1→0 ist dann das komplementäre Ereignis zu 1→1, und wir erhalten: p10(Δt ) = 1-p11(Δt ) = 1 − e -μΔt → q10 = μ Damit haben wir alle Größen zusammen, um Chapman-Kolmogoroff für dieses Modell explizit hinzuschreiben und zu lösen ⎛ -λ λ ⎞ ⎟⎟ (p0'(t), p1'(t)) = (p0(t), p1(t))*⎜⎜ ⎝ μ − μ⎠ p0(0) = 1 und p1(0) = 0 Da p0(t), p1(t) für alle t ≥ 0 Wahrscheinlichkeiten mit 0 ≤ p0(t), p0(t) ≤ 1 und p0(t) + p1(t) =1, können die Lösungen für die Chapman-Kolmogoroff-Gleichungen keine exponentiell ansteigenden Funktionen sein – oszillierende Lösungen scheiden ebenfalls aus. Übrig bleiben Konstanten und exponentiell abfallende Funktionen der Art: a + be–αt welche für große Zeiten sich praktisch nicht mehr ändern, d. h. ihre Ableitungen verschwinden ebenfalls lim p0,1(t) = π 0,1 lim p'0,1(t) = 0 t →∞

t →∞

Das Differenzialgleichungssystem reduziert sich damit auf ein simples, homogenes, lineares System: ⎛ -λ λ ⎞ ⎟⎟ (0,0) = (π 0, π1)*⎜⎜ ⎝ μ −μ⎠ 0 = π 0 (-λ ) + π1μ → π1 = (λ / μ) * π 0

8.6 Zur Lösung der Zustandsgleichungen

95

π 0 + π1 = 1 = π 0 + ( λ / μ ) * π 0 = 1 π0 =

1 1+

λ μ

π1 =

λ/μ 1 + (λ / μ )

Beide Lösungen hängen nur von ρ = λ/μ ab und haben folgenden Verlauf:

Abb. 8.6 Stationäre Zufallswahrscheinlichkeiten

Der Punkt ρ = 1 entspricht der Situation, dass Ankunfts- und Verarbeitungsrate identisch sind (s. Abb. 8.6). Das Auffinden der zeitabhängigen Lösungen folgt den üblichen Standardmethoden. Wir nutzen p1(t) = 1 – p0(t) aus, so dass p0’(t) + (λ + μ)p0(t) = μ und wählen die Variation der Konstanten. Mit den Anfangsbedingungen p0(0) = 1, p1(0) = 0 (das Modell ist bei t = 0 leer) folgt: 1 ρ p 0(t) = e-(1+ ρ)μt + 1+ ρ 1+ ρ p1(t) =

ρ (1-e-(1+ ρ)μt ) 1+ ρ

Es ist offensichtlich, dass unsere asymptotischen Lösungen π0, π1 reproduziert werden.

96

8 Die Chapman-Kolmogoroff-Gleichungen

8.7 Zwei konkrete Modelle über Reserve Wir wollen jetzt das obige zweidimensionale Modell in zweifacher Hinsicht verändern – einmal bezüglich der Systemdynamik und zum anderen über die Zahl der Zustände. Wie im Kap. 7 sollen zwei DB-Server modelliert werden, wobei das System funktionstüchtig ist, wenn einer arbeitet. Dies läuft unter dem Namen kalte Reserve, der Zustand 0 beschreibt zwei funktionstüchtige Server; fällt der aktuelle arbeitende Server aus, übernimmt die Reservemaschine diese ohne Zeitverzögerung (Zustand 1). Fällt Server 2 während der Reparatur auch noch aus, erreichen wir Zustand 2,

λ Ausfallrate λ 0

1

2

μ Reparaturrate Abb. 8.7 Systemdynamik der kalten Reserve

von dem es keine Rückkehr mehr gibt (s. Abb. 8.7). Die Zustandswahrscheinlichkeiten p0(t), p1(t) und p2(t) gehorchen nach Chapman-Kolmogoroff der Dynamik: p′0 ( t ) = −λp0 ( t ) + μp1 ( t ) p1′ ( t ) = λp0 ( t ) − (λ + μ)p1 ( t ) p′2 ( t ) = λp1 ( t )

mit den Anfangswerten p0(0) = 1 und p1(0) = 0. Die Gleichungen für p0, p1 entkoppeln von p2 und Einsetzen liefert p1′′( t ) + (2λ + μ) * p1′ ( t ) + λ2p1 ( t ) = 0

Zum Lösen dieser linearen Differenzialgleichung 2. Ordnung machen wir den Ansatz p1 ( t ) = eνt . Es folgt ν 2 + (2λ + μ)ν + λ2 = 0 , sodass ν1, 2 = −

λ 2λ + μ μ ± * D , D2 = 1 + 4 > 0 2 2 μ

8.7 Zwei konkrete Modelle über Reserve νt

97

ν t

Damit haben wir zwei Basislösungen e 1 bzw. e 2 und die Gesamtlösung lautet p1 ( t ) = Aeν1t + Beν 2 t . Da p1(0) = 0, ist B = -A und explizites Einsetzen ergibt

p1 ( t ) = 2Ae

−

2λ + μ t 2

⎡ μ tD − μ tD ⎤ ⎢e2 − e 2 ⎥ *⎢ ⎥ 2 ⎢ ⎥ ⎣ ⎦

wobei A noch festzulegen ist. Wir bestimmen p0(t) über λp0 ( t ) = p1′ ( t ) + (λ + μ)p1 ( t )

1 − p0 (t) = e D

⎛ μ 2λ + μ ⎜ 2 tD t e 2 ⎜ ⎜⎜ ⎝

−e 2

μ − tD 2

μ ⎞ ⎛ μ ⎞ ⎟ − 2λ + μ t ⎜ e 2 tD + e − 2 tD ⎟ 2 ⎟+e ⎜ ⎟ 2 ⎟⎟ ⎜⎜ ⎟⎟ ⎠ ⎝ ⎠

⎛λ⎞ die Konstante A berechnet sich über p1(0) = 0 zu ⎜⎜ ⎟⎟D −1 . ⎝μ⎠ Da 2λ + μ = (2ρ + 1)μ und −

(

)

2λ + μ μ μ t + tD = − 2ρ + 1 − 4ρ + 1 t < 0 2 2 2

denn 2ρ + 1 − 4ρ + 1 ~ 2ρ mit ρ ≥ 0 , konvergieren bei μt → ∞ alle Exponentialterme gegen null, sodass

π0 = lim p 0 ( t ) = 0 , π1 = lim p1 ( t ) =0 t →∞

t →∞

π2 = 1 wegen π0 + π1 + π2 = 1

Die folgende Abb. 8.8 zeigt das zeitliche Verhalten für ρ = 1 (Ausfall = Reparaturrate) – man erkennt, wie rasch der obige stationäre Zustand sich einstellt. Für ρ < 1 hält die Nichtstationarität deutlich länger an, bei ρ > 1 erreichen wir π2 = 1 noch schneller. Daher ist natürlich die Zeitspanne bis zum Erreichen von 2 interessant – man nennt sie die Lebensdauer des Systems.

98

8 Die Chapman-Kolmogoroff-Gleichungen

Abb. 8.8 Zeitlicher Verlauf der Zustandswahrscheinlichkeiten

Zur Berechnung von benötigt man F( t ) , die Verteilung der Überlebenswahrscheinlichkeit, diese ergibt sich zu F( t ) = p 0 ( t ) + p1 ( t ) . Die gesuchte mittlere Überlebenszeit [10] ist ∞

∞

∫

∫

< t 02 >= dt F( t ) = dt (p0 ( t ) + p1 ( t )) 0

0

wobei die Herleitung unter 1 zu finden ist.

1

Der Mittelwert einer Zufallsgröße t ergibt sich über die Verteilungsdichte f(t) zu

∞

∞

0

0

= ∫ dt * t * f ( t ) = ∫ dt * t * F′( t ) wobei F(t) = prob(tL ≤ t) die Verteilung darstellt. Die zweite Form legt eine partielle Integration mit u = t, u’ = 1, υ’ = F’(t) nahe:

[

]∞

∞

∞

= t * F( t ) 0 − ∫ dt *1 * F( t ) = lim(t * F( t )) − ∫ F( t )dt

0

t →∞

0

Stellt t die Überlebensdauer dar, ist es günstiger, nach der Überlebenswahrscheinlichkeit und deren Verteilung F( t ) = prob( t L > t ) = 1 − F( t )

zu analysieren:

8.7 Zwei konkrete Modelle über Reserve

99

Für eine bessere Transparenz und um ein Gefühl für diese Art von Rechnung zu bekommen, betrachten wir erst den einfachen Fall μ = 0, d. h. es findet keine Reparatur statt. Die Lösung der Chapman-Kolmogoroff-Gleichungen lauten in diesem Fall p 0 ( t ) = e − λt und p1 ( t ) = (λt )e −λt , sodass ∞

∫

< t μ02= 0 > k = dt (1 + λt )e− λt = 0

∞

∫

1 d(λt )(1 + λt )e− λt λ 0

∞

=

∫

1 2 dτ(1 + τ)e − τ = λ λ 0

Dieses Ergebnis leuchtet sofort ein, denn der Prozess des Ausfallens kann zweimal auftreten. Im Reparaturfall μ > 0 kann die Lebensdauer < t 02 > k nur größer werden – zu erwarten ist ein Korrekturterm proportional μ. Wir definieren eine neue Konstante a = (2ρ + 1) / D = (2ρ + 1) / 4ρ + 1 sowie die neue Variable τ = μtD/2 und bilden

wieder die Verteilung F = p0 + p1 = e− aτ (a sinh τ + cosh τ)

wobei sinh τ = (eτ – e–τ)/2 und cosh τ = (eτ + e–τ)/2 die üblichen Hyperbolischen Funktionen darstellen. Da τ = (μ*t*D)/2, ist dt = (2/(μ*D))dτ, sodass ∞

< t 02 > k =

∫

2 dτ(a sinh τ + cosh τ) μD 0

⎡

t

t →∞ ⎣

⎤

0

= lim ⎢ t * F( t ) − ∫ dtF( t )⎥

⎦

⎡ ⎤ = lim ⎢ t * F( t ) − t + ∫ dt (1 − F( t ))⎥ t →∞ ⎣ 0 ⎦ t ⎡ ⎤ = lim ⎢− t (1 − F( t ) + ∫ dt (1 − F( t ))⎥ t →∞ ⎣ 0 ⎦ t

[

]

∞

= lim t * F( t ) + ∫ dt F( t ) t →∞

0 ∞

Für Exponentialverteilungen verschwindet der Grenzwert und es bleibt = ∫ dt F( t ) 0

100

8 Die Chapman-Kolmogoroff-Gleichungen

=

2 1 2(4ρ + 1) 2ρ + 1 1 2ρ + 1 * * = μ 4ρ + 1 4ρ2 4ρ + 1 μ ρ2

Mit ρ = λ/μ folgt < t 02 > k =

2 1 2 μ + = + 2 λ ρλ λ λ

Man beachte bei dem Korrekturterm μ/λ2 die starke Abhängigkeit von λ2, welche seinen Einfluss erheblich beschränkt. Bei festen λ können wir die dimensionslose Größe λk = 2 + 1/ρ bilden, welche für Vergleiche besser geeignet ist. Wenn z. B. die beiden Server immer parallel laufen (heiße Reserve, s. Abb. 8.9), was in modernen redundanten Systemen häufig realisiert wird, dann haben wir eine andere dynamische Situation, μ

0

1

2 λ

2 Abb. 8.9 Doppeltes System der heißen Reserve

welche sich in den folgenden Differenzialgleichungen wiederfindet p′0 ( t ) = −2λp0 ( t ) + μp1 ( t ) p1′ ( t ) = 2λp 0 ( t ) − (λ + μ)p1 ( t ) , p′2′ ( t ) = λp1 ( t )

Im Prinzip können wir jetzt genauso wie beim System der kalten Reserve vorgehen. Zunächst der Fall μ = 0, es folgt Fh ( t ) = e −2λt + 2e − λt (1 − e − λt ) , < t μ02= 0 > h =

31 2λ

Bei festen λ ergibt der Vergleich der beiden Systeme (kalte und heiße Reserve) ohne Reparatur λ < t μ02= 0 > k = 2 , λ < t μ02= 0 > h =

3 2

eine um 50% schlechtere Lebensdauer des „heißen“ Systems.

8.7 Zwei konkrete Modelle über Reserve

101

Der Reparaturfall μ > 0 folgt ebenfalls dem Muster der kalten Reserve – die entsprechende Rechnung resultiert in λ < t 02 > h =

3 1μ 3 1 + = + 2 2 λ 2 2ρ

Abbildung 8.10 demonstriert dann die Verlaufsunterschiede in beiden Modellsystemen:

Abb. 8.10 Lebensdauervergleich von kalter und heißer Reserve

Wenn also der Umschaltprozess ohne Verzögerung verläuft, ist das System der kalten Reserve wegen seiner deutlich längeren Lebensdauer, auch bei Reparaturen, zu bevorzugen.

9 Von der Lust am Modellieren

Die im vorigen Abschnitt entwickelten Modellvorstellungen lassen sich nun beliebig ausbauen und mit einer gewissen Lust an Mathematik ergeben sich interessante Einblicke – wie realitätsnah diese sind, hängt natürlich von den Voraussetzungen ab. Wir unterstellen einmal durchgängig exponentiell verteilte Zwischenankunfts- und Bearbeitungszeiten und geben uns dem Vergnügen hin, durch simple Umformungen einige, hoffentlich transparente und übertragbare Ergebnisse aus Modellanalysen und Beispieldiskussionen hervorzubringen.

9.1 M/M/1/∞ und die Skalierung Wir beginnen mit dem einfachsten Modell des letzten Abschnitts, in welchem ein Strom von Forderungen mit einer Rate λ auf einen Server trifft, der diese mit der Rate μ bedient. Die offizielle Bezeichnung ist M/M/1/∞, da Ankunfts- und Bearbeitungszeit jeweils exponentiell verteilt sind (vom Typ Markoff), ein (1) Server existiert und unendlich (∞) viele Warteplätze vorhanden sein sollen. Die mittlere Verweilzeit in diesem System berechnet sich über das 1. Little’sche Gesetz λ * = < k > zu ρ λ 1 = * 1− ρ μ 1− ρ 1 1 1 < t V >= * =< t S > μ 1− ρ 1− ρ

λ < t V >=< k >=

da = 1/μ.

104

9 Von der Lust am Modellieren

Was geschieht mit , wenn wir die Service-/Bearbeitungszeit auf den p-ten Teil herabsetzen können, d. h. → /p? Es folgt: =

< tS > 1

* = S ρ p p−ρ 1− p

und damit können wir das Verhältnis von alter () und neuer () Verweilzeit, den Speed-Up S(p) diskutieren: ρ < tS > 1− < tV > p−ρ p 1− ρ = = = p* S(p) = < t V ( p) > < t S > 1 − ρ 1− ρ p−ρ

Für große p verhält sich S(p) ~ p, dies versteht man im Prinzip unter Skalierung. Zur Übung wird angeregt, eine obere Schranke für den Speed-Up der Wartezeit (p²/ (1 – ρ)) auszurechnen.

9.2 Das Modell M/M/1/B mit endlichem Wartepool Eine vernünftige Variante des Standardmodells M/M/1/∞ besteht darin, nur endlich viele Warteplätze zuzulassen, und wenn diese voll sind, alle weiteren Forderungen abzuweisen. Man spricht in diesem Fall auch von einem Verlustsystem M/M/1/B und dieser Sachverhalt impliziert folgendes Zustandsdiagramm: λ 0

λ 1

μ

λ 2

μ

...

λ

k–1

k

...

μ

mit den Zustandswahrscheinlichkeiten π0, π1... πB. Man sieht sofort k = 1...B λπk–1 = μπk ρ = λ/μ, πk = ρπk–1 πk = ρkπ0

B–1

B μ

9.2 Das Modell M/M/1/B mit endlichem Wartepool

105

Die noch freie Konstante π0 (die Wahrscheinlichkeit, dass dieses System leer ist) wird über die Normierung bestimmt B

1=

∑

B

π k = π0

k =0

∑ k =0

ρ k = π0 *

1 − ρB +1 1− ρ

1− ρ π0 = 1 − ρB +1

Der nächste Schritt besteht in der Bestimmung der relevanten Leistungsgrößen wie Wartewahrscheinlichkeit pW = 1 – π0 Durchsatz DB(ρ) Blockierungswahrscheinlichkeit pB Beginnen wir mit pW: p W = 1 − π0 = 1 −

1− ρ 1 − ρB = ρ * 1 − ρB +1 1 − ρB +1

und tragen diese Größe gegen die Auslastung ρ auf (s. Abb. 9.1). B = 10 B=3

Abb. 9.1 Wartewahrscheinlichkeit für M/M/1/B

106

9 Von der Lust am Modellieren

Man sieht sofort, dass nach einem fast linearen Anstieg im Bereich 0 ≤ ρ ≤ 1 die Wartewahrscheinlichkeit für höhere Auslastungsbereiche im Sättigungsbereich ist. Für jeden Zustand k = 1, 2, 3... kann es eine Verarbeitungsrate μk geben, die den maximalen Durchsatz in diesem Zustand festlegt. Da jeder Zustand k nur mit einer Wahrscheinlichkeit πk vorkommt, ist der reale Durchsatz πk*μk und der Gesamtdurchsatz ergibt sich zu DB (ρ) =

∑ k ≥1

B

μ k * πk =

∑

B

μ * πk = μ

k =1

∑π

k

= μ(1 − π0 ) = μpW

k =1

↑ in diesem Modell und mit der gerade diskutierten Formel für pW gilt D B (ρ) = μ * ρ

1 − ρB

= λ*

1 − ρB

1 − ρ B+1 1 − ρ B+1 Im M/M/1/∞-Modell ist D(ρ) = μ * pW = μ * ρ = λ, sodass wir sehr einfach den Unterschied beider Modelle verstehen können.

D(ρ) – DB(ρ) = λ − λ = λ * ρB

1 − ρB 1 − ρB ( 1 = λ − ) 1 − ρB+1 1 − ρB +1

1− ρ 1 − ρB +1

Da pB = ρB(1 – ρ)/(1 – ρB+1) die Wahrscheinlichkeit ist, dass alle Warteplätze belegt sind, stellt λ*pB genau den Anteil der Forderungen dar, der abgewiesen werden muss. Der Verlauf von pB zeigt, dass diese Größe für viele Warteplätze, also B >> 1 im Bereich 0 ≤ ρ ≤ 1 vernachlässigbar ist [4]. B1 Wir betrachten einen Router mit mehreren Kanälen, pro Kanal sind B Pufferplätze vorgesehen. Wie groß muss B sein, wenn wir die Blockadewahrscheinlichkeit p(B) vorgeben. Es gilt 1− ρ p(B) = ρB 1 − ρB +1 und dies muss nach B aufgelöst werden. Wir setzen x = ρB und erhalten p(B) =

1− ρ x 1− ρ* x

=>

x=

p(B) 1 − ρ + ρ * p(B)

9.3 Ein weiteres Verlust-Modell mit p Prozessoren

107

Da 0 ≤ ρ ≤ 1 und 0 < p(B) < 1 ist sicherlich ρp(B) 20) und bei p(B): 10-2 => 10-6 So folgt im Lastbereich 0,5 ≤ ρ ≤ 0,6, dass zwischen 5 und 10 Pufferplätze pro Kanal bei p(B) = 10–3 benötigt werden.

9.3 Ein weiteres Verlust-Modell mit p Prozessoren Ein weiteres Modell, welches einen Teil von Forderungen ablehnt, weil seine Kapazität es nicht zulässt, ist M/M/p/0. Das bedeutet Ankunft- und Bedienprozess sind vom Typ Markoff (M), statt einem Prozessor haben wir p gleichartige mit einer Servicerate μ für jeden einzelnen – ein Wartepool existiert jedoch nicht (0).

108

9 Von der Lust am Modellieren

Ein Beispiel wären die p Einwahlmodems in ein Providernetz, λ wäre die mittlere Zahl der Einwahlversuche pro Zeiteinheit und 1/μ die mittlere Belegungsdauer. Die möglichen Zustände dieses Modells sind durch die Anzahl k der belegten Prozessoren/Bedieneinheiten (Modem) gekennzeichnet. Es gilt k = 0, 1, 2,... p und damit folgendes Zustandsdiagramm λ

λ

0

λ

1

2

μ

...

2μ π1

π0

k-1

λ k

k*μ πk–1 πk

π2

...

p-1

p

p*μ πp–1 πp

Im statistischen Gleichgewicht gilt für die Zustandswahrscheinlichkeiten πk: λ * πk −1 = kμ * πK

k = 1 ... p

λ ρ πk = πk −1 = πk −1 k *μ k λ ρ= μ

Durch Ausprobieren für k = 1, 2, 3,... kann man die Lösung von πk = (ρ/k) πk–1 relativ einfach zu ρk π= π0 k = 1, 2, ... p k! raten. Wie immer ist die freie Konstante π0 über die Normierung festgelegt p

p

1=

∑π

k

= π0

k =0

ρk

∑ k! = e k =0

ρ

Γ(p + 1, ρ) π0 Γ(p + 1,0)

wobei die Γ-Funktion (s. Abb. 9.2) wie folgt definiert ist ∞

∫

Γ(p + 1,0) = pΓ(p,0) = p!= dt e − t t p 0

∞

∫

Γ(p + 1, ρ) = dt e − t t p ≤ Γ(p + 1,0) ρ

9.3 Ein weiteres Verlust-Modell mit p Prozessoren

109

Diese Funktion hat nur einen ungewöhnlichen Namen, vom Verlauf her ist sie völlig unkompliziert Г(p + 1, ρ) p!

ρ ρ≤1

Γ(p + 1, ρ) ≈ p! Γ(p + 1, ρ) ≈ ρpe–ρ

ρ >> 1

Abb. 9.2 Verlauf der unvollständigen Γ- Funktion

und mit ihrer Hilfe folgt für die Zustandswahrscheinlichkeiten π0 = e − ρ

Γ(p + 1,0) Γ(p + 1, ρ)

πk = e −ρ

Γ(p + 1,0) ρk * Γ(p + 1, ρ) k!

Damit sind wir in der Lage, die Leistungsgrößen wie Blockier-/Abwehrwahrscheinlichkeit pB, den Durchsatz D oder die mittlere Anzahl belegter Prozessoren/Bedienstationen zu berechnen und zu analysieren. Die Blockade- oder Abwehrwahrscheinlichkeit ist ganz einfach über die Besetzung aller p Prozessoren definiert p B = πk = p =

Γ(p + 1,0) − ρ ρp *e * p! Γ(p + 1, ρ)

Mit einigen Umformungen, insbesondere Г(p + 1, 0) = p! ergibt sich p B = ρp * e −ρ

1 Γ(p + 1, ρ)

110

9 Von der Lust am Modellieren

Nutzen wir noch die Relation Г(p + 1, ρ) = pГ(p, ρ) + ρpe–ρ aus, so folgt schließlich pB = 1− p

Γ(p, ρ) Γ(p + 1, ρ)

Die Zahl der akzeptierten Prozesse oder die effektive Ankunftsrate oder der Durchsatz ergibt sich dann zu (1 − p B )λ = λ

pΓ(p, ρ) Γ(p + 1, ρ)

Hält man μ fest und variiert ρ, indem man λ verändert, so lässt Abb. 9.3 das Sättigungsverhalten des Durchsatzes bei steigender Last (ρ) erkennen.

8

p = 10

6

p=5

4

p=2

2

p=1

0 0

2

4

ρ

6

8

10

Abb. 9.3 Durchsatzverhalten von M/M/p/0

Ähnliches gilt für die Auslastung ρ(S) in diesem Systemmodell: ρ(S) =< t S > *D =

1 λpΓ(p, ρ) Γ(p, ρ) * =ρ pμ Γ(p + 1, ρ) Γ(p + 1, ρ)

denn im Bereich 0 ≤ ρ ≤ 1 ist Г(p + 1, ρ) ≈ p! und damit ρ(S) ~ ρ/p, also ein schwacher linearer Anstieg. Für ρ >> 1 gilt Г(p + 1, ρ) ~ ρpe–ρ, sodass ρ(S) ≈ 1. Interessant ist nun /p, d. h. die mittlere Anzahl von Forderungen pro Prozessor, diese ist mit der Auslastung ρ(S) identisch. Solange /p < 1, wird keine Blockade/Abweisung von Forderungen erfolgen müssen – erst bei /p ≥ 1 tritt dieser Fall ein und man müsste eventuell weitere Prozessoren hinzunehmen. Betrachtet man daher die Abhängigkeit von p, ρ bleibt fest, so erhält man einen relativ schwachen Abfall in p (s. Abb. 9.4).

9.4 Der Fall unendlich vieler Prozessoren

111

p 0,9 0,8

ρ=5

0,7 0,6 0,5

ρ=2

0,4 0,3

ρ=1

0,2 0,1

ρ = 1/2 1

2

3

4

5

p Abb. 9.4 Verlauf der Auslastung /p

Γ(p, ρ) =ρ p Γ(p + 1, ρ)

Dieser geht für höhere Auslastungswerte ρ fast in eine Konstante über, sodass eine Hinzunahme weiterer Prozessoren p kaum noch einen Effekt zeigt.

9.4 Der Fall unendlich vieler Prozessoren Vor dem Hintergrund moderner Hochleistungssysteme mit mehreren tausend bzw. hunderttausend Prozessoren liegt es nahe, einmal den Fall p → ∞ beim M/M/p/0-Modell zu untersuchen. Die Zustandsübergänge ändern sich nicht, es gilt λπ0 = 1 * μ * π1 λπ k = k * μ * πk +1 für k = 1…∞

Wie vorhin lässt sich die Lösung zu πk = (ρk / k!)π0 leicht erraten, die Wahrscheinlichkeit π0 wird standardmäßig über die Normierung festgelegt. 1=

∞

∑ k =0

π k = π0

∞

∑ρ k =0

k

/ k! = π0eρ ⇒ π0 = e −ρ

112

9 Von der Lust am Modellieren

Und damit haben wir πk = (ρ k / k!)e −ρ , k = 0…∞. Man beachte, dass dieser Fall mit unendlich vielen Prozessoren sehr viel leichter zu behandeln ist als mit festen p! Wir berechnen zunächst den Mittelwert der aktiven Prozessoren ∞

=

∑

k * πk =

k =1

= ρe − ρ

∞

ρk

∑ k k! e

ρ

k =1

∞

ρk −1

∑ (k − 1)! = ρe

−ρ ρ

e =ρ

k =1

und mit Hilfe des 1. Little’schen Gesetzes die mittlere Verweilzeit λ = = ρ = λ/μ, d. h. aber = (1/μ). Für den Durchsatz ∞

D = ∑ μk * πk , μk = k * μ k =1

folgt auf die gleiche Weise D = μρ = λ und damit werden alle ankommenden Aufträge in der gleichen Zeit abgearbeitet – eine Blockade oder Abweisung wie im endlichen Fall erfolgt klarerweise nicht.

9.5 Modelle mit variabler Last In den bisherigen Situationen ist die Last, ausgedrückt über die Ankunftsrate λ, immer als konstant angenommen – eine Voraussetzung, welche in vielen Fällen (selbst im Rahmen einer Modellierung) nicht besonders zutreffend ist. Nahe liegt eine Abhängigkeit von der Zeit λ = λ(t), diese haben wir aber durch unsere Gleichgewichts- und Mittelwertsbetrachtungen praktisch eliminiert. In gewisser Hinsicht wird sie jedoch durch die Abfolge der möglichen Zustände k = 0, 1, 2, 3,... ersetzt. Wir greifen diesen Aspekt auf und postulieren als Ersatz eine Abhängigkeit der Form λ = λ(k). Ein gutes Beispiel dafür ist die Fluss-Kontrolle oder Fluss-Steuerung bei Datenübertragungsprotokollen (s. Abb. 9.5). Zum Beispiel wenn der Sender (S) den Empfänger (E) mit Datenpaketen überflutet

9.5 Modelle mit variabler Last

E

113

tE λ

stop; λ’< λ

λ’

S

tS

Abb. 9.5 Fluss-Kontrolle bei DFÜ

und die Senderate vom Empfänger heruntergesetzt wird λ λ’ < λ. Solche Mechanismen sind in Modemprotokollen, aber auch in TCP/IP verankert. Wir werden dazu zwei Modelle diskutieren – eines, welches Zustände mit k >> 1 gar nicht zulässt und leicht zu analysieren ist. Das andere ist etwas unhandlicher, wir können aber daran besser die Methode, Submodelle zu einem Ganzen zusammenzusetzen, besser verstehen. Wir beginnen mit dem leichteren Fall, dass die Last zustandsabhängig kontinuierlich abnimmt λ(k) = λ/k für k = 1, 2, 3,... – dies entspricht folgendem Zustandsdiagramm λ/1 0

λ/2 1

μ π0

λ/3 2

μ π1

λ/k 3

...

μ

μ

π2

πk-1

Im Gleichgewicht gilt ⎛λ⎞ ⎛λ⎞ ⎜ ⎟π0 = μπ1 sowie μπk = ⎜ ⎟πk −1 1 ⎝ ⎠ ⎝k⎠ und damit πk =

ρ πk −1 k

k–1

k = 1,2,3,...

ρ=

λ μ

πk

k

114

9 Von der Lust am Modellieren

Die Lösung kann durch sukzessives Einsetzen leicht zu πk =

ρk π0 k!

k = 1,2,3,...

geraten werden. Natürlich bestimmen wir die Wahrscheinlichkeit für das leere System π0 wieder über die Normierung: 1=

∞

∑π

k

= π0

k =0

∞

ρk

∑ k! = π e

ρ

0

k =0

Die Summe im obigen Ausdruck ist mit Maple [11] leicht zu bewerkstelligen. Damit gilt π0 = e − ρ

πk =

ρk −ρ e k!

k = 1,2,3,...

und wir können die Leistungsgrößen berechnen, als Erstes die Wartewahrscheinlichkeit pW = 1 – π0 = 1 – e–ρ

pw 1/e ~ 1/3

0

0,2

0,4

0,6

0,8

1

ρ

Abb. 9.6 Wartewahrscheinlichkeit im verzögerten System

Im verzögerten System muss bei höherer Last deutlich weniger wahrscheinlich (30%) gewartet werden (s. Abb. 9.6). Die mittlere Anzahl von Forderungen/Prozessen im System berechnet sich zu < k >=

∞

∑ k =1

kπ k = e − ρ

∞

∑ k =1

∞

k

ρk ρk −1 = e − ρρ = e−ρρeρ = ρ k! ( k − 1 )! k =1

∑

9.5 Modelle mit variabler Last

115

und zeigt damit im Vergleich zum Standardsystem M/M/1/∞ einen simplen Verlauf in Abhängigkeit von ρ – vor allem im Überlastbereich ρ > 1/2 sind bis zu 30% weniger Prozesse aktiv. Dieser Sachverhalt wird noch verständlicher, wenn wir die Wahrscheinlichkeit p(n) berechnen, dass mindestens n Forderungen/Prozesse im System sind: p( n ) =

∞

∑

πk = 1 −

k =n

n −1

∑

πk = 1 −

k =0

n −1

ρk −ρ Γ(n, ρ) ρ e = 1 − e −ρ e Γ(n,0) k! k =0

∑

Wir vergleichen p(n) mit ρn, dem Wert für das Standardsystem M/M/1/∞ ρn

p(n)

Abb. 9.7 Vergleich mit dem M/M/1/∞-Modell

und konstatieren, dass im lastabhängigen Modell höhere n-Werte praktisch nicht vorkommen (s. Abb. 9.7). Bestimmt man den Durchsatz D(λ) und die Auslastung ρ(S), so muss man berücksichtigen, dass λ zustandsabhängig ist – sinnvoll ist daher < λ >=

λ

∞

∑λ π

k k

k =0

zu substituieren. Im Gleichgewicht wird D(λ) = , die explizite Rechnung ergibt D(λ ) =

∞

∞

∞

k ⎛ λ ⎞ ρk ρk −1 ⎛ λ ⎞ ρ −ρ −ρ = μe −ρ ⎜ ⎟ e = e μ ⎜⎜ ⎟⎟ k + 1 ⎠ k! (k − 1)! μ (k + 1)! k =0 ⎝ k =0 ⎝ ⎠ k =0

∑

= μe −ρ (eρ − 1) = μ(1 − e −ρ )

∑

∑

116

9 Von der Lust am Modellieren

Für ρ =

⎛1⎞ 1 , ρ(S) = ⎜⎜ ⎟⎟ * μ(1 − e −ρ ) = 1 − e −ρ μ ⎝μ⎠

d. h. bis auf konstante Faktoren haben wir wiederum die (1 – e–ρ)-Abhängigkeit. Als letzte Leistungsgröße bleibt uns noch die Diskussion der mittleren Verweilzeit , welche natürlich am einfachsten über das 1. Gesetz von Little * = bestimmt wird: < t V >=

ρ 1 ρ2 = = * −ρ < λ > μ(1 − e ) λ 1 − e −ρ

Für ρ m

ρ = λ/μ

ρ^ = ρ/m

9.7 Leistungsunterschiede

119

Im Standardverfahren würde man in diesem zusammengesetzten Modell jetzt π0 über die Normierung berechnen. Da wir nur an bzw. interessiert sind, soll die Normierungsrechnung möglichst vermieden werden. Wir argumentieren = + , = 1/μ d. h. wir brauchen noch . Solange die Zahl der Anforderungen kleiner als die Zahl der Prozessoren ist, gibt es keine Wartezeit, also trägt nur das rechte Submodell dazu bei. Mit dem 2. Little’schen Gesetz λ* = benötigen wir eigentlich nur die mittlere Zahl der wartenden Forderungen < q >=

∞

∑ ( k − m) π

k

= πm

k =m

∞

∑ (k − m)ρˆ

k −m

k =m

= πm (0 + 1 * ρˆ 1 + 2 * ρˆ 2 + ...) = πm

∞

∑ kρˆ

k

k =1

= πm

ρˆ (1 − ρˆ ) 2

Für den letzten Schritt der Summation setzen wir Maple [11] ein. Hinsichtlich der weiteren Überlegungen zeigt es sich, dass es günstig ist, die Wartewahrscheinlichkeit pW (wie in der letzten Analyse) einzuführen pW =

∞

∑π

k

= πm

k =m

∞

∑ ρˆ

k −m

k =m 2

= π m (1 + ρˆ + ρˆ + ρˆ 3 + ...) 1

= πm

∞

∑ ρˆ

k

k =0

=

πm 1 − ρˆ

Da < q >= πm

ρˆ π ρˆ ρˆ = m * = pW 2 1 − ρˆ (1 − ρˆ ) 1 − ρˆ 1 − ρˆ

folgt < t W >=

1 ρˆ 1 λ p 1 1 p * pW = * * W = * * W ˆ ˆ λ 1− ρ λ m * μ 1 − ρ μ m 1 − ρˆ

Da = 1/μ ergibt sich letztlich < t W > = < tS >

pW m(1 − ρˆ )

120

9 Von der Lust am Modellieren

Als Problem bleibt natürlich die explizite Ausformulierung der Wartewahrscheinlichkeit pW, wir verzichten darauf und schätzen (brutal aber richtig) pW < ρ/m = ^ρ (s. Abb. 9.10). M/M/1/∞ M/M/m/∞

pW 1

ρ

ρ/m pW (exakt)

0 0

1

m

ρ

Abb. 9.10 Wartewahrscheinlichkeit im M/M/m/∞-Modell

Mit dieser Abschätzung folgt für die mittlere Wartezeit < t W > ≤ < tS >

ρˆ m(1 − ρˆ )

und für die mittlere Verweilzeit einer Forderung ⎞ ⎛ ρˆ ⎟⎟ < t V > = < t S > + < t W > ≤ < t S > ⎜⎜1 + ⎝ m(1 − ρˆ ) ⎠ wobei 0 ≤ ρ^ ≤ 1 oder 0 ≤ ρ ≤ m. Wir demonstrieren die Einsatzfähigkeit des obigen Resultats an einem etwas ausführlicheren Beispiel [6]. Ein Datenbank-Server empfängt 40 req/sec, seine mittlere Service-Zeit für ein req ist 20 msec = 20*10–3 sec. Mit diesen Werten folgt für die Ankunfts- und Bearbeitungsraten

λ = 40 req/sec, μ = 1/ = 1/20*103 sec–1 = 50 req/sec von denen wir annehmen, dass beide die Mittelwerte einer Exponentialverteilung sind. In diesem Fall kann der Server durch ein M/M/1/∞-Modell modelliert werden

9.7 Leistungsunterschiede

ρ=

λ 40 4 = = (80%) μ 50 5

121

(hohe Auslastung!)

1 1 1 = < tS > * = 5 < t S > = 100 m sec * 4 μ 1− ρ 1− 5

< t V >=

Da = + , ist = 80 msec (4 ), d. h. 80% der Verweilzeit gehen mit Warten verloren. Zur Verbesserung dieser Situation stehen folgende Alternativen zur Auswahl: a) neuer Prozessor mit = /2 b) zwei Prozessoren mit Wir analysieren zunächst die Alternative (a) mit dem schnelleren Prozessor: μ=

1 < tS > a

=

2 2 , ρ = λ* < t S > / 2 = (40%) < tS > 5

Damit haben wir schon einmal eine deutliche Lastverminderung. Die neue mittlere Verweilzeit berechnet sich wie , < tS > 50 1 5 = * < tS > = m sec * 3 1− 2/5 6 2 20 1 ⎛5 1⎞ > = < t V a > − < t Sa > = ⎜ − ⎟ < t S > = < t S > = m sec 3 3 ⎝6 2⎠

< t Va > = < t Wa

Hinsichtlich der Verbesserung von Warte- und Verweilzeit sind die Gewinne eklatant < tV > < tV > a

=

5 < tS > < tW > 4 < tS > = 6, = = 12 a 5 / 6 < tS > < t W > 1/ 3 < tS >

wobei vor allem die Wartezeitverminderung beachtenswert ist.

122

9 Von der Lust am Modellieren

Die Alternative (b) besteht aus dem Einsatz von zwei Prozessoren – beide mit der Service-Zeit . Das entsprechende theoretische Modell ist M/M/2/∞, d. h. m = 2. Mit unseren vorherigen Überlegungen gilt 1 pW * m 1 − ρˆ ρ/ 2 1 ≤ < tS > * * m 1− ρ/ 2

< t W b > = < tS > *

und wenn die Zahlenwerte ρ = 4/5 und m = 2 eingesetzt werden 2 5 1 2/5 1 < t W b > ≤ < tS > * * = < tS > * * = < tS > 5 6 3 2 1− 2/5 4 < t V b > ≤ < tS > + < t W b > = < tS > 3

Bezogen auf die unbefriedigende Ausgangssituation ergeben sich folgende Relationen < tV > < t Vb >

=

5 < tS > 15 < t W > 4 < tS > = , = = 12 4 / 3 < tS > 4 < t W b > 1/ 3 < tS >

Das heißt der Gewinn bei der Wartezeit ist gegenüber der schnellen Prozessorlösung (a) gleichgeblieben, bei der Verweilzeit ist das Verhältnis nicht mehr so günstig. Man gewinnt mit dem Dual-Prozessor (b) nur noch einen Faktor 4 statt 6 bei der Alternative (a). Interessant ist natürlich noch, wie gut bzw. schlecht unsere Approximation pW ~ ρ/m gegenüber der exakten Rechnung ist. Mit den vorliegenden Zahlenwerten folgt π0

pW

/

/

exakt

3/7

2/9 (8/35)

1/5 (4/21)

6/5

approx.

-

2/5

1/3

4/3

Die Resultate der Näherung liegen, wie nicht anders zu erwarten, deutlich über den exakten Werten – bei den mittleren Verweilzeiten beträgt die Differenz allerdings nur ca. 10%, dies ist aber wegen des Einflusses der Service-Zeiten verständlich.

9.8 Modell eines File-Servers

123

9.8 Modell eines File-Servers Als letztes Beispiel diskutieren wir das Modell eines File-Servers mit M Clienten (s. Abb. 9.11). Der File-Server S(μ) bedient im Mittel μ Aufträge pro Zeiteinheit. Diese werden von M-Clienten jeweils mit der gleichen Rate α erzeugt, α α α

1 2 3

S(μ)

. . . α

M Abb. 9.11 File-Server-Modell

im Server bearbeitet und anschließend zurückgegeben. Dabei wird folgendes Zustandsschema eingehalten. 0: kein Client aktiv 1: ein Client aktiv 2: zwei Clienten aktiv . . . k: k Clienten aktiv M – 1: M – 1 Clienten aktiv M: M Clienten aktiv

M*α (M – 1)α (M – 2)α

Aufträge möglich Aufträge möglich Aufträge möglich

(M – k)α 1*α 0

Aufträge möglich Aufträge möglich Aufträge möglich

und die Abläufe bzw. Übergänge zwischen den Zuständen 0, 1,... M – 1, M gehorchen dem Diagramm

M*α

(M – 1)α

0

1 μ

2 μ

(M – k)α ...

k

k+1 μ

1*α ...

M–1 M μ

Dies impliziert zwischen den Zustandswahrscheinlichkeiten (πk, k = 0, 1,... M) die Gleichgewichtsbeziehungen

124

9 Von der Lust am Modellieren

M*α*π0 = μ*π1

π1 = M(α/μ)π0

(M – k)α*πk = μ*πk+1

πk+1 = (M – k)(α/μ)πk k = 1,... M – 1

1*α*πμ–1 = μ*πM

πM = 1*(α/μ)πM–1

Wir lösen schrittweise auf (ρ = α/μ): π2 = (M – 1)ρ*π1 = (M – 1)M*ρ2π0 π3 = (M – 2)ρ*π2 = (M – 2)(M – 1)M*ρ3π0 . . . πk = (M – k + 1)(M – k + 2)... (M – 1)M*ρkπ0 und legen die noch freie Konstante über die Normierung fest: M ⎛ ⎞ π k = π 0 ⎜1 + (M − k + 1)(M − k + 2)...(M − 1)Mρ k ⎟ ⎜ ⎟ k =0 ⎝ k =1 ⎠ Zum Auswerten der Summe bringen wir die Koeffizienten von ρk in eine bessere Darstellung, für M = 3 folgt zum Beispiel: M

1=

∑

K=1 K=2 K=3 K=4

∑

M M(M – 1) M(M – 1)(M – 2) M(M – 1)(M – 2)(M – 3)

3 3*2 3*2*1 3*2*1*0

Das Ganze sieht in etwa so aus wie Binomialkoeffizienten: ⎛M⎞ M! ⎜⎜ ⎟⎟ = ⎝ k ⎠ k!(M − k )!

⎛M⎞ M! k!⎜⎜ ⎟⎟ = ⎝ k ⎠ (M − k )!

und dies sind genau unsere Koeffizienten (M – k + 1)(M – k + 2)...(M – 1)M, wobei ⎛ M ⎞ M! ⎜⎜ ⎟⎟ = =1. ⎝ 0 ⎠ 0!M!

9.8 Modell eines File-Servers

125

Für unsere Normierungsgleichung folgt nun ⎛ 1 = π 0 ⎜1 + ⎜ ⎝

M ⎛M⎞ ⎛M⎞ ⎞ k!⎜⎜ ⎟⎟ρk ⎟ = π0 k!⎜⎜ ⎟⎟ρk = π0SM (ρ) k ⎠ ⎟⎠ k⎠ k =1 ⎝ k =0 ⎝ M

∑

∑

Die Berechnung von SM(ρ) überlassen wir Maple/Mathematica [11, 12] SM (ρ) = e1 / ρρ M Γ(M + 1, 1 / ρ)

wobei wiederum die schon bekannte unvollständige Γ-Funktion auftaucht. Da π0 = 1/SM(ρ), folgt hierfür

M=1

2

10

5

Abb. 9.12 Idle-Wahrscheinlichkeit π0

und man sieht, dass ab 5 Clienten und ρ > 1/2 das System fast vollständig den Idle(0)-Zustand vermeidet (s. Abb. 9.12). Betrachten wir den einfachsten Fall mit einem Clienten (M = 1) 1*α π0 0

1 π1

μ wobei π0 = 1/(1 + ρ) und π1 = ρ/(1 + ρ).

126

9 Von der Lust am Modellieren

π π0 π1

ρ Abb. 9.13 Zustandswahrscheinlichkeit im repair-man-Modell

Man erkennt die Bevorzugung des Leer(Idle)-Zustandes für ρ ≤ 1/2, erst für ρ > 1 ist es damit vorbei. Für die Wartewahrscheinlichkeit gilt pW = 1 – π0 = ρ/(1 + ρ) = π1, d. h. ein kontinuierliches Anwachsen mit steigender Last (Bemerkung: wegen des Pendelns zwischen zwei Zuständen läuft dieses Modell unter dem Namen repairman, s. Abb. 9.13). Zurück zum M-Clienten-Modell, das wir jetzt vollständig behandeln können. π0 =

1 SM (ρ)

⎛M⎞ πk = k!⎜⎜ ⎟⎟ρk π0 ⎝k⎠

k = 1, 2, ... M − 1, M

Als erste Leistungsgröße schauen wir uns die Wartewahrscheinlichkeit pW(M, ρ) an: p W (M, ρ) = 1 − π0 = 1 −

e −1 / ρ ρM Γ(M + 1, 1 / ρ)

9.8 Modell eines File-Servers

127

5

M=1

Abb. 9.14 Wartewahrscheinlichkeit im File-Server-Modell

Man sieht sofort, dass man nur dann eine reelle Chance hat, einen File-Server ohne große Wartezeiten für die einzelnen Clienten zu betreiben, wenn ρ ≤ 1/5, also im Niedriglastbereich (s. Abb. 9.14)! Als nächste Leistungsgröße betrachten wir die mittlere Zahl von Anforderungen im Server/Clienten-System: M

< k >=

∑

M ⎛M⎞ ⎛M⎞ k!⎜⎜ ⎟⎟k * ρk = π0ρ k!⎜⎜ ⎟⎟k * ρk −1 k⎠ k⎠ k =1 ⎝ k =1 ⎝ M

k * π k = π0

k =0

∑

∑

Nun ist k*ρk–1 = d(ρk)/dρ und wir können ohne Probleme die Differenziation d/dρ vor die Summe ziehen < k >= π0ρ

=

M ⎛M⎞ ⎞ d ⎛⎜ d k!⎜⎜ ⎟⎟ρk ⎟ = π0ρ (SM (ρ) − 1) ⎜ ⎟ dρ ⎝ k =1 ⎝ k ⎠ ⎠ dρ

∑

1 ρSM (ρ)

+

Mρ − 1 Mρ − 1 π0 (M, ρ) p = + =M− W ρ ρ ρ ρ

Der Verlauf von (M, ρ) kann relativ simpel aus den bisherigen Resultaten bestimmt werden: π (M, ρ) ~ M , denn π0 fällt für alle M mit ρ >> 1 : < k > ~ M + 0 ρ wachsendem ρ π0 1 1 = ~ → 0 1 / ρ M +1 ρ e1/ ρ ρ M +1Γ(M + 1, 1 / ρ) e ρ M!

128

9 Von der Lust am Modellieren

ρ < 1: hier läuft die Argumentation über 1/ ρ >> 1(M) und (M, ρ = 0) = 0 Also folgt ein ähnliches Verhalten wie pw (s. Abb. 9.15).

5

M=4

4 3 2 1

M=1

0 0

1

ρ

2

Abb. 9.15 Mittlere Zahl von Aufträgen im Client/Server-Modell

Die Verweil- und Wartezeiten berechnen wir mithilfe der Little’schen Gesetze, dazu benötigen wir neben auch zunächst : M M M M ⎛M ⎞ < q >= ∑ (k − 1) πk = ∑ kπk − ∑ π k = ∑ kπk −0 * π0 − 1* π1 − ⎜ ∑ π k −π0 − π1 ⎟ k =2 k =2 k =2 k =0 ⎝ k =0 ⎠ = < k > −π1 − 1 + π0 + π1 =< k > −(1 − π0 ) =< k > −p w Für das Server-M-Clienten-Modell folgt also

=

Mρ − 1 ρ

+

M ρ − 1 + π0 − ρp w π0 − pw = ρ ρ

ρ < q > = Mρ − (1 − π0 ) − ρp w = Mρ − p w − ρp w = Mρ − (1 + ρ)p w < q >= M −

1+ ρ pw ρ

Im Fall M = 1 ist pw = ρ/(1 + ρ) und damit = 0, für M = 2 gilt pw = (2ρ + 2ρ2)/(1 + 2ρ + 2ρ2), sodass folgt = 2ρ2/(1 + 2ρ + 2ρ2) (s. Abb. 9.16).

9.8 Modell eines File-Servers

129

1,5 1

M=2 0,5 0 0

1

2

3

ρ

Abb. 9.16 Mittlere Warteschlangenlänge

Zur Bestimmung der mittleren Wartezeit würde man das Little’sche Gesetz λ* = heranziehen – allerdings gibt es nur eine Generierungsrate α von einzelnen Clienten – daher bietet sich hier die Mittelung M

< α >=

∑α

k

* πk

k =0

an. Vom Zustandsdiagramm her ist αk = (M – k)*α und daher M

< α >=

∑

M

( M − k ) * α * π k = αM

k =0

∑ k =0

M

πk − α

∑k * π

k

k =0

= α*M*1 – α* = α(M – ) = α(M – M + pw/ρ) = α*pw/ρ = μ*pw Einsetzen in das 2. Little’sche Gesetz * = liefert 1+ ρ pw ρ M 1+ ρ μ* < t w >= − pw ρ

μ * p w < t w >= M −

130

9 Von der Lust am Modellieren

6

μ

10 = M

5 4,5 4 3,5 3 2,5 2 1,5 1 0,5 0

5 2 0

0,5

ρ 1

2

Abb. 9.17 Verweilzeit-Verhalten bei M-Clienten

Man erkennt einen stark lastabhängigen Bereich 0 ≤ ρ ≤ 1, während für ρ > 1 sich für alle M relativ rasch eine leistungsabhängige Sättigung herauskristallisiert (s. Abb. 9.17).

10 Leistungsanalyse auf Modellbasis

Die Zerlegung eines DV-Systems S in Komponenten oder Subsysteme, S = {S1, S2,... Sn}, ist, wie bereits erwähnt, schon ein erster Schritt in Richtung Modellierung. Die Gründe für diese Vorgehensweise liegen auf der Hand – man erhofft sich aus der Kenntnis der Lokalitäten, den Subsystemen, ein besseres Verständnis für die Ursachen der Leistung des ganzen Systems. Dementsprechend haben wir erst lokale Leistungsgesetze abgeleitet, gültig nur für Teilsysteme, und anschließend auf dieser Basis, wie etwa beim „general response law“, Gesetze globaler Natur. Dabei ist die Kenntnis von Systemzeiten tS(i) oder Besuchshäufigkeiten vi von fundamentaler Bedeutung. Diese Größen können und müssen gemessen werden, andere, wie die mittlere Anzahl von Aufträgen im i-ten Teilsystem, sind häufig nur unter großen Schwierigkeiten oder überhaupt nicht zugänglich. Auf der anderen Seite zeigen die Modellbetrachtungen des vorausgegangenen Abschnitts sowie die einfach strukturierten Gesetze von Little eine erstaunliche Effizienz und Transparenz in der Leistungsanalyse. Natürlich liegt es nahe, die beiden Ansätze zu kombinieren und das zu untersuchende DV-System in solche Teilsysteme zu zerlegen, dass diese einzeln unseren Modellvorstellungen genügen, d. h. exponentiell verteilte Zwischenankunfts- und Bearbeitungszeiten sowie die Zeitunabhängigkeit der Zustandswahrscheinlichkeiten im Gleichgewicht. Darüber hinaus nehmen wir insgesamt ein Gleichgewicht der Teilsysteme untereinander an, wie bereits in früheren Beispielen beschrieben. Dabei steht das Konzept der Little’schen Gesetze, die Betrachtung von Mittelwerten, im Vordergrund und man vermeidet somit den erheblichen Aufwand, der mit der expliziten Berechnung von Zustandswahrscheinlichkeiten verbunden ist. Wir konzentrieren uns fast vollständig auf die mittlere Verweil-/Antwort-/Durchlaufzeit eines Auftrags im System der Komponenten S1...Sn – die Bestimmung der Auslastungen ρ1... ρn werden wir im Sinne der Engpass-Analyse nur skizzieren. Es sind zwei grundsätzlich verschiedene Situationen zu unterscheiden. Einmal ein offenes System mit externen Quellen, bei dem die genaue Anzahl von Aufträ-

132

10 Leistungsanalyse auf Modellbasis

gen nicht bekannt ist, z. B. ein Mail-System, welches aus einem Server und zwei Viren-Scannern besteht. Alternativ dazu betrachten wir ein geschlossenes System, in welchem eine feste Anzahl N von Aufträgen in den Subsystemen 1...n abgearbeitet werden, wobei unterstellt wird, dass jeder fertige Auftrag sofort durch einen neuen ersetzt wird und somit die Gesamtzahl N konstant bleibt.

10.1 Die Diskussion des offenen Modellsystems Wir beginnen mit dem einfacheren Fall des offenen Systems, auf dessen i-tes Teilsystem eine Forderung/ein Auftrag zukommt. Da sich im Mittel bereits Aufträge dort befinden, ist • die Wartezeit * tS(i) • die Verweilzeit = * tS(i) + tS(i), denn der Teilauftrag muss ja auch bedient werden, also = tS(i) * ( + 1) Da für jede Komponente i einer Messung nicht einfach zugänglich ist, wenden wir das Gesetz von Little an. • = Di * = Di * tS(i) * ( + 1) Nun gilt das Auslastungsgesetz ρi = ts(i) * Di und damit • = ρi ( + 1) Nach aufgelöst folgt • < k i >=

ρi 1 − ρi

• < t V (i) >= t S (i) * (< k i > +1) = n

• < t V >=

∑v i =1

n

i

< t V (i) > =

∑ i =1

t S (i) 1 − ρi

vi * t S (i) 1 − ρi

Man sieht sofort, dass der Ausdruck für mit dem analytisch abgeleiteten Ergebnis des vorangegangenen Abschnitts übereinstimmt, ebenso die Formel für , wenn tS(i) durch 1/μi ersetzt wird. Weiterhin wird klar, je stärker die i-te Komponente ausgelastet ist, ρi ≈ 1, desto größer wird, wegen des Nenners 1 – ρi, der Beitrag zur mittleren Verweilzeit eines Auftrags im Gesamtsystem.

10.1 Die Diskussion des offenen Modellsystems

133

Das folgende, etwas ausführlichere Beispiel zeigt eine Kombination dieser Modellvorstellungen mit den operationalisierten Leistungsgesetzen und lässt sich zudem relativ einfach verallgemeinern. Von Clienten werden Anforderungen (req) an einen Server (S) geschickt, welcher zu ihrer Bearbeitung zwei Platten A und B benötigt (s. Abb. 10.1).

Clienten

A

#req(A), tB(A)

S

tB(S)

B

#req(B), tB(B)

#req

Abb. 10.1. Client-Server-Modell

Das Beobachtungsintervall sei tM Sekunden, die Anzahl der Anforderungen #req und die gemessenen Aktivzeiten tB = (tB(S), tB(A), tB(B)) – wobei tB(A) < tB(B) sowie #req (A) < #req(B). Die Modellvoraussetzungen, exponentiell verteilte Zwischenankunfts- und Bearbeitungszeiten, sollen auch für die Subsysteme S, A, B erfüllt sein. Unser Hauptziel ist natürlich die Ableitung der mittleren Antwortzeit einer Anforderung, allerdings sollen auch die lokalen Leistungsgrößen wie Auslastungen oder Besuchshäufigkeiten bestimmt werden. So folgt für die Plattensysteme • vA =

# req(A) # req

vB =

# req(B) # req

• ρA =

t B (A) tM

ρB =

t B (B) tM

• ρA < ρB da

t B (A) < t B (B)

Hinsichtlich des Server-Beitrags ist die Situation nicht ganz so einfach, denn es muss auf die Verknüpfung der Komponenten untereinander eingegangen werden, am einfachsten mithilfe der Matrix P der Übergangswahrscheinlichkeiten:

134

10 Leistungsanalyse auf Modellbasis

C

S

A

B

C

0

1

0

0

S

p10

0

p12

p13

A

0

1

0

0

B

0

1

0

0

und dem linearen Gleichungssystem (1, vS, vA, vB) = (1, vS, vA, vB)P. Da wir vA und vB schon kennen, interessiert nur noch vS, welches wir über die zweite Spalte der Matrix bekommen vS = 1*1 + vS*0 + vA*1 + vB*1 = 1 + vA + v B Dieses Ergebnis widerspiegelt den Sachverhalt, dass jeder Plattenzugriff auch einer Server-Aktion bedarf und ist eine fundamentale Eigenschaft des vorliegenden „Client-Server-Modells“. Wir erhalten mit den Werten für vA und vB: • vS = 1 +

# req(A) # req(B) + # req # req

ρS =

t B (S) tM

sodass wir den Flaschenhals dieses Systems über max(ρS, ρA, ρB) bestimmen können. Damit sind alle Größen festgelegt, mit deren Hilfe die mittlere Anwort-/Verweilzeit einer Anforderung berechnet werden kann: < t V >=

∑

vi t S (i) 1 − ρi i =S, A , B

Wir benötigen vits(i), da wir die Auslastungen ρi kennen. Das Auslastungsgesetz, welches lokale und globale Kennzahlen verknüpft ρi = vitS(i)*D liefert vitS(i) = ρi/D, und da wir den Gesamtdurchsatz D = #req/tM kennen, folgt

10.1 Die Diskussion des offenen Modellsystems

< tv >=

135

1 ρi D i =S, A , B 1 − ρi

∑

Mit der Verwendung der unmittelbar gewonnenen Messwerte ρi = tB(i)/tM ändert sich dieser Ausdruck zu < t V >=

tM # req

∑

t B (i) t − t B (i) i =S, A , B M

Bei der Engpass-Analyse ist jedoch die Abhängigkeit von den Auslastungen ρi vorzuziehen, da der Einfluss der einzelnen Komponenten auf klarer zu erkennen ist. Das folgende Beispiel soll dies verdeutlichen. B1 Das diskutierte „Central-Server“-Modell mit den Komponenten S, A, B lässt sich ohne Schwierigkeiten auf einen Mail-Server S mit zwei Viren-Scannern A, B übertragen. Der Server hat 240 Anforderungen, #req = 240, im Messintervall von tM = 60 sec. Diese werden in A, B auf Viren geprüft und anschließend weitergeleitet – wir fragen nach dem mittleren Zeitbedarf für diese Prozesse. Im Zeitintervall tM sind die Aktiv/Busy-Zeiten wie folgt gemessen (sec): tB(S) = 30

tB(A) = 15

tB(B) = 45

Die Auslastungen ρi sowie ρi/(1 – ρi) ergeben sich damit zu • ρS =

t B (S) 30 1 ρS = = ; =1 tM 60 2 1 − ρS

• ρA =

ρA t B (A) 15 1 1 = = ; = tM 60 4 1 − ρ A 3

• ρB =

t B (B) 45 3 ρB = = ; =3 tM 60 4 1 − ρB

Klarerweise ist B mit 75% Auslastung der Engpass. Zur endgültigen Bestimmung von wird noch der Durchsatz D = #req/tM = 240/60 = 4 req/sec sowie die Besuchshäufigkeiten vA = vB = 1, vS = 1+ vA + vB = 3 gebraucht: < tv >=

1 vi *ρi 1 1 5 = (3 *1 + 1* + 1* 3) ≈ sec D i = S, A , B 1 − ρ i 4 3 3

∑

136

10 Leistungsanalyse auf Modellbasis

d. h. die Weiterleitung einer Mail in diesem nicht ausgewogenen System benötigt im Mittel 5/3 sec – verursacht durch den Zeitbedarf des Viren-Scanners B und die Inanspruchnahme des Servers S. Wir untersuchen jetzt zwei technische Verbesserungen des Systems, zunächst die Halbierung der Service-Zeit tB(B) des zentralen Servers: tB(S) => (1/2)*tB(S) ρS ' =

(1 / 2) t B (S) 1 t B (S) 1 = = ρS tM 2 tM 2

1 1 1 * = 2 2 4 1⎛ 1 1 ρS ' 1/ 4 1/ 4 1 ⎞ 11 = = = Æ = ⎜ 3 * + 1 * + 1 * 3 ⎟ ≈ 1 − ρS ' 1 − 1 / 4 3 / 4 3 4⎝ 3 3 ⎠ 10 =

der Gewinn bezüglich der Verweildauer beträgt mehr als 50%! Diese Maßnahme ist natürlich mit Kosten belastet, da doppelt so schnelle Prozessoren eingesetzt werden müssen. Als Alternative kann man analysieren, wie groß der Gewinn ist, wenn die Last von B auf A verlagert wird, d. h. vB = 0, und zwar unter der Annahme, dass die Bedien/Service-Zeit von A sich dadurch verdoppelt: tB’’(A) = 2*tB(A) = 2* 15 = 30

ρA ' =

2t B (A) 30 1 = = tM 60 2

ρA ' ' 1 − ρA ' '

=

1/ 2 =1 1/ 2

sowie v’’A = 2 1 (3 *1 + 2 *1 + 0 * 3) = 5 4 4 damit beläuft sich der Gewinn bezogen auf das Ausgangssystem immerhin auf ca. 30% und ist zudem kostenneutral! Als letztes untersuchen wir den Effekt beider Maßnahmen, also Halbierung der Prozessorzeit und das Abschalten des langsamen Systems B:

=

< t V ' ' ' >=

1 ⎡ ρA ' ρ ' ⎤ 1⎡ 1⎤ 3 + S ⎥ = ⎢2 *1 + 3 * ⎥ = ⎢ D ⎣1 − ρA ' 1 − ρS ' ⎦ 4⎣ 3⎦ 4

10.1 Die Diskussion des offenen Modellsystems

137

Gegenüber der alten Verweilzeit ≈ 5/3 ergibt dies einen Speed-Up / ≈ 2 und damit eine 100%tige Verbesserung.

Zum Abschluss diskutieren wir zwei einfache, aber strukturierte Modelle aus mehreren Komponenten, von denen jede einzelne sich wie ein Standardsystem verhält. B2 Wir betrachten ein linear angeordnetes System von drei Komponenten S1, S2, S3 – die dazugehörigen Bearbeitungsraten sind μ1, μ2, μ3. Die Komponente S3 wird von einem externen Auftragsstrom λ beliefert.

μ2

μ1

μ3

λ

Wie in Kap. 5 beschrieben lösen wir die Flussgleichung ⎛ 0 0 0⎞ ⎜ ⎟ (λ1,λ 2 , λ 3 ) = (0,0, λ ) + (λ1,λ 2 , λ 3 ) ⎜ 1 0 0 ⎟ ⎜ 0 1 0⎟ ⎝ ⎠

λ1 = λ2 = λ3 = λ und können oben für jede Komponente die Zustandswahrscheinlichkeit πi (k ) = (1 −

λ λ ki )( ) μi μi

(k1, k 2 , k 3 ) = 0, 1, 2, 3,...

berechnen. Die Wahrscheinlichkeit für das Gesamtsystem (ki Aufträge im Subsystem Si) ist p( k1 , k 2 , k 3 ) = π1 ( k1 ) * π 2 ( k 2 ) * π 3 ( k 3 ) = (1 −

λ λ k1 λ λ λ λ )( ) (1 − )( ) k 2 (1 − )( ) k 3 μ1 μ1 μ2 μ2 μ3 μ3

Die Normierungseigenschaft

∑ p(k ,k , k ) = 1 1

2

3

k1 , k 2 , k 3

ist erfüllt, da jeder Faktor πi(ki) schon normiert ist.

138

10 Leistungsanalyse auf Modellbasis

Aufgrund dieser Normierung und der Produkteigenschaft der Zustandswahrscheinlichkeiten folgt = + + =

ρ ρ1 ρ + 2 + 3 1 − ρ1 1 − ρ2 1 − ρ3

wobei ρi = λ/μi, i=1, 2, 3. Das 1. Gesetz von Little λ * = kann nicht global, sondern nur lokal für die Teilsysteme 1, 2, 3 formuliert werden, λi * = , damit gilt = /λi und weiterhin < t V >=

1 ρ1 1 ρ2 1 ρ3 + + μ1 1 − ρ1 μ 2 1 − ρ2 μ3 1 − ρ3

Dieses additive Gesetz liegt auf der Hand, da die Modellierung keine überlappenden Phasen 1, 2,3 vorsieht.

B3 Wir diskutieren ein offenes Modell, welches aus vier Subsystemen IOInterface (4), CPU (1), Terminal (2) und Disk (3) besteht.

Terminal

p12 = 1/4 Quelle

λ=

CPU

IO-Interface

5req sec

p13 = 3/4

Disk

p34 = 1 Die internen Ankunftsraten λi=1...4 berechnen sich wie folgt λ 4 = λ + λ3

λ 1 = λ4

λ1 = 4λ = 20 λ2 = 1/4 λ1 = 5

λ2 = 1/4 λ1

λ3 = 3/4 λ1

λ3 = 3/4 λ1 = 15 λ4 = λ1 = 20

Die mittleren Service-Zeiten = 1/μi, i = 1...4, sind vorgegeben. 1/μ1 = 1/100 1/μ2 = 1/20

1/μ3 = 1/30

1/μ4 = 1/50

10.2 Über die Analyse von geschlossenen Systemen

139

Damit berechnen sich die Auslastungen ρi = λi/μi wie folgt ρ2 = 1/4

ρ1 = 1/5

ρ3 = 1/2

ρ4 = 2/5

und ein möglicher Engpass liegt bei ρ3 = 1/2 (50%), d. h. beim Plattensystem. Die Leistungsgröße „mittlere Verweilzeit “ eines Auftrags berechnet sich nach Little (1): λ* = = + + +

= ρi / (1 – ρi)

= 1/4 + 1/3 + 1 + 2/3 = 9/4

λ* = 5* = 9/4 =>

≈ 1/2 [sec]

Man beachte, dass wegen der Verarbeitungsüberlappung nicht die Summe der einzelnen Verweilzeiten der Subsysteme genommen werden muss.

Es darf bei aller Transparenz und Eleganz dieser Art von Analyse nicht vergessen werden, dass bestimmte Voraussetzungen, nämlich exponentiell verteilte Zwischenankunfts- und Bearbeitungszeiten, erfüllt sein müssen. Sieht man die Analyse mehr unter einem qualitativen Aspekt, genügt häufig allerdings ihre Unterstellung.

10.2 Über die Analyse von geschlossenen Systemen Wie bereits zu Beginn dieses Abschnitts über Leistungsanalysen auf Modellbasis angeschnitten, wollen wir jetzt unser Modellsystem S und S1, S2,... Sn Komponenten als abgeschlossen betrachten – die sonstigen Vorraussetzungen bleiben unverändert. Es wird angenommen, dass eine feste Anzahl N von Aufträgen (req) im System zirkuliert, jeder bearbeitete Auftrag wird sofort durch einen neuen ersetzt. Man könnte nun vermuten, dass unter solch einfachen Annahmen Leistungsanalyse und -verständnis keine Probleme verursachen, leider ist das Gegenteil der Fall. Die Ursache liegt in der endlichen Zahl von Systemzuständen ⎛ N + n − 1⎞ ( N + n − 1)! ⎜⎜ ⎟⎟ = ⎝ n − 1 ⎠ N!(n − 1)!

140

10 Leistungsanalyse auf Modellbasis

die untereinander über ein lineares Gleichungssystem verbunden sind. Dadurch ist die Produktform für Zustandswahrscheinlichkeiten des Gesamtsystems S = (S1, S2,... Sn) im Gleichgewicht (mit ki Aufträgen in der Komponente Si) p(k1, k2,... kn) = p1(k1) p2(k2)... pn(kn) nicht mehr unmittelbar einsichtig – vor allem die Normierung der Wahrscheinlichkeiten (d. h. die Summe über alle Zustandswahrscheinlichkeiten muss 1 sein) ist sehr aufwendig. Ein Beispiel soll dies verdeutlichen. B4 System mit drei (n = 3) Komponenten/Subsystemen,

μ2 k2

μ1 k1

μ3 k3

deren Bearbeitungsraten μ1, μ2 und μ3 sind. Es sollen N = 2 Aufträge zirkulieren. Damit gibt es 4!/(2!*2!) = 6 Zustände (2, 0, 0) (0, 1, 1) (1, 1, 0) (0, 2, 0) (1, 0, 1) (0, 0, 2) mit folgenden Übergängen (0, 2, 0) μ2

μ3 μ1 (0, 1, 1)

(1, 1, 0) μ2

μ2 μ3

μ3 (0, 0, 2)

(1, 0, 1) μ1

(2, 0, 0) μ1

Das Gleichgewicht hat zur Folge, dass μ2π(0, 2, 0) = μ3π(0, 1, 1) (μ1 + μ2)π(1, 1, 0) = μ2π(0, 2, 0) + μ3π(1, 0, 1)

10.2 Über die Analyse von geschlossenen Systemen

141

Hat man π(2, 0, 0), π(1, 1, 0)... usw. berechnet, können die Randwahrscheinlichkeiten bestimmt werden. p1(0) = π(0, 2, 0) + π(0, 1, 1) + π(0, 0, 2) p1(1) = π(1, 1, 0) + π(1, 0, 1) p1(2) = π(2, 0, 0) Anschließend lässt sich die Produktform p1(k1) p2(k2) p3(k3) berechnen. Im Prinzip hat man wie bereits erwähnt zwar nur ein großes lineares Gleichungssystem zu lösen – für die Zustandswahrscheinlichkeiten – und kann anschließend alle Leistungsgrößen wie die mittlere Antwortzeit N ausrechnen. Es hat sich jedoch gezeigt, dass es wesentlich günstiger ist, Algorithmen zu entwickeln, welche direkt die Berechnung von Auslastungen, Antwortzeiten und Durchsätzen erlauben – am besten natürlich in Anlehnung an das bereits diskutierte offene System [5]. Beschränken wir uns zunächst nur auf die Bestimmung der mittleren Antwort-/ Bearbeitungszeit eines Auftrags, wenn N Aufträge in n Teilsystemen abgearbeitet werden müssen. Für jede Komponente Si gilt das Gesetz von Little N = λi(N)N = Di(N)N, wobei wegen des vorausgesetzten Gleichgewichts Durchsatz und Ankunftsrate identisch sind. Da weiterhin gilt Di(N) = viD(N), wobei D(N) der Durchsatz des ganzen Systems und vi die Besuchshäufigkeit, kann das Little’sche Gesetz wie folgt formuliert werden N = D(N)viN Um unser Ziel n

< tV >N =

∑v < t i

V (i)

>N

i =1

zu erreichen, brauchen wir die Zeiten N in den einzelnen Komponenten/Subsystemen, hier kann man ähnlich wie beim offenen System argumentieren: N = tS(i)(1 + N–1)

142

10 Leistungsanalyse auf Modellbasis

d. h. die mittlere Verweildauer N in der i-ten Komponente bei N Aufträgen im System bestimmt sich aus der Service-Zeit tS(i) dieser Komponente und der mittleren Anzahl N–1 bei N – 1 Aufträgen. Wir setzen unser modifiziertes Little’sches Gesetz in diese Beziehung ein: N = tS(i)(1 + D(N – 1)viN–1) und nutzen aus D( N ) =

N < tV >N

=

N n

∑ v < t (i) > i

v

N

i =1

sodass wir letztlich eine Rekursionsgleichung erhalten ⎞ ⎛ ⎜ ⎟ ⎜ vi < t V (i) > N −1 ⎟ < t V (i) > N = t S (i)⎜1 + ( N − 1) n ⎟ ⎜ ⎟ vi < t V (i) > N −1 ⎟ ⎜ i =1 ⎝ ⎠

∑

Der Schritt N = 1 definiert den Beginn der Rekursion n

1 = tS(i) => < t V > N =1 =

∑ v t (i) i S

i =1

eine explizite Auflösung für höhere N ist nur in speziellen Fällen möglich. B5 Das System besteht aus einer Komponente, d. h. i = n = 1 und vi = 1 ⎛ v < t (1) > N −1 ⎞ ⎟ N = t S (1)⎜⎜1 + ( N − 1) 1 V v1 < t V (1) > N −1 ⎟⎠ ⎝

= tS(1)(1 + (N – 1)*1) = N*tS(1) N = N = N*tS(1) D( N ) =

N N 1 = = < t V > N N * t S (1) t S (1)

ist unabhängig von N.

10.2 Über die Analyse von geschlossenen Systemen

143

In den meisten Fällen wird man die Rekursion numerisch lösen, zumal man dann für jedes N auch den Durchsatz, die Antwortzeit sowie die Auslastung jeder Komponente bestimmen kann und somit die Basisdaten für eine Engpass-Analyse zur Verfügung hat. Das folgende Beispiel zeigt dies einmal anhand konkreter Zahlen auf. B6 Wir untersuchen ein System aus {Terminal/Client, Server, Platte A, Platte B}. Vom Terminal-Clienten werden N Anforderungen submittiert, welches ist die mittlere Antwortzeit N? Die Systemdaten (Zeiten in sec) sind

tS(A) = 3/10

tS(B) = 2/10

vA = 10

vB = 5

tS(S) = 1/8 vS = 1 + 5 + 10 = 16

⎛ v < t (i) > N −1 ⎞ ⎟ < t V (i) > N = t S (i)⎜⎜1 + ( N − 1) i V < t V > N −1 ⎟⎠ ⎝

∑v < t

< t V >N =

i

V (i )

>N

i =S, A , B

D(N) = N / N ist der Durchsatz und ρN(i) = vi tS(i)*D(N) die Auslastung der i-ten Komponente. N

1

2

3

4

5

N 3/10 1/2 3/5 3/4

4/5

N 2/10 1/4 1/4 1/4

4/15

N 1/8 1/6 1/3 1/3

5/16

N

6

14

15

D(N)

1/6 2/9 1/4 2/7

1/3

ρN(A)

½

ρN(B)

1/6 2/9 1/4 2/7

1/3

ρN(S)

1/3 4/9 1/2 4/7

2/3

9

12

2/3 3/4 6/7

1

Man erkennt sehr schön, dass der Hauptbeitrag zur ansteigenden Verweilzeit von der Platte A kommt, die bei einer Anforderung schon zu 50% ausgelastet ist und bei N = 5 voll, d. h. 100%. Dies ist also das Subsystem, welches eine weitere Durchsatzsteigerung verhindert.

144

10 Leistungsanalyse auf Modellbasis

Unter dem Aspekt, dass qualitative Abschätzungen des Systemverhaltens zum Verständnis häufig völlig ausreichend sind, wollen wir zwei Näherungslösungen diskutieren. Die erste (Schweitzer 1971) setzt bei N = tS(i)(1 + N–1) an. Wegen

folgt

< ki > N −1 < ki > N ≈ N −1 N < ki > N −1 ≈

N −1 < ki > N N

und damit kann N −1 ⎛ ⎞ < t V (i) > N ≈ t S (i)⎜1 + < ki >N ⎟ N ⎝ ⎠

approximiert werden. Da nach Little (1) gilt N = D(N)viN und D(N) = N / N erhält man nach einigen Umformungen: < t V (i) > N =

t s (i) v t (i) 1 − ( N − 1) i S < t V >N

Da (N – 1) / N ≈ D(N) sowie D(N)*vi*ts(i) = ρN(i), die Auslastung der i-ten Komponente und diese immer 0 ≤ ρN(i) ≤ 1 erfüllt, können wir nähern ⎛ v t (i) ⎞ ⎟ < t V (i) > N ≈ t S (i)⎜⎜1 + ( N − 1) i S < t V > N ⎟⎠ ⎝

Weiterhin ist die Verweilzeit von N Anforderungen N sicherlich größer als die, wenn nur ein Auftrag im System ist N ≥ 1

10.2 Über die Analyse von geschlossenen Systemen

145

und damit folgt ⎛ v t (i) ⎞ < t V (i) > N ≤ t S (i)⎜⎜1 − ( N − 1) i S ⎟⎟ < t V >1 ⎠ ⎝ < t V >1 = v1t S (1) + v 2 t S (2) + ... + v n t S (n ) =: t S

Für unser exakt gerechnetes Beispiel erhalten wir damit eine sehr gute Übereinstimmung. Ist man lediglich an der Verweilzeit N des ganzen Systems interessiert, so kann durch einfache Summation eine obere Schranke erhalten werden. n n ⎡ ⎛ v t (i) ⎞⎤ < t V > N = ∑ vi < t V (i) > N ≤ ∑ ⎢ v i t S (i)⎜⎜1 + ( N − 1) i S ⎟⎟⎥ t S ⎠⎦⎥ i =1 i =1⎣ ⎢ ⎝

⎛ n < t V > N ≤ t S ⎜⎜1 + ( N − 1) ∑ i =1 ⎝

⎛ vi t S (i) ⎞ ⎜ ⎟ ⎜ t ⎟ ⎝ S ⎠

2⎞

⎟ ⎟ ⎠

Erinnern wir uns, dass tS = N=1 und 1/1 = D(1) der Durchsatz bei einer Forderung im System ist. Dann gilt vi t S (i) vi t S (i) = = D(1) * vi t S (i) = ρ1 (i) tS < t V >1

wobei ρ1 (i) die Auslastung der i-ten Komponente bei N = 1 darstellt. Definieren wir n

ρˆ 2 =

∑ i =1

2

⎛ vi t S (i) ⎞ ⎜ ⎟ = ⎜ t ⎟ ⎝ S ⎠

n

∑ ρˆ (i) 2 1

i =1

so ist ρˆ 2 eine Systemkonstante, und wir können einen einfachen linearen Zusammenhang zwischen N und N konstatieren < tV >N ≤ (1 − ρˆ 2 ) + ρˆ 2 * N tS

146

10 Leistungsanalyse auf Modellbasis

Für unser Beispiel B6 ergibt sich B6’ tS = 3/10 * 10 + 2/10 * 5 + 1/8*16 = 6 ρ1 (S) =

vS t S (S) 16 *1 / 8 = = 1/ 3 tS 6

ρ1 (A) =

v A t S (A) 10 * 3 / 10 = = 1/ 2 tS 6

ρ1 (B) =

v B t S (B) 5 * 2 / 10 = = 1/ 6 tS 6

ρˆ 2 = ρˆ 12 (S) + ρˆ 12 (A) + ρˆ 12 (B) =

7 18

⎡⎛ 7⎞ 7 ⎤ < t V > N ≤ 6⎢⎜1 − ⎟ + N ⎥ ⎣⎝ 18 ⎠ 18 ⎦

Die Reproduktion der vorherigen Werte ist selbstverständlich erfüllt.

Die zweite Approximation geht von der ursprünglichen Rekursion aus und ist wie folgt begründet. Die Antwortzeit für N ≥ 2 Aufträge ist sicherlich größer als die Antwortzeit für einen Auftrag im System (wie gehabt) n

< t V > N −1 =

∑ i =1

n

vi < t V (i) > N −1 ≥

∑ v t (i) =< t i S

V

>1

i =1

Da für 1 nur die bekannten Systemzeiten tS(i) eine Rollen spielen, definieren wir tS:= und können abschätzen ⎛ v < t (i) > N −1 ⎞ ⎟ < t V (i) > N ≤ t S (i)⎜⎜1 + ( N − 1) i V ⎟ tS ⎠ ⎝

10.2 Über die Analyse von geschlossenen Systemen

147

Dies ist eine wesentlich handhabbarere Form und mit 1 = tS(i) für alle i = 1...n kann man auch eine explizite Lösung hinschreiben: a i :=

vi t S (i) tS

< t V (i) > N = 2 = t S (i)(1 + 1* a i ) < t V (i) > N = 3 = t S (i)(1 + 2 * a i + 2 *1* a i 2 ) < t V (i) > N = 4 = t S (i)(1 + 3 * a i + 3 * 2 * a i 2 + 3 * 2 *1 * a i 3 ) #

< t V (i) > N = t S (i)(1 + ( N − 1)a1i + ( N − 1)( N − 2)a i2 + ... + ( N − 1)( N − 2)( N − 3) ... 2 *1* a iN −1 ) = t S (i)

N −1

⎛ N − 1⎞ k ⎟a i k ⎟⎠

∑ k!⎜⎜⎝ k =0

Zum expliziten Ausrechnen der Summe bemühen wir Mathematica [12] N −1

⎛ N − 1⎞ k ⎟a i = e1 / a i * a i N −1Γ( N, 1 / a i ) k ⎟⎠

∑ k!⎜⎜⎝ k =0

sodass eine geschlossene Lösung der Rekursion möglich ist: < t V (i) > N

⎛ v t (i) ⎞ ≤ t S (i)⎜⎜ i S ⎟⎟ ⎝ tS ⎠

N −1

⎞ ⎛ t ⎛ tS ⎞ ⎟ exp ⎜ S ⎟ Γ⎜⎜ N, ⎟ ⎜ ⎟ ⎝ vi t S (i) ⎠ ⎝ vi t S (i) ⎠

Eine weitere Analyse zeigt, dass für (vits(i)/tS) = < tB > + < tW > = < tB > + < tB >

pW 1 ⎛ ρ ⎞ 1 1 ⎜⎜1 + ⎟= = 1 − ρ μC ⎝ 1 − ρ ⎟⎠ μC 1 − ρ

sodass nicht zu große ρ < 2/3 vernünftige Antwortzeiten garantieren. Wie oben bereits erwähnt, ist einer der wichtigsten Aspekte moderner Kommunikationssysteme der Betrieb als „shared medium“, z. B. beim W-LAN oder GSM. Dies bedeutet im Prinzip die Unterteilung in p selbstständige Subkanäle und damit natürlich auch eine Aufteilung der Kapazität C in C/p im einfachsten homogenen Fall – zwei weitere Modelle sind damit zu (І): M(λ)/M(μC)/1/∞ denkbar: λ p

(ІІ) => λ

C p

#

# λ p

M(λ/p)/M(μC/p)/1/∞

# C p

M(λ/p)/M(μC/p)/1/∞

bzw. C p

(ІІІ) => λ

#

M(λ)/M(μC/p)/1/∞

# C p

M(λ)/M(μC/p)/1/∞

11.1 Allgemeine strukturelle Überlegungen

151

Die Auslastungen ρІ,ІІ,ІІІ sind alle identisch ρ = λ/(μC), hinsichtlich und der Wartezeit gibt es doch erhebliche Unterschiede. So haben wir bereits zu 1/(μC) berechnet, für die Modelle ІІ und ІІІ folgt = =

1 = p/(μC) = p* μC / p

und damit ein linearer Anstieg mit der Zahl p der Subkanäle. Dies ist verständlich, da die Kapazität dieser Kanäle mit C/p abfällt. Bezüglich der Wartezeit 1 p = * * W p 1− ρ

ist die Situation nicht so einfach zu analysieren. Wenn die Zahl der aktiven tasks kleiner als p ist, gibt es keine Wartezeit, jeder Kommunikationswunsch kann sofort bedient werden. Die Modelle ІІ und ІІІ verhalten sich da identisch, während І natürlich schon für mehr als eine task eine Wartezeit aufweist. In ІІ ist die Aufteilung in p Auftragswarteschlangen λ/p insofern problematisch, dass Situationen mit leeren Subkanälen nicht unwahrscheinlich sind (die Idle-Wahrscheinlichkeiten π0(p) müssen aufaddiert werden) und wir deshalb dieses Modell ІІ aus Effizienzgründen von den weiteren Betrachtungen ausschließen. Aus dem gleichen Grund stellt übrigens die Bahn für p Fahrkartenschalter nur eine Warteschlange für die Kunden zur Verfügung. Die mittlere Bearbeitungszeit in einem Subkanal wurde bereits zu p/(μC) bestimmt, sodass wir für die Wartezeit Folgendes erhalten: (μC)* =

pW ,0≤ρ der Beweis ist durch explizites Einsetzen sehr einfach zu führen 1− ρ • =

a b(1 − ρ ) b auch dieser Beweis ist durch Benutzung der ursprünglichen Formel und einigen Umformungen einfach; es gilt die Randbedingung (a/b) < μC/λ bzw. b/a > ρ • ≤ ; dies wurde von L. Kleinrock [1] bewiesen und ist insofern bedeutsam, da es zeigt, dass bezüglich der Antwortzeit ein System ohne Subkanäle das optimale System ist. Mit dem Little’schen Gesetz λ* < tV(p, λ, C)> = (mittlere Anzahl von Aufträgen/tasks/Nachrichten) und (i)–(iii) kann man sehr schön ableiten, dass die kleinste Anzahl von Aufträgen im System ohne Subkanäle zu finden ist und außerdem in λ und C skaliert.

11.2 Analyse des ALOHA-Protokolls

153

4

(μC

3,5 3 2,5 2 1,5

4/5

1

3/5

0,5 0 1

1/5

3

5

7

9

p

Abb. 11.2 Verhalten der Wartezeit in Abhängigkeit von p

11.2 Analyse des ALOHA-Protokolls Nach diesen etwas allgemeineren Ausführungen wollen wir uns den Regeln zur Übertragung von Nachrichten oder Daten zwischen Kommunikationspartnern, die üblicherweise als Protokoll bezeichnet werden, zuwenden. Im Bereich der Datenverarbeitung/Informationstechnologie existiert eine große Vielfalt, bekannte Beispiele sind das Internetprotokoll TCP/IP, das Ethernetprotokoll für LAN’S (Local Area Network) und WAN’S (Wide Area Network) oder zum Beispiel die Familie 802.1x für die drahtlose Übertragung (Wireless LAN) [13]. Es liegt jedoch nicht im Rahmen unserer Diskussion, hier einzelne Features/Aspekte der obigen, aktuellen Protokolle hinsichtlich ihres Leistungsverhaltens, etwa gemessen am Durchsatzvermögen, zu untersuchen. Vielmehr wollen wir uns auf die grundlegenden Mechanismen, die allen Protokollen in etwa gemeinsam sind, beschränken. Wie in den obigen allgemeineren Ausführungen setzen wir voraus, dass der Zugriff der Kommunikationspartner/Clients auf das gemeinsame Übertragungsmedium (Kanal) per Zufall erfolgt. Das älteste und auch einfachste Protokoll dieser Art ist ALOHA, welches ca. 1970 an der Universität von Hawaii entwickelt wurde und die Grundlage für viele moderne Entwicklungen bildet. Es basiert auf folgenden Regeln: • Jeder Client sendet Nachrichten, wann und soviel er will. • Alle Nachrichten/Pakete sind gleich lang und benötigen den Kanal tp Zeiteinheiten (Slot).

154

11 Konzepte zur Analyse von Kommunikationssystemen

• Sind mehr als zwei Nachrichten/Pakete auf dem Kanal, erfolgt eine Kollision, gefolgt von einem Abbruch der Übertragung und der Bereitstellung für eine Wiederholung. • Jeder Client ist während des Sendeversuchs und der Kollisionsbearbeitung blockiert. Um das Leistungsverhalten dieses Protokolls zu analysieren, benötigen wir den effektiven Durchsatz D sowie die mittlere Anzahl von Paketen und die mittlere Anzahl von Wiederholungen . Es werden λ0 Pakete generiert und λ r Pakete wiederholt, sodass die angebotene Last λ = λ 0 + λ r . Sei [0, t M ] das Messintervall/Beobachtungsintervall und p 0 ( λ, t M ) die Wahrscheinlichkeit dafür, dass das aktuelle Datenpaket keine Kollision/Störung erfährt, dann gilt natürlich für den effektiven Durchsatz D = λ ⋅ p0 (λ, t M ) . Die Wahrscheinlichkeit, dass ein Testdatenpaket von irgendeinem Clienten in k Versuchen einmal Erfolg hat, d. h. k – 1 Fehlschläge und 1-mal Erfolg, ergibt sich zu:

(1 − p0 (λ, t M ))k −1 * p0 (λ, t M ) Im Mittel sind damit:

=

∞

∑ k * (1 − p (λ, t 0

M ))

k −1

* p 0 (λ , t M )

k =1

= p 0 (λ , t M ) *

∞

∑ k* q

0 (λ , t M )

k −1

; q 0 = 1 − p0

k =1

Versuche notwendig – ist leicht zu berechnen

< k > = p0

∞

∑

kq 0k −1 = p0

k =1

= p0

= p0

d dq 0

k 0

= p0

k =1

(−1)(−1) (1 − q 0 )

2

∑ dq k =1

∞

∑q

∞

=

d

(q 0k ) 0

d ⎛ 1 ⎞ ⎜ ⎟ dq 0 ⎜⎝ 1 − q 0 ⎟⎠

p0 (1 − (1 − p 0 )) 2

= p 0−1

Das heißt, mit wachsender Kollisionsfreiheit p 0 (λ, t M ) 6 1 nimmt die Zahl der Pakete ab und die Kanalbelastung sinkt (s. Abb. 11.3).

11.2 Analyse des ALOHA-Protokolls

155

25 20 15

10

p 0 (λ , t M )

5 0 0

0,2

0,4

0,6

0,8

1

Abb. 11.3 Mittlere Versuchsanzahl bis zum Übertragungserfolg in ALOHA

Die mittlere Zahl < r > der Wiederholungen ergibt sich aus dem obigen Wahrscheinlichkeitsansatz sofort zu: =

∑

∞ r =1

r(1 − p 0 ) r =

1 p02

−

1 , p0

und zeigt ein sehr starkes Anwachsen wenn p0 < 1/2 – viel stärker als ! Die weitere Diskussion hängt nun stark vom explizitem Verlauf von p 0 (λ, t M ) ab, welchen wir jetzt für zwei Protokollvarianten bestimmen wollen. Zur vereinfachten Modellierung nehmen wir an, dass die Generierung der Datenpakete durch einen Poisson-Prozess modellierbar ist 0⎯ ⎯→ 1⎯ ⎯→ 2 "k −1 ⎯ ⎯→ k⎯ ⎯→ k +1 λ λ λ λ

k Anzahl der generierten Pakete

p k (t) Wahrscheinlichkeit für k Pakete zum Zeitpunkt t p′k (t) = λp k −1 (t) − λp k (t) k = 1,2... p′k (t) = − λp 0 (t) ~ p 0 (t) = e −λt

p k (t) =

(λ t k ) − λt e k!

156

11 Konzepte zur Analyse von Kommunikationssystemen

Damit ist die Wahrscheinlichkeit, dass kein Paket unterwegs ist, p 0 (λ, t M ) = e − λt M , und 1 − e − λt M = q 0 (λ, t M ) , dass mindestens eins generiert wurde – bezogen auf das Beobachtungsintervall: [0, t M ] . Im nächsten Schritt spezifizieren wir t M für die erste Protokollvariante „jeder kann zu einem beliebigen Zeitpunkt senden“. nachher

m

tN

tN + tP

i

t

0

tA

tA + tP

l vorher tv

tV + tP

Abb. 11.4 Sendeversuch in ALOHA

Der i-te Client soll bei t = t A einem aktuellen Sendeversuch starten: Wenn l-ter Client zum Zeitpunkt t V vorher gesendet hat, muss t V + t p ≤ t A sein, sonst haben wir eine Kollision. Wenn m-ter Client zum Zeitpunkt t N senden will und t N ≤ t A + t P , d. h. Client i ist noch nicht fertig, haben wir eine Kollision, es muss also t N ≥ t A + t P sein (s. Abb. 11.4). Eine Kollisionsfreiheit haben wir also nur dann, wenn t V + t P ≤ t A und t A + t P ≤ t N

Das heißt aber, im Intervall [t A − t P , t A + t P ] mit der Länge 2 t P darf keine Kollision passieren. Damit muss t M = 2t P gewählt werden und es folgt: p0 (λ, t M = 2t P ) = e −2λt P

11.2 Analyse des ALOHA-Protokolls

D(λ, t P ) = λe-2λt P

, < k >=

157

1 2 λt =e p p0

Die Paketübertragungszeit t P ist eine feste, physikalische Systemgröße, aber der zu verarbeitende Durchsatz λ kann natürlich variieren: t P * D(λ, t P ) = (λ * t P ) * e −2λt P

⎛1⎞ D(λ, t P ) = ⎜⎜ ⎟⎟ xe − 2x ⎝ tP ⎠

wobei x = λt P gesetzt wurde. Eine solche dimensionslose Größe ist zur Analyse meistens sehr vorteilhaft. 1/tP ist der theoretisch mögliche Durchsatz Dth, sodass der effektive Durchsatz D(x ) = D th * xe −2x

untersucht werden muss. Es ist D(x = 0 ) = 0 , bei xm = 1/2 hat die Funktion ein Maximum (s. Abb. 11.5) mit

D ⎛1⎞ D D⎜ ⎟ = th < th : 2 2e 5 ⎝ ⎠ 1,2 1

Dth

D(x)

0,8 0,6 0,4

Dm(1/2)

0,2 0 0

0,5

1

1,5 X

Abb. 11.5 ALOHA (Durchsatz) in Abhängigkeit von x = λtP

2

2,5

3

158

11 Konzepte zur Analyse von Kommunikationssystemen

Damit werden im günstigsten Fall knapp 20% der angebotenen und zur Wiederholung bereitstehenden Pakete durch den Übertragungskanal geschleust werden können. Ein bescheidenes Ergebnis! Die Ursache für dieses schlechte Leistungsverhalten liegt in der Protokollcharakteristik „jeder kann senden, wann er will“, welches zu einem exponentiellen Anwachsen der Kollisionen und Wiederholungen führt.

11.3 Eine Verbesserung mit Slotted ALOHA Beseitigt man den Schwachpunkt der willkürlichen Sendung und lässt als Sendezeitpunkte nur ein festes Zeitraster der Länge tp zu (Slotted ALOHA, s. Abb. 11.6), | 0

| tp

| 2tp

| 3tp

| 4tp

t

Sendezeitpunkte Abb. 11.6 Sendezeitpunkte (Slotted ALOHA)

so verbessert sich der Durchsatz deutlich. Das Fenster der Kollisionsfreiheit verkürzt sich von 2tp auf tp und damit gilt: − λt P pSA = e − x , DSA (x ) = D th * xe − x 0 =e

< k SA >= e x , < r SA >= e 2x − e x

Der maximale Durchsatz liegt jetzt bei x m = 1 mit SA

(

)

D th ⎛ 2 ⎞ < ⎜ ⎟ * D th ≈ 0.4 * D th und hat sich praktisch verdoppelt – e ⎝5⎠ die Ursache liegt natürlich in dem günstigeren exponentiellen Verlauf. Zu einem tieferen Verständnis dieses Verhaltens in Abhängigkeit von der Last reicht diese einfache Modellierung nicht aus, vor allem da weder die Zahl m der blockierten Clients, die Zahl n – m der sendebereiten (freien) Clients noch die Wahrscheinlichkeiten s für das Senden eines neu generierten Pakets bzw. r für das Senden eines zurückgestellten (kollidierten) Pakets bisher eine Rolle spielten. SA DSA eff x m = 1 =

11.3 Eine Verbesserung mit Slotted ALOHA

159

Man kann jedoch eine entsprechende Analyse auf der Grundlage eines Markoff’schen Modells vornehmen (s. Abb. 11.7). Die Zufallsvariable m = 0…n wäre die Anzahl der durch Wiederholungen blockierten Clients mit folgendem Übergangsdiagramm:

m:

0← ⎯⎯ 1← ⎯⎯ 2 ← ⎯⎯ 3.......

n

.

π0

π1 …

πn

Abb. 11.7 Markoff-Modell für „Slotted ALOHA“

Die Bestimmung der π0…πn verläuft nach dem üblichen Muster, wenn auch technisch etwas aufwendiger, und soll deshalb hier nicht aufgeführt werden. Etwas intuitiver und zunächst auch sehr viel einfacher ist folgende Argumentation. Der angebotene Durchsatz D, auf der Grundlage des „Slotted ALOHA“, setzt sich aus zwei Anteilen zusammen: • den nicht blockierten (n – m) Clients, welche mit der Wahrscheinlichkeit s eine Nachricht im aktuellen „Slot“ senden wollen, im Mittel also (n – m)*s Clients, • den m blockierten Clients, welche eine kollidierte Nachricht mit der Wahrscheinlichkeit r senden möchten – im Mittel m*r. Bezogen auf den Zeitslot tp können wir zur Durchsatzbestimmung das Gesetz von Little heranziehen: • λ*tp ≈ gc(m), das ist die mittlere Anzahl sendewilliger Clients auf dem Kanal gc(m) = (n – m)*s + m*r • für den angebotenen Durchsatz D folgt somit D = gc(m)/tp; da tp eine feste, für den Kanal typische Konstante, kann auch zur dimensionslosen Größe (tp*D) = gc(m) = (n – m)*s + m*r übergegangen werden, und haben damit ein bewährtes und schon oft angewandtes Verfahren, wobei D aber den angebotenen und nicht den realen Durchsatz Deff auf dem Kanal darstellt (s. Abb. 11.8).

160

11 Konzepte zur Analyse von Kommunikationssystemen

tp*D s*n m*r m n Abb. 11.8 Angebotener Kanaldurchsatz

Für den effektiven Durchsatz gilt nämlich wie bereits weiter oben argumentiert: Deff = λ*p (keine Kollision, d. h. kein zusätzliches Paket auf dem Kanal) = λp0(λtp) = λe–λtp für die Poisson-Ankunftsverteilung ⎛1⎞ ⎛ λt p ⎞ − λt p − λt ⎟⎟e = ⎜ ⎟ * λt p e p = D th ⎜⎜ = D th p1 λt p ⎜ tp ⎟ ⎝ 1! ⎠ ⎝ ⎠

( )

(t

Wie p

eben,

) ( )

* Deff = λt p e

( )

gehen − λt p

wir

= g c (m )e

wieder

− g c (m)

auf

die

dimensionslose

Größe

= g K (m) , welche der mittleren Anzahl der

vom Kanal bewältigten Nachrichten/Pakete entspricht (s. Abb. 11.9). tpDth 1 gK(m) gC(m)

2/5 Dth

s*n

m1

Abb. 11.9 Kanaldurchsatz

m*

m2

n

m

11.4 Eine anspruchsvollere Analyse von Slotted ALOHA

161

Den maximalen Durchsatz ≈ (2/5) erhält man über g’K(m*) = 0 zu gK(m*) = 1, d. h. m* = (s/(r – s))*n. Solange m1 ≤ m* ≤ m2 gilt, befindet man sich im Unterlastbereich, da gK(m) > gc(m), d. h. das Angebot liegt unterhalb der Verarbeitungskapazität. Am stabilsten ist der Arbeitspunkt m1, da hier einmal die Zahl der blockierten Clients minimal ist und der Durchsatz des Kanals bei einer Zunahme von m immer noch ansteigt. Dies gilt z. B. für m* und m2 nicht mehr.

11.4 Eine anspruchsvollere Analyse von Slotted ALOHA Alternativ zu diesen rein heuristischen Überlegungen kann man auch etwas konsequenter von einem simplen Bernoulli-Modell für den „Sender-Prozess“ ausgehen, welches dann durch eine realistische Näherung auf das Poisson-Modell führt. Dazu betrachten wir: • die Wahrscheinlichkeit ps(i, m), dass i freie Clients im nächsten Slot ein neu generiertes Paket senden, ist: ⎛n − m⎞ i ⎟⎟ * s * (1 − s )n − m −i p S (i, m ) = ⎜⎜ i ⎝ ⎠ • die Wahrscheinlichkeit pr(i, m), dass i blockierte Clients im nächsten Slot ein kollidiertes Paket senden, ist: ⎛ m⎞ p r (i, m ) = ⎜⎜ ⎟⎟ * r i * (1 − r )m −i ⎝i⎠

Dann ist die Wahrscheinlichkeit p(1), dass ein Paket mit Erfolg auf den Weg gebracht wird: p(1) = p s (1, m )* p r (0, m) + p s (0, m) * p r (1, m)   

  

F

K

Die beiden Anteile F (frei) und K (kollidiert) werden wir jetzt mit einigen technischen Umformungen so verändern, dass die Abhängigkeiten von (n – m, m, s, r) deutlich werden. Natürlich kann man p(1) auch einfach in einen plot-Befehl von Maple [11] oder Mathematica [12] stecken, die analytische Behandlung bringt jedoch deutlich größere Chancen auf ein besseres Verständnis. Es ist:

162

11 Konzepte zur Analyse von Kommunikationssystemen

⎛n - m⎞ 1 ⎛m⎞ ⎟⎟ * s * (1 − s )n - m −1 * ⎜⎜ ⎟⎟ * r 0 * (1 − r )m −0 , F = p s (1, m )* p r (0, m ) = ⎜⎜ 0⎠ 1 ⎝⎠  

⎝  

FA

FB

und wir wenden jetzt für FA und FB die Poisson’sche Näherung an: FA ≈

((n − m ) * s )1 * e−(n − m)*s , 1!

FB ≈

((m − 0) * r )0 * e−(m-0)*r 0!

Damit ist der Beitrag von den freien Clients F ≈ (n − m) * s * e − (n − m)*s − m*r

wobei n – m, m >> 1 und s, r s: ein kollidiertes Paket wird eher gesendet als ein neu generiertes Paket; mit wachsendem r fällt der Kanaldurchsatz dramatisch mit m ab. r = s: der Durchsatz ist eine Konstante n*s*e–n*s, die nicht weiter von m abhängt. r < s: die Glockenkurve wird nach rechts verschoben, allerdings nicht symmetrisch. Ansonsten können wir uns auf die früheren, rein heuristischen Analysen zurückziehen – vor allem was den Betrieb am Gleichgewichtspunkt betrifft.

12 Modell und Wirklichkeit

Das schwierigste Problem der Leistungsanalyse ist die Übereinstimmung von dem modellierten System mit der Wirklichkeit. Klarerweise kann ein Modell nicht alle Aspekte des untersuchten realen Systems wiedergeben, dann bräuchte man ja nicht zu modellieren.

12.1 Bemerkungen zu den Modellvoraussetzungen Am transparentesten und praxisnächsten ist der Ansatz, sich bei der Modellierung auf ganz wenige Kontrollstrukturen und die sie repräsentierenden Variablen zu beschränken. Nehmen wir z. B. einen eLearning-Server, dessen Verhalten sicherlich von einer Vielzahl von Größen wie Prozessorgeschwindigkeit, Hauptspeichergröße, Zahl der offenen TCP-Ports, aber auch der Anzahl N der Nutzer bestimmt wird. Deren Struktur und gegenseitige Abhängigkeiten sind in Bezug auf das Leistungsverhalten sehr schwer und auch nur unter nicht beweisbaren Annahmen zu modellieren, sodass es unter Umständen wesentlich günstiger erscheint, sich auf die Auslastung ρ, den Durchsatz D und die mittlere Antwortzeit zu beschränken. Diese sind entweder direkt bestimmbar oder aber aus anderen leicht zugänglichen Größen wie die Aktivzeit tA und der Messzeit tM ableitbar: ρ=

tA = t S (1) * D tM

D=

1 t * A = D theor * ρ t S (1) t M

Damit gilt

166

12 Modell und Wirklichkeit

wobei Dtheor = (1/ts(1)) den theoretisch möglichen maximalen Durchsatz darstellt. Da 0 ≤ ρ ≤ 1 gilt D ≤ Dtheor. Wenn wir jetzt einmal unterstellen, dass unser reales System durch ein M(λ)/M(μ)/1/∞-Modell (s. Kap. 7) mit der Ankunftsrate λ und der Bearbeitungsrate μ repräsentiert werden kann, dann folgt (Kap. 6, 7) für den Durchsatz D=

∞

∑μ π ; k k

k =1 ∞

=μ

∑π

k

μ k = μ k = 1...∞

= μ(1 − π0 ) = μ(1 − (1 − ρ)) = μρ

k =1

wobei ρ = λ/μ. Da μ = 1/ = Dtheor, gilt letztendlich DModell = ρ*Dtheor, also eine ähnliche Beziehung wie im empirischen Auslastungsgesetz der obigen Ausführungen. Dies beweist aber hinsichtlich der Modellgültigkeit überhaupt nichts, vielmehr müssen wir nachweisen, dass sowohl der statistische Ankunfts- als auch der entsprechende Bearbeitungsprozess einer Exponentialverteilung, z. B. p λ ( t ' ≤ t ) = 1 − e − λt

(das gleiche für μ) genügt, wobei pλ(t’ ≤ t) = fλ(t) die Wahrscheinlichkeitsverteilung für das zu analysierende Ereignis, z. B. die Ankunft von Transaktionen mit der Rate λ, darstellt. Die Wahrscheinlichkeitsdichte dλ(t) ergibt sich als Ableitung:

dλ (t) =

d p λ ( t ' ≤ t ) = λe − λt , dt

sodass wir damit den Mittelwert über ∞

∞

0

0

∫

∫

< t >λ = dt t * d λ ( t ) = dt (λt )e− λt =

∞

∫

1 1 d(λt )(λt )e − ( λt ) = λ λ 0

berechnen können, die Standardabweichung ergibt die Quadratwurzel des gleichen Wertes.

12.2 Ein explizites Beispiel

167

12.2 Ein explizites Beispiel Wie entscheidet man nun, ob gemessene Daten einer solchen Verteilung genügen? Wir demonstrieren die Vorgehensweise an einem Beispiel. An fünf Messpunkten texp(1..5) wird die empirische Verteilung fexp(1..5) wie im Kap. 5 bestimmt; es ergeben sich folgende Werte: texp

0

1/2

1

2

4

fexp

0

2/5

3/5

9/10

0,98

welche die Zwischenankunftszeiten bzw. deren Wahrscheinlichkeitsverteilung von Transaktionen in dem eLearning-Server darstellen sollen. Zunächst bestimmen wir λ über e − λt = 1 − f λ ( t ) ln e −λt = −λt = ln(1 − f λ ( t ))

wobei wir anstelle der kontinuierlichen Variable t die obigen Messwerte einsetzen * λt exp (k ) = − ln(1 − f exp (k )) = f exp (k )

Es ergibt sich fexp(k)

0

2/5

3/5

9/10

0,98

f*exp(k)

0

1/2

9/10

23/10

38/10

wobei die Werte genähert sind. Da λk = f*exp(k)/texp(k), berechnen wir dieses Verhältnis für alle k = 1…5: λk

/

1

9/10

11/10

19/20

d. h. λ ~ 1 ist ein akzeptabler Näherungswert. Die Paare (λ*tk, f*exp(k)) = (1*tk, f*exp(k)) sollten jetzt in etwa auf einer Geraden liegen, was durch einen Plot bestätigt wird (s. Abb. 12.1).

168

12 Modell und Wirklichkeit

f*

4

2

t 2

4

*

Abb. 12.1 Plot von (1*tk, f exp ( k ) ); k = 2,…., 5

Sinnvollerweise wird man diese Gerade durch das Verfahren der linearen Regression (Methode der kleinsten Quadrate) bestimmen. Dazu berechnen wir zunächst die Mittelwerte. 5

∑

< t exp >=

1 1 15 3 t exp (k ) = * = 5 k =1 5 2 2

* < f exp >=

1 1 74 3 * f exp (k ) = * ~ , 5 k =1 5 10 2

5

∑

sodass nach dem üblichen Verfahren die Regressionsgerade der Gleichung = a* + b = 3/2 = (3/2)a + b genügt, wobei a, b durch die Forderung 5

∑ k =1

5

* * (f exp (k ) − < f exp >) 2 =

∑ (f

* 2 exp ( k ) − a * t exp ( k ) − b)

= Min!

k =1

festgelegt sind. Differenzieren nach a bzw. b und null Setzen der entsprechenden Ableitungen liefert:

12.2 Ein explizites Beispiel

169

5

∑ 2( f

* exp (k ) − a * t exp ( k ) − b)(− t exp ( k ))

∑ 2( f

* exp (k ) − a * t exp ( k ) − b)(−1)

=0

k =1 5

=0

k =1

Die zweite Gleichung ist nichts anderes als die Mittelwertgleichung = a* + b, wir lösen nach b auf und setzen in die erste Gleichung ein: 5

a=

∑f

* * exp ( k ) t exp ( k ) − 5* < f exp

>< t exp >

k =1

5

∑t

2 exp ( k ) − 5* < t exp

>2

k =1

Mit den Werten unseres Beispiels ergibt sich diesbezüglich 5

∑

2 t exp (k ) =

k =1

85 ~ 21 , 4

5

∑f

* exp ( k ) * t exp ( k )

k =1

=

830 ~ 21, 40

sodass a ~ 1 und b ~ 0, was aufgrund der Daten auch nicht anders zu erwarten ist. Die Regressionsgerade f*reg = 1*t gilt für alle Werte t im Messbereich [texp(1), texp(5)] = [0, 4]. Ihre Güte wird durch das Maß 5

r=

∑ (f

* * 2 exp ( k ) − f reg ( k ))

∑ (f

* < f exp >) 2

k =1 5

* exp ( k ) −

k =1

bestimmt, wobei f*reg(k) = a*texp(k) + b. Ist r = 1, haben wir keine Gerade vorliegen, während r = 0 mit Sicherheit eine Gerade ergibt; p = 1 – r ist die entsprechende Wahrscheinlichkeit. In unserem Beispiel ist f*reg(k) ≈ 1*texp(k) ≈ fexp(k) für k = 1..5, d. h. alle Differenzen im Zähler von r verschwinden und damit ist r ≈ 0, p = 1 – r ≈ 1, woraus mit Sicherheit eine Regressionsgerade folgt. Damit können wir für die empirischen oder experimentellen Daten eine Exponentialverteilung unterstellen: pλ ( t ' ≤ t ) = 1 − e − λt = 1 − e −1*t ; λ ≈ 1 < t >= (1 / λ ) ≈ 1

und eine Modellierung des Ankunftsprozesses vom Markoff-Typ als gerechtfertigt ansehen. Bezüglich der Bearbeitung mit der Rate μ würde man entsprechend vor-

170

12 Modell und Wirklichkeit

gehen. In der Praxis genügt es häufig, eine weitgehende Konstanz, d. h. λk ≈ λ für alle Messpunkte k = 1...n, zu überprüfen.

12.3 Modelle des G/M/1/∞-Typs mit nicht bekannter Ankunftsverteilung Was unternimmt man aber, wenn über den Verteilungstyp der Ankunfts- bzw. Bedienprozesse keine oder nur eingeschränkt Aussagen gemacht werden können? Klarerweise wird die diskutierte Argumentationskette zur Berechnung der Zustandswahrscheinlichkeiten und der entsprechenden Leistungsmaße nicht mehr anwendbar sein. Will man dennoch den bereits erhaltenen Ergebnissen eine Relevanz zugestehen, empfiehlt sich eine Vorgehensweise, welche die Resultate der Analyse von Exponentialverteilungen um Korrekturen ergänzt. Von L. Kleinrock et al. [1] ist dies sehr transparent und effizient vorgestellt worden, allerdings sprengen die dort verwandten mathematischen Techniken unseren Diskussionsrahmen. Wir skizzieren daher nur die wichtigsten Schritte und beginnen unter einem Modell, bei dem der Bedienprozess vom Typ Markoff ist, B( t B ≤ t ) = 1 − e −μt für die Verteilung der Bedienzeit, während über die Verteilung der Zwischenankunftszeit A(τ ≤ t ) nichts bekannt ist (G für General, Modellbezeichnung G/M(μ)/1/∞); meistens ist sie aber empirisch vorgegeben und man kennt Mittelwert sowie Standardabweichung. Wenn der Auftrag/Client Ck zum Zeitpunkt tk in das System kommt, warten dort bereits wk Clienten. Trifft ein weiterer Auftrag/Client Ck+1 zum Zeitpunkt tk+1 ein, so ist τ k = tk +1 − tk die Zwischenankunftszeit und w k +1 = w k +1 − s k +1 Clienten warten auf Bearbeitung; sk+1 werden in der Zwischenzeit τk bedient; Abb. 12.2 verdeutlicht die Situation. wk+1

wk

0 Ck+1 tk+1

Ck tk sk+1 Abb.12.2 G/M/1/∞

t

12.3 Modelle des G/M/1/∞-Typs mit nicht bekannter Ankunftsverteilung

171

Die Elemente pij der Übergangsmatrix P (s. Kap. 7, 8, 9) bestimmen sich zu pij( k ) = prob( w k +1 = j / w k = i)

= prob(i + 1 – j Aufträge werden während τk bedient), man beachte, dass τk die Zwischenankunftszeit darstellt! Klarerweise muss man über alle vorkommenden Zwischenankunftszeiten τk (k = 0, 1,…) summieren: pij =

∞

∑

pij( k ) =

k =0

∞

∑ prob (i + 1 – j Clienten bedient in τ = τ ) prob(τ = τ ) k

k

k =0

wobei jedes τk einen Basiswert darstellt und wir den Satz über die vollständige Wahrscheinlichkeit1 benutzt haben. Die diskrete Summation kann man durch ein Integral ersetzen ∞

∫

p ij = prob(i + 1 − j Clienten bedient/τ) a(τ)dτ 0

die Funktionen a(τ) = dA(τ)/dτ = A’(τ) stellt die Dichte der Zwischenankunftsverteilung dar. Nach Voraussetzung ist unser Bedienprozess mit der Rate μ vom Markoff-Typ, daher gilt i+1-j prob(i + 1 – j Clienten bedient in τ) = (μτ) e-μτ (i+1-j)! sodass für das Übergangsmatrixelement pij letztlich folgt ∞

pij = ∫ dτa(τ) 0

(μτ)i+1-j -μτ e (i+1-j)!

Mit i + 1 – j ≥ 0 resultiert sofort pij = 0 für j > i + 1, denn bereits „abwesende“ Clienten/Aufträge werden natürlich nicht mehr abgefertigt. Damit sind alle Ele-

1 Sei (Ak) ein vollständiges Ereignissystem und B ein beliebiges Ereignis. Sind die bedingten Wahrscheinlichkeiten prob (B/Ak) und die Wahrscheinlichkeiten prob (Ak) bekannt, so gilt

prob( B) = ∑ prob( B / A k ) * prob( A k ) k In unserem Fall ist Ak = (τ = τk) und B = (i + 1 – j Clienten bedient)

172

12 Modell und Wirklichkeit

mente der Matrix P bekannt und die stationären Zustandswahrscheinlichkeiten πk ergeben sich aus dem linearen Gleichungssystem (π0, π1, π2, …) = (π0, π1, π2, …) P πj =

∞

∑π p

für j ≥ 0

i ij

i =0

Die explizite Lösung lässt sich ohne Probleme angeben, man kann aber auch wie folgt argumentieren. Die Bedienung ist „Markoff“ und deshalb liegt eine geometrische Verteilung der πj wie bei M/M/1/∞ nahe. Mit dem Ansatz πj = N*σj, wobei N eine Normierungskonstante und 0 < σ < 1 lässt sich formulieren: ∞

πj = N* σj=

∑ N*σ p i

ij

i =0

∞

σj =

∑σ p i

ij

j≥0

i =0

Wir dividieren beide Seiten durch σ bezüglich der Poisson-Bedingung: σ1 = σ =

∞

∑

j −1

und ersetzen pij durch das obige Integral

∞

∫

σi +1− j dτa(τ)

i =0

0

(μτ)i +1− j −μτ e (i + 1 − j)!

was für alle j ≥ 1 gilt. Die Summation kann man unter das Integral ziehen σ=

∫

∞ 0

⎡ ∞ (σμτ)i +1− j ⎤ −μτ dτa(τ) ⎢ ⎥e ⎣⎢ i = 0 (i + 1 − j)! ⎦⎥

∑

und explizit ausführen2, sodass schlussendlich die Beziehung

2

(σμτ)i +1− j = eσμτ ; j =1 genügt! i = 0 (i + 1 − j)! ∞

∑

12.4 Modell mit deterministischer Ankunftszeit

173

∞

σ=

∫ dτa(τ)e

− (1−σ ) μτ

0

zur Bestimmung von σ bleibt. Eine Lösung σ = 1 kennen wir, sie ist trivial 1=

∫

∞ 0

dτa(τ)

da dies für die Wahrscheinlichkeitsdichte sowieso gilt. Für die Fälle 0 < σ < 1 muss a(τ) explizit bekannt sein oder aus empirischen Daten durch ein Näherungsverfahren bestimmt werden. Wir testen unser Vorgehen zunächst, indem wir für die Ankunft einen Markoff− λτ

− λt

Prozess nehmen, d. h. A ( t ) = 1 − e , a ( t ) = λe , und unser M/M/1/∞Resultat reproduzieren. Einsetzen in obiges Integral ergibt ∞

∫

σ = dτλe − λτe − (1− σ) τ = 0

λ 1 + (1 − σ)μ

mit den Lösungen σ1 = 1 und σ2 = λ/μ = ρ; natürlich nehmen wir σ2 = ρ. Die Normierung N berechnet sich auf dem üblichen Weg (Kap. 7) zu N = 1 – σ2 = 1 – ρ und damit erhalten wir das bekannte geometrische Verteilungsmuster π k = (1 − σ 2 )σ k2 = (1 − ρ)ρ k (k = 0, 1, …) sowie die entsprechenden Leistungsgrößen.

12.4 Modell mit deterministischer Ankunftszeit Ein etwas akademisches, aber leicht zu rechnendes Beispiel eines echten G/M/1/∞-Modells ist G = D, d. h. die Zwischenankunftszeit ist fest, wie etwa die Time-Slots beim ALOHA-Protokoll in Kap. 11. Für die entsprechende Verteilung A(t) bedeutet dies A( t ≤ t A ) = θ( t − t A ) =

1 wenn t – tA ≥ 0 0 sonst

174

12 Modell und Wirklichkeit

Die Ableitung nach der Zeit A’(t) = a(t) ist die berühmte Dirac- oder Impulsfunktion a(t) = δ(t – tA) mit der Eigenschaft ∞

∫ dtδ(t − t

A )f ( t )

= f (t A )

0

Einsetzen in unsere Bestimmungsgleichung für σ ergibt ∞

∞

0

0

∫

∫

σ = dta ( t )e − (1− σ)μt = dtδ( t − t A )e − (1− σ)μt = e − (1− σ)μt A

wobei wir die triviale Lösung σ1 = 1 leicht erkennen. Zum Auffinden der zweiten Lösung 0 < σ2 < 1 müssen wir die rechte Seite etwas genauer analysieren r (σ) = e − (1− σ)μt A r (0) = 1 / eμt A

r ' (0) = μt A / eμt A < 1

r (1) = 1

r ' (1) = μt A

und man erkennt sofort, dass das Verhalten von r(σ) stark von μtA abhängt (s. Abb. 12.3).

μtA = 1

σ

μtA = 2

Abb. 12.3 r(σ) = exp (-(1 – σ)μtA) geschnitten mit σ

μtA = 4

12.4 Modell mit deterministischer Ankunftszeit

175

Wenn r’(1) = μtA ≤ 1 finden wir überhaupt keinen Schnittpunkt, nur r’(1) = μtA > 1 liefert einen relevanten Beitrag. Zunächst bedeutet dies tA > (1/μ) = , d. h. die Zwischenankunftszeit muss größer als die mittlere Bearbeitungszeit sein. Weiterhin ist die Ankunftsrate λ = 1/tA, sodass μtA = μ/(1/tA)= μ/λ = 1/ρ > 1 – damit haben wir aber unsere altbekannte Stabilitätsbedingung ρ < 1 wieder. Eine exakte Lösung von r(σ) = σ ist natürlich nicht möglich, aber für μtA > 1 können wir r(σ) linearisieren. r (σ) ≈ r (0) + σr ' (0) = e −μt A + σμt A e −μt A ≈ σ

=> σappr =

1 e

μt A

− μt A

~

1 e

μt A

=

1 1/ ρ

e

;0= ρ + ρ 2

1 + C 2B ρ ⎛ ρ 2 ⎞ = ⎜1 − (1 − C B ) ⎟ 2(1 − ρ) 1 − ρ ⎝ 2 ⎠

Da = ρ/(1 – ρ) die mittlere Anzahl in Aufträgen im Standardmodell M/M/1/∞, folgt ⎞ ⎛ ρ < k >=< k Std > ⎜1 − (1 − C 2B ) ⎟ ⎠ ⎝ 2 Die Verweilzeit bestimmt sich aus dem ersten Gesetz von Little λ* =

(

)

, der Korrekturfaktor 1 − ρ(1 − C B ) / 2 bleibt erhalten. Bilden wir den Speed-Up /, so ist dieser gerade der Kehrwert des Korrekturfaktors Sp =

2

1 1−

ρ (1 − C 2B ) 2

=

2 2 − ρ(1 − C 2B )

≤2

2

Eine hohe Auslastung ρ ~ 4/5 und C B < 1, d. h. eine sehr schmale Verteilung der Bedienzeit, ergeben einen mageren Speed-Up von 50–60%, sonst liegt er noch deutlich darunter. Wählen wir etwa für die Verteilung der Bedienzeit G = D, B( t ) = θ( t − t B ) , b( t ) = δ( t − t B )

12.6 Beispiel zu einem Modellvergleich

177

so erfolgt die Bearbeitung in einem festen Takt. Damit ist σ 2B = 0 (Impulsverteilung), es folgt Sp = 2/(2 – ρ) und wir sind bei den obigen Werten. Alle Verteilungen G, bei denen C 2B > 1 , also sehr breite Verteilungen, sind noch ungünstiger, da der Nenner im Speed-Up in diesem Fall anwächst und einen Wert kleiner 1 produziert. Damit haben wir eine einfache Abschätzung für eine ganze Klasse von Modellen gegenüber dem transparenten Standard M/M/1/∞. Eine Verallgemeinerung auf G/G/1/∞ erfordert noch einmal einen höheren Aufwand an mathematischen Techniken, ohne dass damit ein praktisch umsetzbarer Erkenntnisgewinn verbunden ist – wir verzichten und verweisen auf die Darstellungen bei L. Kleinrock [1]. Wegen ihrer Relevanz für die praktische Anwendung übernehmen wir jedoch von dort eine robuste Nährung für die Wartezeit bei ρ ≈ 1 (heavy traffic approximation): < t W >≈

λ σ2A + σ 2B 2 1− ρ

wobei ρ = /, λ = 1/ und σA bzw. σB die Standardabweichung/Varianz des Ankunfts- und Bedienprozesses (man überzeuge sich von der Qualität der Approximation im Fall M(λ)/M(μ)/1/∞ selbst).

12.6 Beispiel zu einem Modellvergleich Zum Abschluss der Diskussion wollen wir noch den expliziten Vergleich zweier Modelle durchführen und zwar M(λ)/M(μ)/1/∞ versus M(λ)/M(μ)/2/∞, welchen wir ansatzweise in einem Beispiel schon in Kap. 9 skizziert haben. Wir konzentrieren uns dabei auf die Wartewahrscheinlichkeit pW, die mittlere Verweilzeit , den Durchsatz D und den Speed-Up S. Beginnen wir mit der Wartewahrscheinlichkeit pW, welche im Standardmodell M/M/1/∞ der Beziehung p (W1) = ρ = λ / μ genügt. Nach den in Kap. 9 entwickelten Konzepten folgt für das Modell mit zwei Prozessoren M/M/2/∞ 2

p(W2) =

3

π2 ⎛ ρ ⎞ 1 − ρˆ , ρˆ = ρ / 2 , π2 = 2⎜ ⎟ 1 − ρˆ ⎝ 2 ⎠ 1 + ρˆ

3

ˆ ) /(1 + ρˆ ) , Für M/M/2/∞ gilt μπ1 = λπ 0 und 2μπk = λπ k −1 , k ≥ 2, damit folgt π 0 (1 − ρ

π k = 2ρˆ k π 0 und ρˆ = λ / 2μ = ρ / 2 .

178

12 Modell und Wirklichkeit

Einsetzen und Umformen liefert p (W2) = ρ 2 /( 2 + ρ) , sodass sich für das Verhältnis der Wahrscheinlichkeiten zu ρ p(W2) 1 = ≤ (1) pW 2 + ρ 3

berechnet, d. h. wir gewinnen 60% beim Warten. Bezüglich der Verweilzeiten ergibt sich ⎛ p (1) ⎞ 1 < t (V1) >=< t S > ⎜1 + W ⎟ =< t S > ⎜ 1− ρ ⎟ − ρ 1 ⎝ ⎠ ⎛ 1 p (W2) ⎞ ⎟ =< t S > 4 < t (V2) >=< t S > ⎜1 + ⎜ 2 1 − ρˆ ⎟ 4 − ρ2 ⎝ ⎠

und wir bekommen einen auslastungsabhängigen (ρ) Speed-Up S=

< t (V1) > < t (V2) >

=

1 4 − ρ2 4 1− ρ

4 1 welcher monoton ansteigt, z. B. S(ρ = ) ~ 2 und S(ρ = ) ~ 4 , 5 2 d. h. aber, nur bei sehr hohen Auslastungen ρ ≥ 4/5 wird man über den Faktor 2 hinauskommen, für ρ < 1/2 hat man einen schwachen linearen Anstieg S ~ 1 + ρ. Betrachten wir jetzt als letzte Leistungsgröße den Durchsatz

D=

∞

∑μ

k

* πk

k =1

Für M/M/1/∞ gilt μk = μ für alle k ≥ 0, also D(1) =

∞

∑ k =1

μπk = μ

∞

∑π k =1

k

= μ(1 − π0 ) = μρ = λ

12.6 Beispiel zu einem Modellvergleich

179

Dies bedeutet, es kann nicht mehr durchgesetzt/verarbeitet werden, als ankommt, aber eben auch nicht weniger. Beim M/M/2/∞-Modell ist μ1 = μ und μk = 2μ für k ≥ 2, sodass D ( 2) = μ1 * π1 +

∞

∑ k =2

2μπ k =μπ1 + 2μ

∞

∑π

k

k =2

= μπ1 + 2μ(1 − π 0 − π1 ) = 2μρˆ = 2μλ / 2μ = λ

Dieses Ergebnis mag auf den ersten Blick überraschend sein, da wir doch bei M/M/2/∞ zwei Prozessoren einsetzen, um die angebotene Last λ abzuarbeiten. Da wir aber Stationarität und statisches Gleichgewicht sowie einen unendlichen Wartepool vorausgesetzt haben, gilt genau die gleiche Argumentation wie bei M/M/1/∞ – es kann nicht mehr und nicht weniger verarbeitet werden wie angeboten. Würde man den Speed-Up auf der Grundlage von S = D / D berechnen, käme 1 heraus und man würde sich fragen, was der ganze „Modell-Bau“ soll, da er eindeutig gegen die Erfahrung und den gesunden Menschenverstand verstößt. Die Ursache liegt natürlich in den Voraussetzungen, welche man machen muss, um die Modelle überhaupt aufstellen zu können und die leider zu oft in den Hintergrund treten. ( 2)

(1)

13 Über die Gültigkeit von Gesetzen

Als Fazit der Diskussion von Modellvarianten zeigt sich, dass dem bereits in Kap. 3 eingeführten Speed-Up auch bei dieser Thematik eine nicht zu unterschätzende Bedeutung als Leistungsmaß zukommt. Ganz wesentlich dafür ist seine Unabhängigkeit von speziellen Eigenschaften der zu untersuchenden Systemen – diese drückt sich dahingehend aus, dass nur wenige und leicht messbare Größen sein Verhalten bestimmen. Diesem Vorteil steht eine gewisse Unsicherheit bezüglich der Amdahl’schen oder Gustafson’schen Formulierung des Speed-Ups mit ihren zahllosen Varianten gegenüber – zudem wird häufig mit rein sequentiellen (skalaren) Systemen verglichen, was streng genommen kaum zulässig ist. Von besonderem Interesse ist heute aber eigentlich die Größenskalierung echter Parallelsysteme, welche durch die erwähnten Ansätze nur unvollständig erfasst wird. Zur besseren Analyse der Problematik wollen wir auf der Grundlage des Durchsatzes beide Gesetze noch einmal kurz ableiten, mögliche Zusammenhänge und ein einfaches Modell diskutieren sowie den Einfluss der Kommunikation untersuchen. Zum Speed-Up ist es häufig zweckmäßig, die Effizienz als Quotienten von gemessenem und theoretisch möglichem Durchsatz zu betrachten; diese Größe spielt bei der Messung über den Linpack-Benchmark eine große Rolle.

13.1 Die Skalierung nach Amdahl und Gustafson Das betrachtete System besteht aus p Teilsystemen (Prozessoren), die Anwendung habe die Dimension n, welche bei p = 1 die Zeit tV benötigt. Der Durchsatz des Einprozessorsystems (p = 1, sequentielle Verarbeitung) ist D1 = n/tV.

182

13 Über die Gültigkeit von Gesetzen

Bei Parallelbetrieb p > 1 läuft der Zeitanteil (1 – α)tV nur sequentiell und der Rest αtV (0 ≤ α ≤ 1) parallel, d. h. aber αtV → (αtV)/p. Da n unverändert bleibt, folgt Dp =

n

=

αt (1 − α) t V + V p

n 1 1 = D1 α tV 1− α + α 1− α + p p

sodass sich für den Speed-Up nach Amdahl S A (α , p ) =

Dp D1

=

1 1− α +

α p

, 0 ≤ α ≤ 1, p ≥ 1

ergibt. Es handelt sich also bei Amdahl um eine Skalierung der Verweilzeit tV im Gegensatz zu Gustafson, wo die Problemgröße n skaliert. Wir zerlegen n in einen sequentiellen nseq = (1 – β)n und in einen parallelen nll = βn, 0 ≤ β ≤ 1 Anteil. Dieser kann bei Einsatz von p Prozessoren nun um den Faktor p*nll = p*β*n vergrößert/skaliert werden, also n’ = nseq + p*β*n= (1 – β)n + p*β*n. Für den Durchsatz D′p = n’/tV folgt damit D′p =

(1 − β)n + p * β * n ⎛ n ⎞ = ⎜⎜ ⎟⎟(1 + (p − 1)β) tV tV ⎠ ⎝

D1

und für den Speed-Up also SG (β, p) =

D′p D1

= 1 + (p − 1)β

welcher im Gegensatz zu SA(α, p) ein lineares (skaliertes) Verhalten in β und p aufzeigt. Solch ein Verhalten hat SA(α, p) nur im Fall α =1, d. h. wenn es keinen sequentiellen Zeitanteil gibt (SA(1, p) ~ p). Ganz allgemein gilt beim Einsatz von p Prozessoren D(p) = S(p)*D(1) und somit eine Skalierung bezüglich der skalaren Verarbeitung (p = 1). Eine relative Skalierung [14] könnte man wie folgt angehen D(p) = S(p) * D(1) =

S(p) S(p) * p * D(1) = * D th (p) p p

13.1 Die Skalierung nach Amdahl und Gustafson

183

Dth(p) ist der theoretisch mögliche Durchsatz von p Prozessoren, die Größe ε(p) = S(p)/p mit 0 ≤ ε(p) ≤ 1 heißt Effizienz. Wenn ε(p) ~ const bei p >> 1 oder p → ∞, dann gibt ε(p) ~ const ~

S(p' ) =

S(p) S(p' ) mit p’ > p ~ p p'

p' S(p) = p’ ε(p) p

d. h. wir haben jetzt eine relative Skalierung, p’ gegen p. Machen wir z. B. eine Zeitskalierung à la Amdahl ε A ( p) =

S A (α, p) 1 = → 0 bei p → ∞ p (1 − α)p + α

so werden wir keinen relativen Speed-Up bei einer größeren Prozessorzahl p’ erwarten können. Anders ist die Situation bei Gustafson ε G ( p) =

SG (β, p) 1 − β = + β → β bei p → ∞ p p

bei der von vornherein feststeht, dass eine Steigerung um (p’/p) möglich ist. Wie bereits einmal erwähnt, existiert schon sehr lange eine gewisse Unzufriedenheit mit beiden Gesetzen (Amdahl, Gustafson) und es wurden viele Ansätze zur Verbesserung der Situation entwickelt [15, 16] – von durchschlagenden Erfolg kann man bei keinem sprechen. So wurde zum Beispiel von Shi [17] der folgende Zusammenhang zwischen α und β elaboriert

⎛ ⎞ β ⎜⎜1 + * β ⎟⎟(1 − α) = 1 − β 1 ⎝ ⎠ welcher die Umrechnung dieser Koeffizienten erlaubt. Dies ist erheblich konsequenter als das einfache Gleichsetzen, obwohl es von den Voraussetzungen völlig klar ist, dass man dies nur in Spezialfällen tun kann. Trotzdem ist bei der Shi’ schen Relation eine gewisse Skepsis angebracht, da hierbei eine p-Abhängigkeit von α, β fortgeschrieben wird, die weder die Formulierung von Amdahl noch die von Gustafson hergibt.

184

13 Über die Gültigkeit von Gesetzen

13.2 Verallgemeinerte Durchsatzskalierung Van Catledge [18] hat einen interessanten Ansatz konzipiert, der im Prinzip wie folgt auf unsere Art der Durchsatzbetrachtungen übertragen werden kann: n (k ) = (1 − β)g1 (k ) + β f1 (k ) ⎛ ⎞ α t V (k ) = ⎜⎜ (1 − α)g 2 (k ) + f 2 (k ) ⎟⎟cpi * takt −1 p ⎝ ⎠ n (k ) takt (1 − β)g1 (k ) + β f1 (k ) D(p, k ) = * = t V (k ) N cpi (1 − α)g (k ) + α f (k ) 2 2 D1 p   

S( p ,α ,β, k )

Man skaliert also jeweils in der Problemgröße und der Zeit, hat jetzt allerdings vier Skalierungsfunktionen f1, 2(k), g1, 2(k). Die damit verbundenen Freiheiten werden jedoch durch die notwendige Reproduktion einiger Standardsituationen eingeschränkt. So haben wir mit α = 0, β = 0 nur die rein skalare Verarbeitung auf einem Prozessor (p = 1), d. h. es muss S(p = 1, α = 0, β = 0, k = 1) gelten und damit g1(k) = g2(k) für alle k = 1…p. Im streng parallelen Fall, α = β = 1, folgt für den Durchsatz D(p, k ) = D1

β f1 ( k ) f (k ) = p * D1 * 1 (α / p )f 2 ( k ) f 2 (k )

Da gelten muss D(p, k) = p* D1, bedeutet dies, dass f1(k) = f2(k) und von den ursprünglich vier Skalierungsfunktionen bleiben nur zwei, f(k) und g(k), übrig. Nun ist der skalare Anteil in praktisch allen Anwendungen unveränderbar und wir können g(k) ≈ 1 nähern. Damit reduziert sich der Durchsatz auf

D(p,k)=

(1-β)+βf(k) *D1 α (1-α)+ *f(k) p  

S(p, k)

und dieser geht mit f(k = 1) = 1 in DA(p) (Amdahl) über sowie für f(k = p) = p in DG(p) (Gustafson). Folgende Abb. 13.1 zeigt das Verhalten von S(p, k)

13.2 Verallgemeinerte Durchsatzskalierung

185

G(k = p) k = 50

k = 10

A(k = 1)

Abb. 13.1 Skalierung zwischen Amdahl und Gustafson

Mit der linearen Skalierungsfunktion f(k) = k, k = 1…p, kann auch die Effizienz ε (p, k) ε(p, k ) =

S(p, k ) (1 − β) + βf (k ) = p (1 − α )p + αf (k )

unter Reproduktion der Amdahl-/Gustafson-Situationen bestimmt werden. Den entsprechenden Verlauf zeigt Abb. 13.2.

186

13 Über die Gültigkeit von Gesetzen

G(k = 100) k = 50

k = 10

A(k = 1)

Abb. 13.2 Skalierungsverhalten der Effizienz

Obwohl die Ergebnisse recht zufriedenstellend sind, bleibt doch eine gewisse Unsicherheit bezüglich der richtigen Wahl von f(k) und natürlich auch von g(k) – außerdem wird der Einfluss der Kommunikation nicht berücksichtigt. Interessant ist dieser Ansatz trotzdem, da er mit seiner Skalierung über (f(k), k = 1..p) alle Konfigurationen zwischen Amdahl und Gustafson berücksichtigt und genau diese Konzeption in Verbindung mit einer Arbeit von E. Gelenbe [19] gesehen werden muss, die auf die p-Abhängigkeit des Speed-Up zielt und außerdem noch eine elegante Einbeziehung der Effizienz erlaubt. Letztere soll im Folgenden kurz vorgestellt werden.

13.3 Ein möglicher Ansatz über Prozessorkonfigurationen Sei tV(1) die Laufzeit eines Auftrags/einer Anwendung auf einem 1-ProzessorSystem (skalaren System). Haben wir p > 1 Prozessoren zur Verfügung, dann werden mit einer Wahrscheinlichkeit πk k Prozessoren aktiv sein (k = 1, …, p), die entsprechende Laufzeit ist tV(k) = tV(1)/k. Die Gesamtlaufzeit tV ergibt sich damit als gewichtete Summe über alle k = 1,…,p Prozessorkonfigurationen: p

tV =

∑ k =1

p

πk *

πk t V (1) = t V (1) k k k =1

∑

13.3 Ein möglicher Ansatz über Prozessorkonfigurationen

187

und somit folgt für den Speed-Up S=

t V (1) = tV

t V (1) p

t V (1)

πk

=

1 p

πk

∑k ∑k k =1

k =1

Man sieht sofort, dass das Verhalten entscheidend von
= k

p

πk

∑k k =1

abhängt, man kann diese Größe als eine „Schätzung“ für den Kehrwert des mittleren Parallelitätsgrads (Zahl der aktiven Prozessoren) auffassen. Ist z. B. gewährleistet, dass π1 = π2 = … = πp–1 = 0 und πp = 1, d. h. alle Prozessoren arbeiten parallel, so ist = 1/p und für den Speed-Up folgt S(ideal) = p, dies ist der optimale Fall. Da aber in allen Anwendungen immer ein Zeitanteil rein skalar (p = 1) laufen muss, wählen wir π1 = 1 – α, π2 = π3 = … = πp–1 = 0 und πp = α mit 0 ≤ α ≤ 1. Dies ergibt = 1 – α + α/p und reproduziert den üblichen Speed-Up à la Amdahl S( Amdahl) =

1 1 (für p >> 1) ≤ 1− α + α / p 1− α

Interessant wird es, wenn jede Prozessorkonfiguration k = 1…p die gleiche Wahrscheinlichkeit πk = π (k = 1…p) besitzt. Da gelten muss p

1=

∑ k =1

p

πk ~

∑ π = π * p = 1 ~ π = 1/ p k =1

folgt p

< 1 / k >= (1 / p)

Γ' (p + 1)

∑1/ k = p (γ + Γ(p + 1) ) ≥ ln p / p 1

k =1

wobei γ = 0, 57… die Euler’sche Konstante und Г(p) die in Kap. 9 beim M/M/p/0Modell eingeführten Г-Funktionen darstellen. Der entsprechende Speed-Up resultiert zu

188

13 Über die Gültigkeit von Gesetzen

S(1/ p ) =

p p ≤ Γ' (p + 1) ln p γ+ Γ(p + 1)

und zeigt damit zwar ein quasilineares Verhalten, welches aber deutlich unter S(ideal) = p liegt (s. Abb. 13.3).

p

p ln p

Abb. 13.3 Speed-Up im realen und idealen Fall

Für kleinere Werte von α liegt S(Amdahl) immer unter S(1/p), erst für α = 3/5 und kleinere Prozessorzahlen weist die Amdahl-Konfiguration geringfügig bessere Werte auf, für große bis sehr große p ist sie mit ihrem niedrigen und konstanten Verhalten erheblich ungünstiger.

13.4 Die Effizienz von p Prozessoren Den obigen Ansatz wollen wir jetzt ausnutzen, um die bereits erwähnte Effizienz bei Systemen von p Prozessoren zu analysieren. Dazu gehen wir zunächst auf den Ausgangspunkt von Kap. 2 zurück und betrachten eine Last aus n Maschineninstruktionen, welche auf p Prozessoren mit jeweils dem Takt takt und einem entsprechenden cpi-Wert ablaufen. Anstelle der Verweilzeit tV tritt wieder die Bearbeitungszeit tB, Einflüsse des Betriebssystems werden vernachlässigt.

13.4 Die Effizienz von p Prozessoren

189

Der Durchsatz D(1) auf einem Prozessor ergibt sich zu n/tB(1), wobei tB(1) = zcpu = n*cpi*takt–1, also: D(1) =

n n * cpi * takt −1

1 1 = D theor (1) * cpi cpi

= takt *

mit Dtheor(1) = takt. Die Effizienz folgt damit zu ε = D(1)/Dtheor(1) = 1/cpi; ein Wert, der nur für superskalare Prozessoren (cpi < 1) über 1 liegt. Im Fall p > 1 sei πk(k = 1…p) die Wahrscheinlichkeit, dass k Prozessoren parallel aktiv sind, dann ist t B (k ) = n k * cpi * takt −1 = n *

nk * cpi * takt −1 n

die Zeit, welche jeder der k Prozessoren für nk Instruktionen benötigt, und daher folgt für die Gesamtzeit p

tB =

∑

πk * t B (k ) = n * p * cpi * p −1 * takt −1

k =1

p

∑π k =1

k

nk n

Der Durchsatz D(p) = n/tB berechnet sich damit zu 1

D(p) = p * takt * cpi −1 *

p

p

∑π

k

nk n

*

k =1

und da Dtheor(p) = p*takt folgt für die Effizienz ε = D(p) / D theor (p) =

1 * cpi

1 p

p*

∑π k =1

k

nk n

Für die weitere Diskussion muss nur die Summe im Nenner analysiert werden; zur besseren Transparenz wählen wir wie vorhin drei Fälle mit konkreten πk’s aus. Im Ideal-Fall läuft alles (n Instruktionen) auf p Prozessoren, d. h. π1 = π2 = … = πp–1 = 0 und πp = 1. Damit ist die Summe leicht auszuwerten p

p*

∑π k =1

k

*

nk ( n / p) = p *1 * =1 n n

190

13 Über die Gültigkeit von Gesetzen

und ε = Dideal(p)/Dtheor(p) =cpi–1 unabhängig von p. Eine bessere Skalierung bekommt man nicht. Im Real-Fall sind alle Prozessorkonfigurationen gleich wahrscheinlich, d. h. π1 = π2 = … = πp = 1/p. Da nk = n/k folgt p

p

∑

p

πk *

k =1

∑

nk 1 (n / k ) =p * = n p n k =1

p

Γ' (p + 1)

∑ k = γ + Γ(p + 1) ≥ ln p 1

k =1

Für ε = Dreal(p)/Dtheor(p) folgt somit ⎛

1 ⎞⎟ ε = cpi ⎜ ⎟ ⎝ k =1 k ⎠ −1 ⎜

p

∑

−1

≤

1 1 * cpi ln p

d. h. wir bekommen einen schwachen monotonen Abfall mit wachsendem p, der allerdings für große p kaum noch sichtbar ist. Im Amdahl-Fall kann ein Teil der Instruktion auf p Prozessoren ablaufen und der Rest nur auf einem Prozessor (skalarer Teil). Für die Wahrscheinlichkeiten bedeutet dies πp = α, πp–1 = πp–2 = … = π2 = 0 und π1 = 1 – α und damit für die Summe p

p

∑π k =1

k

⎛ nk α⎞ = p⎜⎜ (1 − α) *1 + ⎟⎟ = (1 − α)p + α n p⎠ ⎝

Die Effizienz berechnet sich also zu ε = D Amdahl (p) / D theor (p) =

1 1 * cpi p(1 − α) + α

und zeigt damit eine starke p-Abhängigkeit. Diese kann allerdings vermieden werden, wenn beim Übergang p → p’ > p der Nenner skaliert wird p(1 – α) + α → p’(1 – α’) + α’ α' = 1 − (1 − α)

p p −1 bei großem p, p’. ~ 1 − (1 − α) p' p'−1

13.5 Über eine mögliche Einbeziehung der Kommunikation

191

Dies entspricht genau der Problemskalierung bei Gustafson. Abbildung 13.4 stellt noch einmal das Verhalten von ε in einigen Fällen zusammen:

Amdahl α = 0.99

1 ln p

Amdahl α = 0.90

Abb. 13.4 Effizienz für die Standardfälle

13.5 Über eine mögliche Einbeziehung der Kommunikation Zum Abschluss wollen wir die noch fehlende Kommunikation zwischen k = 1…p Prozessoren in unsere bisherige Betrachtung mit einbeziehen, die Bearbeitungszeit modifiziert sich zu ⎛ t C (k ) ⎞ ⎟ t B (k ) = n k * cpi * takt −1 + t c (k ) = cpi * takt −1 ⎜⎜ n k + cpi * takt −1 ⎟⎠ ⎝

wobei tC(k) die Kommunikationszeit von k Prozessoren. Wir definieren t(1) = cpi* takt–1 als die mittlere Ausführungszeit für eine Basisinstruktion und t (C2) als die typische Zeit, welche für die Kommunikation zwischen zwei Prozessoren benötigt wird. Für tC(k) machen wir den nahe liegende Ansatz t C (k ) = t (C2) * c(k ) , wobei c(k) eine Funktion ist, die nur noch von der Kommunikationstopologie und der dimensionslosen Prozessorzahl k abhängt, sinnvollerweise ist c(1) = 0. Damit folgt

192

13 Über die Gültigkeit von Gesetzen

t (C2) t (C2) t C (k ) = = = * c ( k ) r * c ( k ); r cpi * takt −1 t (1) t (1)

und p

tB =

∑

πk t B (k ) = n * cpi * takt −1

k =1

p

∑π k =1

k

n k + r * c( k ) n

Da nk = n/k und nk/n = 1/k reduziert sich tB zu t B = n * cpi * takt −1

p

⎛ πk

∑ ⎜⎝ k

+

k =1

r ⎞ c( k ) ⎟ n ⎠

Der Durchsatz DC(p) = n/tB ergibt sich damit zu 1

DC (p) = p * takt * cpi −1

p

p

πk

∑ ⎛⎜⎝ k

+

k =1

r ⎞ c( k ) ⎟ n ⎠

sodass für die Effizienz folgt: εC =

1 * cpi

1 p

p

r πk +p k n k =1

∑

p

∑ π c( k ) k

k =1

und man sieht sofort, dass die Kommunikation diesen Leistungsparameter verkleinern muss. Wie vorhin diskutieren wir wieder drei Spezialfälle. Im idealen Fall π1 = … = πp–1 = 0, πp = 1, d. h. alles läuft parallel auf p Prozessoren, reduzieren sich die Summen im obigen Nenner 1 r p p * + p * 1 * c( p ) = 1 + r c( p ) p n n

sodass εideal = C

1 1 * p cpi 1 + r c(p) n

13.5 Über eine mögliche Einbeziehung der Kommunikation

193

Dies bedeutet aber, wie eigentlich vorauszusehen, dass die Effizienz ε durch den Kommunikationsanteil eventuell stark verkleinert wird. Im realen Fall, bei dem alle k = 1…p Prozessorkonfigurationen gleich wahrscheinlich sind, π1 = … = πp = 1/p, ergibt die erste Summe γ + Γ' (p + 1) / Γ(p + 1) , was wir schon kennen, und bei der zweiten Summe kürzt sich das p heraus, also εCreal =

1 cpi

1 γ+

Γ' (p + 1) r + Γ(p + 1) n

p

∑ c( k ) k =1

Zur weiteren Auswertung müssten wir die c(k) explizit hinschreiben und aufsummieren, im Rahmen einer rein qualitativen Betrachtung genügt die Abschätzung γ+

Γ' (p + 1) r + Γ(p + 1) n

p

∑ c(k) ≥ ln p + n c(p) r

k =1

welche für die Effizienz den folgenden Ausdruck ε Creal ≤

1 1 * cpi ln p + r c(p) n

ergibt. Ein interessantes Resultat, denn mit r ~ 1 – 10 und n ≥ 106 zeigt sich dieser Leistungsparameter praktisch unabhängig von p (jedenfalls für die Fälle c(p) ~ const, p, p*ln(p); c(p) ~ p² wird jedoch für n ≥ 1012 ebenfalls konstant). Dies widerspiegelt die Beobachtung, dass z. B. bei Lastmessungen mit Linpack die Effizienz (für sehr große p) sich aus praktisch zwei konstanten Faktoren zusammensetzt. Von Relevanz ist auch, dass mit einer Skalierung von n über mehrere Größenordnungen die Kommunikationsanteile kaum noch Bedeutung zeigen – eine ähnliche Situation wie beim Skalengesetz von Gustafson. Bei der ganzen obigen Diskussion ist zu beachten, dass n die Anzahl der Instruktionen und nicht die Problemgröße nP ist – es gilt n = f(nP), wobei die explizite Form von f(nP) von der Anwendung abhängt. Bei Linpack – dem Lösen linearer Gleichungssysteme – gilt n ~ n 3P , d. h. n = 106 entspricht nP = 100 und n = 109 dem Wert nP = 1000. Ein in der Praxis nicht unübliches nP = 106 führt zu n = 1018, mit r = 10 und c(p) = p², p ~ 105 reduziert sich der Beitrag der Kommunikation auf die Größenordnung (r/n)p² ~ (10/1018)*1010 = 10–7 und wäre demnach vernachlässigbar.

Literaturverzeichnis

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18]

[19]

L. Kleinrock, Queuing Systems Vol 1: Theory, Queuing Systems Vol 2: Computer Applications; Wiley-Interscience, 1975 and 1976 R. Jain, The Art of Computer Systems Performance Analysis; Wiley New York, 1991 M. Haas & W. Zorn, Methodische Leistungsanalyse von Rechensystemen, R. Oldenbourg, München, Wien, 1995 Tran-Gia, Analytische Leistungsbewertung Verteilter Systeme; Springer-Verlag Heidelberg, 1996 G. Bolch, Leistungsbewertung von Rechensystemen; B.G. Teubner-Verlag Stuttgart, 1989 J. L. Hennessy & D. A. Patterson, Computer Architecture Third Edition; Morgan Kaufmann (Elsevier), 2003 W. Schönauer, Scientific Computing on Vector Computers; North Holland Amsterdam, 1987 R. Mathar & D. Pfeifer, Stochastik für Informatiker; B.G. Teubner-Verlag Stuttgart, 1990 E. Dotzauer, Grundlagen der Digitalen Simulation; Hanser-Verlag München, 1987 F. Beichelt, Stochastische Prozesse für Ingenieure; B.G. Teubner-Verlag Stuttgart, 1996 Maple, University of Ontario(Canada) & ETH Zürich(CH) Mathematica, Stephen Wolfram Research Inc. L. L. Peterson & B. S. Davie, Computer-Netze; dpunkt.verlag Heidelberg, 2004 K. Hwang, Advanced Computer Architecture; McGraw-Hill New York, 1993 Xingfu Wu & Weili, Performance models for scalable cluster computing: Jour. of Systems Architecture 44 (1998) 189–205 und die dort zitierte Literatur H. H. Wacker, Das skalierte Gesetz von Amdahl, in Praxis der Informationsverarbeitung und Kommunikation Yuan Shi, Reevaluating Amdahl’s and Gustafson’s Law F. A. van Catledge, Toward a general model for evaluating the relative performance of computer systems – Intern. Jour. of Supercomp. Appl. Vol 3, No 2, p 100–108, 1989 E. Gelenbe, Multiprocessor Performance; Wiley New York, 1989

Index

#

B

#last 5

Basislösungen 97 Bearbeitungszeit 75 Bedienprozess 171 Bedienzeit 176 Befehlsverarbeitung 24 Belegungsdauer 108 Benchmark-Beispiel 39 Bernoulli-Modell 161 Bessel-Funktionen Ik(tZ) 76 Besuchshäufigkeit 56, 59, 61, 131, 133, 135, 141 Besuchshäufigkeiten 57 Binomialkoeffizienten 124 Black-Box-Modell 27, 73 Blockade- oder Abwehrwahrscheinlichkeit 109 Blockadewahrscheinlichkeit 106 Blockier-/Abwehrwahrscheinlichkeit 109 Blockierungswahrscheinlichkeit 105 bottleneck 55 busy 53 bzeit 6

A Abarbeitungsrate μ 94 abgeschlossen 139 Ablaufzeit 2, 48 Ablaufzeit zcpu 5, 15, 41 absorbierender Zustand 84 Addition 42 Aktiv/Busy-Zeit 135 Aktivzeit tA 165 ALOHA 153, 156 ALOHA (Durchsatz) 157 ALOHA-Protokoll 173 Amdahl 15, 181 Amdahl’sche Gesetz 16 Ankunftsrate 28, 93 Antwortzeit 71, 146 Antwortzeit-Gesetz 64, 66, 68 Anzahl von Aufträgen 78 Approximation 146 arithmetische Mittel 46 Aufträge 64 Auftragsverarbeitung 28 Ausfallrate 85 Auslastung 33, 54, 133 Auslastung ρ 165 Auslastungsgesetz 55 Auslastungsgesetzes 53

C Central-Server 135 Central-Server-Modell 62 Central-Server-System 61 Chapman-Kolmogoroff 96 Chapman-Kolmogoroff-Gleichungen 87, 94, 99 Client 67, 123 Client/Server-Modell 128

198

Index

Clienten 61 Client-Server-Modell 133, 134 Cluster-Prinzip 14 cpi 6-8, 41, 188 Cray-1 21 Cyber205 21 D Daten- oder Vektor-Pipeline-Prinzip 18 Datenbank-Server 120 Datenbanksystem 84 Datenpaket 79, 112 DB-Server 96 Denkzeit 68 Dhrystone 38, 45 Diagramm 123 Dialogsysteme 67 Dichtefunktion 48 Differenzialgleichung 76 Differenzialgleichung erster Ordnung 88 Differenzialgleichungssystem 76, 93, 94 Dirac- oder Impulsfunktion 174 Division 42 Dual-Prozessor 122 Durchsatz 2, 10, 27, 35, 105, 112, 141, 157 Durchsatz D 54, 67, 109, 135, 165 Durchsatzskalierung 184 Durchsatzsteigerung 70, 143 Dynamik 87 dynamische Situation 100 E effektive Ankunftsrate 110 effektive Durchsatz 162 Effizienz 183, 185, 186, 189, 190, 192, 193 Eigenvektor 61 Eigenwert 61 ein Mail-System 132 Einwahlmodem 108 Einwahlversuch 108 eLearning-Server 167 Endliche Modelle 86 Engpass 135, 139 Engpass-Analyse 56, 59, 131, 143 Erwartungswertes 75

Euler’sche Konstante 187 Exponentialverteilung 120, 166, 169 F File-Server 123, 127 File-Server-Modell 127 Flaschenhals 55, 134 Flaschenhals-Analyse 55 Flussgleichung 137 Fluss-Kontrolle 112, 118 Forderung (req) 67 Freiheitsgrad 52 G G/G/1/∞ 177 G/M/1/∞ 170, 173 Gedächtnislosigkeit 74 General Response Law 66 Generierung der Datenpakete 155 geometrische Verteilung 172 geometrischen Mittels 46 Gesamtdurchsatz 106 Gesamtdurchsatz D 134 Gesamtlösung 97 geschlossene Lösung 147 geschlossenes System 132 Gesetz von Amdahl 15 Gesetz von Gustafson 22 Gewicht der Befehlsgruppe 26 Gibson-Mix 38 Gleichgewicht 31, 32, 55, 59, 140 Gleichgewichtspunkt 163 Gleitkommainstruktionen 44 globale Gültigkeit 67 Größenskalierung 181 Grundgesamtheit/Population 49 Grundlast 41 Gruppen von Instruktionen 6 GSM 150 Gustafson 181, 183, 191 H heavy traffic approximation 177 heiße Reserve 100 Histogrammbeispiel 29 Hochleistungssysteme 111 Hyperbolischen Funktionen 99

Index

I IBM-Roadrunner-System 13 Idealfall einer Skalierung 23 Idle-Wahrscheinlichkeit 151 Integer-Division 43 K kalte Reserve 96 Kanal 149, 153, 154, 159 Kanalbelastung 154 Kanaldurchsatz 160, 163 Kapazität C 149, 150 Kennzahlen 134 Kernels 38 Kollision 154, 156, 162 Kollisionsfreiheit 154, 156, 158 Kommunikation 191 Kommunikationskanal 149 Kommunikationspartner 149 Kommunikationsprotokoll 149 Kommunikationssysteme 149 Kommunikationstopologie 191 Kommunikationszeit 191 Kommunikationszeit pro task 150 Komposition 116 Konfidenzintervall 49 Korrekturfaktor 176 Korrekturterm 99, 117 L Last 2, 112 Last zustandsabhängig 113 Lastdefinition 3 Lastmenge 27 Lastmessung 3 Lastverminderung 121 Laufzeit 2 Lebensdauer 101 Leerschleife 41 Leerzyklen 25, 26 Leistung 1 Leistungsanalyse 2, 165 Leistungsanalyse und Modellierung 3 Leistungsfähigkeit eines Cache-Systems 17 Leistungsgesetze 53 Leistungsgröße 80 Leistungsmaß 5 Leistungsmessung 3 Leistungsunterschiede 118

Linpack 193 Linpack-Basis 38 Linpack-Benchmark 181 Little’sche Gesetz 34 Little’schen Gesetz 152 Little’schen Gesetze 34, 35, 64 lokale Gültigkeit 67 M M(λ)/M(μC)/1/∞-Modell 150 M/G/1/∞ 176 M/M/1/∞ 103, 106, 115 M/M/1/∞-Modell 120 M/M/2/∞ 122, 177 M/M/m/∞-Modell 120 M/M/p/0 107, 110 Mail-Server 135 Maple 114, 119, 161 Maple/Mathematica 125 Markoff 103 Markoff’sches Zustandsmodell 74 Markoff-Modelle 149 Markoff-Prozess 74 Mathematica 147, 161 Matrix der Übergangsraten 93 maximalen Durchsatzes 69 M-Clienten 123 M-Clienten-Modell 126 Messzeit tM 165 MFLOPs 10 MFLOPS 13 Min/Max-Problem 71 MIPS 10, 11 MIPS und Ablaufzeit 12 MIPSMIX – Rate 43 MIPS-Rate 41 Mittelwert 166 Mittelwertgleichung 169 Mittelwertvergleich 46 mittlere aktive Zeit 54 mittlere Antwortzeit 165 mittlere Antwortzeit N 141 mittlere Anzahl 114 mittlere Anzahl 154 mittlere Anzahl 131 mittlere Bearbeitungszeit 33 mittlere Überlebenszeit 98 mittlere Verweilzeit 112, 150 mittlere Verweilzeit 79, 139 mittlere Wartezeit 34 Mixe 38

199

200

Index

Modellgültigkeit 166 Modellierung 73, 87, 131, 155, 165 Modell-RISC-Maschine 7 Modellsystem 139 Multiplikation 42 N Näherungslösung 144 Normalverteilung 49 Normierung 105, 108, 111, 119, 124, 138 Normierungsbedingung 77 O obere Schranke 145 offenes Modell 138 offenes System 131 Operational Laws 53 P Paket 156 Paketübertragungszeit 157 Parallelbetrieb 182 Parallelitätsgrad 187 Parallelsystem 181 Peta-FLOP 13 Pfad 88, 92 Pipeline-Durchsatz 19 Pipeline-Takt 19 Poisson’sche Näherung 162 Poisson-Ankunftsverteilung 160 Poisson-Bedingung 172 Poisson-Prozess 155 Poisson-Verteilung 93 Primitiv-Kernel 43 Problemgröße n 182 Problemskalierung 191 Produkteigenschaft 138 Produktform 140, 141 Protokoll 153 Protokollvariante 156 Providernetz 108 Prozessorkonfiguration 187, 190, 193 Prozessorkonfigurationen 186 R Randwahrscheinlichkeiten 141 Rate 73 reflektierender Zustand 84

Regression 168 Regressionsgerade 168, 169 Rekursion 77, 142, 143, 146, 147 Rekursionsgleichung 76, 142 relative Skalierung 182, 183 repair-man 126 Reparaturrate 85 Router 106 S Sättigung 130 Sättigungspunkt 70, 71 Schweitzer 1971 144 Segmentierung 57 Server 61, 67 Server/Clienten-System 127 Server-M-Clienten-Modell 128 Service-/Bearbeitungszeit 104 Service-Demand-Zeit 56 Service-Zeit 54, 120, 136, 142 shared medium 150 skalare Datenanteil 22 Skalengesetz 152 Skalierung 104, 182 Skalierung der Verweilzeit tV 182 Skalierungsfunktion 185 Skalierungsfunktionen 184 Slot 153 Slotted ALOHA 158, 159, 161 SPEC-Benchmark 38 Speed-Up 10, 16, 17, 22, 104, 137, 176–179, 181, 182, 187 Speicherkonflikten 25 Stabilitätsbedingung 175 Standardabweichung 166 Standardansatz 76 Standardmodell 117 Standardsystem 115 Standardverfahren 119 Stationäre Zufallswahrscheinlichkeiten 95 Statistik 48 Stichprobe/Sample 49 Subeinheiten 73 Subkanal 151 Subkanäle 150 Submodell 116 Subsystem 55, 64, 131, 141, 143 Summation 171, 172 superskalare Prozessoren 189 Systemdynamik 74

Index

Systemengpässe 55 Systemzeit 131, 146 T Takt 5, 188 tasks 149, 151 TCP/IP 113 Teillast 61 Teilsystem 55, 57, 141, 181 TFLOPS 13 top500 14 t-Verteilung 51 U Übergang 88, 90, 91 Übergänge 87 Übergangsmatrix 87, 171 Übergangsmatrixelement 171 Übergangswahrscheinlichkeit 57, 58, 61, 64, 87, 133 Übergangswahrscheinlichkeiten 57, 65 Überlastbereich 115 Überlebenswahrscheinlichkeit 98 V Variation der Konstanten 95 Vektor der externen Zuflussraten 65 Vektor der internen Zuflussraten 65 Vektorpipeline 21 Verarbeitungsrate 28 Verarbeitungsüberlappung 139 Vergleich von Benchmarks 45 Verlust-Modell 107 Verlustsystem M/M/1/B 104 Verteilung der stochastischen Variablen 28 Verteilungsdichte 75 Verteilungsfunktion 48, 75

201

Verteilungshistogramm 30 Vertrauenswürdigkeit (Konfidenz) 48 Verweildauer 136 Verweilzeit 28, 32, 116, 122 Verweilzeit 103, 176 Verweilzeit N 145 visit ratio 56 W Wahrscheinlichkeitsdichte 166, 173 Wartepool 73 Wartewahrscheinlichkeit 105, 120, 126, 175 Wartezeit 81, 122 Wartezeit 129, 151 Wartezeitverhalten 82 Whetstone 38, 45 W-LAN 150 Z Zeit-Dynamik 75 Zeitunabhängige Lösung 77 Zeitverkürzung 22 Zerlegung 131 Zufluss 64 Zustandsdiagramm 104, 108, 113, 118, 129 Zustandsgraph 84 Zustandswahrscheinlichkeit 74 Zustandswahrscheinlichkeiten 92, 104, 109 Zustandswahrscheinlichkeiten πk 78 Zwischenankunftszeit 167 Γ Γ-Funktion 108, 125 Г-Funktionen 187