Die Erfindung betrifft ein Parallel-Verarbeitungs-Array, beispielsweise ein Single Instruction Multiple Data(SIMD)-Verarbeitungs-Array, mit einer Vielzahl von Verarbeitungselementen (processing elements, PEs). Insbesondere betrifft die vorliegende Erfindung ein Parallel-Verarbeitungs-Array, das ausgestaltet ist, die Effizienz des Arrays zu verbessern, wenn datenabhängige Verarbeitungsoperationen gehandhabt werden.

In einem SIMD-Verarbeitungs-Array empfängt jedes Verarbeitungselement (processing element, PE) des Arrays die gleiche Anweisung über einen gemeinsamen Anweisungsstrom und führt die Anweisung basierend auf lokalen Daten aus, die für das Verarbeitungselement eindeutig sind. Parallel-Verarbeitungs-Arrays eignen sich daher gut zur Ausführung sich stark wiederholender Aufgaben, bei denen zur selben Zeit dieselben Operationen für mehrere Daten durchgeführt werden, zum Beispiel solche, die mit Bildverarbeitung verknüpft sind. SIMD stellt daher eine flächeneffiziente, skalierbare, leistungsarme Implementierung bereit. Während SIMD für Anwendungen geeignet ist, die signifikante Wiederholungen in den Daten und in der Verarbeitung von den Daten enthalten, ist SIMD nicht zum Durchführen von datenabhängigen Verarbeitungsoperationen geeignet.

Zum Beispiel sind bei der Videoverarbeitung (z. B. Zeilenentflechtung, Rauschunterdrückung, horizontaler dynamischer Spitzenwertbildung) die meisten Operationen für alle Datenelemente in dem Array exakt gleich und verwenden daher das SIMD-Array auf effiziente Weise. Datenabhängige Verarbeitungsoperationen, wie zum Beispiel Nachschlagetabellen-Operationen oder Multiplikation mit unterschiedlichen Koeffizienten basierend auf der Platzierung von Daten in einem Array, verwenden jedoch ein SIMD-Verarbeitungs-Array nicht effizient.

Ein Beispiel eines parallelen Verarbeitungs-Arrays ist gegeben in „Kestrel: Design of an 8-bit SIMD parallel processor" von D. M. Dahle u.w. in Proceedings of the 17th Conference an Advanced research in VLSI, IEEE Comput. Soc. 1997, Seiten 145-162, das ein SIMD-Verarbeitungs-Array mit gemeinsamen systolischen Registern (systolic shared registers, SSRs) für Inter-PE-Kommunikation offenbart. Jedes PE enthält einen statischen Speicher mit wahlfreiem Zugriff (random access memory), um die Speicherkapazität der SSRs zu ergänzen und um einen lokal adressierbaren Speicher bereitzustellen.

1 zeigt eine Schematik eines typischen Verarbeitungselements (PE) 1 in einer Xetal SIMD-Verarbeitungsarchitektur (wobei Xetal ein leistungsarmer Parallelprozessor für digitale Videokameras ist). Das Verarbeitungselement 1 umfasst eine arithmetische logische Einheit (arithmetic logic unit, ALU) 3, einen Multiplexer (MUX) 5, einen Akkumulator (ACCU) 7 und ein Flagregister (FLAG) 9. Das Verarbeitungselement 1 empfängt eine Rundsendeanweisung 10, die von allen anderen Verarbeitungselementen in dem Array (nicht gezeigt) empfangen wird. Die ALU 3 verarbeitet die Anweisung 10 basierend auf lokalen Daten. Der Akkumulator 7 wird zum Speichern eines letzten Ergebnisses bereitgestellt, das als der Operand für die nächste Anweisung 10 benutzt werden kann. Typischer Weise umfasst die ALU 3 einen Addierer und einen Multiplikator, wodurch innerhalb eines Taktzyklus durchzuführende Vergleiche, Addition, Subtraktion, Datengewichtung und Multiplizier-Akkumulier-Operationen ermöglicht werden. Typischer Weise enthält das Flagregister 9 ein 1-Bit-Flag, das entsprechend dem letzten Ergebnis gesetzt wird. Basierend auf diesem Flag-Status sind bedingte Durchlassanweisungen möglich, die eine beschränkte Form der Datenabhängigkeit in den Algorithmen erlauben.

Es sei angemerkt, dass der Multiplexer 5 durch die Rundsendeanweisung 10 gesteuert wird. Bei der Xetal-Architektur empfängt der Multiplexer 5 eine Anzahl von Eingangssignalen, die mit der ALU 3 selektiv verbunden sind. Zum Beispiel empfängt der Multiplexer 5 Daten von einem Teil des Zeilenspeichers 6 und Daten vom linken und rechten Kommunikationskanal 8, 12. Der Multiplexer 5 empfängt ebenfalls Koeffizientendaten (coeff) 16. Auf diese Weise wird das ACCU-Signal 14 aus dem Akkumulator 7 als ein Operand für eine Operation verwendet, und der Multiplexer 5 wählt den zweiten Operanden aus. Daher kann der zweite Operand aus dem linken Kommunikationskanal 8, dem rechten Kommunikationskanal 12 oder dem Zeilenspeicher 6, oder eine „feste" Zahl aus der Koeffizienteneingabe 16 gewählt werden.

Das Durchführen einer datenabhängigen Verarbeitung, zum Beispiel Abfragen eines Wertes aus einer Nachschlagetabelle, oder das Durchführen verschiedener Operationen mit verschiedenen Datenelementen des gleichen Arrays sind bei dieser Art von Prozessoren entweder nicht möglich oder benötigen viele lange und komplizierte Iterationen. Dies führt zu einer schwachen Effizienz des SIMD-Verarbeitungs-Arrays.

Zum Beispiel benötigt das Durchführen einer Multiplikation nach dem Empfangen eines Wertes aus einer Nachschlagetabelle mit zehn Elementen in der in 1 gezeigten Xetal-Architektur vierzig Operationen. Eine den Xetal-Befehlssatz verwendende Implementierung, in der für einen Nachschlagevorgang der Wert mit einer unteren Grenze verglichen werden muss, wird nachfolgend gezeigt: Man nehme an, r0 weist die Datenelemente eines gewünschten Arrays auf.

• 1. accu=r0; – bewege die Daten zu dem Akkumulator
• 2. accu=MAX(accu, lower_limit0); – finde das Maximum zwischen r0 und lower_limit0 und speichere es in accu
• 3. accu=accu·coeff0; – dieses ist die Operation in dem Intervall
• 4. r1=PASSC(accu, r1); – falls r0 in dem Bereich lag, behalte das Ergebnis, sonst kopiere r1 in das nächste Intervall

Wie oben gezeigt, müssen für alle Einträge in der Nachschlagetabelle (LUT), zum Beispiel zehn in dem oben bereitgestellten Beispiel, alle vier der obigen Operationen durchgeführt werden. Das bedeutet, dass für ein Zehn-Element-LUT vierzig Operationen benötigt werden.

Die Aufgabe der vorliegenden Erfindung ist es, ein Parallel-Verarbeitungs-Array bereitzustellen, das nicht die oben stehenden Nachteile hat, wenn datenabhängige Operationen durchgeführt werden.

In Übereinstimmung damit wird das vorgenannte Problem gemäß den unabhängigen Ansprüchen gelöst.

Das oben definierte Verarbeitungs-Array hat den Vorteil, dass es effizienter als ein herkömmliches Verarbeitungs-Array ist, wenn datenabhängige Verarbeitungsoperationen durchgeführt werden.

Zum besseren Verständnis der vorliegenden Erfindung und um deutlicher zu zeigen, wie diese verwirklicht werden kann, wird im Folgenden beispielhaft Bezug auf die beigefügten Zeichnungen genommen, in denen:

1 ein schematisches Diagramm eines Verarbeitungselements eines Parallel-Verarbeitungs-Arrays gemäß dem Stand der Technik zeigt; und

2 ein schematisches Diagramm eines Verarbeitungselements eines Parallel-Verarbeitungs-Arrays gemäß der vorliegenden Erfindung zeigt.

