DE19860062A1

DE19860062A1 - Verfahren der erzwungenen Registerteilung für die Konstruktion von leistungsarmen VLSI

Info

Publication number: DE19860062A1
Application number: DE19860062A
Authority: DE
Inventors: Anand Raghunathan; Sujit Dey; Ganesh Lakshminarayana; Niraj Jha
Original assignee: NEC Corp; Princeton University
Current assignee: NEC Corp; Princeton University
Priority date: 1997-12-23
Filing date: 1998-12-23
Publication date: 1999-07-01
Also published as: JP2000057201A; US6195786B1; JP3150122B2

Description

IA. Gebiet der Erfindung

Diese Erfindung bezieht sich auf die Reduktion des Lei stungsverbrauchs für digitale VLST-Folgeschaltungen. Genauer bezieht sich diese Erfindung auf ein System und auf ein Verfahren zum Reduzieren des Leistungsverbrauchs unter Verwendung von Verfahren der erzwungenen Register teilung. Diese Erfindung ist in einem System der erzwun genen Registerteilung und in Verfahren zum Reduzieren des Leistungsverbrauchs in einer Folgeschaltung unter Verwen dung der erzwungenen Registerteilung ausgeführt.

IB. Hintergrund

In VLSI-Schaltungen wird die Leistungsdissipation häufig von der dynamischen Komponente dominiert, die jedesmal erlitten wird, wenn Signale in einer Schaltung einen Logikübergang erfahren. In der Praxis ist ein großer Bruchteil solcher Übergänge, die während des Betriebs üblicherweise verwendeter Schaltungen erlitten werden, unnötig. Solche Übergänge haben keinen Einfluß auf das von der Schaltung berechnete Ergebnis.

Sinnvollerweise kann gefolgert werden, daß möglicherweise nicht alle Teile einer Schaltung während jedes Taktzyklus zu arbeiten brauchen. Einige Komponenten können in eini gen Taktzyklen im Leerlauf sein. Unter Anerkennung dieser Tatsache wurden mehrere leistungsarme Konstruktionsver fahren vorgeschlagen, die darauf beruhen, daß unnötige Signalübergänge unterdrückt oder beseitigt werden. Im allgemeinen wird zur Bezeichnung solcher Verfahren der Begriff Power Management verwendet. Die Anwendung des Power Managements auf eine Konstruktion umfaßt zwei Schritte:

- Identifizieren der Leerlaufzustände für verschie dene Teile der Schaltung.
- Neukonstruieren der Schaltung zum Beseitigen der Schaltaktivität in den Leerlaufkomponenten, somit Vermeiden unnötiger Leistungsdissipation in diesen Teilen.

Das Power Management wird häufig von Konstrukteuren energiesparender Systeme entwickelt und ist vielleicht eines der am häufigsten verwendeten leistungsarmen Kon struktionsverfahren. Siehe J. Rabaey und M. Pedram (Herausgeber), Low Power Design Methodologies., Kluwer Academic Publishers, Norwell, MA, (1996). Ebenso ist es wünschenswert, ein in automatische Synthese-Hilfsmittel integriertes Power Management zu besitzen.

Viele moderne Mikroprozessoren wenden die Strategie an, den Takteingang mit Registern und anderen Schaltungsblöc ken zu verknüpfen, um unnötige Übergänge in dem Taktsi gnal sowie in dem betrachteten Schaltungsblock zu unter drücken. Siehe A. Correale, "Overview of power minimiza tion techniques employed in the IBM PowerPC 4xx embedded processors", Proc. Int. Symp. Low Power Design, S. 75-80 (Apr. 1995). Automatische Syntheseverfahren zum Anwenden der Taktverknüpfung und zum Maximieren ihrer Effizienz sind ebenfalls bekannt. Siehe G. Tellez, A. Farrahi und M. Sarrafzadeh, "Activity driven clock design for low power circuits.", Proc. Int. Conf. Computer-Aided Design, S. 62-65, (Nov. 1995) und L. Benini, P. Siegel und G. DeMicheli, "Saving power by synthesizing gated clocks for sequential circuits", IEEE Design & Test of Computers, S. 32-41, (Winter 1994).

Unlängst wurden höhere Syntheseverfahren für das Power Management vorgeschlagen. Siehe E. Musoll und J. Corta della, "High-level synthesis techniques for reducing the activity of functional units", Proc. Int. Symp. Low Power Design, S. 99-104, (Apr. 1995); J. Monteiro, S. Devadas, P. Ashar und A. Mauskar, "Scheduling techniques to enable power management", Proc. Design Automation Conf., S. 349-352 (Juni 1996) und A. Raghunathan, S. Dey, N. K. Jha und K. Wakabayashi, "Power management techniques for control-flow intensive designs", Proc. Design Automation Conf. S. 429-434 (Juni 1997). Ein auf das Maximieren der Leerlaufzeiten für die Funktionseinheiten gerichteter Planungsalgorithmus wurde in J. Monteiro, S. Devadas, P. Ashar und A. Mauskar, "Scheduling techniques to enable power management", Proc. Design Automation Conf., S. 349-352 (Juni 1996) vorgestellt.

Ein Controller-Neuspezifizierungsverfahren auf der Grund lage der Neukonstruktion der Controller-Logik zum Redu zieren der Aktivität in den Komponenten des Datenpfads wurde in A. Raghunathan, S. Dey, N. K. Jha und K. Wakaba yashi, "Power management techniques for control-flow intensive designs", Proc. Design Automation Conf., S. 429-434 (Juni 1997) vorgestellt. Verfahren, die auf das Maximieren der "Schlafzeiten" der Ablageelemente wie etwa der Register und der Speicher gerichtet sind, wurden in A. Farrahi, G. Tellez und M. Sarrafzadeh, "Memory segmentation to exploit sleep mode operation", Proc. Design Automation Conf., S. 36-41 (Juni 1995) vorge stellt. Auf der Logikebene wurden zwei erfolgreiche Power Management-Verfahren auf der Grundlage der geschützten Bewertung und der Vorausberechnung vorgestellt. Siehe V. Tiwari und S. Malik, "Guarded evaluation: Pushing power management to logic level synthesis design", Proc. Int. Symp. Low Power Design, S. 221-226 (Apr. 1995) und M. Aldina, J. Monteiro, S. Devadas, A. Gosh und M. Pa paefthymiou, "Precomputation based sequential logic optimization for low power", IEEE Trans. VLSI Systems, Bd. 2, S. 426-436.

Die geschützte Bewertung identifiziert Logikkegel, die bei bestimmten Eingangszuständen abgeschaltet werden können. Diese Logikkegel werden durch Zwischenspeicher "geschützt", die gesperrt werden, wobei somit verhindert wird, daß der Logikkegel Leistung verbraucht, wenn der Ausgang des Kegels das Ausgangssignal der Schaltung nicht beeinflußt. Bei der Vorausberechnung wird zu der ur sprünglichen Schaltung ein einfaches, die Vorausberech nungsschaltung genanntes Schaltnetz hinzugefügt. Bei gewissen Eingangszuständen schaltet die Vorausberech nungslogik die ursprüngliche Schaltung ab und berechnet die Ausgangssignale selbst.

Zum Reduzieren des Leistungsverbrauchs in einer Schaltung durch Beseitigen unnötiger Logikübergänge bei verschiede nen Signalen in der Schaltung wurden mehrere herkömmliche Verfahren verwendet. Zur Bezugnahme auf diese Verfahren insgesamt wird der Begriff "Power Management" verwendet.

Die höhere Synthese (die auch Verhaltenssynthese genannt wird) setzt eine Verhaltensbeschreibung einer VLSI-Schal tung in eine Registerübertragungsebenen-Strukturverwirk lichung (RTL-Strukturverwirklichung) um, die als eine Verbindung von Makroblöcken (z. B. von Funktionseinhei ten, Registern, Multiplexern, Bussen, Speicherblöcken usw.) und einer zufälligen Logik beschrieben wird.

Eine Verhaltensbeschreibung einer Folgeschaltung enthält eine algorithmische Spezifikation ihrer Funktionalität.

Es ist möglich, daß eine solche Beschreibung fast keine Informationen über das zyklenweise Verhalten der Schal tung oder ihrer Strukturverwirklichung enthält. Typi scherweise kompilieren die Hilfsmittel für die Verhal tenssynthese eine Verhaltensbeschreibung in ein geeigne tes Zwischenformat wie etwa in einen Steuerdaten-Ablauf plan (CDFG). Die Vertizes in der CDFG stellen verschie dene Operationen der Verhaltensbeschreibung dar. Um Datenabhängigkeiten zwischen Operationen und dem Steuer ablauf darzustellen, werden die Daten- und Steuersignal flanken verwendet.

Typischerweise führen die Hilfsmittel für die höhere Synthese eine oder mehrere der folgenden Aufgaben aus: Transformation, Modulauswahl, Taktauswahl, Planung, Betriebsmittelzuordnung und -zuweisung (auch als Be triebsmittel- oder Hardwareteilung bezeichnet). Die Planung bestimmt das zyklenweise Verhalten des Entwurfs dadurch, daß sie jede Operation einem oder mehreren Taktzyklen oder Steuerschritten zuweist. Die Zuordnung entscheidet die Anzahl der Hardware-Betriebsmittel jedes Typs, die zum Verwirklichen der Verhaltensbeschreibung verwendet werden. Die Zuweisung bezieht sich auf das Binden jeder Variablen (und der entsprechenden Operation) an eines der zugeordneten Register (und an die entspre chenden Funktionseinheiten).

Die Registerteilung oder -zuweisung bezieht sich auf ein Verfahren zum Abbilden jeder Variablen in der Verhaltens beschreibung einer Folgeschaltung auf ein Register in ihrer RTL-Verwirklichung. Ein umfassender Überblick über höhere Syntheseverfahren findet sich in R. Camposano und W. Wolf, High-Level VLSI Synthesis. Kluwer Academic Publishers, Norwell, MA, 1991 und D. D. Galski, N. D. Dutt, A. C.-H. Wu und S. Y.-L. Lin, High-level Synthesis: Introduction to Chip and System Design. Kluwer Academic Publishers, Norwell, MA, 1992.

Es wurden Vorgehensweisen des automatischen Folgeschal tungs-Power Managements vorgeschlagen, die die folgenden Verfahren verwenden:

- Taktverknüpfung: Verknüpfen von Taktsignalen, um die in dem Taktnetz und in den Registern verbrauchte Leistung zu sparen, L. Benini, P. Siegel und G. DeMi cheli, "Saving power by synthesizing gated clocks for sequential circuits", IEEE Design & Test of Compu ters, S. 32-41 (Winter 1994) und L. Benini und G. De- Micheli, "Automatic synthesis of gated-clock sequen tial circuits", IEEE Trans. Computer-Aided Design, Bd. 15, S. 630-643 (Juni 1996).
- Vorausberechnung: Sperren von Registern gegenüber dem Laden, um den Leistungsverbrauch in den Registern und in dem Schaltnetz, in das die Register einspei sen, einzusparen, M. Aldina, J. Monteiro, S. Devadas, A. Ghosh und M. Papaefthymiou, "Precomputation-based sequential logic optimization for low power", IEEE Trans. VLSI Systems, Bd. 2, S. 426-436 (Dez. 1994).
- Operandenisolation: Das Einsetzen transparenter Zwischenspeicher an den Eingängen eines eingebetteten Schaltnetzblocks sowie einer zusätzlichen Steuer schaltungsanordnung zum Erfassen von Leerlaufzustän den für den Logikblock 16, 7, 8]. Die Ausgänge der Steuerschaltungsanordnung werden entsprechend verwen det, um die Zwischenspeicher an den Eingängen des Lo gikblocks gegenüber den sich ändernden Werten zu sperren. Somit werden die Eingangswerte der vorange henden Zyklen an den Eingängen des betrachteten Lo gikblocks erhalten, was die unnötige Leistungsdissi pation beseitigt.
- Controllergesteuertes Power Management: Neukon struieren der Steuerlogik einer Schaltung in der Weise, daß der Leistungsverbrauch infolge unnötiger Schaltaktivität in dem Datenpfad minimiert wird, A. Raghunathan, S. Dey und N. K. Jha, "Power management techniques for control-flow ,p intensive designs", Proc. Design Automation Conf., S. 429-434 (Juni 1997).

IC. Probleme in herkömmlichen Power Management-Verfahren

Die ersten zwei oben diskutierten Verfahren, die Taktver knüpfung und die Vorausberechnung, sind nur auf Taktnetze und auf Logikblöcke anwendbar, an deren Eingängen sich Register befinden. Somit können sie nicht verwendet werden, um die Leistung in eingebetteten Logikblöcken, d. h. in Logikblöcken, deren Eingänge mit den Ausgängen anderer Schaltnetzblöcke verbunden sind, einzusparen.

Das dritte und das vierte Verfahren, die Operandenisola tion und das controllergesteuerte Power Management, können auf beliebige eingebettete Logikblöcke angewendet werden. Bei der Verwendung des Operandenisolations-Ver fahrens und des controllergesteuerten Power Management-Ver fahrens, die der vorliegenden Erfindung näher als die anderen obenerwähnten Verfahren stehen, bestehen jedoch mehrere Nachteile.

In der Praxis kann die Operandenisolation infolge der folgenden Ursachen unwirksam sein:

- Ein Überfluß kleinerer Komponenten wie Multiple xer dominiert den Leistungsverbrauch, während die Funktionseinheiten für einen kleinen Teil der Gesamt leistung verantwortlich sein können. Siehe A. Raghu nathan, S. Dey und N. K. Jha, "Glitch analysis and reduction in register-transfer-level power optimiza tion", in Proc. Design Automation Conf., S. 331-336, Juni 1996. Der zusätzliche Leistungsbedarf infolge des Einsetzens transparenter Zwischenspeicher ist vergleichbar mit den Leistungseinsparungen, die er halten werden, wenn das Power Management auf Teil schaltungen wie etwa auf Multiplexernetze angewendet wird.
- Die Signale, die die Leerlaufzustände für die verschiedenen Teilschaltungen erfassen, kommen typi scherweise (z. B. infolge der Anwesenheit verschach telter Bedingungsformen in jedem Controller-Zustand, wobei die Leerlaufzustände von den Ausgangssignalen der Komparatoren von dem Datenpfad abhängen können) spät an. Somit werden die Zeitgebungs-Nebenbedingun gen, die zum Anwenden der herkömmlichen Power Manage ment-Verfahren auferlegt werden müssen (das Freigabe signal für die transparenten Zwischenspeicher muß ausgeregelt sein, bevor sich seine Dateneingangs signale ändern können), häufig nicht erfüllt.
- Um maximale Leistungseinsparungen zu erhalten, muß die Anwesenheit einer merklichen Störimpulsakti vität in den Steuersignalen sowie in den Datenpfadsi gnalen in Rechnung gestellt werden, Siehe A. Raghu nathan, S. Dey und N. K. Jha, "Glitch analysis and reduction in register-transfer-level power optimiza tion", in Proc. Design Automation Conf., S. 331-336, Juni 1996.

In gewissem Umfang mildert das controllergesteuerte Power Management die obigen Probleme, indem es das Hinzufügen einer zusätzlichen Schaltungsanordnung wie etwa der transparenten Zwischenspeicher zu der Konstruktion ver meidet (nur der Controller-Teil der Schaltung wird neu konstruiert) und potentielle negative Wirkungen wie etwa die Erhöhung der Schaltungsverzögerung und der Störim pulsleistung während des Power Management-Verfahrens in Rechnung stellt. Siehe A. Raghunathan, S. Dey und N. K. Jha, "Power management techniques for control-flow ,p intensive designs", in Proc. Design Automation Conf., S. 429-434, Juni 1997.

Jedoch kann das controllergesteuerte Power Management (ebenso wie die meisten anderen bekannten Power Manage ment-Verfahren) nur auf Schaltungen angewendet werden, deren Strukturdarstellung gegeben oder vorausgesetzt ist. Somit beschränkt die existierende Struktur der Schaltung den Umfang, in dem sie die Leistung reduzieren können. Die Struktur der Schaltung, die von Hand festgelegt oder durch eine höhere Synthese (ohne Betrachtung des Power Managements) bestimmt worden sein kann, kann unter dem Gesichtspunkt des Power Managements wesentlich unter der optimalen liegen.

Außerdem sind datendominierte Verhaltensbeschreibungen üblicherweise in Signal- und Bildverarbeitungsanwendungen anzutreffen, wobei sie durch das Übergewicht der Arithme tikoperationen charakterisiert sind. In einem solchen Fall wurde beobachtet, daß der Leistungsverbrauch der Funktionseinheiten den Gesamtleistungsverbrauch dieser Schaltungen dominiert, wobei ein wesentlicher Bruchteil dieser Leistung verbraucht wird, wenn die Funktionsein heiten keine nutzbaren Ausgangssignale erzeugen. Die herkömmlichen Power Management-Verfahren, von denen viele die Anordnung transparenter Zwischenspeicher an den Eingängen der Funktionseinheiten umfassen, können die Schaltungsverzögerungen entlang des kritischen Pfads erhöhen. Somit ist es möglich, daß sie keine akzeptablen Lösungen für Konstruktionen darstellen, die starken Leistungszwängen unterliegen.

II. Zusammenfassung der Erfindung

