Seminar
Analyse von Softwarefehlern
WS 2002-2003

 

Der Pentiumbug

 
Einleitung
 
Zeitlicher Ablauf
 
SRT-Algorithmus
 
    SRT-Algorithmus allgemein
 
    SRT-Division auf dem Pentium
 
    Quotientenbitselektion auf dem Pentium
 
Analyse des Bugs
 
Kritische Bitmuster
 
Statistische Auswertung des Bugs
 
Ausblick
 
Quellen und Links

 

Einleitung        up

1994 überschwemmte Intel die Computerwelt mit einer gigantisch angelegten Werbekampagne, die von den Schlagworten "Pentium" und "intel inside" geprägt war. Ziel war es, die Marktposition weiter auszubauen und auf Dauer zu festigen. Da sich die Bezeichnung x86 nicht markenrechtlich schützen ließ, entschloss sich Intel, den Nachfolger des i486 den geschützten Namen PentiumTM zu geben. Dadurch wollte man den eigenen Prozessor klar von den Produkten der Konkurrenz abheben, was zweifellos gelang.

Aber nicht nur der Name war neu. Selbstverständlich war die Chip-Architektur im Vergleich zum Vorgänger verbessert worden. Eine Neuerung war unter anderem die Überarbeitung des Divisions-Algorithmus für Fließkommazahlen. Dieser sollte die Kompatibilität zum i486 gewährleisten, jedoch schneller sein. Konnte der i486 noch pro Takt eine Quotientenziffer bestimmen, berechnete der Pentium pro Takt zwei Quotientenstellen.

Als dann nach der Markteinführung bekannt wurde, dass der Pentium bei eben dieser FPU-Division Fehler machen konnte, wurde Intel der Bekanntheitsgrad zum Verhängnis. Die Medienlandschaft stürzte sich auf den FDIV-Bug und berichtete exzessiv. Aus "intel inside" wurde "error inside". Das Verhalten von Intel im Umgang mit dem Bug trug nicht gerade zur Besserung der Lage bei. Nachdem man den Fehler nach langem Zögern endlich zugab, startete man wiederum nach langem Zögern die kostspieligste Rücknahmeaktion in der Geschichte der Halbleiterindustrie.

  

Der folgende Text gliedert sich semantisch in drei große Abschnitte.

Der Erste enthält eine kurze Zusammenfassung und einen knappen historischen Überblick über die Entdeckung des Bugs und über die Reaktion der Öffentlichkeit.

Anschließend wird der vom Pentium verwendete SRT-Algorithmus zur Berechnung von Fließkommadivisionen genauer erklärt. Zunächst in allgemeiner Form beschrieben wird dann auf die vom Pentium verwendete spezifische Version eingegangen.

Am Ende folgt eine Analyse zur Häufigkeit mit der der Bug auftritt.

 

Auszug nach [e]

 

 

 

Zeitlicher Ablauf        up

Nach der Markteinführung des Pentiums und der damit verbundenen Werbekampagne schien alles bestens für Intel zu laufen. Doch das Bekanntwerden von Divisionsfehlern machte Intel einen großen Strich durch die Rechnung.

Intel selbst gibt an, den Bug erst im August 1994 gefunden zu haben.

Als Entdecker des Bugs außerhalb von Intel gilt Professor Thomas Nicely. Dieser war damals am Lynchburg College in Virginia tätig. Professor Nicely beschäftigte sich in seinen Forschungen vornehmlich mit Primzahlen, Primzahltupeln, Primzahltripeln und ihren mathematischen/numerischen Eigenschaften. Eines seiner Programme berechnete verschieden Summen von Primzahlen. Dabei wurden bis dahin unbekannte Reihen berechnet und zur Korrektheitsüberprüfung Zwischenergebnisse mit den Werten von schon bekannten Summen verglichen. Sein Programm lief schon über einen längeren Zeitraum auf mehreren Rechnern, meist 486er-Systemen. Im März 1994 kam auch ein Pentiumsystem dazu. Im Juni 1994 stellte er fest, dass ein vom Pentiumsystem gelieferter Wert von dem schon bekannten Wert für diese Summe abwich. Alle anderen Rechner gaben das richtige Ergebnis zurück. Trotz "double precision" waren die Ergebnisse schlechter als mit "single precision". Nicely machte sich auf die Suche nach dem Fehler. Er fand dabei auch einen Fehler im Borland C++ 4.02-Compiler und dachte zunächst, dies sei die Ursache für die falsche Berechnung. Nach und nach stellte sich aber heraus, dass der Fehler in der Rechenoperation 1/p, also der Division, lag. Am 24. Oktober wandte er sich an Intel. Diese antworteten ihm, dass ihnen der Fehler bekannt sei, sie aber keinen Lösungsvorschlag für das Problem hätten. In der neueren Revision der CPU sei der Fehler behoben. Sechs Tage später, am 30. Oktober 1994, postete Nicley seine Ergebnisse auf einem Compuserve Server und schickte auf der Suche nach einer Lösung seine Ergebnisse an Personen und Organisationen, von denen er glaubte, dass sie Zugang zu vielen Pentium-Systemen hätten. Sein Beispiel für eine fehlerhafte Division war 1/824633702441.

Dr. Timothy Coe von Vitesse Semiconductors rief die Community auf ihm weitere Beispiele des Bugs zuzuschicken, auf deren Basis er ein Model der Dividiereinheit des Pentium entwickeln konnte. Anhand dieses Models konnte man die Funktionsweise des Dividierers verstehen und den Fehler erklären. Über sein Model bestimmt er, dass auch die Berechnung des Quotienten 4195835/3145727 fehlerhaft sei. Richtig wäre 1,33382, aber der Pentium lieferte als Ergebnis 1,33374. Der relative Fehler beträgt hier 6,1 *10-5 oder 61ppm (ca. das Doppelte des verträglichen CO-Gehalts in Atemluft), was sogar in diesem Fall eine geringere Genauigkeit als "single precision" ist.

