DE19925411A1 - Controller-basiertes Powermanagement für sequentielle Schaltungen mit geringer Leistungsaufnahme - Google Patents

Abstract

Durch die vorliegende Erfindung wird eine controllerbasierte Powermanagementtechnik bereitgestellt, durch die Steuersignale mit geringem Zusatzaufwand umspezifiziert werden, um vorhandene Multiplexernetze und Funktionseinheiten umzukonfigurieren oder umzustrukturieren und unnötige Aktivitäten zu minimieren. Obwohl die Steuersignale in einer RTL-Implementierung vollständig spezifiziert sind, können sie in/unter bestimmten Zuständen/Bedingungen umspezifiziert werden, wenn die Datenpfadkomponenten, die sie steuern, nicht aktiv sein müssen. DOLLAR A Ein anderer Aspekt der vorliegenden Erfindung betrifft einen Algorithmus zum Ausführen eines Powermanagements durch Controller-Umspezifizierung, mit: Konstruieren eines Aktivitätsgraphen für jede Datenpfadkomponente, Identifizieren von Bedigungen, unter denen die Komponente nicht aktiv sein muß, und Umetikettieren des Aktivitätsgraphen, wodurch die entsprechenden Steuerausdrücke umspezifiziert werden. Durch den Algorithmus werden negative Auswirkungen der Controller-Umspezifizierung vermieden. Experimentelle Ergebnisse zeigen, (i) daß durch eine Controller-Umspezifizierung ein effizientes Powermanagement ausgeführt und erhebliche Leistungseinsparungen für steuerungsablaufintensive Strukturen oder Entwürfe erhalten werden können, die mehrere Herausforderungen an herkömmliche Powermanagementtechniken darstellen, und (ii) daß es wichtig ist, die verschiedenen potentiellen negativen Auswirkungen zu berücksichtigen, während eine ...

Description

I. Hintergrund der Erfindung I A. Bereich der Erfindung

Die vorliegende Erfindung betrifft die Reduzierung des Leistungsverbrauchs bzw. der Leistungsaufnahme sequentieller Schaltungen. Die Erfindung betrifft insbesondere ein System und ein Verfahren zum Reduzieren des Leistungsverbrauchs bzw. der Leistungsaufnahme. Die vorliegende Erfindung wird durch ein controller-basiertes Leistungs- oder Powermanage­ mentsystem, ein Verfahren zum Managen des Leistungsver­ brauchs bzw. der Leistungsaufnahme einer sequentiellen Schaltung und ein Computerprogrammprodukt zum Ausführen des Verfahrens realisiert.

I B. Verwandte Technik

Der Leistungsverbrauch bzw. die Leistungsaufnahme von CMOS-Schaltungen ist durch die dynamische Komponente domi­ niert, die immer dann belastet wird, wenn Signale in solchen Schaltungen Logikübergänge ausführen. In der Praxis zeigt sich jedoch, daß einige große Teile solcher in einer Schal­ tung auftretenden Logikübergänge unnötig sind. Diese unnöti­ gen Logikübergänge beeinflussen den am Schaltungsausgang er­ zeugten Wert nicht. Daher müssen in jedem Taktzyklus nicht alle Teile einer Schaltung aktiv sein.

Herkömmlich wurden mehrere Techniken verwendet, um den Leistungsverbrauch bzw. die Leistungsaufnahme einer Schal­ tung durch Eliminieren unnötiger Logikübergänge verschiede­ ner Signale in der Schaltung zu reduzieren. Der Ausdruck "Leistungs- oder Powermanagement" wird zusammengefaßt ver­ wendet, um auf diese Techniken zu verweisen.

Herkömmliche, als "Powermanagementtechniken für sequen­ tielle Schaltungen" (sequential circuit power management techniques) bezeichnete Techniken wurden für den Entwurf von Schaltungen auf der Logik- und der Architekturebene ange­ wandt. Bei einigen dieser Techniken werden entweder Takte torgesteuert oder verhindert, daß Flipflops/Register geladen werden, um den Leistungsverbrauch zu reduzieren. In diesen Techniken finden Einsparungen sowohl im Taktbaum als auch in der Logik statt, der Signale von den Flipflops zugeführt werden.

Eine andere Kategorie von Techniken wird als "Powerma­ nagement für kombinatorische Schaltungen" (combinational circuit power management) bezeichnet. Auch hierbei wird die Technik auf der Logik- und der Architekturebene angewandt. Kombinatorische Techniken identifizieren inaktive Teile ei­ ner Schaltung, die als "powermanagement-gesteuerte Teil- oder Unterschaltungen" ("sub-circuits under power manage­ ment") (SUP) bezeichnet werden, innerhalb des gleichen Takt­ zyklus und schalten sie aus bzw. deaktivieren sie.

Die meisten modernen Mikroprozessoren und Microcontrol­ ler für tragbare Anwendungen verwenden die Strategie der Torschaltung von Takteingangssignalen von Registern in einem Schaltungsblock, um unnötige Übergänge des Taktsignals sowie innerhalb des Schaltungblocks zu unterdrücken. Vergl. A. Correale Jr., "Overview of the Power Minimization Techniques Employed in the IBM PowerPC 4xx Embedded Processors", Proc. Int. Symp. Low Power Design, Seiten 75-80, April 1995; B. Suessmith and G. Paap III, "PowerPC 603 Microprocessor Power Management", Communications ACM, Bd. 37, Seiten 43-46 (Juni 1994) und V. Tiwari, R. Donnelly, S. Malik und R. Gonzalez, "Dynamic Power Management for Microprocessors: A Case Stu­ dy", Proc. Int. Conf. VLSI Design, Seiten 185-192 (Jan. 1997).

Eine andere in der Literatur beschriebene Technik ist eine automatische Synthesetechnik, in der Takte torgesteuert werden, um ihre Effizienz zu maximieren. Vergl. L. Benini, P. Siegel und G. DeMicheli, "Saving Power by Synthesizing Gated Clocks for Sequential Circuits", IEEE Dsign & Test of Computers, Seiten 32-41, Winter 1994; G. Tellez, A. Farrahi und M. Sarrafzadeh, "Activity Driven Clock Design for Low Power Circuits", Proc. Int. Conf. Computer-Aided Design, Seiten 62-65, Nov. 1995.

Herkömmlich wurde eine Technik zum Teilen einer Regi­ ster-Transfer-Level- (RTL-) Schaltung in Teilschaltungen verwendet, denen mehrere nichtüberlappende Takte zugeführt werden, um den Leistungsverbrauch zu reduzieren. Vergl. C. Papachristou, M. Spining und M. Nourani, "An effective Power Management Scheme for RTL Design Based on Multiple Clocks", Proc. Design Automation Conf., Seiten 337-342, Juni 1996.

Bei einer anderen Leistungsoptimierungstechnik wird das Ausgangssignal eines Logikblocks einen oder mehrere Zyklen im voraus berechnet. Das Ausgangssignal eines Logikblocks und die vorausberechnete Information werden verwendet, um Register am Eingang der Blöcke zu deaktivieren, die in zu­ künftigen Zyklen geladen werden. Vergl. M. Aldina, J. Mon­ teiro, S. Devadas, A. Gosh und M. Papaefthymiou, "Precompu­ tation-Based Sequential Logic Optimization for Low Power", IEEE Trans. VLSI Systems, Bd. 2, Seiten 426-436, Dez. 1994.

Konstrukteure oder Designer verfolgten herkömmlich auch das Konzept, unnötige Übergänge zu Logikblöcken zu vermei­ den, deren Eingängen keine Signale von Registern zugeführt werden, indem "Signalbarrieren", z. B. Durchgangstransistoren oder transparente Signalspeicher, eingefügt werden. Vergl. M. Aldina, J. Monteiro, S. Devadas, A. Gosh und M. Pa­ paefthymiou, "Precomputation-Based Sequential Logic Opti­ mization for Low Power", IEEE Trans. VLSI Systems, Bd. 2, Seiten 426-436, Dez. 1994 und V. Tiwari, S. Malik und P. As­ har, "Guarded Evaluation: Pushing Power Management to Logic Synthesis/Design", Proc. Int. Symp. Low Power Design, Seiten 221-226, Apr. D95 und A. Correale Jr., "Overview of the Po­ wer Minimization Techniques Employed in the IBM PowerPC 4xx Embedded Processors", Proc. Int. Symp. Low Power Design; Seiten 75-80, Apr. 1995.

Eine andere in der Literatur vorgeschlagene Technik ist eine als überwachte Bewertung (guarded evaluation) bezeich­ nete automatische Technik. Hierbei werden Teile einer Schal­ tung, die isoliert bzw. getrennt oder abgeschaltet bzw. de­ aktiviert werden können, für jeden Zyklus bestimmt. Vergl. V. Tiwari, S. Malik und P. Ashar, "Guarded Evaluation: Pus­ hing Power Management to Logic Synthesis/Design", Proc. Int. Symp. Low Power Design, Seiten 221-226, April 1995.

Außerdem wurde das Konzept der Operandentrennung in die High-Level-Synthese integriert. Hierbei werden transparente Signalspeicher an den Eingängen jeder Funktionseinheit ein­ gefügt, um die Werte des vorangehenden Zyklus in Steuer­ schritten des Programmablaufs einzufrieren oder festzuhal­ ten, in denen die Funktionseinheit nicht verwendet wird. Vergl. E. Musoll und J. Cortadella, "High-Level Synthesis Techniques for Reducing the Activity of Functional Units", Proc. Int. Symp. Low Power Design, Seiten 99-104, Apr. 1995.

Ein Verfahren zum Ausführen eines Programmablaufs wäh­ rend der High-Level-Synthese zum Maximieren der Möglichkei­ ten für eine Vorausberechnung wurde durch J. Monteiro, P. Ashar und S. Devadas, "Scheduling Techniques to Enable Power Management" Proc. Design Automation Conf., Seiten 349-352, Juni 1996 beschrieben. Software- und firmware-gesteuerte Po­ wermanagementtechniken sind bereits kommerzielle Praxis und werden durch Produkte, z. B. SPARClite Microprocessor von Fu­ jitsu und NoteBios 4.0 von Phoenix Technologies realisiert.

Die Entwicklung von High-Level-Design-Techniken, in de­ nen die vorstehend erwähnten Powermanagementtechniken ver­ wendet wurden, wurden häufig durch spezielle Anwendungsge­ biete vorangetrieben, z. B. durch Datenfluß- und Steuerab­ lauftechniken. Die Datenflußtechnik ist häufig ein arithme­ tisch intensives Anwendungsgebiet, das digitale Signalverar­ beitung, Bildverarbeitung, Graphik- und verschiedene Multi­ mediaanwendungen einschließt. Die Steuerablauftechnik ist dagegen häufig ein entscheidungsintensives Anwendungsgebiet, das Netzwerk-/Telekommunikationsprotokolle, systemintegrier­ te oder eingebettete Controller usw. einschließt.

Die Funktionsbeschreibungen datenflußintensiver Struk­ turen sind dominiert von arithmetischen Operationen, z. B. Addition, Subtraktion und Multiplikation. Die Funktionsbe­ schreibungen steuerablaufintensiver Strukturen sind dagegen durch verschachtelte Bedingungskonstrukte oder -strukturen, datenabhängige Schleifen und Vergleichsoperationen domi­ niert, wobei nur sehr wenig arithmetische Operationen vorge­ sehen sind.

Der Flächenbedarf, die Verzögerungszeit und die Lei­ stung struktureller RTL-Implementierungen datenflußintensi­ ver Entwürfe oder Strukturen sind durch arithmetische Ein­ heiten und Register im Datenpfad dominiert. Dagegen sind der Flächenbedarf, die Verzögerungszeit und die Leistung steuer­ ablaufintensiver Entwürfe oder Strukturen durch nicht- arithmetische Einheiten, z. B. durch Multiplexer, Bitmanipu­ lationseinheiten und Vergleicher, dominiert.

Eine große Anzahl von Entwürfen oder Strukturen sind in der Praxis steuerablaufintensiv. Eine wesentliche Anzahl von Entwürfen oder Strukturen enthält eine wesentliche Mischung aus Steuerablauf- und Datenflußstrukturen.

Steuerablaufintensive Strukturen weisen mehrere Eigen­ schaften auf, die Herausforderungen für herkömmliche Power­ managementtechniken darstellen:

• - Der Leistungsverbrauch ist dominiert durch eine Viel­ zahl kleiner Komponenten, z. B. Multiplexer, während Funktionseinheiten möglicherweise nur einen geringen Teil der Gesamtleistung verbrauchen. Vergl. A. Raghu­ nathan, S. Dey und N. K. Jha, "Glitch Analysis and Re­ duction in Register-Transfer-Level Power Optimization", Proc. Design Automation Conf., Seiten 331-336, Juni 1996. In solchen Schaltungen ist ein durch Einfügen transparenter Signalspeicher verursachter zusätzlicher Leistungsverbrauch vergleichbar mit Leistungseinsparun­ gen, die erhalten werden, wenn für Unterschaltungen, z. B. Multiplexernetze, ein Powermanagement ausgeführt wird.
• - Signale, die inaktive Zustände für verschiedene Unter­ schaltungen erfassen, treffen typischerweise spät ein (z. B. aufgrund des Vorhandenseins verschachtelter Bedin­ gungen in jedem Controllerzustand, wobei die inaktiven Zustände von Ausgangssignalen von Vergleichern im Da­ tenpfad abhängen können). Daher sind zeitliche Ein­ schränkungen, die auferlegt werden müssen, um herkömm­ liche Powermanagementtechniken anzuwenden, häufig nicht erfüllt, weil das "Freigabe"-Signal für die transparen­ ten Signalspeicher sich einschwingen bzw. einen Über­ gang ausführen muß, bevor seine Dateneingänge sich än­ dern können.
• - Das Vorhandensein wesentlicher Störimpulsaktivität so­ wohl in Steuer- als auch in Datenpfadsignalen muß be­ rücksichtigt werden, um optimale Leistungseinsparungen zu erzielen. Vergl. A. Raghunathan, S. Dey und N. K. Jha, "Glitch Analysis and Reduction in Register- Transfer-Level Power Optimization", Proc. Design Auto­ mation Conf., Seiten 331-336, Juni 1996.

Diese Probleme zeigen, daß herkömmliche Powermanage­ menttechniken für steuerablaufintensive Strukturen häufig ungeeignet sind. Andererseits verursachen sie negative Ef­ fekte, z. B. Schaltungsverzögerung, Störimpulsaktivität in Steuer- und Datenpfadsignalen und die Ausbildung fehlerhaf­ ter kombinatorischer Zyklen.

Obwohl in den vorstehend erwähnten herkömmlichen Syste­ men mehrere Techniken verwendet wurden, müssen noch immer wesentliche Einsparungen des Leistungsverbrauchs in Daten­ fluß- und Steuerablaufstrukturen erreicht werden. Der Lei­ stungsverbrauch sollte beim Entwurf täglich verwendeter Pro­ dukte weiter reduziert werden, um das durch sequentielle Schaltungen dargebotene Potential auszunutzen oder zu reali­ sieren. Beispielsweise sind Einsparungen des Leistungsver­ brauchs erforderlich, um Vorrichtungen, z. B. Personalcompu­ ter, Fernsteuerungen usw., weiter zu miniaturisieren.

Mindestens die folgenden Probleme existieren in her­ kömmlichen Techniken für die Entwicklung oder den Entwurf sequentieller Schaltungen:

• - eine wesentlicher Anteil der in sequentiellen Schaltun­ gen verbrauchten Leistung ist unnötig.
• - Durch herkömmliche Techniken wird keine so große Lei­ stungsreduzierung erreicht wie durch den aktuellen Stand der Technologie erreicht werden kann.
• - Herkömmliche Powermanagementtechniken verursachen Schaltungsverzögerungen.
• - Herkömmliche Powermanagementtechniken verursachen Stör­ impulsaktivität in Steuer- und Datenpfadsignalen.
• - Herkömmliche Powermanagementtechniken führen zur Aus­ bildung fehlerhafter kombinatorischer Zyklen.
• - Herkömmliche Powermanagementtechniken sind möglicher­ weise für steuerablaufintensive Strukturen ungeeignet.

II. Zusammenfassung der Erfindung

Es ist eine Aufgabe der vorliegenden Erfindung, die mit der Identifizierung und Reduzierung des unnötigen Leistungs­ verbrauchs sequentieller Schaltungen, einschließlich Daten­ fluß- und Steuerablaufschaltungen, verbundenen Probleme zu lösen, ohne die in herkömmlichen Techniken auftretenden ne­ gativen Effekte zu verursachen.

Es ist insbesondere Aufgabe der vorliegenden Erfindung, Powermanagement für Komponenten im Datenpfad einer sequenti­ ellen Schaltung unter Verwendung einer Controller- Umspezifizierung auszuführen.

Es ist eine andere Aufgabe der vorliegenden Erfindung, die Controller-Umspezifizierungsmethodologie für steuerab­ laufintensive Strukturen zu erweitern, die in jedem Control­ lerzustand mehrere Bedingungspfade aufweisen können.

Es ist eine noch andere Aufgabe der vorliegenden Erfin­ dung, Techniken bereitzustellen, durch die negative Effekte der Controller-Umspezifizierung, eine Erhöhung der Störim­ pulsaktivität von Signalen in der Schaltung, eine Erhöhung der Schaltungsverzögerung und die Ausbildung fehlerhafter kombinatorischer Schleifen vermieden werden.

Es ist eine noch andere Aufgabe der vorliegenden Erfin­ dung, einen Algorithmus zum Ausführen einer Powermanagement­ technik durch Controller-Umspezifizierung vorzuschlagen.

Um diese Aufgaben der Erfindung zu lösen, wird ein con­ troller-basiertes Powermanagementsystem für sequentielle Schaltungen mit einer Schaltungseingangseinheit, einem RTL- Schaltungsstrukturanalysator, einer Controller-Umstrukturie­ rungseinheit und einer Schaltungsausgangseinheit bereitge­ stellt, wobei die Schaltungseingangseinheit eine sequentiel­ le Schaltung empfängt, der RTL-Schaltungsstrukturanalysator die empfangene Schaltung für eine Controller-Umspezifizie­ rung analysiert und die Controller-Umstrukturierungseinheit die Schaltung unter Verwendung der Controller-Umspezifizie­ rung durch Ändern der Steuerlogik umstrukturiert, um den Leistungsverbrauch zu reduzieren.

Weitere Verbesserungen sind, daß die Umstrukturierungs­ einheit einen RTL-Einheit-Zähler, einen Aktivitätsgraphgene­ rator, eine Aktivitätsgraph-Umetikettierungseinrichtung und einen Steuerlogikreflektor aufweist, wobei der RTL-Einheit- Zähler RTL-Einheiten in der empfangenen Schaltung zählt, der Aktivitätsgraphgenerator einen Aktivitätsgraphen der RTL- Einheiten erzeugt und die Aktivitätsgraph-Umetikettie­ rungseinrichtung den Aktivitätsgraphen umetikettiert.

