Resumo Técnico: OrderPlace

Definição do Problema

O posicionamento de macros é uma etapa crítica no design físico de chips modernos, ditando fundamentalmente a qualidade, o desempenho e a manufaturabilidade do circuito integrado final. Formalmente, trata-se de um problema de otimização combinatória de larga escala que requer a determinação de posições físicas para macros dentro de uma tela fixa sem sobreposição. Embora avanços recentes em aprendizado de máquina tenham acelerado a determinação de coordenadas, a dimensão temporal do sequenciamento de posicionamento (ou seja, a ordem na qual as macros são posicionadas) permanece amplamente governada por heurísticas estáticas ou permutações aleatórias.

O artigo argumenta que o sequenciamento de posicionamento não é meramente uma etapa de pré-processamento, mas um fator decisivo na otimização. Em processos de posicionamento sequencial, as decisões iniciais definem as condições de contorno viáveis para todas as macros subsequentes. Uma única decisão subótima no início da sequência pode desencadear um "efeito dominó" irreversível, restringindo o espaço de solução e levando a ótimos locais pobres. Apesar disso, os métodos existentes focam predominantemente na questão espacial de "Onde posicionar?", enquanto tratam a questão temporal de "Quem vai primeiro?" como um prior fixo. Além disso, explorar o impacto do sequenciamento é notoriamente difícil porque o sinal de ordenação é frequentemente mascarado por métodos de refinamento poderosos, e avaliar uma única sequência normalmente requer a execução de um ciclo completo de posicionamento, o que é computacionalmente proibitivo.

Metodologia: OrderPlace

Para enfrentar esses desafios, os autores propõem o OrderPlace, um framework de evolução guiado por proxy e baseado em Grandes Modelos de Linguagem (LLMs), projetado para descobrir automaticamente estratégias de ordem de posicionamento de macros. O framework opera através de três componentes principais:

1. Estratégias Iniciais de Ordem de Posicionamento

O framework inicializa uma população de estratégias para fornecer um espaço de busca diversificado. Estas são categorizadas em:

• Estratégias Estáticas: Computam prioridades baseadas puramente em características geométricas e topológicas de nível de macro (ex: área, grau, conectividade de rede).
• Estratégias Dinâmicas: Adaptam as prioridades com base no estado evolutivo do posicionamento, frequentemente inspiradas em dinâmicas físicas (ex: potenciais de mola, modelos de campo, redução de entropia).

2. Evolução de Estratégias Dirigida por LLM

O OrderPlace utiliza LLMs (ex: GPT-4, DeepSeek-V3, Claude) para evoluir estratégias de ordenação em nível de código. O processo envolve:

• Engenharia de Prompt: O LLM recebe prompts de sistema que definem o papel de um especialista em VLSI e prompts de usuário contendo resultados de avaliação das melhores estratégias (Top-K) da geração anterior.
• Geração de Código: O LLM gera novas classes Python que representam estratégias de posicionamento, seja como ordenadores estáticos ou funções de prioridade dinâmica.
• Ciclo Evolutivo: O framework mantém uma população de estratégias através de gerações. Ele seleciona as Top-K estratégias com base em pontuações de aptidão (fitness) e as utiliza como contexto para gerar novas estratégias candidatas, fomentando a descoberta de novas combinações e mecanismos dinâmicos.

3. Avaliação Guiada por Proxy

Para mitigar o custo proibitivo da otimização em escala total para cada candidato, o OrderPlace introduz um mecanismo de avaliação de proxy leve:

• Procedimento Ganancioso Guiado por Máscara de Fio (Wire-Mask-Guided Greedy): Em vez de otimização completa, as estratégias são avaliadas usando um algoritmo de posicionamento ganancioso determinístico guiado por máscaras de comprimento de fio pré-computadas.
• Monte Carlo Paralelo: Cada estratégia é executada em múltiplas sementes iniciais aleatórias em paralelo para gerar uma distribuição de resultados de Comprimento de Perímetro de Meio-Perímetro (HPWL).
• Pontuação de Aptidão (Fitness Scoring): A aptidão de uma estratégia é a média do HPWL sobre as execuções bem-sucedidas. Um mecanismo de timeout e validação de sintaxe garantem eficiência e robustez.

