DE60102425T2

DE60102425T2 - Optimierte Erzeugung von Hardware aus Quellprogrammen mit Multiplikationen

Info

Publication number: DE60102425T2
Application number: DE60102425T
Authority: DE
Inventors: Paul Philip Boca; Andrew Kay
Original assignee: Sharp Corp
Current assignee: Sharp Corp
Priority date: 2000-08-30
Filing date: 2001-08-23
Publication date: 2005-02-24
Anticipated expiration: 2021-08-24
Also published as: GB2366404A; US20020026305A1; US6820257B2; DE60102425D1; JP2002149728A; EP1187044B1; EP1187044A3; GB0021222D0; EP1187044A2

Description

Zu einer Synthese auf hohem Niveau (die auch als Verhaltenssynthese beschrieben wird und von D. Gajski, A. Wu, N. Dutt und S. Lin in "High-level Synthesis; introduction to chip and System design", Kluwer Academic Publishers, 1992 beschrieben ist) gehörte das automatische Kompilieren einer Beschreibung zum Verhalten einer Schaltung in einer Sprache wie Behavioural VHDL, C/C++ oder Java bis herunter auf einen äquivalenten Register-Transfer-Level(kurz RTL)-Code (z. B. K. Nishida, K. Okada, M. Ohnishi, A. Kay, P. Boca, A. Yamada und T. Kambe in "A high-level synthesis method considering synchronous communications between threads" in Proceedings of VLD '99, 1999). Bei RTL handelt es sich um Daten, die für eine Beschreibung der gewünschten Schaltung auf niedriger Ebene sorgen. Zum Kompilieren eines Quellprogramms herunter auf den RTL-Code gehört typischerweise, dass es einer Anzahl von Schritten wie folgt unterzogen wird:

(a) Als Erstes muss das Quellprogramm in eine interne Repräsentation gewandelt werden. Es existieren mehrere derartige Repräsentationen, aus denen ausgewählt werden kann, jedoch werden typischerweise Kontroll- und Datenflussgraphen (CDFGs) siehe D. Gajski, A. Wu, N. Dutt und S. Lin in "Highlevel Synthesis; introduction to chip and System design", Kluwer Academic Publishers, 1992) verwendet. Der CDFG wird durch einen als Datenflussanalyse bekannten Prozess erzeugt. Die CDFG-Knoten, die der Quellenebenenoptimierer erzeugt (siehe die 4) sind abstrakte Operationen, die Konzepten auf Quellebene entsprechen, wie Multiplikation, Verschiebung, Addition, Kommunikation usw. Zum Beispiel sind in der 4 die dort vorhandenen Kästchen mit "*" und "+" Knoten.
(b) Dann wird der CDFG optimiert. Die Optimierungen, die an der Verhaltensbeschreibung ausgeführt werden, fallen in zwei Kategorien; diejenigen, die bei Softwarecompilertechnologie bekannt sind, und diejenigen, die speziell auf eine Hardware hin zugeschnitten sind. Es ist geschickt, so viel Optimierungen wie möglich vorzunehmen, bevor man sich einer speziellen Hardwarearchitektur zuwendet, da die Größe (hinsichtlich der Siliciumfläche, d.h. der Anzahl der Gatter) für teure Operationen, wie Multiplizierer und Schieber in Hardware, deutlich gesenkt werden kann.
(c) Bindung: Dadurch werden Operationen in den CDFGS auf mögliche Funktionseinheiten (kurz FUs) abgebildet, die dazu erforderlich sein können, das Design in Hardware zu realisieren. Während der Bindung wird jeder abstrakten Operation ein geeigneter Bindungsoperator zugewiesen. Zum Beispiel kann einer abstrakten 8-Bit-Additionsoperation ein 8-Bit-Addierer zugewiesen werden; es könnte auch ein allgemeinerer Bindungsoperator zugewiesen werden, wie eine kombinierte Addier/Subtrahier-Einheit.
(d) Ablaufplan. Dieser arbeitet aus, in welchem Taktzyklus jede der Operationen im CDFG auszuführen ist, wobei diese Einschränkungen wie der Taktgeschwindigkeit und den verfügbaren Ressourcen unterliegt.
(e) Zuordnung. Dabei wird jeder Operation im CDFG eine tatsächliche FU zugewiesen. Um die Anzahl der verwendeten FUs zu minimieren, wird eine gemeinsame Nutzung ausgeführt. Dazu gehört das Verwenden derselben FU für zwei verschiedene Operationen derselben Art. Wenn z.B, in einem Taktzyklus eine 3-Bit-Addition und in einem anderen eine 6-Bit-Addition vorliegen, kann für beide Operationen eine einzelne 6-Bit-Addierer-FU verwendet werden. Während der Zuordnung wird jeder Bindungsoperator einer speziellen Instanz einer Schaltungskomponente, die als Funktionseinheit bezeichnet wird, zugeordnet. Funktionseinheiten entsprechen im Allgemeinen Instanzen von Bibliothekskomponenten in der RTL. Es existiert die Vorstellung einer allgemeinen Schaltungskomponente, z. B. eines Multiplizierers, und der Zuordner weist einer speziellen Instanz dieser Komponente einen Bindungsoperator zu. Zum Beispiel kann ein Bindungsmultiplizierer entsprechend 3 × 3 → 3 einer Funktionseinheit entsprechend 3 × 3 → 3 zugeordnet werden. So kann eine einzelne Funktionseinheit in der RTL auf niedriger Ebene dafür verantwortlich sein, mehrere abstrakte Operationen im optimierten CDFG zu implementieren.
(f) Das abschließende Stadium der Synthese auf hoher Ebene besteht darin, aus dem mit Ablaufplan versehenen CDFG RTL-Code zu erzeugen.

Es wird auf die 2 Bezug genommen, gemäß der die obigen Schritte (a) und (b) dem Optimierungsstadium auf Quellebene entsprechen und die Schritte (c) bis (f) dem Stadium der Synthese auf hoher Ebene entsprechen.
Dann kann ein Logiksynthesewerkzeug (wie der Synopsys-Designcompiler) dazu verwendet werden, die RTL in eine Beschreibung auf Gatterebene zu wandeln. Aus einer derartigen Beschreibung kann ein Chip 10 (1) hergestellt werden. (Hinweis: nicht alle Synthesesysteme auf hoher Ebene behandeln die Bindung, die Zuordnung und den Ablaufplan als drei getrennte Stadien; einige derselben kombinieren diese Stadien.)
Zu einigen Beispielen von Synthesesystemen auf hoher Ebene gehören die Folgenden: Behavioral Compiler, http://www.synopsys.com; Frontier Design, http://www.frontierd.com; C level Design, http://www.cleveldesign.com; und A. Kay, "Hardware Compiler", am 12. September 1996 eingereichte UK-Patentanmeldung Nr. 2317245.
Bei den oben genannten Sprachen auf hoher Ebene werden die Multiplikationsoperationen typischerweise homogen typisiert. Das heißt, dass die Typen (das Wort "Typ" wird in dieser Beschreibung dazu verwendet, das Vorzeichen und die Bitbreite anzugeben) der Eingangswerte für diese Operatoren dieselben wie die Typen der Ausgabe sind. Compiler für derartige Sprachen (siehe z. B. den Bach-Compiler gemäß A. Yamada, K. Nishida, R. Sakurai, A. Kay, T. Nomura und T. Kambe in "Hardware synthesis with the Bach System", ISCAS '99, 1999) fügen Typensembles automatisch so ein, dass Multiplikationen homogen sind. Benutzer werden dazu angereizt, homogene Operationen zu verwenden anstatt ihren Code von Hand auf gute Funktion zu optimieren. Dies, da Homogenität die Komplexität der Sprache reduziert, was zu Designs führt, für die die Wahrscheinlichkeit erhöht ist, dass die korrekt sind. Jedoch bestehen die Kosten, die dafür gezahlt werden, darin, dass das Design unter Umständen nicht effizient ist.
Kum et al. beschreiben in "Word-length optimization for high-level synthesis of digital Signal processing Systems" in IEEE Workshop on Signal Processing Systems 1998, SIPS'98, S. 569 bis 578 eine die Wortlänge optimierende Software zum Senken der Kosten synthetisierter integrierter Schalt kreise. Um dies zu bewerkstelligen, werden Quantisierer in einen Datenflussgraphen eingeführt, und nach dem Partitionieren des Graphen wird die minimal erforderliche Wortlänge für jedes partitionierte Signal bestimmt. Bindungs- und Zeitplanvorgänge werden unter Verwendung der minimalen Wortlänge ausgeführt. Abschließend wird die Wortlänge der einzelnen Funktionseinheiten dadurch optimiert, dass die Wortlänge ihrer Operanden erhöht wird, bis ein gewünschtes Funktionsziel erreicht ist. Operationen, die derselben Funktionseinheit zugewiesen sind, sollten dieselbe Wortlänge aufweisen. Ein Nachteil der oben beschriebenen Technik besteht darin, dass sie das Ergebnis eines Algorithmus beeinflussen kann und so nur für näherungsweise Multiplikationen geeignet ist.
Die 2 zeigt die zwei Stadien eines Hardwaredesigns auf hoher Ebene als Optimierung auf Quellebene gefolgt von einer Synthese auf hoher Ebene. Darauf folgt eine Synthese auf niedriger Ebene. Typischerweise wird zwischen der Quellebene und der ersten Syntheseebene irgendeine Art einer Datenflussrepräsentation, z. B. CDFG, verwendet.
Ein Multiplizierer nimmt zwei ganze Zahlen als Eingangswerte auf, und er liefert ihr Produkt als Ausgangswert. Multiplizierer zeigen abhängig davon, ob die Eingangswerte und der Ausgangswert als ganze Zahlen mit oder ohne Vorzeichen anzusehen sind, verschiedene Implementierungen. Insgesamt existieren acht verschiedene Fälle. Um den Gegenstand zu vereinfachen, sei hier ein einfacheres Modell betrachtet, bei dem alle Eingangs- und Ausgangswerte vorzeichenlos sind. Die unten beschriebenen speziellen Ausführungsformen decken mehrere Fälle ab.
Bei bisherigen Werkzeugen lag das "Alphabet" möglicher Multiplizierer, die zur Synthese verfügbar waren, immer in der Form (a) r × r → r oder (b) r × r → 2r vor, wobei p × p → r für einen Multiplizierer steht, dessen Eingangswerte die Breiten p und q aufweisen und dessen Ausgangswerte die Breite r aufweist. Diese Typen (a) und (b) werden hier als homogene Multiplizierer bezeichnet.
Nicht homogene Multiplizierer können in der Form p × q → r vorliegen, wobei p und q verschieden sind und größenmäßig keine Beziehung zu r zeigen müssen.
Synthesesysteme auf hoher Ebene nutzen eine Anzahl von Optimierungen für Designs zum Verringern ihrer Fläche. Eine derartige Optimierung besteht im Ersetzen von Multiplikationen der Potenz zwei durch Linksschiebeoperationen. (Eine Linksschiebeoperation wird unter Verwendung des Symbols « geschrieben.) Beispiel: x * 8 = x ≪ 3. Dies ist als Potenzreduktion bekannt (siehe G. Micheli: "Synthesis and Optimization of Digital Circuits", McGraw Hill, 1994).
Potenzreduktion gilt auch für Multiplizierer, bei denen einer der Operanden als Summe oder Differenz einer Potenz von zwei ausdrückbar ist. In derartigen Fällen kann der Multiplizierer durch eine Summe oder Differenz zweier Verschiebungen ersetzt werden. Zum Beispiel gilt: x * 7 = x ≪ 3 –x. (Hinweis: x = x ≪ 0)
Bisherige Optimierer können eine Potenzreduktion ausführen, um einen Multiplizierer vollständig wegzulassen, jedoch erzeugen sie immer eine homogene Repräsentation, um auf das Synthesestadium auf hoher Ebene überzugehen. Typischerweise verwendet irgendein spezielles Werkzeug den Typ (a) oder den Typ (b), jedoch nicht beide.
Durch die Erfindung ist ein Verfahren zum Kompilieren eines Quellprogramms zum Erzeugen von Hardware mit den folgenden Schritten geschaffen:

(a) Ausführen einer Datenflussanalyse des Quellprogramms zum Erzeugen einer Datenflussrepräsentation des Quellprogramms, die eine Anzahl von Multiplizierern enthält, von denen jeder so ausgebildet ist, dass er ein erstes und ein zweites Eingangsargument mit einer ersten bzw. einer zweiten Eingangsbitbreite aufweist und einen Ausgangswert mit einer Ausgangsbitbreite erzeugt; gekennzeichnet durch die folgenden weiteren Schritte:
(b) Optimieren der Datenflussrepräsentation in solcher Weise, dass die Eingangsbitbreiten und die Ausgangsbitbreite selbst dann verringert sind, wenn dies dazu führt, dass die Eingangsbitbreiten und die Ausgangsbitbreite für einige oder alle der Multiplizierer nicht gleich sind; und
(c) Ausführen einer Synthese auf hoher Ebene an der optimierten Datenflussrepräsentation, einschließlich einer gemeinsamen Nutzung von Funktionseinheiten, mit Eingangs- und Ausgangsbitbreiten, unter den Multiplizierern auf solche Weise, dass die zum Erzeugen der Funktionseinheiten benötigte Siliciumfläche verkleinert ist, selbst wenn dies dazu führt, dass in dieser Funktionseinheit die Eingangs- und Ausgangsbitbreiten nicht alle gleich sind.

Die Erfindung erweitert demgemäß das Alphabet möglicher Bindungsoperatorty pen (z. B. Addition, Multiplikation, Subtraktion usw.), wie sie verfügbar sind (bei einer Synthese auf hoher Ebene), um nicht-homogene Multiplizierer in die Datenflussrepräsentierung vor der Synthese auf hoher Ebene ebenso wie Homogene einzuschließen, und um die Breiten der Eingangswerte und der Ausgangswerte der Multiplizierer in diesem frühen Stadium so weit wie möglich zu verringern. Durch diese Vorgehensweise wird diese Information auf Quellebene während der Synthese auf hoher Ebene verfügbar gemacht, um die Synthese billigerer, schnellerer Schaltkreise zu ermöglichen. Multiplizierer bilden teure Hardware und ihre Größe nimmt quadratisch zu, wenn die Bitbreite zunimmt.
Um die Erfindung bei einem Synthesesystem auf hoher Ebene anzuwenden, ist es erforderlich, den Optimierer zu modifizieren, um optimierte Beschreibungen zu erzeugen; außerdem muss der Synthesizer auf hoher Ebene modifiziert werden, um die Zusatzinformation zu nutzen.
Da die Breite, oder die Anzahl der Bits der Eingangswerte und der Ausgangswerte von Multiplizierern durch die Erfindung verringert werden kann, wird diese Technik als Bitbreitenoptimierung bezeichnet.
Der Synthesizer auf hoher Ebene muss so modifiziert werden, dass er eine einzelne Bitbreite, die für eine Multiplizierer-Funktionseinheit optimiert ist, für mehrere hinsichtlich der Bitbreite optimierte abstrakte Multiplizierer-Operatoren gemeinsam nutzen kann (wenn dies zweckdienlich ist). Im einfachsten Fall sind zwei abstrakte Operatoren Kandidaten für gemeinsame Nutzung, wenn sie genau denselben Typ haben. (Für Multiplizierer wird dies bedeuten, dass sowohl die Typen der Eingangswerte als auch diejenigen der Ausgangswerte gleich sein müssen.) Dies kann für übliche Schaltkreise zu einschränkend sein, und die bevorzugte Ausführungsform gibt eine bevorzugte Erweiterung an, die mehr gemeinsame Nutzung zulässt. Gemeinsame Nutzung erfolgt tatsächlich nur dann, wenn dies der Ablaufplan zulässt und wenn der Zuordner dies wählt.
Es sei angenommen, dass es erwünscht ist, eine vorzeichenlose abstrakte Multiplikationsoperation p × q → r zu implementieren. Im Allgemeinen kann die Multiplikationsschaltung umso kleiner und schneller sein, je kleiner p, q und r gemacht werden. Das Zulassen nicht-homogener Multiplizierer bedeutet, dass (z. B.) p durch den Optimierer verkleinert werden kann, wobei q und r fest bleiben. Solange p ausreichend breit ist, um den entsprechenden Eingangswert zu repräsentieren, ist das Ergebnis korrekt. In ähnlicher Wei se kann q verkleinert werden. Schließlich kann r verkleinert werden, wenn entweder (1) r breiter als der Wert ist, wie er für den nächsten Operator im Graphen erforderlich ist oder (2) gezeigt werden kann, dass das Multiplikationsergebnis immer ausreichend klein ist, um mit weniger Bits repräsentiert zu werden.
Bei einer Synthese auf niedriger Ebene wird ein Schaltkreis mit einem Multiplizierer, der größer als erforderlich ist, häufig durch einfache Optimierungsregeln auf niedriger Ebene optimiert. Wenn z. B. ein als null bekanntes Signal mit einem anderen Signal UND-verknüpft wird, ist das Ergebnis immer null, so dass das UND-Gatter weggelassen werden kann, ohne dass das Verhalten des Schaltkreises beeinflusst wird, wobei jedoch sein Funktionsvermögen und sein Preis verbessert werden. Jedoch kann bei einer Synthese auf hoher Ebene eine einzelne Multiplizierer-Funktionseinheit von mehreren verschiedenen abstrakten Operationen gemeinsam genutzt werden, von denen jede ihre eigenen Breitenerfordernisse hat. Die spezielle Berechnung wird von Multiplexern ausgewählt, die durch eine spezielle Steuerschaltung gesteuert werden. Das Platzieren dieser Multiplexer im Schaltkreis kann den Optimierer auf niedriger Ebene 'blind' machen, so dass er keine Optimierungen erkennen kann, die er aus der Perspektive auf Quellebene als vollkommen gültig anerkennen würde.
Ein Beispiel hierfür ist in den 5 und 6 angegeben.
Es sei die 6 betrachtet (Schaltkreiszuordnung unter Verwendung des Stands der Technik). Multiplexer 62 und 63 wirken effektiv wie Schalter, um zu bestimmen, welche Eingangswerte einem Multiplizierer 64 zugeführt werden. In ähnlicher Weise wirkt ein Demultiplexer 65 wie ein Schalter zum Bestimmen, ob der Ausgangswert des Multiplizierers 64y oder z zugeführt wird. Das Schaltverhalten der Multiplexer 62 und 63 sowie des Demultiplexers 65 wird durch eine Steuerung 68 gesteuert. Wenn der linke Multiplexer 62 seinen linken Eingangswert auswählt (Register a), verfügt der linke Eingangswert in den Multiplizierer 64 über acht Bits mit Werten, die zum Kompilierungszeitpunkt nicht bestimmt werden können. Wenn der linke Multiplexer 62 seinen rechten Eingangswert auswählt (Ensemble des Registers b), ist zum Kompilierungszeitpunkt bekannt, dass die obersten fünf Bits null sind. Dies, da das Typensemble 66 den 3-Bit-Ausgangswert des Registers a auf acht Bits ändert. Jedoch kann der Logikoptimierer diese Information nicht verwenden, da er nicht weiß, ob vom Multiplexer 62 der linke oder der rechte Eingangswert ausgewählt wird. Daher kann der linke Eingangswert für den Multiplizierer 64 nicht auf weniger als acht Bits verringert werden. Daher ist eine Multiplizierer 64 entsprechend 8 × 8 → 8 erforderlich.
Alternativ kann, unter Verwendung der Erfindung, die Zuordnung zum in der 8 dargestellten Schaltkreis führen. Der Zuordner, der als eine seine Aufgaben eine gemeinsame Benutzung ausführt, nutzt die Zusatzinformation zur Größe der zwei Bindungsoperatoren, um sie gemeinsam zu nutzen und um einen einzelnen Multiplizierer entsprechend 3 × 8 → 8 zu verwenden, Der sich ergebende Schaltkreis ist daher kleiner.
In den Figuren erscheinen Bindungsoperatoren nicht tatsächlich. Die 5 ist ein CDFG vor einer Synthese auf hoher Ebene, und so sind die *'s abstrakte Operationen. In der 6 ist * eine Funktionseinheit.
Das Verfahren erlaubt es Benutzern, Code in einer Algorithmussprache zu schreiben, ohne dass sie sich übermäßig damit beschäftigen müssen, wie teuer der Code in Hardware sein wird.
Homogene Operationen sind im Allgemeinen einfacher zu verstehen als nichthomogene, so dass eine geringere Wahrscheinlichkeit dafür besteht, dass der Benutzer einen Fehler macht. Die Erfindung erlaubt es dem Benutzer, beim einfacher zu verstehenden Sprachmodell zu verbleiben, aber dennoch kompakte Schaltkreise zu erzeugen.
Nun werden Ausführungsformen spezieller, nur beispielhaft, und unter Bezugnahme auf die folgenden Zeichnungen beschrieben.
1 zeigt ein Bild eines Chips;
2 zeigt schematisch ein Design auf hoher Ebene;
3 zeigt ein Flussdiagramm zum Erläutern, wie Optimierungsregeln bei der Ausführungsform angewandt werden;
4 ist ein Beispiel eines CDFG zum Repräsentieren des Ausdrucks (x*y) + (z*w);
5 zeigt einen einen Vorsynthese-CDFG für ein kleines Beispiel;
6 zeigt ein mögliches Schaltkreisschema nach dem Betreiben des Bei spiels in der 5 mittels eines Synthesesystems auf hoher Ebene;
7 zeigt den CDFG, wie er sich durch Anwenden der Optimierungsregeln bei der Ausführungsform auf den CDFG in der 5 ergibt; und
8 zeigt ein mögliches Schaltkreisschema, wie es sich durch Anwenden der vorgeschlagenen Erweiterung (auf Synthese auf hohem Niveau) auf den CDFG in der 5 ergeben kann.
In der Beschreibung wird folgende Notation verwendet.

(a) U steht für vorzeichenlos und S steht für vorzeichenbehaftet. Vorzeichenbehaftet und vorzeichenlos entsprechen Standard-ANSI-C (siehe B.W. Kernigan und D.M. Ritchie in "The ANSI C Programming Language", Software Series, Prentice Hall, 1988). Bei einer ganzen Zahl mit Vorzeichen steht das erste Bit für eine negative Zahl, z. B. im 4-Bit-Fall: –8, 4, 2, 1. Als Beispiel repräsentiert die 4-Bit-Ganzzahl 1100 mit Vorzeichen –4 (d.h. – 8+4), wohingegen die vorzeichenlose 4-Bit-Ganzzahl 1100 12 repräsentiert (d.h. +8+4).
(b) T und T' werden so verwendet, dass sie für Vorzeichen stehen, d.h. U oder S.
(c) Ein Multiplizierer p × q → r, wobei p und q kleiner als oder gleich groß wie r sind, verfügt über Eingangswerte der Breiten p und q und einen Ausgangswert der Breite r.
(d) Die Notation *(p,q,r,T) steht für einen Multiplizierer p × q → r mit dem Vorzeichen T, wobei T entweder U oder S ist.
(e) Vorzeichenlos-#n ist ein vorzeichenloser Typ der Breite n, und vorzeichenbehaftet-#n ist ein Typ der Breite n mit Vorzeichen.
(f) σ liefert die Breite eines vorgegebenen Ausdrucks zurück. Wenn z. B. x und y wie folgt definiert sind: - vorzeichenlos-#3 x; - vorzeichenbehaftet-#4 y; gelten σx = 3 und σy = 4. Daher kann σ als Art Kurzschrift angesehen werden.
(g) (U#n)x bedeutet das Umformen (d.h. Ändern) von x in den Typ vorzeichenlos-#n, und (S#n)x bedeutet das Umformen von x auf den Typ varzeichenbehaftet-#n. Wenn n kleiner als die Breite von x ist, wird x abgeschnitten. Wenn n größer als die Breite von x ist, bestehen zwei mögliche Resultate: – wenn x vorzeichenbehaftet ist, werden n-σx Kopien des Vorzeichenbits von x mit x verbunden. Dies wird als Vorzeichenerweiterung bezeichnet. – Wenn x vorzeichenlos ist, werden n-σx Nullen mit x verbunden. So wird, beim oben angegebenen Beispiel, wenn die vorzeichenbehaftete ganze Zahl 1100 in eine vorzeichenbehaftete 5-Bit-Ganzzahl umgeformt wird, dieselbe zu 111100, was immer noch –4 (d.h. –16+8+4) repräsentiert. Wenn sie sechs Bits lang ist, wird sie zu 111100 usw. Wenn das erste Bit null ist oder wenn die ganze Zahl vorzeichenlos ist, erfolgt eine Erweiterung mit den Werten null statt den Werten eins.
(h) ⊔ erstellt das Maximum zweier Zahlen. Zum Beispiel gilt ⊔(3,4) = 4.

Es wird auch die folgende Terminologie verwendet.

(a) Ein homogener Multiplizierer der Breite r ist ein solcher entsprechend r × r → r.
(b) Ein nicht-homogener Multiplizierer ist ein solcher entsprechend p × q → r, wobei p und q kleiner als r sind.
(c) Eine Operation ist kommutativ, wenn ihre Argumente vertauscht werden können. Eine Multiplikation ist kommutativ (z. B. 5*3 = 3*5.)
(d) Eine Umformung ist eine Operation, die den Typ einer ganzen Zahl ändert, und sie wird durch "Typumformung" ausgeführt.

Regeln werden in der Form e → f, falls P angegeben, wobei e und f Ausdrücke sind, und P eine Bedingung ist. Diese Regel ist wie folgt zu lesen: "Ersetze e durch f, wenn e P genügt". Für einige Regeln existieren typischerweise verschiedene Resultate für verschiedene Werte P. Damit nicht für jedes P eine gesonderte Regel angegeben werden muss, wird die Notation auf die folgende Weise erweitert:

e → f₁, wenn p₁
f₂, wenn p₂
f_k, wenn p_k

Dies ist wie folgt zu lesen: "wenn e p₁ genügt, ist e durch f₁ zu ersetzen. Wenn e p_k genügt, ist e durch fk zu ersetzen". Es sei angenommen, dass e nur einer der Bedingungen genügen kann.
Regeln zur gemeinsamen Nutzung abstrakter Multiplikationsoperatoren werden wie folgt ausgedrückt: op1, op2 → fu wobei op1 und op2 abstrakte Multiplikationsoperatoren sind und fu eine Funktionseinheit ist. Diese Regel ist wie folgt zu lesen: "op1 und op2 benutzen beide gemeinsam fu".
Ein Kontroll- und Datenfluss-Datengraph (kurz CDFG) besteht aus Knoten und Kanten. Jede abstrakte Operation in der Quellsprache verfügt über ihre eigene Knotenart.
Knoten sind durch Kanten miteinander verbunden. Es existieren zwei Kantenarten: eine Steuerkante und eine Datenkante. Es wird eine CDFG-Standardform verwendet, wie von der Art, wie sie von D. Gajski, A. Wu, N. Dutt und S. Lin in "High-level synthesis: introduction to chip and system design", Kluwer Academic Publishers, 1992 beschrieben ist.
Als Beispiel sei der Ausdruck (x*y) + (z*w) betrachtet, bei dem x, y, z und w jeweils vom selben Typ sind. Ein diesen Ausdruck repräsentierender CDFG ist in der 4 angegeben. Es ist zu beachten, dass jede der Operationen * und + ein Knoten (als Kasten dargestellt) entspricht. Kanten (als Pfeile dargestellt) führen von x und y in einen der Multiplizierer, und Kanten führen von z und w in den anderen Multiplizierer. Die Ausgänge der Multiplizierer führen in den Additionsknoten. Diese Kanten sind Datenkanten und sie zeigen den Datenfluss durch den Graphen.
Es werden CDFGs dazu verwendet, Programme zu repräsentieren, bevor irgendeine Synthese auf hoher Ebene angewandt wird. Aus diesem Grund werden diese als Vorsynthese-CDFGs bezeichnet.
Bei den hier beschriebenen Ausführungsformen sind der CDFG-Optimierer und das Synthesesystem auf hoher Ebene erweitert. Diese Erweiterungen werden nun beschrieben.
Der CDFG-Optimierer (wobei es sich um eine Softwaremaschine handelt, die CDFG-Optimierungen anwendet) ist dadurch erweitert, dass einige neue Regeln hinzugefügt sind, um die Breiten der Eingangswerte und der Ausgangswerte von Multiplizierern auf das Minimum zu verringern.
Jede Anwendung einer Regel verwendet einen CDFG als Eingangsgröße und liefert einen CDFG als ihre Ausgangsgröße zurück.
Die Regeln sind wiederholt anzuwenden (wie es durch das Flussdiagramm in der 3 dargestellt ist).
Um die Beschreibung zu unterstützen, werden der Eingangswert und der Ausgangswert der Regeln unter Verwendung einer Horizontalnotation geschrieben. Diese Notation entspricht dem Ausdruck, der das CDFG-Fragment repräsentiert. Außerdem sei, der Einfachheit halber, angenommen, dass die Regeln für Ausdrücke der Form ((T#p)x)*(p,q,r,T)((T#q)y) gelten, wobei T entweder U oder S ist und sowohl p als auch q kleiner als oder gleich groß wie r sind. Es geht keine Allgemeinheit verloren, wenn diese Annahme getroffen wird, da zusätzliche Umformungen dazu verwendet werden können, Ausdrücke in die obige Form zu wandeln. Zum Beispiel entspricht der Ausdruck x*(p,q,r,T)((T#q)y) dem Folgenden ((T#(σs))x)*(p,q,r,T)((T#q)y), wenn x das Vorzeichen T hat.
Die Regeln 0 bis 3 betreffen eine Verringerung der Breiten von Eingangswerten.
Regel 0 ((T#p)x)*(p,q,r,T)((T#q)y) → (T#r)(x*(σx,σy,r,T')y), wenn σx < p und σy < q gelten. wobei T und T' entweder U und S oder S und U sind und x und y beide das Vorzeichen T' tragen.
Diese Regel entfernt die Umformungen von den Argumenten zu den Multiplizierern, ändert den Typ des Multiplizierers von p × q → r auf (σx) x (σy) → r und führt eine Umformung ein, um das Ergebnis auf das Vorzeichen T zurückzuwandeln.
Regel 1 ((T#P)x)*(p,q,r,T)((T#4)y) ((T#p)x)*(p,q,r,T)((T*q)y), wenn p≤σx&g≤σy gelten. ((T#p)x)*(p,σ,y,r,T)y, wenn p<≤σx&q≤σy gelten. x*(σx,q,r,Z)((T#q)y), wenn p>σx&q≤σy gelten. x*(σx,σy,r,T)y, wenn p>σx&q>σy gelten. wobei T entweder S oder U ist und die Vorzeichen von x und y ebenfalls T sind. Hier erfolgt eine Erläuterung der Regel.
Die Zeile p ≤ σx & q ≤ σy sagt, dass dann, wenn p und q kleiner als oder gleich groß wie die Breiten von x bzw. y sind, keine Optimierung auszuführen ist.
Die Zeile p ≤ σx & q > σy sagt, dass dann, wenn p nicht breiter als die Breite von x ist und q breiter als die Breite von y ist, die Umformung von y zu entfernen ist und der Typ des Multiplizierers auf p x (σy) → r zu ändern ist.
Die Zeile p > σx & q ≤ σy entspricht der vorigen Zeile, jedoch mit der Ausnahme, dass die Umformung von x weggenommen wird und der Typ des Multiplizierers auf (σx) x q → r geändert wird.
Die Zeile p > σx & q > σy sagt, dass dann, wenn p und q breiter als die Breiten von x bzw. y sind, beide Umformungen weggenommen werden können und der Typ des Multiplizierers auf (σx) x (σy) → r geändert wird.
Regel 2 ((U#p)x)*(p,q,r,U)((U#q)Y) ((U#p)x)*(p,q,r,U)((U*q)y), wenn p≤σx&q≤σy gelten. ((u#P)x)*(P,Φ(y,q)rU)((U#(Φ(y,q)))Y), wenn p≤σx&q>σy gelten. ((U#(Φ(x,p)))x)*(Φ(x,p),q,r,U)((u#q)Y), wenn p>σx&q≤σy gelten. ((U#(Φ(x,p)))x)*(Φ(x,p),Φ(y,q),r,U)((U*(Φ(y,q)))Y), wenn p>σx&q>σy gelten. wobei x und y verschiedene Vorzeichen aufweisen (d.h., der eine Wert ist vorzeichenbehaftet und der andere ist vorzeichenlos) und Φ wie folgt definiert ist: Φ(x,n) = σx, wenn x vorzeichenlos ist = n, wenn x vorzeichenbehaftet ist;
Die Funktion Φ erhält einen Ausdruck x und eine Zahl n, und sie liefert die Breite von x zurück, wenn x vorzeichenlos ist. Wenn x vorzeichenbehaftet ist, liefert Φ n zurück. Nun wird die Regel 2 erläutert.
Die Zeile p ≤ σx & q ≤ σy sagt, dass dann, wenn p und q schmaler als oder gleich groß wie die Breiten von x bzw, y sind, keine Optimierung auszuführen ist.
Die Zeile p ≤ σx & q > σy sagt, dass dann, wenn p nicht breiter als die Breite von x ist und q breiter als die Breite von y ist, das erste Argument nicht zu ändern ist, aber das zweite Argument durch (U#(φ(y,q)))y zu ersetzen ist. Der Ausdruck, in den diese Umformung erweitert wird, hängt vom Vorzeichen von q ab: (U#(φ(y,q)))y wird auf (U#(σ,q))y erweitert, wenn y vorzeichenlos ist, und auf (U#q)y, wenn y vorzeichenbehaftet ist. Der Typ des Multiplizierers wird auf p x (φ(y,q))→r geändert.
Die Zeile p > σx & q ≤ σy ist der vorigen Zeile mit der Ausnahme ähnlich, dass das erste Argument modifiziert wird und der Multiplizierer auf den Typ x(φ(y,q)) → r geändert wird.
Die Zeile p > σx & q > σy sagt, dass dann, wenn p und q breiter als die Breiten von x bzw. y sind, die Möglichkeit besteht, die Breiten von x und y zu verringern. Ob eine Verringerung erfolgt, hängt von den Vorzeichen von x und y ab. Der Typ des Multiplizierers wird auf (φ(x,p) x (φ(y,q)) → r geändert.
Regel 3 ((S#p)x)*(p,q,r,S)((S#q)y) ((S#p)x)*(p,q,r,S)((S*q)y), wenn p≤σx&q≤σy gelten. ((S#p)x)*(p,Ψ(y,q)S)((S#(Ψ(y,q)))y), wenn p≤σx&q>σy gelten. ((S#(Ψ(x,p)))x)*(Ψ(x,p),q,r,S)((S#q)y), wenn p>σx&q≤σy gelten. ((S#(Ψ(x,p)))x)*(Ψ(x,p),Ψ(y,q),r,S)((S*(Ψ(y,q)))y). wenn p>σx&q>σy gelten. wobei die Vorzeichen von x und y verschieden sind und Ψ wie folgt definiert ist: Ψ(x,n) = 1 + σx, wenn x vorzeichenlos ist = n, wenn x vorzeichenbehaftet ist;
Diese Regel ist der Regel mit der Ausnahme ähnlich, dass die Umformungen mit Vorzeichen versehen sind und die Funktion Ψ an Stelle von Φ verwendet ist. Die Funktion Ψ unterscheidet sich von Φ dadurch, dass ein Zusatzbit verwendet wird, wenn x vorzeichenlos ist. Das Zusatzbit ist erforderlich, da vorzeichenbehaftete Zahlen ein Bit zum Speichern des Vorzeichens verwenden.
Die Regeln 4 und 5 stehen mit einer Verringerung der Breite der Ausgangswerte in Zusammenhang.
Häufig werden bei Berechnungen nur einige der Bits im Ergebnis einer Multiplikation benötigt. Dies zeigt sich selbst in einem CDFG als Umformung des Ausgangswerts eines Multiplizierers. Es werden nun einige Regeln beschrieben, die die Breite von Multiplizierern in dieser Situation verringern. Dadurch kann die Möglichkeit eingeführt werden, dass die Regeln 0 bis 3 dazu angewandt werden, eine weitere Bitbreitenoptimierung von Multiplizie rern auszuführen. In diesem ganzen Abschnitt werden T und T' so verwendet, dass sie entweder für U und S oder für S und U stehen.
Die erste angegebene Regel gilt für Multiplizierer, deren Vorzeichen dasselbe wie das des Umformungswerts ist.
Regel 4 (T#n)(x*(p,q,r,T)y) → (T#n)(x*(p,q,r,T)y), wenn n > r gilt. ((T#n)x)*(n,n,n,T)((T#n)y), wenn n≤r & n<p & n<q gelten. ((T#n)x)*(n,q,n,T)y, wenn n≤r & n<p & n≥q gelten. x*(p,n,n,T)((T#n)y), wenn n≤r & n≥p & n<q gelten. x*(p,q,n,T)y, wenn n≤r & n≥p & n≥q gelten.
Nun wird erläutert, was diese Regel ausführt.
Zeile n > r: wenn die Breite des Ensembles größer als die Breite des Umformungswerts größer als die Breite des Ausgangswerts des Multiplizierers ist, bleibt der Ausdruck unverändert.
Die anderen Zeilen behandeln die verschiedenen Fälle, bei denen es möglich ist, den Ausgangswert des Multiplizierers zu verkürzen.
Zeile n ≤ r & n < p & n < q: wenn die Breite des Umformungswerts kleiner als die Breiten der Eingangswerte für den Multiplizierer ist, sind die Eingangswerte umzuformen und der Multiplizierer auf n × n → n zu ändern.
Die Zeile n ≤ r & n < p & n ≥ q sagt, dass dann, wenn die Breite des Umformungswerts kleiner als die Breite des ersten Arguments (jedoch nicht des zweiten) ist, ein Umformungswert einzufügen ist, um die Breite des ersten Arguments zu verringern, und der Typ des Multiplizierers auf n × q → n zu ändern ist.
Die Zeile n ≤ r & n ≥ p & n < q entspricht der vorigen Zeile mit der Ausnahme, dass sie das zweite Argument verkürzt (durch Einfügen eines Umformungstyps), wobei der Typ des Multiplizierers auf p × n → n geändert wird.
Die Zeile n ≤ r & n ≥ p & n ≥ q sagt, dass dann, wenn n größer als oder gleich groß wie sowohl p als auch q ist, der Umformungswert entfernt werden kann und der Typ des Multiplizierers auf p × q → n geändert werden kann.
Die nächste Regel behandelt den Fall, dass sich das Vorzeichen des Multiplizierers von dem des Umformungswerts unterscheidet.
Regel 5 (T#n)(x*(p,q,r,T')y) → (T#n)(T'#n)(x*(p,q,r,T')y))
Dann kann die Regel 4 angewandt werden. Der zusätzlich eingefügte Umformungswert ist hinsichtlich der Hardware billig, und er würde durch ein Logiksynthese-Werkzeug entfernt werden. Alternativ könnte eine Optimierung auf hoher Ebene auf den Vorsynthese-CDFG angewandt werden, um Umformungswerte zu entfernen. Das Implementieren einer derartigen Optimierung zeigt einen anderen Vorteil, wie es im Unterabschnitt betreffend Regeln zum Entfernen von Umformungswerten erörtert ist.
Die Regel 6 betrifft eine Vereinfachung der Zuordnung.
Aus der Kommutativität der Multiplikation kann Nutzen dahingehend gezogen werden, eine stärkere gemeinsame Verwendung von Funktionseinheiten zuzulassen. Im Stadium vor der Bindung können die Argumente für Multiplikationsknoten so vertauscht werden, dass die Breite des ersten Arguments immer kleiner als die des zweiten, oder gleich groß, ist. Die folgende Regel erzielt dies.
Regel 6 x*(p,q,r,T)y → y*(q,p,r,T)x, wenn p < q gilt. x*(p,q,r,T)y, wenn p ≥ q gilt.
Typischerweise existieren in einem Vorsynthese-CDFG "Ketten" von Umformungswerten, d.h. Ausdrücke der Form (T₁#n₁) ((T₂#n₂)(...((T_k#n_k)x)) mit k 2, wobei die Werte T_i entweder U oder S sind. Das Vorliegen derartiger Ketten kann die Anwendung der Regeln verhindern, wie sie für die Bitbreite optimierende Multiplizierer beschrieben wurden. Daher wird vorgeschlagen, das Optimierungen zum Vereinfachen von Ketten von Umformungswerten auf bekannte Weise in einen CDFG-Optimierer eingeschlossen werden sollten.
Der Synthesizer auf hoher Ebene wird dadurch erweitert, dass Regeln 7 und 8 für gemeinsame Nutzung nicht-homogener Multiplikationsoperatoren hinzugefügt werden. Als Beispiel sei angenommen, dass in einem Taktzyklus der Wert *(3,4,8,U) und in einem anderen Wert *(3,5,8,U) vorliegt, wobei dann bei den Multiplikationsoperationen dieselbe FU gemeinsam nutzen können, die zumindest *(3,5,8,U) ist. Für diese Regeln werden zwei Beispiele angegeben. Die erste Regel gilt für abstrakte Multiplikationsoperationen mit demselben Vorzeichen.
Regel 7 *(p,q,r,T), *ip',q',r',T) → *( ⊔ (q,q'), ⊔ (r,r'),T) wobei T entweder U oder S ist. Es ist zu beachten, dass * rechts vom Pfeil für eine Funktionseinheit steht, wohingegen die Werte * links vom Pfeil abstrakte Operationen sind. Dies sollte zu keinerlei Verwirrung führen, da der Kontext der Regel den Gegenstand klar stellt.
Wenn ein Multiplizierer vorzeichenbehaftet ist und der andere vorzeichenlos ist, besteht eine Wahlmöglichkeit für die zu verwendende Multiplizierer-Funktionseinheit. Jedoch ist es billiger, eine vorzeichenlos FU zu verwenden.
Regel 8 *(p,q,r,S),*(P',a',r',U)→*(⊔ (p,p'), ,⊔(q,q'), ⊔ (r,r'),U)
Diese Regel ist vernünftig, da vorzeichenlose Multiplizierer an Stelle solcher mit Vorzeichen verwendet werden können (wie es leicht bewiesen werden kann).
Bei einer alternativen Ausführungsform kann der CDFG-Optimierer so modifiziert werden, dass vorzeichenbehaftete Multiplizierer in solche ohne Vorzeichen modifiziert werden und die Regel 7 für die gesamte gemeinsame Nutzung von Multiplizierern verwendet wird.
Nun erfolgt ein Beispiel zum Veranschaulichen des Obigen. Das Beispiel betrifft das folgende Codefragment:

y = a*b;
z = c*d;
w = y+z;
wobei die Variablen a, b, c, d, y, z und w von den folgenden Typen sind:
vorzeichenlos-#8 a, d, y, z, w;
vorzeichenlos-#3 b, c;

Eine CDFG-Repräsentation dieses Fragments ist in der 5 gezeigt. Da die Multiplikationsoperation homogen ist, müssen die Typumformungen 52 und 54 eingefügt werden, um b und c auf 8 Bits zu verbreitern. Ein Synthesesystem auf hoher Ebene führt einen Ablaufplan für diese Operationen aus und sorgt für eine gemeinsame Nutzung.
In der 6 ist ein mögliches Schaltkreisschema dargestellt, wie es sich ergeben kann, wenn dieses Beispiel ein Synthesesystem auf hoher Ebene durchläuft. (Der Einfachheit halber ist die Addition ignoriert.) Es ist zu beachten, dass im Graphen der 6 zwei Multiplexer 62 und 63 vorhanden sind, von denen beide über Eingangswerte und Ausgangswerte der Breite 8 verfügen. Die Ausgangswerte dieser Multiplexer 62 und 63 werden in eine Multiplikationsoperation 64 entsprechend 8 × 8 → 8 eingegeben.
Nun sei angenommen, dass die Erfindung angewandt wird. Durch Anwenden der Optimierungsregeln 1 und 6 auf den CDFG in der 5 werden die zwei Umformungswerte 52 und 54 entfernt und die Argumente eines der Multiplizierer vertauscht, so dass sich der CDFG in der 7 ergibt. Wenn dieser CDFG nun an ein Synthesesystem auf hoher Ebene geliefert wird, das durch die Erfindung erweitert wurde, könnte ein Schaltkreisschema wie das in der 8 erzeugt werden. Es ist zu beachten, dass einer der Multiplexer 82 eine Ausgangswertbreite von drei und der andere, 84, eine Ausgangswertbreite von acht aufweist. Die Ausgangswerte dieser Multiplexer werden in eine Multiplikationoperation 80 entsprechend 3 × 8 → 8 eingegeben. Die Multiplexer 82 und 84 sowie ein Demultiplexer 86 werden durch eine Steuerung 88 gesteuert.
Wie es im Anspruch 5 angegeben ist, ist die Erfindung nicht auf Multiplikationsoperatoren beschränkt, deren Eingangswerte und Ausgangswerte dasselbe Vorzeichen tragen. Die Erfindung kann wie folgt bei Multiplizierern angewandt werden, deren Eingangswerte und Ausgangswerte verschiedene Vorzeichen tragen:

(a) im Vorsynthese-CDFG werden die durch die obigen Regeln beschriebenen Optimierungen angewandt;
(b) nachdem alle Optimierungen angewandt wurden, wird ein weiterer Transformationsdurchlauf hinzugefügt, um überflüssige Umformungswerte zu entfernen, wodurch sich Multiplikationsknoten ergeben, deren Eingangswerte und Ausgangswerte nicht notwendigerweise dasselbe Vorzeichen tragen; und
(c) die gemeinsamen Nutzungsregeln 7 und 8 werden entsprechend modifiziert.

Bei einigen Synthesesystemen auf hoher Ebene verfügt die zum Beschreiben von Hardware verwendete Quellensprache über Multiplikationen, deren Ausgangswertbreite doppelt so groß wie die der Eingangswertbreiten ist. Die Erfindung kann wie folgt auch bei derartigen Multiplizierern angewandt werden:

(a) auf der Vorsynthese-CDFG-Ebene werden r × r → 2r entsprechende Multiplizierer in solche gewandelt, die r × r → r entsprechen;
(b) die oben beschriebenen Optimierungsregeln werden angewandt;
(c) in einem gesonderten Transformationsdurchlauf werden p × q → r entsprechende Multiplizierer in solche gewandelt, die p × q → 2r entsprechen; und
(d) es werden die Gemeinsamnutzungsregeln 7 und 8 verwendet.

Claims

Verfahren zum Kombinieren eines Quellprogramms zum Erzeugen von Hardware, mit dem folgenden Schritt: (a) Ausführen einer Datenflussanalyse des Quellprogramms zum Erzeugen einer Datenflussrepräsentation des Quellprogramms, die eine Anzahl von Multiplizierern enthält, von denen jeder so ausgebildet ist, dass er ein erstes und ein zweites Eingangsargument mit einer ersten bzw. einer zweiten Eingangsbitbreite aufweist und einen Ausgangswert mit einer Ausgangsbitbreite erzeugt; gekennzeichnet durch die folgenden weiteren Schritte: (b) Optimieren der Datenflussrepräsentation in solcher Weise, dass die Eingangsbitbreiten und die Ausgangsbitbreite selbst dann verringert sind, wenn dies dazu führt, dass die Eingangsbitbreiten und die Ausgangsbitbreite für einige oder alle der Multiplizierer nicht gleich sind; und (c) Ausführen einer Synthese auf hoher Ebene an der optimierten Datenflussrepräsentation, einschließlich einer gemeinsamen Nutzung von Funktionseinheiten, mit Eingangs- und Ausgangsbitbreiten, unter den Multiplizierern auf solche Weise, dass die zum Erzeugen der Funktionseinheiten benötigte Siliciumfläche verkleinert ist, selbst wenn dies dazu führt, dass in dieser Funktionseinheit die Eingangs- und Ausgangsbitbreiten nicht alle gleich sind.
Verfahren nach Anspruch 1, bei dem es zum Schritt (a) gehört, einen Steuer- und Datenflussgraphen als Datenflussrepräsentation zu erzeugen.
Verfahren nach Anspruch 1 oder 2, bei dem es zum Schritt (b) gehört, die Datenflussrepräsentation so zu optimieren, dass zumindest einer der Multiplizierer in der optimierten Datenflussrepräsentation Eingangsbitbreiten und eine Ausgangsbitbreite aufweist, die nicht alle gleich sind.
Verfahren nach einem der vorstehenden Ansprüche, bei dem jeder Multiplizierer vorzeichenbehaftet oder vorzeichenlos ist.
Verfahren nach einem der vorstehenden Ansprüche, bei dem es zum Optimierungsschritt gehört, eine von Regeln 0 bis 5 anzuwenden, die wie folgt definiert sind: Regel 0 ((T#p)x)*(p,q,r,T)((T#q)y) → (T#r)(x*(σx,σy,rT')y), wenn σx<p&σy<q gelten, wobei T und T' entweder U und S oder S und U sind und x und y beide das Vorzeichen T' tragen; Regel 1 ((T#p)x)*(p,q,r,T)((T#q)y) → ((T#p)x)*(p,q,r,T)((T*q)y), wenn p≤σx&q≤σy gelten. ((T#p)x)*(p,σ,y,r,T)y, wenn p≤σx&q≤σy gelten. x*(σx,q,r,Z)((T#q)y), wenn p>σx&q≤σy gelten. x*(σx, σy,r,T)y, wenn p>σx&q>σy gelten. wobei T entweder S oder U ist und die Vorzeichen von x und y ebenfalls T sind; Regel 2 ((U#P)x)*(p,q,r,U)((U#4)y) ((U#p)x)*(p,q,r,U)((U*q)y), wenn p≤σx&q≤σy gelten. ((Uu#p)x)*(p,Φ(y,q)rU)((U#(Φ(y,q)))y), wenn p≤σx&q>σy gelten. ((U#(Φ(x,p)))x)*(Φ(x,p),q,r,U)((U#q)y), wenn p>σx&q≤σy gelten. ((U#(Φ(x,p)))x)*(Φ(x,p),Φ(y,q),r,U)((U*(Φ(y,q)))y), wenn p>σx&q>σy gelten. wobei von den Werten x und y einer S ist und der U ist und Φ wie folgt definiert ist: Φ(x,n) = σx, wenn x U ist = n, wenn x S ist; Regel 3 ((S#p)x)*(P,q,r,S)((S#q)y) ((S#p)x)*(p,q,r,S)((S*q)y), wenn p≤σx&q≤σy gelten. ((S#p)x)*(p,Ψ(y,q)S)((S#(Ψ(y,q)))y). wenn p≤σx&q>σy gelten. ((S#(Ψ(x,p)))x)*(Ψ(x,p),q,r,S)((S#q)Y), wenn p>σx&q≤σy gelten. ((S#(Ψ(x,p)))x)*(Ψ(x,p),Ψ(y,q),r,S)((S*(Ψ(y,q)))y). wenn p>σx&q>σy gelten. wobei von den Werten x und y einer S ist und der andere U ist und Ψ wie folgt definiert ist: Ψ(x,n) = 1 + σx, wenn x U ist = n, wenn x S ist; Regel 4 (T#n)(x*(p,q,r,T)y) → (T#n)(x*(p,q,r,T)y), wenn n > r gilt. ((T#n)x)*(n,n,n,T)((T#n)y), wenn n≤r & n<p & n<q gelten. ((T#n)x)*(n,q,n,T)y, wenn n≤r & n<p & n≥q gelten, x*(p,n,n,T)((T#n)y), wenn n≤r & n≥p & n<q gelten. x*(p,q,n,T)y, wenn n≤r & n≥p & n≥q gelten. Regel 5 (T#n)(x*(p,q,r,T')y) → (T#n)(T'#n)(x*(p,q,r,T')y)), gefolgt von einer Anwendung der Regel 4; wobei: – U vorzeichenlos bezeichnet und S vorzeichenbehaftet bezeichnet; – T und T' Vorzeichen bezeichnen (d. h. U oder S); – ein Multiplizierer entsprechend p×p → r, wobei p und q kleiner als oder gleich groß wie r sind, Eingangswerte der Breite p und q und einen Ausgangswert der Breite r aufweist; – *(p,q,r,T) einen Multiplizierer entsprechend p×q → r mit dem Vorzeichen T bezeichnet, wobei T entweder U oder 5 ist; – vorzeichenlos-#n ein vorzeichenloser Typ der Breite n ist und vorzeichenbehaftet-#n ein vorzeichenbehafteter Typ der Breite n ist; – σ die Breite eines vorgegebenen Ausdrucks zurückliefert; und – (U#n)x eine Umformung von x auf den Typ vorzeichenlos-#n bedeutet und (S#n)x eine Umformung von x auf den Typ vorzeichenbehaftet-#n bedeutet.
Verfahren nach einem der vorstehenden Ansprüche, bei dem der gemeinsame Nutzungsschritt das Anwenden einer von Regeln 6, 7 oder 8 beinhaltet, um dadurch eine gemeinsame Nutzung der Funktionseinheit zu erlauben, wobei die Regeln 6, 7 und 8 wie folgt definiert sind: Regel 6 x*(p,q,r,T)y → y*(q,p,r,T)x, wenn p < q gilt. x*(p,q,r,T)y, wenn p ≥ q gilt. Regel 7 *(p,q,r,T), *(p',q',r',T) → *(⊔(q,q'), ⊔(r,r'),T ) wobei T entweder U oder S ist; oder Regel 8 *(p,q,r,s),*(p',q',r',U)→*( ⊔(P,P'), ⊔(q,q'), ⊔ (r,r'),U); wobei: – U vorzeichenlos bezeichnet und S vorzeichenbehaftet bezeichnet; – T und T' Vorzeichen bezeichnen (d. h. U oder S); – ein Multiplizierer entsprechend p×p → r, wobei p und q kleiner als oder gleich groß wie r sind, Eingangswerte der Breite p und q und einen Ausgangswert der Breite r aufweist; – *(p,q,r,T) einen Multiplizierer entsprechend p×q → r mit dem Vorzeichen T bezeichnet, wobei T entweder U oder S ist; – vorzeichenlos-#n ein vorzeichenloser Typ der Breite n ist und vorzeichenbehaftet-#n ein vorzeichenbehafteter Typ der Breite n ist; – σ die Breite eines vorgegebenen Ausdrucks zurückliefert; – (U#n)x eine Umformung von x auf den Typ vorzeichenlos-#n bedeutet und (S#n)x eine Umformung von x auf den Typ vorzeichenbehaftet-#n bedeutet; und – ⊔ das Maximum der zwei Zahlen ergibt.