Anordnen von Standardzellen (Notizen eines Außenstehenden)

Nachdem der Autor auf den Artikel „ Zerstörung des Monopols ... “ gestoßen war , war er als Person, obwohl sehr weit von EDA entfernt , aber natürlich neugierig, nicht zu faul, um den Links zu folgen, und ertappte sich unwillkürlich bei dem Gedanken, dass eine der wichtigsten technischen Lösungen die Verwendung von Reihen von Standardzellen ( Standardzelle) ist Layout) - sieht ziemlich kontrovers aus.

Ja, diese Anordnung ist intuitiv, da wir auf ähnliche Weise schreiben und lesen. Außerdem ist es technologisch einfach, Zellen in Reihen anzuordnen, und es ist so bequem, VDD- und GND-Busse anzuschließen. Andererseits tritt ein komplexes kombinatorisches Problem auf, es ist notwendig, die Schaltung in lineare Teile zu schneiden und diese Teile so anzuordnen, dass die Gesamtlänge der Verbindungen (grob) minimiert wird.

Und natürlich stellte sich die Frage, ob es alternative Lösungen gibt ... was ist, wenn ...


Abbildung 1 typische Reihen von Standardzellen ( von hier )

Was wäre wenn

Unter dem Gesichtspunkt der Verringerung der Gesamtbindungslänge wäre es nützlich, Standardzellen entlang einiger der geschwungenen Ex- Kurven anzuordnen: Peano oder Hilbert.

Diese Kurven bestehen aus einer Masse verschiedener „Ecken und Winkel“, sicher gibt es eine Konfiguration, in der die verbundenen Standardzellen im Durchschnitt nahe beieinander liegen.
Oder es kann als Null-Iteration für die weitere Optimierung dienen.


Abbildung 2 Hilbert-Kurve, Felder 8X8 und 64X64

1. Die geschwungenen Kurven sind selbstähnlich, was gut in das Gesamtkonzept passt.
2. Sie haben eine hohe Lokalität, d.h. Punkte, die sich irgendwo in der Nähe der Kurve befinden, befinden sich höchstwahrscheinlich in der Nähe und im Weltraum.
3. Enthält ein hierarchisch organisiertes Kanalnetz.
4. Für die logische Schaltung können Sie ein geeignetes Quadrat oder Rechteck 1x2,2x1 auswählen, in dem es im Überschuss platziert ist, und es entlang der Wischkurve "bewegen" (siehe Abbildung 3), um die optimale Geometrie auszuwählen, da dies nur ein Freiheitsgrad mit einer relativ günstigen Kostenfunktion ist .
   
5. Der Anschluss von Reifen (VDD / GND) bleibt bequem.
6. ...

Abbildung 3 Drei Teile einer Hilbert-Kurve mit unterschiedlichen Verschiebungen.

Also:

• Wir werden mit der Hilbert-Kurve experimentieren
• Wir werden in einem Quadrat 64X64 experimentieren (Abbildung 3)
• Im Elementarschritt der Kurve können mehrere Standardzellen und -räume vorhanden sein - wie viele und in welcher Reihenfolge ist der Parameter des Experiments
• Alle Elementarschritte sind identisch angeordnet
• Elementarschritte gehen mit einer Überlappung einher, d.h. Wenn der Schritt mit einer Standardzelle beginnt, muss am Ende ein Leerzeichen stehen und umgekehrt
• Alle Leerzeichen und Standardzellen haben die gleiche Größe - 1X1
• Alle Zellen werden in einer bestimmten Reihenfolge serialisiert. Diese Reihenfolge ist auch ein Parameter
• Ein weiterer Parameter ist die Verschiebung vom Beginn der Kurve (Punkte (0,0)), ab der wir die Standardzellen in einer bestimmten Reihenfolge anordnen
  
• Bindungslängen zwischen Standardzellen werden gemäß L1 (Manhattan-Abstand) berechnet.
• Die Summe der Längen aller Anleihen ist der gewünschte Wert. Nachdem wir den Mindestbetrag bestimmt haben, finden wir den optimalen Ort

Und als experimentelles Kaninchen nehmen wir einen 8-Bit-Addierer. Es ist einfach genug, aber nicht trivial. Es gibt viele Elemente und Zusammenhänge, um die möglichen Vor- und Nachteile zu spüren. Gleichzeitig gibt es nicht genug davon, um „am Knie“ experimentieren zu können.

Summierer

Fig. 4 ist ein schematisches Diagramm eines vollständigen Einzelbitaddierers


Abbildung 5 So sieht dieses Grafikdienstprogramm Neato von graphwiz


6 8-Bit-Addierer mit Vorzeichen, hier aufgenommen

Wir werden jedoch nur mit ganzen Zahlen ohne das Fehlerflag W arbeiten.


Abb. 7 Der 8-Bit-Addierer sieht also das Punktdienstprogramm von graphwiz.

Es sieht aus wie ein Tanz kleiner Schwäne.


Fig. 8 ist das gleiche Diagramm nach der Optimierung unter Verwendung von Neato.

Versuch 1

• Elementarschritt der Hilbert-Kurve - (Pass, Zelle, Zelle, Pass)
• Diagrammscheitelpunkte (Einheitszellen) alphabetisch sortiert

Abb.9 auf X - Verschiebung von Anfang an, auf Y - die Länge aller Pfade

