-
HINTERGRUND DER ERFINDUNG
-
1. Bereich der Erfindung
-
Diese Erfindung bezieht sich auf
Fehlerkorrektur und genauer gesagt auf Fehlercodes, die Bitfehler
in einem Computer-Speichersystem korrigieren.
-
2. Beschreibung der relevanten
Technik
-
Fehlercodes werden gemeinhin in elektronischen
Systemen verwendet, um Datenfehler wie Übertragungsfehler oder Speicherfehler
zu entdecken und/oder zu korrigieren. Zum Beispiel können Fehlercodes
verwendet werden, um Fehler innerhalb von Daten, die über eine
Telefonleitung, einen Funksender oder einen Compact-Disc-Laser übertragen wurden,
zu entdecken und zu korrigieren. Eine andere gebräuchliche
Verwendung von Fehlercodes ist es, Fehler innerhalb von Daten, die
in einem Speicher eines Computersystems gespeichert sind, zu entdecken
und zu korrigieren. Zum Beispiel können Fehlerkorrekturbits oder
Prüfbits
für Daten
erzeugt werden, bevor sie in einer oder mehreren Speichereinrichtungen
gespeichert werden. Wenn die Daten aus der Speichereinrichtung gelesen
werden, können
die Prüfbits
verwendet werden, um Fehler innerhalb der Daten zu entdecken und
zu korrigieren. Fehler können
entweder durch fehlerhafte Komponenten oder durch Rauschen bzw.
Störspannungen
bzw. -ströme
innerhalb des Computersystems eingeschleppt werden. Fehlerhafte
Komponenten können fehlerhafte
Speichereinrichtungen oder fehlerhafte Datenpfade zwischen Einrichtungen
bzw. Geräten
innerhalb des Computersystems wie fehlerhafte Anschlußstifte
bzw. Kontakte umfassen.
-
Hamming-Codes sind ein gemeinhin
verwendeter Fehlercode. Die Prüfbits
in einem Hamming-Code sind Paritätsbits
für Abschnitte
der Datenbits. Jedes Prüfbit
liefert die Parität
für eine
eindeutige bzw. einzigartige Teilmenge der Datenbits. Wenn ein Fehler
auftritt, d. h. ein oder mehrere Bits ihren Zustand ändern, werden
ein oder mehrere Syndrombits gesetzt (unter der Annahme, daß der Fehler
in der von dem Code abgedeckten Klasse von Fehlern liegt). Allgemein
gesprochen werden Syndrombits erzeugt, indem die Prüfbits neu
erzeugt werden und die neu erzeugten Prüfbits mit den ursprünglichen
Prüfbits
verglichen werden. Wenn die neu erzeugten Prüfbits von den ursprünglichen
Prüfbits
abweichen, ist ein Fehler aufgetreten und ein oder mehrere Syndrombits
werden gesetzt. Welche Syndrombits gesetzt werden, kann auch dazu
verwendet werden zu bestimmen, welches Datenbit seinen Zustand ändert, und
die Korrektur des Fehlers zu ermöglichen.
Wenn zum Beispiel ein Datenbit seinen Zustand ändert, wird dieses Datenbit
ein oder mehrere Prüfbits ändern. Weil
jedes Datenbit zu einer eindeutigen Gruppe von Prüfbits beiträgt, identifizieren
die Prüfbits,
die geändert
wurden, das Datenbit, das seinen Zustand geändert hat. Der Fehler kann
korrigiert werden, indem das als fehlerhaft identifizierte Bit invertiert
wird.
-
Eine allgemein gebräuchliche
Verwendung von Hamming-Codes ist es, Einzelbitfehler innerhalb einer
Gruppe von Daten zu korrigieren. Allgemein gesprochen muß die Anzahl
von Prüfbits
groß genug sein,
so daß 2k–1 größer oder
gleich n ist, wobei k die Anzahl von Prüfbits und n die Anzahl von
Datenbits plus die Anzahl von Prüfbits
ist. Dementsprechend werden sieben Prüfbits benötigt, um einen Einzelfehler
korrigierenden Hamming-Code für
einen 64-Bit Datenblock zu implementieren. Ein Einzelfehler korrigierender
Hamming-Code ist in der Lage, einen einzelnen Fehler zu erkennen
und zu korrigieren. Die Fähigkeit
zur Fehlererkennung des Codes kann durch Hinzufügen eines zusätzlichen
Prüfbits
erhöht werden.
Die Verwendung eines zusätzlichen
Prüfbits ermöglicht es,
daß der
Hamming-Code doppelte Bitfehler erkennt und einzelne Bitfehler korrigiert.
Das Hinzufügen
eines Bits zur Erhöhung
der Fähigkeit
eines Hamming-Codes zur Fehlererkennung wird als erweiterter Hamming-Code
bezeichnet.
-
In einem Einzelfehler-Korrekturcode
wie einem Hamming-Code können
mehrfache Bitfehler dazu führen,
daß ein
oder mehrere Syndrome nicht-Null sind. Mehrfache Bitfehler können jedoch irrtümlich als
ein Einzelbitfehler an einer anderen Bitposition erscheinen. Zum
Beispiel kann in einem Einzelfehler korrigierenden Hamming-Code
mit sechs Prüfbits
ein Bitfehler dazu führen,
daß zwei
Prüfbits ihren
Zustand ändern.
Ein anderer Bitfehler kann dazu führen, daß zwei andere Prüfbits ihren
Zustand ändern.
Dementsprechend ändern
vier Prüfbits
den Zustand, wenn diese zwei Fehler auftreten. Unglücklicherweise
kann ein Einbitfehler in noch einer anderen Bitposition dazu führen, daß dieselben
vier Prüfbits
den Zustand ändern.
Die Prozedur zur Fehlerkorrektur geht womöglich von der Annahme aus,
daß das
Bit, welches alle vier Prüfbits
beeinflußt,
seinen Zustand geändert
hat und invertiert das Datenbit. Wenn die Änderungen der Prüfbits tatsächlich durch zwei
Bitfehler verursacht wurden, hat die Prozedur zur Fehlerkorrektur
ein nicht fehlerhaftes Bit invertiert. Dementsprechend hat die Prozedur
zur Fehlerkorrektur mehr Fehler erzeugt und kann irrtümlich anzeigen,
daß die
Daten fehlerfrei sind.
-
Das Hinzufügen eines erweiterten Paritätsbits löst dieses
Problem. Wenn die Daten aus dem Speicher gelesen werden, werden
die Prüfbits
und das erweiterte Paritätsbit
neu erzeugt und mit den ursprünglichen
Prüfbits
und dem erweiterten Paritätsbit verglichen.
Wenn die neu erzeugten Prüfbits
von den ursprünglichen
Prüfbits
verschieden sind, kann das erweiterte Paritätsbit verwendet werden, um
festzustellen, ob ein oder zwei Bitfehler aufgetreten sind. Wenn
ein Fehler auftritt, wird das neu erzeugte erweiterte Paritätsbit von
dem ursprünglichen
erweiterten Paritätsbit
abweichen. Wenn zwei Fehler auftreten, wird das neu erzeugte erweiterte
Paritätsbit
dasselbe sein wie das ursprüngliche
erweiterte Paritätsbit. Wenn
ein oder mehrere Prüfbits
den Zustand ändern und
das neu erzeugte erweiterte Paritätsbit verschieden ist, ist
ein einzelner Bitfehler aufgetreten und wird korrigiert. Alternativ
werden in dem Fall, daß ein
oder mehrere Prüfbits
den Zustand ändern
und das erweiterte Paritätsbit
dasselbe ist, zwei Bitfehler entdeckt und es wird keine Korrektur
durchgeführt.
In letzterem Fall kann ein nicht korrigierbarer Fehler an eine Speichersteuerung
oder eine andere Komponente innerhalb des Computersystems gemeldet
werden. Es wird darauf hingewiesen, daß mehr als zwei Bitfehler in
einer logischen Gruppe nicht innerhalb der Klasse von Fehlern liegen,
mit der sich der Fehlerkorrekturcode befaßt. Dementsprechend können drei
oder mehr Fehler unerkannt bleiben oder der Fehlerkorrekturcode
kann die Fehler als einen Einzelbitfehler interpretieren und ein
Datenbit invertieren, das nicht fehlerhaft war.
-
Die Paritätsprüfung ist eine gemeinhin verwendete
Technik zur Fehlererkennung. Ein Paritätsbit oder ein Prüfbit wird
zu einer Gruppe von Datenbits hinzugefügt. Das Prüfbit kann abhängig von
der Anzahl von gesetzten Datenbits innerhalb der Gruppe von Datenbits
gesetzt werden. Wenn gerade Parität verwendet wird, wird das
Paritätsbit
die Gesamtzahl von gesetzten Bits einschließlich der Datenbits und des
Prüfbits
gleich einer geraden Zahl machen. Wenn ungerade Parität verwendet
wird, wird das Paritätsbit
die Gesamtzahl von gesetzten Bits einschließlich der Datenbits und des
Prüfbits
gleich einer ungeraden Zahl machen. Die Paritätsprüfung ist wirksam zum Entdecken
einer ungeraden Anzahl von Fehlern. Wenn eine gerade Anzahl von
Fehlern auftritt, erkennt jedoch die Paritätsprüfung den Fehler nicht.
-
Eine verbreitete Verwendung von Fehlercodes
besteht darin, Bitfehler von Daten, die in einem Cachespeicher eines
Computerspeichersystems gespeichert sind, zu entdecken und zu korrigieren.
Allgemein gesprochen ist ein Cachespeicher ein Puffer zwischen einem
Prozessor und relativ langsamen Speichereinrichtungen. Der Cachespeicher
ist typischerweise kleiner und schneller als der Hauptspeicher und
speichert Daten, auf die unlängst
vom Prozessor zugegriffen wurde. Wegen der repetitiven Natur von
Computerprogrammen ist es wahrscheinlicher, daß der Prozessor auf Information,
auf die vor kurzem zugegriffen wurde, zugreift, als daß er auf
andere Information im Speicher zugreift. Dementsprechend kann durch
das Speichern der unlängst
verwendeten Daten in dem schnelleren Cachespeicher die durchschnittliche
Zugriffszeit auf Daten verringert werden. Das Verringern der Zugriffszeit
auf Daten verringert die Zeit, in der der Prozessor auf Daten aus dem
Speicher wartet, was die Gesamtgeschwindigkeit des Prozessors steigert.
-
In 1 werden
Teile eines Computersystems gezeigt, das einen Cachespeicher implementiert.
Das Computersystem 100 beinhaltet den Prozessor 102,
den Cachespeicher 104, die Speichersteuerung 106 und
den Systemspeicher 108. Andere Teile des Computersystems 100 sind
der Einfachheit halber weggelassen. Der Prozessor 102 ist
mit dem Cachespeicher 104 verbunden. Der Cachespeicher 104 ist
mit der Speichersteuerung 106 verbunden, die ihrerseits
mit dem Systemspeicher 108 verbunden ist. Es wird darauf
hingewiesen, daß das
Computersystem von 1 nur
der Veranschaulichung dient. Man kann sich auch andere Konfigurationen
eines Prozessors, eines Cachespeichers und eines Systemspeichers
vorstellen.
-
Der Prozessor 102 fordert
Daten aus dem Systemspeicher 108 durch das Einleiten einer
Speicherleseanforderung auf dem Prozessorbus 110 an. Der
Cachespeicher 104 empfängt
die Speicherleseanforderung und stellt fest, ob die angeforderten
Daten im Cache gespeichert sind. Wenn die angeforderten Daten im
Cache gespeichert sind, liefert der Cachespeicher 104 die
Daten an den Prozessor 102. Alternativ leitet der Cachespeicher 104 eine
Speicherleseanforderung an die Speichersteuerung 106 ein, um
die Daten zu lesen, wenn die angeforderten Daten nicht im Cache
gespeichert sind. Nach einer Ausführungsform greift die Speichersteuerung 106 auf die
Daten aus dem Systemspeicher 108 zu und speichert die Daten
im Cachespeicher 104, der seinerseits die Daten an den
Prozessor 102 liefert. Alternativ können die Daten von der Speichersteuerung 106 parallel
zum Speichern der Daten im Cachespeicher 104 an den Prozessor 102 übermittelt
werden. Wenn der Prozessor 102 im Cachespeicher 104 gespeicherte
Daten überschreibt,
können
verschiedene Techniken zum Erhalt der Kohärenz implementiert werden.
Zum Beispiel können
die Daten sowohl in den Cachespeicher 104 als auch in den
Speicher 108 geschrieben werden, oder die Daten können im
Cachespeicher 104 ungültig
gemacht werden und nur in den Speicher 108 geschrieben
werden. Die vorstehend beschriebene Operation des Computersystems 100 dient
nur zu Zwecken der Veranschaulichung und ist nicht dazu gedacht,
den Schutzbereich der Ansprüche
einzuschränken.
-
Es ist ein verbreitetes Entwurfsziel
für Computersysteme,
die Anzahl von Prüfbits
zu reduzieren, die verwendet werden, um Fehler zu erkennen und zu
korrigieren. Die Prüfbits
erhöhen
die Menge von Daten, die vom System behandelt werden, was die Anzahl
von Speicherkomponenten, Datenpfaden und anderen Schaltungen bzw.
Schaltkreisen anwachsen lassen kann. Darüber hinaus erhöht die erhöhte Anzahl
von Bits die Wahrscheinlichkeit eines Fehlers. Obwohl die Prüfbits einen
Fehler feststellbar und/oder korrigierbar machen, erhöht die Steigerung der
Anzahl von Datenbits innerhalb des Systems die Wahrscheinlichkeit,
daß ein
Fehler auftritt. Aus zumindest diesen Gründen ist es wünschenswert,
die Anzahl von Prüfbits
für ein
gegebenes Niveau von Fehlererkennung und/oder -korrektur zu vermindern.
-
Fahad Alzahrani und Tom Chen offenbaren in "On-Chip TEC-QED ECC
for Ultra-large, single-chip memory systems" (Seiten 132–137 in Proceedings of the
International Conference on Computer Design: "VLSI in Computers and Processors", Los Alamitos, USA,
1994) einen Entwurf, der auf einem SEC-DED-Code mit Ungerader-Gewicht-Spalte
bzw. Odd-Weight-Column SEC-DED-Code
in Verbindung mit einer Paritätstechnik.
-
ZUSAMMENFASSUNG DER ERFINDUNG
-
Spezielle und bevorzugte Aspekte
der Erfindung sind in den anhängenden
unabhängigen
und abhängigen
Patentansprüchen
dargelegt.
-
Die vorliegende Erfindung reduziert
die Anzahl der Prüfbits,
die benötigt
werden, um Fehler in einem Datenblock zu korrigieren, der eine Mehrzahl von
Unterblöcken
enthält.
Jeder Unterblock enthält ein
Unterblock-Prüfbit,
das verwendet werden kann, um das Vorliegen eines Bitfehlers innerhalb
des Unterblocks zu erkennen. Ein zusammengesetzter Unterblock wird
erzeugt, der das spaltenweise exklusive Oder der Bits jedes Unterblocks
darstellt. Mit anderen Worten ist ein erstes Bit des zusammengesetzten Unterblocks
das exklusive Oder aller Bits in einer ersten Spaltenposition des
Unterblocks. Das zweite Bit des zusammengesetzten Unterblocks ist
das exklusive Oder aller Bits in einer zweiten Spaltenposition des
Unterblocks, etc. Nach einer Ausführungsform wird der zusammengesetzte
Unterblock nicht gespeichert, sondern vielmehr nur für Berechnungszwecke verwendet.
Eine Mehrzahl von zusammengesetzten Prüfbits wird erzeugt, um eine
Bitposition eines Fehlers innerhalb des zusammengesetzten Unterblocks zu
entdecken. Wenn ein Bitfehler innerhalb des Datenblocks auftritt,
können
die Unterblock-Prüfbits
verwendet werden, um zu erkennen, in welchem Unterblock der Fehler
auftrat. Die zusammengesetzten Prüfbits können verwendet werden, um festzustellen, welche
Bitposition des zusammengesetzten Unterblocks fehlerhaft ist. Die
fehlerhafte Bitposition des zusammengesetzten Unterblocks kennzeichnet
auch die Bitposition des fehlerhaften Bits in dem Unterblock, der
durch die Unterblock-Prüfbits
gekennzeichnet ist. Dementsprechend können der Unterblock und die
Bitposition innerhalb des Unterblocks durch das Verwenden der Unterblock-Prüfbits und der
zusammengesetzten Prüfbits
erkannt werden.
-
Allgemein gesprochen betrachtet die
vorliegende Erfindung ein Verfahren zur Korrektur eines Bitfehlers
in einem Datenblock, das folgendes umfaßt: Aufteilen des Datenblocks
in eine Mehrzahl von Unterblöcken,
wobei jeder Unterblock eine Mehrzahl von Bitpositionen beinhaltet;
Erzeugen eines ersten Unterblock-Prüfbits für einen ersten Unterblock,
wobei das erste Unterblock-Prüfbit
dafür eingerichtet
ist, einen Fehler in dem ersten Unterblock zu erkennen; Erzeugen
eines zusammengesetzten Unterblocks, wobei jedes Bit des zusammengesetzten
Unterblocks einer Bitposition in der Mehrzahl der Unterblöcke entspricht;
Erzeugen von zusammengesetzten Prüfbits für den zusammengesetzten Unterblock,
wobei die zusammengesetzten Prüfbits
dafür eingerichtet
sind, einen Bitfehler in dem zusammengesetzten Unterblock zu erkennen
und zu lokalisieren; Erkennen eines fehlerhaften Bits in dem ersten
Unterblock unter Verwendung des ersten Unterblock-Prüfbits und
Bestimmen einer Bitposition des fehlerhaften Bits unter Verwendung
der zusammengesetzten Prüfbits;
und Invertieren des fehlerhaften Bits.
-
Die vorliegende Erfindung betrachtet
ferner einen Computerspeicher, der einen Bitfehler in einem Datenblock
korrigiert. Der Computerspeicher enthält eine oder mehrere Speichereinrichtungen
und einen Fehlerkorrekturschaltkreis, der mit der einen oder den
mehreren Speichereinrichtungen gekoppelt ist. Die eine oder mehreren
Speichereinrichtungen sind dafür
eingerichtet, eine Mehrzahl von Unterblöcken des Datenblocks zu speichern.
Jeder der Unterblöcke
enthält
eine Mehrzahl von Bitpositionen. Der Fehlerkorrekturschaltkreis
ist dafür
eingerichtet, den Datenblock zu empfangen, die Unterblock-Prüfbits für jeden
der Unterblöcke
zu erzeugen, einen zusammengesetzten Unterblock zu erzeugen und
zusammengesetzte Prüfbits
zu erzeugen, um eine Bitposition eines fehlerhaften Bits innerhalb
des zusammengesetzten Unterblocks zu entdecken. Die Unterblock-Prüfbits und
die zusammengesetzten Prüfbits werden
in der einen oder den mehreren Speichereinrichtungen gespeichert.
Wenn ein Datenblock mit einem fehlerhaften Bit aus der einen oder
den mehreren Speichereinrichtungen gelesen wird, verwendet der Fehlerkorrekturschaltkreis
die Unterblock-Prüfbits, um
einen Unterblock zu bestimmen, der das fehlerhafte Bit enthält, und
die zusammengesetzten Prüfbits,
um eine Bitposition des fehlerhaften Bits innerhalb des Unterblocks
zu bestimmen, der das fehlerhafte Bit enthält.
-
Die vorliegende Erfindung betrachtet
darüber
hinaus einen Cachespeicher, der einen Bitfehler in einem Datenblock
korrigiert. Der Cachespeicher enthält eine oder mehrere Speichereinrichtungen und
einen Fehlerkorrekturschaltkreis, der mit der einen oder den mehreren
Speichereinrichtungen gekoppelt ist. Die eine oder mehreren Speichereinrichtungen
sind dafür
eingerichtet, eine Mehrzahl von Unterblöcken des Datenblocks zu speichern.
Jeder der Unterblöcke
enthält
eine Mehrzahl von Bitpositionen. Der Fehlerkorrekturschaltkreis
ist dafür
eingerichtet, den Datenblock zu empfangen, Unterblock-Prüfbits für jeden
der Unterblöcke
zu erzeugen, einen zusammengesetzten Unterblock zu erzeugen und
zusammengesetzte Prüfbits
zu erzeugen, um eine Bitposition eines fehlerhaften Bits innerhalb
des zusammengesetzten Unterblocks zu entdecken. Die Unterblock-Prüfbit und
die zusammengesetzten Prüfbits
werden in der einen oder den mehreren Speichereinrichtungen gespeichert.
Wenn ein Datenblock mit einem fehlerhaften Bit aus der einen oder
den mehreren Speichereinrichtungen gelesen wird, verwendet der Fehlerkorrekturschaltkreis
die Unterblock-Prüfbits,
um einen Unterblock zu bestimmen, der das fehlerhafte Bit enthält, und
die zusammengesetzten Prüfbits,
um eine Bitposition des fehlerhaften Bits innerhalb des Unterblocks
zu bestimmen, der das fehlerhafte Bit enthält.
-
KURZBESCHREIBUNG DER ZEICHNUNGEN
-
Andere Ziele und Vorteile der Erfindung
werden beim Lesen der folgenden detaillierten Beschreibung und unter
Bezug auf die begleitenden Zeichnungen offensichtlich, von denen:
-
1 ein
Blockdiagramm eines Prozessors, eines Cachespeichers und eines Systemspeichers ist;
-
2 ein
Blockdiagramm eines Cachespeichers ist;
-
3A eine
Konfiguration eines Cacheeintrages gemäß einer Ausführungsform
der vorliegenden Erfindung darstellt;
-
3B eine
Konfiguration eines Unterblocks eines Cacheeintrages gemäß einer
Ausführungsform der
vorliegenden Erfindung darstellt;
-
3C eine
Konfiguration eines Prüfbitblocks
darstellt, der einem im Cachespeicher gespeicherten Datenblock zugeordnet
ist;
-
4 die
Organisation eines Datenblocks darstellt, der Fehlerkorrekturcodes
enthält,
um einzelne Bitfehler zu korrigieren;
-
5 eine
verbesserte Organisation eines Datenblocks darstellt, der Fehlerkorrekturcodes
enthält,
um einzelne Bitfehler gemäß einer
Ausführungsform
der vorliegenden Erfindung zu korrigieren;
-
6 ein
Flußdiagramm
eines Verfahrens zum Korrigieren einzelner Bitfehler in Cachespeichern
mit Unterblock-Paritätsbits
ist;
-
7 ein
Blockdiagramm eines Computersystems mit einem Cachespeicher und
einem Systemspeicher gemäß einer
Ausführungsform
der vorliegenden Erfindung ist.
-
Während
bei der Erfindung verschiedene Modifikationen und alternative Ausgestaltungen möglich sind,
werden spezifische Ausführungsformen
derselben als Beispiel in den Zeichnungen dargestellt und hier im
Detail beschrieben. Es sollte sich jedoch verstehen, daß die Zeichnungen
und detaillierten Beschreibungen hierzu nicht dazu gedacht sind,
die Erfindung auf die speziell offenbarten Ausführungsformen einzuschränken, sondern
die Erfindung soll im Gegenteil alle Modifikationen, Äquivalenzen
und Alternativen abdecken, die in den Schutzbereich der vorliegenden
Erfindung fallen.
-
DETAILLIERTE
BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORMEN
-
In 2 wird
ein Blockdiagramm des Cachespeichers 104 gemäß einer
Ausführungsform
der vorliegenden Erfindung gezeigt. In der dargestellten Ausführungsform
enthält
der Cachespeicher 104 die Speichereinheit 202,
die Fehlerkorrektureinheit 206 und die Cachesteuerung 208.
Andere Teile des Cachespeichers 104 wurden der Einfachheit
halber weggelassen. Die Speichereinheit 202 beinhaltet eine
Mehrzahl von Einträgen 204A–204X.
Auf Komponenten, die durch eine Referenznummer gefolgt von einem
Buchstaben bezeichnet sind, kann gemeinsam durch die Referenznummer
allein Bezug genommen werden. Zum Beispiel kann auf die Cacheeinträge 204A–204X als
Cacheeinträge 204 Bezug
genommen werden. Allgemein gesprochen ist die Cachesteuerung 208 dafür eingerichtet,
Speicherzugriffsanforderungen vom Prozessor 102 zu empfangen
und festzustellen, ob die angeforderten Daten in der Speichereinheit 202 vorliegen.
Wenn der Speicherzugriff eine Leseanforderung ist und die angeforderten
Daten in der Speichereinheit 202 gespeichert sind, sendet
die Cachesteuerung 208 Steuersignale an die Speichereinheit 202,
um die angeforderten Daten auszugeben. Die angeforderten Daten werden
der Fehlerkorrektureinheit 206 übergeben, die einen oder mehrere
Bitfehler in den Daten erkennt und korrigiert. Alternativ ist die
Cachesteuerung 208 dafür
eingerichtet, eine Anforderung der Daten an die Speichersteuerung 106 zu
senden, wenn die angeforderten Daten in der Speichereinheit 202 nicht
vorliegen. Wenn die Daten empfangen werden, werden die Daten der
Fehlerkorrektureinheit 206 übergeben, die eine Mehrzahl
von Prüfbits
erzeugt, die mit den Daten in der Speichereinheit 202 gespeichert
werden. Wenn alle Einträge
aktuell belegt sind, verwendet die Cachesteuerung 208 einen von
mehreren herkömmlichen
Algorithmen, um festzulegen, welchen Eintrag die neuen Daten überschreiben.
Zum Beispiel kann die Cachesteuerung 208 den am längsten nicht
verwendeten Eintrag der Speichereinheit 202 überschreiben.
-
Wenn der Speicherzugriff eine Schreibanforderung
ist und die angeforderten Daten in der Speichereinheit 202 gespeichert
sind, können
verschiedene herkömmliche
Techniken zum Erhalten der Kohärenz
zwischen dem Cache 104 und dem Speicher 108 implementiert
sein. Zum Beispiel können
die Daten sowohl in den Cache 104 als auch in den Speicher 108 geschrieben
werden, oder die Daten im Cache 104 können ungültig gemacht werden und nur
in den Speicher 108 geschrieben werden.
-
Es wird darauf hingewiesen, daß der Cache 104 direkt
abgebildet oder bereichsassoziativ gesetzt sein kann. Nach einer
bestimmten Ausführungsform speichert
die Speichereinheit 202 64-Byte-Cachezellen bzw. -lines. Jede Cachezelle
enthält
zwei Einträge
von je 32 Bytes. Nach einer bestimmten Ausführungsform kann auf die Daten
durch Lesen oder Schreiben eines 32-Byte-Eintrages oder durch Ein-Byte-Schreiben
zugegriffen werden. Nach einer Ausführungsform enthält jeder
Eintrag 32 Bytes von Daten (oder 256 Bits von Daten) und
41 Prüfbits. Dementsprechend
enthält
jeder Eintrag 297 Bits.
-
In 3A wird
eine Konfiguration eines Cacheeintrages gemäß einer Ausführungsform
der vorliegenden Erfindung gezeigt. In der dargestellten Ausführungsform
enthält
der Cacheeintrag 204A 32 Unterblöcke (S[0:31]) und einen Prüfbitblock
(CB). Jeder Unterblock speichert eine Mehr zahl von Datenbits und
ein oder mehrere Prüfbits,
die verwendet werden können,
um Fehler innerhalb des Unterblocks zu erkennen. Der Prüfbitblock
enthält
eine Mehrzahl von Prüfbits,
die verwendet werden, um Bitfehler innerhalb des Eintrages 204A zu
erkennen und zu korrigieren.
-
In 3B wird
eine Konfiguration eines Unterblocks eines Cacheeintrages gemäß einer
Ausführungsform
der vorliegenden Erfindung gezeigt. In der dargestellten Ausführungsform
enthält
ein Unterblock (S[x]) acht Bits von Daten (D[x][0:7]) und ein Unterblock-Prüfbit (C[x]).
Nach einer bestimmten Ausführungsform
ist das Unterblock-Prüfbit
ein Paritätsbit
der acht Datenbits. Das Unterblock-Prüfbit kann verwendet werden,
um einen Bitfehler innerhalb der Datenbits zu erkennen. Wie vorstehend
diskutiert kann das Unterblock-Prüfbit durch die Fehlerkorrektureinheit 206 vor
dem Speichern von Daten in den Eintrag 204A erzeugt werden.
-
In 3C wird
eine Konfiguration eines Prüfbitblocks
eines Cacheeintrages gezeigt. In der dargestellten Ausführungsform
enthält
der Prüfbitblock neun
Prüfbits
für den
Eintrag (CB[0:8]). Nach einer bestimmten Ausführungsform implementieren die neun
Prüfbits
für den
Eintrag einen Einzelfehler korrigierenden Hamming-Code für die 256
Datenbits und 32 Prüfbits
in dem Eintrag. Dementsprechend können die Prüfbits für den Eintrag verwendet werden, um
das fehlerhafte Bit zu lokalisieren und zu korrigieren, wenn die
Unterblock-Prüfbits
einen Fehler in dem Datenblock entdecken.
-
Nach einer Ausführungsform wird, wenn ein Einzelbyte
gelesen wird, das dem gelesenen Unterblock entsprechende Unterblock-Prüfbit geprüft, um festzustellen,
ob der Unterblock irgendwelche Bitfehler enthält. Wenn keine Bitfehler entdeckt
werden, werden die Daten des Unterblocks verwendet. Alternativ werden
in dem Fall, daß ein
Bitfehler entdeckt wird, dann die Daten aus jedem Unterblock in
dem Eintrag gelesen, und die Unterblock-Prüfbits werden verwendet, um
andere Bitfehler zu entdecken. Wenn mehrfache Bitfehler entdeckt
werden, dann wird ein nicht korrigierbarer Fehler gemeldet. Wenn
nur ein Bitfehler entdeckt wird, dann werden die Prüfbits für den Eintrag
neu berechnet und mit den gespeicherten Prüfbits für den Eintrag verglichen, um
die Bitposition des fehlerhaften Bits zu bestimmen.
-
Wenn ein Eintrag gelesen wird, werden
die Unterblock-Prüfbits
der Bytes des Eintrages geprüft. Wenn
keine Bitfehler entdeckt werden, werden die Daten ohne Korrektur
verwendet. Wenn mehrfache Bitfehler entdeckt werden, wird ein nicht
korrigierbarer Fehler gemeldet. Wenn ein Bitfehler entdeckt wird,
werden die Prüfbits
für den
Eintrag verwendet, um den Bitfehler zu korrigieren. In der vorstehenden Art
und Weise können
fehlerfreie Daten aus dem Cache gelesen werden, ohne die Prüfbits für den Eintrag
zu verwenden, um die Fehlerfreiheit der Daten zu überprüfen. Wenn
ein fehlerhaftes Bit entdeckt wird, können jedoch die Prüfbits für den Eintrag
verwendet werden, um das fehlerhafte Bit zu korrigieren.
-
Während
einer Ein-Byte-Schreiboperation werden alle Unterblöcke des
Eintrages gelesen, und die Prüfbits
werden geprüft.
Wenn keine Fehler entdeckt werden, dann werden die Daten in den
zugehörigen
Unterblock geschrieben und neue Prüfbits für den Eintrag werden erzeugt
und gespeichert. Alternativ werden in dem Fall, daß ein einzelnes
Unterblock-Prüfbit
nicht korrekt ist, die Prüfbits
für den
Eintrag neu erzeugt und mit den gespeicherten Prüfbits für den Eintrag verglichen, und
das fehlerhafte Bit wird korrigiert. Die neuen Daten werden danach
in den zugehörigen
Unterblock gespeichert, und neue Prüfbits für den Eintrag werden erzeugt
und gespeichert. Während
einer 32-Byte-Schreiboperation
werden der Unterblock und die Prüfbits
für den
Eintrag erzeugt, und die Daten und Prüfbits werden gespeichert.
-
In 4 wird
die Organisation eines Datenblocks gezeigt, der Fehlerkorrekturcodes
enthält,
um Einzelbitfehler zu korrigieren. In der dargestellten Ausführungsform
werden die Datenbits und Prüfbits des
Eintrages 204A gezeigt. Wie vorstehend diskutiert, enthält der Eintrag 204A 32
Unterblöcke (S[0:31]).
Jeder Unterblock enthält
acht Datenbits (D[x][0:7]) und ein Unterblock-Prüfbit (C[x]). Nach einer Ausführungsform
ist das Prüfbit
eines Unterblocks ein Paritätsbit
der acht Datenbits innerhalb des Unterblocks. Der Eintrag 204A enthält zusätzlich einen
Prüfbitblock
(CB). Der Prüfbitblock
enthält
eine Mehrzahl von Prüfbits
für den
Eintrag, die verwendet werden können,
um einen Bitfehler innerhalb der Datenbits des Eintrages 204A zu
entdecken und zu korrigieren. Nach einer Ausführungsform speichert der Prüfbitblock
einen Neun-Bit-Hamming-Code, der die 256 Datenbits und die 32 Prüfbits von
Eintrag 204A abdeckt.
-
In 5 wird
eine verbesserte Organisation eines Datenblocks gezeigt, der Fehlerkorrekturcodes enthält, um Einzelbitfehler
gemäß einer
Ausführungsform
der vorliegenden Erfindung zu korrigieren. In der dargestellten
Ausführungsform
enthält
der Cacheeintrag 204A 32 Unterblöcke (S[0:31]), wobei jeder
aus acht Datenbits und einem Prüfbit
besteht. Der Prüfbitblock
von 4 wurde durch einen
zusammengesetzten Prüfbitblock
(Composite Check Bit Block, CBB) ersetzt. Der zusammengesetzte Prüfbitblock
(CBB) enthält
vier zusammengesetzte Prüfbits.
Allgemein gesprochen sind die zusammengesetzten Prüfbits ein
Fehlercode, um einen Fehler innerhalb eines zusammengesetzten Unterblocks
zu lokalisieren. Der zusammengesetzte Unterblock ist ein spaltenweises
exklusives Oder des Unterblocks. Mit anderen Worten ist das erste
Bit des zusammengesetzten Unterblocks (CS[0]) das exklusive Oder des
ersten Bits von jedem Unterblock (D[x][0]). Das zweite Bit des zusammengesetzten
Unterblocks (CS[1]) ist das exklusive Oder des zweiten Bits von jedem
Unterblock (D[x][1]), etc. Dementsprechend enthält der zusammengesetzte Unterblock
in der dargestellten Ausführungsform
neun Bits. Ein Bit des zusammengesetzten Unterblocks entspricht
je einer Datenbitposition innerhalb des Unterblocks und ein Bit
entspricht der Prüfbitposition
innerhalb des Unterblocks.
-
Wenn ein Bitfehler auftritt, ändert das
Bit in dem zusammengesetzten Unterblock, das der Bitposition des
fehlerhaften Bits entspricht, seinen Zustand. Durch das Lokalisieren
des Bits, das in dem zusammengesetzten Unterblock seinen Zustand ändert, kann
die Bitposition eines fehlerhaften Bits innerhalb eines Unterblocks
lokalisiert werden. Dementsprechend können die Unterblock-Prüfbits verwendet
werden, um zu lokalisieren, welcher Unterblock ein fehlerhaftes
Datenbit enthält,
und die zusammengesetzten Prüfbits
können
verwendet werden, um die Bitposition des fehlerhaften Bits innerhalb
dieses Unterblocks zu lokalisieren.
-
Nach einer Ausführungsform sind die zusammengesetzten
Prüfbits
ein Einzelfehler korrigierender Hamming-Code für die neun Bits des zusammengesetzten
Unterblocks. In der oben beschriebenen Art und Weise kann die Anzahl
von Prüfbits
reduziert werden, die benötigten
werden, um einen Bitfehler zu lokalisieren. In der dargestellten
Ausführungsform
sind die neun Prüfbits
für den
Eintrag von 4 durch
vier zusammengesetzte Prüfbits
ersetzt. Es wird darauf hingewiesen, daß der zusammengesetzte Unterblock
nicht im Cache gespeichert wird. Der zusammengesetzte Unterblock
wird als ein Zwischenschritt beim Berechnen der zusammengesetzten
Prüfbits
verwendet, die in dem Cacheeintrag gespeichert werden.
-
Wie vorstehend diskutiert werden
nach einer Ausführungsform
die Daten in 32-Byte-Blöcken
gelesen. Dementsprechend wird, wenn Daten aus dem Cache 202 gelesen
werden, ein Eintrag, der 256 Datenbits und 36 Prüfbits enthält, an den Fehlererkennungsschaltkreis 206 übergeben.
Die Fehlerkorrektureinheit 206 verwendet die Unterblock-Prüfbits, die jedem
Unterblock zugeordnet sind, um festzustellen, ob ein Bitfehler innerhalb
dieses Unterblocks auftritt. Wenn keine Fehler innerhalb des gelesenen
Unterblocks entdeckt werden, dann werden die Daten ohne Korrektur
ausgegeben. Wenn einer der Unterblöcke einen Fehler enthält, dann
wird der zusammengesetzte Unterblock neu erzeugt, die zusammengesetzten
Prüfbits
werden neu erzeugt, und die neu erzeugten zusammengesetzten Prüfbits werden mit
den gespeicherten zusammengesetzten Prüfbits verglichen, um die Bitposition
des Fehlers innerhalb des zusammengesetzte Unterblocks zu lokalisieren. Die
Bitposition des Fehlers innerhalb des zusammengesetzten Unterblocks
entspricht der Bitposition des fehlerhaften Bits in dem Unterblock,
der das fehlerhafte Bit enthält.
Alternativ ist dann ein nicht korrigierbarer Fehler aufgetreten,
wenn ein Fehler in zwei oder mehr Unterblöcken entdeckt wird. Der nicht
korrigierbarer Fehler kann an das System gemeldet werden, oder der
Eintrag kann erneut gelesen werden.
-
Wenn eine Ein-Byte-Schreiboperation
durchgeführt
wird, werden alle gespeicherten Unterblöcke des Eintrags an die Fehlerkorrektureinheit 206 übergeben.
Die Fehlerkorrektureinheit 206 verwendet die Unterblock-Prüfbits, um
Bitfehler innerhalb des Eintrags zu entdecken. Wenn ein korrigierbarer
Fehler entdeckt wird, wird er unter Verwendung der zusammengesetzten
Prüfbits
korrigiert. Wenn keine nicht-korrigierbaren Fehler entdeckt werden,
dann wird das Byte und das zugeordnete Unterblock-Prüfbit in
den Eintrag geschrieben, und es werden neue zusammengesetzte Prüfbits erzeugt.
Es wird darauf hingewiesen, daß das
gespeicherte Byte und das Prüfbit
gelesen werden müssen,
bevor das neue Byte und das Prüfbit
gespeichert werden, um Bitfehler innerhalb des Eintrags zu entdecken
und zu korrigieren.
-
Die Tabelle 1 unten veranschaulicht
die Bits des zusammengesetzten Unterblocks (CS[0:7] und CS[P]),
die zu jedem Bit der zusammengesetzten Prüfbits (CCB[0:3]) beitragen.
Jede Zeile repräsentiert
eines von den vier zusammengesetzten Prüfbits. Jede Spalte repräsentiert
ein Bit des zusammengesetzten Unterblocks. Jedes Bit des zusammengesetzten
Unterblocks, das zu einem zusammengesetzten Prüfbit beiträgt, hat eine Eins in dem entsprechenden
Kästchen.
Zum Beispiel ist das zusammengesetzte Prüfbit drei (CCB[3]) das Paritätsbit von CS[4:7]
und CS[P]. Es wird darauf hingewiesen, daß dies äquivalent dazu ist, das exklusive
Oder der Bits in den Bitpositionen 4–7 und der Prüfbits von
allen Unterblöcken
zu nehmen.
-
-
Nach einer Ausführungsform werden Syndrombits
(S[3:0]) erzeugt, wenn die zusammengesetzten Prüfbits verwendet werden, um
eine Bitposition eines fehlerhaften Bits zu erkennen. Tabelle 2
unten veranschaulicht, welche Bits zu jedem Syndrombit beitragen.
Zum Beispiel ist S[3] das exklusive Oder der Bits CS[4:7] und CS[P]
des zusammengesetzten Unterblocks und von CCB[3]. Die Bitposition
eines Fehlers kann lokalisiert werden, indem Tabelle 2 durchsucht
wird, um die Spalte zu finden, die mit S[3:0] übereinstimmt. Die Syndrombits,
zu denen ein fehlerhaftes Bit beiträgt, stimmen mit den Syndrombits überein.
Wenn die Syndrombits mit keiner Spalte von Tabelle 2 übereinstimmen,
dann ist mehr als ein Bitfehler aufgetreten.
-
-
In 6 wird
ein Verfahren zur Korrektur von Einzelbitfehlern in Datenblöcken mit
Unterblock-Prüfbits
gemäß einer
Ausführungsform
der vorliegenden Erfindung gezeigt. In Schritt 602 wird
der Datenblock in eine Mehrzahl von Unterblöcken aufgeteilt. Jeder Unterblock
enthält
eine Mehrzahl von Bitpositionen. In Schritt 604 wird ein
Unterblock-Prüfbit
für jeden Unterblock
erzeugt. Das Unterblock-Prüfbit
kann verwendet werden, um einen Fehler innerhalb des Unterblocks
zu entdecken. Nach einer Ausführungsform ist
das Unterblock-Prüfbit
ein Paritätsbit
für die
Datenbits innerhalb des Unterblocks. In Schritt 606 wird ein
zusammengesetzter Unterblock erzeugt. Ein zusammengesetzter Unterblock
ist das spaltenweise exklusive Oder der Unterblöcke. Es wird darauf hingewiesen,
daß der
zusammengesetzte Unterblock nur Berechnungszwecken dient und nicht
mit dem Datenblock gespeichert wird.
-
In Schritt 608 werden zusammengesetzte Prüfbits für den zusammengesetzten
Unterblock erzeugt. Die zusammengesetzten Prüfbits sind ein Fehlercode für den zusammengesetzten
Unterblock. Die zusammengesetzten Prüfbits können verwendet werden, um eine
Bitposition eines Fehlers innerhalb des zusammengesetzten Unterblocks
zu entdecken und zu lokalisieren. Nach einer Ausführungsform sind
die zusammengesetzten Prüfbits
ein Einzelfehler korrigierender Hamming-Code für den zusammengesetzten Unterblock.
In Schritt 610 werden die Unterblock-Prüfbits verwendet, um einen Bitfehler
innerhalb eines Unterblocks zu entdecken. In Schritt 612 werden
die zusammengesetzten Prüfbits
verwendet, um die Bitposition des Fehlers innerhalb des zusammengesetzten
Unterblocks zu entdecken. Die Bitposition des Fehlers innerhalb
des zusammengesetzten Unterblocks zeigt die Bitposition des Fehlers in
dem Unterblock an, der das fehlerhafte Bit enthält. In Schritt 614 wird
das fehlerhafte Bit durch Invertieren desjenigen Bits korrigiert,
das durch die Unterblock-Prüfbits
und die zusammengesetzten Prüfbits identifiziert
wurde.
-
In 7 wird
ein Blockdiagramm eines Computersystems mit einem Cache und einem
Systemspeicher zur Korrektur von Einzelbitfehlern mit Unterblock-Paritätsbits gezeigt.
Das Computersystem 700 beinhaltet einen Cachespeicher 725,
einen Systemspeicher 720, einen Bus 730 und Peripherieeinrichtungen
bzw. -geräte 770 und 775.
Es sollte beachtet werden, daß das
Computersystem 700 nur als ein Beispiel gezeigt wird und
viele andere Konfigurationen betrachtet bzw. in Betracht gezogen
werden. Der Systemspeicher 720 und der Cachespeicher 725 enthalten
beide jeweils eine Speichereinheit 702, eine Steuerung 708 und
die Fehlerkorrektureinheit 706 der vorliegenden Erfindung.
Es sollte ebenso beachtet werden, daß die Cacheeinheit 725 innerhalb
des Prozessors 710 enthalten sein kann. Darüber hinaus kann
entweder der Cache oder der Systemspeicher die Fehlererkennungseinheit 706 der
vorliegenden Erfindung enthalten. Der Bus 730 ist wie abgebildet der
Einfachheit halber ein Systembus, jedoch kann das Computersystem 700 andere
Busse beinhalten. Die Befehle, die in dem Prozessor 710 ausgeführt werden,
können
Datenbewegungen zwischen dem Prozessor 710, dem Cachespeicher 725 und
dem Systemspeicher 720 und den Peripherieeinrichtungen 770 und 775 durch
den Bus 730 steuern. Darüber hinaus können Datenbewegungen
auch direkt zwischen dem Prozessor 710 und dem Cachespeicher 725 und
zwischen dem Cachespeicher 725 und dem Systemspeicher 720 ausgeführt werden.
Andere Algorithmen einschließlich
der Cachekohärenz kommen
ebenfalls in Betracht. Es sollte beachtet werden, daß die Anzahl
von Bussen, Prozessoren, Caches, Speichern und Peripherieeinrichtungen
innerhalb des Systems 700 variieren kann. Die Fehlererkennungseinheit 706 kann
auch innerhalb des Cachespeichers 725 und/oder des Systemspeichers 720 oder
außerhalb
dieser Elemente wie in dem Prozessor 710, dem Bus 730,
innerhalb einer Peripherieeinrichtung oder der Kombination solcher
Elemente des Systems enthalten sein.
-
Während
die vorliegende Erfindung unter Bezug auf bestimmte Ausführungsformen
beschrieben wurde, versteht es sich, daß die Ausführungsformen der Veranschaulichung
dienen und daß der Schutzbereich
der Erfindung dadurch nicht eingeschränkt wird. Jedwede Variation, Änderung,
Ergänzung
und Verbesserung an den beschriebenen Ausführungsformen ist möglich. Diese
Variationen, Änderungen,
Ergänzungen
und Verbesserungen können in
den Schutzbereich der Erfindung fallen.