Weitere Verbesserungen sind, daß der RTL-Schal­ tungsstrukturanalysator eine RTL-Block-Identifizierungsein­ richtung, eine Datenabhängigkeitsgraph-Extrahiereinrichtung, eine Steuerungsabhängigkeitsgraph-Extrahiereinrichtung und eine RTL-Block-Sortiereinrichtung aufweist, wobei die RTL- Block-Identifizierungseinrichtung RTL-Blöcke in der empfan­ genen Schaltung identifiziert, die Datenabhängigkeitsgraph- Extrahiereinrichtung einen Datenabhängigkeitsgraphen der empfangenen Schaltung extrahiert und die Steuerungsabhängig­ keitsgraph-Extrahiereinrichtung einen Steuerungsabhängig­ keitsgraphen der empfangenen Schaltung extrahiert und die RTL-Sortiereinrichtung die identifizierten RTL-Blöcke unter Verwendung von Informationen vom Datenabhängigkeitsgraphen und vom Steuerungsabhängigkeitsgraphen ordnet.

Weitere Verbesserungen sind, daß die Controller- Umstrukturierungseinheit außerdem eine Verzögerungs­ bestimmungseinrichtung, eine Einrichtung zum Identifizieren kombinatorischer Schleifen und eine Schaltaktivitätbestim­ mungseinrichtung aufweist, wobei die Verzögerungsbestim­ mungseinrichtung in eine umstrukturierte Schaltung einge­ führte Verzögerungen bestimmt, die Einrichtung zum Identifi­ zieren kombinatorischer Schleifen kombinatorische Schleifen in der umstrukturierten Schaltung identifiziert und die Schaltaktivitätbestimmungseinrichtung alle Schaltaktivitäten in der umstrukturierten Schaltung bestimmt.

Gemäß einem anderen Aspekt der vorliegenden Erfindung wird ein Verfahren zum Ändern der Steuerlogik einer sequen­ tiellen Schaltung bereitgestellt, um den Leistungsverbrauch zu reduzieren, wobei das Verfahren die Datenlogik der se­ quentiellen Schaltung außer hinsichtlich einer wesentlichen Leistungsreduzierung in der Datenlogik nicht beeinflußt.

Gemäß einem noch anderer Aspekt der vorliegenden Erfin­ dung wird ein Verfahren zum Ändern der Steuerlogik für eine sequentielle Schaltung bereitgestellt, wobei das Verfahren die Schritte aufweist: Erzeugen eines Aktivitätsgraphen der sequentiellen Schaltung, Identifizieren inaktiver Zustände im Aktivitätsgraphen, Ändern der Steuerlogik durch Umetiket­ tieren der inaktiven Zustände, um umetikettierte inaktive Zustände zu erzeugen, und Umstrukturieren der Steuerlogik unter Verwendung der umetikettierten inaktiven Zustände. Weitere Verbesserungen weisen ein Verfahren zum Erzeu­ gen eines Aktivitätsgraphen auf, mit den Schritten: Identi­ fizieren von Zuständen mit verschachtelten Bedingungsopera­ tionen, Teilen der Zustände in mehrere Unterzustände, wobei jeder der mehreren Unterzustände einem wechselseitig aus­ schließenden Bedingungspfad entspricht, und Erzeugen eines Vertex im Aktivitätsgraphen für jeden Unterzustand.

Weitere Verbesserungen weisen ein Verfahren mit den Schritten auf: Umetikettieren inaktiver Zustände zum Ver­ hindern von Störimpulsen durch Umetikettieren von Zuständen und Unterzuständen, Identifizieren von Zuständen und Unter­ zuständen, in denen Störimpulse auftreten, und Rückgängigma­ chen Umetikettierung für Zustände und Unterzustände, in de­ nen Störimpulse auftreten.

Gemäß einer weiteren Verbesserung werden Übergangsver­ zweigungen zu einer Schaltungskomponente in der sequentiel­ len Schaltung identifiziert und umspezifiziert, bevor die Komponente umspezifiziert wird. Gemäß einer anderen Verbes­ serung werden Zustände und Unterzustände, für die bekannt ist, daß Ausgangssignale arithmetischer Logikeinheiten Stör­ impulse aufweisen, nicht für die Umbenennung ausgewählt.

Gemäß einer noch anderen Ausführungsform werden Unter­ zustände, die zu einer Verzögerung umspezifizierter Steuer­ signale führen, identifiziert und in einem einzigen Vertex vereinigt.

Gemäß einer anderen Ausführungsform wird ein High- Level-Verzögerungsbestimmungswerkzeug verwendet, um die Ver­ zögerung zu bestimmen.

Gemäß einer anderen Ausführungsform weist der Umetiket­ tierungsschritt ferner auf: Identifizieren von Paaren von Unterzuständen innerhalb eines Zustands, wobei mindestens ein Element der Paare inaktiv ist, Identifizieren weiterer Abhängigkeiten, die in die Schaltung eingeführt werden könn­ ten, wenn die identifizierten Paare von Unterzuständen um­ etikettiert werden, Ausführen eines linearen Zeitdurchlaufs der Schaltung, um zu bestimmen, ob ein kombinatorischer Zy­ klus eingefügt ist und Vereinigen der Paare von Unterzustän­ den in einem einzigen Vertex des Aktivitätsgraphen, wenn ein kombinatorischer Zyklus eingefügt ist.

Gemäß einem anderen Aspekt der vorliegenden Erfindung wird ein Powermanagementverfahren durch Steuerungs- Umspezifizierung bereitgestellt, wobei das Verfahren die Schritte aufweist: Teilen eines Datenpfades einer sequenti­ ellen Schaltung in RTL-Blöcke, Erzeugen eines oder mehrerer Abhängigkeitsgraphen, Ändern der Reihenfolge, in der die RTL-Blöcke für die Umspezifizierung ausgewählt werden sol­ len, um unter Verwendung der Abhängigkeitsgraphen eine ge­ ordnete Liste zu erzeugen, Auswählen der nächsten nicht- umspezifizierten RTL-Einheit in der geordneten Liste, Umspe­ zifizieren jedes Multiplexerbaums, der der ausgewählten RTL- Einheit Signale zuführt, und Wiederholen der Schritte für alle RTL-Einheiten in der geordneten Liste. In bevorzugten Ausführungsformen sind die Abhängigkeitsgraphen Datenabhän­ gigkeitsgraphen und Steuerungsabhängigkeitsgraphen.

Gemäß einer anderen Verbesserung wird die Umspezifizie­ rung ausgeführt unter Verwendung der Schritte: Erzeugen ei­ nes Aktivitätsgraphen, Vereinigen von Unterzuständen im Ak­ tivitätsgraphen, Markieren störimpulsbelasteter Dateneingän­ ge, Anwenden eines Etikettierungsverfahrens mit minimalem Aufwand auf den Aktivitätsgraphen, Rückgängigmachen der Eti­ kettierung für störimpulsbelastete Etiketten im Aktivitäts­ graphen, Wiederholen der Schritte für nicht-etikettierte Vertices, rekursives Umspezifizieren eines linken Multiple­ xerbaum-Vorgängers und rekursives Umspezifizieren eines rechten Multiplexerbaum-Vorgängers.

Gemäß einer weiteren Verbesserung ist ein Verfahren zum Vereinigen von Unterzuständen vorgesehen, mit den Schritten: Auswählen eines Zustands, Identifizieren eines Paars von Un­ terzuständen für den Zustand, Bestimmen, ob mindestens ein Unterzustand des Paars von Unterzuständen inaktiv ist, Ver­ einigen der Unterzustände, wenn sie inaktiv sind und wenn Zyklen erfaßt werden, oder wenn eine bestimmte Verzögerung größer ist als eine Zyklusperiode, und Wiederholen der Schritte für alle Paare von Unterzuständen in dem Zustand und Wiederholen der Schritte für alle Zustände.

Eine noch andere Verbesserung weist ein Umetikettie­ rungsverfahren mit den Schritte auf: Identifizieren eines nächsten nicht-etikettierten Vertex im Aktivitätsgraphen ge­ mäß einem vorgewählten Kriterium, Etikettieren nicht- etikettierter Vertices, so daß der Zusatzaufwand minimiert wird, unter Verwendung der Formel:

und Wiederholen des Schritts für jeden nicht-etikettierten Vertex.

Weitere Verbesserungen weisen ein Verfahren zum Iden­ tifizieren eines nächsten nicht-etikettierten Vertex auf, mit den Schritten: Identifizieren aller Übergänge von allen etikettierten Vertices zu V*, Zuweisen des Aufwandes aller Übergänge für alle im vorangehenden Schritt identifizierten Vertices, Addieren der Aufwände für alle Übergänge, um eine erste Summe zu bilden, Addieren der Aufwände für alle Über­ gänge im vorangehenden Schritt, um eine zweite Summe zu bil­ den, Addieren der ersten und der zweiten Summe und Wiederho­ len aller vorangehenden Schritte für alle nicht- etikettierten Vertices V* und Auswählen eines nicht- etikettierten Vertex V*, so daß der Endaufwand maximal ist.

Gemäß einem anderen Aspekt der vorliegenden Erfindung wird ein Computerprogrammprodukt für ein controller­ basiertes Powermanagementsystem für sequentielle Schaltungen mit einer Schaltungseingangseinheit, einem RTL-Schaltungs­ strukturanalysator, einer Controller-Umstrukturierungs­ einheit und einer Schaltungausgangseinheit bereitgestellt, wobei das Computerprogrammprodukt ein computerlesbares Medi­ um mit einem Schaltungseingangseinheitcode, einem RTL- Schaltungsstrukturanalysatorcode, einem Controller-Umstruk­ turierungseinheitcode und einem Schaltungsausgangseinheit­ code aufweist. Der Schaltungseingangseinheitcode ermöglicht einem Computer, eine sequentielle Schaltung zu empfangen. Der RTL-Schaltungsstrukturanalysatorcode ermöglicht einem Computer, die sequentielle Schaltung für eine Controller- Umspezifizierung zu analysieren. Der Controller-Umstruktu­ rierungseinheitcode ermöglicht einem Computer, die Schaltung unter Verwendung der Controller-Umspezifizierung durch Än­ dern nur der Steuerlogik umzustrukturieren, um den Lei­ stungsverbrauch zu reduzieren.

Gemäß weiteren Verbesserungen weist der Controller- Umstrukturierungseinheitcode einen RTL-Einheit-Zählercode, einen Aktivitätsgraphgeneratorcode, einen Aktivitätsgraph- Umetikettierungscode und einen Steuerlogikreflektorcode auf. Der RTL-Einheit-Zählercode ermöglicht einem Computer, RTL- Einheiten in der sequentiellen Schaltung zu zählen. Der Ak­ tivitätsgraphgeneratorcode ermöglicht einem Computer, einen Aktivitätsgraphen der RTL-Einheiten zu erzeugen. Der Aktivi­ tätsgraph-Umetikettierungscode ermöglicht einem Computer, den Aktivitätsgraphen umzuindizieren.

Gemäß noch weiteren Verbesserungen weist der RTL- Schaltungstrukturanalysatorcode einen RTL-Block-Identifi­ zierungseinrichtungscode, einen Datenabhängigkeitsgraph- Extrahiereinrichtungscode, einen Steuerungsabhängigkeits­ graph-Extrahiereinrichtungscode und einen RTL-Block-Sortier­ einrichtungscode auf. Der RTL-Block-Identifizierungs­ einrichtungscode ermöglicht einem Computer, RTL-Blöcke in der sequentiellen Schaltung zu identifizieren. Der Datenab­ hängigkeitsgraph-Extrahiereinrichtungscode ermöglicht einem Computer, einen Datenabhängigkeitsgraphen der sequentiellen Schaltung zu extrahieren. Der Steuerungsabhängigkeitsgraph- Extrahiereinrichtungscode ermöglicht einem Computer, einen Steuerungsabhängigkeitsgraphen der sequentiellen Schaltung zu extrahieren, und der RTL-Block-Sortiereinrichtungscode ermöglicht einem Computer, die RTL-Blöcke zu sortieren.

Gemäß weiteren Verbesserungen weist der Steuerungsum­ strukturierungseinheitcode ferner einen Verzögerungsbestim­ mungseinrichtungscode, einen Code einer Einrichtung zum Identifizieren kombinatorischer Schleifen und einen Schalt­ aktivitätsbestimmungseinrichtungscode auf. Der Verzögerungs­ bestimmungseinrichtungscode ermöglicht einem Computer, in eine umstrukturierte Schaltung eingeführte Verzögerungen zu bestimmen. Der Code der Einrichtung zum Identifizieren kom­ binatorischer Schleifen ermöglicht einem Computer, kombina­ torische Schleifen in der umstrukturierten Schaltung zu identifizieren, und der Schaltaktivitätbestimmungseinrich­ tungscode ermöglicht einem Computer, alle Schaltaktivitäten in der umstrukturierten Schaltung zu bestimmen.

III. Kurzbeschreibung der Zeichnungen

Die vorstehenden Aufgabe und Vorteile der vorliegenden Erfindung werden durch die nachstehende ausführliche Be­ schreibung bevorzugter Ausführungsformen der Erfindung unter Bezug auf die beigefügten Zeichnungen verdeutlicht; es zei­ gen:

Fig. 1 eine Schaltung, durch die ein Linienzeichnungs­ prozeß implementiert wird und die Teil eines Graphikcontrol­ lerchips ist;

Fig. 2(a) einen extrahierten Teil des Datenpfades der Schaltung von Fig. 1, der aus einem Addierglied und Multi­ plexerbäumen besteht, die dem Addierglied Signale zuführen;

Fig. 2(b) die Logikausdrücke für die Steuersignale, die dem Addierglied und seinem Multiplexerbaum zugeführt werden, und einen Aktivitätsgraphen für das Addierglied;

Fig. 2(c) einen modifizierten Aktivitätsgraphen für das Addierglied und die entsprechenden modifizierten Logikaus­ drücke für die vom Addierglied zugeführten Steuersignale;

Fig. 3(a) einen Teil des Datenpfades eines anderen Bei­ spiels einer RTL-Schaltung;

Fig. 3(b) Originalausdrücke für in Fig. 3(b) darge­ stellte Steuersignale Sel(18) und Sel(19);

Fig. 3(c) eliminierte, unnötige Aktivitäten bei M(18);

Fig. 4(a)-(b) einen Kleiner-als- (<) Vergleicher, der Teil des Datenpfades in einer RTL-Schaltung ist, und seinen Teil-Aktivitätsgraphen;

Fig. 5(a) einen Teil der programmgemäßen Funktionsspe­ zifikation für eine Dealer-Verarbeitung;

Fig. 5(b) eine Arithmetik-Logik-Einheit (ALU) und Mul­ tiplexer der RTL-Implementierung der in Fig. 5(a) darge­ stellten Dealer-Verarbeitung;

Fig. 5(c) einen Teil-Aktivitätsgraphen für die Arithme­ tik-Logik-Einheit (ALU) von Fig. 5(b);

Fig. 6(a) Störimpulsaktivitäten für ein auf der Einfü­ gung transparenter Signalspeicher basierendes Powermanage­ ment;

Fig. 6(b) Störimpulsaktivitäten für ein auf einer Con­ troller-Umspezifizierung basierendes Powermanagement;

Fig. 7(a) einen Vergleicher C M P2 im Strichcode- Datenpfad;

Fig. 7(b) einen Teil-Aktivitätsgraphen für den Verglei­ cher C M P2;

Fig. 7(c) eine Steuerlogik, die ein Signal Sel(7) er­ zeugt und eine Darstellung der Erzeugung von Störimpulsen im Steuersignal, das dem Vergleicher C M P2 zugeführt wird;

Fig. 8(a) eine RTL-Teilschaltung, die aus einem (=)- Vergleicher besteht, der einer Arithmetik-Logik-Einheit (ALU) Signale zuführt;

Fig. 8(b) die originalen und umetikettierten Aktivi­ tätsgraphen für den Vergleicher und die Signalstatistiken am Ausgang des Vergleichers von Fig. 8(a);

Fig. 8(c) die Erzeugung von Störimpulsen im Steuersi­ gnal;

Fig. 9(a) eine Controller-Umspezifizierung und eine Störimpuls-Ausbreitung oder Übertragung von Datensignalen für den Multiplexerbaum, der Teil des PixelGen-Datenpfades ist;

Fig. 9(b) eine Etikettierung des Aktivitätsgraphen, um die Nullverzögerung-Aktivität zu minimieren, die in Fig. 9(a)zu einer wesentlichen Störimpulsausbreitung von c56 führt;

Fig. 9(c) eine alternative Etikettierung für den Akti­ vitätsgraphen, durch die die Störimpulsausbreitung oder -übertragung in Fig. 9(a) reduziert wird;

Fig. 10(a) einen vereinfachten Aktivitätsgraphen für die ALU-Einheit im Dealer-Beispiel;

Fig. 10(b) die Vereinigung von Unterzuständen im Akti­ vitätsgraphen von Fig. 10(a);

Fig. 10(c) einen End-Aktivitätsgraphen zum Anzeigen vereinigter Unterzustandübergänge und ihrer Ausführungszähl­ werte;

Fig. 11(a) eine programmgemäße Teil-Funktions­ spezifikation zum Darstellen der Ausbildung fehlerhafter kombinatorischer Zyklen;

Fig. 11(b) eine Fig. 11(a) zugeordnete RTL-Schaltung zum Darstellen der durch die Controller-Umspezifizierung eingeführten Abhängigkeit in gestrichelten Linien;

Fig. 11(c) einen Aktivitätsgraphen für den (<)- Vergleicher mit einer Etikettierung, die zur Ausbildung feh­ lerhafter kombinatorischer Zyklen führt;

Fig. 12 eine Übersicht des erfindungsgemäßen Control­ ler-Umspezifizierungsalgorithmus;

Fig. 13 eine bevorzugte Ausführungsform eines Systems, das eine erfindungsgemäße Controller-Umspezifizierung aus­ führt;

Fig. 14 eine andere Ausführungsform der Umstrukturie­ rungseinheit;

Fig. 15 eine weitere Ausführungsform des RTL- Schaltungstrukturanalysators;

Fig. 16 weitere Ausführungsformen der Controller- Umstrukturierungseinheit;

Fig. 17 ein Ablaufdiagramm zum Darstellen einer Ausfüh­ rungsform eines Verfahrens zum Ändern der Steuerlogik für eine sequentielle Schaltung zum Reduzieren des Leistungsver­ brauchs;

Fig. 18 ein Ablaufdiagramm zum Darstellen einer Ausfüh­ rungsform eines erfindungsgemäßen Verfahrens zum Modifizie­ ren eines Aktivitätsgraphen hinsichtlich der Berücksichti­ gung verschachtelter Bedingungen;

Fig. 19 ein Ablaufdiagramm zum Darstellen einer Ausfüh­ rungsform eines erfindungsgemäßen Verfahrens zum Modifizie­ ren eines Aktivitätsgraphen hinsichtlich der Berücksichti­ gung verschachtelter Bedingungen;

Fig. 20 ein Ablaufdiagramm einer Ausführungsform eines Verfahrens zum Modifizieren eines Aktivitätsgraphen hin­ sichtlich der Berücksichtigung einer Zunahme der Schaltungs­ verzögerung;

