Simulationsbasierte Zuverlässigkeitsanalyse

Transcript

F. Balbach (ed.), M. Dal Cin, A. Hein, J. Meixner, B. Rümenapp, V. Sieh, J. Stiborsky, O. Tschäche Simulationsbasierte Zuverlässigkeitsanalyse Internal Report No.: 6/96 1 Simulationsbasierte Zuverlässigkeitsanalyse Im Rahmen eines Hauptseminares wurde im Sommersemester 1996 eine zweitägige Blockveranstaltung vom 8.7.-9.7.1996 durchgeführt. Die Idee war dabei, diejenigen Mitarbeiter des Lehrstuhls, die im Rahmen von simulationsbasierter Zuverlässigkeitsanalyse arbeiten, zu einen intensiven Gedankenaustausch anzuregen. Daneben sollte interessierten Studenten die Möglichkeit geboten werden, neben einem vorbereitenden Vortrag eigene Ideen im Rahmen dieses Themas einzubringen. Um eine ungestörte Diskussion zu ermöglichen, wurde das Seminar im Schloß Atzelsberg bei Erlangen abgehalten. Die dadurch erzielte entspannte Atmosphäre trug wesentlich dazu bei, einen offenen Gedankenaustausch bezüglich der verschiedenen Ansätzen zur simulationsbasierten Zuverlässigkeitsanalyse zu ermöglichen. Ein wesentlicher Gedanke bei der Auswahl der Themen war die Gegenüberstellung verschiedener Abstraktionsebenen zur Ermittlung von Zuverlässigkeitsdaten der modellierten Systeme. Die vorgestellten Abstraktionsebenen erstreckten sich dabei von der Gatterebene über die Register-Transferebene bis hin zur Möglichkeit der Beschreibung und Bewertung massiv paralleler Systeme. Im Folgenden sind die Kopien der Folien zu finden, die während der Vorträge verwendet wurden. Im Falle der studentischen Vorträge wurde anstatt der Folien deren Ausarbeitung in diesen Bericht aufgenommen. Die Reihenfolge der hier aufgeführten Kopien entspricht dem zeitlichen Ablauf der Vorträge während des Seminars. 2 REACT Bernhard R
umenapp geLATEXt am 3. Juli 1996 Inhaltsverzeichnis 1 U berblick 2 Das System Model 2 2 3 Das Workload Model 4 4 Fault und Error Model 5 5 Der Ablauf einer Simulation 6 Literaturverzeichnis 8 9 2.1 Die Speichermodule . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Die Prozessormodule . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Die Fehlertoleranzmechanismen . . . . . . . . . . . . . . . . . . 3.1 Das Referenzlokalitatsmodell . . . . . . . . . . . . . . . . . . . . 4.1 Das Fehlermodell der Speicherdefekte . . . . . . . . . . . . . . . 4.2 Das Fehlermodell der Prozessoren . . . . . . . . . . . . . . . . . 4.3 Das Fehlermodell der Fehlertoleranzmechanismen . . . . . . . . . 1 3 3 3 4 5 6 8 1 U
berblick Das REliable Architecture Characterisation Tool ist ein Simulationswerkzeug. Es kann verschiedene fehlertolerante Multiprozessorsysteme analysieren. REACT arbeitet mit einem abstrakten Modell der konkreten Systemarchitektur. REACT fuhrt automatische Testablaufe aus, um die verla lichkeit des Systems akurat und e zient zu messen. REACT bezieht detaillierte System-, Workload- und Fault/ErrorSimulationsmodelle ein, welche zum Teil aus vero entlichten Ergebnissen von Leistungsmessungen und Lowlevel-Fehlerinjektionsexperimenten abgeleitet wurden. 2 Das System Model ' $' $ ' $ &' %$ & % '$ &% &% & % eignet sich fur Systeme, die analog dem abgebildeten Modell dargestellt werden konnen. REACT Prozessor Modul Bus Prozessor Modul Bus FehlertoleranzMechanismen und Verbindungssystem . . . Bus Speicher Modul Bus Speicher Modul . . . Eine Architektur dieser Klasse besteht aus einem oder mehreren Prozessormodulen, verbunden uber Busse durch einen Block von Fehlertoleranzmechanismen hin zu einem oder mehreren Speichermodulen. Die Prozessoren kom2 munizieren nicht direkt untereinander, sondern tauschen nur uber gemeinsame Speicher Daten aus. Die Anzahlen der Prozessor- oder Speichermodule, die von Beginn aktiv sind, und die der hot oder cold standby spare Module konnen beliebig gewahlt werden. Prozessoren oder Speicher werden aufgeteilt in Gruppen. Innerhalb einer Gruppe arbeiten alle Module unabhangig aber synchron mit den gleichen Befehlen bzw. Daten. Zum Beispiel wird man die 3 Prozessoren eines Triple-Modular-Redundancy-Systems als eine Gruppe darstellen. Mehrere disjunkte Gruppen konnen nebeneinander existieren. 2.1 Die Speichermodule Der Zustand eines Speichers wird de niert durch ein Feld von Bits, die angeben, welche der gespeicherte Worte fehlerhaft sind. Es wird also nicht der tatsachliche Speicherinhalt simuliert. Die Funktionalitat der Adressierungslogik wird bei jedem Speicherzugri simuliert. Obwohl Caches im Systemmodell nicht explizit dargestellt werden, wird der Einu von Caches auf Fehlerlatenzzeiten und Fehlerausbreitung durch das Workload Modell berucksichtigt. 2.2 Die Prozessormodule Die Tatigkeit des einzelnen Prozessors dirigiert ein stochastisches Modell. Der Prozessorzustand andert sich, wenn im Prozessor ein Defekt auftritt, oder wenn ein fehlerhafter Wert aus dem Speicher gelesen wird (trotz oder durch Fehlertoleranzmechanismen) 2.3 Die Fehlertoleranzmechanismen Die Fehlertoleranzmechanismen sind Hardwarekomponenten. Sie sollen in der Lage sein, Fehler wahrend eines Zugri s zu erkennen, zu korrigieren oder zu maskieren und bei Ausfall von Modulen das System neu zu kon gurieren. Die Arbeit dieser Komponenten wird durch sechs Softwareroutinen nachgebildet. Diese geben an, wie Adressen und Daten bei dem Zugri transformiert werden. Frei spezi zierbar sind dabei nicht nur Anzahl und Funktionalitat, sondern auch Zusammenhange zwischen den einzelnen Teilen. Dies alles gewahrleistet die notige Flexibilitat um verschiedene Multiprozessorsyssteme abbilden zu konnen. 3 Das Workload Model 3 Ausgangspunkt bildet eine synthetische Workload. Es wird also kein wirklicher Programmcode verwendet, die simulierte Befehlsausfuhrung soll jedoch ein realistisches Verhalten zeigen, was Zugri e auf den Speicher und die dadurch mogliche Fehlerfortpanzung und Fehlerausloschung betri t. Die Workload wird spezi ziert durch 4 Variablen. Das ist die Befehlsausfuhrungsrate (Befehle pro Zeiteinheit), die Leserate und die Schreibrate (Speicherzugri e pro Instruktion) und dazu eine Angabe uber das Lokalitatsverhalten. Zu der Leserate wird noch eins dazuaddiert diese Eins soll dem Lesen der Instruktion entsprechen. Will man den Einu von Cache zu berucksichtigen, so mu man noch die cache miss rate dazumultiplizieren, um die tatsachlichen Speicherzugri sraten zu erhalten. Leserate, Schreibrate und cache miss rate ermittelt man am besten aus einer Analyse eines entsprechenden Uniprozessorsystems. In der Literatur ndet man hierzu Tabellen. Die Speicherzugri e nden in der Simulation nur wortweise statt, nicht wie in realistischen Systemen in Einheiten der Cache-Zeilengro e. Es geht hier nur darum, den Informationsu korrekt darzustellen. 3.1 Das Referenzlokalit
atsmodell Das Referenzlokalitatsmodell beschreibt, wie weit sich Zugri e auf den Speicher verstreuen, es handelt sich mathematisch um eine Verteilung. REACT geht von Bradford-Zipf-Verteilungen1 aus. Der Speicher wird in zwei Bereiche zerlegt, den lokalen und den fernen. Der Anteil des lokalen Bereichs an der gesamten Gro e des Speichers wird durch die Variable
angegeben, der Anteil der Zugri e auf den lokalen Bereich durch .2 Innerhalb und ausserhalb des lokalen Bereiches wird jeweils eine uniforme Verteilung angesetzt. Bradford-Zipf-Verteilungen gehoren zu den hyperbolischen Verteilungen. Man kann sie bei der Untersuchng von Lokalitatsverhalten in sehr verschiedenen Wissenschaftsgebieten antreen. Falls eine Bradford-Zipf-Verteilung vorliegt, erhalt man eine S-formige Kurve, wenn man die Haugkeitsverteilung (z.B. Zahl der Zugri auf eine bestimmte Speicherzelle) uber dem logarithmischen Entfernungsmass (z.B. Stellenzahl der relativen Adresse, mit der auf diese Speicherzelle zugegrien wird), auftragt. 2 Bei vielen kommerziellen Applikationen setzt man
auf 20% und  auf 80%. Das ist die beruhmte 80/20-Regel, die besagt, da sich 80 Prozent aller Speicherzugrie sich auf einen Bereich beschranken, der nur 20 Prozent ausmacht. 1 4 Fault und Error Model 4 injeziert sowohl permanente als auch transiente Defekte. Defekte in verschiedenen Modulen sind stochastisch unabhangig voneinander. Die Zeit, zu der ein Fehler eintritt, ist eine Zufallsgro e mit einer Weibull( )-Verteilung. REACT FWeibull (t) = 1 ; e;(
t)
Wenn mehrere Fehler auf die selbe Stelle tre en, setzt sich der mit der langsten Dauer durch. Reparaturdauern sind logarithmisch normalverteilt. Flog normal (t) = p1 Z ; ln t  2 ;1 x2 e; 2 dx Eine Reparatur beginnt erst nach eine logistischen Verzogerung Plogistics. Das instandgesetzte Modul mu wieder synchronisiert werden dabei verstreicht die Resynchronisationsverzogerung Tresynch . Nach einem kritischen Fehler mu das System neu gestartet werden das kostet die Neustartverzogerung Treboot.                   4.1 Das Fehlermodell der Speicherdefekte Address Active Logic permanent 6 Pbit-array 6 Pbit-latentLatent Fault 6 Next Write Wperm Fault  Free Wtrans 1 Cycle Overwrite Address Active Logic transient 6 Pbit-matrix 6 Pbit-latent Fault Memory faults teilen sich zum einen auf in permanente und transiente zum anderen in solche, die die Bitmatrix und solche, die die Adressierungslogik betre en. 5 Permanente Defekte in der Adressierungslogik fuhren zum Zugri auf zufallige Speicherworte, wo dann falsche Werte gelesen oder geschrieben werden. Permanente Defekte in der Bit-Matrix werden mit einer Wahrscheinlichkeit von Pbitlatent erst einmal latent. Dann werden sie bei nachfolgenden Schreibzugri en jeweils mit der Gegenwahrscheinlichkeit 1 ;Pbit;latent aktiv. Sind sie erst einmal aktiv, bleiben sie in diesem Fehlzustand. Transiente Defekte in der Adressierungslogik sind nur einen Zyklus lange wirksam. Transiente Defekte in der Bit-Matrix werden nur mit der Wahrscheinlichkeit 1 ; Pbit;latent uberhaupt wirksam und bleiben es so lange, bis die Speicherzelle uberschrieben wird. 4.2 Das Fehlermodell der Prozessoren Wie sich die Prozessoren im Fehlerfall verhalten, gibt das stochastische Modell vor. 6                        permanent Latent Fault Wlatent - Active Wperm Fault Free  Dormant Wtrans transient Fault Input Error Platch - Wactive 61 Cycle Pterm ? Wlatent Latent Active 6 ?Pupset Control Upset Permanente Defekte treten mit einer spezi schen Weibull-Verteilung auf. Sie sind zunachst jedoch latent, uben also noch keinen Einu aus. Die Latenzzeiten sind wiederum Weibull-verteilt. Im Zustand des aktiven permantenten Fehlers gilt ein Prozessor als ausgefallen. In jedem Zyklus wird er nun Fehler produzieren. Nur durch Reparatur und Resynchronisation kann er wieder in den fehlerfreien Zustand zuruckkehren. Auch transiente Prozessorfehler treten zu Weibull-verteilten Zeiten auf. So einen transienten Fehler stelle man sich vor als einen falschen Spannungswert auf einer prozessorinternen Leitung. Mit einer Wahrscheinlichkeit Platch wird dieser abgegri en und ruft einen latenten Fehler hervor. Falls dies nicht geschieht, verschwindet die Storung wieder und der Prozessor kehrt in den fehlerfreien Ausgangszustand zuruck. Der latente transiente Fehler bleibt eine Weibull-verteilte Dauer bestehen. Danach gibt es zwei Moglichkeiten. Mit einer Wahrscheinlichkeit von Pupset wird er den Kontrollu des ausgefuhrten Programmes durcheinanderbringen. Der Prozessor weicht dann vom korrekten Instruktionsstrom ab. In diesem "Control Upset\-Zustand verursacht er in jedem Zyklus Fehler, bis er schlie lich resynchronisiert wird. Mit der Gegenwahrscheinlichkeit 1 ; Pupset fuhrt der latente 7 transiente Fehler in den aktiven transienten Fehlzustand. Der aktive Zustand wechselt sich mit dem Ruhezustand dormant state\ ab. Im aktiven Zustand produziert der Prozessor einen Zyklus" lange Fehler, dann wechselt er fur eine Weibull-verteilte Weile in den Ruhezustand, nach der er, falls er mit einer Wahrscheinlichkeit von Pterm in den fehlerfreien Ausgangszustand zuruckfallt, wieder in den aktiven Zustand wechselt, und so fort. Dieses zyklische Verhalten entspricht in der Realitat zum Beispiel einem falschen Wert in einem Register oder einem Cache, der mehrmals ausgelesen wird, bis er schlie lich uberschrieben wird. Die benotigten statistischen Gro en fur das Verhalten von transienten Fehlern ndet man nicht direkt in der Literatur. Man meint aber, sie aus den verzeichneten Zeiten zwischen Fehlern "time between errors'"herausrechnen zu konnen. Die Ausfuhrung einer Instruktion gilt als fehlerfrei, wenn der Prozessor fehlerfrei ist und kein fehlerhaftes Wort gelesen wurde. Ein Schreibzugri einer fehlerhaften Befehlsausfuhrung gilt als das Schreiben eines fehlerhaften Wortes. 4.3 Das Fehlermodell der Fehlertoleranzmechanismen Permanente und transiente Defekte treten zu Weibull-verteilten Zeitpunkten auf, wobei jede Komponente des Blocks aus Fehlertoleranzmechanismen ihre eigene unabhangige Verteilung besitzt. Weil die meisten der Fehlertoleranzmechanismen verhaltnisma ig einfach aufgebaut sind, kaum Zustande haben, geht man hier davon aus, da jeder Defekt auf ein beliebiges einzelnes Bit wirkt, ohne jede Latenz. Ein Fehlertoleranzmechanismus, der an einem oder mehreren solchen Defekten leidet, gilt als ausgefallen. 5 Der Ablauf einer Simulation Wahrend eines Laufs werden mehrere Versuche gestartet. Jeder Versuch ist eine Monte-Carlo-Simulation, die mit dem initialen, fehlerfreien System startet und zufallige Defekt-Ereignisse mit den spezi zierten Verteilungen injeziert und Reparaturen auslost. Die Anzahl der notigen Versuche hangt von dem geforderten Kon denzintervall ab. Die censoring time bestimmt die maximale Dauer eines Versuchs. Tritt vor Verstreichen der censoring time kein Versagen ein, gilt der Versuch als uberstanden und wird abgebrochen. Wenn nicht die Zuverlassigkeit ermittelt werden soll, sondern die Verfugbarkeit, dann ist die Laufzeit gro er, weil ein Versuch, bei dem ein Ausfall auftritt, nicht abgebrochen wird, sondern nach 8 einer simulierten Reparatur weitergefuhrt wird, bis die censoring time erreicht wurde. Erfreulicherweise fuhrt der hohe Abstraktionsgrad der beschriebenen Modelle dazu, da die Ausfuhrung einer Simulation viele Millionen mal weniger Rechenzeit verbraucht, als das simulierte System in der simulierten Zeit leistet. 6 Literaturverzeichnis Autor: Titel: Signatur: Impressum: ISBN/ISSN: weitere Autoren: weitere Angaben: diverse Foundations of dependable computing 14GI/mat 10.5.2-39 Boston u.a.] Kluwer Acad. Publ. 1994 ISBN 0-7923-9484-4 ed. by Gary M. Koob and Clifford G. Lau models and frameworks for dependable systems The Kluwer international series in engineering and computer science Aufsatzsammlung relevanter Teil: Section 3.2 "REACT: An Integrated Tool for the Design of Dependable Computing Systems" von Jeffrey A. Clark and Dhiraj K. Pradhan Autor: Titel: Signatur: Impressum: ISBN/ISSN: Untertitel: relevanter Teil: Milutinovic, Veljko M. Computer architecture 14GI/mat 10.2-278 New York u.a. North-Holland 1988 ISBN 0-444-01019-X concepts and systems Beschreibt einige der Systeme, die mit REACT modelliert wurden. Autor: Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery Special Interest Group on Measurement and 9 Evaluation, SIGMETRICS, Titel: Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems Signarur: 14GI/ZB-769 12 Impressum: New York, NY ISBN/ISSN: ISBN 0-89791-141-5 ISBN 0-89791-112-1 weitere Autoren: Joint Conference on Computer Performance Modelling, Measurement and Evaluation relevanter Teil: S. 28-40 "A measure of program locality and its application" von R. B. Bunt, J. M. Murphy und S. Majumdar. Anwendungen von Bradford-Zipf-Verteilungen. 10 Hauptseminar Simulationsbasierte Zuverl
assigkeitsanalyse Vortrag: Software-implementierte Fehlerinjektionsexperimente transienter Hardware-St
orungen Vortragender: Jorn Stiborsky Datum: 8.7.1996 1 Vorbemerkungen 1.1 Einfuhrung und Begrisdenitionen Moderne Hardware und auch Applikationen m
ussen in vielen Einsatzgebieten ein hohen Ma an Verl
asslichkeit garantieren. Dies erfordert eine immer intensivere Entwicklung von Fehlerdetektionsmanahmen und fehlertoleranter Mechanismen. Um diese zu bewerten und auf ihre Korrektheit hin zu validieren, werden Fehlerinjektionsexperimente durchgef
uhrt. Dabei ist es notwendig, die Begrie Fault (Defekt, St
orung), Error (Fehler, Fehlzustand) und Failure (Ausfall, Fehlfunktion) klar zu trennen. Ein Fault kann einen Error zur Folge haben, ein Error wiederum einen Failure. Die Injektion von Fehlern kann auf zwei Arten durchgef
uhrt werden:
direkt an der Hardware, wobei die St
orungen physikalisch erzeugt werden
am Simulationsmodell, welches das Verhalten des Systems widerspiegelt Das Ziel dieser Injektionen ist immer, die Fehler zu simulieren, die in der Realit
at tats
achlich auftreten (Coverage). Andererseits mu es vermieden werden Fehlfunktionen zu erzeugen, die in der Realit
at nicht Auftreten (Overhead). Ebenso sollte es in der Realit
at keine Fehler mehr geben, die nicht in der Simulation ber
ucksichtigt worden sind (Non-Coverage). Faults k
onnen auch nach ihrer Dauer klassi ziert werden. Dabei unterscheidet man zwischen permanent, intermittent und transient (f
ur die genaue Begriserkl
arung siehe Anhang). Die beiden letzteren sind die Hauptursachen f
ur Hardware-Faults. A
ltere Methoden, St
orungen zu simulieren, haben hohe Laufzeiten, Kosten und Genauigkeitseinschr
ankungen. In diesem Vortrag wird eine Methode vorgestellt, Fehler zu emulieren, wobei versucht wird, diese negativen Eekte einzuschr
anken. 1 1.2 Klassizierung von Fehlerinjektionstechniken Zun
achst werden einige Methoden vorgestellt, Faults sowohl in Software als auch in Hardware zu injizieren. Die Arten der Software-Injizierung werden kurz vorgestellt, weil einige Ideen davon in die Hardware Injektion eingegangen sind. 1.2.1 Methoden um Faults in Software zu injizieren Die Fehler werden einfach durch Modi kation des Quellcodes eingef
ugt.
Error Seeding: Man nimmt an, da k
unstlich eingef
ugte Fehler ebenso oft auftreten, wie Programmierfehler. Werden Errors nun w
arend der Debugphase injiziert und ndet der Debugger einige, so nimmt man an, da dieser auch Programmierfehler gefunden h
atte.
Mutation Analysis: Diese Methode benutzt man, um die Fehler-Aufdeckungsrate von Software-Test-Programmen zu ermitteln. Fehler werden eingef
ugt, das Programm versucht diese zu entdecken und f
uhrt dar
uber Statistik. 1.2.2 Methoden um Faults in Hardware einzufugen