Der Mindestabstand (der erste von) bei einer Verschiebung von 207 (die Gesamtlänge aller Anleihen beträgt 1968). Lassen Sie uns sehen, wie diese optimale Anordnung aussieht.


Fig. 10 ist das optimale Diagramm für die Verschiebung 207, es sieht nicht sehr schön aus.

Experiment 2

• Elementarschritt der Hilbert-Kurve - (Pass, Zelle, Zelle, Pass)
• Eckpunkte des Diagramms (Einheitszellen) in der natürlichen Reihenfolge (wie in der Beschreibung des Diagramms angegeben, siehe Beschreibung des Diagramms oben) -

11 auf X - die Verschiebung von Anfang an, auf Y - die Länge aller Pfade


Fig. 12 optimales Diagramm für Scherlänge 11 750

Experiment 3

• Elementarschritt der Hilbert-Kurve - (Pass, Zelle, Zelle, Pass)
• Die Reihenfolge der Scheitelpunkte wird durch Durchlaufen der Breite des Diagramms bestimmt. Scheitelpunkte ohne Verknüpfungen am Anfang der Liste und am Wochenende am Ende

Abb.13 auf X - Verschiebung von Anfang an, auf Y - Länge aller Pfade


Abb. 14 Optimale Anordnung - Verschiebung 3, Gesamtlänge 1451
Setzen Sie alle Eingabescheitelpunkte am Anfang und die Ausgabe am Ende war nicht sehr gut
eine Idee.

Experiment 4

• der elementare Schritt der Hilbert-Kurve - (Pass, Zelle, Zelle) Sic!
• Die Scheitelpunktreihenfolge ist natürlich, wie in Experiment 2

Abb.15 auf X - Verschiebung von Anfang an, auf Y - Länge aller Pfade


Abb. 16 Optimale Anordnung - Verschiebung 10, Gesamtlänge 503

Experiment 5

Wir müssen etwas mit E / A tun, wir definieren sie in der Nachbearbeitung, d. H. für jede Schicht
Erstellen Sie eine Anordnung ohne E / A-Scheitelpunkte, erstellen Sie dann einen Rahmen mit absorbierender Ausdehnung um den Graphen, wenden Sie E / A-Scheitelpunkte auf den nächsten nicht besetzten Punkt des Rahmens an und berechnen Sie die endgültige Länge

• Elementarschritt der Hilbert-Kurve - (überspringen, Zelle, Zelle)
• Die Reihenfolge der Scheitelpunkte wird durch Anzeigen in der Breite bestimmt, jedoch ohne E / A-Scheitelpunkte

Fig. 17 auf X ist die Verschiebung von Anfang an, auf Y ist die Länge aller Pfade


Abb. 18 Der optimale Ort ist die Verschiebung 607, die Gesamtlänge von 484, der Durchschnitt von 3,33793

Es sieht gut aus, aber was ist, wenn wir nicht die Gesamtlänge der Pfade optimieren, sondern ihre Summe mit der Fläche des belegten Rechtecks. Ihre Dimensionen sind unterschiedlich, daher nehmen wir an, dass wir nicht die Länge des Pfades berechnen, sondern die Fläche unter den Pfaden.

Experiment 6

Die Parameter sind die gleichen wie in Experiment 5, wir optimieren die Fläche.


Abb.19 auf X - Verschiebung von Anfang an, auf Y - Länge aller Pfade


Abb. 20 Optimale Anordnung - Verschiebung 966, Gesamtlänge 639, Durchschnitt 3.30345

Das Rechteck war ziemlich länglich. Aber was ist, wenn wir nicht die Fläche des Rechtecks ​​betrachten, sondern das Quadrat der Hypotenuse, was uns zu mehr quadratischen Formen treibt?

Experiment 7

Die Parameter sind die gleichen wie in Experiment 5, wir optimieren das Quadrat der Hypotenuse.


Fig. 21 auf X ist die Verschiebung von Anfang an, auf Y ist die Länge aller Pfade


Abb. 22 Optimale Anordnung - Verschiebung 70, Gesamtlänge 702, Durchschnitt 3,46207

Experiment 8

• Elementarschritt der Hilbert-Kurve - (Zelle, überspringen) Sic!
• Die Reihenfolge der Scheitelpunkte wird durch Anzeigen in der Breite bestimmt, jedoch ohne E / A-Scheitelpunkte

Wir gehen davon aus, dass die Kosten für das Gehen in Y doppelt so hoch sind wie in X, dies ist näher an der Realität.

Fig. 23 auf X ist die Verschiebung von Anfang an, auf Y ist die Länge aller Pfade


Abb. 24 Optimale Anordnung - Verschiebung 344, Gesamtlänge 650, Durchschnitt 3,8

Schlussfolgerungen

Vorläufige „Wahl der Redaktion“ - Experiment 6.

Es wäre schön, die E / A-Eckpunkte anzuordnen, aber dies erfordert einen Hinweis von der Seite.
Wo genau (Richtung) sollte sich diese Klasse von Eckpunkten befinden?

Aber zuerst möchte ich die Meinung von Experten hören.

PS : Danke an YuriPanchul und andy_p für das Fehlen einer reflexnegativen Reaktion.

UPD (11/02/2019): "Experiment 8" hinzugefügt, wobei sich die Standardzellen an den Knoten der Hilbert-Kurve befinden, d. H. streng auf einem quadratischen Gitter. Darüber hinaus werden sie einerseits zu traditionellen Reihen zusammengefasst und andererseits entlang der Hilbert-Kurve angeordnet.