Những điều tôi ước mình biết trước khi phát triển autorouter

"Những bài học quan trọng để tạo ra bộ tự động đi dây (Autorouter) nhanh nhất thế giới"

Dùng thuật toán A* ở mọi nơi

• A* là một trong những thuật toán mạnh mẽ và linh hoạt nhất cho các bài toán tìm kiếm
• Có thể dùng không chỉ trên lưới 2D đơn giản mà còn cho nhiều loại bài toán khác nhau
• So với BFS, A* nhanh và hiệu quả hơn vì ưu tiên khám phá các nút gần đích hơn theo kiểu 'tìm kiếm có thông tin'
• DFS hoặc BFS đang dùng trong mã hiện có phần lớn đều có thể được thay thế bằng A*
• Để cải thiện hiệu năng, có thể chạy nhiều instance A* và phân bổ thêm tài nguyên cho cấu hình cho kết quả tốt hơn

Thuật toán quan trọng hơn ngôn ngữ lập trình

• Việc phát triển autorouter bằng Javascript hoàn toàn không gặp vấn đề gì
• Cốt lõi của tối ưu hóa là giảm số lần lặp
• Quan trọng hơn hiệu năng ngôn ngữ là “bạn có thể tạo ra một thuật toán thông minh đến mức nào và nhanh đến đâu”
• Javascript phù hợp hơn với các thuật toán thông minh so với việc chỉ dựa vào lặp nhanh

Spatial Hash Indexing hiệu quả hơn cấu trúc cây

• Các cấu trúc dữ liệu dạng cây như Quadtree nhìn chung thường chậm
• Spatial Hash Index nhóm và xử lý các đối tượng ở gần nhau trong không gian bằng cách băm vị trí của chúng
• Cấu trúc dựa trên hash mang lại hiệu năng truy vấn gần mức O(1)
• Cần chọn kích thước cell phù hợp để phát huy hiệu quả, nhưng việc chọn kích thước thích hợp không quá khó

Phân vùng không gian và cache quan trọng hơn thuật toán 1000 lần

• Ngay cả các bảng mạch phức tạp cũng chủ yếu có những mẫu lặp lại
• Tương tự phát triển game, có thể cache các kết quả tính trước để cải thiện hiệu năng một cách đột phá
• Cấu trúc có thể cache và phân vùng không gian sẽ là cốt lõi của autorouter trong tương lai
• Chi phí lưu trữ đang giảm rất nhanh, và chỉ với vài GB cache cũng có thể cải thiện hiệu năng lớn

Không có trực quan hóa thì không thể giải quyết vấn đề

• Với mọi vấn đề, tôi đều bắt đầu bằng cách tạo công cụ trực quan hóa trước
• Nhờ trực quan hóa, có thể tăng tốc độ debug lên hơn 10 lần
• Ngay cả các bước thuật toán đơn giản, khi được trực quan hóa, cũng giúp nhanh chóng xác định nguyên nhân vấn đề

Công cụ profiling của Javascript cực kỳ hữu ích

• Trong tab Performance của Chrome DevTools, có thể xem thời gian tiêu tốn của từng đoạn mã
• Không cần framework riêng vẫn có thể dễ dàng phân tích Flame Chart, mức dùng bộ nhớ và nhiều thứ khác
• Đây là công cụ rất hữu ích cho việc debug hiệu năng

Đừng dùng hàm đệ quy

• Hàm đệ quy thường mang tính đồng bộ và khó chuyển sang A*
• Cách triển khai dựa trên lặp nhanh hơn và dễ theo dõi các nút đã thăm hơn
• Trong hàm đệ quy, việc thay đổi trạng thái khó khăn và kém hiệu quả
• Hãy viết theo hướng dùng vòng lặp bất cứ khi nào có thể

Nên tránh các thuật toán Monte Carlo

• Thuật toán dựa trên tính ngẫu nhiên là không xác định và khó debug
• Các heuristic chuyên biệt theo domain luôn cho hiệu năng tốt hơn
• Không có nhà thiết kế PCB nào vẽ dây ngẫu nhiên → đây không phải cách tiếp cận thực tế
• Tuy vậy, ở giai đoạn đầu, chúng vẫn có thể hữu ích để lấy cảm giác ban đầu

Hãy gắn các bước thuật toán vào không gian bài toán thực tế

• Nếu chuẩn hóa các thuật toán con về gốc tọa độ, sẽ khó nắm được luồng tổng thể
• Bằng cách trực quan hóa đầu vào và đầu ra của từng bước, có thể xác định bước nào gây lỗi
• Điều quan trọng là duy trì hệ tọa độ nhất quán cùng với luồng của thuật toán

Hãy trực quan hóa quá trình lặp bằng hoạt ảnh

• Có thể nhìn thấy một cách trực quan thuật toán đang tìm kiếm kém hiệu quả đến mức nào
• Hoạt ảnh rất hiệu quả trong việc giảm số lần lặp và tăng hiệu quả
• Dễ dàng phát hiện các tình huống có vấn đề (ví dụ: tìm kiếm rơi vào vòng lặp vô hạn)

Không cần lưới, chỉ với toán học kiểm tra giao cắt là đủ

• Dùng toán học vector thay cho lưới sẽ nhanh hơn nhiều
• Trong nhiều trường hợp, phép toán số học còn nhanh hơn truy cập bộ nhớ
• Nhờ LLM, việc triển khai toán học kiểm tra giao cắt cũng trở nên dễ dàng hơn
• Việc dùng lưới không cần thiết là nguyên nhân làm giảm hiệu năng