Fig. 21 ein Ablaufdiagramm zum Darstellen einer Ausfüh­ rungsform eines Verfahrens zum Modifizieren eines Aktivi­ tätsgraphen hinsichtlich der Berücksichtigung zusätzlicher Abhängigkeiten und kombinatorischer Zyklen;

Fig. 22 ein Ablaufdiagramm zum Darstellen einer bevor­ zugten Ausführungsform eines Powermanagementverfahrens durch Controller-Umspezifizierung;

Fig. 23 ein Ablaufdiagramm zum Darstellen einer bevor­ zugten Ausführungsform eines erfindungsgemäßen Umspezifizie­ rungsverfahrens;

Fig. 24 ein Ablaufdiagramm zum Darstellen einer bevor­ zugten Ausführungsform eines erfindungsgemäßen Verfahrens zum Vereinigen von Unterzuständen; und

Fig. 25 ein Ablaufdiagramm zum Darstellen eines Verfah­ rens zum Anwenden eines Etikettierungsprozesses mit minima­ lem Aufwand.

IV. Ausführliche Beschreibung IV A. Controller-Umspezifizierung

In diesem Unterabschnitt werden umfassende Prinzipien diskutiert, die zum Verständnis der Controller-Umspezi­ fizierung beitragen. Die erfindungsgemäße Controller- Umspezifizierungstechnik bezieht sich teilweise auf das Po­ wermanagement im Datenpfad einer sequentiellen Schaltung. Hierbei wird die Leistungsreduzierung durch Umstrukturieren der Logik erreicht, die Steuersignale für den Datenpfad der sequentiellen Schaltung erzeugt. Eine erfindungsgemäß um­ strukturierte Schaltung weist in verschiedenen Datenpfadkom­ ponenten eine reduzierte Aktivität auf. Die Pfade, in denen die Aktivität reduziert ist, können interne Signale von Mul­ tiplexerbäumen und Eingangssignale für Funktionseinheiten und Vergleicher aufweisen.

Wie alle anderen im Hintergrundabschnitt beschriebenen herkömmlichen Powermanagementtechniken (z. B. Operandentren­ nung durch Einfügen transparenter Signalspeicher) basiert auch die erfindungsgemäße Technik auf der Auswertung bzw. Ausnutzung inaktiver Zustände für verschiedene Datenpfadkom­ ponenten. Die inaktiven Zustände sind die Controllerzustän­ de/-bedingungen, für die die berechneten Ergebnisse nicht verwendet werden.

Anders als bei herkömmlichen Techniken ist mit der er­ findungsgemäßen Controller-Umspezifizierung jedoch ein ge­ ringer zusätzlicher Aufwand verbunden, während ein Powerma­ nagementverfahren ausgeführt wird. Gemäß der vorliegenden Technik ändert der Konstrukteur oder Entwickler lediglich die Steuerlogik einer sequentiellen Schaltung, um die vor­ handenen Multiplexernetze umzukonfigurieren, die der SUP- Schaltung während der inaktiven Zustände/Bedingungen Signale zuführen, so daß unnötige Aktivitäten minimiert werden.

Nachstehend wird ein wichtiger Unterschied zwischen der Controller-Umspezifizierung und herkömmlichen Techniken er­ läutert. Während herkömmliche Powermanagementtechniken zum Ziel haben, die Aktivität in der SUP-Schaltung vollständig zu eliminieren, wird durch die vorliegende Erfindung die Ak­ tivität nur wesentlich reduziert. Erfindungsgemäß werden solche Aktivitäten nicht immer vollständig eliminiert. Durch das vorliegende Verfahren werden die gewünschten Ergebnisse erhalten, weil die Aktivität reduziert wird, während der mit herkömmlichen auf Unterbrechungen basierenden Techniken ver­ bundene Zusatzaufwand vermieden wird. Außerdem kann die er­ findungsgemäße Controller-Umspezifizierungstechnik zum Redu­ zieren der Aktivität auch in relativ kleinen Blöcken, z. B. in Multiplexern, verwendet werden.

Die Verwendung des Konzepts von vom Datenpfad hergelei­ teten Don't-care-Zuständen von Ausgangssignalen für den Con­ troller, und einer Analyse des Datenpfades wurde in herkömm­ lichen Systemen im Zusammenhang mit einer Reduzierung der Schaltungsflächen und der Verzögerungszeiten verwendet. Vergl. R. Bergamaschi, D. Lobo und A. Kuehlmann, "Control Op­ timization in High-Level Synthesis Using Behavioral Don't Cares", Proc. Design Automation Conf., Seiten 657-661, Juni 1992 und C. Y. Huang und W. H. Wolf, "Performance-Driven Syn­ thesis in Controller-Datapath Systems", IEEE Trans. VLSI Sy­ stems, Bd. 2, Seiten 68-80, März 1994.

In den erfindungsgemäßen Controller-Umspezifizierungs­ techniken werden "Don't-care"-Informationen verwendet. Ein Schlüsselaspekt der vorliegenden Erfindung ist jedoch die Weise, auf die diese "Don't-care"-Zustände spezifiziert wer­ den, um den Leistungsverbrauch im Datenpfad zu minimieren. Es ist von Interesse, daß für steuerablaufintensive Strukturen mehrere potentielle negative Effekte des Powerma­ nagements betrachtet werden. Beispielsweise kann durch Aus­ führen eines Powermanagementprozesses in einigen Teilen der Schaltung die Schaltungsverzögerung wesentlich erhöht wer­ den. Außerdem ist bekannt, daß Störimpulsaktivitäten in ty­ pischen RTL-Schaltungen wesentlich zum Gesamtleistungsver­ brauch beitragen können. Für steuerablaufintensive Struktu­ ren wurde durch A Raghunathan, S. Dey und N. K. Jha, "Glitch Analysis and Reduction in Register-Transfer-Level Power Op­ timization", Proc. Design Automation Conf., Seiten 331-336, Juni 1996 gezeigt, daß die Berücksichtigung von Störim­ pulsaktivitäten in Steuersignalen besonders wichtig ist.

In dieser Veröffentlichung wird eine umfassende Analyse der Effekte oder Auswirkungen des Powermanagements durch Controller-Umspezifizierung auf die Störimpulsaktivität in verschiedenen Steuer- und Datenpfadsignalen in der RTL- Schaltung dargestellt. Außerdem wird in dieser Veröffentli­ chung dargestellt, daß das Ignorieren dieser Effekte zu ei­ ner wesentlichen Zunahme des durch Störimpulse verursachten Leistungsverbrauchs führen kann, wodurch jegliche erhaltene Leistungseinsparungen mehr als ausgeglichen werden können.

Ähnlicherweise kann eine Controller-Umspezifizierung zur Erzeugung fehlerhafter kombinatorischer Zyklen in der RTL-Schaltung führen, die aufgrund der durch Low-Level- Synthesewerkzeuge auferlegten Einschränkungen inakzeptabel sein können. Basierend auf den vorstehend erwähnten Erkennt­ nissen wird durch die erfindungsgemäßen Techniken eine Con­ troller-Umspezifizierung ausgeführt, während die negative Effekte vermieden werden. Die erfindungsgemäßen Techniken werden auch verwendet, um einen Controller-Umspezifizie­ rungs-/Powermanagementalgorithmus für steuerablaufintensive Entwürfe oder Strukturen zu erzeugen.

IV B. Auswirkungen der Controller-Umspezifizierung

Die Effekte der Controller-Umspezifizierungstechnik können am besten anhand von Beispielen erläutert werden. Das folgende Beispiel zeigt die Effekte oder Auswirkungen der erfindungsgemäßen Umspezifizierung von Steuersignalen auf die Aktivität von Datenpfadsignalen. Es wird die in Fig. 1 dargestellte RTL-Schaltung betrachtet. Diese Schaltung im­ plementiert einen Linienzeichnungsprozeß (PixelGen) und ist Teil eines herkömmlich verwendeten Graphikcontrollerchips. In Fig. 2(a) ist ein Teil des PixeGen-Datenpfades von Fig. 1 extrahiert. Dieser besteht aus einem Addierglied ADD2 und Multiplexerbäumen M(2) und M(3), die dem Addierglied Ein­ gangssignale zuführen. Fig. 2(b) zeigt:

• a) die Logikausdrücke für die Steuersignale, die dem Ad­ dierglied ADD2 und seinen Multiplexerbäumen zugeführt werden (xi stellt eine decodierte Zustandsvariable dar, d. h., xi = 1, wenn der Controller auf den Zustand Si eingestellt ist), und
• b) einen Aktivitätsgraphen für das Addierglied, der die durch das Addierglied in jedem der Controllerzustände S0, S1, S2, S3, S4, S5 und S6 ausgeführten Operationen darstellt.

Ein Aktivitätsgraph zeigt allgemein die durch eine Ein­ heit in ihren verschiedenen Controllerzuständen ausgeführten Operationen. Die Vertices und Arcs im Aktivitätsgraphen ent­ sprechen den Controllerzuständen und den Zustandübergängen. Jeder oval dargestellte Vertex im Aktivitätsgraphen wird durch den durch das Addierglied im entsprechenden Control­ lerzustand ausgeführten Rechenvorgang etikettiert. Arcs sind die die Vertices verbindenden Pfeile. Sie stellen Übergänge von einem Zustand zu einem anderen dar.

Beispielsweise wird der Controllerzustand S3 betrach­ tet, für den Steuersignale Sel(2), Sel(3) beide den logi­ schen Wert "1" annehmen. Gemäß diesen Werten ist leicht er­ sichtlich, daß das Addierglied im Zustand S3 die Operation tempX + Dx ausführt.

Eine geschlossene oder Näherungsanalyse zeigt, daß in einigen Zuständen, z. B. S0, das Addierglied möglicherweise keine Operation ausführen muß. In solchen Zuständen werden die Ergebnisse möglicherweise nicht verwendet. Diese Zustän­ de werden als inaktive Zustände bezeichnet. Durch Verwendung der Programmablauf- und Zuweisungsinformationen aus der High-Level-Analyse können solche inaktiven Zustände basie­ rend auf dem Nichtvorhandensein von dem Addierglied zugeord­ neten Operationen leicht identifiziert werden. In Fig. 2(b) sind solche inaktiven Zustände durch dunkelgetönte Vertices dargestellt. Der durch das Addierglied in inaktiven Zustän­ den ausgeführte Rechenvorgang kann geändert werden, ohne daß die Funktionalität der Schaltungsstruktur beeinflußt wird. Daher ändert sich das Logikergebnis der Schaltung nicht, wenn der durch das Addierglied ausgeführte Rechenvorgang in solchen inaktiven Zuständen geändert wird.

Unter Berücksichtigung des vorstehenden Sachverhalts werden die Steuersignale Sel(2), Sel(3) unter Verwendung von Techniken gemäß in nachfolgenden Abschnitten ausführlicher beschriebenen weiteren Aspekten der vorliegenden Erfindung umspezifiziert.

Die erhaltenen Logikausdrücke für die umspezifizierten Steuersignale und der modifizierte Aktivitätsgraph für das Addierglied sind in Fig. 2(c) dargestellt. Bei diesem modi­ fizierten Aktivitätsgraphen haben sich die Etiketten der Vertices im Aktivitätsgraph geändert. In Zuständen S0, S1 und S2 haben sich die Etiketten von tempY + dY in tempX + dX geändert.

Außerdem werden im vorstehend erwähnten Beispiel zwei aufeinanderfolgende Zyklen in der Operation der PixelGen- Schaltung betrachtet, während denen der Controller den Zu­ standübergang S2 → S3 ausführt. Unter den Originalsteueraus­ drücken vor dem Umetikettieren ist im Addierglied Schaltak­ tivität vorhanden, weil seine Operanden sich von tempY (lin­ ker Operand) und Dy (rechter Operand) im Zustand S2 in tempX bzw. Dx im Zustand S3 ändern.

Andererseits bleiben unter den umspezifizierten Steuer­ ausdrücken alle Eingangsoperanden für das Addierglied sta­ bil. Dies ist der Fall, weil S2 und S3 nach dem vorstehend erwähnten Umetikettieren identische Etiketten haben.

Daher ist ersichtlich, daß durch Umspezifizieren der dem Addierglied zugeführten Steuersignale im vorstehenden Beispiel die Schaltaktivität reduziert wird. Als zur Umspe­ zifizierung äquivalente Operation wird durch Umetikettieren des Aktivitätsgraphen des Addierglieds die Schaltaktivität ebenfalls reduziert. Die Reduzierung der Schaltaktivität führt zu einem reduzierten Leistungsverbrauch des Addier­ glieds.

Während des tatsächlichen Betriebs der Schaltung werden jedoch auch vom Übergang S2 → S3 verschiedene Zustandüber­ gänge auftreten. Daher müssen alle ankommenden und abgehen­ den Arcs betrachtet werden, während entschieden wird, wie ein inaktiver Vertex im Aktivitätsgraphen umetikettiert wird. Dies wird unter Verwendung von Zustandübergangswahr­ scheinlichkeiten oder der Anzahl von Übergängen bzw. Über­ gangszählwerten beim Etikettieren des Aktivitätsgraphen er­ reicht. Ein solches Verfahren bildet einen anderen Aspekt der vorliegenden Erfindung und wird nachstehend formalisiert und beschrieben.

Außerdem kann das Umspezifizieren des Controllers auch zu einer reduzierten Aktivität in Multiplexerbäumen führen. Fig. 3(a) zeigt einen Teil des Datenpfads eines anderen Beispiels einer RTL-Schaltung, die aus einem Register mit den Multiplexern M(18) und M(19) besteht, die der Schaltung Signale zuführen. Das Register speichert den Wert von i.

Die Originalausdrücke für Steuersignale Sel(18) und Sel(19) sind in Fig. 3(b) dargestellt. Der Aktivitätsgraph für das Signal S(18) (das Ausgangssignal des 2-zu-1- Multiplexers), das anzeigt, welcher Operand (c28 oder Null) durch M(18) ausgewählt wird, ist ebenfalls in Fig. 3(b) dar­ gestellt. Die dunkelgetönten Vertices im Aktivitätsgraphen entsprechen Zuständen S0, S1, S2, S4, S6 und S7, in denen der Wert des Signals S(18) nicht verwendet wird. Es wird der Controller-Zustandübergang S7 → S1 betrachtet. Das Signal c28 ist das Ausgangssignal einer Arithmetik-Logik-Einheit (ALU) (in der Figur nicht dargestellt), deren Eingangssigna­ le sich während des vorstehend erwähnten Controller- Zustandübergangs S7 → S1 ändern. Daher ändert sich der Wert des dem Multiplexer zugeführten Operanden (c28) selbst, wo­ durch im Ausgangssignal des Multiplexers M(18) unnötige Ak­ tivität auftritt.

Durch Umspezifizieren der Steuersignale unter Verwen­ dung der erfindungsgemäßen Techniken, wie in Fig. 3(c) dar­ gestellt, wird diese unnötige Aktivität bei M(18) elimi­ niert. Wie in der Figur dargestellt, ändern sich die Zustän­ de S0, S1, S2, S4, S6 und S7 von c28 auf Null.

Ein herkömmliches Verfahren zum Reduzieren der Aktivi­ tät im in Fig. 3(a) dargestellten Multiplexerbaum besteht darin, transparente Signalspeicher an einem ausgewählten Da­ teneingang eines Multiplexers einzufügen, der einem Signal c28 zugeordnet ist, und anschließend diese transparenten Si­ gnalspeicher in Zuständen S0, S1, S2, S4, S6 und S7 "einzu­ frieren". In diesem Fall würde das damit verbundene Overhead bzw. der Zusatzaufwand in neun transparenten Signalspeichern bestehen. Das Signal c28 ist ein 8-Bit-Signal. Es ist deut­ lich, daß dieses Verfahren zu einem wesentlichen Aufwand hinsichtlich der Schaltungsflächen und außerdem zu einem vergleichsweise hohen Leistungsverbrauch führt, während nur geringe Leistungseinsparungen im Multiplexerbaum erhalten werden.

Außerdem nimmt, wenn gemäß den herkömmlichen Verfahren transparente Signalspeicher eingefügt werden, wie vorstehend beschrieben, und die Schaltung bezüglich des Leistungsver­ brauchs ausgewertet wurde, nachdem sie in einer 1.0µ- Standard-Bibliothek eingetragen wurde (es wurden Signalspei­ cher mit geringer Leistungsaufnahme verwendet, um das Lei­ stungs-Overhead zu minimieren), der Gesamtleistungsverbrauch der Schaltung von anfangs 4,495 mW auf 4,461 mW ab, nachdem die Unterbrechungsschaltung eingefügt wurde. Dies entspricht einer sehr geringen Verminderung des Leistungsverbrauchs.

Andererseits wird, wenn die Steuersignale erfindungsge­ mäß umspezifiziert werden, wie in Fig. 3(c) dargestellt, der Gesamtleistungsverbrauch von 4,495 mW auf 4,291 mW redu­ ziert.

Allgemein können im Fall eines b-Bit-m-zu-1-Multi­ plexerbaums gemäß dem herkömmlichen Verfahren b+m+log m transparente Signalspeicher erforderlich sein. In erster Nä­ herung kann vorausgesetzt werden, daß der Aufwand bezüglich der transparenten Signalspeicher sowie die Möglichkeit von Einsparungen hinsichtlich des Ausmaßes der ausschaltbaren Logik ähnlich skaliert werden kann. Dies zeigt, daß es un­ wahrscheinlich ist, daß durch die erfindungsgemäße Verwen­ dung von transparenten Signalspeichern eine wesentliche Lei­ stungsreduzierung für größere Multiplexer erhalten wird.

Die vorstehende Hypothese kann in der Praxis für mehre­ re Multiplexerbäume in RTL-Schaltungsbeispielen verifiziert werden. Auch größere Blöcke, z. B. Arithmetik-Logik-Einheiten (ALU) und Vergleicher in der vorstehend erwähnten PixelGen- RTL-Schaltung weisen wesentliche Probleme bezüglich des Po­ wermanagements bei Verwendung der herkömmlichen Technik auf, in der transparente Signalspeicher eingefügt werden.

Beispielsweise werden transparente Signalspeicher vor dem Subtrahierglied SU B1 in Fig. 1 angeordnet. Basierend auf einer Analyse der Programmablauf- und der Zuweisungsin­ formation, die durch in der Schaltung erzeugte High-Level- Synthesewerkzeuge verfügbar sind, sind die hergeleiteten in­ aktiven Bedingungen für SU B1 durch x0+x1+x3+x4.c8.c32+x5 ge­ geben.

Der Schaltung wird eine Steuerschaltung hinzugefügt, um den vorstehenden Ausdruck zu implementieren. Es zeigt sich, daß die Ankunftszeit des Steuersignals 117,1 ns beträgt. Der früheste Zeitpunkt, an dem Eingangssignale des Subtrahier­ gliedes SU B1 einen Übergang ausführen können, beträgt 4,7 ns. Dies ergibt sich aufgrund des Pfades vom Ausgang des Re­ gisters tempY durch den 2-zu-1-Multiplexer zum linken ein­ gang des Subtrahiergliedes SU B1. Die Zeitsteuerbedingung, die erforderlich ist, um zu gewährleisten, daß eine frühe Änderung in den Dateneingangssignalen sich durch die Power­ managementschaltung nicht verschiebt, ist nicht erfüllt.

Dann wird nur unter Verwendung decodierter Zustandsva­ riablen ein Ausdruck für einen reduzierten Satz inaktiver Zustände hergeleitet.

Das vorstehende Problem tritt in allen Funktionseinhei­ ten und Vergleichern der PixelGen-Schaltung auf, so daß es schwierig wird, ein herkömmliches Powermanagementverfahren auf solche Strukturen anzuwenden. Dadurch werden die Vortei­ le der erfindungsgemäßen Umspezifizierungsverfahren deut­ lich.

IV C. Umspezifizierung durch Umetikettieren des Aktivi­ tätsgraphen unter Verwendung von Zustandübergangszähl­ werten und Aktivitätsmatrizen

Nachstehend wird die Umetikettierung des Aktivitätsgra­ phen diskutiert. Dies kann wiederum unter Verwendung von Beispielen verdeutlicht werden.

Es wird ein Kleiner-als- (<) Vergleicher betrachtet, der Teil des Datenpfades einer RTL-Schaltung ist, und sein Teil-Aktivitätsgraph. Diese sind in den Fig. 4(a) bzw. 4(b) dargestellt. Der Vertex S3 im Aktivitätsgraphen ent­ spricht einem inaktiven Zustand des Vergleichers. Der Akti­ vitätsgraph zeigt außerdem alle Vertices mit ankommenden Arcs vom oder abgehenden Arcs zum Vertex S3. Die Vertices S1, S2, S4 und S5 weisen Etiketten L1 (a < b) L2 (c < d), bzw. L3 (e < d) auf.

In diesem Beispiel kann unter Verwendung der erfin­ dungsgemäßen Techniken der Vertex S3 durch ein anderes Eti­ ket des Satzes {L1, L2, L3} etikettiert werden. Es ist deut­ lich, daß durch solches Umetikettieren die Aktivität und da­ durch der Leistungsverbrauch im Vergleicher reduziert wird.

Die erwartete (oder mittlere) Anzahl von Bitübergängen in den Eingangssignalen des Vergleichers wird als Maß seines Leistungsverbrauchs verwendet. Es können jedoch auch kompli­ ziertere oder höherentwickelte Modelle für den Leistungsver­ brauch im Datenpfad verwendet werden, um die erfindungsgemä­ ße Controller-Umspezifizierungstechnik zu realisieren.

Nachstehend wird der tatsächliche Umetikettierungspro­ zeß unter Verwendung einer bevorzugten Ausführungsform eines erfindungsgemäßen Verfahrens beschrieben. Für jeden Arc Si → Sj im Aktivitätsgraphen bezeichnen P(Si → Sj) die Wahr­ scheinlichkeit eines Controllerzustandübergangs von Si zu Sj. Es wird eine Aktivitätsmatrix AM_Si→_Sj für den Arc Si → Sj im Aktivitätsgraphen erzeugt. Eine solche Matrix (AM) spei­ chert den Aufwand bezüglich der mittleren Bitübergänge, die für verschiedene Kombinationen von Etiketten erhalten wer­ den, die den Vertices Si und Sj zugeordnet werden können. Die Reihen von AM_Si→_Sj werden durch den Satz möglicher Eti­ ketten etikettiert, die Si zugeordnet werden können. Ähnli­ cherweise werden die Spalten von AM_Si→_Sj durch den Satz mög­ licher Etiketten etikettiert, die Si zugeordnet werden kön­ nen.

Als Beispiel wird der Arc vom Vertex S1 zum Vertex S3 im in Fig. 4(a) dargestellten Aktivitätsgraphen betrachtet. Weil das Etikett von S1 als L1 fixiert ist, weist die Akti­ vitätsmatrix AM_S1→_S3 gültige Einträge in nur einer Reihe auf, die durch L1 etikettiert ist. Die den inaktiven Zuständen entsprechenden Vertices im Aktivitätsgraphen werden umeti­ kettiert, während versucht wird, den Gesamtetikettieraufwand (Total Labeling Cost) zu minimieren, der durch folgende For­ mel berechnet wird:

L(Si) bezeichnet das dem Vertex Si im Aktivitätsgraphen zugeordnete Etikett. Für das Beispiel von Fig. 4(a)-(b) ist der Aufwand zum Etikettieren des Vertex S3 mit einem Etikett L* gegeben durch:

AM_S1→_S3 [L1,L*].P(S1→S3) + AM_S2→_S3 [L2,L*].P(S2→ S3) + AM_S3→_S4 [L*,L2].P(S3→S4)+ AM_S3→_S5 [L*,L3].P(S3→S5)

Es sollte betont werden, daß es das Ziel ist, L* ∈ {L1, L2, L3} so zu wählen, daß der durch die vorstehende Glei­ chung gegebene Etikettieraufwand minimiert wird.

Ein markantes Merkmal steuerablaufintensiver Spezifika­ tionen oder Entwürfe ist das Vorhandensein verschachtelter Bedingungen. In Programmabläufen solcher Spezifikationen, in denen verschachtelte Bedingungen vorhanden sind, können in einem einzigen Zustand mehrere wechselseitig ausschließende Folgen oder Sequenzen (Pfade) von Operationen vorgesehen sein. In nachfolgenden Abschnitten werden verschiedene Ef­ fekte oder Auswirkungen der Bedingungen innerhalb von Zu­ ständen und auf das controller-basierte Powermanagement dis­ kutiert. Außerdem werden Ausführungsformen der vorliegenden Erfindung diskutiert, durch die die in einem solchen Fall auftretenden Probleme gelöst werden.

IV D. Controller-Umspezifizierung für steuerablaufinten­ sive Strukturen

In diesem Abschnitt wird eine Ausführungform der vor­ liegenden Erfindung beschrieben, durch die das Basisverfah­ ren der Controller-Umspezifizierung erweitert wird, um steu­ erablaufintensive Strukturen zu handhaben. In solchen Struk­ turen können in jedem Controllerzustand verschachtelte Be­ dingungsoperationen vorhanden sein, die zu mehreren wechsel­ seitig ausschließenden Bedingungspfaden, sogenannten Unter­ zuständen, führen.

D. h., in einem beliebigen vorgegebenen Taktzyklus (oder Controllerzustand) wird durch den Datenpfad ein anderer Satz von Operationen ausgeführt. Dies hängt davon ab, wie Bedin­ gungszweige innerhalb des Zustands ausgewertet werden. Im Aktivitätsgraphen für eine Datenpfadkomponente wird entspre­ chend jedem wechselseitig ausschließenden Pfad oder Unterzu­ stand in jedem Zustand ein Vertex erzeugt. Früher wurde für jeden Zustand nur ein einziger Vertex erzeugt.

Die Bedeutung von Unterzuständen kann unter Verwendung von Beispielen verdeutlicht werden. Es wird ein in Fig. 5(a) dargestellter Teil-Programmablauf für eine Dealer- Verarbeitung betrachtet. Der Programmablauf wurde ausgeführt mit dem Ziel, die mittlere Anzahl von Taktzyklen zu minimie­ ren, die zum Ausführen dieser Spezifikation erforderlich sind und den Ressourcegrenzen eines (<)-Vergleichers und ei­ ner (±)-ALU-Einheit und den Verzögerungsgrenzen unterlie­ gen, durch die eine Datenverknüpfung oder -verkettung zwi­ schen dem (<)-Vergleicher und der ALU-Einheit verhindert wird (um die Bildung eines langen Datenpfades zu vermeiden).

Beispielsweise ist die Operation Card = Card + 1 im Zu­ stand 5S5 nicht vorgesehen, um eine Datenverknüpfung oder -verkettung zwischen dem Vergleicher, der die Operation Card < Decksize ausführt, und der ALU-Einheit, die die Operation Card = Card + 1 ausführt, zu vermeiden. Im Zustand 5S5 sind zwei Bedingungen vorhanden: Suits [Card] ≠ NoSuit und Card < Decksize. Diese Vergleichsoperationen werden durch einen Gleich- und einen Kleiner-als-Vergleicher im Datenpfad aus­ geführt, dessen Ausgangssignale c1 bzw. c2 sind.

Insbesondere sind im Zustand 5S5 drei wechselseitig ausschließende Pfade vorhanden, die den Fällen {c1 = 0, C2 = 1}, {c1 = 0, c2 = 0} bzw. {c1 = 1} entsprechen. Fig. 5(b) zeigt die (±)-ALU-Einheit und die zugeordneten Multiple­ xerbäume, die Teil der RTL-Implementierung sind.

Ein Teil des Aktivitätsgraphen für die ALU-Einheit ist in Fig. 5(c) dargestellt, die die Aktivität der ALU-Einheit in Zuständen 5S4, 5S5 und 5S7 zeigt. Der Zustand 5S5 des Programmablaufs wurde in drei Unterzustände des Aktivitäts­ graphen unterteilt, die jeweils einem der drei möglichen wechselseitig ausschließenden Pfade im Programmablauf ent­ sprechen.

Die Unterzustände im Aktivitätsgraphen sind durch die Kombination aus dem Zustand und den Vergleicherausgangs­ signalen gekennzeichnet, die veranlassen, daß der entspre­ chende Bedingungspfad gewählt wird. Die ALU-Einheit muß nur im Unterzustand 5S5.c1 eine Operation ausführen. Die beiden anderen Unterzustände 5S5.c1.c2 und 5S5.c1.c2 sind inaktive Un­ terzustände, die dunkelgetönt dargestellt sind. Die Arcs im Aktivitätsgraphen bezeichnen Übergänge zwischen Unterzustän­ den und sind mit einer Zahl versehen, die anzeigt, wie häu­ fig der entsprechende Unterzustandübergang während der Simu­ lation eines bestimmten Bewertungstests ausgeführt wurde.

Gemäß der originalen Steuersignalspezifikation wird, immer wenn der Controller sich im Zustand 5S5 befindet, die Operation DeckSize-Seed ausgeführt (einschließlich in den inaktiven Unterzuständen 5S5.c1.c2 und 5S5.c1.c2). Für eine Aus­ führungsfolge der Unterzustände {5S5.c1.c2, 5S7, 5S5.c1.c2, . . .} wird die ALU-Einheit folgende Operationsfolge ausführen: {DeckSize-Seed, Card + 1, Decksize-Seed, . . .}, wodurch in der ALU-Einheit eine wesentliche Aktivität erzeugt wird. Es wird jeder Unterzustand des Zustands 5S5 separat betrach­ tet, und das Vorhandensein der beiden inaktiven Unterzustän­ de führt dazu, daß ihnen ein Etikett zugeordnet werden kann, das von dem Etikett des aktiven Unterzustands verschieden ist. Beispielsweise ist es, weil der Unterzustand 5S5.c1.c2 Übergänge zum und vom Zustand 5S7 aufweist, sinnvoll, den Unterzustand 5S5.c1.c2 mit dem gleichen Etikett zu versehen wie das des Zustands 5S7 (Card + 1), weil der Wert von Card sich im Zustand 5S5 nicht ändert.

Nach dem Umetikettieren bleiben für eine Folge von Zu­ standübergängen, die die Zustände 5S5 und 5S7 einschließen, gemäß einem alternativen Verfahren die ALU-Operanden für Card + 1 stabil, wodurch unnötige Aktivität in der ALU- Einheit vermieden wird.

IV E. Auswirkungen eines controller-basierten Powermana­ gementverfahrens auf die Störimpulsaktivität

Wie vorstehend erwähnt, versucht die Controller- Umspezifizierung die mittlere oder erwartete Nullverzöge­ rung-Schaltaktivität an den Eingängen der betrachteten RTL- Komponente zu minimieren. Das Minimieren der Nullverzöge­ rungsaktivität alleine führt jedoch aufgrund des Vorhanden­ seins von Störimpulsaktivität in verschiedenen Steuer- und Datenpfadsignalen in der RTL-Schaltung nicht zu einer Redu­ zierung des Leistungsverbrauchs. Gemäß einem Aspekt der vor­ liegenden Erfindung wird ein Verfahren bereitgestellt, durch das Störimpulsaktivität reduziert wird, während Powermanage­ menttechniken angewendet werden. Es ist jedoch notwendig, zu verstehen, wie Störimpulse erzeugt werden, um diesen Aspekt der vorliegenden Erfindung umfassend zu beurteilen bzw. zu verstehen.

Es ist bekannt, daß das Vorhandensein von Störimpulsen in Steuersignalen zur Erzeugung und Ausbreitung einer we­ sentlichen Menge von Störimpulsen durch die verschiedenen Datenpfadkomponenten führen kann. Verg. A. Raghunathan, S. Dey und N. K. Jha, "Glitch Analysis and Reduction in Regi­ ster-Transfer-Level Power Optimization", Proc. Design Auto­ mation Conf., Seiten 331-336, Juni 1996. Tatsächlich können alle Leistungseinsparungen durch eine durch Störimpulse ver­ ursachte Erhöhung des Leistungsverbrauchs kompensiert wer­ den.

Die vorstehenden negativen Effekte werden deutlich, während beliebige Powermanagementtechniken angewendet wer­ den. Ähnlicherweise trifft die Betrachtung einer wesentli­ chen Störimpulsaktivität in verschiedenen Signalen während des Powermanagements auch auf eine auf einer Controller- Umspezifizierung basierende Powermanagementtechnik zu. Ähn­ liche Techniken können in anderen Powermanagementtechniken verwendet werden.

Fig. 6(a)-(b) zeigen eine Übersicht der möglichen negativen Effekte oder Auswirkungen des Powermanagements auf die Störimpulsaktivität. Fig. 6(a) zeigt eine allgemeine Powermanagementtechnik für eine Schaltung, die transparente Signalspeicher verwendet, um zu verhindern, daß Übergänge sich zu Eingängen von Unterschaltungen ausbreiten, wenn eine geeignete Steuerbedingung wahr ist.

In den Dateneingängen der transparenten Signalspeicher in der vorstehenden Schaltung kann Störimpulsaktivität vor­ handen sein. Dies kann dazu führen, daß Übergänge zu den Eingängen der SUP-Schaltungen übertragen werden. Die in Fig. 6(a) dargestellten Wellenformen zeigen diese Situation.

Es wird vorausgesetzt, daß der transparente Signalspei­ cher auf einen transparenten oder Durchlaßmodus eingestellt ist, wenn das "Freigabe"-Signal den logischen Wert "0" auf­ weist, und auf einen Haltemodus, wenn das "Freigabe"-Signal den logischen Wert "1" hat. Die Störimpulsaktivität am Da­ teneingang des transparenten Signalspeichers wird zu den Eingängen der SUP-Schaltungen übertragen, wodurch ein unnö­ tiger Leistungsverlust auftritt. Ähnlicherweise kann das dem transparenten Signalspeicher zugeführte "Freigabe"-Signal ebenfalls störimpulsbelastet sein. Die Auswirkungen eines störimpulsbelasteten "Freigabe"-Signals sind abhängig von der exakten Implementierung des transparenten Signalspei­ chers. Für eine typische Implementierung, bei der Invertie­ rer und Torschaltungen verwendet werden, beeinflussen Stör­ impulse im "Freigabe"-Signal das Ausgangssignal des Signal­ speichers nur dann nicht, wenn das Datensignal störimpuls­ frei ist.

Fig. 6(b) zeigt eine Übersicht der Auswirkungen der controller-basierten Powermanagementtechnik auf die Störim­ pulsaktivität. Weil bei der erfindungsgemäßen Technik ein Teil der Steuerlogik umstrukturiert wird, kann die Störim­ pulsaktivität in einem oder in mehreren umspezifizierten Steuersignalen erhöht sein.

Außerdem können einige Dateneingangssignale, die dem Multiplexernetz am Eingang der SUP-Schaltung zugeführt wer­ den, selbst störimpulsbelastet sein (z. B. Ausgangssignale der mit anderen Einheiten verketteten ALU-Einheiten). Wenn die Störimpulsaktivität der Datensignale während der Umspe­ zifizierung ignoriert wird, kann dies zu einer erhöhten Stör­ impulsübertragung von den störimpulsbelasteten Datensigna­ len durch den Multiplexerbaum führen, der der SUP-Schaltung Signale zuführt.

Die beiden vorstehend beschriebenen Effekte können als lokale Effekte bezeichnet werden, weil die Zunahme der Stör­ impulsaktivität in einigen Steuersignalen oder Signalen von Multiplexerbäumen beginnt, die der SUP-Schaltung direkt zu­ geführt werden. Außerdem ist die Betrachtung globaler Effek­ te der Umspezifizierung auf die Störimpulsaktivität wichtig.

Beispielsweise wird vorausgesetzt, daß die SUP- Schaltung ein Vergleicher ist, dessen Ausgangssignal als Eingangssignal für einen Teil der Steuerlogik verwendet wird. Das Umspezifizieren der Steuerlogik, die der SUP- Schaltung Signale zuführt, kann zur Erzeugung einer wesent­ lichen Störimpulsaktivität in Steuersignalen führen, die vom Ausgangssignal der SUP-Schaltung abhängig sind.

Allgemein können alle Steuersignale im transitiven Fan- Out der SUP-Schaltung, d. h. alle Steuersignale, zu denen ein Pfad vom Ausgang der SUP-Schaltung existiert, der nur durch kombinatorische Elemente verläuft, aufgrund der Umspezifi­ zierung der Steuersignale, die der SUP-Schaltung zugeführt werden, störimpulsbelastet werden.

In nachfolgenden Abschnitten werden verschiedene Effek­ te analysiert, die ein auf einer Controller-Umspezifizierung basierendes Powermanagement auf die Störimpulsaktivität der Steuer- und Datensignale in der Schaltung haben kann, und werden Techniken dargestellt, die in verschiedenen Aspekten der vorliegenden Erfindung verwendet werden, um zu gewähr­ leisten, daß die Leistungseinsparungen durch eine Erhöhung des durch Störimpulse verursachten Leistungsverbrauchs nicht kompensiert werden.

IV E.1 Störimpulsaktivität in umspezifizierten Steuersi­ gnalen

Durch Umetikettieren eines Zustands oder Unterzustands im Aktivitätsgraphen einer RTL-Einheit, wodurch die Aktivi­ tät in der Einheit reduziert werden soll, können Störimpulse in dem (den) erhaltenen umspezifizierten Steuersignal(en) erzeugt werden. Um die Erzeugung von Störimpulsen in umspe­ zifizierten Steuersignalen darzustellen, wird ein (=)- Vergleicher C M P2 und der Multiplexer betrachtet, der ihm Signale zuführt, die Teil einer RTL-Implementierung eines Strichcode-Lesegeräts sind, wie in Fig. 7(a) dargestellt.

