Autorouter를 개발하기 전에 알았으면 좋았을 것들

"세계에서 가장 빠른 자동 배선기(Autorouter) 를 만들기 위한 중요한 교훈들"

A* 알고리듬을 모든 곳에 활용하기

• A*는 탐색 문제에서 가장 강력하고 유연한 알고리듬임
• 단순한 2D 그리드 뿐 아니라 다양한 문제에서 사용 가능함
• A*는 BFS보다 빠르고 효율적으로 목적지에 가까운 노드를 우선 탐색하는 '정보 기반 탐색'임
• 기존 코드에서 사용 중인 DFS나 BFS는 대부분 A*로 대체 가능함
• 성능 개선을 위해 여러 A* 인스턴스를 실행하고 그 중 성능이 좋은 설정에 자원을 더 배분하는 기법 사용

프로그래밍 언어보다 알고리듬이 더 중요함

• autorouter를 Javascript로 개발해도 전혀 문제가 없었음
• 최적화의 핵심은 반복 횟수를 줄이는 것임
• 언어 성능보다 “얼마나 똑똑한 알고리듬을 얼마나 빨리 만들 수 있느냐”가 더 중요함
• Javascript는 빠른 반복보다는 스마트한 알고리듬에 더 유리함

트리 구조보다 Spatial Hash Indexing이 더 효율적임

• Quadtree 등 트리 기반 자료구조는 일반적으로 느림
• Spatial Hash Index는 객체의 위치를 해시하여 공간적으로 가까운 객체끼리 묶어 처리함
• 해시 기반 구조는 O(1)에 가까운 탐색 성능 제공
• Cell 크기를 잘 선택해야 효과적이며, 적절한 크기 선택은 어렵지 않음

공간 분할과 캐시가 알고리듬보다 1000배 중요함

• 복잡한 회로 보드도 대부분 반복되는 패턴을 가짐
• 게임 개발처럼 사전 계산된 결과를 캐시하여 성능을 획기적으로 향상시킬 수 있음
• 캐시 가능한 구조와 공간 분할이 미래 autorouter의 핵심이 될 것임
• 저장 공간은 빠르게 저렴해지고 있고, 수 GB 캐시로도 큰 성능 향상 가능함

시각화 없이는 문제 해결 불가

• 모든 문제에 대해 시각화 도구를 먼저 만들고 시작함
• 시각화를 통해 디버깅 속도를 10배 이상 향상시킬 수 있었음
• 단순한 알고리듬 단계도 시각화하면 문제 원인을 빠르게 파악 가능함

Javascript의 프로파일링 도구는 매우 유용함

• Chrome 개발자 도구의 Performance 탭에서 코드별 소요 시간 확인 가능
• 별도 프레임워크 없이도 Flame Chart, 메모리 사용량 등 쉽게 분석 가능함
• 성능 디버깅에 매우 유용한 도구임

재귀 함수는 사용하지 말 것

• 재귀 함수는 일반적으로 동기적이며 A*로 전환이 어려움
• 반복 기반 구현이 더 빠르고, 방문 노드를 추적하기 용이함
• 재귀 함수에서는 상태 변경이 어렵고 비효율적임
• 가능한 한 반복문 기반으로 작성할 것

Monte Carlo 알고리듬은 지양할 것

• 무작위성 기반 알고리듬은 비결정적이고 디버깅이 어려움
• 도메인에 특화된 휴리스틱이 항상 더 뛰어난 성능을 제공함
• 무작위로 선을 그리는 PCB 디자이너는 없음 → 현실적인 접근 아님
• 단, 초기에 감 잡기용으로는 유용할 수 있음

알고리듬 단계를 실제 문제 공간에 고정할 것

• 서브 알고리듬을 원점 기준으로 정규화하면 전체 흐름 파악이 어려워짐
• 각 단계별 입출력을 시각화하여 어떤 단계가 오류를 유발하는지 파악함
• 좌표계를 일관되게 유지하면서 알고리듬 흐름을 유지하는 것이 중요함

반복 과정을 애니메이션으로 시각화할 것

• 알고리듬이 얼마나 비효율적으로 탐색하고 있는지 시각적으로 파악 가능함
• 애니메이션은 반복 횟수를 줄이고 효율성을 높이는 데 매우 효과적임
• 문제 상황을 쉽게 포착할 수 있음 (예: 무한 루프에 빠진 탐색 등)

그리드 없이 교차 판별 수학으로 충분함

• 그리드 사용 대신 벡터 수학을 활용하면 훨씬 빠름
• 메모리 접근보다 수학 연산이 더 빠른 경우도 많음
• LLM 덕분에 교차 판별 수학도 쉽게 구현 가능해졌음
• 불필요한 그리드 사용은 성능 저하 원인임

각 단계별 실패 확률 측정으로 해결 가능성 우선 순위화

• 각 공간 분할 노드에서 실패 확률 추정 가능
• 이후 단계에서 실패할 가능성이 높은 노드를 우선적으로 재구성 또는 재탐색함
• 실패 확률은 명확하게 측정 가능하며 휴리스틱보다 개선 가능성이 큼
• 전체 해결 가능성을 높이는 것이 최적화를 목표로 하는 것보다 더 효과적일 수 있음

Weighted A*로 속도 100배 향상 가능

• 기본 A*는 최적 경로를 보장하지만 속도는 느림
• Weighted A*는 더 탐욕적으로 탐색하여 속도 대폭 향상 가능
• f(n) = g(n) + w * h(n) 으로 가중치 설정만으로 구현 가능함
• 최적성이 약간 손해를 보더라도 훨씬 빠르게 문제를 해결할 수 있음
• 게임 개발 분야에서도 자주 사용되는 기법이며 참고할 만함