Eine Aufgabe dieser Erfindung besteht im Lösen der oben erwähnten Probleme. Genauer besteht eine Aufgabe dieser Erfindung in der Schaffung eines neuen Verfahrens, das die Beziehung zwischen der Aufgabe der Registerteilung in der höheren Synthese und den von den Funktionseinheiten in der RTL-Verwirklichung ausgeführten unnötigen (uner wünschten) Operationen auswertet.

Die vorliegende Erfindung ist auf die Verbesserung der Möglichkeiten des Power Managements während der höheren Synthese von Verhaltensbeschreibungen gerichtet. Die höhere Synthese ist das Verfahren des Kompilierens einer Steuerdaten-Ablaufplan-Beschreibung (CDFG-Beschreibung) der Schaltung zu einer Registerübertragungsebenen-Ver wirklichung (RTL-Verwirklichung).

Zum Verwirklichen der Aufgaben dieser Erfindung wird ein Verfahren zum Reduzieren des Leistungsverbrauchs in einer Folgeschaltung geschaffen, die Funktionseinheiten ent hält, wobei das Verfahren die Registerteilung und die Multiplexer-Konfiguration umfaßt, wobei die Registertei lung und die Multiplexer-Konfiguration die unnötige Schaltaktivität in wenigstens einer Funktionseinheit beseitigen.

Ein weiterer Aspekt dieser Erfindung ist ein Verfahren zum Synthetisieren von Folgeschaltungen mit mehreren Variablen, wobei das Verfahren das Verlängern der Lebens dauer einer oder mehrerer der mehreren Variablen und das Neukonfigurieren der Multiplexer auf der Grundlage der Ergebnisse des früheren Schritts umfaßt. Weitere Verbes serungen umfassen das Ausführen entweder des dynamischen Neubindens von Registern oder des Verdoppelns von Regi stern zum Vermeiden unnötiger Schaltoperationen, die von einer Teilmenge der Variablen hervorgerufen werden, deren Werte in mehr als einer Iteration erforderlich sind.

Ein nochmals weiterer Aspekt dieser Erfindung ist ein Verfahren zum Synthetisieren von Folgeschaltungen, die mehrere Funktionseinheiten, mehrere Operationen umfassen, wobei jede Operation mit mehreren Eingangsvariablen verknüpft ist, wobei das Verfahren das Berechnen der Geburtszeit eines linken Eingangssignals einer nachfol genden Operation, das Berechnen der Geburtszeit des rechten Eingangssignals der nachfolgenden Operation, das Einstellen der Todes zeit der Variablen auf das Maximum der vorangehenden Ergebnisse, das Wiederholen der Berech nungen für jede der mehreren mit einer Operation ver knüpften Eingangsvariablen, das Wiederholen der Berech nungen für die mehreren, auf eine Funktionseinheit abge bildeten Operationen sowie weiter das Wiederholen der Berechnungen für jede Funktionseinheit umfaßt.

Weitere Verbesserungen umfassen das Konfigurieren der Multiplexer in der Weise, daß sie einige Eingangssignale für den Zyklus wie in einem vorangehenden Zyklus auswäh len, falls der Zyklus ein Leerlauf ist. Nochmals weitere Verbesserungen umfassen das Identifizieren einer letzten, auf eine Funktionseinheit abgebildeten Operation, das Identifizieren einer ersten, auf eine Funktionseinheit abgebildeten Operation, das Auswählen einer Eingangsva riablen für die letzte Operation, das Identifizieren der Geburtszeit eines linken Eingangssignals der letzten Operation, das Identifizieren der Geburtszeit eines rechten Eingangssignals der letzten Operation, das Be stimmen, ob das Maximum der Ergebnisse der vorangehenden zwei Schritte größer als die Geburtszeit der Eingangsva riablen ist, das Austauschen der Variablenzuweisungen, falls der erlittene Organisationsaufwand unter einem vorgegebenen Schwellwert liegt, und falls der vorausge hende Schritt wahr ist, das Speichern der Werte der Eingangsvariablen in zusätzlichen Registern, falls der erlittene Organisationsaufwand größer als ein vorgegebe ner Schwellwert ist, das Wiederholen der Schritte für alle auf eine Funktionseinheit abgebildeten Eingangsva riablen und das Wiederholen für alle Funktionseinheiten.

Ein weiterer Aspekt dieser Erfindung ist ein System zum Synthetisieren von Folgeschaltungen mit mehreren Varia blen, wobei das System die Lebensdauer einer oder mehre rer der mehreren Variablen verlängert, wobei es die Multiplexer auf der Grundlage der verlängerten Lebens dauer der Variablen neu konfiguriert. Weitere Verbesse rungen umfassen ein System, wobei das System weiter entweder das dynamische Neubinden der Register oder das Verdoppeln der Register zum Vermeiden unnötiger Schalt operationen ausführt, die durch eine Teilmenge der Varia blen hervorgerufen werden, deren Werte in mehr als einer Iteration erforderlich sind.

III. Liste der Figuren

Die obigen Aufgaben und Vorteile der vorliegenden Erfin dung werden deutlicher anhand der ausführlichen Beschrei bung ihrer zweckmäßiger Ausführungen mit Bezug auf die beigefügte Zeichnung, wobei:

Fig. 1 einen geplanten CDFG zeigt.

Fig. 2 einen Stromlaufplan zeigt, der die Schaltaktivität für eine Konstruktion unter Verwendung von Verfahren des Standes der Technik zeigt.

Fig. 3 einen Stromlaufplan zeigt, der die Schaltaktivität für eine Konstruktion unter Verwendung der vorliegenden Erfindung zeigt.

Fig. 4 Transformationen während dreier Iterationen der Ausführung einer Folgekonstruktion zeigt.

Fig. 5 einen geplanten CDFG zum Veranschaulichen eines weiteren Aspekts dieser Erfindung zeigt.

Fig. 6 links eine Funktionseinheit in einer Architektur mit einem unvollkommenen Power Management und rechts eine Funktionseinheit in einer Architektur mit vollkommenem Power Management zeigt.

Fig. 7 die Operationen zeigt, die eine Funktionseinheit fu während zweier Iterationen der Ausführung eines CDFG ausführt.

Fig. 8 die Grundschritte des höheres Synthesesystems unter Verwendung von Verfahren der vorliegenden Erfindung zeigt.

Fig. 9 einen Pseudocode für ein Prüfverfahren gemäß der vorliegenden Erfindung zeigt.

Fig. 10 einen Pseudocode für ein Verfahren zum Behandeln von Abhängigkeiten zwischen den Iterationen gemäß der vorliegenden Erfindung zeigt.

Fig. 11 einen Ablaufplan zeigt, der eine derzeitige Ausführung der vorliegenden Erfindung zeigt.

IV. Ausführliche Beschreibung

Es wird eine Verhaltensbeschreibung einer Schaltung betrachtet, bei der die Planung und die Betriebsmittel teilung durch ein höheres Synthesehilfsmittel zum Erzeu gen einer RTL-Verwirklichung ausgeführt worden sind. Es wird eine Funktionseinheit in einer solchen RTL-Verwirk lichung betrachtet. Diese Funktionseinheit wird während der Steuerschritte (Taktzyklen) als aktiv bezeichnet, in denen sie zum Ausführen einer Berechnung aus der Verhal tensbeschreibung verwendet wird. Während der anderen Steuerschritte ist sie im Leerlauf.

Obgleich eine Funktionseinheit während ihrer Leerlauf-Steuer stufen keine Berechnung auszuführen braucht, können sich die Werte der Eingangssignale in die Funktionsein heit in der RTL-Verwirklichung ändern, was eine unnötige Leistungsdissipation bewirkt. Es ist klar, daß die Art, in der die Register geteilt werden, einen wesentlichen Einfluß auf die unnötige Leistungsdissipation in den Funktionseinheiten während ihrer Leerlaufzyklen hat.

Eine natürliche Fortsetzung der obigen Beobachtung ist die Frage, ob ohne einen unangemessen hohen Organisati onsaufwand zu erleiden in irgendeiner Weise erzwungen werden kann, daß die Registerteilung ein besseres Power Management für die Funktionseinheiten ermöglicht.

Die vorliegende Erfindung beruht auf der Einsicht, daß die Registerteilung den Leistungsverbrauch beeinflußt. Umfassend besteht das Verfahren aus zwei Schlüsselschrit ten: Dem Verlängern der Lebensdauern der Variablen, um sicherzustellen, daß die alten Operanden der Funktions einheiten während einer hinreichenden Zeit am Leben sind, sowie dem dynamischen Neubinden der Variablen zum Auflö sen von Lebensdauerkonflikten zwischen Kopien der glei chen Variablen in verschiedenen CDFG-Iterationen zwischen den Iterationen. In einem solchen Fall bezieht sich eine Iteration auf die Verarbeitung einer Menge von Eingangs signalen durch die Verhaltensbeschreibung oder durch den CDFG.