2 zeigt ein Verarbeitungselement 1 eines Verarbeitungs-Arrays gemäß der vorliegenden Erfindung. Wie oben in 1 gezeigt, umfasst das Verarbeitungselement 1 eine arithmetische logische Einheit (ALU) 3, einen Multiplexer (MUX) 5, einen Akkumulator (ACCU) 7 und ein Flagregister (FLAG) 9. Der Betrieb dieser Elemente für eine „herkömmliche" Verarbeitung, d.h. nicht datenabhängige Verarbeitung, entspricht genau dem oben in Bezug auf 1 beschriebenen.

Gemäß der Erfindung umfasst das Verarbeitungselement ferner ein Speicherelement (SE) 11, das die Verarbeitung einer lokal angepassten (d.h. datenabhängigen) Verarbeitung in dem Verarbeitungselement 1 unterstützt.

Das Speicherelement 11 umfasst eine Anzahl von Speicherplätzen SE₁ bis SE_N. Die Anzahl von Speicherplätzen wird in dem Entwurfsprozess in Abhängigkeit von der bestimmten Anwendung ausgewählt und kann eine beliebige ganze Zahl sein. Das Speicherelement 11 empfängt Eingangsdaten 13 (data_in) über einen Multiplexer 15. Der Multiplexer 15 ist verschaltet, um Akkumulatordaten 14 von dem Ausgang des Akkumulators 7 und Koeffizientendaten 16 (coeff) aus einem Koeffizientenport des Verarbeitungselements 1 zu empfangen. Der Multiplexer 15 ist ausgestaltet, die Akkumulatordaten 14 oder Koeffizientendaten 16 als die Eingangsdaten 13 dem Speicherelement 11 selektiv unter Steuerung durch ein Steuerungssignal 17 bereitzustellen, das von der Rundsendeanweisung 10 herrührt oder einen Teil der Rundsendeanweisung 10 bildet.

Das Speicherelement 11 empfängt auch ein Indexsignal 19, das mit dem Ausgang eines Multiplexers 21 verbunden ist. Der Multiplexer 21 ist auch verschaltet, um Akkumulatordaten 14 von dem Akkumulator 7 und Koeffizientendaten 16 (coeff) von dem Koeffizientenport des Verarbeitungselements 1 zu empfangen. Der Multiplexer 21 wird ebenfalls durch das Steuerungssignal 17 gesteuert, das von der Rundsendeanweisung 10 herrührt oder einen Teil der Rundsendeanweisung 10 bildet. Ausgangsdaten 22 (data_out) aus dem Speicherelement 11 werden mit dem Eingang des Multiplexers 5 des Verarbeitungselements 1 verbunden. Zwischen dem Ausgang des Speicherelements 11 und dem Multiplexer 5 wird vorzugsweise ein Register 23 (curr_se) bereitgestellt, das zum Speichern eines Werts des Speicherelements 11 verwendet werden kann, wie später in der Anmeldung näher beschrieben wird.

Als Nächstes wird das Betreiben des Ausführungsbeispiels nach 2 in Bezug auf das Speichern verschiedener Koeffizienten in jedem PE beschrieben, um Multiplikation (oder jede andere Operation) mit einem jeweils anderen Koeffizienten pro Dateneintrag in dem Array und das Durchführen einer Nachschlagetabellenoperation bereitzustellen, obwohl die für alle PE verwendete Anweisung dieselbe bleibt.

Wenn das Speicherelement 11 zum Speichern verschiedener Koeffizienten verwendet wird, werden die Koeffizientendaten 16 als ein Index für die Speicherelementtabelle verwendet, und die Akkumulatordaten 14 aus dem Akkumulator 7 oder dem Zeilenspeicher werden an einem entsprechenden Speicherplatz SE_Y in dem Speicherelement 11 gespeichert. Mit anderen Worten, der Multiplexer 15 wird gesteuert, um die Akkumulatordaten 14 als die Eingangsdaten 13 an das Speicherelement 11 weiterzuleiten, während der Multiplexer 21 gesteuert wird, um die Koeffizientendaten 16 weiterzuleiten, die als der Index 19 für den entsprechenden Speicherplatz SE_Y agieren, in dem die Daten zu speichern sind. Dieses ermöglicht das Speichern der korrekten Werte in den korrekten Plätzen SE₁-SE_N des Speicherelements 11. Alternativ, falls erwünscht, können die Koeffizienten durch Anlegen der Koeffizientendaten an dem Eingang 13 und durch Verwenden der Akkumulatordaten als der Index 19 gespeichert werden.