Professor Vaughan Pratt von der Universität Stanford konzentrierte seine Forschung auf das Finden von Fehlern. Er schrieb ein Programm, welches jeweils eine Division für jedes ganzzahlige Paar zwischen 1 und 1000 durchführte, also1 Million Divisionen. Dabei machte der Pentium 627 Fehler, wobei der relative Fehler bei 426 Ergebnissen zwischen 10-5 und 10-7, bei 14 Werten über 10-5 lag. Er beschrieb den Umfang selbst: "Es ist so schlimm, wie es nur sein kann, ohne bei den Leuten die Alarmglocken läuten zu lassen".

Von November 1994 an folgten immer ausführlichere Berichte in den Medien, die neben der Entrüstung der Besitzer fehlerhafter Pentium-CPUs auch einer weiteren Gruppe ein Forum bot, nämlich den Schadenfrohen, die unermüdlich Pentium-Witze nach dem Schema "You mean 2.00000000 + 2.000000000 doesn't equal 3.999998456?" produzierten.

Intel trug nicht gerade zur Entspannung der Lage bei. Man behauptete, der Fehler trete bei einem normalen Anwender nur alle 27000 Jahre einmal auf. Deswegen wollte man zunächst nur die CPUs derjenigen User kostenlos ersetzen, die nachweisen konnten, dass sie wissenschaftliche Berechnungen durchführen und auf äußerst genaue Ergebnisse angewiesen sind.

"Q: How many Pentium designers does it take to screw in a light bulb?" "A: 1.99904274017, but that's close enough for non-technical people."

Den Vorwürfen, sie wären nicht in der Lage einen funktionierenden Prozessor zu entwickeln, entgegnete Intel mit "It's a flaw not a bug", was bedeuten sollte, dass der Algorithmus grundsätzlich funktioniert und richtig arbeitet. Nur im Fertigungsprozess hatte sich ein kleiner Fehler eingeschlichen. Der von Intel verwendete SRT-Algorithmus, der im folgendem näher beschrieben wird, liest zur Berechnung des Quotienten Einträge aus einer hardware-realisierten Tabelle. Diese Tabelle hat aber bei den fehlerhaften CPUs fünf falsche Einträge.

Immer wenn einer dieser Einträge während einer Division benötigt wird, entsteht ab da ein falsches Ergebnis.

Nachdem der Druck auf Intel immer stärker wurde, entschloss man sich schließlich, jede fehlerhafte CPU durch eine fehlerbereinigte Revision zu ersetzen. Die Kosten für diese Aktion beliefen ca. 464 Millionen Dollar. Mindestens ebenso schmerzhaft war der immense Imageschaden.

 

Auszug nach [e], [f]

 

 

 

SRT-Algorithmus        up

In diesen Abschnitt wird der vom Pentium für die Division verwendete SRT-Algorithmus genauer beschrieben. Zunächst wird der Algorithmus allgemein und seine mathematischen Grundlagen erklärt. Anschließend wird auf die Umsetzung im Pentium eingegangen. Zuletzt folgt eine Beschreibung der Auswahlfunktion der Quotientenbits in der CPU. Genau die hierfür verwendete Tabelle ist für den Bug verantwortlich.

 

SRT-Division allgemein        up

Der SRT-Algorithmus ist nach den Anfangsbuchstaben seiner drei Entwickler Sweeny (IBM), Robinson (University of Illinois) und Tocher (Imperial College) benannt. 1958 führten deren unabhängige Bemühungen zur Entwicklung dieses Algorithmus für die Division. Er fand und findet eine weite Verbreitung auf verschiedensten Rechnersystemen, da er sehr flexibel ist und man ihn je nach Situation mit einer anderen Basis (r>=2) realisieren kann.

Der Algorithmus berechnet die Quotientenbits, die er für die Reihendarstellung des Ergebnisses benötigt, allein über Schätzung des partiellen Restes und Näherungswert des Divisors. Dies ermöglicht schnelle Iterationen selbst für längere Wortgrößen. Der Algorithmus erzeugt in der binären Ausführung, d.h. zur Basis r=2 pro Iteration ein Quotientenbit, wählt man die Basis r=4, so können wie im Fall des Pentium 2 Bits pro Iteration bestimmt werden.

 

Die Division

Die Division ist das Inverse der Multiplikation. Dabei ist das besondere, dass der Quotient trotz ganzzahliger Operatoren nicht ganzzahlig sein muss.

Wie man es aus der Schule kennt, berechnet man den Quotienten indem man nicht immer den gesamten Dividenten betrachtet, sondern immer den partiellen Rest, der nach jedem Schritt übrig bleibt.

Ein Beispiel zur Schulmethode: 

  45 / 16 = 2,8125
-32    
   130    
  -128    
         20    
        -16    
             40    
            -32    
                 80    
                -80    
                    0    

 Das Ergebnis lässt sich wie folgt darstellen:

  2*100 + 8*10-1 + 1*10-2 + 2*10-3 + 5*10-4 = 2,8125

Der SRT-Algorithmus arbeitet nach einem ähnlichen Prinzip. Nur die Auswahl der Quotientenbits wird anders bewerkstelligt.

 

Im folgendem gelten folgende Abkürzungen:

p

Dividend

d

Divisor

q

Quotient

r

Basis

R

Rest

Die Division lässt sich hiermit so beschreiben:

  p = q*d + R, wobei R<r

Das Verfahren gilt auch für negative Operatoren. Dies sieht man leicht wenn man sich die Beziehungen (-y)/x = y/(-x) = -(y/x) und (-y)/(-x)=y/x vergegenwärtigt, so dass der Algorithmus letztlich nur die Beträge der Zahlen dividieren muss, das Vorzeichen des Ergebnisses ist das EXOR der Vorzeichen der beiden Operanden.

 

Der SRT-Algorithmus

Das SRT-Verfahren ist eine Kombination aus einem Non-Restoring Divisions-Algorithmus und einer Ziffernauswahlfunktion. Non-Restoring-Verfahren akzeptieren bei der Berechnung negative Werte des Restes, die durch die Subtraktion von zu großen Divisorvielfachen entstehen. Im nächsten Schritt wird dies dann korrigiert. Restoring-Verfahren führen im Gegensatz dazu zuerst eine Probesubtraktion durch. Fällt diese negativ aus, springen sie einen Schritt zurück, d.h. sie stellen das alte Ergebnis wieder her ("restore"). Die Ziffernauswahlfunktion bestimmt in jedem Iterationsschritt eine Ziffer, das Quotientenbit, aus einer gegebenen Ziffernmenge. Dies erfolgt nach einer festgelegten Strategie, die je nach Umsetzung des Verfahrens anders aussehen kann.

