La ubicació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 sólo afectará el rendimiento del chip sino que también podría hacerlo no fabricable 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 tarea mientras optimiza una serie de objetivos para garantizar que un circuito cumpla con sus demandas de rendimiento. En conjunto, los pasos de ubicación y enrutamiento del diseño de circuitos integrados se conocen como lugar y ruta .
Un colocador toma una lista de red de circuitos sintetizada determinada junto con una biblioteca de tecnología y produce un diseño de ubicación válido. El diseño está optimizado de acuerdo con los objetivos antes mencionados y está listo para cambiar el tamaño y el almacenamiento en búfer de la celda, un paso esencial para satisfacer la sincronización y la integridad de la señal . Siguen la síntesis del árbol de reloj y el enrutamiento , completando el proceso de diseño físico. En muchos casos, partes o la totalidad del flujo de diseño físico se repiten 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 poco o ningún espacio entre ellas. Cada fila consta de una serie de sitios que pueden ser ocupados por los componentes del circuito. Un sitio gratuito 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 abarcar varias filas. [1] Algunos bloques pueden tener ubicaciones preasignadas, por ejemplo, a partir 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 denominarse bloques fijos. Alternativamente, es posible que algunos o todos los bloques no tengan ubicaciones preasignadas. En este caso, deben colocarse junto con las celdas en lo que comúnmente se conoce como colocación en modo mixto.
Además de los ASIC, la ubicación conserva su importancia primordial en las estructuras de matrices de puertas, como las matrices de puertas programables en campo (FPGA). En este caso, los transistores prefabricados suelen estar dispuestos en filas (o "conjuntos") que están separados por canales de enrutamiento. [2] La ubicació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 ubicación se formula como 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, que incluyen:
Además, es deseable finalizar rápidamente el proceso de colocación.
La longitud total del cable suele ser 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, acortar mucho los cables a veces hace que la demanda de enrutamiento local supere la oferta de enrutamiento local. Estas situaciones a menudo requieren desvíos de ruta, lo que aumenta la longitud de los cables y los retrasos en las señales. Por lo tanto, después de la optimización preliminar de la longitud total del cable, también es importante gestionar la congestión del enrutamiento.
La minimización de energía generalmente toma nota de 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 provocar gradientes de temperatura perjudiciales. En tales casos, los componentes pueden estar esparcidos.
La ubicación se divide en ubicación global y ubicación detallada. La ubicación global introduce cambios dramáticos al distribuir todas las instancias en ubicaciones apropiadas en la escala global, permitiéndose superposiciones menores. La ubicación detallada traslada cada instancia a una ubicación legal cercana con un cambio de diseño muy moderado. La ubicación y la calidad general del diseño dependen en gran medida del rendimiento de la ubicación global.
Las primeras técnicas para la colocación de circuitos integrados pueden clasificarse como optimización combinatoria . Para diseños de circuitos integrados con miles o decenas de miles de componentes, las metodologías de recocido simulado [3] como TimberWolf [4] muestran los mejores resultados. Cuando los diseños de circuitos integrados crecieron hasta llegar a millones de componentes, la ubicación aprovechó la partición de hipergráficos [5] utilizando marcos de partición anidados como Capo. [6] Los métodos combinatorios evitan directamente la superposición de componentes, pero luchan con la optimización de interconexiones 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 ubicación global interconectan la longitud mediante una función continua y minimizan esta función directamente sujeta a 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 la superposición de componentes y deben posprocesarse mediante métodos combinatorios para una ubicación detallada.La colocación cuadrática 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 y al mismo tiempo separa las células mediante una partición recursiva. El algoritmo [8] modela la densidad de colocación como un término lineal en la función de costo cuadrática y resuelve el problema de colocación 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.
La colocación no lineal modela la longitud del cable mediante funciones exponenciales (no lineales) y la densidad mediante funciones cuadráticas locales por partes, para lograr una mayor precisión y, por lo tanto, una mejora de la calidad. [13] El trabajo académico de seguimiento incluye APlace [14] y NTUplace. [15]
ePlace [16] es un algoritmo de colocación global de última generación. Separa las instancias simulando un campo electrostático, lo que minimiza los gastos generales de calidad y logra un buen rendimiento.
En 2021, Google Brain informó buenos resultados del uso de técnicas de inteligencia artificial (en particular, aprendizaje por refuerzo) para el problema de ubicación. [17] Sin embargo, este resultado es bastante controvertido, [18] [19] [20] ya que el documento no contiene comparaciones directas con los colocadores existentes y es difícil de replicar debido al contenido patentado. Al menos un comentario inicialmente favorable ha sido retractado tras una revisión adicional. [21]
{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite conference}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite conference}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite conference}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite conference}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )