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

• tscircuit용 오픈소스 PCB autorouter를 약 1년 개발한 경험은 A*, 시각화, 공간 분할, 캐싱처럼 탐색 문제를 줄이는 설계가 성능의 핵심임을 보여줌
• 최적화의 초점은 언어나 반복 1회 속도보다 반복 횟수 감소에 있으며, JavaScript라도 더 똑똑하고 캐시 가능한 알고리듬이면 저수준 구현보다 빠를 수 있음
• 공간 검색에서는 QuadTree 같은 범용 트리보다 Spatial Hash Index가 단순하고 빠를 수 있지만, 셀 크기 선택이 잘못되면 조회마다 높은 고정 비용이 발생함
• 복잡한 autorouter 파이프라인은 단계별 입력·출력을 시각화하고 반복 과정을 애니메이션으로 확인해야 하며, 재귀 함수와 Monte Carlo 방식은 디버깅·최적화·결정성에서 불리함
• A*는 Weighted A* 의 Greedy Multiplier로 최적성을 일부 포기하고 속도를 크게 높일 수 있으며, 각 단계는 이후 단계가 풀기 쉬운 상태를 만들도록 실패 확률을 낮춰야 함

---

A*를 기본 탐색 도구로 삼기

• A*는 2D 격자 전용 알고리듬이 아니라 여러 형태의 정보 기반 탐색(informed search) 에 쓸 수 있는 기반 알고리듬임
• BFS는 인접 노드를 모두 탐색하지만, A*는 목적지에 더 가까운 노드를 우선 탐색함
  • 그래프 바깥의 거리 지표를 사용하므로 정보 기반 탐색에 해당함
• 재귀 알고리듬은 깊이 우선 탐색(DFS)에 가깝고, 후보나 이웃을 정렬하지 않고 탐색하는 루프는 BFS에 가까움
• 기존 BFS나 DFS 형태의 코드를 A*로 바꾸면 큰 성능 향상을 얻는 경우가 많음
• autorouter에서는 여러 수준의 A*를 사용해 문제에 맞는 하이퍼파라미터를 찾음
  • 각 autorouter 설정을 후보로 실행함
  • 좋은 비용으로 라우팅에 성공하기 시작한 설정에 더 많은 반복을 배정함
  • 거리 비용과 반복 비용을 함께 벌점으로 쓰는 meta-A* 형태임

언어보다 알고리듬이 중요함

• tscircuit autorouter는 JavaScript로 작성되고 있으며, 성능 논의에서 언어가 먼저 지적되는 경우가 많음
• 알고리듬 최적화는 크게 두 축으로 나뉨
  • 필요한 반복 횟수를 줄여 알고리듬을 더 똑똑하게 만들기
  • 각 반복의 실행 속도를 높이기
• 반복 1회의 속도 개선에 과도하게 집중하면, 잘못된 접근을 빠르게 실행하는 데 그칠 수 있음
• 예를 들어 겹침 검사를 위해 모든 것을 격자로 바꾸는 방식은 언어와 관계없이 느려질 수 있음
• 저수준 최적화된 어셈블리의 단순한 알고리듬보다 JavaScript의 똑똑한 알고리듬이 더 빠를 수 있음
• 개발 시간의 95%는 반복 횟수를 줄이는 데 쓰는 편이 좋으며, 가장 똑똑하고 캐시 가능한 알고리듬에 빨리 도달하게 해주는 언어가 좋은 선택임

Spatial Hash Index가 트리보다 나을 수 있음

• 다차원 공간 최적화에서는 QuadTree가 자주 등장하지만, 범용 트리 자료구조는 느릴 수 있음
• QuadTree는 2D·3D 공간에서 가까운 객체 검색을 O(N)에서 O(log(N))로 줄이는 자료구조로 알려져 있지만, 트리는 데이터에 대한 정보 기반 표현이 아님
• Spatial Hash Index는 객체 자체가 아니라 객체의 위치를 해시해 셀 또는 가까운 것들의 버킷에 저장함
• 이 접근은 HashSet, HashMap처럼 빠른 해시 기반 접근을 공간 데이터에 적용하는 방식임
• 공간 해시가 덜 대중적인 이유는 적절한 셀 크기를 골라야 하기 때문임
  • 셀 크기가 잘못 보정되면 조회마다 높은 고정 비용이 발생함
  • 실제로는 합리적인 셀 크기를 고르는 일이 그렇게 어렵지 않다고 봄

공간 분할과 캐싱이 성능을 바꿈

• iPhone 내부 같은 회로 보드는 대략 10,000~20,000개 트레이스를 가질 수 있고, 최고 수준의 EDA 도구로도 팀이 몇 달 동안 라우팅할 수 있음
• autorouting 문제에서 중요한 단순한 아이디어는 이미 라우팅된 것은 이전에도 라우팅된 적이 있다는 점임
• 게임 개발자는 탐색 메시를 미리 굽고, LLM은 검색을 위해 인터넷을 가중치로 압축함
• 다음 세대 autorouter는 문제를 공간적으로 나누고, 이미 풀린 해답을 담은 큰 캐시를 활용할 수 있음
• autorouting 문제의 99%가 캐시에 미리 풀려 있다면 알고리듬 자체의 속도는 덜 중요해짐
• 현재 많은 알고리듬은 캐시 재사용성과 공간 분할에 충분히 집중하지 않음
• 저장과 캐싱 비용은 계산 속도 향상보다 더 빠르게 낮아지는 것으로 보이며, autorouter를 50% 빠르게 만들기 위해 1GB 캐시를 쓰는 것은 큰 문제가 아니라고 봄

시각화와 프로파일링으로 문제를 직접 보기

• 문제에 대한 시각화가 없으면 해결할 수 없다는 원칙이 중요함
• 숫자만 바라보는 방식으로는 디버깅이 어렵고, 작은 하위 문제마다 시각화를 만들면 문제를 훨씬 빠르게 이해할 수 있음
• autorouter 개발에서는 문제 해결을 시각화부터 시작하는 경우도 많음
• 45도 경로를 찾는 하위 알고리듬도 시각화했으며, 이는 autorouter의 거의 마지막 단계인 Path Simplification Phase에서 쓰임
• JavaScript 프로파일링 도구는 각 코드 줄에서 소비한 총 시간을 밀리초 단위로 보여줌
  • 브라우저에서 JavaScript를 실행하고 Performance 탭을 열면 됨
  • flame chart와 메모리 사용량 기능도 제공됨
• 관련 짧은 영상: youtube short

재귀와 Monte Carlo를 피하기

• 재귀 함수는 성능 지향 코드에서 피하는 편이 좋음
  • 거의 항상 동기적으로 동작해 애니메이션을 위해 중간에 끊기 어려움
  • 본질적으로 DFS이며 A*로 쉽게 바꾸기 어려움
  • 반복 횟수 추적이 쉽지 않음
  • 재귀 함수에서는 가변성이 부자연스럽지만, 성능에는 가변성이 중요할 수 있음
• 반복 기반 구현은 visitedNodes 집합을 유지하고 탐색 전에 노드를 확인할 수 있어 더 빠를 수 있음
• Monte Carlo 알고리듬은 무작위성으로 해답에 접근하지만, 결정적이지 않아 디버깅이 어렵고 휴리스틱 대비 최적인 경우가 거의 없다고 봄
• 후보를 어떻게 평가할지는 알지만 해답에 도달하는 방식을 모를 때, Monte Carlo 방식은 직관을 얻는 데 도움이 될 수 있음
• 비용 함수에 가까운 것이 생기면 Monte Carlo나 Simulated Annealing 같은 무작위 기법보다 더 나은 방식을 써야 함
• 로컬 최소값에 민감하다면 하이퍼파라미터나 더 복잡한 비용 함수를 고려할 수 있음
• PCB 설계자가 회로 보드 위에 무작위로 선을 긋지 않듯, 이 도메인에서는 더 나은 휴리스틱을 찾을 수 있다고 봄

중간 알고리듬은 같은 좌표계에 두기

• autorouter는 현재 13개 단계와 약 20개 하위 알고리듬으로 구성된 파이프라인임
• 공간 분할 결정이나 독립적으로 autoroute된 구역 경계의 경로 단순화 같은 작업에서 반복 횟수를 측정함
• 각 단계의 입력과 출력을 겹쳐 시각화하면 현재 해결 중인 문제의 맥락을 이해할 수 있음
• downstream 단계, 특히 high density routing 단계의 문제는 이전 단계의 출력을 개선해 해결되는 경우가 많음
• 하위 알고리듬을 만들 때 문제를 가장 단순한 형태로 분리하고 좌표를 (0, 0) 주변으로 정규화하고 싶은 유혹이 있음
• 정규화나 복잡한 변환은 초기 단계의 결과가 후속 단계에 미치는 영향을 빠르게 보기 어렵게 만들 수 있음
• 알고리듬 전체 생명주기에서 좌표 공간을 일관되게 유지하는 방식이 유리함
• 각 단계를 순서대로 보고 확대하면 실패한 Design Rule Check의 원인이 되는 단계를 찾는 데 도움이 됨

반복 애니메이션과 격자 회피

• 반복 횟수를 줄이는 것이 중요하므로, 알고리듬 반복을 애니메이션으로 보면 낭비되는 탐색을 직관적으로 파악할 수 있음
• 애니메이션은 특히 Greedy Multiplier를 조정할 때 도움이 됨
• 한 단순 트레이스가 실패해야 할 상황에서 즉시 실패하지 않고 바깥쪽으로 끝없이 해결을 시도하는 사례는 애니메이션 없이는 파악하기 어려웠음
• 두 트레이스 A와 B가 겹치는지 판단하는 방법은 크게 두 가지임
  • A와 B의 각 세그먼트를 보고 교차를 확인함
  • B가 존재하는 격자를 표시한 뒤 A가 지나는 격자에 B가 있는지 확인함
• 격자 방식은 쉽게 1000배 느려질 수 있음
• 빠른 벡터 수학을 쓰면 단일 격자 칸 확인을 위한 메모리 접근보다 두 세그먼트 교차 판단을 위한 dot product가 더 빠를 수 있음
• 엄밀하게는 적절한 여유 공간을 보장하기 위해 세그먼트 간 거리 계산을 써야 하며, 이는 교차보다 조금 더 복잡하지만 크게 다르지는 않음

실패 확률과 Weighted A*

• 공간 분할 단계에서는 각 단계의 해결 실패 확률을 선행 지표로 측정할 수 있음
• Unravel Autorouter는 주요 파이프라인 단계마다 각 Capacity Node의 실패 확률을 추적함
• 각 단계는 인접 노드 재구성이나 재라우팅을 통해 실패 확률을 줄이는 데 집중함
• 실패 확률은 실제로 측정할 수 있고, 알고리듬이 바뀌면 예측도 개선할 수 있음
• 각 단계가 이후 단계의 실패 가능성을 낮추는 방향으로 동작할 수 있음
• 너무 많은 제약을 한 번에 넣기보다 해결 가능성을 우선하는 편이 나음
• 일단 보드가 풀리면 처음부터 최적 해답을 생성하는 것보다 기존 해답을 다루는 편이 더 쉬운 경우가 많음

Greedy Multiplier로 속도와 최적성 절충

• 기본 A*는 최적 해답을 보장하지만, 속도를 더 중시한다면 f(n)을 조금 바꿔 Weighted A* 를 쓸 수 있음
• 일반 A*: f(n) = g(n) + h(n)
• Weighted A*: f(n) = g(n) + w * h(n)
• Weighted A*는 더 탐욕적으로 문제를 풀며 일반적으로 훨씬 빠르게 동작함
• 이 방식은 최적성을 일부 포기하는 대신 A* 성능을 크게 높이는 Greedy Multiplier 역할을 함
• Weighted A*와 다른 A* 변형은 weighted A* and other A* variants here에서 더 볼 수 있음
• 게임 개발자는 autorouting 개발자와 비슷한 문제를 많이 다루므로, 관련 연구를 찾을 때 게임 개발 논문을 살펴볼 수 있음

공개 예정인 autorouter

• tscircuit용 autorouter는 릴리스에 가까워지고 있음
• 작업물은 MIT 라이선스의 오픈소스로 제공됨
• autorouting 해결은 물리 세계 혁신을 크게 열어줄 수 있고, 전자제품의 “vibe-building”을 가능하게 하는 핵심 조각이라고 봄
• 관련 계정: follow me on twitter.

[GN⁺]

Hacker News 의견들

• 대체로 자동 배선기를 믿지 않는 쪽이고, 이 분야에 들어오는 AI 도구들도 마찬가지지만 eCAD에서 레이아웃 일부를 빠르게 만드는 큰 기회가 있다는 건 부정하기 어려움
  완전 자동 도구보다는 공동 제작형 도구를 더 쓸 것 같음. 설계 초반에는 부품 배치가 확정되지 않은 경우가 많고, 배치가 배선에 큰 영향을 주기 때문임. 페이지에서 배치가 알고리즘에 포함되는지는 못 봤음. 이미 push-and-shove나 가끔 자동 완성 같은 도구는 쓰고 있음
  이 시장은 작고, 도구는 파편화돼 있으며, 기존 업체들은 둔한 거대 기업이고, 사용자들은 까다로운 열성파임. KiCad는 죽어도 못 놓겠음. 자동 배선기가 JavaScript로 작성됐다는 점 자체에는 큰 의견은 없지만, CAD 벤더나 오픈소스 도구 생태계에 붙을 계획인지, 아니면 또 다른 새 생태계로 사람들을 끌어들이려는지 궁금함

  • KiCad 지원은 반드시 할 예정임. 배치도 큰 계획이 있지만, 먼저 아주 빠르고 캐시 친화적인 자동 배선기를 기반으로 삼는 게 중요하다고 봄
    캐시 친화적이면 부품을 옮기고 다른 레이아웃을 시도하는 속도가 훨씬 빨라짐. JavaScript는 이제 QuickJS나 Proffor 같은 작은 런타임까지 있어 꽤 이식성이 좋고, 로컬에서 실행하며 거대한 캐시를 직접 만들 수 있을 것으로 봄
    EDA에서 락인과 생태계 파편화는 모두가 걱정해야 하지만, tscircuit와 이 자동 배선기는 MIT 허용 라이선스 기술이라 EDA에서는 드물게 모두와 상호 운용되도록 만들 수 있음
  • 오래전 사라졌고 그리워할 사람도 별로 없는 OrCAD Layout에는 네트 목록을 스프레드시트처럼 보는 화면이 있었고, 자동 배선 제약을 설정하기에 그럭저럭 괜찮은 인터페이스였음
    풋프린트, 배치, 제약, 수동 배선된 네트를 고정하고 나면 매우 빠르게 반복할 수 있었음
    Cadence가 90년대에 SPECCTRA를 인수한 뒤로 PCB 자동 배선기는 꽤 정체돼 있었는데, 누군가 이 분야를 다시 다루는 건 반가움. SPECCTRA를 만든 사람들은 기억상 VLSI 쪽으로 가서 돌아오지 않았고, 명성과 돈이 거기에 있었던 듯함. 한동안 특허 지뢰밭이었을 수도 있고, 지금도 그럴지 모름
    자동 배치는 당시에도 완전히 다루기 어려운 문제였고 지금도 그래 보이지만, 생성형 AI 접근이 잘 맞을 수 있음. 좋은 생성형 AI 기반 1차 부품 배치는 전체 시간을 줄여줄 수 있음. 가장 큰 문제는 완벽하지 않아도 충분히 좋을 수 있다는 걸 고집 센 사람들에게 설득하는 일임
    코드형 회로도를 하려는 시도들은 좀 의아함. 백엔드 형식으로는 잘 되면 좋겠고, 특히 jitx 쪽처럼 앱노트와 데이터시트 수준의 설계 규칙을 부품 모델에 인코딩하는 진전은 좋아 보임. 상업용 설계에 필요한 수준으로 모든 데이터시트를 읽는 일은 생각보다 훨씬 많은 작업이고, 주니어 엔지니어에게 그 과정을 익히게 하는 것도 마찬가지라 자동화는 유익함
    다만 접근들이 회로도를 레이아웃용 데이터 입력, 일종의 소스 코드로 보는 생각에 뿌리내린 듯함. 회로도는 EDA 제품군이 설치되지 않은 사람도 접근할 수 있어야 하는, 세심하게 진화한 시각 언어를 가진 설계 문서이기도 함. Adafruit/Sparkfun/Shenzhen 스타일처럼 명시적 배선을 최소화한 회로도를 해독하며 배운 사람들은 좋은 회로도의 가치를 잘 모를 수도 있음
    또 하나는 유추에 너무 기대어 PCB 수준 설계를 VLSI 설계처럼 만들려는 경향임. 완전히 불가능하다고 보진 않음. DRC와 검증 도구가 더 좋아지면 부품 수준 설계도 VLSI에 더 가까워질 수 있음. 하지만 설계, EDA/CAM/시뮬레이션, 검증, 제조사, 조립사, 부품 벤더, 규제·인증기관 사이의 결합이 너무 느슨해서, 이 중 한 구석만 제대로 해내도 큰 성과임
  • 자동 배선기가 주는 이득은 보통 나중에 프로젝트 비용으로 돌아오는 경우가 많음
    요즘은 임피던스 제어 UHF 설계를 도메인 특화 시뮬레이션 도구와 함께 진행하는 흐름임. 그래서 중요한 트레이스를 먼저 수동으로 배선하고, 아일랜드 폴을 만들고, 마지막으로 전원 연결을 처리함
    KiCad 레이아웃은 없는 것보다는 조금 낫지만, 또 하나의 어설픈 시뮬레이션 도구로 만들려는 건 우스워 보임
  • 최근 5년간 KiCad 개발은 정말 놀라웠음. 최근 두 릴리스에서 전문 CAD 도구에는 있었지만 KiCad에는 없던 큰 기능 두 가지가 들어갔음
    데이터베이스 지원과 outjob 기능임. 그 외에는 채택과 사용자가 이 기능을 어떻게 활용하느냐의 문제에 가깝고, 데이터베이스는 보통 데이터 정리에 대한 사내 관료주의가 더 많이 따라옴
    레이아웃을 빠르게 하는 워크플로 관점에서 KiCad도 이미 어느 정도 그 방향으로 가고 있지 않나 싶음. 예를 들어 7.0쯤 들어간 “트레이스 자동 완성” 기능이 있음. pcbnew에서 단축키 F였던 것 같은데, 현재 배치 중인 트랙의 트레이스를 깔아줌. “트랙 반대편에서 배선” 단축키 E와 함께 쓰면, 서로 다른 두 볼아웃 그리드 사이에서 작업할 때 생산성이 크게 올라감
    버전 9에서는 버스나 여러 트랙을 드래그할 수 있게 돼 이 흐름이 더 빨라질 수 있음
    솔직히 만족스러운 배치까지 갈 수 있고 자동 배선기에 배선 위치 제약을 줄 수 있다면, 설계의 상당 부분은 자동 배선기에 맡길 수 있을 것 같음. 예를 들어 작년에 NXP iMX8MP와 eMMC를 쓰는 보드를 했는데, 프로세서 주변부 볼아웃이 eMMC 볼아웃과 잘 맞아서 칩을 맞춰 놓고 선을 그리기만 하면 됐음. 데이터 버스를 최상위 레이어에 유지하라는 것만 알았다면 자동 배선기가 10분 걸린 일을 몇 초 만에 했을 것임
    자동 배선기 프로젝트들이 겪는 성공 기준 문제가 있음. 보드의 모든 것을 처리할 수 있어야 “완성”이라고 여기는 듯한데, 실무 전기 엔지니어로서는 그걸 원하지 않음. 설계의 작은 덩어리 하나씩 함께 처리하고, 검토할 시간을 준 뒤 다음 덩어리로 넘어가는 자동 배선기를 원함
    레이어를 넘는 제약까지 줄 수 있으면 강력함. 예를 들어 “D0-7이라는 이름의 모든 네트를 1번과 3번 레이어에 유지하고, 길이를 서로 5mm 이내로 맞추며, D0를 길이 기준으로 삼아라” 같은 식임. 이걸 할 수 있으면 DRAM 길이 튜닝을 해결한 셈이고, 훨씬 넓은 복잡도의 설계가 일반 사용자에게도 가능해짐
    시간이 나면 어떤 의미인지 데모로 보여주고 싶음
  • 자동 배선된 프로토타입 PCB를 가져와 bring-up을 해야 했던 적이 있음. CPU와 DRAM 사이 트레이스가 보드를 세 바퀴 돌고 있었음

• 8번에서 몬테카를로 방법을 너무 빨리 배척한 건 큰 실수임
  몬테카를로의 핵심은 정확도와 속도를 맞바꿀 수 있다는 데 있음. 알고리즘을 오래 돌릴수록 더 정확해짐
  더 흥미로운 건 대우도 자주 쓸 수 있다는 점임. 아주 부정확한 결과를 매우 빠르게 얻을 수 있음. 모든 경로를 탐색하는 대신 무작위로 고른 경로 하나만 탐색하는 식임
  이 방식은 알고리즘의 가장 안쪽 중첩 루프에 넣을 때 빛남. 예를 들어 자동 배선을 배우는 신경망을 학습하려면 바깥 루프는 신경망 매개변수를 갱신하고, 안쪽 루프는 그래프를 통과하는 경로를 계산함
  몬테카를로를 쓰면, 편향이 없다면 정확도를 제어하는 이 안쪽 루프를 1회 반복으로 줄일 수 있음. 분산이 커져 바깥 루프는 느려지겠지만 기계학습은 “이론적으로는” 학습할 수 있음
  그래서 체스나 바둑에서처럼 직관적으로 올바른 결정을 고르는 정책을 만들 수 있음. AlphaGo Zero, AlphaChess Zero, AlphaRouter Zero 같은 몬테카를로 트리 탐색 변형에서, 탐색 부분이 없어도 신경망 매개변수로 인코딩된 거대한 캐시가 학습 후에는 신경망 한 번 통과, 즉 상수 시간에 최선의 추정 경로를 계산할 수 있음. 이 상수는 매개변수를 늘리거나 더 오래 학습시켜 메모리와 속도를 쉽게 맞바꿀 수 있음

  • 글을 읽었을 때 MC를 배척한 부분에서 똑같이 반응했음
    MC는 현실 감각을 잡아주는 알고리즘임. 느리지만 거의 항상 구현이 아주 단순하고, 완전히 엉뚱한 곳으로 벗어나지 않았는지 매우 높은 확신으로 재확인하는 데 믿을 만함
  • 다만 글쓴이는 모의 담금질을 언급했으니, 기울기를 계산하지 않는 SA 특성상 신경망을 시도하던 건 아닐 가능성이 큼

• 자동 배선에 대한 훌륭한 논의인데 마지막에 “전자제품의 vibe-building을 가능하게 하는 핵심 조각”이라고 끝나서 좀 아팠음
  배선 자체는 쉬움. 새 배선을 넣기 위해 이미 깔아둔 걸 뜯어내야 하는 순간 복잡해지고, 조합 폭발이 덮쳐옴
  예전에 KiCad에 있던 자동 배선기가 그리움. 애매한 지식재산권 이유로 빠졌는데, 작성자가 자동 배선 회사에서 일한 적이 있었기 때문임. 다시 넣어달라는 사용자들에게는 “진짜 남자는 자동 배선기를 쓰지 않는다”는 식의 반응이 있었음
  https://forum.kicad.info/t/autorouting-and-autoplacement/185...

  • “vibe-*”에 대한 올바른 반응은 움찔하는 것 같음. 요즘 누가 vibe-coded 앱을 홍보할 때마다 조금씩 움찔하지만, 내가 코딩을 시작하던 시절을 떠올리면 오래된 ActionScript 포럼에서 내 코드를 고쳐달라고 계속 귀찮게 굴었고, 어떤 분야든 사람들이 빠르게 시작할 수 있게 되는 데는 큰 잠재력이 있음
    이 자동 배선기와 뒤따를 다른 도구들도 사람들이 많은 지도나 정규 교육 없이 첫 전자제품을 출시할 수 있게 해주길 바람
    물론 좋은 자동 배선기는 전문가에게도 유용해야 하니 그 부분에도 도움이 되길 바람
  • 이 사람들이 잘되길 바라며, 자동 배선기가 KiCad에 통합되면 좋겠음
    하지만 KiCad가 자동 배선기에 힘을 쓰는 걸 별로 보고 싶지 않은 까다로운 옛사람 중 하나로서, PCB 자동 배선기는 늘 골칫거리이고 제대로 동작하지 않음
    왜 그런지는 VLSI 자동 배선기를 보면 알 수 있음. VLSI 자동 배선기도 골칫거리였고 제대로 동작하지 않았음. 그러다 VLSI에 레이어가 매우 많아졌고, 수직 배선용 레이어, 수평 배선용 레이어, 전원용 레이어를 따로 할당하고도 전역 수직 연결, 전역 수평 연결, 전역 전원용 레이어를 몇 개 더 둘 수 있게 됐음
    PCB 자동 배선의 근본 문제는 PCB가 VLSI 칩보다 장애물이 훨씬 많다는 점임. 첫째, 부품 자체가 장애물이자 병목임. 둘째, PCB 비아는 거의 항상 보드의 모든 레이어를 막지만 VLSI 비아는 연결되는 두 레이어만 막음. 셋째, PCB 비아는 대개 배선 금속 폭보다 큼. 넷째, PCB에서 쓰는 레이어 수는 VLSI보다 훨씬 적음. 흔한 건 4레이어이고, 그중 일반 배선에 제대로 쓰는 건 2개뿐이며, 비용 때문에 2레이어도 많고 자동 배선하기는 더 어렵고, 6레이어는 아주 소수임
    결과적으로 PCB 자동 배선은 VLSI 자동 배선보다 훨씬 더 복잡한 작업임

• 글에서 시각화와 캐시 효과를 특히 중요하게 다룬 점은 좋음
  다만 몇 가지는 걸림. “재귀 알고리즘은 깊이 우선 탐색이고, 후보나 이웃을 정렬하지 않고 탐색하는 루프는 너비 우선 탐색”이라는 말은 틀렸거나 직관을 놓친 것 같음. DFS와 BFS는 둘 다 반복문이나 재귀로 쓸 수 있고, 실제 차이는 다음 후보를 스택의 위에서 꺼내느냐 아래에서 꺼내느냐, 즉 스택(FILO)을 쓰느냐 큐(FIFO)를 쓰느냐임
  A가 모든 정보 기반 탐색의 최고 기반이라는 말도 맥락이 필요함. 목표까지의 계산하기 쉬운 “거리” 개념이 있고 같은 그래프에서 쿼리를 몇 번만 돌릴 때 경로 탐색에 유용함. 도로망처럼 거의 정적인 그래프에서 많은 쿼리를 돌릴 계획이면 contraction hierarchy 같은 전처리 알고리즘이 더 나을 수 있음. 여행하는 외판원 문제처럼 최적화하되 목표가 정해져 있지 않다면 2-opt 같은 다른 지역 탐색 휴리스틱이 더 나을 수 있음
  “BFS는 모든 인접 노드를 탐색하고 A는 목적지에 가까운 노드를 우선한다”는 건 차이이긴 하지만, 더 큰 차이는 A*가 동적 알고리즘이라는 점임. 그래서 최단 경로를 찾았다고 확신하고 일찍 종료할 수 있음. BFS는 전체 그래프를 탐색할 때까지 확신하지 못할 수도 있고, 그래프가 거대할 수 있음

  • 재귀가 DFS에 가깝다는 직관은 사람들이 보통 스택 맨 위와 상호작용하는 구조로 쉽게 매핑될 때 알고리즘을 재귀로 작성하기 때문임
    대부분 언어에서 외부 스택을 가져와 생각하는 것보다 그렇게 표현하기가 쉬움. 그래서 실제 코드에서 재귀를 보면 DFS에 더 가까울 가능성이 크지만, 엄격한 규칙은 아님
  • BFS, DFS, A는 탐색하지 않은 노드를 추적하는 자료구조만 다른 같은 알고리즘으로 볼 수 있음
    BFS는 FIFO 큐, DFS는 LIFO 스택, A는 보통 힙으로 구현한 우선순위 큐를 씀
  • BFS라고 해서 전체 그래프를 반드시 탐색해야 하는 건 아님. 어떤 노드에 처음 도달한 순간 그 경로가 최단 경로임을 100% 알 수 있음
    이것이 BFS가 올바른 결과를 내게 하는 기본 불변식 중 하나라서, 모든 목표에 도달하면 일찍 종료할 수 있음
    A와 BFS의 차이는 BFS가 두 점 사이의 최단 경로가 아니라 단일 시작점에서 그래프의 모든 점까지 최단 경로를 찾는다는 데 있음. A는 더 약한 질문에 답하는 대신 개별 쿼리를 빠르게 하는 절충임
    문제 구조가 허용한다면 수천 번의 A* 호출을 한 번의 BFS나 Dijkstra 호출로 바꾸는 것만으로도 큰 속도 향상을 얻을 수 있음. 또 중요한 차이는 BFS가 모든 간선 길이가 같은 그래프에서만 동작하고, A*는 서로 다른 간선 길이를 지원한다는 점임. 둘은 상호 교체 가능한 게 아니고, 리스트에서 최소 원소 찾기가 리스트 정렬을 대체하지 않는 것과 같음

• “사분 트리와 모든 범용 트리 자료구조는 미친 듯이 느리다”, “트리는 데이터에 대한 정보가 담긴 표현이 아니다”, “트리를 쓸 때마다 O(~1) 해시 알고리즘 대신 더 복잡한 O(log N) 알고리즘을 쓰는 것이다”라는 말은 상당히 잘못된 방향임
  해싱 접근은 점들이 균등하게 분포하고, 선택한 고정 분할에 가까운 영역만 질의할 때는 괜찮음. 그렇지 않으면 그 O(1)은 O(n)으로 무너질 수 있음
  데이터 분포를 모를 때 트리는 정보가 담긴 표현임
  무작위 알고리즘도 비슷함. 탐색 공간이 수조 개 이상의 항목이나 가능성으로 이뤄져 있으면 어떻게 할 것인가? 휴리스틱도 없다면? 무차별 대입도 안 되고 영리한 알고리즘도 못 쓰는 상황에서 무작위 알고리즘은 구원자가 됨
  이 특정 애플리케이션에는 필요 없을 수 있지만, 일반화된 단정은 피하는 편이 좋음

  • 측정, 측정, 측정이 필요함. 모든 경우는 다름
    더 진지하게는 트리 기반 알고리즘이 과대평가되는 경향이 있고, 사람들이 빅오 동작에 너무 빠져 상수 계수가 수십만 개 원소에서도 매우 중요하다는 점을 잊는 것 같음. 데이터 지역성 같은 것도 마찬가지임. 때로는 더 복잡한 구조의 장부 처리를 하는 것보다 순차 스캔으로 그냥 훑는 쪽이 더 빠를 때도 있음
    전체적으로는 연산을 작은 래퍼로 감싸고, 쉬운 구현부터 만든 뒤 측정으로 판단하는 편이 나음
    최악의 경우 더 나은 성능을 노리고 다른 구조에 맞춰 프로그램 전체를 다시 써야 하지만, 경험상 파일을 처음부터 다시 쓰면 공짜 개선도 꽤 따라옴
  • 3D에서는 옥트리가 매우 효과적이고 빨랐음. 내가 구현한 방식에서는 트리를 재생성하지 않고도 항목을 이동할 수 있음
    아직 2D나 3D 점을 저장하고 근처 점을 질의하는 만족스러운 방법은 못 찾았음. kD 트리는 좋지만, 고정된 집합을 두고 구조를 만드는 게 아니라 점을 진행하면서 추가하고 싶음

• 거의 모든 내용이 내 게임 개발 휴리스틱과 맞음. JavaScript를 선택한 것도 이해됨
  지금 Lisp식 S-표현식으로 동작하는 게임 모딩 프레임워크를 만들고 있는데, 창의적 반복 시간을 줄이는 최적화가 무엇보다 중요하다는 걸 알게 됨
  A*, Lee 알고리즘 같은 건 모두 멋짐. 어떤 종류의 flood fill이든 시각화를 함께 만들지 않는 건 범죄에 가까움. 도파민을 너무 낭비하는 셈임
  이 글을 보니 내가 읽지 않았지만 게임 개발 근처에 있는 기법들이 이런 문제에도 쓸모가 있을지 궁금해짐. boids 라우터가 꽤 재미있겠다고 생각한 사람이 내가 처음은 아닐 것임. 더 진지하게는 jump flooding 기반 부호 있는 거리장이 많은 힘을 줄 수 있을 것 같음
  특히 공간 해싱에 대한 내용은 내 경험과 맞음. 거의 20년 동안 트리 구조가 들인 시간만큼 가치 있었던 경우를 많이 못 봤음. 예외가 하나 있는데, 내가 만든 러브크래프트식 텍스트 편집기는 반응성 처리에 trie를 꽤 많이 씀. 45,000개 단어를 이벤트 처리용 압축 상태 기계로 만들기에 좋은 방법이었음

  • boids 라우터를 만드는 건 정말 재미있는 아이디어임. 나중 글감으로 남겨둬야겠음
    예전에 재귀 패턴 자동 배선기에 대해 쓴 적이 있는데, 해답 공간이 작아서 기존 기계학습 알고리즘으로 예측하기 쉬운 편임. 자동 배선에는 아직 탐험되지 않은 흥미로운 영역이 아주 많음
    jump flooding은 몰랐음. 다른 사람들을 위해 덧붙이면 거리장을 빠르게 병렬로 근사하는 알고리즘임. 확실히 흥미로울 수 있겠고, 알려줘서 고마움
  • 과거에는 메모리와 캐시가 더 작아서 트리가 훨씬 유용했을 것 같음. 전처리에도 여전히 유용할 수 있다고 보지만, 고정 격자와 똑똑한 크기 조절을 트리와 직접 벤치마크해봐야 할 듯함
    트리는 재귀 알고리즘에도 잘 맞고, 글쓴이는 반복 알고리즘을 재귀보다 택할 이유가 있다고 했으니 이 조언들은 서로 맞물림
    넓게 보면 “재귀”와 “비재귀” 구분은 다소 인위적임. 진짜 질문은 “엄격한 규칙을 가진 미리 짜인 알고리즘이 흐름 제어를 맡는가, 아니면 내가 맡는가”임. 성능을 많이 신경 쓴다면 답은 내가 맡는 쪽이어야 하고, 실행 환경이 제공하는 스택 속으로 실행 상태가 추상화돼 런타임에 이상하게 바꾸기 어려워지면 방해가 되기 시작함

• “집중의 95%는 반복 횟수를 줄이는 데 써야 한다. 그래서 언어는 중요하지 않다”는 말은 어느 정도 맞지만, 장난스럽고 표현력 좋은 해석형·추상적·느린 언어로 훌륭하고 성능 좋은 알고리즘을 만든 뒤에도 성능이 중요하다면, 같은 걸 성능 좋은 저수준 언어로 다시 쓰고 필요하면 아키텍처별 어셈블리까지 작성하면 됨
  numpy, pandas, OpenCV, TensorFlow가 순수 Python으로 작성되지 않은 데는 이유가 있음. Python은 고성능 C++/어셈블리/CUDA 등으로 구현된 작업을 지시하는 역할을 함
  문제 공간을 탐색하고 효율적인 알고리즘을 찾아 블로그로 썼다는 데 아무리 자부심이 있어도, 순수 Python이나 JavaScript로만 작성하겠다고 고집했다면 인기 있는 수치 계산 라이브러리가 되긴 어려웠을 것임
  재미있는 글이긴 하지만, 글쓴이의 알고리즘 통찰로 순수 JavaScript HEVC 인코더가 프레임당 1일에서 3시간으로 줄었다면 같은 결론을 내리긴 어려웠을 것 같음

• 대학 때 기억하던 키워드가 잔뜩 보임. 유명하고 멋진 알고리즘을 쓸 일이 있으면 좋겠음
  실제로는 UI 컴포넌트와 REST API를 만들어 Elasticsearch 결과를 보여주는 일만 하고 있음. 재미있는 것들은 전부 블랙박스 안에 묻혀 있음

  • LLM이 기하 휴리스틱을 다 외우고 있어서 요즘은 알고리즘이 훨씬 재미있어졌음
    게임 개발에서는 피할 수 없는 알고리즘이 많으니, 알고리즘을 만들고 싶다면 타워 디펜스 같은 걸 만들어보면 고전 알고리즘을 많이 다루게 됨
  • 핵심 문제는 학계 커리큘럼과 실제 채용 시장 수요 사이의 심각한 불일치, 그리고 회사들이 위험을 걸러내고 ADA/차별금지법을 우회하기 위한 대리 지표로 “대학 학위 필요”를 쓰는 데 있음. 둘 다 경제에 큰 낭비임
    최소한 현재의 컴퓨터과학 학위는 쪼개야 한다고 봄. 멋진 수학 쪽은 별도 학위가 되어야 하고 AI 관련 새 학위와 합쳐질 수도 있음. 데이터베이스와 네트워크 이론도 별도 학위가 되어야 하며, 저수준 어셈블리도 마찬가지임. 전자 부품, NAND 게이트, 불 대수 등이 어떻게 동작하는지는 전자공학으로 옮기는 게 맞음
    시장이 가장 많이 필요로 하는, CRUD 앱을 찍어낼 수 있는 사람은 학문적 지식이 꼭 필요하다고 우긴다면 별도 학위로 만들거나, 직업교육 쪽으로 옮겨야 함
    동시에 채용 요건의 문지기도 법으로 다뤄야 함. 실제 직무와 거의 관련 없는 학위를 요구하지 못하게 해야 함. 지금은 아이들이 인생의 몇 년을 낭비하고 다섯 자리에서 여섯 자리 달러의 빚을 지게 만들며, 오직 회사가 사람을 걸러내기 쉽게 해주고 있음

• 2D/3D 공간 문제를 직접 다루지는 않지만, 가장 큰 교훈은 시각화의 가치임
  인간은 그림을 이해하고 분석하는 데 매우 뛰어남. 또 하나는 확률적 방법이나 무차별 대입으로 문제의 모양을 먼저 파악한 뒤, 순수 이론적 이해만이 아니라 그에 맞춰 더 나은 방법을 고르는 아이디어임

• “구현 언어는 중요하지 않다”는 말은 이 분야에서는 맞을지도 모르겠지만, 일반적인 소프트웨어 공학에 적용하면 언어 선택이 속도와 필요한 반복 횟수에 영향을 주지 않는다는 가정은 크게 틀렸다고 봄

  • 빅오 수준의 알고리즘 개선을 쫓는 동안에는 빠르거나 느린 언어 실행이 만드는 유효 상수항이 성급한 최적화일 수 있다는 주장은 타당함
    지수항이나 다항항을 통제하려는 단계라면 Rust나 하드코딩 어셈블리와 JavaScript나 VisualBasic의 차이는 꽤 무의미해질 수 있음
  • JavaScript가 자동 배선기를 소규모 설계나 매우 긴 처리 시간 쪽으로 제한할 수도 있다고 생각하지만, tscircuit를 써본 적은 없어서 틀릴 수도 있음