Die Ziffernmenge setzt sich in der Regel folgendermaßen zusammen:

Es gilt: 2a + 1 >= r (Kardinalität der Trägermenge damit größer als notwendig)

Die Symmetrie der Ziffernmenge ist eine Anforderung des Non-Restoring-Verfahrens, die Redundanz der Ziffernmenge ermöglicht die Erzeugung mehrerer (binärer) Quotientenbits pro Rechenschritt.

 

SRT-Algorithmus: (Nach Wiland Schmale)

Der Algorithmus erzeugt eine Reihendarstellung des Quotienten, die beliebige Länge haben kann. Bei unendlicher Laufzeit ergibt sich damit eine exakte Darstellung des Ergebnisses. Wenn unendliche Laufzeit aber akzeptabel wäre, müsste man sich fast keine Gedanken um den Algorithmen-Entwurf machen. In der Realisierung auf dem Rechner muss daher die Laufzeit durch Vorgabe einer maximalen Schrittzahl begrenzt werden, das Ergebnis ist folglich eine Näherung des wahren Quotienten.

Eingabe: r, a, p, d und die Schrittanzahl N

Die folgende Bedingung sei erfüllt: (1)

Wenn (1) nicht gilt, gibt es eine Potenz rg, so dass (1) mit drg statt d gilt ("Shift um g Stellen nach links").

p0 := p

für k = 0, 1, ... N:

Bestimme in Abhängigkeit von pk und d eine Ziffer    derart, dass mit

         pk+1 := r (pk - qkd)    (2)

gilt:

       

Ausgabe: Näherungswert für

 

 

Zur leichteren Nachvollziehbarkeit, hier eine kurze Ausführung zu den Bedingungen (1) und (2):

Zu Bedingung (1):

(Darstellung von Gleitpunktzahl zur Basis r)

Daraus folgt:

                      

bzw.

                      

Bedingung (2) wird einsichtiger, wenn man nun

                     

betrachtet.

Darauf aufbauend, erkennt man, dass folgende Gleichung gelten muss:

                    

 

 

Beweis

Es wird nun indirekt über zwei Behauptungen der Beweis geführt, dass die SRT-Division funktioniert. Die Beweise der beiden Behauptungen sind wiederum so aufgebaut, dass klar wird, wie die Quotientenberechnung nach SRT funktioniert.

Im Laufe des Beweises wird neben der Gültigkeit der SRT-Berechnungsmethode auch ersichtlich, dass
eine Darstellung   besitzt. Und es wird gezeigt, dass der Fehler nach N Schritten  ist.

 

Hiermit und mit der unten eingeführten Behauptung (4) sieht man, dass

                                

gelten muss, was das Vorkommen dieser Ungleichung im Algorithmus einsichtiger macht.

Grundvoraussetzung ist, dass gilt, somit lauten die Behauptungen:

 

(a) Wenn (vgl. (1)), dann gibt es in der Form, so dass (2) gilt

(b) Es gilt:

                   (3)

                  

      was sich leicht umformen läßt zu:

                   (4)

                  

      und:

                   (5)
                    und  

 

 

Beweis der Behauptungen:

Zu a)

Im ersten Schritt der Berechnung ist man bemüht den Wert pk kleiner als   zu halten, denn nur so gilt:

                                   

Hierzu setzt man den gesamten Intervallbereich auf  
(Iop bezeichnet das gesamte Intervall in dem der Algorithmus operiert).

 

Man sieht nun leicht, dass beim "Ziel"-Intervall    die Länge beträgt.

 

Unter Berücksichtigung der Voraussetzung   erkennt man, dass diese Länge >= d ist.

 

Ebenfalls gut zu sehen ist, dass  

 

Dies kann man umformen zu:  

Damit ist gezeigt, dass es ein   geben muss, für das die Ungleichung
erfüllt ist, darüber hinaus wissen wir damit, dass auch    gilt.

 

Etwas anschaulicher gesprochen, kann man sagen, dass man jeden Wert pk, sofern er im "operativen" Intervallbereich liegt, über ein geeignetes qk aus der Ziffernmenge auf das "Ziel"-Intervall abbilden kann.

 

zu b)

Jetzt wird gezeigt, dass der Quotient über die vom SRT-Verfahren benutzte Reihendarstellung dargestellt werden kann.

Man betrachtet nun:

           

und kann mit (3), (4) schreiben:

           

Bedingung (5) liefert unmittelbar die Konvergenz.

 

  

Näherungswert für den Quotienten:

q0 + ...qN*r-1 für , dessen Fehler man mit abschätzen kann.

 

Auszug nach [g]

 

 

 

SRT-Division auf dem Pentium        up

Die Umsetzung der SRT-Division erfolgt im Pentium zur Basis r = 4. Man spricht deshalb von Radix 4 SRT Division.
Der Wert für a ist auf 2 gesetzt, so dass sich für die Quotientenbits folgende symmetrische Ziffernmenge
ergibt. Diese hat gegenüber einer Ziffernmenge wie etwa {0; 1; 2; 3} den Vorteil, dass sie aus lauter Zweier-Potenzen
mit Vorzeichen besteht. Rein hardwaretechnisch lässt sich eine Multiplikation mit 2 wesentlich leichter durchführen als
etwa mit 3. Dies und die Redundanz, aufgrund von , tragen zur hohen Geschwindigkeit der SRT-Division bei.
Außerdem bringt die so gewählte Ziffernmenge bei der Verwendung der in den meisten Computersystemen benutzten
Carry-Save-Addition Vorteile mit sich.

 

Der SRT-Divisions-Algorithmus wurde bereits in allgemeiner Form eingeführt, dennoch soll der Algorithmus mit r = 4 und a = 2 in einem Pseudocode festgehalten werden:

 

Radix 4 SRT Division

p0 := p

für k = 0, 1, ... N

Bestimme in Abhängigkeit von pk und d eine Ziffer qk aus { -2, -1, 0, 1, 2 } so dass mit

pk+1 := 4(pk - qkd)

gilt:

|pk+1| <= 8/3 d

Ausgabe: Näherungswert für

                       

