Entwicklung eines integrierten Schaltkreises für den Algorithmus Polynomdivision

Inhaltsverzeichnis

1. Einleitung

2. Aufgabenstellung
2.1. Der Algorithmus im Detail
2.2. Der Algorithmus am Beispiel
2.3. Der Algorithmus in Java

3. Entwurf
3.1. Entwurfsziele
3.2. Generelle Überlegungen
3.3. Speicheraufteilung
3.3.1. Grobe Speicheraufteilung
3.3.2. Detaillierte Speicheraufteilung
3.4. Struktogramm
3.5. Daten ussgraph
3.5.1. Daten ussgraph ohne Anpassung
3.5.2. Daten ussgraph mit Anpassung
3.5.3. Ausblick - Daten ussgraph der Implementierung .
3.6. Register-Transfer-Folgen und Buszuordnung
3.6.1. RT-Folgen
3.6.2. Buszuordnung
3.7. Zustandsgraph
3.8. Datenpfad
3.9. Finite State Machine
3.9.1. Zustandscodierung
3.9.2. Zustandsautomat mit JK-FlipFlops
3.10. Logikfunktionen der Flip ops
3.11. Steuerlogik
3.12. Top-Zelle

4. Implementierung und Simulation - Arbeitsschritte mit Cadence
4.1. Realisierung des Datenpfades mit Schematic
4.2. Verhaltensbeschreibung in Verilog
4.2.1. Beschreibung der Steuerlogik
4.2.2. Beschreibung der Zustandsmaschine
4.3. Realisierung der Zustandsmaschine in Schematic .
4.4. Realisierung der Top-Zelle in Schematic .
4.5. Veriolog-Simulation
4.5.1. Steuerlogik Test
4.5.2. Zustandsmaschine Test
4.5.3. Top-Zelle Test

5. Synthese

6. Zusammenfassung, Wertung und Ausblick

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

A. Werkzeuge und Hilfsmittel

B. Quelltexte Java Programm
B.1. 1. Version
B.2. 2. Version

C. RT-Folgen mit zwei Addierern

D. Quelltexte Verilog
D.1. Verilog-Beschreibung
D.1.1. Steuerlogik
D.1.2. Zustandsautomat
D.2. Veriolog-Testbench
D.2.1. Steuerlogik_TB
D.2.2. Zustandsmaschine_TB .
D.2.3. Top-Zelle_TB
D.3. Anfangsbelegung des Speichers zum Test
D.4. Netlist

E. Syntheseergebnisse

1. Einleitung

Die vorliegende Belegarbeit entstand zum vorlesungsbegleitenden Praktikum zu der Lehrveranstaltung Schaltkreis- und Systementwurf. Sie bildet die Grundlage für die Bewertung der erzielten Ergebnisse.

Ziel des Praktikums ist die Realisierung einer algorithmischen Aufgabenstellung als integrierter Schaltkreis (engl. Integrated Circuit - IC). Der Entwurf und die Veri kation des Schaltkreises bzw. Prozessors erfolgt im ASIC (engl. Application Speci c Integrated Circuit) mit Standardzellen in 0.35 µm CMOS¹-Technologie mit der EDA² -Software CADENCE. Die Entscheidung für die numerische mathematische Rechenvorschrift el zu gunsten der Polynomdivision aus. Der Algorithmus führt mit einer zum Teil vorgegebenen Speicherbelegung Operationen durch und speichert das Ergebnis wieder im Hauptspeicher ab.

Dabei wird ein vertiefender Einblick in den Entwurf komplexer VLSI-Schaltungen vermittelt. Der Entwurfs uss (Design ow) erfolgt nach der Top-down Strategie. Das Top-Down-Design beginnt mit der Formulierung eines Überblicks über das System, wobei Details zunächst vernachlässigt werden. Anschlieÿend erfolgt die Unterteilung in Abschnitte, wobei die gewünschte Funktionalität zunächst umgangssprachlich angegeben wird. Im Folgenden werden diese Abschnitte genauer ausformuliert, bis schlieÿlich die komplette, detaillierte Spezi kation des Algorithmus erreicht ist. Bei der Top-Down-Methode liegt der Schwerpunkt auf Planung und Verständnis des Systems.

1. Einleitung

Folgende Arbeitsschritte sind in diesem Beleg dokumentiert:

- Beschreibung des zu realisierenden Algorithmus
- Entwurfsziele und generelle Überlegungen
- Einteilung des Speichers
- Erstellung einer schematischen Darstellung des Algorithmus (Struktogramm und Daten ussgraph)
- Umstellung des Daten ussgraph unter Implementierungsgesichtspunkten (Scheduling, Ressourcenzuweisung)
- Erstellung der Architektur des Datenpfades (Anordnung und Verbindung von Verarbeitungs- und Speicherblöcken) unter Verwendung der vorgefertigten Datenpfad-Baublöcke
- Erstellung einer Folge von Ausführungsanweisungen für den Datenpfad (Register-Transfer-Folgen)
- Ableitung des Zustandsgraphen und der Zustandscodierung aus den RT-Folgen
- Erstellung der Logikgleichungen der Übergangslogik der FSM sowie deren Vereinfachung
- Implementierung einer Verhaltensbeschreibung des Zustandsautomaten und der Steuerlogik für den Datenpfad in Verilog
- Entwurf einer digitalen Schaltung (Gatter) zur Realisierung des Zustands automaten unter Verwendung von Elementen der Bibliothek CORELIB
- Veri kation und Simulation mit Cadence-Verilog-XL
- RTL³- und Layoutsynthese der Gesamtschaltung
- Zusammenfassung und Wertung der Arbeit

2. Aufgabenstellung

In diesem Beleg wird die Implementation des Algorithmus der Polynomdivision dokumentiert.

Mit einer vorgegebenen Speicherbelegung führt der Schaltkreis die de nierten Anweisungen aus und legt das Ergebnis wieder im RAM (engl. Random Access Memory) ab. Demzufolge werden alle Werte (Koe zienten der Operanden, Grad der Operanden) zuvor im Speicher an fest vorde nierten Stellen abgelegt. Die dabei frei zu de nierende Speicheraufteilung ist im Kapitel 3.3 dargestellt. Es sei erwähnt, dass der Zugri auf den Speicher einzeln erfolgt.

Im Folgenden werden die Anforderungen an den Schaltkreis beschrieben. Der Schaltkreis soll in der Lage sein, für beliebig viele Stellen der Operanden die Rechenvorschrift auszuführen. Eine Beschränkung bietet lediglich die Gröÿe des Speichers. Die komplette Originalaufgabe mit Lösung (inklusive Rest, falls vorhanden) soll am Ende des Ablaufs im Speicher enthalten sein. Es wird nicht angenommen, dass der Dividend einen höheren Grad besitzt als der Divisor. Diese Eingangsbelegungen müssen abgefangen werden.

Der Schaltkreis löst Aufgaben der folgenden Form:

Abbildung in dieser Leseprobe nicht enthalten

2.1. Der Algorithmus im Detail

Wie bei der schriftlichen Division von Zahlen zieht man auch bei der Polynomdivision vom Dividenden nach und nach passende Vielfache des Divisors ab, bis am Ende möglichst kein Rest mehr bleibt. Dazu wird in jedem Schritt derjenige Summand des Restes eliminiert, bei dem x in der höchsten Potenz steht. Die Summanden des Quotienten ergeben sich aus der Division der Summanden der jeweiligen Reste durch den Summanden des Divisors mit der höchsten Potenz von x.

Wenn der Dividend einen höheren Grad besitzt als der Divisor, dann schreibt der Schaltkreis in die erste Speicherzelle nach Ablauf die Zi er 2, ansonsten eine 1. Daran kann auch entschieden werden, ob die Berechnung vollständig ausgeführt wurde oder nicht.

2.2. Der Algorithmus am Beispiel

Die hier verwendete Beispielaufgabe dient auch zu Testzwecken.

Beispielaufgabe:

Abbildung in dieser Leseprobe nicht enthalten

2.2. Der Algorithmus am Beispiel

Optimierung:

Es ist unschwer zu erkennen, dass die erste Stelle des Restdividenden stets 0 wird. (Das ist das Ziel der Berechnung eines Rundendurchlaufs.) Daher wird dieser Wert nicht mehr berechnet, sondern gleich 0 gesetzt. Dies spart Zeit.

2.3. Der Algorithmus in Java

