Benutzer:Freaky86/testseite

Leistungsbewertung

Die Leistungsbewertung versucht objektive Aussagen über ein oder mehrere Rechensysteme durch messbare Größen zu treffen. Die Leistung wird immer für eine bestimmte Rechnerkonfiguration unter bestimmten Nebenbedingungen unter Anwendung bestimmter Software vorgenommen. Viele Einflüsse ergeben einen breiten Parameterraum, bei der Bestimmung der Leistung eines Rechensystems. Solche Faktoren sind zum Beispiel:

• die verwendeten Algorithmen
• die Umsetzung der Algorithmen in bestimmter Software
• die Hardwarekonfiguration
• das verwendete Betriebssystem
• das Netzwerk
• die Kommunikation

Die Leistungsbewertung von Computersystemen erfolgt anhand verschiedener Kriterien. Dazu zählen:

• Kosten
• Leistungsverbrauch
• Ausführungszeit von Programmen
• Reaktionszeit auf Unterbrechungen
• Verfügbarkeit von Software und Compilern

Ziele und Einsatzgebiete

Planning Phase

Beim Entwurf neuer Hard- und Softwarestrukturen muss überprüft werden, ob einzelne Komponenten den Anforderungen gerecht werden und sich leistungsgerecht in das Gesamtsystem eingliedern. So lassen sich Flaschenhälse auffinden und vermeiden.

Design and Implementation Phase

Bei der Implementierung von Komponenten muss geprüft werden, ob der Entwurf korrekt umgesetzt wurde und ob die Komponente die geforderte Leistung wirklich erbringt.

Configuration Process

Bei der Zusammenstellung einer komplexen Rechenanlage ist es erforderlich, einzelne Teilkomponenten verschiedener Hersteller zu vergleichen und objektiv zu bewerten, um die optimale Konfiguration zu finden.

System Tuning

Ändern sich die Anforderungen an ein System, so kann es plötzlich vorkommen, dass sich einzelne Komponenten als Flaschenhals erweisen. Ungezieltes Aufrüsten ist teuer und ineffizient. Mit der Leistungsbewertung können Engpässe aufgedeckt und beseitigt werden.

Kenngrößen und Leistungskriterien

Durchsatz

Verarbeitungsvolumen pro Zeiteinheit

Programm-Ausführungszeit

Zeit zwischen Start und Ende eines Programms

CPU-Ausführungszeit

Die CPU-Ausführungszeit berechnet sich wie folgt.

CPU-Ausführungszeit = CPU-Taktzyklen × Taktzykluszeit

Außerdem gilt:

Taktzykluszeit = 1 / Taktrate = Programmbefehle × CPI × Taktzykluszeit

CPI (Cycles per Instruction)

Mittlere Zahl der Takte pro Instruktion. Anzahl der Taktzyklen dividiert durch die die Anzahl der ausgeführten Anweisungen die bei der Ausführung des Programms benötigt werden.

CPI = Taktzyklen / Anweisungen

Ein niedriger CPI-Wert steht für hohe Effizienz der CPU, der CPI Wert alleine sagt jedoch nichts über die tatsächliche Geschwindigkeit (Effektivität) aus.

IPC (Instructions per Cycle)

Anzahl der ausgeführten Anweisungen dividiert durch die Anzahl der Taktzyklen, die für die Ausführung des Programms benötigt werden. IPC kann auch als Kehrwert von CPI ausgedrückt werden.

IPC = Anzahl Anweisungen / Taktzyklen

Ein hoher IPC-Wert steht für eine hohe Effizienz der Architektur.

Das Maß MIPS dagegen ist eine Maßeinheit um die Prozessorleistung anzugeben. Ein richtige Bewertung erlaubt jedoch nur die gemeinsame Betrachtung von MIPS und CPI.

Außerdem finden sich oft Angaben der verarbeiteten Fließkommaoperationen pro Sekunde, den FLOPS.

Performance

Performance = 1 / Execution Time

Das Problem bei solchen Maßzahlen ist, dass damit zwar Zahlen rauskommen, die der Käufer vergleichen kann, die aber letztlich in vielen Fällen nur wenig Aussagen machen über die tatsächliche Leistungsfähigkeit des Systems.

Ein weiterer Versuch, die Leistung von Computern zu vergleichen, sind Mixes und Kernprogramme. Diese Versuche sind allerdings relativ aufwändig.

Mixes

Bei Mixen wird versucht, eine mittlere Operationszeit T zu bestimmen. Dazu werden die unterschiedlichen Befehlstypen nach der erwarteten relativen Häufigkeit ihres Auftretens bewertet und summiert.