Fig. 7(b) zeigt einen Teil-Aktivitätsgraphen für den Vergleicher C M P2. Der Zustand 7S3 ist in zwei Unterzustän­ de 7S3.c20 und 7S3.c20 geteilt, die beide inaktive Unterzu­ stände des Vergleichers C M P2 sind. Der Original- Steuerausdruck (Sel(7) = x4) impliziert, daß der Vergleicher im Zustand 7S4 eine Operation limit = 0 ausführt; in allen anderen Zuständen und Unterzuständen wird eine Operation li­ mit = black ausgeführt.

Daher wird für eine Controllerzustandfolge {7S3.c20, 7S4, 7S3.c20, . . .} durch den Vergleicher C M P2 die Operati­ onsfolge {limit = black, limit = 0, limit = black, . . .} aus­ geführt, was zu unnötigen Schaltaktivitäten führt.

Die vorstehend erwähnte Aktivität kann unter Verwendung der erfindungsgemäßen Techniken durch Umetikettieren des Un­ terzustands 7S3.c20 auf limit = 0 und des Unterzustands 7S3.c20 auf limit = black eliminiert werden. Entsprechend muß das Steuersignal Sel(7) in Sel(7) = x3.c20 + x4 umspezifi­ ziert werden, wobei c20 das Ausgangssignal eines anderen Vergleichers C M P1 ist, der die (=)-Operation im Zustand S3 von Fig. 7(b) ausführt. Diese Umspezifizierung führt jedoch zu einer wesentlichen Störimpulserzeugung im Steuersignal Sel(7), wie nachstehend dargestellt wird.

Es werden das umspezifizierte Steuersignal Sel(7) und ein Paar aufeinanderfolgende Taktzyklen in der Operation der Schaltung betrachtet, während denen der Controller einen Übergang vom Zustand 7S4 zum Unterzustand 7S3.c20 ausführt. Die Logik, die das umspezifizierte Steuersignal Sel(7) er­ zeugt, ist in Fig. 7(c) dargestellt. Die Übergänge in ver­ schiedenen Signalen in der Logik, die Sel(7) erzeugt, sind ebenfalls in der Fig. 7 dargestellt.

Damit der Übergang von 7S4 nach 7c3.c20 auftritt, soll­ te das Ausgangssignal des Vergleichers C M P1 im Zustand 7S4 den Wert "0" und im Zustand 7S3 den Wert "1" aufweisen, was in c20 (dem Ausgangssignal des Vergleichers C M P1) zu einem ansteigenden Übergang führt. Ein ansteigender Übergang in x3 und ein abfallender Übergang in x4 sind ebenfalls vorhanden. Weil der ansteigende Übergang in c20, das das Ausgangssignal eines Vergleichers ist, später eintrifft als die Übergänge in x3 und x4, die den decodierten Controllerzustand darstel­ len, tritt im Signal Sel(7) ein vorübergehender abfallender Übergang (Störimpuls) auf, bevor es wieder ansteigt.

Daher werden, obwohl durch die Umspezifizierung von Sel(7) unnötige Aktivitäten im Vergleicher C M P2 anschei­ nend reduziert werden, im umspezifizierten Steuersignal tat­ sächlich Störimpulse erzeugt, wodurch jegliche erreichten Leistungseinsparungen möglicherweise kompensiert werden. Der erfindungsgemäße Controller-Umspezifizierungsalgorithmus führt eine Prüfung hinsichtlich der Erzeugung von Störimpul­ sen in den umspezifizierten Steuersignalen in jedem umeti­ kettierten Zustand bzw. Unterzustand aus unter Verwendung der RTL-Schaltaktivität und der in A. Raghunathan, S. Dey und N. K. Jha, "Register-Transfer Level Estimation Techniques for Switching Activity and Power Consumption", Proc. Int. Conf. Computer-Aided Design, Seiten 158-165, Nov. 1996, durch die Störaktivitäten sowohl in Datenpfad- als auch in Steuersignalen bestimmt werden können.

Für Zustände/Unterzustände, in denen Störimpulse er­ zeugt werden, wird die Umetikettierung rückgängig gemacht, und gegebenenfalls wird eine alternative Etikettierung in Betracht gezogen, wie nachstehend beschrieben wird. Im vor­ stehend erwähnten Strichcodebeispiel wird die Umetikettie­ rung vor 7S3.c20 auf limit = 0 rückgängig gemacht, und das ursprüngliche Etikett limit = black wird wiederhergestellt.

IV E.2 Störimpulseffekte im transitiven Fan-Out der umspezifizierten Steuersignale

Die Vermeidung einer lokalen Erhöhung der Störaktivi­ tät, d. h. in umspezifizierten Steuersignalen, ist nicht aus­ reichend, um zu gewährleisten, daß durch Umspezifizieren ei­ nes Steuersignals Leistungseinsparungen erhalten werden. Das Umspezifizieren eines Steuersignals kann zu einer Erhöhung der Störimpulsaktivität in Daten- oder Steuersignalen im transitiven Fan-Out der unmittelbar betroffenen Unterschal­ tung führen.

Als Beispiel wird die in Fig. 8(a) dargestellte RTL- Teilschaltung betrachtet, die aus einem (=)-Vergleicher be­ steht, der einer ALU-Einheit Signale zuführt. Die dem Ver­ gleicher zugeführten Steuersignale wurden erfindungsgemäß umspezifiziert, um unnötige Aktivitäten im Vergleicher selbst zu reduzieren. Ein Teil des ursprünglichen und umeti­ kettierten Aktivitätsgraphen für den Vergleicher ist in Fig. 8(b) dargestellt.

Als Ergebnis der Umspezifizierung hat sich gezeigt, daß die Störimpulsaktivität eines Steuersignals contr[3], das den Multiplexern an den Eingängen der ALU-Einheit zugeführt wird, wesentlich zunimmt, was zu einem wesentlichen störim­ pulsinduzierten Leistungsverbrauch in der ALU-Einheit führt. Daher ist eine Identifizierung und Vermeidung solcher Situa­ tionen wesentlich, um maximale Leistungseinsparungen durch die Controller-Umspezifizierung zu erhalten.

Die Erzeugung von Störimpulsen im Steuersignal con­ trol[3] kann folgendermaßen erläutert werden. Die Datensta­ tistiken des Vergleicherausgangssignals (c11) vor und nach der Umspezifizierung sind in der in Fig. 8(b) dargestellten Tabelle dargestellt. Beispielsweise nimmt c11 in beiden Zu­ ständen 8S2 und 8S3 ursprünglich zehnmal und nach der Umspe­ zifizierung zweimal den Wert 0 an. Die Umspezifizierung be­ einflußt die Nullverzögerung-Signalstatistiken des Verglei­ cherausgangssignals. Die Gesamtschaltaktivität (Anzahl von 0 → 1- und 1 → 0-Übergängen) im Vergleicherausgangssignal nimmt aufgrund der Umspezifizierung ab. Die Anzahl von 1 → 0- Übergängen alleine im Signal c11, wenn der Controller einen Zustandsübergang von 8S2 nach 8S3 ausführt, nimmt jedoch we­ sentlich zu. Dies führt zu Störimpulsaktivitäten im Aus­ gangssignal des UND-Gatters, das das Signal contr[3] er­ zeugt, wie in Fig. 8(c) dargestellt.

IV E.3 Einfluß der Umspezifizierung eines Steuersignals auf die Umspezifizierung anderer Steuersignale im tran­ sitiven Fan-Out

Im Beispiel von Fig. 8 wurde vorausgesetzt, daß der Logikausdruck für das Steuersignal contr[3] bekannt ist, während das dem (=)-Vergleicher zugeführte Steuersignal um­ spezifiziert wird. Weil die verschiedenen RTL-Schaltungs­ komponenten sequentiell besucht werden, sind die Logikaus­ drücke einiger Steuersignale im transitiven Fan-Out der SUP- Schaltungen möglicherweise nicht bekannt, weil die entspre­ chenden RTL-Komponenten bisher noch nicht für das Powermana­ gement besucht wurden.

In diesen Situationen ist es, weil die Steuersignalaus­ drücke nicht bekannt sind, schwierig, die globalen Effekte der Umspezifizierung auf die Störimpulsaktivität vorherzusa­ gen. Es ist wünschenswert, daß eine solche Situation im ma­ ximal möglichen Umfang vermieden wird. Daher wird im erfin­ dungsgemäßen Controller-Umspezifizierungsverfahren versucht, alle Steuersignale im transitiven Fan-Out eines Vergleichers umzuspezifizieren, bevor die dem Vergleicher selbst zuge­ führten Steuersignale umspezifiziert werden. Wenn eine Um­ spezifizierung auf die vorstehend beschriebene Weise möglich ist, ist auch eine Voraussage der (globalen) Effekte der Um­ spezifizierung des Aktivitätsgraphen des Vergleichers auf die Störimpulsaktivität aller vom Ausgangssignal des Ver­ gleichers abhängigen Steuersignale möglich.

IV E.4 Umspezifizierung und Störimpulsausbreitung oder -übertragung von Datensignalen

Der Nettoeffekt der Controller-Umspezifizierung besteht darin, die verschiedenen Multiplexerbäume im Datenpfad umzu­ konfigurieren, um ihre Dateneingangssignale so auszuwählen, daß die Schaltaktivität in verschiedenen Datenpfadsignalen, und damit der Leistungsverbrauch, minimiert wird.

Durch das erfindungsgemäße Umspezifizierungsverfahren wird das am besten geeignete Etikett für jeden inaktiven Vertex im Aktivitätsgraphen ausgewählt, so daß die erwartete oder mittlere Nullverzögerung-Schaltaktivität in den Ein­ gangssignalen der SUP-Schaltung minimiert wird. Dies kann jedoch nicht auf eine Reduzierung der tatsächlichen Schalt­ aktivität in der SUP-Schaltung übertragen werden, wenn eini­ ge ihnen zugeführte Datensignale störimpulsbelastet sind.

Als Beispiel wird ein Teil der in Fig. 9(a) dargestell­ ten PixelGen-RTL-Schaltung betrachtet, die aus einem Multi­ plexerbaum besteht, der einem Register Signale zuführt. Ei­ nes der Eingangssignale des Multiplexerbaums, c56, ist das Ausgangssignal einer ALU-Einheit und störimpulsbelastet. Es wird vorausgesetzt, daß es das Ziel ist, das Steuersignal Sel(45) umzuspezifizieren, um die Schaltaktivität im Signal M45 zu minimieren. Fig. 9(b) zeigt einen Teil des Aktivi­ tätsgraphen für das Signal M45. Die in Fig. 9(b) dargestell­ te Aktivitätsgraphetikettierung wurde basierend auf erfin­ dungsgemäßen Umetikettierungstechniken erhalten, ohne daß die Tatsache berücksichtigt wurde, daß das Signal c56 stör­ impulsbelastet ist. Die Figur zeigt außerdem den erhaltenen Steuerausdruck und die akkumulierten Schaltaktivitäten aller Bits des Signals M45, die störimpulsbelastet bzw. störim­ pulsfrei sind. Störimpulse treten in einem wesentlichen Teil der Aktivitäten im Signal M45 auf.

Durch weitere Analyse kann gezeigt werden, daß der größte Teils der Störaktivitäten im Signal M45 durch Störim­ pulsausbreitung oder -übertragung vom Signal c56 verursacht wird. Weil die Störimpulsaktivität vom Signal c56 zum Signal M45 übertragen wird, wenn Sel(45) den Wert "0" annimmt, wer­ den die Ergebnisse durch das folgende Experiment vollständig identifiziert.

Die PixelGen-RTL-Schaltung wird implementiert, und die Störimpulsaktivität im Signal c56 wird in jedem Unterzustand getrennt gemessen. Unter Verwendung der vorstehenden Infor­ mationen wird eine Umetikettierung des Aktivitätsgraphen des Signals M45 ausgeführt, während versucht wird, die Wahl des Etiketts c56 in den Unterzuständen zu vermeiden, von denen bekannt ist, daß das ALU-Ausgangssignal störimpulsbelastet ist.

Der erhaltene etikettierte Aktivitätsgraph ist in Fig. 9(c) zusammen mit dem entsprechenden Logikausdruck für Sel(45) und den Aktivitätsstatistiken für M45 dargestellt. Obwohl die Nullverzögerung-Schaltaktivität in M45 leicht er­ höht ist, ist die Gesamtaktivität im wesentlichen aufgrund einer Reduzierung der Störimpulsübertragung von c56 in die verschiedenen Unterzustände, die den Zustand S4 bilden, in M45 erheblich reduziert.

IV F. Wirkung der Controller-Umspezifizierung auf das Leistungsverhalten bzw. die Funktionsweise

In diesem Abschnitt wird gezeigt, daß, wenn den inakti­ ven Unterzuständen Etiketten zugewiesen werden, eine Zunahme der Verzögerungszeit der durch ein Powermanagement gesteuer­ ten Schaltung erhalten werden kann. Von C. Y. Huang und W. H. Wolf, "Performance-Driven Synthesis in Controller-Datapath Systems", IEEE Trans. VLSI Systems, Bd. 2, Seiten 68-80, März 1994 und Bhattacharya, S. Dey und F. Brglez, "Clock Pe­ riod Optimization During Resource Sharing and Assignment", Proc. Design Automation Conf., Seiten 195-200, Juni 1994, wurde gezeigt, daß, wenn zwei Operationen op₁ und op₂, die in einem Zustand zwei wechselseitig ausgeschlossenen Pfaden zu­ geordnet sind, gemeinsam die gleiche Funktionseinheit ver­ wenden, der Wert der Bedingung C_1ca, der der kleinste gemein­ same Ahne oder Vorfahr der beiden Operationen ist (die erste den beiden Datenpfaden gemeinsame Bedingung), erforderlich ist, um zu entscheiden, welche Operation in einem vorgegebe­ nen Taktzyklus bezüglich der Funktionseinheit ausgeführt wird.

Daher wird vom Vergleicher, der die Operation c_1ca aus­ führt, eine Verkettung zur Funktionseinheit eingeführt, die die Operationen op₁ und op₂ ausführt. Ähnlicherweise wird, wenn zwei inaktiven Unterzuständen Si1 und Si2 innerhalb des Zustands Si bestimmte Etiketten Li1 und Li2 zugeordnet sind, die Entscheidung darüber, ob die betrachtete Datenpfadkompo­ nente die Berechnung bezüglich Li1 oder L2 ausführen wird, vom kleinsten gemeinsamen Ahnen oder Vorfahr von Si1 und Si2 abhängen.

Daher werden die Ausdrücke für die umspezifizierten Steuersignale das Ausgangssignal des Vergleichers enthalten, der die Bedingung ausführt, was zu einer Verkettung vom Ver­ gleicher zur betrachteten Datenpfadkomponente führt. Der da­ durch in der RTL-Schaltung gebildete lange Pfad kann zu ei­ ner durch die Controller-Umspezifizierung verursachten Zu­ nahme der Schaltungsverzögerung führen.

Es werden erneut der Teil der Dealer-RTL-Schaltung und der Aktivitätsgraph für die in Fig. 5 dargestellte ALU- Einheit betrachtet. Zur einfacheren Darstellung wird eine vereinfachte Version des Aktivitätsgraphen verwendet, die in Fig. 10(a) dargestellt ist, wobei die drei Unterzustände, die dem Zustand 10S5 zugeordnet sind, zu einer Gruppe zusam­ mengefaßt sind und die entsprechenden Unterzustandübergänge in Übergänge zu/von 10S5 gruppiert wurden. Der schemätische Steuerablauf im Zustand 10S4, der die Bedingungspfade an­ zeigt, denen die Unterzustände zugeordnet sind, ist eben­ falls in gestrichelten Linien dargestellt.

Wenn die beiden inaktiven Unterzustände 10S5.c1.c2 und 10S5.c1.c2 unterschiedlich etikettiert sind, z. B. durch Card + 1 und Decksize-Seed, ist, um eine Auswahl zwischen den beiden Operanden zu treffen, das Ergebnis der im Zustand S5 gezeigten Bedingung (<) erforderlich. Daher werden umspezi­ fizierte Steuersignale, z. B. Sel(10) (vergl. Fig. 5(b)), von dem entsprechenden (<)-Vergleicher abhängen, wodurch ein Pfad in der RTL-Schaltung erzeugt wird, der aus dem (<)- Vergleicher, der Logik, die Sel(10) erzeugt, dem Multiple­ xernetz, das der ALU-Einheit Signale zuführt, und der ALU- Einheit selbst besteht. Eine der Einschränkungen während der Erzeugung des Ablaufs von Fig. 5(a) war, daß eine sol­ che Verkettung vermieden wird, weil dadurch die Schaltungs­ verzögerung (Taktperiode) wesentlich erhöht wird.

Obwohl die Einführung langer Datenpfade durch die Con­ troller-Umspezifizierung unerwünscht ist, falls sie zu einer Störung oder Beeinträchtigung der vorgesehenen Schaltungs­ taktperiode führen (oder zu einer Verzögerungseinschrän­ kung), kann die in einigen der Steuersignale in unkritischen Pfaden verfügbare Toleranz zum unterschiedlichen Etikettie­ ren von Unterzuständen ausgenutzt werden. Für die Unterzu­ stände in jedem Zustand des Aktivitätsgraphen muß erfaßt werden, ob das unterschiedliche Etikettieren der Unterzu­ stände zu einer negativen Toleranz in jedem der Steuersigna­ le führt, die als Ergebnis des Etikettierens umetikettiert werden. Die Toleranz für jedes Steuersignal wird unter Ver­ wendung eines bestimmten Verzögerungsgrenzwertes in primären Ausgangssignalen und Flipflop-Eingangssignalen berechnet. Beispielsweise würde im vorstehenden Beispiel das unter­ schiedlich Etikettieren der Unterzustände 10S5.c1.c2 und 10S5.c1.c2 zur Verkettung des (<)-Vergleichers mit der ALU- Einheit führen, wodurch im Steuersignal Sel(10) eine negati­ ve Toleranz erzeugt würde. Um zu gewährleisten, daß solche Unterzustände durch das Aktivitätsgraph- Umetikettierungsverfahren nicht unterschiedlich etikettiert werden, werden die Unterzustände im Aktivitätsgraphen in ei­ nem einzigen Vertex vereinigt. Dadurch wird gewährleistet, daß der Schaltungsverzögerungsgrenzwert aufgrund des unter­ schiedlichen Etikettierens der beiden Unterzustände nicht beeinträchtigt wird. Beispielsweise werden die beiden Unter­ zustände 10S5.c1.c2 und 10S5.c1.c2 zu einem einzigen Unterzustand 10S5.c1 vereinigt, wie in Fig. 10(b) dargestellt.