Man kann aus |pk+1| <= 8/3 d leicht schließen, dass einer der fünf Wert von pk - qkd den Wert |2/3 d| nicht überschreitet oder zumindest gleich ist.

 

 

Die Skizze zeigt das Intervall , dieses ist noch in fünf Subintervalle unterteilt. Die Subintervalle ergeben
sich aus den Werten der möglichen Wahl einer Ziffer qk . Liegt nun p in einem dieser Teilintervalle, dann muss man
nur noch die Bezeichnung herauslesen und hat ein qk bestimmt. Mit dem ablesbaren Wert von qk kann jedes Sub-Intervall
in das mit qk = 0 bezeichnete Intervall überführt werden.
In Bereichen, in denen sich zwei Intervalle überlappen, ergeben sich zwei zulässige Ziffern für qk, um das Intervall in qk = 0
zu überführen.
Dieses Transformieren auf das Intervall qk = 0 ist notwendig, denn nur hier kann man problemlos mit "4" multiplizieren,
ohne die Bedingung |pk| <= 8/3 d zu verletzen.
Da dies in jedem Iterationsschritt gilt, weiß man, dass |pk+1| <= 8/3 d für beliebige qk (für alle k=0, ... N).

 

 

Als nächstes müsste man wieder zeigen, dass der Quotient die Darstellung

besitzt.

 

Dies für konkrete Werte nachzuweisen ist im Prinzip identisch mit den allgemeinen Ausführungen im obigen Abschnitt, weswegen auf diesen verwiesen wird.

Erwähnenswert scheint, dass infolge der Intervallüberlappungen die Darstellung des Quotienten nicht eindeutig bestimmt ist. Der Wert des Quotienten ist natürlich eindeutig bestimmt, jede Berechnung führt zum selben Ergebnis, nur kann die geometrische Reihe andere Gestalt besitzen.

Ein weit verbreitetes Missverständnissen die erwähnte Redundanz der Ziffernmenge betreffend ist, dass diese wie im Bereich der Codierungslehre der Fehlerkorrektur dient. Dies ist nicht der Fall, denn obwohl es manchmal zwei gültige Zifferauswahlmöglichkeiten gibt, wird der Algorithmus bei einer einmal falsch getroffenen Wahl nicht mehr auf den richtigen Quotienten-Wert ermitteln können.

 

Auszug nach [b], [c]

 

 

 

Quotientenbitselektion auf dem Pentium        up

Zunächst wird hier erklärt, wie die Ziffernauswahl beim Pentium erfolgt. Diese ist ja für den Bug verantwortlich. Im Anschluss daran wird dann noch einmal ein Pseudocode für die SRT-Division im Pentium angegeben, diesmal mit Verwendung der "look-up-table" und der Carry-Save-Addition.

 

Eine effiziente Implementierung des SRT-Algorithmus kann durch geschicktes Wählen von qk erreicht werden, die
Auswahl obliegt der Ziffernauswahlfunktion. Diese bestimmt aus der endlichen Ziffernmenge
in jedem k-ten Schritt eine Ziffer.

 

Die Auswahl kann nach mehreren Strategien erfolgen. Eine relativ einfache wäre, wenn man beispielsweise stets das Minimum von Zk wählt. Allerdings ist dies sicherlich nicht die effizienteste Funktion, so dass in der Praxis i.d.R. kompliziertere Auswahlfunktionen Verwendung finden.

Zudem müssen diese Auswahl-Algorithmen möglichst effizient auf der Hardware umgesetzt werden, was dann wie im Falle des Pentiums mittels einer hardware-realisierten Tabelle, genannt "look-up-table" implementiert wird.

Eben bei der Umsetzung des Designs dieser "look-up-table" des Pentium auf die fertigungstechnische Ebene trat jener Fehler auf, der den uns bekannten Pentium-Bug verursachte.

Diese Tabelle besteht aus 1066 Einträgen, bei fünf Werten wurde "0" anstelle von "2" eingetragen, so dass, falls auf einen dieser fünf Einträge zugegriffen wird, ein falsches Ergebnis für die Division ermittelt wird. Intel erklärte in seinem offiziellen "White Paper", dass es einen Fehler im Skript gab, welches den konzeptionellen Entwurf auf die Hardwareebene übertragen sollte. Es wurden schlichtweg besagte fünf Einträge vergessen und dann mit 0 belegt. Dass man sich heute eine ungefähre Vorstellung von der beim Pentium eingesetzten Look-Up-Tabelle machen kann, muss man Timothy Coe anrechnen. Er rekonstruierte den größten Teil dieser Tabelle, was nur möglich war, weil es den Fehler gab. Ohne den Bug wäre es unmöglich, die von Intel verwendete Tabelle ohne Kenntnis des Entwurfs nachzubilden.

Bei dieser "look-up-table" handelt es sich, wie der Name schon sagt, um eine zweidimensionale Tabelle. Eine Dimension wird mit D (=Divisior) bezeichnet, wobei D eine binäre Zahl mit der Darstellung x.yyyy ist, was anschaulich ein ganzzahliges (integer) Vielfaches von 1/16 ist und zu d wie folgt festgelegt wird:

D <= d < D+ = D + 1/16

Etwas weniger formell beschrieben heißt das, dass die Tabelle in Zellen mit 1/16 Abstand eingeteilt ist.

Die zweite Dimension bestimmt der "geshiftete partielle Rest" Pk, der dann die binäre Form xxxx.yyy - was in diesem Fall das ganzzahlige Vielfache von 1/8 ist - hat. Die Beziehung zu pk lässt sich wie folgt ausdrücken:

Pk <= pk < Pk + 1/4

Im Gegensatz zu D und D+ ist Pk nicht eindeutig festgelegt, sondern lediglich auf zwei Möglichkeiten eingeschränkt. Dies steht im Zusammenhang damit, dass der Pentium - wie die Mehrheit der Prozessoren - im Carry-Save Format rechnet und die tatsächliche Wahl von Pk von der Belegung des Carry- und Sum-Words abhängt.

Das heißt, dass qk auf Grund eines geschätzten Wertes Pk bestimmt wird, wobei letztlich aber pk+1 mit hoher Genauigkeit errechnet wird.

Die unten stehende Grafik zeigt eine solche PD-Tabelle, die qk in Abhängigkeit von Pk und D bestimmt.

 