Zur Verdeutlichung des Algorithmus und der genauen Funktionsweise ist der Ablauf in einem JAVA-Programm programmiert. Die Quelltexte be nden sich im Anhang B. Die korrekte Funktionsweise ist mit Testdaten veri ziert. In der ersten Version des Programms entsteht eine normale Java Software, welche keine Anpassungen bezüglich Hardware besitzt. Auf Parallelisierung wird vorerst ebenfalls kein Wert gelegt. Diese ist im Anhang B.1 abgedruckt.

Daraus entwickelt sich eine an die Hardware angepasste Beschreibung. Das bedeutet, das Java Programm wird so umgeschrieben, dass es nur einen linearen Speicher gibt. Als Zwischenspeicher dienen Register. Weiterhin wurde auch Versucht auf Parallelisierung und E zient zu achten. Durch Registermanagement und logische Verbesserungen entstand ein Programm mit einer minimierten Berechnungsanzahl. Die meisten Operationen wurden in einzelne Berechnungen mit nur 2 Operanden aufgesplittet. Dies sind wesentliche Schritte hin zur Hardwareimplementierung. Da in der Aufgabenstellung gefordert ist, dass alle Operanden nach Ablauf des Algorithmus im Speicher enthalten sind, ist eine extra Kopier-Schleife am Anfang notwendig. Diese Version der Software ist im B.2 dargestellt und bildet die Grundlage der Implementierung.

Anmerkung:

Da viele Register in der äuÿeren und inneren Schleife für die schnelle Abarbeitung benötigt werden, stehen zu Beginn einige davon ungenutzt zur Verfügung. Unter Nutzung dieser ist es gelungen, alle einmaligen Operationen vor Beginn aller Schleifen zu berechnen. Auch in den Schleifen konnte die Struktur verbessert werden. Dies vereinfacht die Gesamtstruktur.

3. Entwurf

Nach der Entscheidung über den Algorithmus und der Validierung der Funktionsweise, kann der Entwurf mittels Top-Down-Design erfolgen. Als erstes ist über die Speicheraufteilung zu entscheiden. Als nächstes wird der Daten ussgraph entworfen. Aus diesen beiden Dingen soll nun der Ressourcenbedarf abgeschätzt werden, um den Datenpfad und die Register-Transfer-Folgen aufzubauen. Anschlieÿend entsteht der Zustandsgraph, woraus wiederum die Zustandscodierung zu entwickeln ist. Zum Schluss entsteht der Zustandsautomat und die Steuerlogik, welche in Hardware gebaut wird.

3.1. Entwurfsziele

Vor der Übertragung des Algorithmus in eine integrierte Schaltung ist es von groÿer Bedeutung diesen zu optimieren. Dabei sollen folgende Aspekte berücksichtigt werden:

- Hoher Durchsatz
- Gleichmäÿig hohe Auslastung der Ressourcen
- Geringe Anzahl an Bussen und Bauteilen
- Geringe Anzahl an Steuerschritten
- Geringer Flächenbedarf der Schaltung
- Geringer Leerlauf der Komponenten des Datenpfades
- Wenige Ressourcen im Datenpfad

Ziel ist es vorrangig einen schnellen Schaltkreis zu entwerfen, der wenig Steuerschritte zur Abarbeitung benötigt und dennoch eine gute Ressourcenauslastung besitzt. Um dieses Ziel zu erreichen wird algorithmentechnisch und steuerlogisch optimiert.

3.2. Generelle Überlegungen

Der Schaltkreis erlaubt nur die Verwendung von integer Zahlen (positive und negative) während des gesamten Ablaufs. Es ist darauf zu achten, dass innerhalb der Lösungsberechnung keine Gleitkommazahlen entstehen, da diese abgerundet werden. Das bedeutet eine Einschränkung der Aufgaben, die der Schaltkreis nicht richtig lösen kann. In einer weiteren Ausbaustufe kann dieses Problem beseitigt werden. Die Zahlen sind daraufhin im Zweierkomplement dargestellt.

Beispielproblem bei Gleitkommazahl:

Diese Beispielaufgabe verdeutlicht, dass das Ergebnis nicht zu gebrauchen ist, wenn sich Gleitkommazahlen in der Berechnung ergeben.

Beispielaufgabe:

Abbildung in dieser Leseprobe nicht enthalten

Die Rundungsfehler ziehen sich durch den ganzen Lösungsweg und das Ergebnis ist nicht verwendbar. Es wird stets abgerundet, wenn es nötig ist. Der Vergleich zur richtigen Lösung auf der folgenden Seite zeigt den Unterschied deutlich. F bedeutet, dass an dieser Stelle eine 0 stehen sollte, aber durch den Rundungsfehler steht eine Zahl.

