Coisas que eu gostaria de saber antes de desenvolver um Autorouter

"Lições importantes para criar o autorouter mais rápido do mundo"

Usar o algoritmo A* em todo lugar

• A* é o algoritmo mais poderoso e flexível para problemas de busca
• Pode ser usado não só em uma simples grade 2D, mas também em vários tipos de problema
• O A* é uma "busca informada" que, de forma mais rápida e eficiente que o BFS, prioriza a exploração de nós mais próximos do destino
• Na maioria dos casos, DFS ou BFS usados em código existente podem ser substituídos por A*
• Para melhorar o desempenho, pode-se executar várias instâncias de A* e alocar mais recursos às configurações que apresentarem melhor performance

O algoritmo é mais importante do que a linguagem de programação

• Não houve problema algum em desenvolver o autorouter em Javascript
• O ponto central da otimização é reduzir o número de repetições
• Mais importante do que a performance da linguagem é "quão inteligente é o algoritmo que você consegue criar, e com que rapidez consegue criá-lo"
• Javascript favorece mais algoritmos inteligentes do que iteração rápida

Spatial Hash Indexing é mais eficiente do que estruturas em árvore

• Estruturas de dados baseadas em árvore, como Quadtree, em geral são lentas
• O Spatial Hash Index agrupa e processa objetos espacialmente próximos ao aplicar hash na posição deles
• Estruturas baseadas em hash oferecem desempenho de busca próximo de O(1)
• É preciso escolher bem o tamanho da célula para obter efeito, e essa escolha adequada não é difícil

Particionamento espacial e cache são 1000 vezes mais importantes do que o algoritmo

• Mesmo placas de circuito complexas costumam ter padrões repetitivos
• Assim como no desenvolvimento de jogos, armazenar resultados pré-calculados em cache pode melhorar drasticamente o desempenho
• Estruturas cacheáveis e particionamento espacial serão a base dos autorouters do futuro
• O armazenamento está ficando barato rapidamente, e até alguns GB de cache já podem trazer grandes ganhos de performance

Sem visualização, não dá para resolver o problema

• Para todo problema, a primeira coisa a fazer foi criar uma ferramenta de visualização
• Com visualização, foi possível melhorar a velocidade de depuração em mais de 10 vezes
• Mesmo etapas simples do algoritmo, quando visualizadas, permitem identificar rapidamente a causa do problema

As ferramentas de profiling do Javascript são muito úteis

• Na aba Performance das ferramentas de desenvolvedor do Chrome, dá para verificar o tempo gasto por trecho de código
• Mesmo sem framework adicional, é fácil analisar Flame Chart, uso de memória etc.
• São ferramentas muito úteis para depuração de performance

Não use funções recursivas

• Funções recursivas geralmente são síncronas e difíceis de converter para A*
• Implementações iterativas são mais rápidas e facilitam o rastreamento de nós visitados
• Em funções recursivas, é difícil alterar estado e isso tende a ser ineficiente
• Sempre que possível, escreva com base em laços iterativos

Evite algoritmos de Monte Carlo

• Algoritmos baseados em aleatoriedade são não determinísticos e difíceis de depurar
• Heurísticas especializadas no domínio sempre oferecem desempenho melhor
• Nenhum designer de PCB traça linhas aleatoriamente → não é uma abordagem realista
• Ainda assim, no começo pode ser útil para ganhar intuição

Mantenha as etapas do algoritmo ancoradas no espaço real do problema

• Normalizar subalgoritmos com base na origem dificulta entender o fluxo completo
• Visualizar as entradas e saídas de cada etapa ajuda a identificar qual etapa está causando erro
• É importante manter o fluxo do algoritmo preservando um sistema de coordenadas consistente

Visualize o processo iterativo com animação

• Dá para perceber visualmente o quanto o algoritmo está explorando de forma ineficiente
• Animações são muito eficazes para reduzir o número de iterações e aumentar a eficiência
• Também facilitam detectar situações problemáticas (por exemplo, uma busca presa em loop infinito)

A matemática de detecção de interseção basta, sem grade

• Em vez de usar uma grade, usar matemática vetorial é muito mais rápido
• Em muitos casos, operações matemáticas podem ser mais rápidas do que acesso à memória
• Graças aos LLMs, ficou mais fácil implementar também a matemática de detecção de interseção
• Usar grade sem necessidade é uma causa de queda de desempenho

Medir a probabilidade de falha em cada etapa ajuda a priorizar a possibilidade de solução

• É possível estimar a probabilidade de falha em cada nó do particionamento espacial
• Depois, prioriza-se a reconfiguração ou nova exploração dos nós com maior chance de falhar nas etapas seguintes
• A probabilidade de falha pode ser medida claramente e tem mais potencial de melhoria do que heurísticas
• Aumentar a chance de resolver o problema como um todo pode ser mais eficaz do que buscar apenas otimização

Com Weighted A*, é possível ganhar 100 vezes em velocidade

• O A* padrão garante o caminho ótimo, mas é lento
• O Weighted A* explora de forma mais gulosa e pode aumentar drasticamente a velocidade
• Pode ser implementado apenas ajustando o peso em f(n) = g(n) + w * h(n)
• Mesmo abrindo mão de um pouco de optimalidade, ele consegue resolver o problema muito mais rápido
• É uma técnica usada com frequência também no desenvolvimento de jogos e vale a referência

[GN⁺]

Comentários no Hacker News

• Descartar métodos de Monte Carlo rapidamente é um grande erro

  • Métodos de Monte Carlo têm a característica de permitir trocar precisão por velocidade
  • Quanto mais tempo o algoritmo roda, mais preciso ele fica
  • Por outro lado, também é possível obter resultados rápidos e imprecisos
  • Em vez de explorar todos os caminhos, explora-se apenas um caminho escolhido aleatoriamente
  • É eficaz usar Monte Carlo no laço mais interno do algoritmo
  • Por exemplo, ao treinar uma rede neural, o laço externo atualiza os parâmetros da rede e o laço interno calcula caminhos pelo grafo
  • Com Monte Carlo, é possível reduzir a precisão do laço interno para uma única iteração
  • Isso intuitivamente permite construir uma política que sempre toma a decisão correta
  • Em xadrez ou Go, é possível calcular o melhor caminho usando variações de busca em árvore de Monte Carlo

• Tenho a posição de que "não se deve confiar em auto-routers"

  • Há uma grande oportunidade na área de eCAD para aumentar a velocidade do layout
  • É mais provável usar ferramentas de cocriação do que ferramentas de automação total
  • No início do projeto, o posicionamento não está definido, o que afeta muito o roteamento
  • Pela página, não dá para confirmar se o posicionamento faz parte do algoritmo
  • Tenho curiosidade sobre o plano para um AR escrito em JavaScript

• O artigo menciona pontos importantes sobre visualização e efeitos de cache

  • Algoritmos recursivos fazem busca em profundidade
  • DFS e BFS podem ser escritos de forma iterativa ou recursiva
  • A* é útil para busca de caminhos
  • BFS explora todos os nós adjacentes, e A* prioriza nós mais próximos do destino
  • A* é um algoritmo dinâmico, capaz de encerrar cedo com confiança ao encontrar o caminho mais curto

• É uma excelente discussão sobre autorroteamento

  • O roteamento em si é fácil
  • Fica complexo quando é preciso remover o que já foi roteado para encaixar algo novo
  • Sinto falta do auto-router do KiCAD

• 95% do foco deveria estar em reduzir o número de iterações

  • Se desempenho ainda for importante, então deve-se reescrever em uma linguagem de baixo nível
  • numpy, pandas, OpenCV e TensorFlow são implementados em C++/assembly/CUDA de alto desempenho

• QuadTree e estruturas de dados em árvore de modo geral são muito lentas

  • Árvores não são uma representação da informação dos dados
  • Abordagens com hashing só servem quando os pontos estão distribuídos de maneira uniforme
  • Algoritmos aleatórios são úteis quando o espaço de busca é muito grande

• Quase tudo isso bate com heurísticas de desenvolvimento de jogos

  • A*, algoritmo de Lee etc. são todos muito legais
  • Escrever flood fill sem visualização é um crime
  • Hashing espacial, em especial, combina muito com a experiência prática

• "indexação por hash espacial > estruturas de dados em árvore" é bom neste domínio, mas não deve ser tomado como verdade universal

  • Se os pontos não estiverem distribuídos de forma uniforme, a função de hash pode ser ruim

• Lembro das palavras-chave que aprendi na universidade

  • Não tenho oportunidade de usar algoritmos sofisticados
  • Em vez disso, construo componentes de UI e APIs REST

• Como alguém que não lida diretamente com problemas espaciais 2D/3D, a maior lição para mim é o valor da visualização

  • Humanos são excelentes em entender e analisar imagens
  • A ideia de usar métodos probabilísticos ou de força bruta para entender o formato do problema é importante