Die fünf Farben repräsentieren die fünf Ziffern +2, +1, 0, -1, -2 (von oben nach unten). Die fehlerhaften Einträge, d.h. diejenigen, die irrtümlich "0" anstelle der "2" enthalten, findet man oberen Ende der Tabelle und sind mit Explosionssymbolen markiert. Leere, weiße Zellen enthalten jeweils einen der zwei gültigen Werte für qk, deren Inhalt aber nicht eindeutig bestimmbar ist. Mit Coe's Modell kann man nur verlässliche Aussagen über die Zelleninhalte der fünf Spalten machen, die die fehlerhaften Einträge beinhalten. Die weißen Zellen oberhalb und unterhalb der Beschränkungen +2, -2 sollten von einem korrekt funktionierenden Pentium nicht erreicht werden, so dass deren Inhalt belanglos ist.

Die fünf falschen Einträge treten für die Divisoren d auf, bei denen D einen der fünf Werte
besitzt. Pro durchgeführt Division nimmt D jeweils einen festen Wert an, d.h. in der Tabelle wird eine Spalte gewählt. Die
fehlerhaften Spalten lassen sich mathematisch so ausdrücken, dass man sie erreicht, wenn  ein ganzzahliges
Vielfaches von ist.

 

Coe und Tang zufolge existiert ein fehlerhafter Eintrag in einer der fünf Spalten beim Wert  

 

Formal lassen sich die Belegungsbereiche für die einzelnen Quotientenziffern auch über Angaben von oberen und unteren Schranken charakterisieren. Es ergibt sich mit Pminq <= P <= Pmaxq folgende Tabelle:

q

-2

-1

 0

 1

 2

 

 

Carry-Save-Addition

Wie bereits angedeutet wird Pk unter Ausnutzung der Besonderheiten der Carry-Save Addition bestimmt. Unter Einbeziehung dieser Addition in den SRT-Divsions-Algorithmus, erhält man ein vollständigeres Bild der Realisation der Division beim Pentium. Um die Vertrautheit mit der Carry-Save-Addition nicht uneingeschränkt vorauszusetzen, soll im Folgenden ein kurzer Überblick gegeben werden.

Aus der Schulzeit weiß man, dass x1 + x2 = x3 , also die Summe zweier Zahlen unter Berücksichtigung der Überträge eine neue Zahl ist. Beim Pentium wird diese Übertragsberücksichtigung, auch als "carry propagation" bezeichnet, vermieden.

Damit besitzt x1 + x2 die Darstellung s2 + c2 .

Dabei wird si mit "sum word" bezeichnet, während ci das "carry word" ist. Der Grundgedanke ist hierbei, wenn beispielsweise s2 + c2 + x3 in binärer Darstellung berechnet wird, sich jede Spalte zu 0, 1, 2 oder 3 aufaddiert und letztlich die Summe modulo 2 im sum word gespeichert wird und die carry bits im carry word.

 

Beispiel:      x1  0 1 1 0 1
                     x2  0 1 1 1 1
                     s2  0 0 0 1 0
                     c2  1 1 0 1 0
                     x3  0 0 1 1 0
                     s3  1 1 1 1 0
                     c3  0 0 1 0 0

 

Beim Pentium besitzt pk nun besagte "Carry Save"-Darstellung, so dass die Berechnung von pk+1 = pk - qkd  mittels eines Carry-Save Addierers erfolgt. Diese auch als "full adder" bezeichneten Addierer berechnen aus drei Eingaben die zwei Ausgabewerte ck + sk.

Bei positiven qk wird  - qkd  im 1-Komplement von  qkd  dargestellt. Der Vorteil dieses Vorgehens liegt dabei, dass im Gegensatz zum 2-Komplement dies in einem Schritt stattfinden kann: es wird einfach das bitweise-Komplement von qkd gebildet und dann im entstehenden carry word das letzte Bit, das sonst immer "0" ist, zu "1" modifiziert.

Der Vorteil bei diesem Vorgehen ist, dass die Berechnung durch eine Kombination von Shiftoperationen, 1-Komplementbildung oder Nullierung erfolgen kann, die alle auf dem Prozessor durch direkte Hardwarerealisierung in einem Takt durchgeführt werden können.

Aus der Darstellung von pk = ck + sk folgt natürlich Pk = Ck + Sk

wobei gilt Ck <= ck < Ck + 1/8  und Sk <= sk < Sk + 1/8

Daraus ergibt sich nun, dass wie oben erwähnt nur gilt: Pk <= pk + ¼

 

 

Mit diesem Wissen kann man den bereits bekannten SRT-Algorithmus nochmals etwas spezifischer aufschreiben:

 

Radix 4 SRT Division mit Carry Save Addition Pentium Style

 

S0 := p0, C0 := 0

 

für k = 0, 1, ... N

           

            qk := Auslesen des Tabelleneintrags unter (Pk, D)

 

            berechne (-qkd) über shiften, nullsetzen, und/oder 1-Komplementbildung;

            ck+1 + sk+1 := 4(ck + sk + (- qkd))  (Carry-Save Addition)

                                   evtl. Korrektur des 1-Komplements durch Einfügen von 1 an der niederwertigsten Stelle in ck+1, falls qk >0

 

Ausgabe:

             

 

Für einen Iterationsschritt müssen bei weiten nicht alle Bit der prozessorinternen Gleitpunktdarstellung von p, d beachtet werden, qk kann schon durch die Betrachtung der ersten 8 signifikanten Bit bestimmt werden. Durch die Verwendung von Näherungswerten und die Optimierung des Algorithmus dahingehend, dass er Rechenoperationen verwendet, die auf der Hardware schnell realisiert werden können, ist die SRT-Division so leistungsoptimiert. Nicht zuletzt spielt hier die Wahl der Basis r = 4 und der symmetrischen Ziffernmenge eine nicht unerhebliche Rolle, da diese eine effiziente Hardware-Umsetzung ermöglichen.  Wählt man r größer, so kann der Dividierer mehr Quotientenbits in einem Iterationsschritt bestimmen, allerdings steigt hierbei der Aufwand für die Quotienten-Auswahlfunktion und die Berechnung des Restes pk+1 für den folgenden Schritt so an, dass es in einer vergleichweise höheren Laufzeit resultieren kann. Ein bekanntes Beispiel für Radix 8 - SRT ist Suns UltraSparc.

 

 