Kernprogramme

Kernprogramme sind typische Anwenderprogramme, die für den zu bewertenden Rechner geschrieben werden. Sie werden jedoch nicht zur Ausführung gebracht, Ziel ist es, die Ausführungszeit auf Grundlage der einzelnen Befehlsausführungszeiten zu bestimmen.

Beobachtende Leistungsbewertung

Die beobachtende Leistungsbewertung wird auch als Monitoring bezeichnet. Je nach Art wird zwischen Software-Monitoring und Hardware-Monitoring unterschieden. Die Beobachtung kann ereignisgesteuert, zeitgesteuert oder zufällig gestartet werden.

Hardware-Monitoring

Hier werden Messfühler direkt an das Messobjekt angebracht, welche die entsprechenden Daten an einen Monitor übertragen. Diese Art der Messung beeinträchtigt den Ablauf des Objektrechners nicht.

Software-Monitoring

Ein Messprogramm wird auf dem Objektrechner installiert, welches die gewünschten Informationen über eine Standardschnittstelle an einen Monitor überträgt. Da die Messprogramme unabhängig von der Hardware arbeiten, sind nur minimale Kenntnisse des Objektrechners nötig und die Messprogramme sind auf nahezu allen Rechnern lauffähig. Jedoch wird der Programmablauf auf dem Objektrechner verändert und es werden zusätzliche Ressourcen verbraucht. Das dynamische Verhalten des Objektrechners wird verfälscht.

Probleme beim Monitoring

• VLSI erschwert das Hardware-Monitoring durch zunehmende Integration von Komponenten
• durch virtuelle Speicherkonzepte sind bestimmte Speicherbereiche zu den Prozessoren nicht mehr zuzuordnen
• RISC-Prozessoren ändern ggf. die Reihenfolge der Befehlsausführung Forwarding
• zunehmende Taktraten bewirken übermäßige Flut von Messdaten

Benchmarks

Benchmarks sind Sammlungen von Programmen oder Programmkernen, die ein bestimmtes Anwenderprofil repräsentieren oder künstlich zusammengestellt werden. Die bekanntesten Benchmarks sind:

• Linpack
• Whetstone
• Dhrystone
• Standard Performance Evaluation Corporation (SPEC)

Dabei sollte man beachten, dass auch hier ein Spielraum für Manipulation vorhanden ist. In der Praxis werden oft Compiler oder auch Befehlssätze derart optimiert, dass gängige Benchmarks besonders schnell ablaufen.

Berechnende Leisungsbewertung

Das allgemeine Warteschlangenmodell.

Warteschlangenmodell für Pipeline-Prozessoren.

Warteschlangenmodell für Multiprozessorsysteme.

Anders als bei den vorher genannten Methoden muss bei der berechnenden Leistungsbewertung kein reales System vorhanden sein.

Graphentheoretische Beschreibung

Besonders in der Kommunikationstechnik bietet es sich an, das System als Graph zu modelieren. Die Komponenten werden als Knoten dargestellt. Verbindungen zwischen den Komponenten werden als Kanten repräsentiert. Jede Kante hat eine Maximalkapazität, welche nicht überschritten werden darf und einen aktuellen Fluss. Das entstandene Netzwerk lässt sich nun bewerten, indem der größtmögliche Fluss zwischen zwei Komponenten bestimmt wird. Wird das paarweise für alle Knoten durchgeführt, so lassen sich langsame Komponenten ausfindig machen.

Verkehrstheoretisches Modell

Eine verkehrstheoretische Beschreibung geht von einer Warteschlange mit Aufträgen aus, welche von einer Bedienstation abgearbeitet wird. Die Aufträge erreichen die Warteschlange mit einer mittlere Ankunftsrate $\lambda$ und verlassen die Bedienstation mit einer mittleren Bedienrate $\mu$. Die Verkehrsintesität wird durch den Quotienten $\sigma ={\frac {\lambda }{\mu }}$ beschrieben. Das System arbeitet nur vernünftig, solange $\sigma \leqq 1$ ist. Andernfalls kommt es zum Überlauf.

Mit diesem Modell lassen sich verschiedene Systeme darstellen. Ein Rechner ohne Pipelining mit nur einem Prozessor bekommt als Verteilungsfunktion eine negative Exponentialverteilung. Pipeline-Prozessoren mit $k$ Stufen werden mit der Erlang-Verteilung modelliert. Für Multiprozessorsysteme nutzt man eine Hyperexponentialverteilung $k$ter Ordnung