3.2. Generelle Überlegungen

Richtige Lösung:

Abbildung in dieser Leseprobe nicht enthalten

3.3. Speicheraufteilung

Zur Bearbeitung des Problems steht nur ein groÿer linearer Speicher zur Verfügung. Dadurch werden alle Werte hintereinander in den externen RAM abgespeichert. Bei exiblen Operandengröÿen hat das eine indirekte Adressierung zur Folge. Um alle Zahlen korrekt zu referenzieren, sind Hilfsvariablen notwendig, welche die Startadresse der einzelnen Operanden enthalten. Diese Hilfsdaten müssen wiederum direkt adressierbar sein und stehen daher am Anfang des Datenspeichers. Ohne direkte Adressierung ist es aufwendig zu entscheiden, welche Daten wo abgespeichert sind. Für die direkte Adressierung werden Werte von Konstanten oder Registern auf den EDB (externer Datenbus) gelegt und der Inhalt der Speicherzelle in das Register DIN (engl. Daten in) gespeichert. Bei der indirekten Adressierung wird zuerst die eigentliche Adresse ermittelt, welche in einem Speicher steht, um danach den Wert dieser Adresse zu erhalten.

3.3.1. Grobe Speicheraufteilung

Die grobe Speicherstrukturierung wird in Tabelle 3.1 dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.1.: Speicherbelegung RAM Übersicht

Es sei vermerkt, dass lediglich die Koe zienten der Operanden, des Ergebnisses und des Restes (nur Zähler) gespeichert werden. Der jeweilige Grad des Koe zienten ist aus der Position zu erkennen. Der Nenner des Restes ist der Divisor und wird daher nicht unnötigerweise doppelt abgespeichert.

3.3.2. Detaillierte Speicheraufteilung

Anhand des programmierten Algorithmus in Java lässt sich eine sinnvolle Speicherbelegung schlussfolgern. Die Belegung der Register und die benötigten Konstanten sind ebenfalls zu erkennen. Zu beachten ist dabei, dass am Anfang des Speichers aus praktischen Gründen die Grad-Zahlen und Start-Adressen stehen, welche einen O set von 8 hervorrufen (Bezeichnung beginnt bei 0). Weiterhin besitzt eine Zahl vom Grad i, i + 1 Koe zienten. Dadurch ergeben sich die jeweiligen

3.3. Speicheraufteilung

Verschiebungswerte. Die Tabelle 3.2. zeigt die detaillierte Aufteilung des Speichers.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.2.: Speicherbelegung RAM

N,M,K und F ist der jeweilige Grad des Polynoms.

(p(x) = N; q(x) = M; s(x) = K; z(x) = F; auf Grund der Übersichtlichkeit als nur eine Variable de niert)

Die Startadresse des Dividenden ist nicht dynamisch und beginnt immer bei 7.

Die Speicherzelle 0, an der das Berechnungsende erkennbar ist, wird am Anfang mit

0 initialisiert.

Die Berechnung der Variablen: gs, q(x), s(x) und z(x) ndet zur Laufzeit statt. Sie werden vorerst mit 0 initialisiert und während des Programmablaufs überschrieben. Somit benötigt der Algorithmus zu Beginn diese Werte: gp,gq, an ... a0, bm ... b0

3. Entwurf

Register werden verwendet um Zwischenwerte zu speichern. Diese Speicher sind sehr schnell und enthalten neben Teilergebnissen auch Adressen und Zahlen die oft benötigt werden bzw. wo ein Speicherzugri sehr lange dauern würde. Diese zusätzlichen Register werden zur Geschwindigkeitsoptimierung eingesetzt und der Flaschenhals¹ -Speicher abgeschwächt. Durch das Zusammenspiel der äuÿeren und inneren Schleife (was den Hauptteil des Algorithmus darstellt) sind zehn Register notwendig. Dabei werden einige Register mehrfach genutzt, bei denen es möglich ist, um die Anzahl gering zu halten. In der Tabelle 3.3 ist die Belegung aller Register dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.3.: Registerbelegung

Die Register R[2] und R[5]werden zusätzlich am Ablaufbeginn des Algorithmus verwendet, um die Start-Adressen des Quotientens und des Restes im Speicher zu berechnen.

Die Register R[3], R[5]und R[7] dienen zusätzlich am Anfang dazu, den Dividenden zu erhalten. Es wird eine Kopie am Ende des Speichers angelegt, woraus sich der Rest später ergibt.

Die Speicherzelle R[10] ergibt sich erst in Kapitel 3.5 und wird dort erläutert.

Die Belegung aller Register ist zu Beginn irrelevant, da sie überschrieben werden.

3.3. Speicheraufteilung

Des Weiteren gibt es noch einen Speicher für Konstanten. Für die direkte Speicheradressierung haben die Zahlen eine wesentliche Bedeutung. Auÿerdem sind die Werte notwendig, um Speicheradressen zu berechnen, Iterationszählvariable hoch bzw. runter zu zählen und Vergleiche durchzuführen.

Die Tabelle 3.4 zeigt die benötigten Werte, welche von Anfang an fest auf dem Chip de niert werden.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.4.: Konstantenspeicher

Anmerkung:

Es besteht die Möglichkeit Konstanten einzusparen, indem der Algorithmus erweitert wird und Vielfache eines anderen Konstantenwertes verwendet werden. Dies soll hier aber nicht geschehen, da dies den Ablauf verzögern würde.

Als letztes existieren noch Speicher am Ausgang jeder Arithmetikeinheit, welcher die Ergebnisse der jeweiligen Operation zwischenspeichert. Diese werden mit TX bezeichnet, wobei X eine Zahl ist. Die genaue Anzahl wird in Kapitel 3.5. festgelegt. AO (engl. Adress out) und DIN werden benötigt, um mit dem RAM zu kommunizieren. Als letztes existieren noch Flagregister FX. Die ergeben sich im Kapitel 3.6 und werden dort näher erläutert.

3.4. Struktogramm

Auf Basis des Algorithmus und des optimierten Programmcodes in Java ist es möglich einen Programmablaufplan zu erstellen. Das Struktogramm ist in Abbildung 3.1 abgebildet.

MEM verweist immer auf den jeweiligen Speicherinhalt des RAMs.

MEM[ MEM[X] ] bzw. MEM[ R[X] ] bildet dabei eine indirekte Adressierung vom Speicherinhalt von der Adresse MEM[X] bzw. R[X]. X steht dabei für einen spezi schen Zahlenwert. R[X] bilden wie schon in vorherigem Kapitel 3.3 beschrieben die Register. Für das bessere Verständnis sind hinter den / / die Kommentare mit angegeben.

Hinweis:

Da im weiteren Verlauf der Bearbeitung der Aufgabe (während der Erstellung des Daten ussgraph) noch Verbesserungen entstanden sind, bildet das Struktogramm nicht exakt den entworfenen Algorithmus ab. Dieses Struktogramm gehört zum Java-Code B.2, welcher die Grundlage für die Implementierung bildet. Es fehlt das Register R[10], welches Datenabhängigkeiten au öst, um parallele Vorgänge zu ermöglichen, die hier aber nicht ersichtlich sind.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1.: Struktogramm Polynomdivision

3.5. Daten ussgraph

Der Daten ussgraph ist ein wichtiger Baustein zum fertigen Schaltkreis. Er dient der schematischen Darstellung vom Algorithmus und dessen Ablauf. Datenabhängigkeiten und strukturelle Abläufe sollen verdeutlicht werden. Ausgehend vom Hardware angepassten Java-Code im Anhang B.2 ergeben sich die folgenden Graphen.

In Abbildung 3.2. und 3.3. ist der Daten ussplan ohne Optimierung zu sehen. Es wird angenommen, dass ausreichend viele Bauelemente zur Verfügung stehen, um den maximalen Parallelisierungsgrad zu erhalten. Daraus wurde ein angepasster Plan erstellt, mit einer beschränkten Anzahl von Arithmetischen Einheiten. Dargestellt in Abbildung 3.4 und 3.5. Die Festlegung der Anzahl der jeweiligen Recheneinheiten geschieht auf der Grundlage des Verhältnisses zwischen Geschwindigkeit der Abarbeitung und der Auslastung der Einheiten. Wenn es sinnvoll ist, werden mehrere arithmetische Einheiten verbaut, um die Anzahl der Steuerschritte zu reduzieren. Dabei wird versucht, die abzuarbeitenden Operationen möglichst optimal anzuordnen, um eine hohe E ektivität des Schaltkreises zu erreichen.

