Organizar celdas estándar (notas de un extraño)

Habiendo encontrado el artículo " Destruyendo el monopolio ... ", el autor, como persona, aunque muy lejos de EDA , pero naturalmente inquisitivo, no era demasiado vago para seguir los enlaces y involuntariamente se sorprendió pensando que una de las principales soluciones técnicas es el uso de filas de celdas estándar ( celda estándar diseño): parece bastante controvertido.

Sí, esta disposición es intuitiva, porque escribimos y leemos de manera similar, además, tecnológicamente es simple organizar las celdas en filas, es muy conveniente conectar los buses VDD y GND. Por otro lado, surge un problema combinatorio difícil, es necesario cortar el circuito en piezas lineales y organizar estas piezas de tal manera que (aproximadamente) minimicen la longitud total de las uniones.

Y, por supuesto, surgió la pregunta de si existen soluciones alternativas ... y eso es si ...


Figura 1 filas típicas de celdas estándar ( desde aquí )

Que pasa si

Desde el punto de vista de reducir la longitud total del enlace, sería útil organizar las celdas estándar a lo largo de algunas de las curvas ex barridas : Peano o Hilbert.

Estas curvas consisten en una masa de varios "rincones y grietas", por supuesto, hay una configuración en la que las celdas estándar conectadas están en promedio cerca una de la otra.
O puede servir como una iteración cero para una mayor optimización.


Figura 2 Curva de Hilbert, campos 8X8 y 64X64

1. Las curvas de barrido son similares, lo que encaja bien en el concepto general.
2. Tienen una alta localidad, es decir Los puntos ubicados en algún lugar cercano en la curva son muy probablemente cercanos y en el espacio.
3. Contener una red jerárquicamente organizada de canales.
4. Para el circuito lógico, puede elegir un cuadrado o rectángulo adecuado 1x2,2x1 en el que se coloca en exceso y "moverlo" a lo largo de la curva de barrido (ver Figura 3) para seleccionar la geometría óptima, porque esto es solo un grado de libertad con una función de costo bastante barata .
   
5. Se mantendrá la conveniencia de la conexión de los neumáticos (VDD / GND).
6. ...

Figura 3 Tres piezas de una curva de Hilbert con diferentes turnos.

Entonces

• experimentaremos con la curva de Hilbert
• Experimentaremos en un cuadrado de 64X64 (Figura 3)
• en el paso elemental de la curva puede haber varias celdas y espacios estándar: cuántos y en qué orden es el parámetro del experimento
• todos los pasos elementales están organizados de manera idéntica
• los pasos elementales van con una superposición, es decir Si el paso comienza con una celda estándar, debe haber un espacio al final y viceversa.
• Todos los espacios y celdas estándar son del mismo tamaño: 1X1
• todas las celdas se serializan en algún orden, este orden también es un parámetro
• otro parámetro es el desplazamiento desde el comienzo de la curva (puntos (0,0)), a partir del cual organizaremos las celdas estándar en un cierto orden
  
• las longitudes de enlace entre celdas estándar se calculan de acuerdo con L1 (distancia de Manhattan)
• la suma de las longitudes de todos los bonos es el valor deseado, habiendo determinado la cantidad mínima, encontraremos la ubicación óptima

Y como conejo experimental, tomemos un sumador de 8 bits. Es bastante simple, pero no trivial. Hay muchos elementos y conexiones para sentir los posibles pros y contras. Al mismo tiempo, no hay suficientes para poder experimentar "en la rodilla".

Totalizador

4 es un diagrama esquemático de un sumador completo de un solo bit


Figura 5 Entonces, ve esta utilidad de gráficos Neato de graphwiz


6 sumador firmado de 8 bits, tomado aquí

Pero solo trabajaremos con enteros, sin el indicador de error W.


Fig. 7 Entonces, el sumador de 8 bits ve la utilidad de puntos de graphwiz.

Parece un baile de cisnes pequeños.


La figura 8 es el mismo gráfico después de la optimización usando neato.

Experimento 1

• paso elemental de la curva de Hilbert - (pase, celda, celda, pase)
• gráficos de vértices (celdas unitarias) ordenados alfabéticamente

Fig.9 en X - desplazamiento desde el principio, en Y - la longitud de todos los caminos

La distancia mínima (la primera de) en un cambio de 207 (La longitud total de todos los enlaces es 1968), veamos cómo se ve esta disposición óptima.


La Figura 10 es el gráfico óptimo para el turno 207, no se ve muy bien.

Experimento 2

• paso elemental de la curva de Hilbert - (pase, celda, celda, pase)
• vértices del gráfico (celdas unitarias) en el orden natural (como se muestra en la descripción del gráfico, consulte la descripción del gráfico anterior) -

11 en X - el cambio desde el principio, en Y - la longitud de todos los caminos


Fig. 12 gráfico óptimo para cizalla 11 longitud 750

Experimento 3

• paso elemental de la curva de Hilbert - (pase, celda, celda, pase)
• El orden de los vértices se determina atravesando el ancho del gráfico, vértices sin enlaces al principio de la lista, el fin de semana al final

Fig.13 en X - cambio desde el principio, en Y - la longitud de todos los caminos


Fig. 14 Disposición óptima - turno 3, longitud total 1451
Poner todos los vértices de entrada al principio y la salida al final no fue muy buena
una idea

Experimento 4

• el paso elemental de la curva de Hilbert - (pase, celda, celda) ¡Sic!
• el orden de vértices es natural, como en el experimento 2

Fig.15 en X - desplazamiento desde el principio, en Y - la longitud de todos los caminos


Fig. 16 Disposición óptima - turno 10, longitud total 503

Experimento 5

Necesitamos hacer algo con IO, los definimos en el procesamiento posterior, es decir para cada turno
construir un arreglo sin vértices IO, luego construir un marco de extensión absorbente alrededor del gráfico, aplicar vértices IO al punto desocupado más cercano del marco y calcular la longitud final

• paso elemental de la curva de Hilbert - (omitir, celda, celda)
• el orden de los vértices se determina visualizando en ancho, pero sin vértices IO

Fig.17 en X es el cambio desde el principio, en Y es la longitud de todos los caminos


Fig. 18 La ubicación óptima es el turno 607, la longitud total de 484, el promedio de 3.33793

Se ve bien, pero ¿qué pasa si optimizamos no la longitud total de las rutas, sino su suma con el área del rectángulo ocupado? Sus dimensiones son diferentes, por lo que asumiremos que no calculamos la longitud del camino, sino el área debajo de los caminos.

Experimento 6

Los parámetros son los mismos que en el experimento 5, optimizamos el área.


Fig.19 en X - cambio desde el principio, en Y - la longitud de todos los caminos


Fig. 20 Disposición óptima: turno 966, longitud total 639, promedio 3.30345

El rectángulo resultó bastante alargado. Pero, ¿qué pasa si consideramos no el área del rectángulo, sino el cuadrado de la hipotenusa, empujándonos a formas más cuadradas?

Experimento 7

Los parámetros son los mismos que en el experimento 5, optimizamos el cuadrado de la hipotenusa.


Fig.21 en X es el cambio desde el principio, en Y es la longitud de todos los caminos


Fig. 22 Disposición óptima: desplazamiento 70, longitud total 702, promedio 3.46207

Experimento 8

• paso elemental de la curva de Hilbert - (celda, saltar) ¡Sic!
• el orden de los vértices se determina visualizando en ancho, pero sin vértices IO

Suponemos que el costo de caminar en Y es el doble que en X, esto está más cerca de la realidad.

Fig.23 en X es el cambio desde el principio, en Y es la longitud de todos los caminos


Fig. 24 Disposición óptima - turno 344, longitud total 650, promedio 3.8

Conclusiones

Preliminar "Elección del editor" - Experimento 6.

Sería bueno organizar los vértices IO, pero esto requiere una pista desde un lado,
donde exactamente (dirección) debe ubicarse esta clase de vértices.

Pero primero me gustaría escuchar la opinión de los expertos.

PD : gracias a YuriPanchul y andy_p por la falta de una reacción refleja negativa.

UPD (11/02/2019): agregado "experimento 8", donde las celdas estándar se encuentran en los nodos de la curva de Hilbert, es decir estrictamente en un enrejado cuadrado. Además, por un lado, se combinan en filas tradicionales y, por otro lado, se ubican a lo largo de la curva de Hilbert.