Wenn ein Wert aus dem Speicherelement 11 in ähnlicher Weise wie oben geladen wird, werden die Koeffizientendaten 16 als ein Index 19 verwendet, um einen Wert aus dem entsprechenden Speicherplatz des Speicherelements 11 an dem Ausgang verfügbar zu machen, wodurch die durchzuführende Multiplikation mit den Daten in dem Akkumulator 7 ermöglicht wird. Mit anderen Worten, wenn Daten aus dem Speicherelement 11 geladen werden, wird der Multiplexer 21 ausgestaltet, die Koeffizientendaten 16 als den Index 19 an das Speicherelement 11 weiterzuleiten, wodurch die entsprechenden Ausgangsdaten 22 aus dem Speicherelement 11 ausgegeben werden. Die Ausgangsdaten aus dem Speicherelement 11 werden über den Multiplexer 5 an die ALU 3 zum Multiplizieren mit den Daten aus dem Akkumulator 7 weitergeleitet.

Wenn das Speicherelement als eine Nachschlagetabelle (look-up-table, LUT) in jedem PE verwendet wird, gibt es eine Anzahl von alternativen Vorgehensweisen zum Speichern der korrekten Werte (lower_limit, Ergebniswert) in dem Speicherelement 11.

Eine Vorgehensweise ist es, einen Teil des coeff-Eingangs als den Index und den anderen Teil als den zu speichernden Wert zu verwenden. Mit anderen Worten, ein Teil der Koeffizientendaten 16 wird von dem Multiplexer 21 als der Index 19 an das Speicherelement 11 weitergeleitet, während der andere Teil der Koeffizientendaten 16 von dem Multiplexer 15 als der zu speichernde Wert weitergeleitet wird. Obwohl das Verfahren den Nachteil des Vergrößerns der Breite des Koeffizientendatensignals hat, weist es den Vorteil des Speicherns von Werten in einem Zyklus auf.

Eine andere Vorgehensweise ist das Generieren der Adresse oder des Index 19 mit Hilfe des Akkumulators 7 und/oder der ALU 3, was das Generieren von verschiedenen Adressen ermöglicht und als Folge das Speichern der gleichen Werte an verschiedenen Plätzen in Speicherelementen von PEs durch Anlegen der Adresse an das Speicherelement 11 mit einer Speicheranweisung, so dass der Wert der Koeffizientendaten 16 in dem entsprechenden Speicherplatz SE_Y des Speicherelements 11 gespeichert wird. In dieser Anordnung ist der Multiplexer 15 ausgestaltet, die Koeffizientendaten 16 weiterzuleiten, während der Multiplexer 21 einen Index 19 bereitstellt, der von dem Akkumulator 7 und/oder ALU 3 generiert worden ist. Diese Vorgehensweise hat den Vorteil, dass ein schmaleres Koeffizientendatensignal erforderlich ist, hat aber den Nachteil, dass eine zusätzliche Verarbeitungsoperation benötigt wird.

Zum Laden eines Werts aus dem Speicherelement 11 wird der Wert des Akkumulators 7 als der Index 19 verwendet und der nachgeschlagene Wert aus dem Speicherelement 11 wird in dem Register 23 (curr_se) für eine weitere Verwendung gespeichert. Mit anderen Worten, die Akkumulatordaten 14 aus dem Akkumulator 7 werden von dem Multiplexer 21 weitergeleitet, um dem Speicherelement 11 einen Index 19 bereitzustellen. Der entsprechende Wert aus dem entsprechenden Speicherplatz SE_Y bildet die Ausgangsdaten 22 des Speicherelements 11 und wird entweder an den Multiplexer 5 direkt weitergereicht oder in dem Register 23 für eine spätere Verwendung gespeichert. Es wird angemerkt, dass das Register 23 (curr_se) bei einem Betrieb mit niedriger Frequenz überbrückt werden kann, um Operationen in einem Zyklus durchzuführen.

