PatentDe  


Dokumentenidentifikation DE10084213B4 23.03.2006
Titel Anordnung und Verfahren zur Steuerung des Datenflusses
Anmelder Systemonic AG, 01099 Dresden, DE
Erfinder Drescher, Wolfram, 01099 Dresden, DE;
Weiss, Matthias, 01187 Dresden, DE
Vertreter Patentanwälte Lippert, Stachow & Partner, 01309 Dresden
DE-Anmeldedatum 29.12.2000
DE-Aktenzeichen 10084213
WO-Anmeldetag 29.12.2000
PCT-Aktenzeichen PCT/DE00/04641
WO-Veröffentlichungsnummer 0000150240
WO-Veröffentlichungsdatum 12.07.2001
Veröffentlichungstag der Patenterteilung 23.03.2006
Veröffentlichungstag im Patentblatt 23.03.2006
IPC-Hauptklasse G06F 9/00(2006.01)A, F, I, 20051017, B, H, DE

Beschreibung[de]

Die Erfindung betrifft eine Anordnung zur Steuerung des Datenflusses bei einer Verarbeitungseinheit mit einer Vielzahl von parallelen Datenpfaden mit jeweils einem Register/Speicher, jeweils einer zugehörigen Verarbeitungseinheit und einem Ergebnisregister, wobei die Verarbeitungseinheiten jeweils nach dem gleichen Algorithmus arbeiten und jeweils eine Recheneinheit enthalten und jeder Datenpfad sowie jedes Ergebnisregister mit dem Steuerausgang einer zentralen Programmsteuereinheit verbunden ist.

Es ist bekannt, dass die Anforderungen an die Verarbeitungsgeschwindigkeit von digitalen Signalprozessoren in den letzten Jahren stetig gestiegen sind. Um diesen Anforderungen zu genügen, sind hauptsächlich zwei Wege eingeschlagen worden. Einerseits wurde versucht, neue Rechenwerke zu entwerfen, die mit einer höheren Taktfrequenz arbeiten. Dafür wurden erstens die Fortschritte in der Halbleitertechnologie genutzt, die kleinere Transistorgrößen erlauben und zweitens wurden die kritischen Pfade in den Rechenwerken durch Pipelining verkürzt [M. Nomura, et al.; "A 300 Mhz 16-b 0.5&mgr;m BiCMOS Digital Signal Processor Core LSI", IEEE Journal of Solid State Circuits, vol. 29, No. 3, März 1994, Seiten 290-297]; [J. Goto, et al., "250-Mhz BiCMOS Super-High-Speed Video Signal Processor (S-VSP) ULSI", IEEE Journal of Solid State Circuits, Vol. 26, No. 12, Dezember 1991, Seiten 1876-1884]. Andererseits werden Ansätze verfolgt, mehrere Recheneinheiten miteinander so zu kombinieren, dass sie parallel arbeiten [J. Kneip, M. Berekovic, J. P. Wittenberg, W. Hinrichs und P. Pirsch, "An Algorithm Adapted Autonomous Controlling Concept for a Parallel Single-Chip Digital Signal Processor", Journal of VLSI Signal Processing 16, Kluwer Academic Publishers, Seiten 31-40, 1997]; [M. Toyokura et al., "A Video DSP with a Macroblock-Level-Pipeline and a SIMD Type Vector Pipeline Architecture for MPEG-2 CODEC", IEEE Journal of Solid State Circuits, Vol. 29, No. 12, Dezember 1994, Seiten 1474-1481]. Durch die Verteilung auf mehrere Einheiten soll die Geschwindigkeit des Gesamtsystems erhöht werden.

Der erste Ansatz ist deswegen problematisch, weil hoch getaktete Rechenwerke eine hohe Leistungsaufnahme aufweisen. Insbesondere für den Einsatz in mobilen Geräten sind Systeme, die solche Rechenwerke enthalten, nur bedingt geeignet. Die Kombination mehrerer niedrig getakteter Rechenwerke ist unter diesem Gesichtspunkt weniger problematisch. Darüberhinaus ist dieser Ansatz immer von der verfügbaren Technologie abhängig, während die Kombination parallel arbeitender Verarbeitungseinheiten ein fast beliebiges Skalieren der Systemleistung ermöglicht und damit die Gesamtleistung des Systems von der Taktfrequenz abgekoppelt werden kann.

Bei Parallel-Systemen kann man generell zwei Ansätze unterscheiden. Auf der einen Seite steht der Multiple-Instruktion-Multiple-Data (MIMD)-Ansatz. Das bedeutet, dass in einem System parallel arbeitender Verarbeitungseinheiten jede dieser Verarbeitungseinheiten zu einem bestimmten Zeitpunkt einen anderen Maschinenbefehl als alle anderen ausführen kann. Außerdem kann jede der Verarbeitungseinheiten mit anderen Daten rechnen.

Auf der anderen Seite gibt es den Single-Instruction-Multiple-Data (SIMD)-Ansatz, das bedeutet, dass zwar alle Verarbeitungseinheiten unterschiedliche Daten verarbeiten, aber jeweils auf die gleiche Art und Weise. Es ist daher nur ein Maschinenbefehl notwendig, um sämtliche Verarbeitungseinheiten zu steuern. Für den SIMD-Ansatz spricht vor allem, dass er es erlaubt, sehr einfache und kleine Systeme paralleler Recheneinheiten zu bauen. Das liegt daran, dass hier nur eine zentrale Programmkontrolleinheit notwendig ist, um die Verarbeitungseinheiten zu steuern. Im Gegensatz dazu erfordert jede Verarbeitungseinheit beim MIMD-Ansatz ihren eigenen Decoder. Das führt zu größeren Systemen mit höherer Leistungsaufnahme. Auf der anderen Seite erlaubt der MIMD-Ansatz für bestimmte Anwendungen eine effektivere Nutzung der Verarbeitungseinheiten. Über die reinen SIMD- und MIMD-Ansätze hinaus gibt es auch kombinierte Systeme, wie beispielsweise in der US 5,355,508 A dargestellt, in denen die Vor- und Nachteile der beiden Methoden gegeneinander ausbalanciert werden können.

In der Druckschrift „Ching-Ming Shang and Shih-Lien Lu; Design of a static MIMD data flow processor using micropipelines; IEEE Transactions on very large Scale Integration (VLSI) Systems; vol. 3; issue 3; pp. 370-378; Sep. 1995" ist ein Datenflussprozessor mit einer von-Neumann-Architektur dargestellt. Dieser Typ einer Prozessor-Architektur unterscheidet sich von Prozessoren mit Havard- bzw. VLIW-Architekturen grundsätzlich dadurch, dass auf Instruktionsspeicher und Datenspeicher nicht getrennt zugegriffen werden kann. Solche Prozessoren mit von Neumann-Architektur werden in ihrem Einsatz vorwiegend für peel-back Prozessoren (general purpose processors) vorgesehen und sind zur Lösung der unten stehenden erfinderischen Aufgabenstellung nicht geeignet, da ihre Fähigkeiten zur Prozessorparallelisierung problematisch sind. Bei dieser Lösung wird in Bezug auf Prozessoren mit von-Neumann-Architektur in grundsätzlicher Weise der Entwurf von Datenflussprozessoren abgehandelt, welche ihre Leistungsverbesserung daraus schöpfen, dass in ihren Modulen die Daten und Befehle gänzlich asynchron, das heißt unabhängig von einem globalen Takt, abgearbeitet werden. Dazu wird die Gesamtlösung eines 8-Bit-Prozessors vorgestellt.

In der US 5,555,386 A und in der Druckschrift „Jamil, T. and Deshmukh, R. G.; Design of a tokenless architecture for parallel computations using associative data flow processor; In Proceedings of the IEEE Southeastcon '96, 11-14 April 1996, Tampa, FL; pp. 649-656" sind algorithmische IF-Abfragen in Datenflussprozessoren beschrieben, in denen Verzweigungen von Befehlen abgearbeitet werden. Dabei handelt es sich um Sprungbefehle. Derartige Sprungbefehle unterscheiden sich vom vorliegenden Anmeldungsgegenstand und führen nicht in der gewünschten Weise zur unten dargestellten Problemlösung.

In anderen Veröffentlichungen ([1] J. Kneip, M. Berekovic, J. P. Wittenberg, W. Hinrichs und P. Pirsch, "An Algorithm Adapted Autonomous Controlling Concept for a Parallel Single-Chip Digital Signal Processor", Journal of VLSI Signal Processing 16, Kluwer Academic Publishers, Seiten 31-40, 1997; [2] W. Gehrke und K. Gaedke, "Associative Controlling of Monolothic Parallel Processor Architectures", IEEE Transactions on Circuits and Systems for Video Technology, Vol. 5, No. 5, Seiten 453-464, Oktober 1995; [3] W. Gehrke und K. Gaedke, DE 195 32 527 A1, Offenlegungsschrift, Deutsches Patentamt 1997; [5] M. Toyokura et al., "A Video DSP with a Macroblock-Level-Pipeline and a SIMD Type Vector Pipeline Architecture for MPEG-2 CODEC", IEEE Journal of Solid State Circuits, vol. 29, No. 12, Dezember 1994, Seiten 1474-1481; [8] C.J. Zarowski, "Parallel Implementation of the Schur-Berlekamp-Massey Algorithm on a Linearly Connected Processor Array", IEEE Transactions on Computers, Vol. 44, No. 7, July 1995) sind ähnliche Strukturen vorgeschlagen worden. Diese Strukturen befassen sich mit der Kontrolle des Programmflusses. In [3] wird ausführlich dargelegt, was gesteuert werden soll (Schleifen, Unterprogramme, Verteiler). Der dort verfolgte Ansatz funktioniert so, dass an jede der Verarbeitungseinheiten jeweils mehrere Maschinenbefehle herangeführt werden, wobei letzten Endes in Abhängigkeit bestimmter Steuersignale nur ein Maschinenbefehl ausgeführt wird.

Die Steuerung des Programmflusses ist für manche Anwendungen bei Parallelprozessoren insbesondere in der digitalen Signalverarbeitung jedoch nur von untergeordneter Bedeutung. Wichtiger ist vielmehr die Steuerung des Datenflusses. Der hier beschriebene Ansatz unterscheidet sich in erster Linie durch das Steuerungsobjekt. Eine Möglichkeit zur Kontrolle des Datenflusses in einer speziellen Hardwareanordnung ist in [8] beschrieben. Diese Anordnung ist jedoch nicht Teil eines programmierbaren Prozessors.

Ein Beispiel für die Notwendigkeit einer effektiven Datenflußkontrolle, insbesondere für Parallelprozessoren für die digitale Signalverarbeitung, ist der Berlekamp-Massey-Algorithmus. Dort werden in jedem Schleifendurchlauf die gleichen Operationen durchgeführt, nur mit verschiedenen Operanden. Die effektive Kontrolle der Operandenauswahl (des Datenflusses) ist somit von herausragender Bedeutung. Ein unter diesem Aspekt ähnlicher Algorithmus ist der Viterbi-Algorithmus, bei dem in jeder Iteration zwei oder mehr Summen gebildet werden, wobei eine von ihnen aufgrund einer Vergleichsentscheidung den Eingangswert für die folgende Iteration bietet. Auch hier ist die durchgeführte Operation immer gleich, es muß lediglich eine Operandenauswahl (Datenflußkontrolle) vorgenommen werden.

Der Erfindung liegt die Aufgabe zugrunde, eine Anordnung und ein Verfahren zur Steuerung des Datenflusses bei einer Verarbeitungseinheit mit einer Vielzahl von parallelen Datenpfaden zu schaffen, mit der es möglich ist, die Funktion der Verarbeitungseinheiten, d.h. die Übernahme der Rechenergebnisse in das zugehörige Ergebnisregister unmittelbar durch den Datenfluß zu steuern.

Die der Erfindung zugrunde liegende Aufgabenstellung wird mit einer Anordnung mit den Merkmalen des Anspruches 1 gelöst.

In einer vorteilhaften Fortbildung der Erfindung ist der Ausgang der Auswerteeinheit mit einem Eingang eines logischen Gatters und der andere Eingang des logischen Gatters mit dem Steuerausgang der zentralen Programmsteuereinheit, sowie der Ausgang des logischen Gatters mit dem Steuereingang des Ergebnisregisters verbunden. Das logische Gatter kann beispielsweise ein UND-Gatter sein. Ein ODER-Gatter ist an dieser Stelle auch problemlos einsetzbar.

Damit besteht auf einfache weise die Möglichkeit, festzulegen, ob das Steuersignal der zentralen Programmsteuereinheit einen Schreibvorgang im Ergebnisregister auslöst, oder das in das Ergebnisregister geschriebene Rechenergebnis der Recheneinheit löscht.

Die der Erfindung zugrundeliegende Aufgabenstellung wird ferner durch ein Verfahren zur Steuerung des Datenflusses dadurch gelöst, dass jede Auswerteeinheit das Rechenergebnis der Verarbeitungseinheit des jeweiligen Datenpfades auf Plausibilität prüft, indem das Rechenergebnis mit einem vorgegebenen Wert verglichen wird und bei der Feststellung unsinniger Werte oder Übereinstimmung mit einem vorgegebenen Wert das Ergebnisregister löscht.

Durch die Erfindung besteht die Möglichkeit, ohne Eingriff der zentralen Steuereinheit, also ohne zusätzlichen Softwareaufwand, zu erreichen, dass einzelne Rechenergebnisse einzelner Datenpfade von der Weiterverarbeitung ausgeschlossen werden können, wenn das Rechenergebnis des Rechenwerkes einen unsinnigen Wert ergibt. Der Datenfluß wird somit durch das Rechenergebnis der Verarbeitungseinheit selbst gesteuert.

Diese Ergebnisüberprüfung, die hardwaremäßig in jeden Datenpfad implementiert ist, kann einfach durch eine IF-Abfrage oder durch das Setzen eines FLAG erfolgen. D.h., es erfolgt hier keine Programmsteuerung, sondern eine Datenflußkontrolle.

Die Erfindung soll nachfolgend an einem Ausführungsbeispiel näher erläutert werden. In den zugehörigen Zeichnungen zeigen:

1 eine übliche Schaltungsanordnung für eine Single Instruction Data Control Einheit; und

2 eine erfindungsgemäße Schaltungsanordnung eines Datenpfades zur Steuerung des Datenflusses.

1 zeigt zur Verdeutlichung des Ausgangszustandes ein Schaltschema einer üblichen SIMD-Signalverarbeitung. Diese SIMD-Einheit besteht aus einer Verarbeitungseinheit PVE mit einer Vielzahl von parallelen Verarbeitungseinheiten VE, die jeweils einen Datenpfad DP bilden. Jede dieser parallelen Verarbeitungseinheiten VE enthält ein Rechenwerk ALU (Arithmetic Logic Unit), dem ein Register REG vorgeschaltet ist und dessen Rechenergebnis in ein Ergebnisregister/Speicher ACCU geschrieben wird.

Gesteuert werden die parallelen Verarbeitungseinheiten durch eine zentrale Programmsteuereinheit PCU, indem sämtliche parallelen Verarbeitungseinheiten VE mit dem gleichen Maschinenbefehl Crtl gesteuert werden. Auf gleiche Weise wird das Schreiben in die Ergebnisregister/Speicher ACCU der jeweiligen parallelen Verarbeitungseinheiten durch den gleichen Maschinenbefehl Crtl gesteuert. Dadurch können sämtliche parallelen Verarbeitungseinheiten VE unterschiedliche Daten nach dem gleichen Algorithmus verarbeiten.

Diese SIMD-Signalverarbeitung wird durch die Erfindung zu einer Anordnung zur Steuerung des Datenflusses erweitert. Das Schema einer entsprechenden Schaltungsanordnung ist aus 2 ersichtlich.

Jede Recheneinheit ALU eines Datenpfades DP ist mit einer Auswerteeinheit AWE verbunden, welche die Übernahme des Rechenergebnisses des Rechenwerkes ALU in das Ergebnissregister ACCU durch Setzen eines FLAG steuert.

Der Ausgang der Auswerteeinheit AWE ist dazu mit einem Eingang eines logischen Gatters LGT und der andere Eingang des logischen Gatters LGT mit dem Steuerausgang der zentralen Programmsteuereinheit PCU verbunden. Der Ausgang des logischen Gatters LGT, welches ein UND- oder auch ein ODER-Gatter sein kann, ist mit dem Steuereingang des Ergebnisregisters/Speichers ACCU verbunden.

Dadurch kann jede Auswerteeinheit AWE das Rechenergebnis der parallelen Verarbeitungseinheit VE des jeweiligen Datenpfades DP auf Plausibilität hin überprüfen, indem das Rechenergebnis der parallelen Verarbeitungseinheit VE mit einem vorgegebenen Wert verglichen wird. Bei Feststellung unsinniger Werte oder bei Übereinstimmung mit einem vorgegebenen Wert, wird das Ergebnisregister ACCU gelöscht.

In einer besonderen Variante prüft die Auswerteeinheit AWE das Rechenergebnis des Rechenwerkes ALU der parallelen Verarbeitungseinheit VE des jeweiligen Datenpfades DP auf Plausibilität. Dies kann einfach dadurch erfolgen, indem das Rechenergebnis der parallelen Verarbeitungseinheit VE mit einem vorgegebenen Wert verglichen wird. Bei der Feststellung unsinniger Werte, oder bei Übereinstimmung mit einem vorgegebenen Wert wird dann die Übernahme des Rechenergebnisses der parallelen Verarbeitungseinheit VE in das Ergebnissregister ACCU gesperrt.

Durch die Erfindung wird verhindert, dass falsche oder unsinnige Rechenergebnisse in das Ergebnisregister ACCU des entsprechenden Datenpfades DP geschrieben werden. D.h., der Datenpfad DP wird bei einem unsinnigen Rechenergebnis für einen Takt gestoppt.

Der Vorteil einer Datenflußkontrolle gegenüber einer Programmflußkontrolle liegt darin, dass lediglich eine einzige Instruktion an alle gleichartigen Verarbeitungseinheiten VE herangeführt werden muß. Dabei muß jedoch die Instruktion Informationen über die alternativen Datenquellen enthalten. Solche Datenquellen können sowohl Busse, als auch Register sein. Durch das Heranführen einer einzigen Instruktion an jede parallele Verarbeitungseinheit VE wird auf dem Chip Verdrahtungsaufwand und somit Fläche eingespart.

Ein weiterer Vorteil liegt in der Tatsache, dass eine zentrale Programmsteuerung PCU zur Steuerung des Programmflusses zu jedem Zeitpunkt an die gleichartigen parallelen Verarbeitungseinheiten VE nur ein Befehlswort ausgeben muß und somit einfacher aufgebaut werden kann.

Das führt wiederum zu einer Ersparnis an Chipfläche. Somit werden die Herstellungskosten reduziert und die Leistungsaufnahme des Chips reduziert.

DPDatenpfad PVEparallele Verarbeitungseinheit REGRegister ACCUErgebnisregister VEVerarbeitungseinheit PCUzentrale Programmsteuerung ALURechenwerk (Arithmetic Logic Unit) LGTlogisches Gatter AWEAuswerteeinheit

Anspruch[de]
  1. Anordnung zur Steuerung des Datenflusses bei einer Verarbeitungseinheit (PVE) mit einer Vielzahl von parallelen Datenpfaden (DP) mit jeweils einem Register/Speicher (REG), jeweils einer zugehörigen Verarbeitungseinheit (VE) und einem Ergebnisregister (ACCU), wobei die Verarbeitungseinheiten (VE) nach dem gleichen Algorithmus arbeiten und jeweils eine Recheneinheit (ALU) enthalten und jeder Datenpfad (DP) sowie jedes Ergebnisregister (ACCU) mit dem Steuerausgang einer zentralen Programmsteuereinheit (PCU) verbunden ist, jede Recheneinheit (ALU) eines Datenpfades (DP) mit einer Auswerteeinheit (AWE) verbunden ist, welche parallel zur Übernahme des Ergebnisses der Recheneinheit (ALU) in das Ergebnisregister (ACCU) das Ergebnis auf Plausibilität überprüft und bei Feststellung unsinniger Werte oder bei Übereinstimmung mit einem vorgegebenen Wert das zugehörige Ergebnisregister (ACCU) über einen Steuereingang am (ACCU) löscht und den Datenpfad (DP) für einen Takt stoppt.
  2. Anordnung nach Anspruch 1, dadurch gekennzeichnet, dass der Ausgang der Auswerteeinheit (AWE) mit einem Eingang eines logischen Gatters (LGT) und der andere Eingang des logischen Gatters (LGT) mit dem Steuerausgang der zentralen Programmsteuereinheit (PCU), sowie der Ausgang des logischen Gatters (LGT) mit dem Steuereingang des Ergebnisregisters (ACCU) verbunden ist.
  3. Anordnung nach Anspruch 2, dadurch gekennzeichnet, dass das logische Gatter (LGT) ein UND-Gatter ist.
  4. Verfahren zur Steuerung des Datenflusses in einer Anordnung nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass jede Auswerteeinheit (AWE) das Rechenergebnis der Verarbeitungseinheit (VE) des jeweiligen Datenpfades (DP) auf Plausibilität prüft, indem das Rechenergebnis mit einem vorgegebenen Wert verglichen wird und bei der Feststellung unsinniger Werte oder Übereinstimmung mit einem vorgegebenen Wert das Ergebnisregister (ACCU) löscht.
Es folgen 3 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com