Có thể ưu tiên khả năng giải quyết bằng cách đo xác suất thất bại ở từng bước

• Có thể ước tính xác suất thất bại tại mỗi node phân vùng không gian
• Sau đó ưu tiên tái cấu trúc hoặc tìm kiếm lại các node có khả năng thất bại cao ở các bước sau
• Xác suất thất bại có thể được đo rõ ràng và có tiềm năng cải thiện lớn hơn heuristic
• Việc tăng xác suất giải được toàn cục có thể hiệu quả hơn là chỉ nhắm đến tối ưu hóa

Có thể tăng tốc 100 lần với Weighted A*

• A* cơ bản đảm bảo đường đi tối ưu nhưng tốc độ chậm
• Weighted A* có thể cải thiện tốc độ rất lớn bằng cách tìm kiếm tham lam hơn
• Có thể triển khai chỉ bằng cách đặt trọng số theo công thức f(n) = g(n) + w * h(n)
• Dù phải đánh đổi một chút về tính tối ưu, vẫn có thể giải bài toán nhanh hơn rất nhiều
• Đây cũng là kỹ thuật thường được dùng trong phát triển game và rất đáng tham khảo

[GN⁺]

Ý kiến Hacker News

• Việc nhanh chóng gạt bỏ phương pháp Monte-Carlo là một sai lầm lớn

  • Điểm đặc trưng của phương pháp Monte-Carlo là có thể đánh đổi giữa độ chính xác và tốc độ
  • Chạy thuật toán càng lâu thì kết quả càng chính xác
  • Ngược lại, cũng có thể nhanh chóng nhận được kết quả kém chính xác
  • Thay vì duyệt mọi đường đi, nó chỉ duyệt một đường đi được chọn ngẫu nhiên
  • Sử dụng Monte-Carlo ở vòng lặp lồng sâu nhất của thuật toán sẽ rất hiệu quả
  • Ví dụ, khi huấn luyện mạng nơ-ron, vòng lặp bên ngoài cập nhật các tham số của mạng, còn vòng lặp bên trong tính toán đường đi qua đồ thị
  • Dùng Monte-Carlo có thể giảm độ chính xác của vòng lặp bên trong xuống còn 1 lần lặp
  • Điều này trực giác cho phép xây dựng một chính sách luôn đưa ra quyết định đúng
  • Trong cờ vua hay cờ vây, có thể dùng các biến thể của Monte-Carlo tree search để tính đường đi tối ưu

• Có quan điểm rằng "đừng tin autorouter"

  • Trong lĩnh vực eCAD có cơ hội lớn để tăng tốc độ bố trí layout
  • Có khả năng sẽ dùng các công cụ đồng sáng tạo hơn là công cụ tự động hóa hoàn toàn
  • Khi bắt đầu thiết kế, việc bố trí chưa được thiết lập nên ảnh hưởng lớn tới routing
  • Không thể xác nhận từ trang đó liệu bố trí có phải là một phần của thuật toán hay không
  • Tò mò về kế hoạch cho AR được viết bằng JavaScript

• Bài viết đề cập đến những điểm quan trọng về trực quan hóa và hiệu ứng cache

  • Thuật toán đệ quy là duyệt theo chiều sâu
  • DFS và BFS có thể được viết theo kiểu lặp hoặc đệ quy
  • A* hữu ích cho việc tìm đường
  • BFS duyệt tất cả các nút kề, còn A* ưu tiên các nút gần đích hơn
  • A* là một thuật toán động, có thể tự tin kết thúc sớm để tìm đường đi ngắn nhất

• Đây là một cuộc thảo luận tuyệt vời về autorouting

  • Bản thân việc routing là dễ
  • Nó trở nên phức tạp khi phải gỡ bỏ những gì đã được route để nhường chỗ cho cái mới
  • Nhớ autorouter của KiCAD

• 95% trọng tâm nên đặt vào việc giảm số lần lặp

  • Nếu hiệu năng vẫn còn quan trọng thì nên viết lại bằng ngôn ngữ mức thấp
  • numpy, pandas, OpenCV, TensorFlow đều được triển khai bằng C++/assembly/CUDA hiệu năng cao

• QuadTree và các cấu trúc dữ liệu cây nói chung rất chậm

  • Cây không phải là cách biểu diễn thông tin của dữ liệu
  • Cách tiếp cận bằng hashing chỉ phù hợp khi các điểm phân bố đồng đều
  • Thuật toán ngẫu nhiên hữu ích khi không gian tìm kiếm rất lớn

• Gần như mọi thứ đều khớp với các heuristic trong phát triển game

  • A*, thuật toán của Lee, v.v. đều rất tuyệt
  • Viết flood fill mà không có trực quan hóa là một tội ác
  • Spatial hashing đặc biệt khớp với kinh nghiệm

• "Lập chỉ mục bằng spatial hash > cấu trúc dữ liệu cây" là đúng trong miền này, nhưng không nên được xem là chân lý phổ quát

  • Nếu các điểm không phân bố đồng đều thì hàm băm có thể kém hiệu quả

• Nhớ lại các từ khóa đã học ở đại học

  • Không có cơ hội dùng các thuật toán fancy
  • Thay vào đó lại xây dựng các thành phần UI và REST API

• Với tư cách là người không trực tiếp làm việc với các bài toán không gian 2D/3D, bài học lớn nhất là giá trị của trực quan hóa

  • Con người rất giỏi trong việc hiểu và phân tích hình ảnh
  • Ý tưởng dùng các phương pháp xác suất hoặc brute-force để hiểu hình dạng của vấn đề là rất quan trọng