Beispiel: 1.875 / 1

                 1.875 =  0001.111 00000000000
                                0000.000 00000000000
                   -2*1 =  1101.111 11111111111
                                0000.011 11111111100
                                1111.000 00000000100
                 -(-1)*1=  0001.000 00000000000
                                1001.111 11111100000
                                1000.000 00000100000
                   -2*1 =   1101.111 11111111111
                                0000.000 00011111100
                                1111.111 11100000100
                   -0*1 =   0000.000 00000000000
                                1111.111 11111100000
                                0000.000 00000100000
                                0000.000 00000000000
                                1111.111 11100000000
                                0000.000 00100000000

                                1.875 = 2 - 1/4 + 2/16 + 0/32 + ....

 

Auszug nach [b]

 

 

 

Analyse des Bugs        up

An die oben erwähnten Grundlagen der SRT-Division im Pentium schließt sich nun eine kurze Analyse des eigentlichen Bugs bzw. der Entstehung eines fehlerbehafteten Ergebnisses an. Man sollte sich vor Augen führen, dass der Algorithmus im Pentium durchaus meist richtig rechnt, dies aber von den Eingabeoperanden abhängt.

Hierzu führten Coe/Tang ausführliche Untersuchungen, um dann festzustellen, dass das Erreichen eines fehlerhaften Eintrags der PD-Tabelle ein relativ diffiziles Unterfangen ist.

 

Aus der Struktur der Tabelle läßt sich zeigen, dass die fehlerhaften Einträge PBad der PD-Tabelle nur von den Einträgen direkt unterhalb erreicht werden können. Diese Einträge direkt unterhalb der fünf fehlerhaften Stellen, als "foothold" bezeichnet, sind eine notwendige, aber nicht hinreichende Bedingung einen PBad zu erreichen. Entgegen der intuitiven Vermutung, dass jeder Eintrag der Tabelle mit ähnlicher Wahrscheinlichkeit erreicht werden könne, gibt es Einträge, die einander bedingen.

 

Wie oben bereits erklärt, ist die P-Dimension der "look-up-table" in 1/8 Schritten unterteil, so dass sich für den Wert des Foothold unterhalb eines fehlerhaften Eintrags

ergibt.

 

Insgesamt gibt es vier Möglichkeiten einen Foothold zu erreichen:

  • vom oberen Ende der q = -2 Region kommend
  • vom oberen Ende der q = -1 Region kommend
  • vom Foothold selbst
  • vom Eintrag direkt unterhalb des Footholds

 

Es soll hier noch einmal hervorgehoben werden, dass die fehlerhaften Einträge nur über die Footholds erreicht werden können, und diese wiederum nur auf die vier genannten Arten, wobei letztere beiden nachweislich nicht im nächsten Schritt auf einen fehlerhaften Eintrag führt. damit gibt es genau zwei zulässige Fehlerentstehungswege.

Um diese Feststellungen nachvollziehen zu können, muss man das Modell des Pentium weiter konkretisieren und betrachtet hierzu die Definition von D+.

Es gibt mit qk { -2, -1, 0, 1, 2 } fünf mögliche Werte für qkD+:

Anmerkung: die negativen Zahlen werden in 2-Komplement Darstellung angegeben – wobei d’x die Schreibweise für die komplementären Bitstellen ist.

 

Da hier nur die ersten acht signifikanten Stellen betrachtet werden, werden die Zahlen abgerundet, wobei die Bildung von D+ eigentlich mit dem Aufrunden vergleichbar ist - wenn man von der Addition der Brüche 1/8 und 1/16 absieht.

 

Abermals kann man die iterative Gleichung des SRT-Algorithmus erweitern und erhält somit letztlich die Version, die tatsächlich vom Pentium berechnet wird:

Pk+1 = 4(Pk - qkD+) + Rk

Der Wert von Rk wird durch einige wenige höherwertige Bits wie folgt bestimmt:

 

In der Formel stehen si, ci, di für die entsprechenden Bitstellen im Summen- und Carry-Word und Divisor. Die Funktion carry-
over (b1,b2,b3) nimmt "1" an, wenn zwei ihrer Argumente mit "1" belegt sind. Die Korrektur-Terme -1/2 und -1/4 bei q = -2, -1
sind darauf zurückzuführen, dass Pk+1 über D+ ausgedrückt wird und nicht wie bisher über D. Bei den positiven Quotientenziffern
q = 1,2 entfallen die Korrekturen aufgrund des dadurch entstanden Fehlers, dass anstelle von für den Wert von
-D verwendet wird.

 

Nimmt man den größtmöglichen Wert der Parameter an, so ergibt sich

 

Im Folgendem gilt die Annahme, dass D+ ein Vielfaches von 3/16 ist, d.h. es wird eine der fünf Spalten, die einen fehlerhaften Eintrag enthalten, betrachtet.

Zu jedem möglichen qk und einigen ausgewählten extremalen Pk lassen sich mit Hilfe der obigen Gleichungen die maximal erreichbaren Pk+1 in einer Tabelle angeben. Hiermit kann veranschaulicht, wie hoch man bei bekanntem qk in der Tabelle kommen kann, wie schwer es also letztlich ist, einen fehlerhaften Eintrag zu erreichen.

 

 Falls Pk

 , dann Pk+1

 Foothold  erreichbar ?

qk

Pk

 

-2

 

 

ja

-1

 

 

ja

0

 

 

nein

1

 

 

nein

 

 Falls Pk

 , dann Pk+1

Fehlerhafter Eintrag erreichbar?

2

 

 

ja

2

 

 

nein

 

Die Ursache für die zwei "kleiner gleich" Operatoren besteht darin, dass D+ > 1 ist.

Es lässt sich eine Folge von P's und entsprechenden q's, die zum fehlerhaften Eintrag führen, feststellen:

Der Index m in der mittleren Spalte gibt die Zahl der Wiederholungen des Eintrags an, also m >= 1 -mal. Die erste Spalte besagt, dass der Weg in Abhängigkeit von q= -2, -1 bei Pmax-2 oder Pmax-1 begonnen werden kann.

 

Auszug nach [b]

 

 

 

Kritische Bitmuster        up

