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 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 IC se conocen como lugar y ruta .
Un placer toma una lista de red de circuitos sintetizados dada junto con una biblioteca de tecnología y produce un diseño de ubicación válido. El diseño se optimiza de acuerdo con los objetivos antes mencionados y está listo para el cambio de tamaño de la celda y el almacenamiento en búfer, un paso esencial para la satisfacción de la integridad de la señal y la sincronización . Sigue la síntesis del árbol de reloj y el enrutamiento , completando el proceso de diseño físico. En muchos casos, partes o todo el 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 específicos de la aplicación , o ASIC, el área de disposición del núcleo del chip comprende varias filas de altura fija, con algo de espacio o sin espacio entre ellas. Cada fila consta de varios 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 almohadillas de E / S. 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 estirar varias filas. Algunos bloques pueden tener ubicaciones asignadas previamente, 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 se denominan normalmente bloques fijos. Como alternativa, es posible que algunos o todos los bloques no tengan ubicaciones asignadas previamente. En este caso, deben colocarse con las celdas en lo que comúnmente se conoce como ubicación de modo mixto.
Además de los ASIC, la ubicación conserva su importancia primordial en las estructuras de arreglos de puertas, como los arreglos de puertas programables en campo (FPGA). En FPGA, la ubicación mapea los subcircuitos del circuito en bloques lógicos FPGA programables de una manera que garantiza la finalización de la etapa posterior de enrutamiento.
Objetivos y limitaciones
La colocación se suele formular como un problema de optimización restringida . La restricción es eliminar las superposiciones entre todas las instancias de la lista de conexiones. El objetivo de optimización puede ser múltiple, que normalmente incluye:
- Longitud total del cable : Minimizar la longitud total del cable, o la suma de la longitud de todos los cables en el diseño, es el objetivo principal de la mayoría de los colocadores existentes. Esto no solo ayuda a minimizar el tamaño del chip y, por lo tanto, el costo, sino que también minimiza la potencia y el retraso, que son proporcionales a la longitud del cable (esto supone que los cables largos tienen un búfer adicional insertado; todos los flujos de diseño moderno hacen esto).
- Sincronización : el ciclo de reloj de un chip está determinado por el retraso de su ruta más larga, generalmente conocida como ruta crítica. Dada una especificación de rendimiento, un placer debe asegurarse de que no exista una ruta con un retraso que exceda el retraso máximo especificado.
- Congestión : si bien es necesario minimizar la longitud de cable total para cumplir con los recursos de enrutamiento totales, también es necesario cumplir con los recursos de enrutamiento dentro de varias regiones locales del área central del chip. Una región congestionada puede dar lugar a desvíos de rutas excesivos o hacer imposible completar todas las rutas.
- Energía : la minimización de energía generalmente implica distribuir las ubicaciones de los componentes de la celda para reducir el consumo general de energía, aliviar los puntos calientes y suavizar los gradientes de temperatura.
- Un objetivo secundario es la minimización del tiempo de ejecución de la ubicación .
Tecnicas basicas
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 con pequeñas superposiciones permitidas. La ubicación detallada cambia 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.
Al principio, la colocación de circuitos integrados se maneja mediante enfoques combinatorios. Cuando el diseño de CI era de escala de mil puertas, las metodologías de recocido simulado [1] como TimberWolf [2] exhiben el mejor rendimiento. A medida que el diseño de IC entró en la integración a escala millonaria, la ubicación se logró mediante particiones hipergráficas recursivas [3] como Capo. [4]
Posteriormente, la colocación cuadrática superó a las soluciones combinatorias tanto en calidad como en estabilidad. GORDIAN [5] formula el costo de la longitud del cable como una función cuadrática mientras sigue separando las celdas mediante particiones recursivas. El algoritmo [6] modela la densidad de ubicación como un término lineal en la función de costo cuadrático y resuelve el problema de ubicación mediante programación cuadrática pura. La mayoría de los colocadores cuadráticos modernos (KraftWerk, [7] FastPlace, [8] SimPL [9] ) siguen este marco, cada uno con diferentes heurísticas sobre cómo determinar la fuerza de densidad lineal.
La ubicación no lineal presenta un mejor rendimiento sobre otras categorías de algoritmos. El enfoque en [10] primero modela la longitud de cable por funciones exponenciales (no lineales) y la densidad por funciones cuadráticas locales por partes, con el fin de lograr una mejor precisión y, por lo tanto, una mejora de la calidad. Los trabajos académicos de seguimiento incluyen principalmente APlace [11] y NTUplace. [12]
ePlace [13] es el algoritmo de ubicación global más avanzado. Separa las instancias simulando un campo electrostático, que introduce la mínima calidad de sobrecarga y, por lo tanto, logra el mejor rendimiento.
Ver también
Referencias
- ^ S. Kirkpatrick, CDG Jr. y MP Vecchi. Optimización mediante recocido simulado. Science, 220 (4598): 671–680, 1983.
- ^ C. Sechen y A. Sangiovanni-Vincentelli. TimberWolf3.2: un nuevo paquete de enrutamiento global y colocación de celdas estándar. En DAC, páginas 432–439, 1986.
- ^ George Karypis, Rajat Aggarwal, Vipin Kumar y Shashi Shekhar. Particionamiento de Hypergraph multinivel: Aplicaciones en el dominio VLSI. En DAC, págs. 526 - 529, 1997.
- ^ Caldwell, AE; Kahng, AB; Markov, IL (junio de 2000). " ¿Puede la bisección recursiva producir por sí sola ubicaciones enrutables? ". Actas de la 37ª Conferencia de Automatización del Diseño . págs. 477–482.
- ^ Kleinhans, JM; Sigl, G .; Johannes, FM; Antreich, KJ (marzo de 1991). "GORDIAN: colocación de VLSI mediante programación cuadrática y optimización de corte". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 10 (3): 356–365. doi : 10.1109 / 43.67789 . S2CID 15274014 .
- ^ H. Eisenmann y FM Johannes. Colocación global genérica y plano de planta. En DAC, páginas 269–274, 1998.
- ^ P. Spindler, U. Schlichtmann y FM Johannes. Kraftwerk2: un enfoque rápido de colocación cuadrática dirigida por la fuerza utilizando un modelo de red preciso. IEEE TCAD, 27 (8): 1398–1411, 2008.
- ^ N. Viswanathan, M. Pan y C. Chu. FastPlace3.0: Un algoritmo de colocación cuadrático multinivel rápido con control de congestión de colocación. En ASPDAC, páginas 135–140, 2007.
- ^ Kim, M.-C .; Lee D.-J .; Markov IL (enero de 2011). "SimPL: un algoritmo de colocación eficaz". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 31 (1): 50–60. doi : 10.1109 / TCAD.2011.2170567 . S2CID 47293399 .
- ^ WC Naylor, R. Donelly y L. Sha. Sistema de optimización no lineal y método para la optimización de la longitud del cable y el retardo para un posicionador automático de circuitos eléctricos. En la patente de EE. UU. 6301693, 2001.
- ^ AB Kahng, S. Reda y Q. Wang, "Arquitectura y detalles de un colocador analítico a gran escala de alta calidad", en ICCAD 2005, págs. 891-898.
- ^ T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen y Y.-W. Chang. NTUPlace3: un colocador analítico para diseños de tamaños mixtos a gran escala con bloques preinstalados y restricción de densidad. IEEE TCAD, 27 (7): 1228-1240, 2008.
- ^ J. Lu, P. Chen, C.-C. Chang, L. Sha, DJ-S. Huang, C.-C. Teng y C.-K. Cheng, "ePlace: Colocación basada en electrostática utilizando el método de Nesterov", DAC 2014, págs. 1-6.
Más lecturas / Enlaces externos
- Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados (TCAD)
- Transacciones ACM sobre Automatización de Diseño de Sistemas Electrónicos (TODAES)
- Transacciones IEEE en sistemas de integración a gran escala (TVLSI)