Die oben beschriebene Erfindung stellt ein verbessertes Verarbeitungs-Array bereit, da diese den Verarbeitungselementen ermöglicht, auf jede der folgenden Weisen betrieben zu werden:

• a) jedes PE führt die gleiche Operation basierend auf einer Rundsendeanweisung aus, (d.h. „normaler" Betrieb)
• b) ein PE verwendet einen anderen Koeffizienten basierend auf den zu verarbeitenden Daten, um die gleiche Rundsendeoperation auszuführen, oder
• c) bei einer Rundsendung an alle PE, LUT-Operationen durchzuführen, führt das PE eine Funktion aus, die in einer Nachschlagetabelle beschrieben worden ist.

In einer Videoverarbeitungsanwendung können beispielsweise die meisten Funktionen mit einer zeilenbasierten Verarbeitung (zum Beispiel Zeilenentflechtung, Rauschunterdrückung, horizontale dynamische Spitzenwertbildung) durchgeführt werden oder können im Sinne der zeilenbasierten Verarbeitung ausgedrückt werden (zum Beispiel kann ein Aufwärtswandler mit 2×2 Blockgröße auf Zeilenbasis verarbeitet werden durch Akkumulieren von 2×2 Blöcken als zwei Zeilen und Durchführen einer zeilenbasierten Verarbeitung). Das bedeutet, dass die meisten Operationen für alle Datenelemente in dem Array exakt dieselben sind und daher unter Verwendung des „normalen", oben in (a) beschriebenen PE-Betriebs durchgeführt werden können.

Wenn jedoch Aufgaben wie zum Beispiel eine Multiplikation (oder andere Operanden) mit unterschiedlichen Koeffizienten basierend auf Platzierung der Daten in einem Array durchgeführt werden, wird das Verarbeitungselement gemäß der vorliegenden Erfindung ausgestaltet, wie oben in (b) beschrieben betrieben zu werden.

Ähnlich wird bei der LUT-Operation das Verarbeitungselement ausgestaltet, wie oben in (c) beschrieben betrieben zu werden.

Die Erfindung hat den Vorteil des Verwendens der Eigenschaften der SIMD-Verarbeitung, wobei dennoch ein effizienteres Betreiben bereitgestellt wird, wenn datenabhängige Verarbeitungsoperationen durchgeführt werden müssen. Zum Beispiel würde in der vorliegenden Erfindung die Verarbeitung einer Multiplikation mit einem nachgeschlagenen Wert etwa zwei Operationen (abhängig von der Implementierungswahl für eine LUT-Operation) benötigen, was ungefähr nur 5% des früher beschriebenen Verfahrens ausmacht, das vierzig Instruktionen benötigte.

Daher stellt die Erfindung einen indirekt adressierbaren Speicher pro Verarbeitungselement bereit, der für datenabhängige Operationen verwendet werden kann, wie zum Beispiel Nachschlagetabellenoperationen, und zum Zugreifen auf unterschiedliche Koeffizienten, die mit der gleichen Anweisung für alle PEs verwendet werden können.

Es sei angemerkt, dass der erweiterte Bereich, der für ein Verarbeitungselement aufgrund des Speicherelements benötigt wird, kein nachteiliger Faktor ist, da der Zwischenverbindungsbereich der dominierende Faktor auf einem Chip wie diesem ist. Somit vermeidet das Plazieren der Speicherelemente in der Nähe der arithmetischen logischen Einheit (ALU) ein weiteres Überlasten des Kommunikationsnetzwerks (d. h. Verdrahtungsoverhead).

Obwohl das bevorzugte Ausführungsbeispiel in Bezug auf Videoverarbeitung beschreiben wurde, ist für eine Fachperson ersichtlich, dass das erfindungsgemäße Verarbeitungselement auch für andere Funktionen verwendet werden kann.

Obwohl das bevorzugte Ausführungsbeispiel in Bezug auf die Xetal-Architektur beschrieben wurde, ist die Erfindung ferner auf andere Ausgestaltungen der parallelen Verarbeitungsarchitektur in gleicher Weise anwendbar.