DE60221515T2

DE60221515T2 - Speichersystem für schleifenbeschleunigung nach wunsch

Info

Publication number: DE60221515T2
Application number: DE60221515T
Authority: DE
Inventors: Michael Los Alto SCHLANSKER; Shail A. Sunnyvale GUPTA
Original assignee: Hewlett Packard Development Co LP
Current assignee: Hewlett Packard Development Co LP
Priority date: 2001-03-23
Filing date: 2002-03-21
Publication date: 2008-01-31
Anticipated expiration: 2022-03-22
Also published as: WO2002077794A3; EP1388048A2; EP1388048B1; US20020138718A1; WO2002077794A2; JP2005509930A; DE60221515D1; US6766445B2

Description

Gebiet der Erfindung
Die vorliegende Erfindung bezieht sich auf Computerhardware und spezieller auf eine Hardwarestruktur zur Verwendung in kundenspezifischen Hardwarebeschleunigern, die verwendet werden, um Schleifen voranzutreiben.
Hintergrund der Erfindung
Computerprogramme machen häufig von „Schleifen" Gebrauch, um Daten zu verarbeiten. Eine Schleife besteht aus einem Netzwerk von Operationen, die wiederholt auf einen Strom von Eingangsdaten angewandt werden, um einen Strom von Ergebnissen zu erzeugen. Kundenschaltkreise machen ebenfalls von derartigen Schleifen Gebrauch.
Hardwareanordnungen, die entworfen sind, um die Berechnung von Schleifen zu beschleunigen, sind in Fachkreisen bekannt. Im Allgemeinen verwenden diese Hardwarestrukturen eine Mehrzahl von Funktionseinheiten, die an verschiedenen Iterationen der Schleife arbeiten, um durch Überlappen der Berechnungen einer Anzahl von Schleifen-Iterationen die Zeit zu reduzieren, die benötigt wird, um die Schleife zu berechnen. Der höchste Grad an Überlappung wird erhalten, wenn eine einzelne Funktionseinheit jeden Vorgang innerhalb des Schleifenkörpers ausführt und in jedem Taktzyklus eine neue Iteration ausgelöst wird. In diesem Fall liegt eine einfache Eins-zu-Eins-Entsprechung zwischen den Hardwarefunktionseinheiten und den Operationen innerhalb des Programmgraphs sowie eine einfache Entsprechung zwischen Datenflussrändern in dem Programmgraph und tatsächlichen Hardwaredatenwegen vor. Einfache Eins-zu-Eins-Lösungen sind sehr effizient, da sie einen minimalen Satz von Betriebsmitteln aufweisen, die alle in jedem Zyklus tätig sind.
Solche Entwürfe sind jedoch oft zu kostenintensiv. Weniger kostenintensive Entwürfe benutzen Schemata, in denen eine Mehrzahl von Funktionseinheiten verwendet wird, um überlappte Berechnungen zu liefern; jedoch löst die Gesamtheit der Funktionseinheiten nur alle Π Zyklen eine Schleifeniteration ein, wobei Π > 1 ist.
Im Allgemeinen erzeugt eine Iteration der Schleife Werte, die bei nachfolgenden Berechnungen benötigt werden, und zwar entweder in der aktuellen Iteration oder in einer nachfolgenden Iteration. Diese Werte müssen in einer bestimmten Form von Hochgeschwindigkeitsspeicher gespeichert werden, auf den alle Funktionseinheiten, die diese Werte benötigen, zugreifen können. Die Kosten dieses Speichers machen einen beträchtlichen Teil der Kosten eines Hardwareschleifenbeschleunigers aus.
Die EP 0416513 bezieht sich auf eine FIFO-Speichervorrichtung, die für digitale Kommunikationsvorrichtungen und dergleichen verwendet wird und eine Mehrzahl von D-Flipflops aufweist, die zum Speichern von Daten in Kaskade miteinander geschaltet sind; zwischen die D-Flipflops geschaltete Selektoren zum Auswählen eines Eingangsdatums oder eines zu speichernden Datums, das von dem D-Flipflop auf der vorhergehenden Stufe ausgegeben ist; und auf ein Taktsignal, ein Schreibsignal und ein Lesesignal ansprechende Steuerschaltungen zum Steuern des Speichervorgangs der D-Flipflops und des Auswahlvorgangs der Selektoren. Die Steuerschaltung speichert ein Signal, das das Vorliegen oder Fehlen von in den D-Flipflops gespeicherten Daten kennzeichnet und führt Steuerung in einer solchen Art und Weise durch, dass ein Eingangsdatum zu dem D-Flipflop auf der letzten Stufe, in den noch keine Daten geschrieben worden sind, übertragen wird, um das Datum ansprechend auf ein Schreibsignal in denselben zu schreiben, und dass Daten auf entsprechenden D-Flipflops in jedem Takt ansprechend auf ein Lesesignal gleichzeitig zu dem D-Flipflop auf der nachfolgenden Stufe geschoben werden.
Weitgehend ist es die Aufgabe der vorliegenden Erfindung, eine verbesserte Hardwarebeschleunigerarchitektur zum Beschleunigen von Schleifen bereitzustellen.
Es ist eine weitere Aufgabe der vorliegenden Erfindung, ein Hochgeschwindigkeitsspeichersystem zur Verwendung in Hardwarebeschleunigern und ähnlichem bereitzustellen.
Diese und andere Aufgaben der vorliegenden Erfindung werden den Fachleuten aus der folgenden ausführlichen Beschreibung der Erfindung und den beiliegenden Zeichnungen ersichtlich.
Zusammenfassung der Erfindung
Die vorliegende Erfindung ist eine Berechnungseinheit zur Verwendung bei Schleifenberechnungen. Die Berechnungseinheit umfasst eine Funktionseinheit, eine Mehrzahl von Phasenleitungen und ein Speicherregister. Die Berechnungseinheit ist programmiert, alle Π Zyklen eine Iteration der Schleife auszulösen. Die Funktionseinheit weist einen Ergebnisausgang zum Ausgeben eines Berechnungsergebnisses pro Zyklus auf. Es gibt eine Phasenleitung entsprechend jedem der Π Zyklen. Das Speicherregister umfasst ein linear geschaltetes Array von Schiebezellen, das eine erste Schiebezelle aufweist. Jede Schiebezelle weist ein Eingangstor, ein Ausgangstor, ein Schiebesteuertor und ein ODER-Gatter auf. Jede Schiebezelle empfängt den in der Schiebezelle zu speichernden Wert auf dem Eingangstor, wobei der gespeicherte Wert ansprechend auf ein Steuersignal auf dem Schiebesteuertor gespeichert wird. Das ODER-Gatter weist einen Ausgang, der mit dem Schiebefreigabetor verbunden ist, und einen Eingang für jeden Zyklus auf, auf dem diese Schiebezelle das Steuersignal empfangen soll, wobei dieser Eingang mit der diesem Zyklus entsprechenden Phasenleitung verbunden ist. Das Eingangstor der ersten Schiebezelle ist mit dem Ergebnisausgang verbunden. Eine Mehrzahl derartiger Berechnungseinheiten kann miteinander verbunden werden, um einen Schleifenbeschleuniger zu bilden. Der Beschleuniger umfasst eine Querverbindungsschaltung zum Koppeln mindestens eines Schiebezellenausgangs einer der Berechnungseinheiten mit einem Eingang einer Funktionseinheit einer anderen der Berechnungseinheiten in einem ausgewählten Zyklus der Π Zyklen.
Kurze Beschreibung der Zeichnungen
1 ist ein Blockdiagramm eines bekannten Hardwareschleifenbeschleunigers 10.
2 ist ein Blockdiagramm eines Hardwareschleifenbeschleunigers, der Schieberegister verwendet.
3 ist ein Blockdiagramm einer Funktionseinheitsanordnung 30 eines Hardwarebeschleunigers, die ein Speicherregister 31 gemäß der vorliegenden Erfindung verwendet.
4 ist ein Blockdiagramm eines Schleifenbeschleunigers 100, der zwei Funktionseinheitsanordnungen 101 und 102 gemäß der vorliegenden Erfindung aufweist.
5 ist ein Blockdiagramm einer Funktionseinheitsanordnung 50 eines Hardwarebeschleunigers gemäß der vorliegenden Erfindung, die ein Speicherregister 51 gemäß der vorliegenden Erfindung verwendet, die einen zusätzlichen Eingang in das Speicherregister 51 aufweist.
6 ist ein Blockdiagramm eines Ausführungsbeispiels der vorliegenden Erfindung, das einen Bus verwendet, der weniger als II Drähte aufweist.
7 veranschaulicht ein Ausführungsbeispiel der vorliegenden Erfindung, das zwei Modulo-Busse verwendet, um das Verschieben der Zellen in dem Speicherregister zu steuern.
Ausführliche Beschreibung der Erfindung
Die Art und Weise, in der die vorliegende Erfindung ihre Vorteile liefert, kann mit Bezug auf die 1, die ein Blockdiagramm eines bekannten Hardwareschleifenbeschleunigers 10 darstellt, leichter verstanden werden. Der Beschleuniger 10 umfasst eine Anzahl von Funktionseinheiten 12 und eine Registerdatei 14 zum Speichern von Ergebnissen, die in einer Iteration einer Schleife erzeugt wurden und in einer gewissen späteren Iteration der Schleife benötigt werden. Da die Funktionseinheiten in der Regel bei sehr hohen Geschwindigkeiten wirksam sind, muss auch die Registerdatei bei sehr hohen Geschwindigkeiten wirksam sein. Folglich machen die Kosten der Registerdatei einen beträchtlichen Anteil der Kosten des Schleifenbeschleunigers aus.
Ein Verfahren zum Implementieren des in 1 gezeigten Schemas ist die Verwendung einer Reihe von Schieberegistern, um die Zwischenergebnisse zu speichern. Ein Hardwareschleifenbeschleuniger, der Schieberegister einsetzt, ist in 2 bei 20 gezeigt. Bei dem Beschleuniger 20 gibt jede Funktionseinheit 22 ihre Ergebnisse an ein Schieberegister 24 aus, das aus einer Reihe von Zellen 25 gebildet ist. In jedem Zyklus wird ein neues Funktionsergebnis in die oberste Zelle des Schieberegisters geschoben, und die vorher gespeicherten Ergebnisse werden nach unten geschoben. Ein Multiplexer 26 liefert eine Einrichtung zum Auswählen eines der in dem Schieberegister gespeicherten Werte zur Verwendung durch die benachbarte Funktionseinheit. Es können zusätzliche Multiplexer aufgenommen werden, wenn die Ergebnisse von mehr als einer Funktionseinheit benötigt werden.
Die Länge der Schieberegister wird durch die Anzahl der Zyklen bestimmt, über die ein Ergebnis zur Verwendung in einer Berechnung noch benötigt wird. Wenn ein Ergebnis noch benötigt wird, wird dieses Ergebnis als „lebendig" bezeichnet. Das langlebigste Ergebnis bestimmt die Länge des Schieberegisters. Es sollte beachtet werden, dass das Schieberegister alle der nach einem lebendigen Ergebnis berechneten Ergebnisse speichern muss, selbst wenn diese Ergebnisse „tot" sind, d. h. für zukünftige Berechnungen nicht benötigt werden. Folglich benötigt diese Form eines bekannten Beschleunigers sehr große Schieberegister und Multiplexer, die die Kosten des Beschleunigers erhöhen.
Die vorliegende Erfindung sieht ein Speicherregister vor, das einem Schieberegister ähnlich ist, jedoch ohne die Beschränkungen des oben erläuterten Speicherregisters auf der Basis eines Schieberegisters aufzuweisen. Es wird jetzt Bezug genommen auf 3, die ein Blockdiagramm einer Funktionseinheitsanordnung 30 eines Hardwarebeschleunigers ist, die ein Speicherregister 31 gemäß der vorliegenden Erfindung verwendet. Das Speicherregister 31 ist aus einer Mehrzahl von Speicherzellen 33 gebildet, die ein neues Ergebnis hineinschieben, sooft sich ein Signal (SE) auf einer Schiebefreigabelinie 35 auf einem vorbestimmten Pegel befindet. Wenn SE niedrig ist, behält die Speicherzelle ihren alten Wert; wenn SE hoch ist, wird ein neuer Wert von dem Eingang der Speicherzelle gelatcht. Das SE-Signal wird durch ein ODER-Gatter 34 erzeugt, das mit einer Mehrzahl von Signallinien 37 verbunden ist, die als die Phasenbussignale bezeichnet werden. Es sei darauf hingewiesen, dass Speicherregistereinträge nicht in jedem Zyklus verschoben werden müssen. Wenn zum Beispiel das durch Funktionseinheit 32 berechnete aktuelle Ergebnis nicht bei einer zukünftigen Berechnung benötigt wird, muss das Ergebnis nicht in Speicherregister 31 geschoben werden.
Zudem können eine oder mehrere Zellen gehalten werden, während andere geschoben werden. Somit können tote Werte überschrieben werden, ohne Daten aus dem Speicherregister zu schieben. Folglich ist die Länge des Speicherregisters durch die maximale Anzahl von Ergebnissen bestimmt, die zu einer beliebigen gegebenen Zeit lebendig sind, und nicht durch die Lebenszeit des langlebigsten Ergebnisses. Folglich ist ein Speicherregister gemäß der vorliegenden Erfindung beträchtlich kleiner als ein herkömmliches Speicherregister auf der Basis eines Schieberegisters. Das Reduzieren der Anzahl von Zellen hilft auch, Zwischenverbindungskosten zu reduzieren. Wenn zwei Operanden von derselben Speicherzelle und durch dieselbe Funktionseinheit (zu bestimmten Zeitpunkten) gelesen werden, kann ein einziger Datenweg beide Datenübertragungen unterstützen, ohne dass ein Multiplexer benötigt wird.
Nach diesem Überblick über die Hardware wird die Art und Weise, in der ein Speicherregister gemäß der vorliegenden Erfindung gesteuert wird, ausführlicher beschrieben. Wie im Vorhergehenden erwähnt, besteht eine Schleife aus einem Netzwerk von Operationen innerhalb eines Schleifenkörpers, die wiederholt auf einen Strom von Eingangsdaten angewandt werden, um einen Strom von Ergebnissen zu erzeugen. Der Auslösungsintervall zwischen der Ausführung von Iterationen benachbarter Schleifen innerhalb von Funktionseinheiten in einem kundenspezifischen Beschleuniger ist durch Π bezeichnet. Ein Π von 1 entspricht einer Ausführungsrate, die, nach einem Initialisierungszeitraum, die Berechnung eines Schleifenkörpers in jedem Zyklus abschließt. Die Speicherregister der vorliegenden Erfindung sind entworfen, um Π > 1-Entwürfe wirksam zu unterstützen. Sie tragen dazu bei, die Anforderungen, sowohl was die Register als auch das Schalten betrifft, in derartigen kostengünstigen kundenspezifischen Beschleunigern zu reduzieren. Es sei darauf hingewiesen, dass die maximale Anzahl von Phasenbuslinien, die benötigt werden, um ein Speicherregister gemäß der vorliegenden Erfindung zu steuern, Π ist.
Die erste Zelle 42 des Speicherregisters mit angeschlossenem Schreibtor ist mit der Funktionseinheit 32 verbunden, die einen Strom von Werten in die Zelle erzeugt. Ein neuer Wert wird in die erste Zelle geschoben, sooft ein neuer lebendiger Wert durch die Funktionseinheit erzeugt wird. Nachfolgende Zellen speichern Werte, die aus vorherigen Zellen geschoben werden. Eine Verschiebung in eine nachfolgende Zelle findet statt, wenn der Wert innerhalb der vorherigen Zelle lebendig ist und wenn die vorherige Zelle sich verschieben muss, um einen anderen lebendigen Wert zu empfangen, d. h. ihre Vorgängerin speichert einen lebendigen Wert, der herausgeschoben werden muss.
Da alle Π Zyklen eine neue Iteration ausgelöst wird, gibt es Π Schiebemuster, die programmiert werden müssen, und zwar eines für jeden Zyklus. Entsprechend ist jedes Muster durch eine andere Phasenbuslinie bestimmt. Wenn eine bestimmte Zelle sich in dem k-ten Zyklus verschieben soll, hat das ODER-Gatter für diese Zelle einen Eingang, der mit der k-ten Phasenleitung verbunden ist. Soll sich die Zelle nicht verschieben, wird keine derartige Verbindung hergestellt. Zum Beispiel hat in 3 ein ODER-Gatter 38 keinen Eingang, der mit einer Phasenleitung 41 verbunden ist, weshalb eine Zelle 40 sich nicht in dem der Phasenleitung 41 entsprechenden Zyklus verschiebt. Dagegen wird sich die Zelle 40 auf den den Phasenleitungen 44 und 45 entsprechenden Zyklen verschieben. Im Wesentlichen sind die Schiebemuster durch das Setzen der Verbindungen zwischen den ODER-Gattereingängen und den Phasenbuslinien programmiert. Während des Betriebs des Beschleunigers werden dann die Phasenleitungen der Reihe nach durch eine Steuerung 39 aktiviert, und zwar eine pro Zyklus, und die relevanten Speicherzellen schieben ihre Inhalte nach unten.
Das Speicherregister 31 kann in kundenspezifische Hardware implementiert sein, wobei die ODER-Gatter dauerhaft mit den Phasenleitungen verdrahtet sind. Jedoch kann das Speicherregister 31 auch in programmierbare Gatterarrays und andere Arten programmierbarer Hardware implementiert sein. In solchen Fällen können die Verbindungen zwischen den ODER-Gattern und den Phasenleitungen über programmierbare Schaltelemente wie z. B. einen Schalter 46 hergestellt werden.
Wenn klar definiert ist, wann genau sämtliche Verschiebungen innerhalb eines Speicherregisters stattfinden, ist es möglich, anhand der Verschiebungshistorie des Speicherregisters zu verfolgen, wo jeder Wert innerhalb des Speicherregisters zu jedem Zeitpunkt liegt. Wenn ein Wert durch einen nachfolgenden Vorgang zu einem spezifischen Zeitpunkt gelesen wird, wird das Speicherregisterelement, in dem dieser Wert zu diesem Zeitpunkt gespeichert ist, identifiziert. Zu diesem Zeitpunkt wird dann ein Hardwaredatenweg von dem Registerelement, das die Daten speichert, zu dem Funktionseinheitstor, das die Daten benötigt, geschaltet, um die erforderliche Datenübertragung zu unterstützen. Auf diese Weise können Speicherregister der vorliegenden Erfindung die Sequentialisierung von Operanden zwischen Funktionseinheiten steuern. Abgriffspunkte zum Übertragen von Daten von einem Speicherregister an eine bestimmte Funktionseinheit müssen nur bei den Speicherregisterzellen implementiert sein, die einen lebendigen Wert speichern, der durch eine Funktionseinheit gelesen werden muss.
Es wird jetzt Bezug genommen auf 4, die ein Blockdiagramm eines Schleifenbeschleunigers 100 darstellt, der zwei Funktionseinheitsanordnungen 101 und 102 gemäß der vorliegenden Erfindung aufweist. Die im Vorhergehenden beschriebenen Datenwege können festverdrahtet sein oder durch eine bestimmte Form eines Schaltnetzwerks vorliegen, wie z. B. einen Querverbindungsschalter 103, der die Ausgänge von Speicherregistern in den Funktionseinheitsanordnungen mit den relevanten Eingängen der verschiedenen Funktionsgeneratoren in dem Beschleuniger verbindet. Die spezifischen Verbindungen werden durch die Phase der Berechnung bestimmt, die durch eine der Steuerungen oder eine getrennte Steuerung, die die Aktivitäten sämtlicher Funktionseinheiten in dem Schleifenbeschleuniger koordiniert, an den Querverbindungsschalter kommuniziert werden kann. Wird während der Schleife eine bestimmte Funktionseinheitsausgabe nicht zu einer Funktionseinheit geleitet, können die entsprechenden Schalter in dem Querverbindungsschalter weggelassen werden, wodurch sich die Kosten des Beschleunigers reduzieren.
Es wird darauf hingewiesen, dass auch an anderen Zellen als der ersten Zelle Werte in das Speicherregister eintreten können. Es wird jetzt Bezug genommen auf 5, die ein Blockdiagramm einer Funktionseinheitsanordnung 50 eines Hardwarebeschleunigers gemäß der vorliegenden Erfindung darstellt, die ein Speicherregister 51 gemäß der vorliegenden Erfindung verwendet, die einen zusätzlichen Eingang in Speicherregister 51 aufweist. Bei diesem Ausführungsbeispiel stellt ein Multiplexer 53 durch die Steuerung einer Steuerung 59 einen Eingang 55 bereit, der zum Einführen eines neuen Wertes in Speicherregister 51 verwendet werden kann. Dieser Eingang kann über Verbindungswege wie z. B. den in 3 gezeigten Querverbindungsschalter mit anderen Funktionseinheiten verbunden sein. Alternativ könnte dieser Eingang mit einem anderen Register in dem Beschleuniger verbunden sein. Derartige zusätzliche Eingänge sind nützlich für die Initialisierung der Funktionseinheit vor Beginn der Schleifenberechnung. Außerdem unterstützen derartige Eingänge eine wiederholte bedingte Zuweisung zu einem gemeinsamen Register oder virtuellen Register.
Das in den im Vorhergehenden beschriebenen Ausführungsbeispielen verwendete Steuerschema stützt sich auf einen Phasenbus, der das Zeitmodulo Π in einem uncodierten Format rundsendet. Der Phasenbus besteht aus Π Drähten, wobei der i-te Draht exakt in den Zyklen, die i modulo Π sind, einen vorbestimmten Wert (z. B. eins) aufweist. Jedoch können auch andere Steuerschemata implementiert sein.
Es wird jetzt Bezug genommen auf 6, die ein Blockdiagramm eines Ausführungsbeispiels der vorliegenden Erfindung darstellt, das einen Bus verwendet, der weniger als II Drähte aufweist. Bei diesem Ausführungsbeispiel der vorliegenden Erfindung wird das Zeitmodulo Π als eine binäre Nummer auf einem codierten Zeitbus 237 durch eine Steuerung 239 rund gesendet. Dies erfordert weit weniger Drähte zum Rundsenden für große Π, es erfordert jedoch auch, dass jede der Zellen einen oder mehrere Komparatoren umfasst, die den Wert, der auf dem codierten Zeitbus rundgesendet wird, gegen bekannte Zeitpunkte, zu denen sich jede Zelle planmäßig verschieben soll, prüfen. Beispielhafte Komparatoren sind bei 201-203 gezeigt. So werden z. B. bei dem Steuerbus eines Π = 8-Systems nur drei Drähte benötigt. Es wird eine Zelle 206 betrachtet, die sich in dem dritten und fünften Zyklus verschieben soll. Die fragliche Zelle weist zwei bei 201 und 202 gezeigte Komparatoren auf, die diese zwei Werte auf dem Bus erfassen, und Logiksignale erzeugen, die durch das ODER-Gatter 204 verbunden sind, um zu bewirken, dass die Verschiebung exakt bei einer dieser beiden Bedingungen stattfindet. Verschiebt sich eine Zelle wie z. B. die Zelle 205 nur bei einem Zählwert, kann ein einzelner Komparator 203 verwendet und das ODER-Gatter weggelassen werden.
Ausführungsbeispiele der vorliegenden Erfindung, in denen Mehrfach-Modulo-Zähler verwendet werden, können ebenfalls hergestellt werden. Es wird jetzt Bezug genommen auf 7, die ein Ausführungsbeispiel der vorliegenden Erfindung veranschaulicht, das zwei bei 337 und 338 gezeigte Modulo-Busse verwendet, um das Verschieben der Zellen in dem Speicherregister zu steuern. Jeder Bus wird von einem Modulo-Zähler aus betrieben, wobei die den Bussen 337 und 338 entsprechenden Modulo-Zähler bei 339 bzw. 340 gezeigt sind. Bei derartigen Ausführungsbeispielen wird jeder Modulo-Zähler durch eine Steuerung 335 auf einen vorbestimmten Anfangszustand eingestellt. Die Zählung ist für jeden Zähler durch ein gemeinsames Taktsignal gesteuert. Es wird kein Phasenbus oder sonstige Verdrahtung (außer Takt) benötigt, um diese Zähler miteinander zu verbinden, da die Zähler in Verriegelungsschritt-Harmonie zählen. Die Zähler können ein uncodiertes Phasenbussignal oder ein codiertes Zeitbussignal erzeugen. Bei dem in 7 gezeigten Beispiel erzeugt ein Zähler 339 ein codiertes Bussignal und ein Zähler 340 erzeugt ein uncodiertes Bussignal. Jede Schiebezelle kann an die nächstliegende oder am günstigsten gelegene Steuerung angeschlossen sein, um die Verschiebung zu steuern. Bei dem in der Figur gezeigten Beispiel ist eine Schiebezelle 306 über Komparatoren 301 und 302 mit dem Bus 337 verbunden, und eine Schiebezelle 305 ist mit dem Bus 338 verbunden. Die Einrichtung zum Decodieren von Schiebesignalen ist durch den Typ des Busses bestimmt, mit dem die Zelle verbunden ist. Folglich verwendet die Zelle 306 Komparatoren des bezüglich der 6 erörterten Typs und die Zelle 305 ist direkt durch ein ODER-Gatter 304 mit den einzelnen Buslinien verbunden.
Die Verwendung von separaten Zählern oder Steuerungen kann die Menge an erforderlichen Zwischenverbindungen reduzieren. Wenn sich z. B. mehrere Zellen nur bei einem oder zwei Zuständen des Modulo-Zählers verschieben, können diese Zellen mit einem uncodierten Bus verbunden sein, bei dem die unbenutzten Leiter fehlen.
Die im Vorhergehenden beschriebenen Ausführungsbeispiele der vorliegenden Erfindung wurden hinsichtlich von Funktionseinheiten erörtert, die pro Zyklus ein Ergebnis erzeugen. Den Fachleuten ist jedoch klar, dass dies die maximale Rate ist, mit der jede Funktionseinheit Ergebnisse ausgibt. Es ist möglich, dass auf einigen Zyklen eine oder mehrere der Funktionseinheiten keinen Ausgang erzeugt. Eigentlich erzeugt diese Funktionseinheit einen Null-Ausgang in dem fraglichen Zyklus. Es kann z. B. sein, dass eine Gleiteinheit zwei Zyklen benötigt, um ein Ergebnis abzuschließen, während die anderen Funktionseinheiten nur einen Zyklus benötigen. In dem ersten Zyklus einer derartigen Zwei-Zyklus-Sequenz schiebt das mit dieser Funktionseinheit verbundene Speicherregister keinen neuen Wert hinein.
Verschiedene Modifizierungen der vorliegenden Erfindung werden den Fachleuten aus der vorhergehenden Beschreibung und den beiliegenden Zeichnungen ersichtlich. Folglich soll die vorliegende Erfindung einzig durch den Schutzbereich der folgenden Ansprüche beschränkt sein.