Es folgen nun einige Überlegungen zu möglichen bzw. für das Erreichen eines Fehlers notwendigen Bitmustern des Divisors sowie des Summen- und Carry-Words. Coe und Tang haben über Untersuchung aller in Frage kommender Bitmuster festgestellt, dass beim Divisor zusätzlich d5 = d6 = d7 = d8 = d9 = d10 = 1 sein müssen, um im Falle eines der oben gezeigten kritischen Divisoren überhaupt einen Fehler zu erzeugen.

Dies wurde beim obigen Fehlerentstehungsweg zunächst einmal für den Fall m = 1 gezeigt. Für den Fall m > 1 stellte sich anschließend heraus, dass dieser nicht eintreten kann, wenn ein fehlerhafter Eintrag erreicht wird, womit folgt, dass m = 1 der einzig gültige Fall ist.

Alan Edelman vergleicht den Beweis mit einem Logikspiel das "Send More Money" heißt. In diesem Spiel muss man den Buchstaben mehrerer Wörter Ziffern zuordnen und versuchen eine korrekte Addition zu bekommen. Ein Beispiel hierfür ist SEND (9567) + MORE (1085) = MONEY (10652). Ähnliches muss im Falle der Bitmusterbestimmung gelingen, das heißt, für Platzhalter müssen Werte ermittelt werden, um ein Ergebnis zu bekommen, das man eigentlich schon kennt.

Aus der Rückwärtsfolgerung der bekannten Werte für qk beim Entstehen eines Fehlers und der Bitbelegung im Falle des Bug läßt sich nachstehende Tabelle erschließen:

 Erläuterungen zur Beschriftung:

Wegen R = Rmax muss gelten c4,c5,s4,s5,d5,d6 = 1
Arithmetische Folgerung von oben
Carry-Bit von oben bzw. 8(PBad -1/8) ist gerade
Bitweises Komplement des oberen Divisors
Es muss gelten: R = Rmax - 3/8
Arithmetische Folgerung von unten
Arithmetische Folgerung von oben
8PBad = 3 (mod 4)
Zeile darüber erfordert Carry-Bit
Komplent des entsprechenden Divisorbits der obersten Addition
0 ist arithmetisches Resultat von oben; 1 folgt, da 8PBad = 3 (mod 4)

Die Erläuterungen beziehen sich auf den Fall q= -2, gelten prinzipiell aber in analoger Argumentation für q= -1.

Aus dieser Musteranalyse lässt sich schlussfolgern, dass im Falle q= -1 die Divisorbits 5 bis 8 '1' sein müssen, während für q= -2 die Bits 5 bis 9 mit '1' belegt sein müssen. Verfolgt man solche Belegungsstrategien mit dieser Vorgabe noch einen Schritt weiter zurück, ergibt sich in vergleichbarer Weise, dass auch die Divisorbits 9 und 10 auf jeden Fall '1' enthalten müssen.

Die kritischen Bitmuster für einen Bug sind damit eindeutig festgelegt, und nur bei ihrem Auftreten im Divisor und dem Divisionsrest kann der Bug überhaupt eine Wirkung erzielen, andere Bitmuster bleiben ungefährlich, d.h. es wird ein korrektes Ergebnis ermittelt.

Nicht weiter eingegangen wird auf den Beweis, dass auf dem Weg zum Bug vom oberen Ende der q= -2/q= -1 Region der q= 2 Bereich nur ein einziges Mal, und zwar mit dem Foothold, berührt wird, dass also das m aus dem vorigen Abschnitt 1 sein muss. Der Beweis besteht wieder aus der Konstruktion von möglichen Bitmusterbelegungen unter der Annahme, dass m>1 gilt, also q= 2 mehrfach auftritt. Diese Annahmen lassen kein Bitmuster zu, sondern führen in einen Widerspruch, wie der interessierte Leser selbst versuchen kann nachzuprüfen.

Abschließend lässt sich ebenfalls aus den vorkommenden Bitmuster noch zeigen, warum der absolute Fehler, der durch den Bug erzeugt werden kann, etwa durch 5*10-5 beschränkt bleibt. Eine weitere Besonderheit des Divisionsfehlers ist nämlich, dass die ersten acht Bit des Quotienten immer richtig berechnet werden, egal ob ein kritisches Bitmuster vorliegt oder nicht. Dies läst sich aus den vorhergegangenen Betrachtungen folgern:  

Ausgehend von der Annahme, dass der Bug im 8-ten Schritt auftritt, weiß man dann, dass im 6-ten Schritt das sum, carry und qk wie im unten abgebildeten Diagramm belegt sein müssen. Betrachtet werden diese Werte vom vierten Bit von links an. Die Darstellung wird durch die Tatsache einfacher, dass im ersten Schritt, d.h. ohne Berechnungen kein Übertrag auftreten konnte und so das Carry-Word noch leer, sprich alle Stellen '0' sind. Ein wenig abstrahiert kann man sagen, dass das Bitbelegungsschema einer Wellenbewegung von oben nach unten ähnelt. In jedem Fall muss aber q1 unabhängig von den Operanden positiv sein, was den Schluss ermöglicht, dass die Bits q2, ..., q6 aufgrund der Überschneidungen der qkd-Zeile von einem Iterationsschritt zum nächsten alle positiv bleiben. Im Widerspruch zu dieser Feststellung steht aber, dass man weiß, dass im Falle des Bugs q6 < 0 ist. Dies erlaubt die Schlussfolgerung, dass das Bitmuster, das in dem Diagramm in der 6. Zeile steht und der "Auslöser" für den Bug ist, nicht vor dem siebten Schritt und deswegen der Bug nicht vor dem 9. Schritt auftreten kann.

Da die Bits q0 bis q7 damit stets korrekt sind, kann der Fehler frühestens an der vierten dezimalen Nachkommastelle in genannter Größenordnung auftreten.

 

 1.Schritt: .
0
.
  .  .  .  .  .  .  .  .  .  .  .  .  .  . 1 1 1 1 1
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  .  .  .  .  .  .  .  .  .  .  .  .  .  . 1 1 1 1 1
 2.Schritt: .
0
.
  .  .  .  .  .  .  .  .  .  .  . 1 0 0 0 0 0  .  .
  .  .  .  .  .  .  .  .  .  .  . 1 1 1 1 1  .  .  .
  .  .  .  .  .  .  .  .  .  .  . 1 1 1 1 1  .  .  .
 3.Schritt: .
0
.
  .  .  .  .  .  .  .  . 1 0 0 0 0 0  .  .  .  .  .
  .  .  .  .  .  .  .  . 1 1 1 1 1  .  .  .  .  .  .
  .  .  .  .  .  .  .  . 1 1 1 1 1  .  .  .  .  .  .
 4.Schritt: .
0
.
  .  .  .  .  . 1 0 0 0 0 0  .  .  .  .  .  .  .  .
  .  .  .  .  . 1 1 1 1 1  .  .  .  .  .  .  .  .  .
  .  .  .  .  . 1 1 1 1 1  .  .  .  .  .  .  .  .  .
 5.Schritt: .
0
.
  .  . 1 0 0 0 0 0  .  .  .  .  .  .  .  .  .  .  .
  .  . 1 1 1 1 1  .  .  .  .  .  .  .  .  .  .  .  .
  .  . 1 1 1 1 1  .  .  .  .  .  .  .  .  .  .  .  .
 6.Schritt: 1
1
.
 1 1 1 1  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 1 1 1 1  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 1 1 1 1  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
   Bit #4  

 

Auszug nach [b], [c], [d]

 

 

 

Statistische Auswertung des Bugs        up

Zum Abschluss der Ausführungen folgt eine kurze statistische Analyse des Bugs bzw. vornehmlich eine Betrachtung deren Ergebnisse. Es wurden von vielen Seiten Untersuchungen geführt, um den Fehler auf seine Häufigkeit hin zu untersuchen. Das breite Einsatzfeld der Pentium-CPUs, aber auch - wie oben beschrieben wurde - die große Spezifität der Bug-auslösenden Operanden führt zu recht verschiedenen Ergebnissen, eben je nachdem in welchem Feld die ausführlicheren Test gemacht wurden. So ist es nicht von der Hand zu weisen, dass extreme User, wie Prof. Nicely viel öfter mit einem fehlerhaften Ergebnis zu tun haben werden, als ein User, der nur gelegentlich mit seinem Rechner arbeitet und dabei kaum mathematischen Berechnungen vornimmt. Nicely wurde von Steven Smith, einen der Ingeneuren des Pentiums, als "...the most extreme user." bezeichnet, der rund um die Uhr nur extrem genaue mathematische Berechnung durchführe. Alle anderen Benutzertypen würde der Bug eigentlich gar nicht wirklich betreffen, wenn man Intels statistischer Auswertung Glauben schenken würde. Der durchschnittliche User würde bei Grafikprogrammen wie PRINT SHOP oder ADOBE ACROBAT VIEWER und bei Spielen alle 270 Jahre vom Bug betroffen, bei Tabellenkalkulationsprogrammen wie EXCEL oder LOTUS 123 alle 27000 Jahre und bei Textverarbeitungen wie WORD eigentlich nie. Deswegen sträubte man sich auch lange gegen den generellen Austausch aller fehlerhaften CPUs. Laut IBM andererseits soll der Fehler dagegen einmal 28 Tage auftreten. Dies liegt sicher daran, welche statistische Untersuchungsart man zugrunde liegt. Intel geht von zufällig verteilten Datensätzen bei 15 min CPU-Nutzungszeit pro Tag aus, während IBM als Grundlage eine FDIV-Operation alle 1000 Rechentakte annimmt. Welcher Wert der Wahrheit näher kommt, kann hier nicht endgültig gesagt werden. Festzuhalten bleibt nur, dass die Fehlerwahrscheinlichkeit mit zunehmender numerischer Anforderung an den Prozessor und mit abnehmender Gleichverteilung der Operanden korreliert. Nähere Informationen zur statistischen Auswertung findet man in Intels White Paper.

 

Auszug nach [a], [e], [f]

 

 

 

Ausblick        up

Es gab und gibt in der Computergeschichte durchaus ähnliche Fehler in Hardwarebausteinen. Aber keiner schlug auch nur annähernd so hohe Wellen wie Intels Pentium-Bug. Dies liegt sicher zum einen am Bekanntheitsgrad von Intel, der aggressiven Webekampagne, der Verbreitung des Pentiums und natürlich auch am Umgang von Intel mit dem Bug. Das Verheimlichen und Aussitzen des Problems, der Umgang mit den Kunden, als es um das Ersetzen der fehlerhaften Chips ging, all dies trug zum Imageverlust des Unternehmens bei. Es wäre wahrscheinlich besser gewesen, wenn man in den sauren Apfel gebissen hätte und sofort an die Öffentlichkeit gegangen wäre. Auch dann wäre man die "Lachnummer" der Branche gewesen, aber die Verärgerung der Kunden wäre wahrscheinlich geringer ausgefallen.

Niemand ist vor Fehlern gefeit und bei der Komplexität von Hardwarebausteinen kann es immer wieder zu Fehlern kommen, die man nicht durch Tests findet. Am Beispiel des Pentium-Bugs sieht man, was kleine Fehler, fünf falsche Einträge in einer Tabelle, bewirkt durch eine fehlerhafte Übertragung auf die Hardwareebene, für Konsequenzen nach sich ziehen können. Und im Umgang mit diesem Fehler machte Intel sicher keine gute Figur.

 

 

 

Quellen und Links        up

Quellen

[a] Vaughan Pratt, Anatomy of the Pentium Bug

[b] Alan Edelman, The Mathematics of the Pentium Division Bug

[c] Anthony Caola, 18.337 Parallel Scientific Computing, Lecture 3, The Pentium Bug

[d] Tim Coe und Ping Tak Peter Tang, It Takes Six Ones To Reach a Flaw

[e] Ray Valdes, Pentium Crosses the Great Divide

[f] Intel, White Paper

[g] Wiland Schmale, SRT-Division

 

Links

http://www.intel.com/procs/support/pentium/fdiv/

 

Folien zum Vortrag (ZIP-File)

 

 

 

 
Boris Ljepoja                                                                                                                                                                      ljepoja@in.tum.de          
Thomas Pfennig                                                                                                                                                                 pfennig@in.tum.de
Stefan Rosenegger                                                                                                                                                             rosenegg@in.tum.de