Uma vez concluída a busca evolutiva, as Top-K estratégias passam por um ajuste fino via procedimento ganancioso guiado por máscara de fio para produzir os resultados finais de posicionamento.

Principais Contribuições

1. Mudança de Perspectiva: O artigo fornece evidência teórica e empírica de que o sequenciamento de posicionamento é uma dimensão crítica, embora historicamente negligenciada, da otimização. Demonstra que uma ordenação subótima leva a uma degradação assintótica na qualidade da solução (ex: degradação $\Omega(l)$ para topologias de cadeia e $\Theta(g)$ para topologias de estrela).
2. Inovação Metodológica: O OrderPlace é o primeiro framework de evolução dirigido por LLM especificamente projetado para o sequenciamento de posicionamento de macros. Ele integra com sucesso a avaliação por proxy para resolver o desafio dos ciclos de feedback caros na otimização de floorplanning.
3. Descoberta de Novas Estratégias: O framework descobre algoritmos de ordenação generalizáveis que variam de heurísticas estáticas a regras dinâmicas complexas inspiradas na física (ex: modelos gravitacionais, redução de entropia e priorização de fechamento de rede) que superam heurísticas criadas manualmente.

Resultados Experimentais

Os autores avaliaram o OrderPlace no conjunto de benchmarks padrão ISPD 2005 (oito designs de chips).

• Desempenho: O OrderPlace alcançou os melhores (menores) valores de HPWL em 7 de 8 circuitos.
• Comparações:
  • Comparado ao WireMask-EA, o OrderPlace reduziu o comprimento de fio em 34,04%.
  • Comparado ao método de estado da arte EGPlace, o OrderPlace reduziu o comprimento de fio em 14,08%.
  • Em uma comparação direta usando o teste de soma de postos de Wilcoxon, o OrderPlace teve um desempenho significativamente superior em 7 circuitos comparado ao EGPlace.
• Convergência: O OrderPlace demonstrou uma eficiência computacional notável, convergindo significativamente mais rápido que o EGPlace. A melhor estratégia descoberta atingiu consistentemente pontos de convergência mais baixos mais cedo na trajetória de otimização.
• Congestionamento e Tamanho Misto: O OrderPlace também mostrou roteabilidade superior (congestionamento) e alcançou desempenho de liderança em tarefas de posicionamento de tamanhos mistos quando combinado com um posicionador global (DreamPlace).
• Impacto do LLM: Estudos de ablação confirmaram que as estratégias geradas por LLM superaram consistentemente todas as estratégias iniciais criadas manualmente, indicando que o ganho de desempenho provém da descoberta de políticas de ordenação não triviais além das heurísticas existentes.

Significância e Alegações

O artigo afirma que o OrderPlace representa a primeira evidência sistemática de que o sequenciamento de posicionamento, tradicionalmente visto como um passo de pré-processamento estático, serve como um determinante crítico na otimização de posicionamento. Ao automatizar a descoberta de estratégias de ordenação via LLMs e avaliação por proxy, o método mitiga efetivamente a subotimalidade em posicionamentos baseados em decisões de sequência.

Os autores enfatizam que sua abordagem é distinta de trabalhos anteriores que tratam o sequenciamento como um prior fixo ou dependem de agentes de RL para aprender sequências implicitamente. Em vez disso, o OrderPlace otimiza explicitamente a sequência de entrada como um hiperparâmetro. O trabalho sugere que o potencial de otimização do sequenciamento de posicionamento é uma dimensão "latente" que, quando desbloqueada, pode acelerar fundamentalmente os solvers gananciosos e liberar melhores soluções globais.

Limitações: O estudo é atualmente limitado à avaliação do impacto da ordem de posicionamento em métodos gananciosos guiados por máscara. A interação com métodos estocásticos e baseados em aprendizado permanece inexplorada, e propõe-se trabalhos futuros para investigar como a ordenação de posicionamento pode potencializar métodos de posicionamento baseados em aprendizado profundo.