Es besteht die Möglichkeit, Befehle vor die Sprungentscheidung zu ziehen, solange das Ergebnis nicht zurückgeschrieben wird. Wenn die Berechnung umsonst ist, dann wird minimal Energie verschwendet. Aber im günstigen häu gen Fall spart dies Zeit.

Einschränkung:

Es sei darauf hingewiesen, dass noch nicht die mehrere Takte lange Berechnungszeit des Dividierers einbezogen ist. Weiterhin wird noch nicht beachtet, dass die indirekte Speicheradressierung mehrere Takte benötigt und nur einzeln auf den Speicher zugegri en werden darf. (In einem Takt ist es nicht erlaubt, mehrere Werte aus dem Speicher zu holen) Zwischenregister sind nicht mit angegeben, da diese erst in den RT-Folgen im Kapitel 3.6 festgelegt werden.

3.5.1. Daten ussgraph ohne Anpassung

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2.: Daten ussplan ohne Optimierung (Teil1)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3.: Daten ussplan ohne Optimierung (Teil2)

Erläuterungen:

In der Kopier-Schleife kann MEM[ R[5]] später zurückgeschrieben, da vorher die Sprungbedingung (engl. Branch Condition - BC) ausgewertet werden muss. Somit verzögert sich auch das Zurückschreiben von R[5]. Der gleiche Fall tritt in der äuÿeren Schleife für MEM[ R[4] ] und in der inneren Schleife für MEM[ R[5]] auf. Das Register R[5] darf in der Kopier-Schleife und in der inneren Schleife erst nach dem Schreiben in den Speicher (MEM[ R[5]]) mit dem neuen Wert beschrieben werden, da vorher der Wert für die Adressierung benötigt wird. Das gilt analog für R[4] in der äuÿeren Schleife. Dabei wird R[5]ebenfalls später zurückgeschrieben, da das Zurückschreiben von R[4] und R[5] in einem Schritt geschehen soll.

(nur eine Aktion, anstatt zwei)

3.5. Daten ussgraph

Es existieren zwei Enden. Ende 1 tritt ein, wenn der Divisorgrad gröÿer als der Dividendengrad ist. Ende 2 wird nach erfolgreicher Berechnung ausgeführt.

3.5.2. Daten ussgraph mit Anpassung

Die Struktur-Optimierungen nach dem ASAP-² und ALAP³ -Prinzip ergaben keine wesentlichen Verbesserungen. Der Gleitbereich der Operatoren gab Aufschluss über die Möglichkeiten. Mittels FDS (engl. Force direct Scheduling) entstand der optimale Plan.

Die Aufstellung des Daten ussgraphen zeigt, dass der Bauteilbedarf vorerst auf folgende Recheneinheiten begrenzt werden kann.

-2 Addierer
-1 Multiplizierer
- 1 Dividierer

Alle weiteren Bauteile und deren Verbindungen werden im Kapitel 3.8 dargestellt.

Der Versuch Funktionelles Pipelining einzuführen, um eine bessere Ressourcenauslastung durch zeitlich versetztes Abarbeiten von Teilalgorithmen zu bekommen, ist auf Grund der beschränkten Ressourcen nicht machbar, wie der optimierte Daten ussgraph 3.5. zeigt.

Strukturelles Pipelining:

Es wird ein zusätzliches Register R[10] eingeführt, um in der inneren Schleife, die sehr oft ausgeführt wird, die scheinbare Datenabhängigkeit (engl. Write after Read

- WAR) von R[5]aufzulösen. Dadurch kann ein Steuerschritt gespart werden und die Abarbeitung verläuft schneller. Das selbe Prinzip wird in der Kopier-Schleife angewendet. In der äuÿeren Schleife ist es für R[4] nicht notwendig, da der Dividierer mehrere Takte benötigt und somit genug Zeit bleibt, die Daten korrekt zurück zuschreiben. Daher steht R[4] und MEM[ R[4] ] auf dem gleichen Steuerschritt im Daten ussgraph mit Optimierung (wobei MEM[ R[4] ] noch das ehemalige R[4] meint).

Es ist möglich die erste If Anweisung (MEM[1] >= MEM[2] ) mit der ersten Berechnung (MEM[3] = MEM[1] - MEM[2] ) parallel auszuführen, da dies keinen Ein uss auf den weiteren Ablauf hat. Die Berechnung ist für beide sogar gleich, wie sich später herausstellt. Nur die verwendeten Ergebnisse sind unterschiedlich. Diese Optimierung spart einen Steuerschritt.

Diskussion (unter Berücksichtigung der Einschränkung):

Es besteht die Möglichkeit einen Addierer einzusparen. Allerdings erhöht sich dadurch die Anzahl der Steuerschritte. Am Ablaufplan ist zu erkennen, dass 2 Addierer ausgelastet werden können. Dies verdeutlicht die Ressourcenauslastung. Die innere Schleife wird sehr oft ausgeführt und würde somit einen Flaschenhals bilden, wenn nicht genügend arithmetische Einheiten zur Verfügung stehen. Daher el die Entscheidung vorerst auf 2 Addierer, um einen schnellen Ablauf zu gewährleisten. Im Verhältnis der Fläche ist die Addiereinheit wesentlich kleiner als der Dividierer und fällt somit nicht stark ins Gewicht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.4.: Daten ussgraph mit Anpassung (Teil1)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.5.: Daten ussgraph mit Anpassung (Teil2)

Die Ressourcenauslastung in der oft ausgeführten inneren Schleife zeigt, dass es eine richtige Entscheidung war 2 Addierer zu verwenden, um die Abarbeitung nicht groÿ zu behindern.

Der Multiplizierer und der Dividierer werden im Ablaufplan jeweils nur einmal benötigt, sind aber von essentieller Wichtigkeit und lassen sich daher nicht durch ein einfaches Prinzip ersetzen.

3.5.3. Ausblick - Daten ussgraph der Implementierung

Bei der Erstellung der RT-Folgen in Kapitel 3.6 ergibt sich eine neue Sicht auf die Anzahl der Addierer. Die detaillierte Erläuterung ist in Kapitel 3.6.1 nachzulesen. Es stellte sich heraus, dass durch die Verzögerung des Dividierers und des limitierten Speicherzugri es es sinnvoll ist, nur einen Addierer zu verwenden. Der Ablauf in den Schleifen, die den Hauptteil der Rechenzeit in Anspruch nehmen, wird nicht durch die Verwendung nur eines Addierers verzögert. Lediglich der Teil für die Vorbereitung der Berechnung.

In der äuÿeren Schleife muss die Datenabhängigkeit für R[2] aufgelöst werden. Durch die Zeitliche Verschiebung des Dividierers wird sonst R[2] zuerst aktualisiert, obwohl der frühere Wert noch nötig ist, um das Ergebnis an die richtige Stelle zurück zuschreiben. Dazu steht das Register R[10] zur Verfügung.

In den folgenden Date ussgraphen, Abbildung 3.6 und 3.7, ist die Verzögerung der Speicheroperationen und die 4 Takte lange Berechnung des Dividierers enthalten. Zwischenregister werden mit angegeben.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.6.: Daten ussgraph mit 1 Addierer (Teil1)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.7.: Daten ussgraph mit 1 Addierer (Teil2)

3.6. Register-Transfer-Folgen und Buszuordnung

3.6.1. RT-Folgen

Aus dem Daten ussgraphen ergeben sich die RT-Folgen (engl. Register-TransferFolgen) im Anhang C.1. und C.2.

Dadurch, dass der Dividierer 4 Takte zur Berechnung benötigt, und es einen limitierten Zugri auf den Speicher gibt, verschiebt sich die vorgesehene Anordnung der Steuerschritte des Daten ussgraphen. Der Versuch, die Addierer-Operationen in der äuÿeren und inneren Schleife über die zusätzlichen Schritte zu verteilen, gelingt. Auf Grund dieser Tatsachen wird im Hauptteil des Algorithmus nur ein Addierer benötigt. Demnach ist es sinnvoll, nur einen Addierer für den gesamten Ablauf zu verwenden, da der andere Teil des Ablaufs nicht stark beeinträchtigt wird. Die RTFolgen mit 2 Addierern sind auf Grund der Übersichtlichkeit im Anhang C zu nden. Somit ist die vorläu ge Betrachtung im Daten ussgraph hinfällig und es wird nur ein Addierer im Folgenden verwendet. Diese Tatsache ist bereits im Kapitel

3.5.3 erwähnt und nochmals ein neuer Daten ussgraph abgebildet, der die RT-Folgen wiederspiegelt.