Es wird ein erzwungenes Registerteilungsverfahren ge schaffen, das in existierende höhere Synthesesysteme integriert werden kann, um Architekturen zu erzeugen, deren Funktionseinheiten keine Leistung verschwenden. Dieses Verfahren wurde in den Rahmen eines existierenden höheren Leistungsoptimierungs-Synthesesystems integriert, das Mehrfachdurchläufe, die Verkettung, Strukturpipeline-Funk tionseinheiten und Schleifen in dem CDFG handhaben kann und die Wirkungen der mehreren Verhaltenssynthese aufgaben wie etwa der Funktionseinheitsauswahl (dem Auswählen des Typs der Funktionseinheit für eine Opera tion), der Planung, der Taktauswahl (der Auswahl der Taktperiode), der Betriebsmittelzuordnung (dem Bestimmen der Anzahl jedes Betriebsmitteltyps), der Betriebsmittel teilung und der Skalierung der Speisespannung dynamisch abwägen kann.

Experimentelle Ergebnisse zeigen eine bis zu zweifache Reduktion der Leistung bei zusätzlichen Flächenbedarfen von nicht mehr als 6,4% ohne irgendeine Funktionsminde rung im Vergleich zu leistungsoptimierten Architekturen. Die vorliegende Erfindung ergänzt bekannte Registertei lungsverfahren für eine geringe Leistung wie etwa A. Raghunathan und N. K. Jha "Behavioral synthesis for low power" in Proc. Int. Conf., Computer Design, S. 255-270, Okt. 1994, J. Chang und M. Pedram, "Register allocation and binding for low power" in Proc. Design Automation Conf., S. 29-35, Juni 1995 und C. H. Gebotys, "Low energy memory and register allocation using network flow" in Proc. Design Automation Cont. S. 435-440, die die Schalt aktivität an dem Ausgang der Register während aktiver Taktzyklen zu minimieren versuchen.

Die vorliegende Erfindung kann in Verbindung mit irgend einem existierenden Verfahren der Registerteilung (das kein Power Management betrachtet) verwendet werden.

Die vorliegende Erfindung tritt an die Stelle der Notwen digkeit der Verwendung der Operandenisolation in Funkti onseinheiten in der RTL-Verwirklichung. Sie setzt voraus, daß die Multiplexer in dem Datenpfad entsprechend als ein Nachverarbeitungsschritt unter Verwendung eines Verfah rens wie etwa des controllergesteuerten Power Managements konfiguriert werden. A. Raghunathan, S. Dey und N. K. Jha, "Power management techniques for control-flow inten sive designs", in Proc. Design Automation Conf., S. 429-434 (Juni 1997).

Der Rest der Diskussion ist wie folgt organisiert. Der Abschnitt IVA weist nach, daß die Registerbindung (die Zuweisung von Variablen an Register) eine wesentliche Auswirkung auf die Möglichkeiten des Power Managements haben kann, und zeigt, wie für einen geringen zusätzli chen Aufwand bezüglich der Anzahl der Register eine wesentliche Reduzierung oder Beseitigung der unerwünsch ten Schaltaktivität in den Funktionseinheiten möglich ist. Abschnitt IVB definiert Architekturen mit vollkomme nem Power Management und leitet Bedingungen an den Plan und an die Variablenzuweisung ab, die für ein vollkomme nes Power Management erfüllt sein müssen. Weiter werden die Verfahren der vorliegenden Erfindung und zweckmäßige Ausführungen diskutiert. Der Abschnitt IVC diskutiert eine zweckmäßige Ausführung, bei der die Verfahren der vorliegenden Erfindung zum Erleichtern des Power Manage ments in ein existierendes höheres Synthesesystem inte griert werden. Der Abschnitt IVD stellt experimentelle Ergebnisse und der Abschnitt V die Schlußfolgerungen dar.

IVA. Die Wirkung der Registerteilung auf den Leistungs verbrauch von Funktionseinheiten

Ein Schlüsselaspekt dieser Erfindung besteht darin, daß der Leistungsverbrauch durch eine geeignetere Register teilung reduziert werden kann. Diese Wirkungen der Regi sterteilung werden hier unter Verwendung von Beispielen dargestellt. Es wird hier gezeigt, daß die Art, in der die Registerzuordnung und die Registerbindung erfolgen, einen großen Einfluß auf die unerwünschte Schaltaktivität in einer Schaltung haben können. Weiter wird die Beseiti gung einer unerwünschten Schaltaktivität aus einer Kon struktion durch eine Kombination von Verfahren mit einem geringen zusätzlichen Aufwand bezüglich der Anzahl der Register gezeigt. Es wird ein Beispiel dargestellt, das zeigt, daß die unerwünschte Schaltaktivität beseitigt werden kann, ohne die Anzahl der Register in der synthe tisierten Architektur zu erhöhen.

Beispiel 1: Es wird der in Fig. 1 gezeigte geplante CDFG betrachtet. Jede Operation in dem CDFG ist mit ihrem Namen (der in dem Kreis angeordnet ist, der die Operation darstellt) und mit dem Namen der Instanz der Funktions einheit, auf die sie abgebildet wird (der außerhalb des Kreises angeordnet i st, der die Operation darstellt), kommentiert. Jede Variable in dem CDFG ist mit ihrem Namen kommentiert. Die Taktzyklusgrenzen sind mit punk tierten Linien kommentiert. Der Plan besitzt fünf Steuer schritte, s1, . . ., s5. Der Steuerschritt s5 wird verwendet, um die Ausgangswerte in den Registern zu halten und um sie an die Umgebung zu übermitteln, mit der die Konstruk tion wechselwirkt, und um die Eingangswerte für die nächste Iteration in ihre jeweiligen Register zu laden.

Um den Einfluß der Variablenzuweisung auf den Leistungs verbrauch abzuschätzen, werden zwei Anwärter auf Zuwei sungen, die in Tabelle 1 gezeigte Zuweisung 1 und Zuwei sung 2, betrachtet. Die unter Verwendung dieser Zuweisun gen erhaltenen Architekturen wurden Logiksyntheseoptimie rungen unterworfen und unter Verwendung einer 1,2 Mikro meter-Standardzellenbibliothek angeordnet und geleitet. Die aus den Konstruktionen extrahierten Transistorebenen-Netz listen wurden unter Verwendung eines Schalterebenen simulators mit typischen Eingangssignalspuren zur Messung der Leistung simuliert. Für die Schaltung Konstruktion 1, die aus der Zuweisung 1 synthetisiert wurde, betrug der Leistungsverbrauch 30,71 mW, während der Leistungsver brauch für die Schaltung Konstruktion 2, die aus der Zuweisung 2 synthetisiert wurde, 18,96 mW betrug.

Tabelle 1

Zwei Variablenzuweisungen für den in Fig. 1 gezeigten geplanten CDFG

Zur Erläuterung des deutlichen Unterschieds des Lei stungsverbrauchs der zwei Konstruktionen werden unter Verwendung der Fig. 2 bzw. 3 die Schaltaktivitäten in den Funktionseinheiten, aus denen die Konstruktion 1 und die Konstruktion 2 bestehen, untersucht. In diesen Figuren ist jede Funktionseinheit durch einen bezeichneten Kasten dargestellt. Die vertikalen, zu dem Kasten hinführenden Linien stellen eine Dauer dar, die gleich einer Iteration der Ausführung des CDFG ist. Jeder Steuerschritt ist mit (i) den Symbolwerten, die an den Eingängen der Funktions einheit in der Verwirklichung auftreten, und (ii) falls vorhanden, mit der Operation, die der von der Funktions einheit ausgeführten Berechnung entspricht, kommentiert.

Zum Beispiel erscheinen die Variablen v1 und v2 für die Funktionseinheit MUL1, Fig. 2, in dem Steuerschritt s1 an ihrem linken bzw. rechten Eingang. Die in dem Steuer schritt s1 von MUL1 ausgeführte Berechnung entspricht der Operation *1 des CDFG. Zyklen, in denen sich eines der Eingangssignale einer Funktionseinheit oder beide ändern, was eine Leistungsdissipation bewirkt, sind in den Figu ren schraffiert. Jede Variablenänderung kann mit der Ausführung einer neuen Operation verknüpft werden. Zy klen, während derer störende Eingangssignalübergänge auftreten, die nicht irgendwelchen CDFG-Operationen entsprechen, sind mit einem X gekennzeichnet.

Der mit diesen Operationen verknüpfte Leistungsverbrauch kann ohne Änderung der Funktionalität der Konstruktion beseitigt werden. Eine Funktionseinheit führt keine unerwünschte Operation aus, wenn ihre beiden Eingangs signale nicht geändert werden. Ein Zyklus, in dem sich ein Eingangssignal einer Funktionseinheit nicht ändert, ist nicht mit irgendeiner Variablen gekennzeichnet. Zum Beispiel ändern sich in Fig. 3 die Eingangssignale der Funktionseinheit MUL1 von dem Steuerschritt s1 zu dem Steuerschritt s2 nicht. Somit sind die Eingangssignale von MUL1 in dem Steuerschritt s2 nicht gekennzeichnet.