Claims

Eine Berechnungseinheit [30, 50, 100] zur Verwendung in Schleifenberechnungen, wobei die Berechnungseinheit [30, 50, 100] angepasst ist, um alle Π Zyklen eine Iteration der Schleife auszulösen, wobei die Berechnungseinheit [30, 50, 100] folgende Merkmale aufweist: eine Funktionseinheit [32, 52], die einen Ergebnisausgang aufweist, der zum Ausgeben eines Berechnungsergebnisses angepasst ist; einen ersten Zähler [339], der angepasst ist, einen Wert aufzuweisen, der pro Zyklus weitergezählt und alle Π Zyklen zurückgesetzt wird; einen ersten Phasenbus [37, 237, 337], der angepasst ist, einen Zustand aufzuweisen, der durch den Wert des ersten Zählers [339] bestimmt ist; und ein Speicherregister, das ein linear angeschlossenes Array von Schiebezellen [33, 40, 42, 205, 206, 305, 306] aufweist, das eine erste Schiebezelle [42, 206, 306] aufweist, wobei jede Schiebezelle [33, 40, 42, 205, 206, 305, 306] ein Eingangstor, ein Ausgangstor und ein Schiebesteuertor [35] aufweist, wobei jede Schiebezelle [33, 40, 42, 205, 206, 305, 306] angepasst ist, einen Wert zu empfangen, der in der Speicherzelle [33, 40, 42, 205, 206, 305, 306] auf dem Eingangstor gespeichert werden soll, wobei der Wert ansprechend auf ein Steuersignal auf dem Schiebesteuertor [35] gespeichert ist, wobei das Eingangstor der ersten Schiebezelle [42, 206, 306] mit dem Ergebnisausgang verbunden ist, wobei jede Schiebezelle [33, 40, 42, 205, 206, 305, 306] ferner eine Schiebesteuer schaltung [34, 38, 201, 203] aufweist, die mit dem ersten Phasenbus [37, 237, 337] und dem Schiebesteuertor [35] verbunden ist und zum Erzeugen des Steuersignals auf dem Schiebesteuertor [35] angepasst ist.
Die Berechnungseinheit [30, 50, 100] gemäß Anspruch 1, bei der der erste Phasenbus [37, 237, 337] Π Leiter [41, 44, 45] aufweist, wobei ein Leiter [41, 44, 45] jedem der Π Zyklen entspricht, und bei der die Schiebesteuerschaltung [34, 38, 201, 203] ein ODER-Gatter [34, 38] aufweist, das einen Ausgang, der mit dem Schiebefreigabetor verbunden ist, und einen Eingang für jeden Zyklus, in dem sich diese Schiebezelle [33, 40, 42, 205, 206, 305, 306] verschieben soll, aufweist, wobei dieser Eingang mit der diesem Zyklus entsprechenden Phasenleitung verbunden ist.
Die Berechnungseinheit [30, 50, 100] gemäß Anspruch 1, bei der der erste Phasenbus [37, 237, 337] angepasst ist, eine binär codierte Darstellung des Wertes in dem Zähler aufzuweisen, und bei der die Schiebesteuerschaltung [34, 38, 201, 203] einen Komparator aufweist, der zum Erzeugen des Steuersignals für jeden Zyklus, in dem sich diese Schiebezelle [33, 40, 42, 205, 206, 305, 306] verschieben soll, angepasst ist.
Die Berechnungseinheit [30, 50, 100] gemäß Anspruch 1, die ferner folgende Merkmale aufweist: einen zweiten Zähler [340], der angepasst ist, einen Wert aufzuweisen, der pro Zyklus weitergezählt und alle Π Zyklen zurückgesetzt wird; eine Schaltung [335], die angepasst ist zu bewirken, dass der erste und der zweite Zähler [340] erste bzw. zweite Anfangswerte übernehmen; einen zweiten Phasenbus [338], der angepasst ist, einen Zustand aufzuweisen, der durch den Wert des zweiten Zählers [340] bestimmt ist, wobei die Schiebesteuerschaltung [34, 38, 201, 203] mindestens einer der Schiebezellen [33, 40, 42, 205, 206, 305, 306] mit dem zweiten Phasenbus verbunden ist.
Die Berechnungseinheit [30, 50, 100] gemäß Anspruch 1, die ferner einen Multiplexer [53] aufweist, der einen ersten und einen zweiten Eingang und einen Ausgang aufweist, wobei der ersten Eingang mit dem Ausgang einer der Schiebezellen [33, 40, 42, 205, 206, 305, 306] verbunden ist, und er Ausgang des Multiplexer [53] mit dem Eingang einer anderen der Schiebezellen [33, 40, 42, 205, 206, 305, 306] verbunden ist.
Die Berechnungseinheit [30, 50, 100] gemäß Anspruch 1, bei der die Berechnungseinheit [30, 50, 100] in ein programmierbares Gatterarray implementiert ist.
Die Berechnungseinheit [30, 50, 100] gemäß Anspruch 2, bei der einer der Eingänge eines der ODER-Gatter [34, 38] durch einen programmierbaren Schalter [46] mit einer der Phasenleitungen verbunden ist.
Ein Schleifenbeschleuniger [100], der zum Auslösen einer Iteration einer Schleife alle Π Zyklen angepasst ist, wobei der Schleifenbeschleuniger [100] eine Mehrzahl von Berechnungseinheiten [30, 50, 100] gemäß einem der Ansprüche 1 bis 7 aufweist, wobei jede der Berechnungseinheiten [30, 50, 100] ferner folgende Merkmale aufweist: eine Querverbindungsschaltung [103], die zum Koppeln des Ausgangs mindestens einer Schiebezelle [33, 40, 42, 205, 206, 305, 306] einer der Berechnungseinheiten [30, 50, 100] mit einem Eingang einer Funktionseinheit [32, 52] einer anderen der Berechnungseinheiten [30, 50, 100] in einem aus den Π Zyklen ausgewählten Zyklus angepasst ist.
Ein Speicherregister, das zum Speichern von Werten, die auf einem Speichereingangstor in einer Schleifenberechnung empfangen wurden, angepasst ist, wobei alle Π Zyklen eine Schleifeniteration ausgelöst wird, wobei das Speicherregister folgende Merkmale aufweist: eine Mehrzahl von Phasenleitungen, wobei eine jedem der Π Zyklen entspricht; und ein linear angeschlossenes Array von Schiebezellen [33, 40, 42, 205, 206, 305, 306], das eine erste Schiebezelle [42, 206, 306] aufweist, wobei jede Schiebezelle [33, 40, 42, 205, 206, 305, 306] ein Eingangstor, ein Ausgangstor, ein Schiebesteuertor [35] und ein ODER-Gatter [34, 38] aufweist, wobei jede Schiebezelle [33, 40, 42, 205, 206, 305, 306] angepasst ist, einen Wert, der in der Schiebezelle [33, 40, 42, 205, 206, 305, 306] auf dem Eingangstor gespeichert werden soll, zu empfangen, wobei der Wert ansprechend auf ein Steuersignal auf dem Schiebesteuertor [35] gespeichert wird, wobei das ODER-Gatter [34, 38] einen Ausgang, der mit dem Schiebefreigabetor verbunden ist, und einen Eingang für jeden Zyklus, auf dem diese Schiebezelle [33, 40, 42, 205, 206, 305, 306] das Steuersignal empfangen soll, aufweist, wobei dieser Eingang mit der diesem Zyklus entsprechenden Phasenleitung verbunden ist, wobei das Eingangstor der ersten Schiebezelle [42, 206, 306] mit dem Speichereingangstor verbunden ist.
Das Speicherregister gemäß Anspruch 9, bei dem mindestens eine der Schiebezellen [33, 40, 42, 205, 206, 305, 306] nicht mit einer Phasenleitungen verbunden ist.
Das Speicherregister gemäß Anspruch 9, bei dem einer der Eingänge eines der ODER-Gatter durch einen programmierbaren Schalter [46] mit einer der Phasenleitungen verbunden ist.