Optimierung:

Bei der Erstellung wurde stets überlegt, welche Operationen parallel ablaufen können, um eine möglichst kleine Anzahl von Schritten zu bekommen, sofern es möglich ist. Dabei ist es sehr hilfreich, dass in mehrere Register gleichzeitig geschrieben bzw. aus Registern geladen werden kann. Weiterhin sei die Bestrebung möglichst wenig verschiedene Anbindungen der einzelnen Elemente an den Bus zu erzeugen, sowie wenige MUX (Multiplexer) und viele Tri-State Treiber zu verwenden. Dies geschieht unter der Maÿgabe, möglichst wenige Register und wenige Busse zu erzeugen. (Hier ist nur die optimierte Folge abgebildet. Die anderen Folgen sind nicht von Belangen.)

Die RT-Folgen zeigen den genauen Ablauf des Algorithmus auf dem Datenpfad, welcher in Kapitel 3.8 dargestellt wird, und bilden die Grundlage für die Erstellung der Steuerlogik. Dabei lassen sich die RT-Folgen in die 7 folgenden Bereiche unterteilen:

1. Start (NOP); Steuerung des Algorithmus zu Beginn
2. Vorbedingung (PRECON1 bis PRECON5 - Precondition); Test ob Polynomdivision sinnvoll ist
3. Vorbereitung (LA1 bis LA7 - Lineare Anteil); Vorbereitung der Schleifen
4. Kopier-Schleife (KS1 bis KS4); Kopiert den Dividenden an das Ende der Speicherbelegung, woraus sich am Ende der Berechnung der Rest ergibt
5. Äuÿere Schleife (AS1 bis AS6); Berechnung des Ergebnisses der jeweiligen Stufe und Vorbereitung der inneren Schleife
6. innere Schleife (IS1 bis IS5); Berechnung des Rests in jeder Stufe
7. Ende (FIN1 und FIN2); Legt im Speicher auf MEM[0] einen Wert ab, um den Berechnungserfolg zu erkennen

Die Sprungauswertung geschieht mittels Flags. Dabei werden die zu vergleichenden Operanden von einander subtrahiert. Der Test kann bei > nur auf ZERO erfolgen, da sich die zu vergleichenden Werte langsam angleichen. (Ansonsten müsste auf ZERO und NEGATIV geprüft werden.) Bei ≥ wird auf NEGATIV getestet.

R[5] dient zu Beginn auch als Zwischenspeicher für MEM[1], damit nicht erneut im linearen Teil auf den Bus zugegri en werden muss. Das Gleiche gilt für R[2] und MEM[2].

Es gibt zwei verschiedene Arten von Flags (NEGATIV und ZERO). Daher entstehen bei der Implementierung die Flagregister F1 und F2. Diese sind ausschlieÿlich an den Addierer (ADD) angebunden.

Die Abbildungen 3.8 und 3.9 zeigen die zu implementierenden RT-Folgen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.8.: RT-Folgen (Teil 1)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.9.: RT-Folgen (Teil 2)

Der Versuch strukturelles Pipelining einzuführen, um die Daten für den Dividierer eher zu laden, damit in der äuÿeren Schleife früher mit der Berechnung begonnen werden kann scheitert. Es würden mehr neue Steuerschritte entstehen, sodass der Ablauf nicht schneller verläuft. E zientes Pipelining wird auch durch die indirekte Adressierung und fehlen von Ressourcen behindert. Daher werden keine weiteren Maÿnahmen in dieser Hinsicht eingeleitet.

3.6.2. Buszuordnung

Es ergibt sich die Zuordnung der Bauelemente zu den Bussen wie folgt in den Tabellen 3.5 bis 3.10. Falls nach dem Registernamen noch in Klammern load oder write steht, ist damit gemeint, dass nur über den entsprechenden Bus vom Speicher auf das jeweilige Element geladen bzw. auf das jeweilige Element geschrieben wird. Bei allen anderen Registern wird über den jeweiligen Bus geschrieben und geladen. Von Konstanten wird nur geladen.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.5.: Buszuordnung

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.6.: Buszuordnung

[...]

---

¹ engl. Complementary Metal Oxide Semiconductor engl.

² Electronic Design Automation

³ Register Transfer Level

¹ Engpass bei der Datenübertragung/Abarbeitung

² engl. as soon as possible 3

³ engl. as late as possible