Eine Untersuchung der Fig. 2 und 3 offenbart, daß die Funktionseinheiten, die die Konstruktion 2 bilden, nur eine unerwünschte Operation ausführen, während die Funk tionseinheiten, die die Konstruktion 1 bilden, acht unerwünschte Operationen ausführen. Dies erläutert den Unterschied des Leistungsverbrauchs zwischen den zwei Konstruktionen.

Beispiel 2: Das vorausgehende Beispiel hat gezeigt, daß die erzwungene Registerteilung die Anzahl der unerwünsch ten Operationen m einer Schaltung deutlich reduzieren kann. Dieses Beispiel zeigt ein weiteres, als dynamische Registerneubindung bezeichnetes Verfahren, das die uner wünschten Operationen in Verbindung mit der Variablenzu weisung weiter beseitigen kann.

Es wird die Funktionseinheit SUB1 in Konstruktion 2 betrachtet. Eine Überprüfung von Fig. 3 offenbart, daß sie in dem Steuerschritt s1 jeder Iteration eine uner wünschte Operation ausführt. Dies liegt daran, daß der Multiplexer an ihrem Eingang von dem Steuerschritt s3 jeder Iteration bis zu dem Steuerschritt s1 der nächsten Iteration das Register R5 auswählt, dem die Variable v12 zugewiesen ist. Da v12 in dem Steuerschritt s1 jeder Iteration einen neuen Wert erlangt, berechnet SUB1 in dem Steuerschritt s1 v11-v12, was unerwünscht ist, da der Wert von v11 der vorausgehenden Iteration entspricht, während der Wert von v12 der momentanen Iteration ent spricht. Dieses Problem würde selbst dann fortdauern, wenn an dem Eingang von SO B1 v3 anstelle von v12 ausge wählt wäre. Dies liegt daran, daß v3 nur an dem Ende des Steuerschritts s1 erzeugt wird, was bewirkt, daß SUB1 v11-v3 mit dem alten Wert von v3 berechnet. Es wird angemerkt, daß der alte Wert von v12 (aus der vorausge henden Iteration) an dem Eingang von SUB1 zum Vermeiden der unerwünschten Operation erhalten werden muß, bis der neue Wert von v3 in der momentanen Iteration geboren worden ist.

In diesem Fall kann die unerwünschte Operation beseitigt werden, ohne daß ein Preis bezüglich der Anzahl der verwendeten Register gezahlt werden müßte, indem die den Registern R5 und R6 in abwechselnden Iterationen zugewie senen Variablen ausgetauscht werden. In geraden Iteratio nen wird v3 auf R6 und v12 auf R5 abgebildet, während sie in ungeraden Iterationen umgekehrt abgebildet werden.

Tabelle 2

Zwei verschiedene Variablenzuweisungen für den in Fig. 5 gezeigten geplanten CDFG

Fig. 4 zeigt diese Transformation während dreier Itera tionen der Ausführung der Konstruktion. In dieser Figur ist die Linie, die den rechten Eingang von SUB1 dar stellt, mit dem Register kommentiert, das die ausgewählte Variable enthält. Wie in der Figur gezeigt ist, speichert das Register R6 die Variable v12 in der Iteration i, die Variable v3 in der Iteration i+1 usw. Da die Variable v3 in der Iteration i+1 im Register R6 gespeichert wird, wird der alte Wert von v12 an dem Eingang von SUB1 erhal ten, bis v3 geboren worden ist, was somit die in Fig. 3 gezeigte mit X bezeichnete unerwünschte Operation vermei det.

In den Beispielen 1 und 2 wurde gezeigt, daß unerwünschte Operationen bei einer geringen Erhöhung der Anzahl der Register wesentlich reduziert oder beseitigt werden können. Wie das folgende Beispiel zeigt, können uner wünschte Operationen manchmal jedoch ohne einen zusätzli chen Aufwand an Registern beseitigt werden.

Beispiel 3: Es wird der in Fig. 5 gezeigte geplante CDFG betrachtet. Tabelle 2 zeigt zwei Anwärter für Variablen zuweisungen, Zuweisung 1 und Zuweisung 2, die beide die gleiche Anzahl an Registern erfordern. Um den Leistungs verbrauch zu bestimmen, wurden bei der Synthese die den zwei Konstruktionen entsprechenden Architekturen mit typischen Eingangssignalspuren simuliert.

Die unter Verwendung der in Zuweisung 1 gezeigten Varia blenzuweisung abgeleitete Architektur verbrauchte 42,86 mW, während die unter Verwendung von Zuweisung 2 abgeleitete Architektur 34,05 mW verbrauchte. Es zeigt sich, daß die Funktionseinheit MUL1 für die aus der Zuweisung 1 erhaltene Konstruktion in den Zyklen s2 und 53 unerwünschte Operationen ausführt, während die Funkti onseinheit ADD1 in dem Zyklus s4 eine unerwünschte Opera tion ausführt. Für die aus der Zuweisung 2 erhaltene Konstruktion wird die Variablenzuweisung in der Weise gewählt, daß keine unerwünschten Operationen ausgeführt werden.

Die obigen Beispiele dienen zur Erläuterung dessen, daß eine vernünftige Variablenzuweisung ein Schlüsselfaktor beim Beseitigen unerwünschter Operationen ist. Die vor liegende Erfindung ist auf das Beseitigen unerwünschter Operationen in den Funktionseinheiten gerichtet. Da die Funktionseinheiten in diesen Architekturen keine uner wünschten Operationen ausführen, d. h., da irgendeine in einer Funktionseinheit ausgeführte Operation eine gül tige, von dem CDFG angeforderte Operation ist, werden die durch das Anwenden der Verfahren der vorliegenden Erfin dung erzeugten Architekturen als Verfahren mit vollkomme nem Power Management bezeichnet.

In den folgenden Abschnitten werden Bedingungen an den Plan und an die Variablenzuweisung abgeleitet. Wenn sie erfüllt sind, führen diese Bedingungen zu Architekturen mit vollkommenem Power Management. Die Integration dieser Bedingungen in ein existierendes leistungsoptimierendes höheres Synthesesystem wird ebenfalls beschrieben.

IVB. Vollkommenes Power Management

Ein weiterer Schlüsselaspekt dieser Erfindung ist die Identifizierung der Bedingungen, deren Erfüllung ein vollkommenes Power Management sicherstellt. Solche Bedin gungen werden in diesem Abschnitt abgeleitet.

Es wird eine Funktionseinheit fu betrachtet, die eine Operation des Typs op ausführt, wobei sie die Operationen op1, op2, . . ., op(i-1) und opi ausführt, die in den Zeit schritten t1, t2, . . ., t(i-1) bzw. ti geplant sind. Der Operation opj werden an ihrem linken bzw. rechten Eingang die Variablen vj_1 und vj_2 zugeführt, während sie die Variable vi_out erzeugt. Während sich irgend eines der Eingangssignale der fu ändert, verbraucht sie eine Lei stung. Die insgesamt verbrauchte Leistung kann als

P_fu = Σ P(vj'_1, v(j+1)'_1, vj'_2, v(j+1)'_2) (1)

geschrieben werden, wobei vi'_1 (vi'_2) die Variable an dem linken (rechten) Eingang der fu vor der Änderung ist und wobei v(j+1)'_1, (v(j+1)'_2) die neue Variable ist, während P(vj'_1, v(j+1)'_1, vj_2, v(j+1)'_2) der mit der Variablenänderung verknüpfte Leistungsverbrauch ist.

Somit sind die Variablen an den Eingängen der Funktions einheit gestrichen gezeigt, während die Variablen, die den Operationen zugeführt werden, ungestrichen gezeigt sind. Diese Unterscheidung wird getroffen, da die einer Funktionseinheit zugeführten Variablen eine Obermenge der Variablen sind, die den auf sie abgebildeten Operationen zugeführt werden. Zum Beispiel wird angenommen, daß die Variablen, die an dem Eingang einer Funktionseinheit fu1, die die Operation op1 (Eingangssignale v1_2 und v1_2) ausführt, erscheinen, von den Registern R1 und R2 abhän gen, die in ihren linken bzw. rechten Eingang eingaben. Wenn angenommen wird, daß v1_1 und v3_1 auf R1 abgebildet sind, während v1_2 und v2_2 auf R2 abgebildet sind, erscheinen an den Eingängen der Funktionseinheit v1_1, v3_1, v1_2, v2_2. Diese Variablen werden als gestrichene Variablen bezeichnet, wobei v1_1 und v1_2 einer Teilmenge von ihnen entsprechen. Im allgemeinen hängt P(vj'_1, v(j+1)'_1, vj_2, v(j+1)'_2) von der Verwirklichung der Funktionseinheit und von der mit den Variablen P(vj'_1, v(j+1)'_1), vj_2, v(j+1)'_2) verknüpften Signalstatistik ab. Irgendein Paar {vj_1, vj'_2} von gleichzeitig an dem linken und rechten Eingang von fu derart auftretenden Variablen, daß op(vj'_1, vj'_2) von dem CDFG nicht benö tigt wird, bildet eine unerwünschte Operation, wobei die durch die Änderung hervorgerufenen Operationen weggelas sen werden können, ohne die Funktionalität der Schaltung zu ändern. Wie das Beispiel 4 zeigt, unterliegt eine Architektur dem vollkommenen Power Management, wenn alle solchen unerwünschten Operationen beseitigt sind.

Beispiel 4: Fig. 6 zeigt links eine Funktionseinheit in einer Architektur mit unvollkommenem Power Management und rechts eine Funktionseinheit in einer Architektur mit vollkommenem Power Management gemäß der vorliegenden Erfindung. Die Linien an dem linken und rechten Eingang der Funktionseinheit bezeichnen die Zeitachse und sind mit den Eingangsvariablen und mit ihren Geburtszyklen kommentiert. Die schraffierten Leisten entsprechen Ände rungen der Eingangswerte und stellen Zyklen, in denen Leistung verbraucht wird, dar. Wie in der Figur gezeigt ist, entsprechen in dem Fall von Architekturen mit voll kommenem Power Management alle leistungsverbrauchenden Eingangsänderungen von dem CDFG geforderten Operationen.

IVB.1 Bedingungen für ein vollkommenes Power Management

Die folgenden drei Bedingungen sind hinreichend, um ein vollkommenes Power Management sicherzustellen:

- Die Folge der in irgendeiner Iteration an dem linken Eingang von fu erscheinenden Werte entspricht v1_1, v2_1, . . ., vi_1.
- Die Folge der in irgendeiner Iteration an dem rechten Eingang von fu erscheinenden Werte entspricht v1_2, v2_2, . . ., vi_2.
- Die Werte an den Eingängen von fu in irgendeinem Taktzyklus entsprechen einem Paar (vj_1, vj_2), 1≦j≦i.

Es ist klar ersichtlich, daß unter den angegebenen Bedin gungen jede in einer Funktionseinheit ausgeführte Opera tion ein nutzbares Ausgangssignal erzeugt, wobei keine unnötigen Operationen eingeführt werden, was somit ein vollkommenes Power Management sicherstellt. Damit diese Bedingungen erfüllt sind, sollten die Multiplexer an dem linken und rechten Ausgang der Funktionseinheit die Variablen vj_1 bzw. vj_2 mit 1≦j≦i auswählen, bis v(j+1)_1 und v(j+1)_2 verfügbar sind. Dies kann nur erfolgen, falls die Werte von vj_1 und vj_2 in den Regi stern, denen sie zugewiesen sind, bis max(birth(v(j+1)_1), birth(vj+1)_2)) verfügbar sind, wobei birth(vj_k) die Geburtszeit der Variablen vi_k ist.

Wie in Abschnitt IVB.2 erläutert ist, würde das Verlän gern der Lebensdauern der Variablen (des Intervalls zwischen dem Geburt und dem Tod einer Variablen) in dieser Weise in einigen Fällen jedoch zu unerfüllbaren Nebenbedingungen führen.

IVB.2 Dynamische Registerneubindung

Fig. 7 zeigt die von der Funktionseinheit fu während zweier Iterationen der Ausführung des CDFG ausgeführten Operationen. Die Abfolge der von fu in einer Iteration ausgeführten Operationen lautet op1, op2, . . ., opi. Die Variable vi_1 wird im Zyklus m geboren, während die Variable v1_1 im Zyklus n mit m<n geboren wird. Um in diesem Fall die Ausführung der unerwünschten Operationen zu vermeiden, sollte der neue Wert von v1_1 an dem linken Eingang von fu vi_1 nachfolgen. Somit muß bis zum Zyklus n an dem linken Eingang vi_1 ausgewählt sein.

Da jedoch vi_1 im Zyklus m einen neuen Wert annimmt, verbraucht die Funktionseinheit im Zyklus m eine unnötige Schaltleistung. Für ein vollkommenes Power Management muß der neue Wert von vi_1 somit in einem getrennten Register gespeichert werden, während der alte Wert unversehrt bleibt, bis er nicht mehr benötigt wird. Somit müssen verschiedene Instanzen der gleichen Variablen, die in verschiedenen Iterationen der Ausführung des CDFG erzeugt wurden, auf verschiedene Register abgebildet werden. Dies kann leicht auf Kosten eines zusätzlichen Registers dadurch erfolgen, daß der neue Wert von vi_1, bevor er fu zugeführt werden darf, in einem unbelegten Register gepuffert wird. Es wird angemerkt, daß ein weiterer Aspekt dieser Erfindung eine nachfolgend beschriebene von dem zusätzlichen Registeraufwand freie Lösung für dieses Problem schafft, die als die nachfolgend beschriebene dynamische Registerneubindung bezeichnet wird.

R1 und R8 sollen die Register, auf die die Variablen v1_1 und v1_1 abgebildet sind, bezeichnen. Die Variablenzuwei sungen für die Register R1 und R8 werden in abwechselnden Iterationen des CDFG ausgetauscht, d. h., falls in einer geraden Iteration S1 die Menge der auf R1 abgebildeten Variablen und S8 die Menge der auf R2 abgebildeten Varia blen bezeichnet, werden die Variablen in S1 (S8) in einer ungeraden Iteration auf R2 (R1) abgebildet. In diesem Szenarium wird der alte Wert von vi_1 in P2 erhalten, bis v1_1 geboren worden ist, was die Abwesenheit der unnöti gen Schaltaktivität in fu sicherstellt. Es wird jedoch angemerkt, daß diese Lösung zu einer zusätzlichen Verbin dung in dem Datenpfad führen könnte, da jede Funktions einheit, die ursprünglich in R1 (R,) eingibt, nun eben falls in R2 (R1) eingeben sollte, während jede Funktions einheit, in die ursprünglich aus R1 (R8) eingegeben wird, nun ebenfalls aus R2 (R1) eingegeben werden sollte.

In der Praxis wird dieses Verfahren für (als die Anzahl der hinzugefügten 2-zu-1-Multiplexer gemessenen) zusätz liche Verbindungsaufwände bis zu einen Schwellwert von vier angewendet. Für zusätzliche Verbindungsaufwände von mehr als vier wird die Registerverdopplung bevorzugt. Dieser Schwellwert beruht auf Leistungsabschätzungsexpe rimenten.

IVB.3 Der Algorithmus

Die in den früheren Abschnitten dargestellten Verfahren der erzwungenen Registerteilung, der dynamischen Regi sterneubindung und der Registerverdopplung können in irgendein höheres Synthesesystem integriert werden. In diesem Abschnitt wird ein Algorithmus für das vollkommene Power Management in dem Kontext eines leistungsoptimie renden höheren Synthesesystems geschaffen. Siehe A. Raghunathan und N. K. Jha ["An iterative improvement algorithm for low power datapath synthesis"] Proc. Int. Conf., Computer Aided Design, S. 597-602, Nov. 1995. Es wird eine Übersicht über das System dargestellt, auf die eine Beschreibung der zum Erzeugen von Architekturen mit vollkommenem Power Management erforderlichen Modifikatio nen folgt.

Fig. 8 zeigt die Grundschritte des höheren Synthesesy stems, das auf einem iterativen Verbesserungsverfahren beruht, das lokalen Minima entgehen kann. Das System nimmt als Eingabe eine zu einem CDFG kompilierte Verhal tensbeschreibung, eine Bibliothek der im voraus charakte risierten Module für die Fläche, für den Tag und für die Leistung, eine Menge typischer Eingangssignalspuren zum Erleichtern der Leistungsabschätzung und der Abtastperi ode (des Austastintervalls zwischen der Ankunft zweier aufeinanderfolgender Iterationen der Eingangssignale) an.

Die Synthese beginnt in 810 mit der Identifizierung der Menge der möglichen Taktperioden und Speisespannungen. Für jedes solches Paar wird die Synthese mit der Ablei tung einer Anfangslösung 820 begonnen. Die vollständigen Planungs-, Zuordnungs- und Bindungsinformationen werden durch die Anwendung einer Folge von Verschiebungen (einzelne Verschiebungen können einen negativen Gewinn haben) transformiert.

Das "Verschieben" in 830-860 kann eine Instanz einer Funktionseinheit in dem Datenpfad durch eine Instanz eines anderen Typs ersetzen, Paare von Funktionseinheiten oder von Registern zu einer bzw. zu einem zusammenführen oder eine Funktionseinheit oder ein Register in mehrere Funktionseinheiten oder Register aufspalten. Es wird der Einfluß jeder dieser Verschiebungen auf die Leistung berechnet, wobei die leistungseffizienteste Folge der Verschiebungen, die keine Abtastnebenbedingungen ver letzt, verwirklicht wird.

Die in Fig. 8 schraffiert gezeigten Kästen bezeichnen die Syntheseschritte, die modifiziert werden müssen, um das vollkommene Power Management zu integrieren. Das Power Management-Verfahren wird in drei Phasen angewendet. Die ersten zwei Phasen 830, 840 gehören zu Verschiebungs-Aus wahl-Verfahren, während die dritte 880 nach der itera tiven Verbesserung stattfindet. Die ersten zwei Zustände stellen ein vollkommenes Power Management in jeder CDFG-Iteration sicher, ignorieren aber die in Abschnitt IVB.2 beschriebenen Wirkungen zwischen den Iterationen. Für die Korrektur solcher Wirkungen zwischen den Iterationen ist die dritte Stufe vorgesehen, die nach der Synthese statt findet.

In jedem Schritt des Algorithmus, d. h. vor und nach der Anwendung jeder Verschiebung, existiert ein vollständiger Plan und ein vollständiger Datenpfad. Wenn eine Modulaus wahl, eine Betriebsmittelteilung oder eine Betriebs mittelaufspaltung betrachtet werden, wird zunächst die resultierende Architektur geplant, um sicherzustellen, daß ein gültiger Plan existiert. Nachdem eine Architektur geplant ist, werden die Lebensdauern der Variablen geprüft, um zu sehen, ob ihre Verlängerungen zwischen den Iterationen, die zum Sicherstellen der Abwesenheit unerwünschter Operationen erforderlich sind, irgendwelche Konflikte in den Lebensdauern der Variablen hervorrufen.

Da jede Variable auf ein getrenntes Register abgebildet wird, ist die Anfangslösung durch die Abwesenheit uner wünschter Operationen gekennzeichnet. Architekturen, die unerwünschte Operationen anzeigen, werden zurückgewiesen. Typischerweise werden unerwünschte Operationen nur durch Verschiebungen eingeführt, die verschiedene Register zu einem zu vereinigen versuchen. Somit beeinflußt diese Einschränkung die Funktionseinheitsteilung oder Funkti onseinheisaufspaltung oder Modulauswahlverschiebungen in der Praxis nicht. In dieser Phase ist nicht bestimmt, ob eine Eingangsvariable der (in der aufsteigenden Reihen folge der Geburt) letzten auf eine Funktionseinheit abgebildeten Operation am Leben erhalten werden kann, bis alle Eingangssignale für die erste auf die Funktionsein heit abgebildete Operation in der nächsten Iteration geboren worden sind. Dies liegt daran, daß sich zusätzli che hinzugefügte Register oder zum Beseitigen des Pro blems während einer Verschiebung der iterativen Verbesse rung ausgeführte Zuweisungsaustausche zwischen den Itera tionen wegen zukünftiger Verschiebungen selbst dann als unzulänglich oder redundant erweisen können, wenn dieses Problem in dieser Phase erfaßt und gelöst wird.

Der Pseudocode für das Prüfverfahren ist in Fig. 9 ge zeigt. Die äußere Schleife stellt den Durchlauf der Funktionseinheiten, die den Datenpfad bilden, dar. Die auf die Funktionseinheit abgebildeten Operationen werden dann in steigender Reihenfolge der Geburt durchlaufen. Jede Eingangsvariable v der Operation op wird dann über prüft, um sicherzustellen, daß ihre Todeszeit bis zu der Geburtszeit des letzten ankommenden Eingangssignals der Operation, die unmittelbar auf op folgt, verlängert werden kann. Falls das der Fall ist, wählen die Multiple xer an dem Eingang der betrachteten Funktionseinheit die Variable v zum Erscheinen an dem geeigneten Eingang aus, bis das letzte ankommende Eingangssignal von op geboren worden ist. Falls das nicht der Fall ist, wird davon ausgegangen, daß die Architektur kein vollkommenes Power Management besitzt, wobei eine andere betrachtet wird. Da sichergestellt ist, daß die Anfangsarchitektur frei von unerwünschten Operationen der Art ist, auf die dieses Unterprogramm prüft, liefert der Synthesealgorithmus der vorliegenden Erfindung immer eine gültige Lösung.

Durch Abhängigkeiten zwischen den Iterationen erzeugte Probleme werden gelöst, sobald die iterative Verbesserung abgeschlossen wird. Der Pseudocode für das Verfahren zum Behandeln der Abhängigkeiten zwischen den Iterationen ist in Fig. 10 gezeigt und entspricht dem schraffierten Kasten in Fig. 8, der dem vorletzten Schritt des Synthe sealgorithmus entspricht. Wie zuvor stellt die äußere Schleife das Durchlaufen der Funktionseinheiten in dem Datenpfad dar. In diesem Fall sind die zuerst geborene und die zuletzt geborene Operation, die auf die Funkti onseinheit abgebildet werden, von Interesse. Falls die Geburtszeit einer Eingangsvariablen zu der zuletzt gebo renen Operation kleiner als die Geburtszeit des als letztes ankommenden Eingangssignals zu der zuerst gebore nen Operation ist, verfügt die Architektur über kein vollkommenes Power Management. Dieses Problem wird entwe der durch eine Registerverdopplung oder durch einen Austausch der Variablenzuweisungen zwischen den Iteratio nen behandelt.

Der in Fig. 11 gezeigte Ablaufplan zeigt eine Ausführung der vorliegenden Erfindung. Dieser Ablaufplan ist selbst erklärend.

Tabelle 3

Ergebnisses der Leistungseinsparung und des zusätzlichen Flächenbedarfs

IVB.4 Experimentelle Ergebnisse

Eine zweckmäßige Ausführung der vorliegenden Erfindung wird im Rahmen eines höheren Leistungsoptimierungs-Syn thesesystems SCALP realisiert. Siehe A. Raghunathan und N. K. Jha "An iterative improvement algorithm for low power datapath synthesis", in Proc. Int. Conf., Computer Aided Design, S. 597-602, Nov. 1995. Die Experimente bewerten die Verfahren der vorliegenden Erfindung unter Verwendung mehrerer Verhaltensbeschreibungen von Signal- und Bildverarbeitungsanwendungen.

Das modifizierte SCALP liest eine Textbeschreibung eines CDFG ein und führt einen V_dd-Abschnitt, eine Taktauswahl, eine Funktionseinheitsauswahl, eine Planung, eine Be triebsmittelzuweisung und -bindung aus, die schließlich zu einer aus einer Datenpfad-Netzliste und einer Be schreibung des Controllers als einer endlichen Zustands maschine bestehenden leistungsoptimierten Architektur mit vollkommenem Power Management führt. Der Controller und die Datenpfad-Netzliste werden vereinigt und unter Ver wendung des SIS-Logiksynthesesystems auf die MSU-Stan dardzellenbibliothek abgebildet. Die Anordnung und das Leiten werden unter Verwendung von Hilfsmitteln aus der Programmfamilie OCTTOOLS ausgeführt.

Eine aus dem Entwurf extrahierte Schalterebenen-Schaltung wird unter Verwendung des Schalterebenensimulators IRSIM-CAP simuliert, wobei die geschaltete Kapazität aufge zeichnet und zum Abschätzen des Leistungsverbrauchs verwendet wird. Da der Leistungsverbrauch aus einer entwurfsbasierten Simulation abgeschätzt wird, können die Controller-Leistung, die Störimpulsleistung, die Verbin dungsleistung, die Taktleistung usw., die auf den höheren Ebenen nicht leicht in Rechnung gestellt werden können, genau abgeschätzt werden. Die für die Simulation verwen deten Eingangssignalfolgen werden dadurch erhalten, daß zunächst eine Gaußsche Folge mit einem verschwindenden Mittelwert erzeugt und das Ergebnis dann durch ein Auto regressionsfilter geleitet wird, um das gewünschte Niveau der zeitlichen Korrelation einzuführen.

Tab. 3 zeigt die erhaltenen experimentellen Ergebnisse. Die erste Spalte liefert den Namen der Schaltung. Hin sichtlich der Bewertungsprogramme sind Paulin Tseng und Dot prod wohlbekannte Bewertungsprogramme für die höhere Synthese. Lat und Fir sind ein Teil der HYPER-Distribu tion. Siehe See J. Rabaey, C. Chu, P-Hoang und M. Potkon jak, "Fast prototyping of data path intensive architectu res", IEEE Design 4 Test of Computers, S. 40-51, Februar 1991. Test1 ist der in Beispiel 3 gezeigte CDFG.

Die Hauptspalten P und A zeigen den Leistungsverbrauch und die Fläche der synthetisierten Schaltungen ohne und mit vollkommenem Power Management. Es wird angemerkt, daß die Steuersignale für die Multiplexer und für die Regi ster in der Schaltung in beiden Fällen in der Weise spezifiziert wurden, daß sie den Leistungsverbrauch der Konstruktion unter Verwendung der in 171 dargestellten Verfahren optimieren. Die Nebenspalten SCALP bzw. PPM beziehen sich auf Architekturen, die durch ein nicht modifiziertes SCALP (ohne die Hilfe des Power Manage ments) und durch die Verfahren der vorliegenden Erfindung optimiert wurden. Die Spalten P.S. und A.O. stellen die Leistungseinsparungen und die zusätzlichen Flächenbedarfe für Konstruktionen mit vollkommenem Power Management in Bezug auf leistungsoptimierte Konstruktionen, die aus dem nicht modifizierten SCALP erhalten wurden, dar. Die Zykluszeit der synthetisierten Konstruktionen wurde bei 25 ns festgelegt, während die Abtastperioden des SCALP und der Konstruktionen mit vollkommenem Power Management erzwungenermaßen gleich waren. Die erhaltenen Ergebnisse zeigen, daß die vorliegende Erfindung für die gleiche Verzögerung eine 26,045%ige mittlere Leistungsreduktion gegenüber den bereits leistungsoptimierten Schaltungen bei einem durchschnittlichen zusätzlichen Flächenbedarf von nur 1,89% erreicht.

V. SCHLUSSFOLGERUNGEN

In dieser Erfindung wird das Konzept des vollkommenen Power Managements geschaffen, das auf das Beseitigen einer unerwünschten Schaltaktivität in den Funktionsein heiten, aus denen eine datendominierte Schaltung besteht, gerichtet ist. Es wird gezeigt, daß die Art, in der die Variablen den Registern zugewiesen werden, einen großen Einfluß auf die Existenz unerwünschter Operationen haben kann. Es werden Bedingungen an die Variablenzuweisung abgeleitet, deren Erfüllung die Abwesenheit unerwünschter Operationen in den Funktionseinheiten, die einen Daten pfad bilden, sicherstellt. Auf der Grundlage dieser Bedingungen wird ein Algorithmus geschaffen, der in ein existierendes höheres Synthesesystem integriert werden kann, um die unerwünschte Schaltaktivität in den Funkti onseinheiten zu beseitigen. Eine Verwirklichung der Erfindung im Rahmen eines existierenden höheren Synthese systems, das auf die Leistungsoptimierung gerichtet ist, zeigte ohne irgendeine Minderung der Funktion der synthe tisierten Architektur eine bis zu zweifache Reduzierung der Leistung bei zusätzlichen Flächenbedarfen von nicht mehr als 6,4%.

Weitere Modifikationen und Änderungen an der Erfindung sind für den Fachmann auf dem Gebiet aus der vorstehenden Offenbarung und Lehre offensichtlich. Während hier nur bestimmte Ausführungen der Erfindung spezifisch beschrie ben wurden, ist somit klar, daß zahlreiche Modifikationen daran vorgenommen werden können, ohne von dem Geist und dem Umfang der Erfindung abzuweichen.

Claims

1. Verfahren zum Reduzieren des Leistungsverbrauchs in einer Folgeschaltung, die Funktionseinheiten enthält, wobei das Verfahren die Registerteilung und die Multiple xer-Konfiguration umfaßt,
wobei das Verfahren die unnötige Schaltaktivität in wenigstens einer Funktionseinheit beseitigt.

2. Verfahren zum Synthetisieren einer Folgeschaltung aus der Verhaltensspezifikation, wobei die Folgeschaltung mehrere Variablen besitzt, wobei das Verfahren umfaßt:

a) Verlängern der Lebensdauer einer oder mehre rer der mehreren Variablen; und
b) Neukonfigurieren der Multiplexer in der Folgeschaltung auf der Grundlage der Ergebnisse aus Schritt a.

3. Verfahren nach Anspruch 2, wobei das Verfahren ferner umfaßt:

c) Ausführen entweder des dynamischen Neubindens von Registern oder des Verdoppelns von Registern zum Vermeiden unnötiger Schaltoperationen, die von einer Teilmenge der mehreren Variablen hervorgerufen werden, wobei die Werte der Teilmenge der mehreren Variablen in mehr als einer Iteration erforderlich sind.

4. Verfahren zum Synthetisieren einer Folgeschal tung, die mehrere Funktionseinheiten enthält, wobei auf jede der mehreren Funktionseinheiten mehrere Operationen abgebildet werden, wobei jede der mehreren Operationen mit mehreren Eingangsvariablen verknüpft ist, wobei das Verfahren umfaßt:

a) Auswählen einer Funktionseinheit;
b) Auswählen einer Operation, die auf die Funk tionseinheit aus Schritt a abgebildet wird;
c) Auswählen einer mit der Operation aus Schritt b verknüpften Variablen;
d) Berechnen einer ersten Geburtszeit eines linken Eingangssignals einer nachfolgenden Operation der Operation aus Schritt b;
e) Berechnen einer zweiten Geburtszeit eines rechten Eingangssignals einer nachfolgenden Operation aus Schritt d;
f) Einstellen einer Todes zeit einer Variablen in der Weise, daß sie das Maximum der ersten Geburtszeit und der zweiten Geburtszeit ist;
g) Wiederholen der Schritte c-f für jede der mehreren mit der Operation aus Schritt 1 verknüpften Eingangsvariablen;
h) Wiederholen der Schritte b-g für jede der mehreren auf die Funktionseinheit aus Schritt a abgebil deten Operation; und
i) Wiederholen der Schritte a-h für jede Funkti onseinheit;
j) Konfigurieren der Multiplexer in der Weise, daß sie einige Eingangssignale für einen momentanen Iterationszyklus wie in einem vorausgehenden Iterations zyklus auswählen, falls der momentane Iterationszyklus ein Leerlauf ist.