Durch eine Vorverarbeitung, die ausgeführt wird, bevor versucht wird, den Aktivitätsgraphen einer Datenpfadkompo­ nente umzuetikettieren, werden die Unterzustände jedes Zu­ stands durch Bestimmen der Verzögerung untersucht, die sich durch das unterschiedliche Etikettieren der Unterzustände ergibt. Dies wird erreicht durch Verwendung des High-Level- Verzögerungsbestimmungswerkzeugs FEST (S. Bhattacharya, S. Dey und F. Brglez, "Provably correct high-level timing ana­ lysis without path sensitization", Proc. Int. Conf. Compu­ ter-Aided Design, Seiten 736-742, Nov. 1994). Wenn das Eti­ kettieren zu einer negativen Toleranz in den Steuersignalen führt, werden die Unterzustände vereinigt. Im tatsächlichen Aktivitätsgraphen sind für jeden Übergang, der Unterzustände beinhaltet, und nicht nur für Übergänge, die Zustände bein­ halten, Ausführungshäufigkeiten oder Wahrscheinlichkeiten und Aktivitätsmatrizen erforderlich. Übergänge zwischen Un­ terzuständen wurden in den Aktivitätsgraphen von Fig. 10(a) und 10(b) zur vereinfachenden Darstellung nicht explizit an­ gezeigt. Fig. 10(c) zeigt den tatsächlichen Aktivitätsgra­ phen für die ALU-Einheit nach dem Vereinigen von Unterzu­ ständen, wobei der Graph explizit Arcs für Übergänge zwi­ schen Unterzuständen aufweist und ihre Ausführungszählwerte dargestellt sind.

IV G. Durch Controller-Umspezifizierung erhaltene feh­ lerhafte kombinatorische Schleifen

Obwohl bei einer herkömmlichen Interpretation kombina­ torischer Schaltungen vorausgesetzt wird, daß solche Schal­ tungen eine azyklische Topologie aufweisen, ist bekannt, daß auch Schaltungen mit zyklischer Struktur kombinatorisch sein können. Vergl. W. H. Kautz, "The Necessity of Closed Loops in Minimal Combinational Circuits", IEEE Trans. Computers, Sei­ ten 162-164, Feb. 1970 und S. Malik, "Analysis of cyclic combinational circuits", IEEE Trans. Computer-Aided Design, Bd. 13, Seiten 950-956, Juli 1994. Im Zusammenhang mit der High-Level-Synthese wurde in L. Stok, "False loops through resource sharing", Proc. Int. Conf. Computer-Aided Design, Seiten 345-348, Nov. 1992 gezeigt, daß ein ungeordnetes Re­ source-Sharing-Verfahren zur Ausbildung fehlerhafter kombi­ natorischer Schleifen in der synthetisierten RTL-Schaltung führen kann.

Resource-Sharing-Techniken zum Vermeiden der Ausbildung solcher kombinatorischer Schleifen wurden auch durch L. Stok, "False loops through resource sharing", Proc. Int. Conf. Computer-Aided Design, Seiten 345-348, Nov. 1992 be­ schrieben. Dieser Abschnitt demonstriert, daß eine Control­ ler-Umspezifizierung bei Vorhandensein wechselseitig aus­ schließender Bedingungspfade in jedem Controllerzustand auch zur Ausbildung 33821 00070 552 001000280000000200012000285913371000040 0002019925411 00004 33702fehlerhafter kombinatorischer Zyklen in der RTL-Schaltung führen kann.

Es wird die in Fig. 11(a) dargestellte Programmbe­ schreibung (RTL-Funktion) betrachtet, die unter Verwendung eines Addierglieds und eines (<)-Vergleichers durch die in Fig. 11(b) dargestellte RTL-Schaltung implementiert wird. Es existiert eine Datenverkettung vom Ausgang des Addiergliedes zum Eingang des (<)-Vergleichers. Anfangs hängen die Logik­ ausdrücke für die Auswahleingänge der verschiedenen Multi­ plexer, die dem Addierglied Signale zuführen, nicht vom Ver­ gleicherausgangssignal c2 ab. Daher existiert die durch die gestrichelte Linie dargestellte Verbindung in der ursprüng­ lichen RTL-Schaltung nicht.

Nachstehend wird die Anwendung der Controller- Umspezifizierungstechnik zum Minimieren unnötiger Aktivitä­ ten im Addierglied betrachtet. Fig. 11(c) zeigt den Teil- Aktivitätsgraphen für das Addierglied zusammen mit der Eti­ kettierung, durch die die Aktivitäten an den Eingängen des Addiergliedes minimiert werden. Die den Unterzuständen 11S1.c2 und 11S1.c2 zugeordneten Etiketten sind verschieden.

Aus frühen Diskussionen ist klar, daß durch verschiede­ nes Etikettieren der verschiedenen Unterzustände, die einen Zustand bilden, eine Abhängigkeit von den Ausgangssignalen eines oder mehrerer Vergleicher im Datenpfad zur Unterschal­ tung eingeführt werden kann, deren Aktivitätsgraph gerade umetikettiert wird. Im Beispiel von Fig. 11 werden die Steuerausdrücke für die Auswahleingänge der Multiplexerbäu­ me, die dem Addierglied Signale zuführen, nun von c2 abhän­ gen, wodurch eine kombinatorische Abhängigkeit eingeführt wird, wie durch die gestrichelte Linie in Fig. 11(b) darge­ stellt, und dadurch ein kombinatorischer Zyklus in der RTL- Schaltung. Der vorstehend erwähnte kombinatorische Zyklus ist fehlerhaft, weil seine verschiedenen Segmente niemals gleichzeitig, d. h. in einem beliebigen vorgegebenen Zyklus, aktiviert werden, entweder verwendet der Vergleicher das Ausgangssignal des Addiergliedes, oder das Addierglied ver­ wendet das Ausgangssignal des Vergleichers, beide Fälle tre­ ten jedoch nicht gleichzeitig auf.

Obwohl Forscher Techniken zum Handhaben zyklisch kombi­ natorischer Schaltungen während einer Logiksynthese vorge­ schlagen haben, sind solche Fähigkeiten oder Funktionen in gegenwärtigen kommerziellen und betriebsinternen Fertigungs­ werkzeugen nicht typisch oder Standard. Daher kann es häufig erforderlich sein, die Bildung kombinatorischer Zyklen in der RTL-Schaltung zu vermeiden.

Gemäß einem Aspekt der vorliegenden Erfindung wird das Controller-Umspezifizierungsverfahren verbessert, um zu ge­ währleisten, daß durch die Controller-Umspezifizierung auf­ grund der Vereinigung von Unterzuständen im Aktivitätsgra­ phen keine fehlerhaften kombinatorischen Zyklen eingeführt werden.

Für jedes Paar von Unterzuständen im Aktivitätsgraphen, von denen einer oder beide inaktiv sind, werden die zusätz­ lichen Abhängigkeiten von Vergleicherausgangssignalen be­ stimmt, die eingeführt werden, wenn zwei Unterzustände ver­ schieden etikettiert würden. Wenn eine solche Abhängigkeit existiert, wird eine lineare Zeitdurchlaufoperation der RTL- Schaltung ausgeführt um zu bestimmen, ob durch die zusätzli­ che Abhängigkeit ein kombinatorischer Zyklus eingeführt wur­ de. Wenn durch die Zeitdurchlaufoperation ein Zyklus erfaßt wird, wird das Paar von Unterzuständen in einem einzigen Vertex im Aktivitätsgraphen vereinigt. Durch eine solche Vereinigung wird effektiv gewährleistet, daß beide Unterzu­ stände identisch etikettiert werden, wodurch die Einführung eines Zyklus, durch den Abhängigkeiten erzeugt werden, ver­ mieden wird. Gemäß dem in Fig. 11 dargestellten Beispiel ist deutlich, daß durch verschiedenes Umetikettieren von Un­ terzuständen 11S1.c2 und 11S1.c2 ein kombinatorischer Zuyklus erzeugt wird. Daher werden die Unterzustände 11S1.c2 und 11S1.c2 in einem einzigen Vertex 11S1 vereinigt, wodurch ver­ anlaßt wird, daß das Etikett i+1 zwangsweise für den Unter­ zustand 11S1.c2 verwendet wird.

IV H. Powermanagementalgorithmus

Dieser Abschnitt beschreibt einen Algorithmus zum Aus­ führen eines Powermanagements durch Controller-Umspezi­ fizierungstechniken. Zunächst wird die für den Rest dieses Abschnitts verwendete Terminologie eingeführt.

Eine RTL-Schaltung besteht aus einer Verbindung von RTL-Schaltungsknoten, die RTL-Einheiten (Funktionseinheiten, Register oder Vergleicher) sein können, und Verbindungsein­ heiten, d. h. Multiplexernetzen. Beliebige Funktionseinhei­ ten, deren Funktionen nicht ausschließlich auf arithmetische Operationen beschränkt sind, werden unterstützt.

Ein RTL-Block bezeichnet eine RTL-Einheit, die zusammen mit dem (den) Multiplexernetz(en) gruppiert sind, das (die) ihm Signale zuführt (zuführen). Ein RTL-Block kann Steuer­ eingangssignale (z. B. Auswahlsignale für Multiplexer, Aus­ wahlfunktionssignale für ALU-Einheiten) sowie Dateneingangs­ signale aufweisen.

Zwischen Steuereingangssignalen und Dateneingangssigna­ len muß unterschieden werden, weil es das Ziel ist, die Steuerlogik umzuspezifizieren, die verschiedenen RTL-Blöcken die Steuereingangssignale zuführt. Allgemein können Steuer­ signale vom aktuellen Zustand des Controllers sowie von Aus­ gangssignalen anderer RTL-Blöcke abhängen (z. B. von Aus­ gangssignalen von Vergleichern).

Es wird vorausgesetzt, daß eine Daten (Steuerungs) -abhängigkeit zwischen zwei RTL-Blöcken B₁ und B₂ existiert, wenn ein Ausgangssignal von B₁ einem Daten (Steuer)-eingang von B₂ zugeführt wird.

Ein Datenabhängigkeitsgraph (Steuerungsabhängigkeits­ graph) ist ein gerichteter azyklischer Graph, in dem Ver­ tices RTL-Blöcke und Ränder Daten (Steuerungs)-abhängig­ keiten darstellen. Die Daten- und Steuerungsabhängigkeits­ graphen sind azyklisch, obwohl der RTL-Schaltungsgraph zy­ klisch sein kann, weil von Datenpfadregistern zugeordneten RTL-Blöcken abgehende Arcs nicht eingeschlossen sind.

Wenn ein kombinatorischer Pfad vom Ausgang des RTL- Blocks B_i zu einem Dateneingang eines Blocks B_j existiert, ist es wünschenswert, Steuersignale für den Block B_i vor denjenigen für den Block B_j umzuspezifizieren. Dies ist der Fall, weil durch Umspezifizieren der Steuersignale für den Block B_i die an seinen Ausgängen auftretenden Werte und da­ mit die Einträge in den Aktivitätsmatrizen der Aktivitäts­ graphen für Block B_j beeinflußt werden.

Wenn dagegen ein Pfad vom Ausgang eines Blocks B_i zu einem Steuereingang des Blocks B_j existiert, ist es wün­ schenswert, zunächst Block B_j zu verarbeiten, so daß die endgültigen Logikausdrücke für die Steuersignale für B_j ver­ fügbar sind, während die Powermanagementtechnik auf Block B_i angewendet wird, wie vorstehend beschrieben wurde.

Ein Aktivitätsgraph ist ein vertex-etikettierter, arc- gewichteter gerichteter Graph AG = (V, A). Die Vertices des Aktivitätsgraphen stellen die Zustände und Unterzustände des Controllers dar.

Jedem Arc v_i → v_j ist (i) ein Gewicht W_vi→_vj, das die Ausführungshäufigkeit oder die Wahrscheinlichkeit des ent­ sprechenden Zustand- oder Unterzustandübergangs darstellt, und (ii) eine Aktivitätsmatrix AM_vi→_vj zugeordnet, in der der dem Arc zugeordnete Aufwand für verschiedene Kombinationen von Etiketten gespeichert sind, die v_i und v_j zugeordnet wer­ den können.

Ein Satz inaktiver Vertices I ⊃ V ist so gegeben, daß durch Ändern des Etiketts eines beliebigen der Vertices in I die Funktionalität der Struktur nicht beeinflußt wird. Um eine solche Umetikettierung auszuführen, muß ein Maß für den Aufwand der Zuordnung jedes möglichen Etiketts zu einem in­ aktiven Vertex im Aktivitätsgraphen zugeordnet werden. Für Experimente wurden die Einträge in den Aktivitätsmatrizen durch eine RTL-Zyklus-basierte Simulation erhalten.

Das Steuersignalumspezifizierungsproblem ist einem Pro­ blem einer Vertex-Etikettierung mit minimalem Aufwand (MCVLP) bezüglich des Aktivitätsgraphen logisch äquivalent. Ziel ist es, jedem Vertex im inaktiven Satz I exakt nur ein Etikett aus einem Satz von k Etiketten L = L₁, . . ., L_k zuzu­ ordnen. Die Bestimmung eines Maßes für den Aufwand für die Zuordnung wird später beschrieben. Es kann gezeigt werden, daß MCVLP NP-hart ist. Daher wird eine Heuristik verwendet, um dieses Problem zu lösen, wie in diesem Abschnitt später beschrieben wird.

Eine bevorzugte Ausführungform eines erfindungsgemäßen Powermanagementalgorithmus ist im in Fig. 12 dargestellten Pseudocode beschrieben. Zunächst wird der Datenpfad in seine RTL-Teilblöcke unterteilt (Prozedur IDENTIFY_RTL BLOCKS). Dann wird der Daten (Steuerungs)-abhängigkeitsgraph durch Aufruf einer Prozedur CREATE_DATA_DEPENDENCE_GRAPH erzeugt. Die Daten- und Steuerungsabhängigkeitsgraphen werden verwen­ det, um die Reihenfolge herzuleiten, in der die RTL-Blöcke im Datenpfad besucht werden, um ihre Steuersignale umzuspe­ zifizieren.

Bei jedem RTL-Block versucht der Algorithmus zunächst den Aktivitätsgraphen seiner RTL-Einheit umzuetikettieren. Dies wird durch Aufrufen einer Prozedur RESPEC_CON- TROL_SIGNALS erreicht, die die tatsächliche Steuersignalum­ spezifizierung für eine vorgegebene SUP-Schaltung ausführt. Dann wird diese Prozedur für jedes Multiplexernetz im RTL- Block einmal ausgeführt, dem in jedem Fall als Parameter die Wurzel oder der Ursprung des geeigneten Multiplexernetzes zugeführt wird.

Wenn ihr ein Multiplexer als Parameter zugeführt wird, durchläuft die Prozedur RESPEC_CONTROL_SIGNALS das Multiple­ xernetz rekursiv, und versucht, in jedem Schritt die Aktivi­ tät am Ausgang des aktuellen Multiplexers zu minimieren.

Nachstehend wird die Prozedur RESPEC_CONTROL_SIGNALS beschrieben. Zunächst ruft sie eine Prozedur CREATE_ACTIVITY_GRAPH auf, um einen Aktivitätsgraphen für die betrachtete RTL-Einheit oder das betrachtete Multiple­ xerausgangssignal zu erzeugen.

Eine Prozedur MERGE_SUBSTATES wird verwendet, um zu ge­ währleisten, daß durch keine Umetikettierung der inaktiven Aktivätätsgraph-Vertices ein langer Pfad eingeführt werden kann, der zu einer erhöhten Schaltungsverzögerung oder zur Ausbildung eines fehlerhaften kombinatorischen Zyklus führt, wie in vorstehenden Abschnitten beschrieben wurde. Die Schaltungsverzögerung kann aufgrund weniger zusätzlicher Ebenen von Torschaltungen in der umspezifizierten Steuerlo­ gik jedoch trotzdem zunehmen. In der Praxis hat sich jedoch gezeigt, daß solche Effekte, wenn überhaupt, nur zu sehr ge­ ringen zusätzlichen Verzögerungen führen, wie durch nachste­ hend dargestellte experimentelle Ergebnisse demonstriert wird.

Eine einfache heuristische Prozedur MIN_COST_LABELING wird verwendet, um das MCVLP-Problem bezüglich des Aktivi­ tätsgraphen zu lösen. Die Prozedur führt eine Iteration über die nicht-etikettierten Vertices des Aktivitätsgraphen aus, wobei die in jedem Schritt abgetasteten nicht-etikettierten Vertices etikettiert werden, so daß der zusätzliche Etiket­ tieraufwand minimiert wird.

Die Reihenfolge, in der nicht-etikettierte Vertices während der Prozedur besucht werden, hat einen wesentlichen Einfluß auf die endgültige Etikettierung. Ein nicht- etikettierter Vertex V* wird als nächster zu besuchender Vertex ausgewählt, so daß die durch die folgende Gleichung gegebene Größe Labeled_Vertex_Arcs(V*) maximal wird.

Das hinter diesem Kriterium stehende Grundprinzip ist, daß die Kenntnis der benachbarten Vertices zugeordneten Eti­ ketten wesentlich ist, um den Aufwand für die Zuweisung ei­ nes Etiketts zum abgetasteten Vertex exakt zu berechnen. Nachdem der als nächstes zu etikettierende Vertex V* abgeta­ stet wurde, wird eine geeignete Näherung verwendet, um ihm ein Etikett zuzuweisen. Ein Etikett L* ∈ L wird so ausge­ wählt, daß die durch die nachstehende Gleichung gegebene Größe Incr_Labeling_Cost(V*,L*) minimal wird.

Wie vorstehend dargestellt wurde, kann das Umspezifi­ zieren eines Steuersignals dazu führen, daß in einem der um­ spezifizierten Steuersignale oder in anderen Daten- und/oder Steuersignalen Störimpulse erzeugt werden. Um die Effekte der Störimpulse in Dateneingangssignalen für die Multiple­ xernetze zu berücksichtigen, identifiziert die Prozedur für jeden inaktiven Unterzustand im Aktivitätsgraphen die Stör­ impulsaktivität in jedem Dateneingangssignal für das Multi­ plexernetzwerk, das der SUP-Schaltung Signale zuführt.

Für diesen Zweck werden die durch A. Raghunathan, S. Dey und N. K. Jha in "Register-Transfer Level Estimation Techniques for Switching Activity and Power Consumption", Proc. Int. Conf. Computer-Aided Design, Seiten 158-165, Nov. 1996 dargestellten RTL-Schaltaktivitätsbestimmungstechniken verwendet.

Alle Dateneingangssignale, deren Störimpulsaktivität größer ist als ein durch den Benutzer spezifizierter Schwel­ lenwert, werden als störimpulsbelastete Signale identifi­ ziert. Durch den Umspezifizierungsalgorithmus der bevorzug­ ten Ausführungsform wird versucht, die Ausbreitung oder Übertragung der Störimpulsaktivität von Datensignalen fol­ gendermaßen zu eliminieren bzw. zu minimieren.

Während ein Etikett für einen inaktiven Zustand ausge­ wählt wird, versucht die Prozedur zunächst, ein Etikett aus­ zuwählen, das keinem störimpulsbelasteten Dateneingangs­ signal zugeordnet ist. Wenn ein solches Etikett nicht exi­ stiert, werden die störimpulsbelasteten Dateneingangssignale in aufsteigender Reihenfolge ihrer Störimpulsaktivität in den inaktiven Unterzuständen sortiert, und ein Etikett wird in dieser Prioritätsreihenfolge ausgewählt.

Eine Prozedur SELECTIVELY_UNDO_LABELS_FOR_GLITCHING wird aufgerufen, um die Störimpulsaktivität in den umspezi­ fizierten Steuersignalen sowie in anderen Steuersignalen im transitiven Fan-Out der SUP-Schaltung zu berücksichtigen. Die Prozedur verwendet zunächst die Schaltaktivitätsbestim­ mungseinrichtung, um Störimpulsaktivitäten für die Steuer­ ausdrücke der umspezifizierten Steuersignale sowie anderer Steuersignale im transitiven Fan-Out der SUP-Schaltung zu bestimmen.

Für Steuersignale, in denen die Störimpulsaktivität we­ sentlich erhöht ist, werden Informationen darüber gesammelt, welche Unterzustände der Steuersignale störimpulsbelastet sind, und ob die Erhöhung der Störimpulsaktivität primär auf die Störimpulserzeugung in der Steuerlogik oder auf die Störimpulsausbreitung über die Steuerlogik oder auf beides zurückzuführen ist.

Eine Unterscheidung zwischen der Störimpulserzeugung in der Steuerlogik und einer Ausbreitung über die Steuerlogik ist aus folgendem Grund notwendig. Um eine Erhöhung der Störimpulsaktivität in einem Steuersignal in einem Unterzu­ stand Si1 zu vermeiden, muß im allgemeinen die Aktivitäts­ graphumetikettierung in Si1 und allen Unterzuständen mit Übergängen zu oder von Si1 rückgängig gemacht werden. Um ei­ ne Erhöhung der Störimpulsausbreitung in Si1 zu vermeiden, ist es dagegen ausreichend, die Umetikettierung nur in Si1 selbst rückgängig zu machen. Nachdem einige der Etiketten im Aktivitätsgraphen aufgehoben wurden, wird durch die Prozedur MIN_COST_LABELING eine Iteration ausgeführt, um alternative Etiketten für Unterzustände auszuwählen, deren Etiketten aufgehoben wurden.

IV I. Controller-Umspezifizierungssystem

Fig. 13 zeigt eine bevorzugte Ausführungsform eines Sy­ stems, das eine erfindungsgemäße Controller-Umspezifizierung ausführt. Es besteht aus einer Schaltungseingangseinheit 1310, einem RTL-Schaltungsstrukturanalysator 1330, einer Controller-Umstrukturierungseinheit 1320 und einer Schal­ tungsausgangseinheit 1340. Die Schaltungseingangseinheit 1310 empfängt eine sequentielle Schaltung, der RTL- Schaltungsstrukturanalysator 1330 analysiert die empfangene Schaltung für eine Controller-Umspezifizierung, und die Con­ troller-Umstrukturierungseinheit 1320 strukturiert die Schaltung unter Verwendung der Controller-Umspezifizierung durch Ändern der Steuerlogik um, um den Leistungsverbrauch zu reduzieren. Schließlich wird die umstrukturierte Schal­ tung durch die Ausgangseinheit 1340 ausgegeben.

Fig. 14 zeigt weitere Verbesserungen, wobei die Um­ strukturierungseinheit einen RTL-Einheit-Zähler 1410, einen Aktivitätsgraphgenerator 1420, eine Aktivitätsgraphumetiket­ tierungseinrichtung 1430 und einen Steuerlogikreflektor 1440 aufweist. Der RTL-Einheit-Zähler 1410 zählt RTL-Einheiten in den empfangenen Schaltungen. Der Aktivitätsgraphgenerator 1420 erzeugt einen Aktivitätsgraphen der RTL-Einheiten, und die Aktivitätsgraphumetikettiereinrichtung 1430 etikettiert den Aktivitätsgraphen um. Der Steuerlogikreflektor modifi­ ziert die Steuerlogik gemäß dem umetikettierten Aktivitäts­ graphen.

Fig. 15 zeigt eine weitere Verbesserung, wobei der RTL- Schaltungsstrukturanalysator eine RTL-Block-Identifizie­ rungseinrichtung 1510, eine Datenabhängigkeitsgraph-Extrak­ tionseinrichtung 1520, eine Steuerungsabhängigkeitsgraph- Extraktionseinrichtung 1530 und eine RTL-Block-Sortier­ einrichtung 1540 aufweist. Die RTL-Block-Identifizierungs­ einrichtung 1510 identifiziert RTL-Blöcke in der empfangenen Schaltung. Die Datenabhängigkeitsgraph-Extraktionseinrich­ tung 1520 extrahiert einen Datenabhängigkeitsgraphen der empfangenen Schaltung. Die Steuerungsabhängigkeitsgraph- Extraktionseinrichtung 1530 extrahiert einen Steuerungsab­ hängigkeitsgraphen der empfangenen Schaltung, und die RTL- Block-Sortiereinrichtung 1540 ordnet die identifizierten RTL-Blöcke unter Verwendung von Informationen vom Datenab­ hängigkeitsgraphen und vom Steuerungsabhängigkeitsgraphen.

Fig. 16 zeigt Verbesserungen, wobei die Controller- Umstrukturierungseinheit ferner eine Verzögerungsbestim­ mungseinrichtung 1660, eine Einrichtung 1670 zum Identifi­ zieren kombinatorischer Schleifen und eine Schaltaktivität­ bestimmungseinrichtung 1640 aufweist. Die Verzögerungsbe­ stimmungseinrichtung 1660 bestimmt in eine umstrukturierte Schaltung eingeführte Verzögerungen. Die Einrichtung 1670 zum Identifizieren kombinatorischer Schleifen identifiziert kombinatorische Schleifen in der umstrukturierten Schaltung, und die Schaltaktivitätbestimmungseinrichtung 1640 bestimmt alle Schaltaktivitäten in der umstrukturierten Schaltung.

IV J. Ablaufdiagramme für bevorzugte Ausführungsformen erfindungsgemäßer Verfahren

Fig. 17 zeigt ein Ablaufdiagramm zum Darstellen einer Ausführungsform eines Verfahrens zum Ändern der Steuerlogik einer sequentiellen Schaltung zum Reduzieren der Leistungs­ aufnahme bzw. des Leistungsverbrauchs. In Schritt 1710 wird eine sequentielle Schaltung eingegeben. In Schritt 1720 wird ein Aktivitätsgraph der sequentiellen Schaltung erzeugt. In Schritt 1730 werden inaktive Zustände in der sequentiellen Schaltung identifiziert. Diese inaktiven Zustände werden in Schritt 1740 umetikettiert. Nachdem die inaktiven Zustände umetikettiert wurden, wird die Steuerlogik der sequentiellen Schaltung in Schritt 1750 umstrukturiert, und in Schritt 1760 wird die umstrukturierte Schaltung ausgegeben.

Fig. 18 zeigt ein Ablaufdiagramm zum Darstellen einer Ausführungsform eines erfindungsgemäßen Verfahrens zum Modi­ fizieren eines Aktivitätsgraphen, um verschachtelte Bedin­ gungen zu berücksichtigen. In Schritt 1820 wird ein noch nicht verarbeiteter Zustand in der sequentiellen Schaltung ausgewählt. In Schritt 1830 bestimmt der Algorithmus, ob der Zustand verschachtelte Bedingungen enthält. Wenn er keine verschachtelten Bedingungen enthält, schreitet der Algorith­ mus zu Schritt 1860 fort. Wenn der ausgewählte Zustand ver­ schachtelte Bedingungen enthält, wird der Zustand in Schritt 1840 in Unterzustände geteilt. Für jeden der Unterzustände wird in Schritt 1850 ein Vertex erzeugt, und der Algorithmus schreitet zu Schritt 1860 fort. Wenn mehr Schritte zu verar­ beiten sind, kehrt der Algorithmus zu Schritt 1830 zurück und wird fortgesetzt.

Fig. 19 zeigt ein Ablaufdiagramm zum Darstellen einer Ausführungsform eines erfindungsgemäßen Verfahrens zum Modi­ fizieren eines Aktivitätsgraphen, um verschachtelte Bedin­ gungen zu berücksichtigen. Nach dem Umetikettieren von Zu­ ständen in Schritt 1740 wird durch diesen Algorithmus in Schritt 1910 ein noch nicht verarbeiteter Zustand oder Un­ terzustand ausgewählt. In Schritt 1910 wird festgestellt, ob im ausgewählten Zustand Störimpulse auftreten. Wenn keine Störimpulse auftreten, schreitet der Algorithmus zu Schritt 1940 fort. Wenn Störimpulse auftreten, wird die Umetikettie­ rung des Zustands oder Unterzustands in Schritt 1930 rück­ gängig gemacht. Wenn mehr zu verarbeitende Zustände und Un­ terzustände existieren, kehrt der Algorithmus von Schritt 1940 zurück zu Schritt 1920.

Fig. 20 zeigt ein Anlaufdiagramm zum Darstellen einer Ausführungsform eines erfindungsgemäßen Verfahrens zum Modi­ fizieren eines Aktivitätsgraphen, um eine Zunahme der Verzö­ gerung zu berücksichtigen. In Schritt 2010 wird festge­ stellt, ob die Verzögerung zunimmt. In Schritt 2020 werden die Zustände vereinigt, in denen die Verzögerungen zunehmen.

Fig. 21 zeigt ein Ablaufdiagramm zum Darstellen einer Ausführungsform eines Verfahrens zum Modifizieren eines Ak­ tivitätsgraphen, um zusätzliche Abhängigkeiten und kombina­ torische Zyklen zu berücksichtigen. In Schritt 2110 wird ein neues Paar von Unterzuständen innerhalb eines Zustands iden­ tifiziert, wobei ein Element des Paars inaktiv ist. In Schritt 2130 wird festgestellt, ob zusätzliche Abhängigkei­ ten eingeführt werden, wenn die Paare umetikettiert werden. Wenn dies nicht der Fall ist, schreitet der Algorithmus zu Schritt 2160 fort. Wenn zusätzliche Abhängigkeiten existie­ ren, wird in Schritt 2130 ein linearer Zeitdurchlauf bezüg­ lich der Schaltung durchgeführt. In Schritt 2140 wird fest­ gestellt, ob kombinatorische Zyklen eingeführt werden. Wenn kombinatorische Zyklen eingeführt werden, wird das Paar in Schritt 2150 vereinigt. Wenn keine kombinatorischen Zyklen eingeführt werden, schreitet der Algorithmus zu Schritt 2160 fort, wo er zu Schritt 2110 zurückkehrt, falls weitere Paare existieren.

Fig. 22 zeigt ein Ablaufdiagramm zum Darstellen einer bevorzugten Ausführungsform eines Powermanagementverfahrens durch Controller-Umspezifizierung. In Schritt 2210 wird ei­ ne sequentielle Schaltung eingegeben. In Schritt 2220 wird die Schaltung in RTL-Blöcke geteilt. In Schritt 2230 werden ein oder mehrere Abhängigkeitsgraphen für die Schaltung er­ zeugt. In Schritt 2240 wird die Reihenfolge des Besuchs der RTL-Blöcke erzeugt. In Schritt 2250 wird ein RTL-Block aus­ gewählt, der bisher noch nicht ausgewählt wurde. In Schritt 2260 wird jeder Multiplexerbaum ausgewählt, der dem ausge­ wählten RTL-Block Signale zuführt. In Schritt 2270 kehrt der Algorithmus zu Schritt 2250 zurück, wenn RTL-Blöcke verblei­ ben, die gemäß dem Algorithmus noch umspezifiziert werden sollen.

Fig. 23 zeigt ein Ablaufdiagramm zum Darstellen einer bevorzugten Ausführungsform eines erfindungsgemäßen Umspezi­ fizierungsverfahrens. In Schritt 2310 wird ein Aktivitäts­ graph erzeugt. In Schritt 2320 werden Unterzustände verei­ nigt. In Schritt 2330 werden störimpulsbelastete Datenein­ gangssignale identifiziert. In Schritt 2340 wird ein Etiket­ tierprozeß mit minimalem Aufwand durchgeführt. In Schritt 2350 werden störimpulsbelastete Etiketten umetikettiert. In Schritt 2360 kehrt der Algorithmus zu Schritt 2340 zurück, wenn mehr nicht-etikettierte Vertices existieren. In Schritt 2370 führt der Algorithmus diesen Umspezifizierungsalgorith­ mus rekursiv für den linken Multiplexerbaum und dann für den rechten Multiplexerbaum aus.

Fig. 24 zeigt ein Ablaufdiagramm zum Darstellen einer bevorzugten Ausführungsform eines erfindungsgemäßen Verfah­ rens zum Vereinigen von Unterzuständen. In Schritt 2410 wird ein Zustand ausgewählt, der noch nicht verarbeitet wurde. In Schritt 2420 wird ein Paar von Unterzuständen innerhalb des ausgewählten, noch nicht verarbeiteten Zustands ausgewählt. In Schritt 2430 wird festgestellt, ob das Paar von Unterzu­ ständen inaktiv ist. Wenn dies der Fall ist, schreitet der Algorithmus zu Schritt 2470 fort, von wo er zu Schritt 2420 zurückkehrt, um mehr Unterzustände zu identifizieren. Wenn das Paar von Unterzuständen nicht inaktiv ist, werden in Schritt 2440 Zyklen identifiziert. Wenn Zyklen vorhanden sind, schreitet der Algorithmus zu Schritt 2460 fort, um Un­ terzustände zu vereinigen. Wenn keine Zyklen vorhanden sind, wird in Schritt 2450 festgestellt, ob die bestimmte Verzöge­ rung größer ist als die Zyklusperiode. Wenn die Verzögerung größer ist als eine Zyklusperiode, schreitet der Algorithmus zu Schritt 2460 fort, um solche Unterzustände zu vereinigen. Schließlich kehrt der Algorithmus in den Schritten 2470 und 2480 zurück, um mehr Paare von Unterzuständen und mehr Zu­ stände zu verarbeiten.

Fig. 25 zeigt ein Ablaufdiagramm zum Darstellen eines Verfahrens zum Ausführen einer Etikettierung mit minimalem Aufwand. In Schritt 2510 wird der nächste nicht-etikettierte Vertex ausgewählt. In Schritt 2520 wird der Vertex so eti­ kettiert, daß der zusätzliche Aufwand minimiert wird. In Schritt 2530 kehrt der Algorithmus zu Schritt 2510 zurück, um weitere Vertices zu verarbeiten.

IV K. Experimentelle Ergebnisse

In diesem Abschnitt werden Ergebnisse der Anwendung ei­ ner bevorzugten Ausführungsform der erfindungsgemäßen con­ troller-basierten Powermanagementtechnik auf die folgenden RTL-Schaltungen beschrieben, die typische steuerungsablauf­ intensive Spezifikationen implementieren. Es werden ein Strichcode-Lesegerät und eine Dealer-Verarbeitung verwendet, d. h. ein Verfahren, das als Dealer für das Black-Jack- Kartenspiel dient. Vergl. S. Bhattacharya, S. Dey und F. Brglez, "Clock Period Optimization During Resource Sharing and Assignment", Proc. Design Automation Conf., Seiten 195-­ 200, Juni 1994.

GCD ist eine Implementierung des größten gemeinsamen Teilers, PixelGen ist eine Linienzeichnungsverarbeitung, die Teil eines Graphik-Controllers ist. Vergl. A. Raghunathan, S. Dey, N. K. Jha und K. Wakabayashi, "Controller Re- Specification To Minimize Switching Activity in Control­ ler/Data Path Circuits", Proc. Int. Symp. Low-Power Electro­ nics and Design, Seiten 301-306, August 1996.

X.25 ist eine vereinfachte Version des Übertragungspro­ zesses des X.25-Übertragungs- oder Kommunikationsprotokolls.

Vergl. S. Bhattacharya, S. Dey und F. Brglez, "Performance analysis and optimization of schedules for conditional and loop-intensive specifications", Proc. Design Automation Conf., Seiten 491-496, Juni 1994.

Diese Spezifikationen sind außer durch Arithmetik- und Vergleichsoperationen durch das Vorhandensein verschachtel­ ter Schleifen und Bedingungen und Feldabhängigkeiten in Ver­ haltens- oder Funktionsbeschreibungen gekennzeichnet. Die anfänglichen RTL-Schaltungen wurden durch Synthetisieren von VHDL-Funktionsbeschreibungen unter Verwendung eines bekann­ ten Verhaltens- oder Funktionssystems erhalten. Vergl. S. Bhattacharya, S. Dey und F. Brglez, "Clock Period Optimiza­ tion During Resource Sharing and Assignment", Proc. Design Automation Conf., Seiten 195-200, Juni 1994 und S. Bhat­ tacharya, 5. Dey und F. Brglez, "Performance analysis and optimization of schedules for conditional and loop-intensive specifications", Proc. Design Automation Conf., Seiten 491-­ 496, Juni 1994.

Als Ergebnis der Anwendung der dargestellten Powermana­ gementtechniken wird nur der Controller modifiziert, während der Datenpfad nicht modifiziert wird. Die anfänglichen und die controller-umspezifizierten RTL-Schaltungen wurden ähn­ lich optimiert. Vergl. CMOS6 Library Manual, NEC Electro­ nics, Inc., Dez. 1992.

Diese Netzlisten wurden verwendet, um Flächenwerte, Verzögerungen und den Leistungsverbrauch bzw. die Leistungs­ aufnahme zu messen.

Tabelle 1 zeigt die durch die vorliegende, controller­ basierte Powermanagementtechnik (COP) erhaltenen Leistungs­ einsparungen und den damit verbundenen zusätzlichen Flä­ chenbedarf und Verzögerungen. Die Bezeichnungen Original und COP beziehen sich auf RTL-Schaltungen vor und nach Anwendung der erfindungsgemäßen Powermanagementtechniken, bei denen versucht wird, ihre negativen Auswirkungen auf die Verzöge­ rung und die Störimpulsaktivität zu vermeiden. Die Spalten Leistung, Fläche, Verzögerung und Leistungsred. bezeichnen den Leistungsverbrauch (in Milliwatt), die Fläche (Zellen­ gitterzahl + Verdrahtungsflächen-Schätzwert), die Verzöge­ rung (Taktperiode in Nanosekunden) und die Spannungsreduk­ tionen nach Zuordnung zur verwendeten Technologiebibliothek. Zum Messen des Leistungsverbrauchs wurde ein auf Simulation basierendes Leistungsbestimmungswerkzeug verwendet. Die für die Simulation verwendeten Vektoren wurden folgendermaßen erhalten. Für jeden Entwurf bzw. jede Struktur wurde ein Verhaltens- oder Funktionsbewertungstest verwendet, der ty­ pische Anregungen enthielt, die basierend auf der Kenntnis der Funktionalität des Entwurfs bzw. der Struktur und der vorgesehenen Umgebung hergeleitet wurden.

Es wurde eine Anregungseinrichtung verwendet, um eine zyklusbezogene Eingangsvektorbahn zu erhalten. Der vorste­ hende Schritt ist besonders wichtig für steuerungsablaufin­ tensive Strukturen oder Entwürfe, bei denen, anders als bei datenflußintensiven Strukturen oder Entwürfen, die Anzahl von zur Berechnung erforderlichen Taktzyklen in Abhängigkeit von den Eingangswerten variiert. Die zyklusbezogene Ein­ gangsvektorbahn wurde verwendet, um die anfänglichen und die bezüglich des Leistungsverbrauchs optimierten Strukturen oder Entwürfe zu bewerten. Die Ergebnisse zeigen, daß das controller-basierte Powermanagement bei nominellen zusätzli­ chen Flächen und Verzögerungen zu wesentlichen Einsparungen im Leistungsverbrauch (bis zu 52%) für steuerungsablaufin­ tensive RTL-Strukturen oder Entwürfe führt.

Tabelle 1

Experimentelle Ergebnisse: durch controller­ basiertes Powermanagement erhaltene Leistungseinsparungen

Um die Wichtigkeit der Betrachtung der negativen Effek­ te oder Auswirkungen der Umspezifizierung auf die Verzöge­ rung und die Störimpulsaktivität aufzuzeigen, wurde eine weitere Experimentreihe durchgeführt. Die Controller der RTL-Schaltungen wurden ohne Berücksichtigung der Nebeneffek­ te der Umspezifizierung auf die Schaltungsverzögerung und auf die Störimpulsaktivitäten in Signalen der RTL-Schaltung (COP w/o Nebeneffekte) umstrukturiert. Diese Ergebnisse wur­ den mit COP-Techniken verglichen und sind in Tabelle 2 dar­ gestellt. Die Ergebnisse zeigen, daß, wenn die negativen Auswirkungen des Powermanagements auf die Schaltungsverzöge­ rung und den durch störimpulsinduzierten Leistungsverbrauch ignoriert werden, ein wesentlicher Anstieg (bis 76%) der Schaltungsverzögerung erhalten wird, und daß Leistungsein­ sparungen durch eine Erhöhung des störimpulsinduzierten Lei­ stungsverbrauchs kompensiert werden.

Tabelle 2

Experimentelle Ergebnisse: Vermeidung der negati­ ven Effekte des Powermanagements

Die Erfindung wurde unter Bezug auf bestimmte Ausfüh­ rungsformen der Erfindung beschrieben, für Fachleute ist je­ doch ersichtlich, daß innerhalb des Schutzumfangs der vor­ liegenden Erfindung verschiedene Modifikationen und Änderun­ gen vorgenommen werden können.

Claims (25)

1. Controller-basiertes Powermanagementsystem für sequen­ tielle Schaltungen mit:
einer Schaltungseingangseinheit;
einem Register-Transfer-Level- (RTL-) Schaltungs­ strukturanalysator;
einer Controller-Umstrukturierungseinheit; und einer Schaltungsausgangseinheit
wobei die Schaltungseingangseinheit eine sequenti­ elle Schaltung empfängt;
der RTL-Schaltungsstrukturanalysator die sequenti­ elle Schaltung für eine Controller-Umspezifizierung analysiert;
die Controller-Umstrukturierungseinheit die Schal­ tung unter Verwendung einer Controller-Umspezifizierung durch Ändern nur der Steuerlogik der sequentiellen Schaltung umstrukturiert, um den Leistungsverbrauch zu reduzieren; und
die Ausgangseinheit eine umstrukturierte Schaltung ausgibt.

2. Controller-basiertes Powermanagementsystem nach An­ spruch 1, wobei die Controller-Umstrukturierungseinheit aufweist:
einen RTL-Einheit-Zähler;
einen Aktivitätsgraphgenerator;
eine Aktivitätsgraphumetikettierungseinrichtung; und
einen Steuerlogikreflektor;
wobei der RTL-Einheit-Zähler RTL-Einheiten in der sequentiellen Schaltung zählt;
der Aktivitätsgraphgenerator Aktivitätsgraphen der RTL-Einheiten erzeugt; und
die Aktivitätsgraphumetikettierungseinrichtung die Aktivitätsgraphen umetikettiert.

3. Controller-basiertes Powermanagementsystem nach An­ spruch 1 oder 2, wobei der RTL-Schaltungsstruktur­ analysator aufweist:
eine RTL-Block-Identifizierungseinrichtung;
eine Datenabhängigkeitsgraph-Extraktionseinrich­ tung;
eine Steuerungsabhängigkeitsgraph-Extraktionsein­ richtung; und
eine RTL-Block-Sortiereinrichtung;
wobei die RTL-Block-Identifizierungseinrichtung RTL-Blöcke in der sequentiellen Schaltung identifi­ ziert;
die Datenabhängigkeitsgraph-Extraktionseinrichtung einen Datenabhängigkeitsgraphen der sequentiellen Schaltung extrahiert;
die Steuerungsabhängigkeitsgraph-Extraktionsein­ richtung einen Steuerungsabhängigkeitsgraphen der se­ quentiellen Schaltung extrahiert; und
die RTL-Block-Sortiereinrichtung die RTL-Blöcke sortiert.

4. Controller-basiertes Powermanagementsystem nach einem der Ansprüche 1 bis 3, wobei die Controller-Umstruktu­ rierungseinheit ferner aufweist:
eine Verzögerungsabschätzungseinrichtung;
eine Einrichtung zum Identifizieren kombinatori­ scher Schleifen; und
eine Schaltaktivitätabschätzungseinrichtung;
wobei die Verzögerungsabschätzungseinrichtung in eine umstrukturierte Schaltung eingeführte Verzögerun­ gen abschätzt;
die Einrichtung zum Identifizieren kombinatori­ scher Schleifen kombinatorische Schleifen in der um­ strukturierten Schaltung identifiziert; und
die Schaltaktivitätabschätzungseinrichtung jegli­ che Schaltaktivität in der umstrukturierten Schaltung abschätzt.

5. Verfahren zum Ändern der Steuerlogik einer sequentiel­ len Schaltung zum Reduzieren des Leistungsverbrauchs, wobei durch das Verfahren die Datenlogik der sequenti­ ellen Schaltung außer bezüglich des Leistungsverbrauchs in der Datenlogik der sequentiellen Schaltung nicht be­ einflußt.

6. Verfahren zum Ändern der Steuerlogik einer sequentiel­ len Schaltung zum Reduzieren des Leistungsverbrauchs, wobei das Verfahren die Schritte aufweist:

• a) Erzeugen eines Aktivitätsgraphen der sequenti­ ellen Schaltung;
• b) Identifizieren von inaktiven Zuständen im Ak­ tivitätsgraphen;
• c) Ändern der Steuerlogik durch Umetikettieren der inaktiven Zustände, um umetikettierte inaktive Zu­ stände zu bilden; und
• d) Umstrukturieren der Steuerlogik unter Verwen­ dung der umetikettierten inaktiven Zustände.

7. Verfahren nach Anspruch 6, wobei Schritt (a) ferner aufweist:

• a) (1) Identifizieren von Zuständen mit verschach­ telten Bedingungsoperationen;
• b) (2) Teilen der Zustände in mehrere Unterzustän­ de, wobei jeder der mehreren Unterzuständen einem von sich wechselseitig ausschließenden Bedingungspfaden entspricht; und
• c) (3) Erzeugen eines Vertex im Aktivitätsgraphen für jeden der mehreren Unterzustände.

8. Verfahren nach Anspruch 6 oder 7, wobei Schritt (c) ferner aufweist:

• a) (1) Umetikettieren von Zuständen und Unterzu­ ständen;
• b) (2) Identifizieren einer Untergruppe der Zu­ stände und einer Untergruppe der Unterzustände, in de­ nen Störimpulse auftreten; und
• c) (3) Rückgängigmachen der Umetikettierung für die Untergruppe der Zustände und die Untergruppe der Unterzustände, die in Schritt (c) (2) identifiziert wur­ den.

9. Verfahren nach einem der Ansprüche 6 bis 8, wobei tran­ sitive Fan-Outs zu einer Schaltungskomponente in der sequentiellen Schaltung identifiziert und umspezifi­ ziert werden, bevor die Schaltungskomponente umspezifi­ ziert wird.

10. Verfahren nach einem der Ansprüche 6 bis 9, wobei die Zustände und ihre entsprechenden Unterzustände, von de­ nen bekannt ist, daß die Ausgangssignale ihrer Arithme­ tiklogikeinheit störimpulsbelastet sind, für das Umeti­ kettieren nicht ausgewählt werden.

11. Verfahren nach einem der Ansprüche 8 bis 10, wobei Schritt (c) ferner aufweist:

• a) (4) Identifizieren von Unterzuständen, die, wenn sie unterschiedlich etikettiert sind, zu einer Er­ höhung der Verzögerung umspezifizierter Steuersignale führen;
• b) (5) Vereinigen von in Schritt (c) (4) identifi­ zierten Unterzuständen in einem einzigen Vertex.

12. Verfahren nach einem der Ansprüche 6 bis 11, wobei Schritt (c) ferner aufweist:

• a) (6) Identifizieren von Paaren von Unterzustän­ den, die jedem der Zustände zugeordnet sind, wobei min­ destens ein Element jedes Paars inaktiv ist;
• b) (7) Identifizieren zusätzlicher Abhängigkeiten, die eingeführt werden, wenn die Paare von Unterzustän­ den umetikettiert werden;
• c) (8) Ausführen eines linearen Zeitdurchlaufs für die Schaltung;
• d) (9) Bestimmen, ob ein kombinatorischer Zyklus eingeführt wird; und
• e) (10) Vereinigen jedes der Paare von Unterzu­ ständen in einem einzigen Vertex im Aktivitätsgraphen, wenn ein kombinatorischer Zyklus eingeführt wurde.

13. Verfahren nach Anspruch 11 oder 12, wobei ein High- Level-Verzögerungsbestimmungswerkzeug verwendet wird, um negative Toleranzen zu bestimmen.

14. Verfahren zum Powermanagement durch Steuerungs- Umspezifizierung, wobei das Verfahren die Schritte auf­ weist:

• a) Teilen eines Datenpfades einer sequentiellen Schaltung in RTL-Blöcke;
• b) Erzeugen eines oder mehrerer Abhängigkeitsgra­ phen;
• c) Ändern der Reihenfolge, in der die RTL-Blöcke für eine Umspezifizierung ausgewählt werden, unter Ver­ wendung des einen oder mehrerer Abhängigkeitsgraphen, um eine geordnete Liste zu erzeugen;
• d) Auswählen der nächsten nichtumspezifizierten RTL-Einheit in der geordneten Liste;
• e) Umspezifizieren jedes Multiplexerbaums, der der in Schritt (d) ausgewählten RTL-Einheit Signale zu­ führt; und
• f) Wiederholen der Schritte (d) bis (e) für alle RTL-Einheiten in der geordneten Liste.

15. Verfahren nach Anspruch 14, wobei einer der Abhängig­ keitsgraphen ein Datenabhängigkeitsgraph ist.

16. Verfahren nach Anspruch 14, wobei einer der Abhängig­ keitsgraphen ein Steuerungsabhängigkeitsgraph ist.

17. Verfahren nach einem der Ansprüche 14 bis 16, wobei die Umspezifizierung in Schritt (e) unter Verwendung der folgenden Schritt ausgeführt wird:

• a) (1) Erzeugen eines Aktivitätsgraphen;
• b) (2) Vereinigen von Unterzuständen im Aktivi­ tätsgraphen;
• c) (3) Markieren störimpulsbelasteter Datenein­ gangssignale;
• d) (4) Anwenden eines Etikettiervorgangs mit mini­ malem Aufwand auf den Aktivitätsgraphen;
• e) (5) Rückgängigmachen des Etikettierens für die störimpulsbelasteten Etiketten im Aktivitätsgraph;
• f) (6) Wiederholen der Schritte (e) (4)-(e) (5) für alle nicht-etikettierten Vertices;
• g) (7) rekursives Umspezifizieren eines linken Multiplexerbaum-Vorgängers; und
• h) (8) rekursives Umspezifizieren eines rechten Multiplexerbaum Vorgängers.

18. Verfahren nach Anspruch 17, wobei der Schritt (e) (2) zum Vereinigen von Unterzuständen aufweist:

• a) (2) (i) Auswählen eines Zustands;
• b) (2) (ii) Identifizieren eines Paars von Un­ terzuständen für den Zustand;
• c) (2) (iii) Bestimmen, ob mindestens ein Unter­ zustand des Paars von Unterzuständen inaktiv ist;
• d) (2) (iv) Vereinigen der Unterzustände, wenn Schritt (e)(2) (iii) wahr ist und wenn Zyklen erfaßt werden;
• e) (2) (v) Vereinigen der Unterzustände, wenn Schritt (e) (2) (iii) wahr ist und wenn die bestimmte Verzögerung größer ist als eine Zyklusperiode;
• f) (2) (vi) Wiederholen der Schritte (e) (2) (ii) bis (e) (2) (v) für alle Paare von Unterzuständen des Zu­ stands; und
• g) (2) (vii) Wiederholen der Schritte (e) (2) (1) bis (e) (2) (vi) für alle Zustände.

19. Verfahren nach Anspruch 17 oder 18, wobei Schritt (e) (4) aufweist:

• a) (4) (i) Identifizieren des nächsten nicht- etikettierten Vertex im Aktivitätsgraphen gemäß einem vorausgewählen Kriterium;
• b) (4) (ii) Etikettieren nicht-etikettierter Vertices, so daß der Zusatzaufwand minimiert wird; und
• c) (4) (iii) Wiederholen von Schritt (e) (4) (ii) für jeden nicht-etikettierten Vertex.

20. Verfahren nach Anspruch 19, wobei Schritt (e) (4) (i) aufweist:
Auswählen eines nicht-etikettierten Vertex V*;
Identifizieren aller Übergänge von allen etiket­ tierten Vertices Vi nach V*;
Zuweisen eines Aufwandes für Übergänge zwischen allen Vertices, die im vorangehenden Schritt identifi­ ziert wurden;
Addieren der im vorangehenden Schritt zugewiesenen Aufwände, um eine erste Summe zu bilden;
Identifizieren aller Übergänge von V* zu allen etikettierten Vertices Vj;
Zuweisen eines Aufwandes für Übergänge zwischen allen im vorangehenden Schritt identifizierten Ver­ tices;
Addieren der im vorangehenden Schritt zugewiesenen Aufwände, um eine zweite Summe zu bilden;
Addieren der ersten und der zweiten Summe, um den etikettierten Vertexwert zu erhalten;
Wiederholen aller vorangehender Schritte für alle unetikettierten Vertices; und
Auswählen des Vertex mit maximalem etikettiertem Vertexwert.

21. Verfahren nach Anspruch 19 oder 20, wobei der zusätzli­ che Aufwand in Schritt (e) (4) (ii) unter Verwendung der Formel:
berechnet wird, wobei
Li und Lj Etiketten,
AM eine Aktivitätsmatrix, und
W eine Wahrscheinlichkeit oder eine Anzahl bzw. einen Zählwert der Übergänge zwischen den entsprechen­ den Unterzuständen bezeichnen.

22. Computerprogrammprodukt für ein controller-basiertes Powermanagementsystem für sequentielle Schaltungen mit einer Schaltungseingangseinheit, einem RTL-Schaltungs­ strukturanalysator, einer Controller-Umstrukturierungs­ einheit und einer Schaltungausgangseinheit, wobei das Computerprogrammprodukt ein computerlesbares Medium aufweist, mit:
einem Schaltungseingangseinheitcode;
einem RTL-Schaltungsstrukturanalysatorcode;
einem Controller-Umstrukturierungseinheitcode; und
einem Schaltungsausgangseinheitcode;
wobei einem Computer durch den Schaltungseingangs­ einheitcode ermöglicht wird, eine sequentielle Schal­ tung zu empfangen;
einem Computer durch den RTL- Schaltungsstrukturanalysatorcode ermöglicht wird, die sequentielle Schaltung für eine Controller- Umspezifizierung zu analysieren;
einem Computer durch den Controller- Umstrukturierungseinheitcode ermöglicht wird, die Schaltung unter Verwendung einer Controller-Umspezifi­ zierung durch Ändern nur der Steuerlogik umzustruktu­ rieren, um den Leistungsverbrauch zu reduzieren; und
durch den Schaltungsausgangseinheitcode eine um­ strukturierte Schaltung ausgegeben wird.

23. Computerprogrammprodukt nach Anspruch 22, wobei der Controller-Umstrukturierungseinheitcode aufweist:
einen RTL-Einheit-Zählercode;
einen Aktivitätsgraphgeneratorcode;
einen Aktivitätsgraph-Umetikettierungseinrich­ tungscode; und
einen Steuerlogikreflektorcode;
wobei einem Computer durch den RTL-Einheit- Zählercode ermöglicht wird, RTL-Einheiten in der se­ quentiellen Schaltung zu zählen;
einem Computer durch den Aktivitätsgraphgenerator­ code ermöglicht wird, einen Aktivitätsgraph der RTL- Einheiten zu erzeugen; und
einem Computer durch den Aktivitätsgraph- Umetikettierungseinrichtungscode ermöglicht wird, den Aktivitätsgraphen umzuetikettieren.

24. Computerprogrammprodukt nach Anspruch 22 oder 23, wobei der RTL-Schaltungsstrukturanalysatorcode aufweist:
einen RTL-Block-Identifizierungseinrichtungscode;
einen Datenabhängigkeitsgraph-Extraktionseinrich­ tungscode;
einen Steuerungsabhängigkeitsgraph-Extraktionsein­ richtungscode; und
einen RTL-Block-Sortiereinrichtungscode;
wobei einem Computer durch den RTL-Block- Identifizierungseinrichtungscode ermöglicht wird, RTL- Blöcke in der sequentiellen Schaltung zu identifizie­ ren;
einem Computer durch den Datenabhängigkeitsgraph- Extraktionseinrichtungscode ermöglicht wird, einen Da­ tenabhängigkeitsgraphen der sequentiellen Schaltung zu extrahieren;
einem Computer durch den Steuerungsabhängigkeits­ graph-Extraktionseinrichtungscode ermöglicht wird, ei­ nen Steuerungsabhängigkeitsgraphen der sequentiellen Schaltung zu extrahieren; und
einem Computer durch den RTL-Block- Sortiereinrichtungscode ermöglicht wird, die RTL-Blöcke zu sortieren.

25. Computerprogrammprodukt nach einem der Ansprüche 22 bis 24 wobei der Controller-Umstrukturierungseinheitcode ferner aufweist:
einen Verzögerungsabschätzungseinrichtungscode;
einen Code einer Einrichtung zum Identifizieren kombinatorischer Schleifen; und
einen Schaltaktivitätabschätzungseinrichtungscode;
wobei einem Computer durch den Verzögerungsab­ schätzungseinrichtungscode ermöglicht wird, in eine um­ strukturierte Schaltung eingeführte Verzögerungen abzu­ schätzen;
einem Computer durch den Code der Einrichtung zum Identifizieren kombinatorischer Schleifen ermöglicht wird, kombinatorische Schleifen in der umstrukturierten Schaltung zu identifizieren; und
einem Computer durch den Schaltaktivitätabschät­ zungseinrichtungscode ermöglicht wird, alle Schaltakti­ vitäten in der umstrukturierten Schaltung abzuschätzen.