Resumen Técnico: OrderPlace

Planteamiento del Problema

El posicionamiento de macros es un paso crítico en el diseño físico de chips modernos, dictando fundamentalmente la calidad, el rendimiento y la manufacturabilidad del circuito integrado final. Formalmente, es un problema de optimización combinatoria a gran escala que requiere la determinación de las posiciones físicas de las macros dentro de un lienzo fijo sin superposiciones. Si bien los avances recientes en aprendizaje automático han acelerado la determinación de coordenadas, la dimensión temporal del secuenciamiento de colocación (es decir, el orden en el que se colocan las macros) sigue estando gobernada en gran medida por heurísticas estáticas o permutaciones aleatorias.

El artículo argumenta que la secuencia de colocación no es simplemente un paso de preprocesamiento, sino un factor decisivo en la optimización. En los procesos de colocación secuencial, las decisiones tempranas definen las condiciones de contorno factibles para todas las macros subsiguientes. Una sola decisión subóptima al principio de la secuencia puede desencadenar un "efecto dominó" irreversible, restringiendo el espacio de soluciones y conduciendo a óptimos locales deficientes. A pesar de esto, los métodos existentes se centran predominantemente en la cuestión espacial de "¿Dónde colocar?" mientras tratan la cuestión temporal de "¿Quién va primero?" como un conocimiento previo fijo. Además, explorar el impacto del secuenciamiento es notoriamente difícil porque la señal de ordenamiento suele estar enmascarada por poderosos métodos de refinamiento, y evaluar una sola secuencia requiere típicamente ejecutar un ciclo de colocación completo y computacionalmente prohibitivo.

Metodología: OrderPlace

Para abordar estos desafíos, los autores proponen OrderPlace, un marco de evolución guiado por modelos de lenguaje de gran tamaño (LLM) y basado en proxies, diseñado para descubrir automáticamente estrategias de orden de colocación de macros. El marco opera a través de tres componentes principales:

1. Estrategias de Orden de Colocación Inicial

El marco inicializa una población de estrategias para proporcionar un espacio de búsqueda diverso. Estas se categorizan en:

• Estrategias Estáticas: Computan prioridades basándose únicamente en características geométricas y topológicas a nivel de macro (por ejemplo, área, grado, conectividad de red).
• Estrategias Dinámicas: Adaptan las prioridades basándose en el estado de colocación evolutivo, a menudo inspiradas en la dinámica física (por ejemplo, potenciales de resorte, modelos de campo, reducción de entropía).

2. Evolución de Estrategias Impulsada por LLM

OrderPlace utiliza LLMs (por ejemplo, GPT-4, DeepSeek-V3, Claude) para evolucionar estrategias de ordenamiento a nivel de código. El proceso implica:

• Ingeniería de Prompts: Al LLM se le proporciona un system prompt que define el rol de un experto en VLSI y un user prompt que contiene los resultados de evaluación de las estrategias con mejor desempeño (Top-K) de la generación anterior.
• Generación de Código: El LLM genera nuevas clases de Python que representan estrategias de colocación, ya sea como ordenadores estáticos o funciones de prioridad dinámica.
• Ciclo Evolutivo: El marco mantiene una población de estrategias a través de generaciones. Selecciona las estrategias Top-K basadas en puntuaciones de aptitud (fitness) y las utiliza como contexto para generar nuevas estrategias candidatas, fomentando el descubrimiento de nuevas combinaciones y mecanismos dinámicos.

3. Evaluación Guiada por Proxy

Para mitigar el costo prohibitivo de la optimización a escala completa para cada candidato, OrderPlace introduce un mecanismo de evaluación de proxy ligero:

• Procedimiento Greedy Guiado por Máscara de Cable (Wire-Mask): En lugar de una optimización completa, las estrategias se evalúan utilizando un algoritmo de colocación codicioso (greedy) determinista guiado por máscaras de longitud de cable precomputadas.
• Monte Carlo en Paralelo: Cada estrategia se ejecuta en múltiples semillas iniciales aleatorias en paralelo para generar una distribución de resultados de Longitud de Perímetro de Medio de Cable (HPWL).
• Puntuación de Aptitud (Fitness Scoring): La aptitud de una estrategia es la media del HPWL sobre las ejecuciones exitosas. Un mecanismo de tiempo de espera (timeout) y la validación de sintaxis aseguran la eficiencia y robustez.

Una vez que la búsqueda evolutiva concluye, las estrategias Top-K se someten a un ajuste fino mediante el procedimiento greedy guiado por la máscara de cable para producir los resultados finales de colocación.

Contribuciones Clave

1. Cambio de Perspectiva: El artículo proporciona evidencia teórica y empírica de que la secuencia de colocación es una dimensión crítica, aunque históricamente pasada por alto, de la optimización. Demuestra que un ordenamiento subóptimo conduce a una degradación asintótica en la calidad de la solución (por ejemplo, degradación $\Omega(l)$ para topologías de cadena y $\Theta(g)$ para topologías de estrella).
2. Innovación Metodológica: OrderPlace es el primer marco evolutivo impulsado por LLM diseñado específicamente para el secuenciamiento de colocación de macros. Integra con éxito la evaluación por proxy para resolver el desafío de los bucles de retroalimentación costosos en la optimización de la planificación de áreas (floorplanning).
3. Descubrimiento de Nuevas Estrategias: El marco descubre algoritmos de ordenamiento generalizables que van desde heurísticas estáticas hasta reglas dinámicas complejas inspiradas en la física (por ejemplo, modelos gravitacionales, reducción de entropía y priorización de cierre de redes) que superan a las heurísticas diseñadas manualmente.

Resultados Experimentales

Los autores evaluaron OrderPlace en la suite de benchmarks ISPD 2005 (ocho diseños de chips).

• Rendimiento: OrderPlace logró los mejores valores (más bajos) de HPWL en 7 de los 8 circuitos.
• Comparaciones:
  • Comparado con WireMask-EA, OrderPlace redujo la longitud de cable en un 34.04%.
  • Comparado con el método de vanguardia EGPlace, OrderPlace redujo la longitud de cable en un 14.08%.
  • En una comparación directa utilizando la prueba de suma de rangos de Wilcoxon, OrderPlace funcionó significativamente mejor en 7 circuitos en comparación con EGPlace.
• Convergencia: OrderPlace demostró una eficiencia computacional notable, convergiendo significativamente más rápido que EGPlace. La mejor estrategia descubierta alcanzó consistentemente puntos de convergencia más bajos de manera más temprana en la trayectoria de optimización.
• Congestión y Tamaño Mixto: OrderPlace también mostró una capacidad de enrutabilidad (congestión) superior y logró un rendimiento líder en tareas de colocación de tamaños mixtos cuando se combinó con un colocador global (DreamPlace).
• Impacto del LLM: Los estudios de ablación confirmaron que las estrategias generadas por LLM superaron consistentemente a todas las estrategias iniciales diseñadas a mano, lo que indica que la ganancia de rendimiento proviene del descubrimiento de políticas de ordenamiento no triviales más allá de las heurísticas existentes.

Significado y Reivindicaciones

El artículo afirma que OrderPlace representa la primera evidencia sistemática de que el secuenciamiento de colocación, tradicionalmente visto como un paso de preprocesamiento estático, sirve como un determinante crítico en la optimización de la colocación. Al automatizar el descubrimiento de estrategias de ordenamiento mediante LLMs y evaluación por proxy, el método mitiga eficazmente la suboptimidad en la colocación basada en decisiones de secuencia.

Los autores enfatizan que su enfoque es distinto de trabajos previos que tratan el secuenciamiento como un conocimiento previo fijo o que dependen de agentes de aprendizaje por refuerzo (RL) para aprender secuencias implícitamente. En su lugar, OrderPlace optimiza explícitamente la secuencia de entrada como un hiperparámetro. El trabajo sugiere que el potencial de optimización del secuenciamiento de colocación es una dimensión "latente" que, al desbloquearse, puede acelerar fundamentalmente los solucionadores codiciosos y permitir mejores soluciones globales.

Limitaciones: El estudio está actualmente limitado a evaluar el impacto del orden de colocación en métodos greedy guiados por máscaras. La interacción con métodos estocásticos basados en aprendizaje permanece inexplorada, y se propone trabajo futuro para investigar cómo el ordenamiento de colocación puede mejorar los métodos de colocación impulsados por aprendizaje profundo.