5. Verfahren zum Synthetisieren einer Folgeschal tung, die mehrere Funktionseinheiten enthält, wobei auf jede der mehreren Funktionseinheiten mehrere Operationen abgebildet werden, wobei jede der mehreren Operationen mit mehreren Eingangsvariablen verknüpft ist, wobei das Verfahren umfaßt:

a) Auswählen einer Funktionseinheit;
b) Auswählen einer Operation, die auf die Funk tionseinheit aus Schritt a abgebildet wird;
c) Auswählen einer mit der Operation aus Schritt b verknüpften Variablen;
d) Identifizieren einer letzten auf die zweite Funktionseinheit abgebildeten Operation;
e) Identifizieren einer ersten auf die zweite Funktionseinheit abgebildeten Operation;
f) Auswählen einer Eingangsvariablen für die letzte Operation;
g) Identifizieren einer dritten Geburtszeit eines linken Eingangssignals der ersten Operation;
h) Identifizieren einer vierten Geburtszeit eines rechten Eingangssignals der ersten Operation;
i) Bestimmen, ob das Maximum der dritten Ge burtszeit und der vierten Geburtszeit größer als die Geburtszeit der Eingangsvariablen aus Schritt n ist;
j) Austauschen der Variablenzuweisungen, falls der in dem Austausch erlittene Organisationsaufwand unter einem vorgegebenen Schwellwert liegt und falls der Schritt q wahr ist;
k) Speichern der Werte der Eingangsvariablen des Schritts n in zusätzlichen Registern, falls der Organisa tionsaufwand über einem vorgegebenen Schwellwert liegt und falls der Schritt a wahr ist;
l) Wiederholen der Schritte f-k für alle der letzten Operation entsprechenden Eingangsvariablen;
m) Wiederholen der Schritte a-l für alle Funkti onseinheiten; und
n) Konfigurieren der Multiplexer in der Weise, daß sie für einen momentanen Iterationszyklus die glei chen Eingangssignale wie in einem vorausgehenden Iterati onszyklus auswählen, falls der momentane Iterationszyklus ein Leerlauf ist.

6. System zum Synthetisieren einer Folgeschaltung mit mehreren Variablen, wobei das System die Lebensdauern von wenigstens einer der mehreren Variablen verlängert, damit sich verlängerte Lebensdauern ergeben, und die Multiplexer auf der Grundlage der verlängerten Lebensdau ern neu konfiguriert.

7. System nach Anspruch 6, wobei das System entweder das dynamische Neubinden der Register oder das Verdoppeln der Register zum Vermeiden unnötiger Schaltoperationen ausführt, die von einer Teilmenge der mehreren Variablen verursacht werden, wobei die Werte der Teilmenge der mehreren Variablen in mehr als einer Iteration erforder lich sind.