Ein verkehrstheoretisches System wird mit Hilfe der Kendall-Notation beschrieben. Typische Modelle sind M/M/1/1 und M/M/1

Leistungsdatenbanken

Fachzeitschriften und -magazine veröffentlichen regelmäßig Rankings zur Leistungsfähigkeit von Rechnersystemen oder -komponenten. Diese werden durch Kennzahlen oder Benchmarks bestimmt. Im Internet werden u.A. die 500 leistungsfähigsten Rechner aufgelistet.

Literatur

• John L. Hennessy, David A. Patterson: Rechnerarchitektur: Analyse, Entwurf, Implementierung, Bewertung. Vieweg, Braunschweig 1994, ISBN 3-528-05173-6
• Andrew S. Tanenbaum, James Goodman: Computerarchitektur. 4. Auflage, Pearson Studium, München 2001, ISBN 3-8273-7016-7

Schnelle Fourier-Transformation

Implementierung (Pseudocode)

Die Implementierung erfolgt durch einen rekursiven Algorithmus. Das Feld wird als Parameter übergeben und solange in zwei Felder mit geradem bzw. ungeradem Index aufgeteilt, bis es nur noch aus einem Element besteht (Rekursionsabbruch). In jedem Rekursionsdurchlauf wird eine Schleife bis zur halben Länge des Feldes durchlaufen, da mit jedem Schleifendurchlauf gleich zwei Feldelemente berechnet werden können (siehe Komplexität).

$\mathrm {function} \ \operatorname {fft} (n,{\vec {f}}):$

$\mathrm {if} \ (n=1)$

$\mathrm {return} \ {\vec {f}}$

$\mathrm {else} \$

${\vec {g}}=\operatorname {fft} \left({\frac {n}{2}},f_{0},f_{2},\ldots ,f_{n-2}\right)$

${\vec {u}}=\operatorname {fft} \left({\frac {n}{2}},f_{1},f_{3},\ldots ,f_{n-1}\right)$

$\mathrm {for} \ k=0\ \mathrm {to} \ {\frac {n}{2}}-1$

${\begin{aligned}c_{k}=g_{k}+u_{k}\cdot e^{-2\pi ik/n}\\c_{k+n/2}=g_{k}-u_{k}\cdot e^{-2\pi ik/n}\end{aligned}}$

$\mathrm {return} \ {\vec {c}}$

Automaten

Bekannte Typen von Automaten sind (jeweils mit Abkürzungen in deterministischer und nichtdeterministischer Variante):

• Turingmaschinen (DTM/NTM): akzeptieren die Typ-0-Sprachen (Rekursiv aufzählbare Sprache) und damit auch Typ-1-Sprachen. Durch die Turingmaschine wird außerdem der Begriff der Berechenbarkeit definiert. Siehe Churchsche These.
• linear beschränkte Automaten (DLBA/LBA): akzeptieren die Typ-1-Sprachen (kontextsensitive Sprachen)
• Kellerautomaten (DPDA/PDA): akzeptieren die Typ-2-Sprachen (Kontextfreie Sprachen)
• Endliche Automaten (DFA/NFA): akzeptieren die Typ-3-Sprachen (Reguläre Sprachen)
• Zweikellerautomat: ohne Einschränkung der Turingmaschine gleichwertig. Syntaktische Beschränkungen dieses Modells führen zur Charakterisierung der Typ-1- und Typ-2-Sprachen.
• Registermaschinen: sind genau so mächtig wie Turingmaschinen, bieten aber in einigen Fällen ein besseres Maß für die Zeitkomplexität.

Die Menge der Automaten stehen wie folgt mit den Mengen der Sprachklassen und Grammatiken in Beziehung:

Chomsky-Hierarchie	Sprachklasse		nicht deterministischer Automat		deterministischer Automat
Typ-0-Grammatik	${\color {blue}{\mathcal {RE}}}$	$=$	${\color {blue}{\mathcal {NTM}}}$	$=$	${\color {blue}{\mathcal {DTM}}}$
Typ-1-Grammatik	${\color {blue}{\mathcal {CS}}}$	$=$	${\color {blue}{\mathcal {LBA}}}$	$\supseteq$	${\mathcal {DLBA}}$
Typ-2-Grammatik	${\color {blue}{\mathcal {CF}}}$	$=$	${\color {blue}{\mathcal {PDA}}}$	$\varsupsetneq$	${\mathcal {DPDA}}$
Typ-3-Grammatik	${\color {blue}{\mathcal {REG}}}$	$=$	${\color {blue}{\mathcal {NFA}}}$	$=$	${\color {blue}{\mathcal {DFA}}}$

