La colocación es un paso esencial en la automatización del diseño electrónico : la parte del flujo de diseño físico que asigna ubicaciones exactas para varios componentes del circuito dentro del área central del chip. Una asignación de ubicación inferior no solo afectará el rendimiento del chip , sino que también podría hacer que no se pueda fabricar al producir una longitud de cable excesiva, que está más allá de los recursos de enrutamiento disponibles . En consecuencia, un colocador debe realizar la asignación mientras optimiza una serie de objetivos para garantizar que un circuito cumpla con sus demandas de rendimiento. En conjunto, los pasos de colocación y enrutamiento del diseño de CI se conocen como colocación y ruta .
Un colocador toma una lista de conexiones de circuitos sintetizados dada junto con una biblioteca de tecnología y produce un diseño de colocación válido. El diseño se optimiza de acuerdo con los objetivos antes mencionados y está listo para el redimensionamiento de celdas y el almacenamiento en búfer, un paso esencial para la satisfacción de la integridad de la señal y el tiempo . A continuación, se realiza la síntesis del árbol de reloj y el enrutamiento , lo que completa el proceso de diseño físico. En muchos casos, partes o todo el flujo de diseño físico se iteran varias veces hasta que se logra el cierre del diseño .
En el caso de los circuitos integrados de aplicación específica , o ASIC, el área de diseño del núcleo del chip comprende una serie de filas de altura fija, con algún espacio o sin espacio entre ellas. Cada fila consta de una serie de sitios que pueden ser ocupados por los componentes del circuito. Un sitio libre es un sitio que no está ocupado por ningún componente. Los componentes del circuito son celdas estándar, macrobloques o pads de E/S. [1] Las celdas estándar tienen una altura fija igual a la altura de una fila, pero tienen anchos variables. El ancho de una celda es un número entero de sitios.
Por otro lado, los bloques suelen ser más grandes que las celdas y tienen alturas variables que pueden extenderse por varias filas. [1] Algunos bloques pueden tener ubicaciones preasignadas (por ejemplo, de un proceso de planificación de piso anterior), lo que limita la tarea del colocador a asignar ubicaciones solo para las celdas. En este caso, los bloques suelen tener referencias fijas. Alternativamente, algunos o todos los bloques pueden no tener ubicaciones preasignadas. En este caso, deben colocarse con las celdas en lo que comúnmente se conoce como colocación en modo mixto.
Además de los ASIC, la colocación conserva su importancia primordial en las estructuras de matriz de puertas, como las matrices de puertas programables en campo (FPGA). Aquí, los transistores prefabricados suelen estar dispuestos en filas (o "matrices") que están separadas por canales de enrutamiento. [2] La colocación asigna los subcircuitos del circuito a bloques lógicos FPGA programables de una manera que garantiza la finalización de la etapa posterior de enrutamiento.
La colocación se formula como una optimización restringida . En particular, el ciclo de reloj de un chip está determinado por el retraso de su ruta más larga, generalmente denominada ruta crítica. Dada una especificación de rendimiento, un colocador debe asegurarse de que no exista ninguna ruta con un retraso que exceda el retraso máximo especificado.
Otras limitaciones clave incluyen:
Generalmente existen múltiples objetivos de optimización, entre ellos:
Además, es deseable finalizar el proceso de colocación rápidamente.
La longitud total del cable es típicamente el objetivo principal de la mayoría de los colocadores existentes y sirve como precursor de otras optimizaciones porque, por ejemplo, la potencia y el retardo tienden a crecer con la longitud del cable. La longitud total del cable determina la demanda de enrutamiento y si puede ser satisfecha por el suministro de enrutamiento definido por las vías de enrutamiento disponibles. Sin embargo, hacer cables muy cortos a veces lleva a que la demanda de enrutamiento local exceda el suministro de enrutamiento local. Tales situaciones a menudo requieren desvíos de enrutamiento, que aumentan las longitudes de los cables y los retrasos de la señal. Por lo tanto, después de la optimización preliminar de la longitud total del cable, también es importante manejar la congestión del enrutamiento.
La minimización de potencia generalmente toma en cuenta los cables con mayores factores de actividad de conmutación y asigna mayor prioridad a hacerlos más cortos. Cuando se colocan muchos componentes "calientes" cerca, puede surgir un punto caliente y generar gradientes de temperatura perjudiciales. En tales casos, los componentes pueden distribuirse.
La colocación se divide en colocación global y colocación detallada. La colocación global introduce cambios drásticos al distribuir todas las instancias en ubicaciones adecuadas en la escala global, permitiendo superposiciones menores. La colocación detallada desplaza cada instancia a una ubicación legal cercana con un cambio de diseño muy moderado. La colocación y la calidad general del diseño dependen en gran medida del rendimiento de la colocación global.
Las primeras técnicas para la colocación de circuitos integrados se pueden clasificar como optimización combinatoria . Para diseños de CI con miles o decenas de miles de componentes, las metodologías de recocido simulado [3] como TimberWolf [4] exhiben los mejores resultados. Cuando los diseños de CI crecieron a millones de componentes, la colocación aprovechó la partición de hipergrafos [5] utilizando marcos de partición anidada como Capo. [6] Los métodos combinatorios previenen directamente las superposiciones de componentes pero tienen dificultades con la optimización de interconexión a gran escala. Por lo general, son estocásticos y pueden producir resultados muy diferentes para la misma entrada cuando se lanzan varias veces.
Los métodos analíticos para el modelo de posicionamiento global interconectan la longitud mediante una función continua y minimizan esta función directamente sujeta a las restricciones de densidad de componentes. Estos métodos se ejecutan más rápido y escalan mejor que los métodos combinatorios, pero no evitan las superposiciones de componentes y deben posprocesarse mediante métodos combinatorios para lograr un posicionamiento detallado. El posicionamiento cuadrático es un método analítico temprano que modela la longitud de interconexión mediante una función cuadrática y utiliza técnicas de optimización cuadrática de alto rendimiento. Cuando se desarrolló, demostró una calidad competitiva de resultados y también estabilidad, a diferencia de los métodos combinatorios. GORDIAN [7] formula el costo de la longitud del cable como una función cuadrática mientras aún separa las celdas mediante particiones recursivas. El algoritmo [8] modela la densidad de posicionamiento como un término lineal en la función de costo cuadrático y resuelve el problema de posicionamiento mediante programación cuadrática pura. Una mejora común es ponderar cada red por la inversa de su longitud en la iteración anterior. Siempre que el proceso converja, esto minimiza un objetivo lineal en la longitud del cable. [9] La mayoría de los colocadores cuadráticos modernos (KraftWerk, [10] FastPlace, [11] SimPL [12] ) siguen este marco, cada uno con diferentes heurísticas sobre cómo determinar la fuerza de densidad lineal.
Modelos de posicionamiento no lineales de longitud de cable mediante funciones exponenciales (no lineales) y densidad mediante funciones cuadráticas locales por partes, con el fin de lograr una mayor precisión y, por lo tanto, una mejora de la calidad. [13] Los trabajos académicos de seguimiento incluyen APlace [14] y NTUplace. [15]
ePlace [16] es un algoritmo de posicionamiento global de última generación. Separa las instancias mediante la simulación de un campo electrostático, lo que minimiza la sobrecarga de calidad y, por lo tanto, logra un buen rendimiento.
En 2021, Google Brain informó de buenos resultados del uso de técnicas de IA (en particular, aprendizaje por refuerzo) para el problema de la colocación. [17] Sin embargo, este resultado es bastante controvertido, [18] [19] [20] ya que el artículo no contiene comparaciones directas con colocadores existentes y es difícil de replicar debido al contenido exclusivo. Al menos un comentario inicialmente favorable se ha retractado tras una revisión más profunda. [21]
{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )