Organisation des cellules standard (notes d'un étranger)

Après être tombé sur l'article " Détruire le monopole ... ", l'auteur, en tant que personne, bien que très loin de l' EDA , mais naturellement curieux, n'était pas trop paresseux pour suivre les liens et s'est involontairement surpris en pensant que l'une des principales solutions techniques était l'utilisation de rangées de cellules standard ( cellule standard mise en page) - semble assez controversé.

Oui, cet arrangement est intuitif, car nous écrivons et lisons de manière similaire, en plus, il est technologiquement simple d'organiser les cellules en rangées, il est si pratique de connecter les bus VDD et GND. D'autre part, un problème combinatoire complexe se pose, il est nécessaire de couper le circuit en pièces linéaires et de disposer ces pièces de manière à (grossièrement) minimiser la longueur totale des joints.

Et bien sûr, la question s'est posée de savoir s'il existe des solutions alternatives ... et si ...


Figure 1 lignes typiques de cellules standard ( d'ici )

Et si

Du point de vue de la réduction de la longueur totale des liaisons, il serait utile de disposer des cellules standard le long de certaines courbes ex de balayage : Peano ou Hilbert.

Ces courbes sont constituées d'une masse de divers «coins et recoins», il y a certainement une configuration dans laquelle les cellules standard connectées sont en moyenne proches les unes des autres.
Ou il peut servir d'itération nulle pour une optimisation supplémentaire.


Figure 2 Courbe de Hilbert, champs 8X8 et 64X64

1. Les courbes de balayage sont auto-similaires, ce qui s'intègre bien dans le concept global.
2. Ils ont une localité élevée, c'est-à-dire les points situés quelque part à proximité sur la courbe sont très probablement à proximité et dans l'espace.
3. Contiennent un réseau de canaux organisé hiérarchiquement.
4. Pour le circuit logique, vous pouvez choisir un carré ou un rectangle 1x2,2x1 approprié dans lequel il est placé en excès et le "déplacer" le long de la courbe de balayage (voir figure 3) pour sélectionner la géométrie optimale, car il ne s'agit que d'un degré de liberté avec une fonction de coût plutôt bon marché. .
   
5. La commodité de la connexion des pneus (VDD / GND) restera.
6. ...

Figure 3 Trois morceaux d'une courbe de Hilbert avec différents décalages.

Donc:

• nous expérimenterons la courbe de Hilbert
• nous allons expérimenter dans un carré 64X64 (figure 3)
• dans l'étape élémentaire de la courbe, il peut y avoir plusieurs cellules et espaces standard - combien et dans quel ordre est le paramètre de l'expérience
• toutes les étapes élémentaires sont disposées de manière identique
• les étapes élémentaires vont avec un chevauchement, c'est-à-dire si l'étape commence par une cellule standard, il doit y avoir un espace à la fin de celle-ci, et vice versa
• tous les espaces et cellules standard sont de la même taille - 1X1
• toutes les cellules sont sérialisées dans un certain ordre, cet ordre est également un paramètre
• un autre paramètre est le décalage depuis le début de la courbe (points (0,0)), à partir duquel nous organiserons les cellules standard dans un certain ordre
  
• les longueurs de liaison entre les cellules standard sont calculées selon L1 (distance de Manhattan)
• la somme des longueurs de toutes les obligations est la valeur souhaitée, après avoir déterminé le montant minimum, nous trouverons l'emplacement optimal

Et en tant que lapin expérimental, prenons un additionneur 8 bits. C'est assez simple, mais pas anodin. Il y a beaucoup d'éléments et de connexions pour ressentir les avantages et les inconvénients potentiels. En même temps, il n'y en a pas assez pour pouvoir expérimenter «sur le genou».

Totalisateur

4 est un diagramme schématique d'un additionneur complet à un seul bit


La figure 5 voit donc cet utilitaire graphique Neato de graphwiz


6 additionneur signé 8 bits, pris ici

Mais nous ne travaillerons qu'avec des entiers, sans le drapeau d'erreur W.


Fig. 7 Ainsi, l'additionneur 8 bits voit l'utilité de point de graphwiz.

Cela ressemble à une danse de petits cygnes.


La figure 8 est le même graphique après optimisation en utilisant neato.

Expérience 1

• pas élémentaire de la courbe de Hilbert - (passe, cellule, cellule, passe)
• sommets du graphique (cellules unitaires) triés par ordre alphabétique

Fig.9 sur X - décalage depuis le début, sur Y - la longueur de tous les chemins

La distance minimale (la première) à un décalage de 207 (La longueur totale de toutes les liaisons est 1968), voyons à quoi ressemble cet arrangement optimal.


La figure 10 est le graphique optimal pour le shift 207, il n'a pas l'air très joli.

Expérience 2

• pas élémentaire de la courbe de Hilbert - (passe, cellule, cellule, passe)
• sommets du graphique (cellules unitaires) dans l'ordre naturel (comme indiqué dans la description du graphique, voir la description du graphique ci-dessus) -

11 sur X - le décalage depuis le début, sur Y - la longueur de tous les chemins


Fig.12 graphique optimal pour cisaillement 11 longueur 750

Expérience 3

• pas élémentaire de la courbe de Hilbert - (passe, cellule, cellule, passe)
• l'ordre des sommets est déterminé en parcourant la largeur du graphe, des sommets sans liens au début de la liste, le week-end à la fin

Fig.13 sur X - décalage depuis le début, sur Y - la longueur de tous les chemins


Fig.14 Disposition optimale - décalage 3, longueur totale 1451
Mettez tous les sommets d'entrée au début et la sortie à la fin n'était pas très bonne
une idée.

Expérience 4

• le pas élémentaire de la courbe de Hilbert - (passe, cellule, cellule) Sic!
• l'ordre des sommets est naturel, comme dans l'expérience 2

Fig.15 sur X - décalage depuis le début, sur Y - la longueur de tous les chemins


Fig.16 Disposition optimale - décalage 10, longueur totale 503

Expérience 5

Nous devons faire quelque chose avec IO, nous les définissons en post-traitement, c'est-à-dire pour chaque quart de travail
construire un arrangement sans sommets IO, puis construire un cadre d'étendue absorbante autour du graphique, appliquer des sommets IO au point inoccupé le plus proche du cadre et calculer la longueur finale

• pas élémentaire de la courbe de Hilbert - (saut, cellule, cellule)
• l'ordre des sommets est déterminé par la visualisation en largeur, mais sans sommets IO

Fig.17 sur X est le décalage depuis le début, sur Y est la longueur de tous les chemins


Fig.18 L'emplacement optimal est le quart de travail 607, la longueur totale de 484, la moyenne de 3.33793

Il a l'air bien, mais que se passe-t-il si nous optimisons non pas la longueur totale des chemins, mais sa somme avec l'aire du rectangle occupé. Leurs dimensions sont différentes, nous supposerons donc que nous calculons non pas la longueur du chemin, mais la zone sous les chemins.

Expérience 6

Les paramètres sont les mêmes que dans l'expérience 5, nous optimisons la zone.


Fig.19 sur X - décalage depuis le début, sur Y - la longueur de tous les chemins


Fig.20 Disposition optimale - décalage 966, longueur totale 639, moyenne 3,30345

Le rectangle s'est avéré assez allongé. Mais que se passe-t-il si nous considérons non pas l'aire du rectangle, mais le carré de l'hypoténuse, nous poussant vers des formes plus carrées?

Expérience 7

Les paramètres sont les mêmes que dans l'expérience 5, nous optimisons le carré de l'hypoténuse.


Fig.21 sur X est le décalage depuis le début, sur Y est la longueur de tous les chemins


Fig.22 Disposition optimale - décalage 70, longueur totale 702, moyenne 3,46207

Expérience 8

• pas élémentaire de la courbe de Hilbert - (cellule, sauter) Sic!
• l'ordre des sommets est déterminé par la visualisation en largeur, mais sans sommets IO

Nous supposons que le coût de la marche en Y est deux fois plus élevé qu'en X, c'est plus proche de la réalité.

Fig.23 sur X est le décalage depuis le début, sur Y est la longueur de tous les chemins


Fig.24 Disposition optimale - décalage 344, longueur totale 650, moyenne 3,8

Conclusions

«Choix des rédacteurs» préliminaire - Expérience 6.

Ce serait bien d'organiser les sommets d'E / S, mais cela nécessite une indication latérale,
où exactement (direction) cette classe de sommets doit être située.

Mais je voudrais d'abord entendre l'avis d'experts.

PS : merci à YuriPanchul et andy_p pour l'absence de réaction négative réflexe.

UPD (11/02/2019): ajout de «l'expérience 8», où les cellules standard sont situées aux nœuds de la courbe de Hilbert, c'est-à-dire strictement sur un réseau carré. De plus, d'une part, ils sont combinés en rangées traditionnelles et, d'autre part, ils sont situés le long de la courbe de Hilbert.