Die Mengeninklusion LBA ⊇ DLBA ist nur eine Vermutung, da bisher noch nicht bewiesen wurde, ob die DLBAs die gleiche Sprachklasse akzeptieren wie die LBAs. Die Gleichheit NTM = DTM steht im engen Zusammenhang mit dem P-NP-Problem (P≟NP).

Pipelining

Taktung

Der Takt wird durch die Zykluszeit der Pipeline bestimmt und berechnet sich aus der Summe der maximalen Stufenverzögerung $\tau _{m}$ aus allen Stufenverzögerungen $\tau _{i}$ und einem Zusatzaufwand $d$, welcher durch die Zwischenspeicherung der Ergebnisse in Pipeline-Registern verursacht wird.

Zykluszeit: $\tau ={\underset {i}{\max }}(\tau _{i})+d=\tau _{m}+d$

Leistungssteigerung

Durch das Pipelining wird der Gesamtdurchsatz gegenüber Befehlsabarbeitung ohne Pipelining erhöht. Die Gesamtzeit für die Pipeline-Verarbeitung mit $k$ Stufen und $n$ Befehlen bei einer Zykluszeit $\tau$ ergibt sich aus:

Gesamtzeit: $T_{k}=(k+n-1)\cdot \tau$

Anfangs ist die Pipeline leer und wird in $k\cdot \tau$ Schritten gefüllt. Nach jeder Stufe wird ein neuer Befehl in die Pipeline geladen und ein anderer Befehl wird fertig gestellt. Die restlichen Befehle werden daher in $(n-1)\cdot \tau$ Schritten fertig gestellt.

Bildet man nun den Quotienten aus der Gesamtzeit für Befehlsabarbeitung mit und ohne Pipelining, so erhält man den Speed-Up. Dieser repräsentiert den Leistungsgewinn, der durch das Pipelining Verfahren erreicht wird:

Speed-Up: $S_{k}={\frac {T_{1}}{T_{k}}}={\frac {n\cdot k\cdot \tau }{(k+n-1)\tau }}={\frac {n\cdot k}{k+n-1}}$

Geht man davon aus, dass immer genügend Befehle vorhanden sind, welche die Pipeline füllen, so ergibt sich der Grenzwert des Speed-Ups für n gegen unendlich:

$\lim _{n\to \infty }S_{k}={\frac {n\cdot k}{k+n-1}}=k$

Das bedeutet, dass mit zunehmender Stufenanzahl $k$ die Leistung beliebig gesteigert werden kann. Jedoch lässt sich die Befehlsabarbeitung nicht in beliebig viele Stufen unterteilen. Eine Steigerung der Stufenanzahl hat ebenfalls schwerere Auswirkungen beim Auftreten von Daten- oder Steuerungskonflikten zur Folge. Ebenfalls steigt der Aufwand der Hardware mit steigender Stufenanzahl $k$.

Datenhazards

Datenhazards werden in drei Typen eingeteilt: RAW, WAR, und WAW

Read After Write (RAW) Hazards:

Diese Konflikte werden durch Algorithmen verursacht. Eine Instruktion I2 liesst aus einem Register (Phase Instruction Decode), in das die vorher gestartete Instruktion I1 noch nicht geschrieben hat (Phase Write Back).

I1: R1 + R2 = R3
I2: R3 + R2 = R4

Write After Read (WAR) Hazards:

Eine Instruktion I3 überschreibt einen Wert, bevor die früher gestartete Instruktion I2 diesen gelesen hat. Das tritt immer dann auf, wenn Instruktion I2 auf das Ergebnis einer früheren Berechnung aus Instruktion I1 warten muss. WAR-Hazards treten daher nur nach einem RAW-Hazard auf.

I1: R1 * R2 = R3 (verursacht mit I1 einen RAW)
I2: R3 + R4 = R5 (wartet auf R3 aus I1)
I3: R6 + R7 = R4 (überschreibt R4, bevor I2 gelesen hat)

Write After Write (WAW) Hazards:

Eine langsamere Instruktion I1 überschreibt das Ergebnis einer später gestarteten, schnelleren Instruktion I2. Dieser Konflikt tritt daher nur in Superskalaren Recheneinheiten auf, bei denen mehrere Funktionseinheiten vorhanden sind. Eine schnellere Instruktion (z.B. Addition) überholt eine früher gestartete, langsamere Instruktion (z.B. Multiplikation)

I1: R1 * R2 = R3 
I2: R4 + R5 = R3 
I3: R6 + R4 = R7