Methode der Injektion { Software-Simulation: Das Komplette SUT wird auf einem anderen Rechner simuliert. Faults sind hier die Ver
anderung logischer Werte w
ahrend der Simulation. Nachteile sind die groen Geschwindigkeitseinbuen und die oft nicht zug
angliche Hardwarebeschreibung. { Hardware-Emulation: Die Hardware des SUT wird hier verwendet, wobei noch eine zus
atzliche Verdrahtung angebracht ist um Spannungswerte w
ahrend der Laufzeit hervorzurufen. Dabei ist wieder eine vollst
andige HW-Beschreibung notwendig. Diese Simulations-HW ist auerdem schwer herzustellen und die ist keine exakte Kopie des Originals. { Fault-Emulation: Das tats
achliche SUT wird benutzt, und Faults werden entweder durch zus
atzliche HW-Features oder durch SWIFI injiziert. Oft gibt es jedoch keine U
bereinstimmung mit den simulierten und den tats
achlichen Faults. { Physikalische Fault-Injektion: Die tats
achliche HW wird wieder benutzt. Faults werden durch Spannungs
anderungen oder durch Bestrahlung der Chips mit radioaktiven Teilchen erzeugt. Wiederum herrscht oft keine U
bereinstimmung mit simulierten und tats
achlichen Faults. Abstraktionslevel der Fehlerinjektionstechniken (Auf h
oherem Level wird gemessen, auf niedrigerem wird injiziert) { Circuit-Level Chip Basic Block Gate Device Device: Ein Transistor und dessen Arbeitsweise werden betrachtet. Bei simulierter Injektion wird dieser durch Strahlung oder andere physikalische Belastung beein ut. 2 Gate: Einfache logische Gatter (z.B. UND, ODER, Multiplexer) werden in ihrer Funktionsweise beein ut. Basic Block: Hier werden einzelne funktionale Einheiten wie Addierer, Decodierer und Register betrachtet. Die Funktionsweise kann durch Manipulation niedrigerer Komponenten beein ut werden. Chip: Faults werden an den a
ueren Schnittstellen der integrierten Schaltungen injiziert. Bei Microprozessoren werden diese St
orungen an den a
ueren Adre-, Daten- oder Kontroll-Leitungen erzeugt. { Functional-Level Network System Macro-Operation Micro-Operation Micro-Operation: Die Arbeitsweise des Microprozessors wird w
ahrend jeder Micro- Instruction gest
ort. Die Faults entsprechen fehlerhaften Daten-Transfers oder falschem Micro-Sequencing. Macro-Operation: Die Funktionsweise der Instruktionen des Prozessors wird durch Bit-Flips im Instruktionswort manipuliert. System: Die Speicher- und I/O-Zugrie des Prozessors werden gest
ort. Dies hat schlielich Auswirkungen auf die Systemebene. Network: Nachrichten und Zugrie auf gemeinsam benutzte Ressourcen werden gest
ort. 1.3 Verschiedene Arten der Fehler-Emulation Ein sequentielles Netzwerk kann man auf folgendes einfaches Modell reduzieren: Combinational Network (für boolsche Transformation des Inputs) Input-Vektor Output-Vektor State (Speicherelemente) Clock Es besteht aus einer Logikeinheit, die mit einem Speicherelement gekoppelt ist. Die Zustands
anderungen erfolgen durch den Takt. Seine Aufgabe ist die Transformation eines EingabeVektors in einen Ausgabe-Vektor. Analog kann man eine Prozessor auf dieses Modell reduzieren: Signale in den Prozessor an den I/O-Pins ALU Signale generiert vom Prozessor an I/O-Pins sichtbare und nicht sichtbare Register Clock Bei der Injektion von Faults w
ahren eines Intervalls T=t
t ] sind folgende zwei Gegebenheiten wesentlich: j 3 k 1. Die einzigen Parameter, die bestimmen was w
ahrend eines Intervalls T (begrenzt durch den Takt) passiert, sind der momentane Zustand t und der Eingabevektor. 2. Die direkten Auswirkungen einer Eingabe sind ausschlielich durch den neuen Zustand t und den Ausgabevektor bestimmt. Wenn eine Fault komplett innerhalb eines Intervalls auftritt, kann dieser nur den neuen Zustand t und den Ausgabevektor direkt beein ussen. Wenn dieser Defekt keine weiteren Auswirkungen auf folgende Zust
ande hat, nennt man ihn uberschrieben (overwritten). Dies tritt z.B. auf, wenn die ALU momentan nicht gebraucht wird. Beein ut er jedoch darauffolgende Zust
ande, spricht man von nicht-uberschrieben (non-overwritten). Er kann jedoch im Laufe der Zeit wieder u
berschrieben werden. j k k Die verschiedenen Methoden der Fault-Emulation: Forward Fault Emulation: Der momentane Zustand ist t . W
ahrend des Zeitraums T (bei SWIFI Zeit f
ur eine Instruktion) wird der Eingabevektor so manipuliert, da der neue Zustand der Auswirkung eines Faults, also einen Error (Fehlzustand) entspricht. Durch die Logikeinheit beschr
ankt kann jedoch der Ausgabevektor nicht jeden beliebigen Wert annehmen. Reverse Fault Emulation: Wenn sich das Netzwerk im neuen Zustand t be ndet, wird der Ausgabevektor direkt ver
andert (z.B. Bit-Flips). Im n
achsten Taktzyklus kann dieser fehlerhafte Vektor wieder als Eingabe dienen. Hybrid Fault Emulation: Man l
at den tats
achlichen Prozessor bis zu der Instruktion laufen, an welcher der Fehler simuliert werden soll. Zu diesem Zeitpunkt t wird der Zustand des Prozessors ausgelesen (sichtbare und nicht sichtbare Register, spezielle Pins am Prozessor erm
oglichen dies) und in das Simulationsmodell u
bertragen. Im Modell hat man nun freien Zugri auf die verschiedenen Einheiten des Prozessors. Die St
orung kann nun durch entsprechende Modi kationen von Zust
anden simuliert werden. Nach dieser Instruktion wird der Zustand des Modells wieder in den Prozessor zur
uckgelesen und dieser l
auft mit voller Geschwindigkeit weiter. Durch diese Methode werden Zeitverluste drastisch reduziert. Die hybride Methode stellt somit ein ezientes Werkzeug dar, auf Instruktionssatzebene transiente Faults in einem Combinational Network in einem vertretbaren Zeitrahmen zu simulieren. j k j 2 Hauptteil 2.1 Entwicklung eines Fehler-Modells FIAT und FERRARI (siehe Anhang) sind SWIFI Plattformen zur Fault-Emulation. Die simulierten St
orungen sind jedoch willk
urlich, und haben oft wenig Bezug zu real auftretenden Defekten. So ist das Coverage niedrig, der Overhead und die Non-Covered Faults sind hoch. Eine h
ohere Coverage kann durch eine komplette Simulation auf Device- oder Gatter-Ebene erzeugt werden. Dies birgt jedoch einige Schwierigkeiten in sich:
Eine exakte Hardware-Beschreibung ist oft nicht verf
ugbar. 4

Die Entwicklung solcher Modelle ist oft sehr kostspielig. Diese Simulationen ben
otigen sehr viel Zeit, auch wenn man nur ein beschr
anktes Zeitintervall betrachtet. Die Experimente, die in diesem Vortrag beschrieben werden, werden auf einer h
oheren Abstraktionsebene durchgef
uhrt, auf dem Register Transfere Level (RTL). Dies hat den Vorteil, da die Geschwindigkeit der Error-Erzeugung hoch ist und die Kosten niedrig. Die Abstraktionsebene kann deshalb h
oher als die Gatter-Ebene angesehen werden, da eine Operation des Prozessors nicht Zyklus f
ur Zyklus beschrieben sein muss. Andererseits ist sie niedriger als vorangegangene Modelle f
ur Bit-Flips, da die Funktionalit
at der Instruktionen ber
ucksichtigt wird. Durch die Software-Simulation wird nun eine v
ollige Kontrolle u
ber die Arten von Fehlern und Injektionen gew
ahrleistet. Da 80% bis 90% aller Fehler transient oder intermittend sind, spezialisiert sich dieses neue Werkzeug ausschlielich auf nicht-permanante Faults, die etwa durch eine instabile Hardware oder durch Umweltein
usse hervorgerufen werden. 2.2 ASPHALT: Ein Werkzeug fur hybride Fehler-Injektion auf RTL-Ebene Die Sprache ASPHALT stellt ein Werkzeug dar, hybride Fault-Emulation auf der RTL-Ebene zu betreiben. Dabei ben
otigt man eine Beschreibung des Prozessors aus der Sichtweise der Architektur. Dies beinhaltet eine Liste der Register und eine RTL-Beschreibung der DatenTransfers, die bei jeder Instruktion statt nden. Die Syntax von ASPHALT ist der von C sehr
ahnlich. Der Basis-Datentyp ist das Register, welches mit einer gewissen Bitl
ange deklariert werden mu . Auf die Register kann entweder ganz oder mit einer Spezi zierung der Bit-Anzahl zugegrien werden. Register gleicher Gr
oe k
onnen zu einem Register-File zusammengefat werden und auf dieses kann man wie auf ein Array zugreifen. Die Sprache enth
alt ausserdem alle wichtigen Konstrukte wie if/then/else, while, for, do/while und spezialisierte Fallunterscheidungs-Konstrukte wie decode/case. Einige weitere Besonderheiten, die f
ur die Prozessormodellierung notwendig sind:
Eingebaute Routinen zum Lesen und Schreiben auf Speicher und I/O sind vorhanden.
Eingebaute Routinen f
ur verschiedene Arten von Prozessor-Traps sind vorhanden: Adre, Bus-, Programm-, Privileg- und Opcode-Traps.
Die Additions- und Subtraktions-Operatoren erlauben ein optionales Carry-Bit Argument.
Alle arithmetischen und logischen Operatoren generieren automatisch passende negative-, zero-, carry- und overow-Flags.
Bitl
angen von Operanden werden nach Kompatibilit
at u
berpr
uft. Das Verketten und Herausziehen von Bit-Feldern wird unterst
utzt.
Der Benutzer ist auch in der Lage Subroutinen zu schreiben, deren Parameter call by name aufgerufen werden. Ebenso ist die Rekursion erlaubt. 5 2.3 RTL Fault-Modell der verschiedenen Einheiten eines Prozessors PROCESSOR Data Processing Storage Transfere Functional Units Control Processing Einen Prozessor kann man grob in eine Datenverarbeiungs- und eine Kontroll-Einheit unterteilen. Erstere ist wiederum in funktionelle Einheiten wie Speicherverwaltung, Transfereund Verarbeitungs-Einheit unterteilt. In diesem Abschnitt ist jede dieser Einheiten durch die RTL-Sprache beschrieben und ein Fehler-Modell wird darauf angewendet. F
ur den Entwurf eines Fehler-Modells gelten zwei grundlegende Regeln:
Die produzierten Faults sollen mit den tats
achlichen HW-St
orungen u
bereinstimmen.
M
oglichst implemtierungsunabh
angig bleiben (d.h. Annahmen werden gemacht, die fast jede Prozessor-Implementierung abdecken) Ziel ist es wiederum, das Coverage gro und den Overhead klein zu halten. Diese beiden Regeln beein ussen sich jedoch gegseitig in einer unangenehmen Weise. Bleibt man implementierungsunabh
angig und wird eine Vielzahl von Funktionen ber
ucksichtigt, ist das Coverage gro, der Overhead jedoch auch. Wenn die Implementierung nur die einfachsten StandardProzessorfunktionen abdeckt, ist das Verhalten genau umgekehrt. In den folgenden Beispielen werden nur nicht-permanente Faults injiziert. Die St
orung ist nur w
ahrend der Ausf
uhrung einer einzigen Code-Zeile aktiv. Es wird auch nur ein Fault pro Simulation injiziert. 2.3.1 Data Storage und Transfere Die Daten-Speicherungs-Einheiten sind die einzelnen Flip ops, Register und Register-Files (in ASPHALT alles als reg deklariert).
Die M
oglichen Hardware-Faults { Eine oder mehrere Einheiten bleiben auf 0 oder 1 stehen. { Eine oder mehrere Einheiten machen keinen 0-1 oder 1-0 U
bergang. { Ein oder mehrere Paare von Einheiten sind miteinander gekoppelt. { Alle oder manche Register werden mit einem Wert am Eingang geladen, wenn dies nicht passieren sollte (extraneous loads). { Alle oder manche Register werden nicht geladen, wenn dies passieren sollte (missed loads).
Auswahl bestimmter Faults f
ur die Emulation Um die Anzahl der Faults nicht zu hoch ansteigen zu lassen, werden nur einige ausgew
ahlt. So zum Beispiel einzelne Bit-St
orungen oder Faults beim L
oschen oder Setzen von Register-Werten. Die Missed Loads k
onnen auch einfach simuliert werden. Die Extraneous Loads werden jedoch nicht ber
ucksichtigt.
Liste der RTL-Faults 6 { Eine Bitfolge im Speicher oder in den Registern wird mit einem Bitvektor (2 j 0  i Vektorl
ange;1) durch XOR verkn
upft. i { Alle Bits eines Registers werden auf 1 gesetzt. { Alle Bits eines Registers werden auf 0 gesetzt. { Eine Wert-Zuweisung wird nicht ausgef
uhrt. So werden z.B. f
ur ein Register zeitweise die ersten drei genannten St
orungen injiziert, immer kurz bevor ein Wert in einem Register ben
otigt wird. Nun wird das Beispiel eines Multiplexers in einem Prozessor herangezogen. Dieser mu unter anderem ein Register aus einem Register-File ausw
ahlen, Eingabewerte f
ur die ALU selektieren und Werte ausw
ahlen, die in den Speicher geschrieben werden m
ussen. R0 R1 Rn MUX Die m
oglichen HW-Faults
{ Keine Quelle wird ausgew
ahlt. { Die falsche Quelle wird selektiert. { Mehr als eine Quelle wird ausgew
ahlt. Je nach Architektur der HW-Schaltung werden diese Werte durch AND oder OR verkn
upft. Auswahl bestimmter Faults f
ur die Emulation f
ur den Multiplexer Nur das zweite Fault-Modell wird in diesem RTL Modell benutzt, nur in Bezug auf die Auswahl eines Registers innerhalb eine Files. Dies zus
atzlich noch auf etwas anderes bezogen w
urden die Fehler sonst zu extrem ansteigen lassen. Liste der RTL-Faults f
ur Multiplexer So passiert der einzige injizierte RTL-Fault w
ahrend eines Zugris auf ein Register-Array. Statt des richtigen Registers wird ein anderes ausgew
ahlt.

Bei einem Demulitplexer wird ein Wert in ein bestimmtes Register hineingeschrieben. R0 R1 Rn DEMUX

Die m
oglichen HW-Faults sind die folgenden: { Kein Ziel ist ausgew
ahlt. { Anstatt des richtigen Ziels wird ein anderes oder noch zus
atzliche andere ausgew
ahlt. Auswahl bestimmter Faults f
ur die Emulation f
ur den Demultiplexer Der erste Punkt wird durch das schon oben genannte Missed Load erzeugt. So muss nur die Auswahl eines anderen oder mehrerer anderer Zielregister simuliert werden. 7
RTL-Fault f
ur Demultiplexer Soll ein Wert in ein Register innerhalb eines Arrays abgelegt werden, so w
ahlt man einfach beliebig ein anderes oder mehrere andere Register aus fuer die Abspeicherung des Wertes. Nun wird das Beispiel der Busse im Zusammenhang mit St
orungen genauer erl
autert.


Die m
oglichen HW-Faults in Bussen { Eine oder mehrer Leitungen bleiben im Zustand 0 oder 1. { Eine oder mehrere Leitungen bilden eine AND oder OR Funktion aufgrund von Kurzschl
ussen oder elektrischen Ein
ussen. Die Faults im internen Bus machen sich nur dann bemerkbar, wenn auch Daten intern transferiert werden. Faults, die sich nur auf eine einzige Leitung beschr
anken, werden schon von Bit-St
orungen in Registern sowie von den Input- und Output-Faults einzelner Bits in den funktionellen Einheiten (siehe unten) abgedeckt. Mehrere Bit-Faults werden nicht emuliert. F
ur die externen Busse werden einzelne Bit-St
orungen an den Adressen- und Datenleitungen injiziert. Die RTL-Faults sind dann die folgenden: { XOR-Verkn
upfung eines Bits einer Adresse (s.o.) vor einer Speicher- oder I/O- Lese- oder Schreib-Operation. Dies wird f
ur jedes Bit wiederholt. { XOR-Verkn
upfung eines Daten-Bits (s.o.) vor einer Speicher- oder I/O- Lese- oder Schreib-Operation. Dies wird f
ur jedes Bit wiederholt. 2.3.2 Data Processing Functional Units Die datenverarbeitenden funktionellen Einheiten sind ALU, Shifter oder andere spezielisierte Einheiten wie z.B. Inkrementierer. Wegen der Vielzahl dieser Komponenten, m
ussen die unterschiedlichen St
orungen auf einem m
oglichst allgemeinen Niveau betrachtet werden.
Die m
oglichen Hardware-Faults sind dann die folgenden: { Eine odere mehrere Eingabe-, Ausgabe- oder interne Daten-Leitung bleiben auf 0 oder 1 stehen oder sie beein ussen sich gegenseitig. { Ein oder mehrer Gatter erzeugen eine falsche Ausgabe. { Eine oder mehrere bedingte Anweisungen werden falsch ausgerechnet. { Die falsche Funktion wird ausgef
uhrt. { Ein Rechenschritt im Pr
aprozessor wird eliminiert. { Ein falscher Pr
aprozessorschritt wird durchgef
uhrt. F
ur ein RTL Fault-Modell m
ussen allgemeine Verarbeitungseinheiten beschrieben werden. Dies wird zuerst am Modell einer allgemeinen ALU gezeigt. Spezielle Einheiten wie Multiplizierer oder Dividierer werden wegen der Vielzahl der verschiedenen Implememtierungsm
oglichkeiten nicht modelliert. Durch Schiebe- und Addier-Operationen k
onnen diese jedoch emuliert werden. 8 A B n n Control n R

Condition codes: zero, overflow, negative, cary Auswahl bestimmter Faults am Beispiel der ALU Auerhalb der ALU k
onnen an den Daten-Ein- und Ausg
angen einzelne Bit-St
orungen auftreten. Control- und Pr
aprozessor-Faults werden auf einfache Permutationen reduziert (z.B. A op B ) A op A, A - B ) B - A, e.t.c). Die Ersetzung einer un
aren Operation durch eine bin
are wird wegen der vielen M
oglichkeiten f
ur den zweiten Input nicht modelliert. Einzelne Bitfehler im Condition Code werden durch St
orungen der Statuszeile in der Control Section generiert. Liste der RTL-Faults f
ur ALU-Operationen { Un
are Operationen  XOR-Verkn
upfung eines Bits des Ergebnisvektors dies wird f
ur jedes Bit wiederholt.  Eine andere un
are Operation wird durchgef
uhrt.  Die Eingabe wird unver
andert zur Ausgabe geschickt. { Bin
are Operationen  XOR-Verkn
upfung eines Bits des Ergebnisvektors dies wird f
ur jedes Bit wiederholt.  Eine andere bin
are Operation wird durchgef
uhrt dies wird f
ur jedes add, subtract, OR, NOR, XOR, XNOR, AND und NAND wiederholt.  Der A- oder B-Input wird direkt als Output durchgereicht.  Der A-Input wird auch als B-Input verwendet, oder umgekehrt (z.B. A + B ) A + A).  A oder B wird vor der Operation negiert. Dies schliet den Fall einer fehlenden Negation mit ein, denn :(:A) = A.  A oder B wird vor der Operation gel
oscht { Addition, Subtraktion und un
ares Minus  XOR-Verkn
upfung des U
bertrag-Eingabevektors.  XOR-Verkn
upfung eines Bits im U
bertrag dies wird f
ur jedes Bit wiederholt.  XOR-Verkn
upfung eines U
bertragbits und des entsprechenden Ergebnisbits dies wird f
ur jedes Bit wiederholt. { Vertauschung von A und B nur bei der Subtraktion, da alle anderen Operationen kommutativ sind. Als weiteres Beispiel wird ein allgeimeines Modell eines Shifters betrachtet. Um die Performance zu erh
ohen, ist diese Einheit oft Parallel zu den Datenpfaden der ALU geschaltet. 9 X Amount n log2n Generic Shifter Module Control n Z


Condition codes: zero, negative Die m
oglichen Hardware-Faults f
ur einen Shifter { Ein oder mehrere Bits des In- oder Outputs bleiben auf 0 oder 1 stehen. { Ein oder mehrere Gatter im Schiebe-Netzwerk bleiben auf open oder closed stehen. { Die falsche Funktion wird ausgef
uhrt (links/rechts). { Ein falscher Condition-Code wird erzeugt. { Der Amount-Wert ist falsch. Auswahl bestimmter Faults f
ur die Emulation Um die Zahl der RTL-Faults zu reduzieren werden nur Bit-Flips am Output simuliert, wodurch die Bit-Flips am Input und die Gatter-St
orungen im wesentlichen abgedeckt werden. Daraus ergeben sich folgende RTL-Faults: { XOR-Verkn
upfung eines Bits im Outputvektor Z dies wird f
ur jedes Bit wiederholt. { Verschiebung des Vektors X um die falsche Zahl dies wird f
ur jede falsche Zahl zwischen 0 und der L
ange von X wiederholt. { Die falsche Operation wird ausgef
uhrt und wiederholt f
ur jeden Links- und RechtsShift. 2.3.3 Kontroll-Einheit (Steuerwerk) Die Kontroll-Einheit eines Prozessors kann auf verschiedene Arten realisiert sein: fest-verdrahtet, mikroprogrammiert, nano-programmiert oder eine Kombination von diesen. Verschiedene Implementierungen dieser Einheiten sind f
ur unterschiede in der gleichen Architektur verantwortlich (z.B. Ausf
uhrungszeit, Taktzyklen, Parallelismus, Pipelining, e.t.c.).
Aus diesem Grund wird nur ein Fault-Modell auf einem hohen Level verwendet: { Es wird eine falsche Instruktion ausgef
uhrt wegen falscher Dekodierung. { Eine Steuer-Anweisung c(i) wird gest
ort:  c(i) fehlt, wenn sie ausgegeben sein sollte.  c(i) liegt st
andig an.  c(i) wird zus
atzlich oder anstelle von c(j) ausgegeben, immer dann, wenn c(j) anliegen sollte.  Status-Signale k
onnen gest
ort sein,
ahnlich den Steuer-Anweisungen. 10

Auswahl bestimmter Faults f
ur die Emulation: Um die erste St
orung zu simulieren, wird jede Instruktion als case-Anweisung in einer Dekodier-Instruktion angegeben. Dabei werden alle anderen Anweisungen statt der richtigen ausgef
uhrt. Fehlende Steueranweisungen werden dadurch emuliert, indem bestimmte Anweisungen nicht ausgef
uhrt werden. Eine fehlende load-Anweisung wurde schon durch die RegisterSt
orungen abgedeckt. Das st
andig anliegende c(i)-Signal ist ein permanenter Fehler und wird hier nicht modelliert. Das Anliegen eines falschen Kontroll signals wird eingeschr
ankt verwirklicht, indem nur ein falsches Kommando statt des richtigen ausgef
uhrt wird. Dies wurde durch andere St
orungen zum Groteil schon abgedeckt (z.B. aus einem Register-File wird das falsche Register ausgew
ahlt, Faults in ALU oder Schieberegister). Zus
atzlich modelliert wurde die Ersetzung eines Speicher- durch einen I/O-Lese/Schreibe-Zyklus (oder umgekehrt) oder die Ersetzung einer Signed- durch eine Unsigned-Bit-Extension oder umgekehrt. Fehler in den Status-Signalen werden modelliert, indem logische Werte negiert werden. Dies verursacht falsche Sprunganweisungen und Fehler im Condition-Code. Liste der RTL-Faults, die nicht durch obige Abschnitte schon abgedeckt worden sind: { Eine Evaluierungs-Anweisung wird nicht ausgef
uhrt. { Eine Speicher- oder I/O-Operation wird nicht ausgef
uhrt. { Ein Speicher-Read/Write wird duch einen I/O-Read/Write ersetzt (oder ungekehrt). { Eine Signed- wird durch eine Unsigned-Bit-Erweiterung ersetzt (oder umgekehrt). { Die Werte folgender logischer Operationen und Werte werden invertiert: logisches NOT, OR, AND Vergleichsoperatoren (not)equal, greater than (or equal) ConditionCodes negative, zero, carry, overow. 2.4 Die Arbeitsweise von ASPHALT Die Arbeitsweise von ASPHALT ist in vier Phasen aufgeteilt: 1. Lesen des RTL-Codes und des Anfangszustands: Es wird die RTL-Beschreibung eingelesen und die Registerwerte des tats
achlichen Prozessors kurz vor der Instruktion, die gest
ort wird. Instruktionen und Daten k
onnen aus dem Speicher gelesen werden. 2. Der storungsfreie Lauf (golden run): Die main-Routine und die von main aufgerufenen Prozeduren werden st
orungsfrei ausgef
uhrt. W
ahrend der Ausf
uhrung erstellt ASPHALT eine Liste (RTL execution trace) mit den Werten aller Operationen. Der Endzustand und eine Liste aller Speicher- und I/O-Ausgaben werden gespeichert. 3. Die Durchlaufe mit injizierten Storungen (faulty runs): ASPHALT geht die Liste vom vorhergehenden Durchlauf Schritt f
ur Schritt durch und macht jeweils einen gest
orten Durchlauf f
ur jeden m
oglichen Fault der in einer Operation auftreten k
onnte. Es wird immer nur ein Fault pro Durchlauf injiziert! Wenn dieser fertig ist, werden wieder der Endzustand und eine Liste aller Speicher- und I/O-Ausgaben gesichert. Falls die St
orung den Aufruf einer Fehler-Routine (fatal error)verursacht, wird der Typ des Fehlzustandes gespeichert. 11 4. Nachbearbeitung (post processing, error collapsing): Die Zust
ande aus den Listen der zweiten und dritten Phase werden miteinender verglichen. Wenn ein Fault keine weiteren Auswirkungen hat, k
onnen manche Zustandspaare identisch sein (overwritten fault). St
orungen der dritten Phase werden als a
quivalent betrachtet, wenn die Endzust
ande oder die aufgerufenen Fehler-Routinen gleich sind. Diagramm, das den Proze des error-collapsing zeigt: Injizierte RTL-Faults Resultieren de Zustände Overwritten-Faults Equivalent Fatal Errors Equivalent Error States 2.5 Validierung der RTL-Simulation am Beispiel des ROMP von IBM 2.5.1 Coverage versus Overhead Um herauszu nden, in welchem Ausma die Software-Simulation die Realit
at abdeckt, wird eine RTL-Simulation mit einer auf Gatter-Ebene ablaufenden verglichen. Die beiden Modelle m
ussen die gleiche Instruktion ausf
uhren, die gest
ort wird. Der Anfangszustand der Register und des Speichers mu ebenfalls identisch sein. Nach dem Durchlauf werden die beiden resultierenden Zust
ande miteinander verglichen. - Instruktion, die gestört wird - Anfangszustand (Register und Speicher) Initialisierung Initialisierung Simulation auf Gatterebene VERILOG RTL-Simulation Menge von Zuständen Menge von Zuständen ASPHALT Vergleich Den Vergleich kann man durch ein Venn Diagramm gra sch darstellen. Ziel der RTLSimulation ist, das die Resultate der St
orungen beider Modelle in hohem Ma u
bereinstimmen, d.h. das Coverage soll hoch sein. non-covered Resultierende Zustände aus der Gate-Level Simulation covered overhead Resultierende Zustände aus der RTL Simulation 2.5.2 ROMP U berblick Der ROMP von IBM wird f
ur verschiedene Versuchsreihen ausgew
ahlt. Zum einen, weil eine Prozessorbeschreibung auf Gatterebene bereits entwickelt worden ist, zum anderen, weil dieser Prozessor eine Vielzahl von Besonderheiten enth
alt: RISC Architektur, Pipelining, ein festverdrahtetes und micro-codiertes Steuerwerk und einen asynchronen Instruktions-Prefetch Buer. Er bestitzt auerdem 32bit General Purpose Register und 4Gb virtuellen Adressraum. Der Prozessor ist in vier Haupeinheiten unterteilt: Ausf
uhrungseinheit, Steuerwerk, InstruktionFetching und ROMP Storage Channel Interface. 12 2.5.3 ROMP Hardware-Modell Das Modell auf Gatter-Ebene wurde in VERILOG (HW-Beschreibungssprache und Simulator) in etwa 2600 Zeilen Code erstellt. Das Fault-Modell wird dabei in zwei Teile zerlegt:
Faults auf Gatter-Ebene: Dies sind einzelne transiente Fixed-At-0 oder Fixed-At-1 Faults. Leitungen bleiben entweder auf 0 oder auf einen bestimmten Wert f
ur einen Taktzyklus. Nur eine Code-Zeile pro Durchlauf wird gest
ort.
Register-Faults: Dies sind vor allem Missed Loads (das Register wird nicht geladen, wenn dies geschehen sollte), Extraneous Loads (das Register wird geladen, wenn dies nicht geschehen sollte), oder Bit-Flips in den Registern. Spannungs
anderungen an den Ein-und Ausgabeleitungen werden auf Gatter-Ebene durchgef
uhrt. 2.5.4 Ergebnisse Die Tabelle zeigt die Ergebnisse einer Fault-Injektion in die a (add) Instruktion des ROMP. Von den 771 Error-Zust
anden wurden durch das RTL-Modell 692 reproduziert. Weil das RTLModell des Steuerwerks auf einen h
oheren Level inplementiert ist (s.o.), wurden dort nur 68.85% der Fehler reproduziert im Gegensatz zu den 99.70% des Daten-Abschnitts. A
quivalente Error-Zustande, die auch Gesamtzahl der Faults die fatale injizierten Faults Errors verursachten Error-Zust
ande (s.o.) in RTL aufgetreten sind Gate-Level, Control-Section 4452 60 61 42 (68.86%) Gate-Level, Data-Section 7686 4 669 667 (99.70%) Total Gate-Level 12138 64 711 692 (97.33%) RTL-Level 1718 40 834 Quelle Bei den insgesamt 91 Befehlen des ROMP wurde eine Gesamt-Coverage von 0.972% erreicht. Bei einigen Befehlen wurden zun
achst nur niedrige Werte gemessen. Dies war auf Abweichungen in den Implentierungsdetails des Gatter- und des RTL-Modells zur
uckzuf
uhren. Nach genauer Code-Analyse sind diese beseitigt worden, so da kein Befehl einen Wert unter 0.94% erreicht. 2.5.5 Die benotigten Zeiten Die Versuche wurden auf einer DECstation 5000 durchgef
uhrt. Die folgende Tabelle vergleicht die Zeiten der VERILOG- mit der ASPHALT-Simulation: CPU-Zeit f
ur eine Instruktion Faults u
ber 91 Instruktionen Einzelne Error-States Injektion:Error Rate CPU-Zeit, um einen Error zu erzeugen Zeit f
ur alle Faults u
ber 91 Instruktionen VERILOG ASPHALT 1.65s 24.2ms 1 327 004 176 245 61 266 75 052 21.7 : 1 2.35 : 1 35.8s 56.9ms 609CPU-h 1.19CPU-h 3 Schlu: Beitrage zum Bereich der Fehlerinjektion Das Werkzeug ASPHALT hat einen groen Beitrag zum Bereich der Fehlerinjektion geleistet:
Ein neues Fehler-Modell ist entwickelt worden, das auf einer RTL-Beschreibung des Prozessors basiert. 13


Es gibt ein automatisiertes Werkzeug, das die Error-Patterns 500 mal schneller als ein Gatter-Modell des Prozessors injiziert. Bis zu 97% der Fehler eines Modells auf Gatter-Ebene k
onnen reproduziert werden. Dieses Fehler-Modell kann als Paradigma f
ur zuk
unftige Experimente an zuk
unftigen Prozessoren angesehen werden. 4 Anhang 4.1 Genaue Begrisdenitionen 4.1.1 Fault - Error - Failure Fault: Defekt, St
orung (z.B. auf Physikalischer Ebene) Error: Fehler, Fehlzustand (z.B. auf Informationsebene) Failure: Ausfall, Fehlfunktion (z.B. auf Systemebene) 4.2 Klassizierung von Faults nach ihrer Dauer permanent: st
andig, dauerhaft intermittent: tempor
ar, treten gelegentlich auf, wegen instabiler Hardware, e.t.c. transient: tempor
ar, von Umweltein
ussen abh
angig 4.2.1 reliability - availability - dependability reliability: Zuverl
assigkeit (Wahrscheinlichkeit R(t) daf
ur, da das System w
ahrend des Zeitintervalls 0, t] fehlerfrei ist, vorausgesetzt, es war zum Zeitpunkt t = 0 intakt R(t) = P f L > t g , mit R(0) = 1, L ist die Funktionsdauer des Systems (Lebensdauer)) availability: Verf
ugbarkeit (Wahrscheinlichkeit A(t) daf
ur, da das System zum Zeitpunkt t fehlerfrei ist (wobei es zuvor beliebig oft ausgefallen sein kann) A(t) = P f System intakt zur Zeit t g f
ur nicht reparierbare Systeme gilt A(t) = R(t)) dependability: Verl
asslichkeit (Ma f
ur Vertrauen, da man in Dienstleistung eines Rechensystems stecken kann) 4.3 Verwendete Abkurzungen und Erklarungen ASPHALT: ASembly-language level FAULT simulator DEPENT: Simulations-Umgebung FIAT: SWIFI Plattform f
ur hohe Fehlerquoten, die benutzt wird um Bit-Faults in einem Prozessor zu produzieren w
ahrend der Ausf
uhrung eines Befehls. Sie erzeugt Bit-Flips im Speicher, um fehlerhaftes Schreiben zu simulieren. 14 FERRARI: SWIFI Plattform f
ur hohe Fehlerquoten, die benutzt wird um Bit-Faults in einem Prozessor zu produzieren w
ahrend der Ausf
uhrung eines Befehls. Sie emuliert Zeilen-Fehler in den Adre- oder Daten-Zeilen, wenn ein Daten-Operand oder Opcode geholt wird, indem Code-Sequenzen modi ziert werden. Sie injiziert auch Fehler in den Condition-Code. FFE: Forward Fault Emulation HDL: Hardware Description Language MTTF: Mean Time To Failure (Mittlere Intaktzeit zwischen zwei Ausf
allen des Gesamtsystems) RFE: Reverse Fault Emulation ROMP: IBM's Risc Oriented MicroProcessor RTL: Register Transfere Level SUT: System Under Test SWIFI: SoftWare Implememted Fault Injection VERILOG: Hardware-Beschreibungssprache und -Simulator VLSI: Very Large Scale Integration 4.4 Literatur




Koob, G. Lau, C. Foundations od Dependable Computing Kapitel 3.1 IEEE, Vol. 39, NO. 4, April 1990, Seite 575 Fault Injection Experiments Using FIAT IEEE 1992 FERRARI: A Tool for The Validation of System Dependability Properties Dal Cin, M. Vorlesungsskript SS 96: Zuverl
assigkeit und Fehlertoleranz Golze, Ulrich VLSI-Entwurf eines RISC-Prozessors Vieweg 1995 15 Umgebung zur Modellierung von Rechnersystemen Probleme bei der Modellierung { { { { { Ungewohnte Ausdrucksform (Beispiel Petrienetze) Unbekannte Programmiersprache (Beispiel Simulator in C++) Haug unubersichtlich Schwierig zu erlernen Dokumentation neuer Elemente meist schlecht, somit konnen Elemente haug nicht wiederverwendet werden Anforderungen: { Unabhangigkeit von Programmiersprachen oder wenigstens die Moglichkeit, verschiedene Programmiersprachen frei zu mischen { Hilfestellung beim Analyse{Design{Implementations{Zyklus { Integration von Werkzeugen zur Erstellung der Dokumentation { Unterstutzung fur verschiedene Modellierungstechniken ( z.B. Petrinetze, ereignisorientierte Simulation ) { Oene Architektur 1 Designumgebung f
ur Elemente Beispiel: Leitungsvermittelnder Routing{Switch Zugang zu weiteren Editoren Warteschlange der Ausgänge Warteschlange für blockierte Ereignisse Abweiser Einstellung für den Takt 2 Beispiel f
ur Aufgabentrennung Beispiel: Fehlertoleranzbeschreibung wird von der Beschreibung der Mechanismen abgekoppelt. 4 BIGbold Implementation der Designs { Designs bestehen aus zwei Teilen:
Elementen (Trager der Struktur)
Komponenten (Trager des Verhaltens) { Elemente und Komponenten sind Objekte { Elemente und Komponenten wirken als Codegeneratoren { Werkzeuge fur Standardaufgaben (Hilfetexte, Einbindung in Dokumentation, Parameterdenition, : : :) 5 BIGbold Implementation der Klassen und Werkzeuge { Klassen fur Elemente und Komponenten und Werkzeuge mussen implementiert werden. { Oene Architektur heit, da der Anwender eigene Klassen und Werkzeuge implementieren kann. { Implementation der Werkzeug{ und Objektkommunikation und des Object{repository { Ebene reexiv, das heit, Werkzeuge implementieren Werkzeuge 6 BIGbold Zieldarstellung { Durch Modellierungsumgebung nicht festgelegt { 1. Implementation fur eventorientiert Simulation. { Verwendung von CORBA, um Sprachneutralitat zu gewinnen. 7 Problemorientierte Darstellung F
ur die Beschreibung sollten, wenn m
oglich, bekannte Verfahren verwendet werden. EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh VHDLEinführung 1/6 4.11.1997 Volkmar Sieh, IMMD-III / SFB-182 VHDLEinführung EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh VHDLEinführung 2/6 4.11.1997 Überblick über VHDL VHDL: Very High Speed Integrated Circuits Hardware Description Language vollständige Programmiersprache: z.B. – Arrays, Records, Pointer, Aufzählungstypen, … – FOR, WHILE, IF, CASE, …-Anweisungen – Funktionen, Prozeduren – Packages – Prozesse, Synchronisationsmechanismen besonders geeignet zur Beschreibung von Hardware-Komponenten VHDL beschreibt Komponenten durch • Beschreibung der Ein- und Ausgabesignale (Ports) und 1. Verhaltensbeschreibung 2. Strukturelle Beschreibung 3. Mischformen aus 1 und 2 EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E VHDLEinführung 3/6 4.11.1997 Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Beispiel für eine Beschreibung der Ein- und Ausgangssignale (Volladdierer) Carry-In Carry-Out Operand A Sum Operand B ENTITY full_adder IS GENERIC( delay: ); PORT( op_a: op_b: c_in: sum: c_out: ); END full_adder; time IN IN IN OUT OUT bit; bit; bit; bit; bit EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh VHDLEinführung 4/6 4.11.1997 Beispiel für eine Verhaltensbeschreibung (Volladdierer) ARCHITECTURE behaviour1 OF full_adder IS BEGIN sum <= op_a XOR op_b XOR c_in AFTER delay; c_out <= op_a AND op_b OR op_a AND c_in OR op_b AND c_in AFTER delay; END behaviour; oder ARCHITECTURE behaviour2 OF full_adder IS VARIABLE s: bit; VARIABLE c: bit; BEGIN PROCESS(op_a, op_b, c_in) BEGIN IF c_in = ’0’ THEN s := op_a XOR op_b; c := op_a AND op_b; ELSE s := NOT (op_a XOR op_b); c := op_a OR op_b; END IF; sum <= s AFTER delay; c_out <= c AFTER delay; END PROCESS; END behaviour; EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E VHDLEinführung 5/6 4.11.1997 Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Beispiel für eine strukturelle Beschreibung (Volladdierer) Carry In C3 Operand A Carry Out C2 Operand B C1 Sum EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh VHDLEinführung 6/6 4.11.1997 Beispiel für eine strukturelle Beschreibung (Volladdierer) ARCHITECTURE structural OF full_adder IS SIGNAL c1: bit; SIGNAL c2: bit; SIGNAL c3: bit; BEGIN gen_c1: and2 GENERIC MAP( delay => PORT MAP( i0 => i1 => o => gen_c2: and2 GENERIC MAP( delay => PORT MAP( i0 => i1 => o => gen_c3: and2 GENERIC MAP( delay => PORT MAP( i0 => i1 => o => gen_c_out: or3 GENERIC MAP( delay => PORT MAP( i0 => i1 => i2 => o => gen_sum: xor3 GENERIC MAP( delay => PORT MAP( i0 => i1 => i2 => o => END structural; delay/2) op_a, op_b, c1); delay/2) op_a, c_in, c2); delay/2) c_in, op_b, c3); delay/2) c1, c2, c3, c_out); delay) op_a, op_b, c_in, sum); EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 1/14 4.11.1997 Volkmar Sieh, IMMD-III / SFB-182 Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung • Motivation • VHDL-Erweiterung • Beispiel • Zusammenfassung EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 2/14 4.11.1997 Motivation Rahmen: statistische Bewertung von Software- und Hardware-Fehlertoleranzmaßnahmen durch Fehlerinjektionsexperimente Gegeben: Software (Betriebssystem + Last + Fehlertoleranz-Software) Hardware (VHDL-Modell) „Fehlermodell“ EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 3/14 4.11.1997 Motivation Aufgabe: • Durchführung von ca. 10000 Fehlerinjektionsexperimenten • Protokollierung der Auswirkungen • statistische Auswertung Problem: • In welche Komponente soll ein Fehler injiziert werden? • Welcher Typ von Fehler soll injiziert werden? • Wann soll der Fehler injiziert werden? • Wie lange soll der Fehler injiziert werden? Wie wahrscheinlich sind bestimmte Fehler zu einem bestimmten Zeitpunkt mit bestimmter Dauer in einer bestimmten Komponente? ⇒ Software- (und Hardware-) Test/Bewertung nur mit genauer Kenntnis der Hardware und ihrer Fehler(verteilungen) möglich EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 4/14 4.11.1997 VHDL-Erweiterung Lösungsansatz: Vereinigung von Hardware-Modell und Fehlermodell Teil des Hardware-Modells: • mögliche Fehlertypen • maximale Fehlerraten • Verteilung der Fehlerdauer • Fehlerauswirkungen Vorteile: für Fehlerinjektionsexperimente lassen sich die Fehlertypen und -zeitpunkte mit der jeweiligen Fehlerdauer automatisch generieren Chip-Designer bekommt Anhaltspunkte zur Optimierung Nachteil: erweiterte/neue Modellierungs-Sprache notwendig (Compiler/Simulator) EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 5/14 4.11.1997 Beispiel: Not-Gatter (Original): ENTITY not_gate IS PORT ( input: IN output: OUT ); END not_gate; bit; bit ARCHITECTURE behaviour OF not_gate IS BEGIN PROCESS (input) BEGIN output <= NOT input; END PROCESS; END behaviour; EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 6/14 4.11.1997 Beispiel: Not-Gatter (modifiziert): ENTITY not_gate IS PORT( input: IN output: OUT ); END not_gate; bit; bit ARCHITECTURE behaviour OF not_gate IS SIGNAL i_stuck_at_0: BOOLEAN INTERVAL 10000 h DURATION SIGNAL i_stuck_at_1: BOOLEAN INTERVAL 15000 h DURATION SIGNAL o_stuck_at_0: BOOLEAN INTERVAL 20000 h DURATION SIGNAL o_stuck_at_1: BOOLEAN INTERVAL 30000 h DURATION BEGIN PROCESS (input) BEGIN IF i_stuck_at_0 OR o_stuck_at_1 THEN output <= ’1’; ELSIF i_stuck_at_1 OR o_stuck_at_0 THEN output <= ’0’; ELSE output <= NOT input; END IF; END PROCESS; END behaviour; 5 5 5 5 ns; ns; ns; ns; EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 7/14 4.11.1997 Beispiel (Latch): ENTITY latch IS PORT( clk: input: reset: output: ); END latch; IN IN IN OUT bit; bit; bit; bit ARCHITECTURE behaviour OF latch IS SIGNAL i_stuck_at_0: BOOLEAN INTERVAL 1e14 SIGNAL i_stuck_at_1: BOOLEAN INTERVAL 1e14 SIGNAL clk_stuck_at_0: BOOLEAN INTERVAL 1e13 SIGNAL clk_stuck_at_1: BOOLEAN INTERVAL 1e13 SIGNAL reset_stuck_at_0:BOOLEAN INTERVAL 1e10 SIGNAL reset_stuck_at_1:BOOLEAN INTERVAL 1e10 SIGNAL o_stuck_at_0: BOOLEAN INTERVAL 1e15 SIGNAL o_stuck_at_1: BOOLEAN INTERVAL 1e15 BEGIN PROCESS(clk, input, reset, ...) VARIABLE state: bit := ’0’; BEGIN IF (reset = ’1’ AND NOT reset_stuck_at_0) OR reset_stuck_at_1 THEN state := ’0’; ELSIF (clk = ’1’ AND NOT clk_stuck_at_0) OR clk_stuck_at_1 THEN IF i_stuck_at_0 THEN state := ’0’; ELSIF i_stuck_at_1 THEN state := ’1’; ELSE state := input; END IF; END IF; IF o_stuck_at_0 THEN output <= ’0’; ELSIF o_stuck_at_1 THEN output <= ’1’; ELSE output <= state; END IF; END PROCESS; END behaviour; ns ns ns ns ns ns ns ns DURATION DURATION DURATION DURATION DURATION DURATION DURATION DURATION 1 2 1 2 1 2 1 2 ns; ns; ns; ns; ns; ns; ns; ns; EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 8/14 4.11.1997 Auswertungsbeispiel 2-Bit-Zähler 1 register bit0 reset clock register bit1 reset clock EXA NDER H ER F RIE D RIC IV L A R G SIT Ä T ER Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh -U N AL NG EN - NÜRN B E Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 9/14 4.11.1997 Trace-Files (Beispiel) Fehlerfreier Lauf: 200 210 211 211 212 213 214 214 215 220 230 231 231 231 231 232 232 233 233 234 234 240 ’1’ ’0’ ’1’ ’1’ ’0’ ’0’ ’0’ ’1’ ’1’ ’1’ ’0’ ’0’ ’1’ ’0’ ’1’ ’1’ ’0’ ’0’ ’1’ ’1’ ’1’ ’1’ ’0’ ’1’ ’0’ ’0’ ’1’ ’1’ ’1’ ’0’ ’0’ ’0’ ’1’ ’1’ ’0’ ’1’ ’0’ ’0’ ’1’ ’1’ ’0’ ’0’ ’0’ ’0’ /CLK /CLK /BIT0/TMP_O /O0 /BIT0/TMP_I /C01 /CO /BIT1/TMP_I /CO /CLK /CLK /BIT0/TMP_O /BIT1/TMP_O /O0 /O1 /BIT0/TMP_I /BIT1/TMP_I /CO /C01 /CO /BIT1/TMP_I /CLK Fehlerhafter Lauf: 200 208 210 211 211 220 230 233 234 235 236 236 237 240 ’1’ ’0’ /CLK FALSE TRUE /BIT0/XOR2/SA1_I1 ’0’ ’1’ /CLK ’1’ ’0’ /BIT0/TMP_O ’1’ ’0’ /O0 ’1’ ’0’ /CLK ’0’ ’1’ /CLK TRUE FALSE /BIT0/XOR2/SA1_I1 ’0’ ’1’ /BIT0/TMP_I ’0’ ’1’ /C01 ’0’ ’1’ /CO ’1’ ’0’ /BIT1/TMP_I ’1’ ’0’ /CO ’1’ ’0’ /CLK Welche Daten sind für den Benutzer interessant? EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 10/14 4.11.1997 Welche Daten sind für den Benutzer interessant? – Wahrscheinlichkeiten für eine bestimmte Auswirkungen der Fehler • für das gesamte System • innerhalb einzelner Komponenten – Verteilung der Recovery-Zeit für Fehler • im gesamten System • innerhalb einzelner Komponenten – Wahrscheinlichkeit einer bestimmten Auswirkungen abhängig von der Fehlerdauer – Wahrscheinlichkeit einer bestimmten Auswirkungen abhängig vom Systemzustand – …? EXA NDER -U ER F RIE D RIC IV H - N AL L /: | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | R G SIT Ä T ER A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 11/14 4.11.1997 BIT0: | AND2: | | 0( 0.0) 61( 47.3) 68( 52.7) 2.87 | | 0( 0.0) 51( 38.9) 80( 61.1) 2.83 | | 0( 0.0) 65( 52.4) 59( 47.6) 2.81 | | 0( 0.0) 115(100.0) 0( 0.0) | | 0( 0.0) 42( 37.2) 71( 62.8) 2.01 | | 0( 0.0) 55( 44.4) 69( 55.6) 2.01 | 0( 0.0) 389( 52.9) 347( 47.1) 2.50 | REGISTER1: | | 0( 0.0) 95( 84.8) 17( 15.2) 2.47 | | 0( 0.0) 17( 13.8) 106( 86.2) 4.07 | | 2( 1.8) 107( 94.7) 4( 3.5) 11.00 | | 0( 0.0) 74( 60.7) 48( 39.3) 4.50 | | 0( 0.0) 115( 88.5) 15( 11.5) 2.07 | | 0( 0.0) 16( 12.4) 113( 87.6) 4.98 | | 0( 0.0) 104( 83.2) 21( 16.8) 2.33 | | 0( 0.0) 106( 98.1) 2( 1.9) 1.00 | 2( 0.2) 634( 65.9) 326( 33.9) 4.23 | XOR2: | | 0( 0.0) 3( 2.5) 118( 97.5) 3.44 | | 0( 0.0) 16( 13.8) 100( 86.2) 3.06 | | 0( 0.0) 12( 10.3) 105( 89.7) 3.93 | | 0( 0.0) 148(100.0) 0( 0.0) | | 0( 0.0) 9( 7.4) 112( 92.6) 4.03 | | 0( 0.0) 18( 13.3) 117( 86.7) 3.04 | 0( 0.0) 206( 27.2) 552( 72.8) 3.50 2( 0.1) 1229( 50.0) 1225( 49.9) 3.41 BIT1: | AND2: | | 0( 0.0) 91( 75.2) 30( 24.8) 1.00 | | 0( 0.0) 73( 65.8) 38( 34.2) 1.00 | | 0( 0.0) 78( 77.2) 23( 22.8) 1.00 | | 0( 0.0) 95( 74.8) 32( 25.2) 1.00 | | 0( 0.0) 110( 75.3) 36( 24.7) 1.00 | | 0( 0.0) 29( 22.1) 102( 77.9) 1.00 | 0( 0.0) 476( 64.6) 261( 35.4) 1.00 | REGISTER1: | | 0( 0.0) 135( 95.1) 7( 4.9) 1.57 | | 0( 0.0) 65( 52.8) 58( 47.2) 2.10 | | 1( 0.7) 141( 96.6) 4( 2.7) 11.75 | | 0( 0.0) 84( 75.0) 28( 25.0) 2.86 | | 0( 0.0) 102( 97.1) 3( 2.9) 2.00 | | 0( 0.0) 75( 54.3) 63( 45.7) 2.29 | | 0( 0.0) 124( 96.1) 5( 3.9) 1.00 | | 0( 0.0) 121(100.0) 0( 0.0) | 1( 0.1) 847( 83.4) 168( 16.5) 2.47 | XOR2: | | 0( 0.0) 67( 50.4) 66( 49.6) 2.06 | | 0( 0.0) 77( 54.6) 64( 45.4) 1.22 | | 0( 0.0) 58( 50.0) 58( 50.0) 1.95 | | 0( 0.0) 61( 52.6) 55( 47.4) 1.07 | | 0( 0.0) 64( 50.8) 62( 49.2) 1.23 | | 0( 0.0) 71( 53.0) 63( 47.0) 1.92 | 0( 0.0) 398( 52.0) 368( 48.0) 1.58 1( 0.0) 1721( 68.3) 797( 31.6) 1.58 3( 0.1) 2950( 59.3) 2022( 40.6) 2.69 SA0_I0 SA0_I1 SA0_O SA1_I0 SA1_I1 SA1_O SA0_D SA0_Q SA0_R SA0_T SA1_D SA1_Q SA1_R SA1_T SA0_I0 SA0_I1 SA0_O SA1_I0 SA1_I1 SA1_O SA0_I0 SA0_I1 SA0_O SA1_I0 SA1_I1 SA1_O SA0_D SA0_Q SA0_R SA0_T SA1_D SA1_Q SA1_R SA1_T SA0_I0 SA0_I1 SA0_O SA1_I0 SA1_I1 SA1_O EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 12/14 4.11.1997 Anzahl der korrigierten Fehler Verteilung der Recovery-Zeit 6000 5000 4000 3000 2000 1000 0 0 ns 5 ns 10 ns 15 ns 20 ns 25 ns Zeit nach dem Verschwinden der Fehlerursache EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 13/14 4.11.1997 Probleme am Beispiel eines Modell eines ATM-Switches – Anzahl der Trace-Files • ein fehlerfreier Lauf • ca. 10000 fehlerbehaftete Läufe – Größe der Trace-Files • fehlerfreier Lauf ca. 6 MByte • fehlerbehafteter Lauf ca. 100 KByte ⇒ Berechnung der Traces sehr zeitaufwendig • Abbruch der Simulation, wenn der Fehler aus dem System erkennbar verschwunden ist • ein fehlerfreier Lauf wird als Ausgangspunkt aller Fehlerläufe verwendet ⇒ 10000 Fehlerinjektionen brauchen „nur“ ca. 4 Stunden ⇒ Auswertung der Trace-Files sehr zeitaufwendig • …? ⇒ Auswertung von 10000 Experimenten braucht ca. 4 Tage – Welche Daten sind für den Benutzer interessant? EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Friedrich-Alexander-Universität Erlangen-Nürnberg IMMD-III / SFB-182 Volkmar Sieh Erweiterung der Modellierungssprache VHDL zur Fehlerbeschreibung 14/14 4.11.1997 Zusammenfassung Software-Entwickler: Fehlerinjektionsexperimente können • ohne Kenntnis der Hardware • automatisch durchgeführt werden Hardware-Entwickler: Bei der strukturellen Modellierung der Hardware steckt die Fehlerbeschreibung schon in den verwendeten Komponenten • kein/kaum erhöhter Modellierungsaufwand • kein/kaum zusätzlicher Aufwand beim Testen Seminar Titel VHDL-basierte Fehleranalyse eines ATM-Switches Fehlermodell und Meßmethoden 1 von 17 10. Juli. 96 Übersicht Seminar 2 von 17 • Motivation • Überlegungen zum Detailgrad der Modellierung • Das Modell eines ATM-Switches • Fehlermodell • Geplante Messungen 10. Juli. 96 Motivation Seminar 10. Juli. 96 Ziel: Diagnose großer Netzwerke P P S S S P S P S Netzwerk Switch • Neben Prozessorfehler müssen auch Fehler in Switches lokalisiert und klassifiziert werden • Grundlage für Diagnose: Wissen über Art und Verhalten von Fehlern 3 von 17 m n Motivation Seminar 10. Juli. 96 Quantitative Fehleranalyse eines ATM-Switches • möglichst detailgetreue Modellierung der Hardware ☞ VHDL • Fehlerinjektion ☞ Ermitteln von Fehlerklassen innerhalb von Modellebenen ☞ Abbildung von Fehlern zwischen den Modellebenen Ebene x Register Busfehler Zellfilter ... fx(Fehlertyp) Ebene x+1 4 von 17 Input Ik kann nicht mehr Nachricht wird zum Output Om durchschalten verfälscht ... Überlegungen zum Detailgrad Seminar 10. Juli. 96 Unterschiedliches Fehlerverhalten bei Pin-level Fehlerinjektion und Fehlerinjektion in interne Komponenten Beispiel: Counter mit J-K FlipFlops stuck_at_1 count enable & & clock J K C J C Q K J C Q A2 K Q A1 A0 Richtige Zählerfolge 000 001 010 011 100 101 110 111 000 001 010 interner Fehler 000 001 010 101 110 111 000 001 010 011 100 pin-level Fehler 000 001 010 xxx 100 101 110 111 000 001 010 5 von 17 Überlegungen zum Detailgrad Seminar 10. Juli. 96 Ziel: Analyse von Fehlerauswirkungen in einem System möglichst detailgetreue Modellierung • VHDL-Gattermodelle von Switches nicht vorhanden ☞ Komponenten gemäß Standards identifizieren (ITU, ATM, etc.) ☞ Keine abstrahierende Modellierung bekannter Hardwarekonzepte ☞ Keine Modellierung unbekannter Hardwareimplementierungen • 6 von 17 Switch-Modell besteht aus vielen verschiedenen Abstaktionsebenen (je nach vorhandener Information über die zu modellierenden Komponenten) Modell eines ATM-Switches Seminar 10. Juli. 96 Der Knockout-Switch • Informationsquellen • Yeh, et. al., (ATT-Bell Labs): Vermittlungstechnologie • ITU-recommendations : Physical-Layer und ATM-Layer • Grobaufbau Kabel ATM-Protokoll ATM-Protokoll ATM-Protokoll 7 von 17 Bus Interface Bus Interface Bus Interface ATM ATM ATM Modell eines ATM-Switches Seminar • 10. Juli. 96 Kabel - CMI-Kodierung des Signals 0 0 T\2 1 0 1 1 1 T\2 T • Eingangsprotokoll - Übersicht Kabel decoder Delineation Sync_buffer Router ATM-Protokoll auf Switch-Ebene 8 von 17 Modell eines ATM-Switches Seminar • Eingangsprotokoll - Delineation 7 bit 0 VPI VPI 1 VCI VCI VCI PTI HEC HUNT byte P Mehrbit Fehler erkannt (Zelle vernichten) Fehlerfrei HEC incorrect PRESYNC ALPHA x incorrect DELTA x correct 9 von 17 • Zelle besteht aus 5 Byte Header und 48 Byte Payload • Header wird durch 8-bit CRC geschützt (korrigiert Einzelfehler, erkennt Mehrfachfehler) • Zellgrenzerkennung durch HEC (Header Error Control) 5 HEC OK SYNC 10. Juli. 96 correction mode kein weiterer Fehler Einbit Fehler erkannt (Korrigieren) Fehler detection mode Modell eines ATM-Switches Seminar • 10. Juli. 96 Eingangsprotokoll - Sync_Buffer und Router • Für jede eingehende Zelle wird vom Router evtl. VPI und VCI im Header umgesetzt • Router fügt Adresse für physikalischen Switch-Ausgang vor jede Zelle ☞ intern herrscht höherer Takt ☞ Sync_Buffer zur Anpassung an internen Takt • Routerkomponente kann nur auf sehr abstrakter Ebene modelliert werden (keine Information über Subkomponenten) • Vermittlungstechnologie - Übersicht 1 2 3 N Zellfilter Konzentrator 1 2 1 2 L Shifter L Shared Buffer Ausgang 10 von 17 Modell eines ATM-Switches Seminar • 10. Juli. 96 Vermittlungstechnologie - Konzentrator 1 2 Inputs 3 4 5 6 7 8 winner looser D D D D D D D D D D D D “Loosers” D Outputs 11 von 17 D Modell eines ATM-Switches Seminar • Vermittlungstechnologie - Shared_Buffer 1 2 3 4 5 6 7 8 Line Number 1 1 1 1 1 0 0 0 1: Filled Cell 0: Empty Cell First Cell Time 1 1 1 1 1 0 0 0 Si+1 = (Si + ki) mod L 1 1 1 1 0 0 0 0 Second Cell Time 1 0 0 0 0 1 1 1 12 von 17 Si: Shiftweite ki: Anzahl gefüller Zellen 10. Juli. 96 Fehlertypen Seminar • Fehler “nur” stuck-at Modell auf in-Ports und out-Ports ☞ 832 verschiedene Fehlertypen • passives stuck-at-x 10. Juli. 96 • Ein-/Ausgang einer Komponente kann einen durch korrektes Verhalten eingenommenen Zustand für eine bestimmte Zeitspanne nicht mehr verlassen • entspricht realem Verhalten [1] • bit-flip • Pegelwert ändert sich auf jeden Fall • Ungeeignet zur Untersuchung des Anteils “folgenloser” Fehler • aktives stuck-at-x • Pegel wird im moment der Aktivierung des Fehlers auf ‘x’ gesetzt • einfachere, schnellere Implementierung (weniger Code) 13 von 17 Fehlertypen Seminar 10. Juli. 96 • Beispiel normale Signaländerung passives stuck-at-1 aktives stuck-at-1 0 ➺ 1 keine Wirkung keine Wirkung 1 ➺ 1 keine Wirkung keine Wirkung 0 ➺ 0 keine Wirkung 0 ➺ 1 1 ➺ 0 1 ➺ 1 1 ➺ 1 14 von 17 Erste Meßergebnisse Seminar • 10. Juli. 96 Fehler im gesamten Switch 4800 "recovery_histogramm" System: DEC Anzahl Experimente: ... 5000 Gesamtzeit: ...................100000 Maximale Trace-Zeit ... 1000 Simulationsdauer .......... ca. 2Std. Erzeugte Datenmenge .. ca. 400 MByte 4750 4700 4650 4600 4550 4500 4450 4400 4350 4300 0 15 von 17 200 400 600 800 1000 1200 1400 1600 1800 2000 Erste Meßergebnisse Seminar • 10. Juli. 96 Fehler in Komponenten des Eingangsprotokolls 2900 "recovery_histogramm" System: DEC Anzahl Experimente: ... 3000 Gesamtzeit: ...................50000 Maximale Trace-Zeit ... 5000 Simulationsdauer .......... ca. 6 Std. Erzeugte Datenmenge .. ca. 500 MByte 2850 2800 2750 2700 2650 2600 2550 2500 2450 0 16 von 17 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Ausblick Seminar 17 von 17 • Lastgenerator • C104 - Switch • MIN - Multistage Interconnection Network (z.B. Benes-Netz) • Optische Netzwerktechnologie 10. Juli. 96 EXA NDER H ER F RIE D RIC IV L A R G SIT Ä T ER Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche -U N AL NG EN - NÜRN B E Fehlertoleranz auf Schaltnetzebene 1/10 8./9. Juli 1996 Fehlertoleranz auf Schaltnetzebene • Grundlagen • Maßnahmen und deren Charakteristik • Beispiel EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche Fehlertoleranz auf Schaltnetzebene 2/10 8./9. Juli 1996 Grundlagen • Fehlermodell • Wahrscheinlichkeit für mindestens einen Fehler im System steigt nahezu linear mit der Anzahl der Komponenten des Systems • Ein fehlertolerantes System zeigt an seinen Ausgängen keine Fehler oder bietet zusätzliche Informationen zur Korrektur von Ausgangsinformationen • Fehlertoleranzmaßnahme darf keinen Single-Point of Failure zu Folge haben EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Fehlertoleranz auf Schaltnetzebene 3/10 8./9. Juli 1996 Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche Single-Point of Failure Voter Voter 4 Bit Adder Voter Voter 4 Bit Adder Voter Voter 4 Bit Adder Voter Voter 4 Bit Adder EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche Fehlertoleranz auf Schaltnetzebene 4/10 8./9. Juli 1996 Maßnahmen • Fehlerkorrektur im Zeitbereich: • Fehlerkorrektur durch Wiederholung der logischen Funktionen • geringer zusätzlicher Gatteraufwand zur Fehlererkennung und Erweiterung des Steuerautomaten • Modifikation der Steuerung • Nachteil: Auswirkungen permanenter Fehler können nicht korrigiert werden • Fehlerkorrektur durch zusätzliche Logik: • Triple modular redundancy (TMR) • andere Kodierungen EXA NDER H ER F RIE D RIC IV R G SIT Ä T ER L A NG EN - NÜRN B Fehlertoleranz auf Schaltnetzebene 5/10 8./9. Juli 1996 Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche -U N AL E Kodierung Beispiel: 7/4-Hamming-Code-Addierer 7/4-HC 7/4-HC Decoder Decoder 4 Bit Adder 7/4-HC bit6 bit5 7/4-HC bit4 bit3 bit2 bit1 bit0 Coder 7/4-HC 7/4-HC Probleme: • Synthese der einzelnen Blöcke • Bestimmung des Gate-Overheads, um mit anderen Maßnahmen (z.B. TMR) vergleichen zu können EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Fehlertoleranz auf Schaltnetzebene 6/10 8./9. Juli 1996 Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche FSMs Eingang aktueller Zustand Kombinatorik Takt Speicher neuer Zustand Ausgang Fehlertoleranzmaßnahmen: • Maßnahmen im Zeitbereich komplex • Eingangs-, Ausgangs- und Zustandssignale können durch Kodierung geschützt werden • Taktleitung in Verbindung mit Speicher nur durch TMR-Maßnahme zu schützen EXA NDER H ER F RIE D RIC IV R G SIT Ä T ER L A NG EN - NÜRN B Fehlertoleranz auf Schaltnetzebene 7/10 8./9. Juli 1996 Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche -U N AL E FSMs Fehlertolerante FSMs: Eingaben Takt 7/4 H TMR Kombinatorik Speicher Parity Ausgaben 7/4 H Eingaben Kombinatorik Takt Speicher Voter Kombinatorik Speicher Voter Kombinatorik Speicher Voter EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche Fehlertoleranz auf Schaltnetzebene 8/10 8./9. Juli 1996 Charakteristik Zeitbereich: • geringer Gatter-Overhead • problematisch für Echtzeitanwendungen • keine Korrektur permanenter Fehler TMR • einfaches Prinzip • mindestens 3-facher Gatteraufwand • ermöglicht fehlertolerante FSMs Kodierung • sehr komplex • Gatteroverhead ? EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Fehlertoleranz auf Schaltnetzebene 9/10 8./9. Juli 1996 Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche Fifo ctrl_in clk data_in Mux Logik Reg6 ... Mux Reg1 Speicher Mux Reg0 ctrl_out data_out EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Fehlertoleranz auf Schaltnetzebene 10/10 8./9. Juli 1996 Seminar zur simulationsbasierten Zuverlässigkeitsanalyse Oliver Tschäche Fifo 2000 simple 1900 count 1800 1700 1600 1500 1400 0 1000 2000 3000 4000 5000 6000 Conjoint Simulation Axel Hein IMMD III Universität Erlangen-Nürnberg EXA NDER -U ER F RIE D RIC IV H - N AL R G SIT Ä T ER L A NG EN - NÜRN B E Seminar im SS ‘96 Simulationsbasierte Zuverlässigkeitsanalyse 08. - 09.07.1996 1 2 Inhalt ☞ Motivation ☞ AWM : Architecture-Workload Model ☞ FRM : Failure-Repair Model ☞ Conjoint Simulation : Kombination von AWM und FRM ☞ Conjoint Simulation : Implementierungsaspekte ☞ Conjoint Simulation : Zusammenfassung Conjoint Simulation A. Hein 3 Motivation ☞ Bewertung von fehlertoleranten parallelen Rechensystemen, so früh wie möglich in der Entwicklungsphase ☞ gemeinsame Leistungs- und Verläßlichkeitsbewertung (Performability) ☞ simulationsbasierte Bewertung ❏ Bewahrung der Flexibilität und Mächtigkeit von Simulationsmodellen ❏ Erhöhung der Anschaulichkeit großer und komplizierter Simulationsmodelle um die Schnittstelle zwischen Modell und Modell-Designer zu verbessern (design-oriented models) ☞ Darstellung komplexer Rechensysteme : massiv parallel und/oder komplizierte Zusammenhänge und Aktionen ☞ Modellierung von Architektur & Last & Fehler-Reparatur-Verhalten Conjoint Simulation A. Hein 4 Motivation ☞ Hauptziel des Conjoint Simulation : Verbesserung des Modellentwurfs und der Modellerstellung ☞ Prinzip: divide-and-conquer ❏ Partitionierung des Gesamtmodells in Teilmodelle ❏ getrennte und unabhängige Erstellung und Validierung der Teilmodelle ❏ Kombination der Teilmodelle zur gemeinsamen Auswertung ❏ Verwendung und Kombination unterschiedlicher Modellierungstechniken ☞ Partitionierung des Modells in Conjoint Simulation ❏ AWM : Architecture-Workload Model ❏ FRM : Failure-Repair Model Conjoint Simulation A. Hein 5 Motivation Workload Model FRM ... AWM ... Architecture Model k Failure-Repair Model Conjoint Simulation A. Hein 6 AWM : Architecture-Workload Model ✏ Unterteilung in Architecture-Model und Workload-Model ✏ Was wird im Architecture-Model dargestellt ? Bestandteile des Zielsystems: Prozessoren, Verbindungseinheiten, Speicher, etc. ❏ topologische Beziehungen zwischen den Bestandteilen ❏ weitere architektur-bezogenen Eigenschaften: process-scheduling, packet switching, message routing, etc. ... ... ... ... ... ❏ Conjoint Simulation A. Hein 7 AM : Architecture-Model ✏ prinzipieller Aufbau des Architecture-Model Architektur Klassen Architecture-Model Klassenbibliothek . .. .. . . ... .. Switch Speicher I/O Linkverbindung Architekturen Objekte der Komponenten ... Prozessor Conjoint Simulation A. Hein 8 AM : Architecture-Model ✏ Klassenhierarchie des Architecture-Model cluster_manager msg_monitor SimParMEMSY SimParPP svr_monitor MP_system grid global_ mapping_ table 1+ 1+ tree 1+ PRC MCI SWT LNK 1+ Conjoint Simulation A. Hein 9 AM : Architecture-Model ✏ 2 Wege zur Erstellung großer und komplexer Architecture-Model ❏ Topologie ist in einer parametrisierbaren Klasse festgelegt : e.g. class grid(x, y, z) ❏ Methoden zur Erstellung hierarchischer Architecture-Model => wesentliche Struktur : cluster - organisiert von der Klasse cluster_manager Conjoint Simulation A. Hein 10 AM : Architecture-Model ✏ hierarchisches Architecture-Model ❏ spiegelt den hierarchischen Aufbau heutiger Multiprozessorsysteme wieder : Clusters und Cubes in Parsytec Systemen, Hypernodes in Convex SPP, Pyramiden in Memsy, Bäume in CM-5 ❏ Definition von Clustern ➫ logische Einheiten ➫ besteht aus Basiskomponenten und anderen Clustern ➫ Cluster Hierarchie ❏ cluster-orientierter Zugriff auf die Cluster und Komponenten : z.B. ( PRC, 137 ) == ( cluster B, 2, cluster A, 4, PRC, 3 ) z.B. ( cluster B, 2, cluster A, 2, PRC, ALL ) ❏ cluster-orientierte Definition der Linkverbindungen und Routingmechanismen z.B. insert_links( FROM, cluster A, 1, PRC, ALL, TO, cluster A, 2, PRC, ALL, LINKS, 2 ) Conjoint Simulation A. Hein 11 AM : Architecture-Model ✏ Beispiel: Zielarchitektur ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ✏ hierarchisches Architecture-Model C ... ... ... B ... Cluster A x*y Cluster Hierarchie: ... Cluster B 4 A Cluster C PRC n PRC SWT Conjoint Simulation A. Hein 12 WM : Workload Model ✏ Was wird im Workload-Model dargestellt ? ❏ verteilte Algorithmen: Transaktionsverarbeitung, numerische Algorithmen, etc. ❏ Systemprogramme: dynamische Lastbalancierung, software-basierte Fehlertoleranzmechanismen, etc. ✏ Klassenhierarchie des Workload-Model (eine Applikation) wl_linear wl_application wl_application 1+ wl_process wl_mapping_table n wl_process 1+ wl_mapping_table wl_action act_use act_lin_comm wl_action Conjoint Simulation A. Hein 13 AWM : Architecture-Workload Model ✏ Welche Modellierungstechniken werden im AWM verwendet ? ❏ ❏ objekt-orientierte Modellierung : ➫ Klassen und Objekte repräsentieren vollständige Architekturen, Bestandteile von Architekturen, parallele Programme und Prozesse paralleler Programme ➫ Verwendung von Aggregation und Vererbung ➫ Bibliotheken : Architekturen, Architekturkomponenten, Applikationen, Applikationsprozesse prozess-basierte Simulation : ➫ dynamischer Ablauf wird dargestellt durch asynchron interagierende Simulationsprozesse (implementiert als Leichtgewichtsprozesse, Koroutinen, Threads, etc.) ➫ Abstraktion von den Ereignissen diskreter Simulation Conjoint Simulation A. Hein 14 AWM : Architecture-Workload Model ✏ Verknüpfung von Architecture-Model und Workload-Model zu AWM ❏ Abbildung des Workload-Model auf Architecture-Model (Mapping) ❏ Beispiel: Workload-Model mit 3 Applikationen Applikation 1 Applikation 0 Applikation 2 Spare Prozessor Objekt Prozessor Objekt Conjoint Simulation A. Hein 15 FRM : Failure-Repair Model ✏ Was wird im Failure-Repair Model dargestellt ? ❏ ❏ Fehler und Ausfälle von Bestandteilen des Architecture-Model ➫ zeitliches Verhalten: transient, permanent, intermittierend ➫ Lokalisierung: spezielle Komponenten oder zufällig ➫ komplexe Szenarien: korrelierte Fehler, Coinzidenz-Fehler ➫ ... Aktivierung und Steuerung von Fehlertoleranzmechanismen ➫ Erkennung fehlerhafter Komponenten ➫ Test, Reparatur ➫ Rekonfiguration, Wiederanlauf ➫ ... Conjoint Simulation A. Hein 16 FRM : Failure-Repair Model ✏ Welche Modellierungstechniken werden im FRM verwendet ? ❏ ❏ Petri Netze ➫ sehr anschaulich ➫ Darstellung von Nebenläufigkeit und Synchronisation in verteilten Systemen ➫ (Serien-Parallel-Diagramme, Fehlerbäume) zeitbehaftete Petri-Netze: timed-transition Petri net (TTPN) ➫ Zeit wird Transitionen zugeordnet (vgl. GSPN) ➫ quantitative Analyse zeitbehaftete Transition zeitlose Transition k Conjoint Simulation A. Hein 17 Conjoint Simulation : Kombination von AWM und FRM ✏ Definition der Schnittstellen zwischen AWM und FRM AWM FRM ? FRM AWM ✏ Zuordnung der Interaktionen zu den Transitionen des TTPN (FRM) ✏ interpreted timed-transition Petri net (ITTPN) ❏ jeder Transition ti des ITTPN werden zwei Mengen CAi und CFi zugeordnet: CAi : Menge von Operationen, die im AWM ausgeführt werden, sobald Transition ti aktiviert wird (mit Ausführungsprioritäten) CFi : Menge von Operationen, die im AWM ausgeführt werden, sobald Transition ti feuert Conjoint Simulation A. Hein 18 Conjoint Simulation ✏ Interaktionen zwischen AWM und FRM ❏ Steuerung des AWM durch das FRM FRM AWM pok tinj Aktive Rolle des FRM ... ... trecover pinj CAinj = 〈 starte Applikationen des Workload-Model 〉 CArecover = 〈 stoppe Applikationen des AWM 〉 CFinj = 〈 injiziere Fehler in einen CFrecover = 〈 repariere fehlerhafte Prozessor des AWM 〉 Komponente des AWM 〉 Conjoint Simulation A. Hein 19 Conjoint Simulation ✏ Interaktionen zwischen AWM und FRM ❏ Einfluß des AWM auf das zeitliche Verhalten des FRM ❏ AWM bestimmt die Zeit zwischen Aktivieren und Feuern der Transitionen des FRM FRM AWM pok tinj Aktive Rolle des AWM trecover pinj ... ... pdet tdet CAdet = 〈 warte auf Erkennen des Fehlers im AWM 〉 CFdet = 〈 Fehler wurde erkannt - im AWM 〉 Conjoint Simulation A. Hein 20 Conjoint Simulation ✏ Interaktionen zwischen AWM und FRM ❏ Einfluß des AWM auf den Ablauf der Ereignisse des FRM FRM pok tinj trec CAdet = 〈 warte auf Fehlererkennung im AWM 〉 trep pinj prep prec tdet tic ❏ pdet tip CFdet = 〈 Fehler ist erkannt im AWM; stoppe Applikationen im AWM and setze Parameter im FRM, so daß: => tic feuert, wenn Spare-Komponenten im AWM verfügbar sind => tip feuert sonst 〉 weiteres Beispiel für aktive Rolle des AWM Conjoint Simulation A. Hein 21 Conjoint Simulation : Kombination von AWM und FRM ✏ Beispiel : Fehlerinjektion in Prozessoren eines Multiprozessorsystems FRM AWM pok tinj pinj tdet pdet tic tip prec prep trec trep Transitionen: Bestimmung der Gewichte und/oder Prioritäten im AWM Bestimmung des Feuerzeitpunktes im AWM Conjoint Simulation A. Hein 22 Conjoint Simulation : Kombination von AWM und FRM Operationen CAi (Aktivieren der Transition ti) Transition ti Operationen CFi (Feuern der Transition ti) tinj starte Anwendungsprogramme und Fehlerer- injiziere Fehler in Prozessor des Architecture-Model kennungsmechanismen (Workload-Model) (Auswirkung auf Workload-Model : Stop von Prozessen des Workload-Model) tdet warte auf Erkennung des Prozessorfehlers im unterbreche Ausführung des Workload-Model; AWM (bestimme Fehlerlatenz) bestimme Gewichte der Transitionen tdic and tdip abhängig von der Verfügbarkeit von Spare-Prozessoren tic ∅ ∅ trec ∅ rekonfiguriere AWM tip ∅ ∅ trep ∅ repariere Architecture-Model Conjoint Simulation A. Hein 23 Conjoint Simulation : Kombination von AWM und FRM ✏ Was kann gemessen werden? ❏ ❏ Zustände des Gesamtsystems, die sich auf die Verläßlichkeit beziehen, spiegeln sich in den Markierungen des FRM wieder, z.B. ➫ Verfügbarkeit (fehlerfreier Zustand) := mittlere Anzahl von Marken in Stelle pok ➫ mittlere Fehlerlatenz := mittlere Anzahl von Marken in Stelle pinj ➫ ... Verhalten des AWM unter Einfluß des FRM ✏ Interaktionen zwischen AWM und FRM (allgemein) ❏ aktive Rolle des FRM : Kontrolle und Steuerung des AWM durch das FRM (z.B. Fehlerinjektionen, Starten und Unterbrechen des Workload-Model, etc.) ❏ aktive Rolle des AWM : Bestimmung von Gewichten und Prioritäten zeitloser Transitionen sowie von Feuerzeiten zeitbehafteter Transitionen Conjoint Simulation A. Hein 24 Conjoint Simulation : Implementierungsaspekte ✏ Verbindung zweier Simulationsmaschinen ❏ zwei Ereignislisten ❏ zwei Simulationszeiten TAWM und TFRM, die synchronisiert werden ❏ FRM : ereignis-orientiert ❏ AWM : prozeß-orientiert ✏ Verknüpfung erfolgt automatisch ❏ durch Definition der Mengen CAi und CFi von Operationen, die im FRM definiert aber im AWM ausgeführt werden ❏ Modelldesigner definiert nicht explizit die Synchronisation von TAWM und TFRM bzw. die Verwaltung der beiden Ereignislisten Conjoint Simulation A. Hein 25 Conjoint Simulation : Zusammenfassung ☞ Conjoint Simulation ❏ Aufteilung des Modells in Architecture-Workload Model (AWM) und FailureRepair Model (FRM) ❏ Kombination von objekt-orientierten und prozess-orientierten Paradigmen mit Petri Netz Modellierung ❏ design-orientierte Modelle zur Vereinfachung der Modellierung komplexer Systeme unter Berücksichtigung von Architektur, Last, und Fehler-Reparatur Verhalten ❏ Integration in die Modellierungsumgebung SimPar ☞ weitere Aspekte ❏ Repräsentation des FRM mittels Serien-Parallel-Diagrammen und Fehlerbäumen ❏ parallele Simulation des AWM (Workstation-Cluster und Multiprozessorsysteme) Conjoint Simulation A. Hein 26 Conjoint Simulation : Zusammenfassung Implementierung des Ansatzes Conjoint Simulation in der Modellierungsumgebung SimPar Modellierungsumgebung für die gemeinsame Leistungs- und Verläßlichkeitsbewertung massiv paralleler, fehlertoleranter Rechensysteme Conjoint Simulation A. Hein 27 Weitere Informationen zu ‘Conjoint Simulation’ WWW: http://faui30t.informatik.uni-erlangen.de:1200/Staff/alhein/simpar/simpar.html Dalibor, Stefan, Axel Hein, and Wolfgang Hohl. Simulation-Based Performability Evaluation of Fault-Tolerant Multiprocessors. in Proceedings of the ESM ‘95, European Simulation Multiconference, Prague (Czech Republic), June 5-7, 1995. Hein, Axel and Klaus Bänsch. SimPar - A Simulation-Based Environment for Performance and Dependability Amalysis of User-Defined Fault-Tolerant Parallel Systems. Internal Report 1/95, IMMD III, University of Erlangen-Nürnberg, 1995. Hein, Axel and David Kreische. An Environment for the Simulation of Timed-Transition Petri Nets. Internal Report 6/95, IMMD III, University of Erlangen-Nürnberg, 1995. Hein, Axel. Modeling of Fault-Tolerant Systems - A Case Study. Report R4.2.5 of the Esprit Project FTMPS 6731, IMMD III, University of Erlangen-Nürnberg, August 1995. Hein, Axel and Kumar K. Goswami. Combined Performance and Dependability Evaluation with “Conjoint Simulation”. in Proceedings of the ESS ‘95, European Simulation Symposium, Erlangen (Germany), October 26-28, 1995. Conjoint Simulation A. Hein