Hal-hal yang seandainya saya ketahui sebelum mengembangkan autorouter

"Pelajaran penting untuk membuat automatic router (Autorouter) tercepat di dunia"

Terapkan algoritme A* di mana-mana

• A* adalah algoritme yang paling kuat dan fleksibel untuk masalah pencarian
• Bisa digunakan bukan hanya pada grid 2D sederhana, tetapi juga pada berbagai jenis masalah
• Dibanding BFS, A* lebih cepat dan efisien karena memprioritaskan penelusuran node yang lebih dekat ke tujuan sebagai bentuk 'pencarian berbasis informasi'
• DFS atau BFS yang digunakan dalam kode yang sudah ada pada umumnya dapat digantikan dengan A*
• Untuk meningkatkan performa, digunakan teknik menjalankan beberapa instance A* lalu mengalokasikan lebih banyak sumber daya ke konfigurasi yang menunjukkan hasil lebih baik

Algoritme lebih penting daripada bahasa pemrograman

• Tidak ada masalah sama sekali meskipun autorouter dikembangkan dengan Javascript
• Inti optimisasi adalah mengurangi jumlah iterasi
• Yang lebih penting daripada performa bahasa adalah “seberapa cerdas algoritme yang bisa dibuat, dan seberapa cepat Anda bisa membuatnya”
• Javascript lebih menguntungkan untuk algoritme yang cerdas daripada sekadar iterasi yang cepat

Spatial Hash Indexing lebih efisien daripada struktur tree

• Struktur data berbasis tree seperti Quadtree umumnya lambat
• Spatial Hash Index meng-hash posisi objek lalu memproses objek yang berdekatan secara spasial dalam kelompok yang sama
• Struktur berbasis hash memberikan performa pencarian yang mendekati O(1)
• Efektivitasnya bergantung pada pemilihan ukuran cell yang tepat, dan memilih ukuran yang sesuai tidak terlalu sulit

Pembagian ruang dan cache 1000 kali lebih penting daripada algoritme

• Bahkan papan sirkuit yang kompleks pun sebagian besar memiliki pola yang berulang
• Seperti dalam pengembangan game, hasil yang telah dipra-hitung bisa di-cache untuk meningkatkan performa secara drastis
• Struktur yang dapat di-cache dan pembagian ruang akan menjadi inti autorouter masa depan
• Biaya penyimpanan terus turun dengan cepat, dan cache beberapa GB saja bisa memberi peningkatan performa yang besar

Mustahil menyelesaikan masalah tanpa visualisasi

• Untuk setiap masalah, pembuatan alat visualisasi selalu dilakukan terlebih dahulu
• Melalui visualisasi, kecepatan debugging bisa ditingkatkan lebih dari 10 kali lipat
• Bahkan tahap algoritme yang sederhana pun, jika divisualisasikan, memungkinkan penyebab masalah ditemukan dengan cepat

Alat profiling Javascript sangat berguna

• Di tab Performance pada Chrome Developer Tools, Anda bisa melihat waktu yang dihabiskan untuk tiap bagian kode
• Bahkan tanpa framework tambahan, Flame Chart, penggunaan memori, dan metrik lainnya bisa dianalisis dengan mudah
• Ini adalah alat yang sangat berguna untuk debugging performa

Jangan gunakan fungsi rekursif

• Fungsi rekursif pada umumnya bersifat sinkron dan sulit dialihkan ke A*
• Implementasi berbasis iterasi lebih cepat dan lebih mudah untuk melacak node yang sudah dikunjungi
• Dalam fungsi rekursif, perubahan state sulit dilakukan dan tidak efisien
• Sebisa mungkin, tulislah dengan basis loop/iterasi

Sebaiknya hindari algoritme Monte Carlo

• Algoritme berbasis keacakan bersifat non-deterministik dan sulit di-debug
• Heuristik yang spesifik terhadap domain selalu memberikan performa yang lebih baik
• Tidak ada desainer PCB yang menggambar jalur secara acak → ini bukan pendekatan yang realistis
• Namun, pada tahap awal algoritme ini bisa berguna untuk mendapatkan intuisi

Kaitkan setiap tahap algoritme ke ruang masalah yang nyata

• Jika sub-algoritme dinormalisasi berdasarkan titik origin, alur keseluruhan akan sulit dipahami
• Dengan memvisualisasikan input dan output di setiap tahap, bisa diketahui tahap mana yang menimbulkan kesalahan
• Menjaga sistem koordinat tetap konsisten sambil mempertahankan alur algoritme adalah hal yang penting

Visualisasikan proses iteratif dalam bentuk animasi

• Anda bisa melihat secara visual seberapa tidak efisien algoritme melakukan pencarian
• Animasi sangat efektif untuk mengurangi jumlah iterasi dan meningkatkan efisiensi
• Situasi bermasalah bisa dengan mudah ditangkap (misalnya pencarian yang terjebak dalam loop tak berhingga)

Tanpa grid pun matematika deteksi perpotongan sudah cukup

• Daripada memakai grid, menggunakan matematika vektor jauh lebih cepat
• Dalam banyak kasus, operasi matematika bahkan lebih cepat daripada akses memori
• Berkat LLM, matematika untuk deteksi perpotongan juga menjadi jauh lebih mudah diimplementasikan
• Penggunaan grid yang tidak perlu adalah penyebab turunnya performa

Ukur probabilitas kegagalan di tiap tahap untuk memprioritaskan kemungkinan penyelesaian

• Probabilitas kegagalan dapat diperkirakan pada setiap node pembagian ruang
• Setelah itu, node yang kemungkinan besar akan gagal pada tahap berikutnya diprioritaskan untuk dikonstruksi ulang atau ditelusuri ulang
• Probabilitas kegagalan bisa diukur dengan jelas dan memiliki potensi perbaikan yang lebih besar daripada heuristik
• Meningkatkan peluang keseluruhan untuk menyelesaikan masalah bisa jadi lebih efektif daripada sekadar mengejar optimisasi

Weighted A* bisa meningkatkan kecepatan hingga 100 kali

• A* dasar menjamin jalur optimal, tetapi kecepatannya lambat
• Weighted A* melakukan pencarian secara lebih rakus sehingga kecepatan bisa meningkat drastis
• Bisa diimplementasikan hanya dengan mengatur bobot melalui f(n) = g(n) + w * h(n)
• Meski sedikit mengorbankan optimalitas, masalah dapat diselesaikan jauh lebih cepat
• Ini juga merupakan teknik yang sering digunakan dalam pengembangan game dan layak dijadikan referensi

[GN⁺]

Komentar Hacker News

• Mengabaikan metode Monte-Carlo terlalu cepat adalah kesalahan besar

  • Ciri khas metode Monte-Carlo adalah dapat menukar akurasi dengan kecepatan
  • Semakin lama algoritme dijalankan, semakin akurat hasilnya
  • Sebaliknya, hasil yang cepat tetapi tidak akurat juga bisa diperoleh
  • Alih-alih menjelajahi semua jalur, metode ini hanya menjelajahi satu jalur yang dipilih secara acak
  • Menggunakan Monte-Carlo pada loop terdalam algoritme itu efektif
  • Misalnya, saat melatih jaringan saraf, loop luar memperbarui parameter jaringan saraf dan loop dalam menghitung jalur melalui graf
  • Dengan Monte-Carlo, akurasi loop dalam dapat diturunkan menjadi 1 iterasi
  • Ini secara intuitif memungkinkan pembangunan kebijakan yang selalu membuat keputusan yang benar
  • Dalam catur atau go, varian Monte-Carlo tree search dapat digunakan untuk menghitung jalur optimal

• Ada di kubu "jangan percaya autorouter"

  • Ada peluang besar di bidang eCAD untuk meningkatkan kecepatan layout
  • Kemungkinan besar akan digunakan alat ko-kreasi ketimbang alat otomasi penuh
  • Pada awal desain, penempatan belum ditetapkan sehingga sangat memengaruhi routing
  • Dari halaman itu, tidak jelas apakah placement merupakan bagian dari algoritme
  • Penasaran dengan rencana untuk AR yang ditulis dalam JavaScript

• Artikelnya menyebut poin penting tentang visualisasi dan efek cache

  • Algoritme rekursif adalah depth-first search
  • DFS dan BFS dapat ditulis secara iteratif maupun rekursif
  • A* berguna untuk pencarian jalur
  • BFS menjelajahi semua node tetangga, sedangkan A* memprioritaskan node yang lebih dekat ke tujuan
  • A* adalah algoritme dinamis yang dapat dihentikan lebih awal dengan keyakinan bahwa jalur terpendek telah ditemukan

• Ini pembahasan yang sangat bagus tentang autorouting

  • Routing itu sendiri mudah
  • Menjadi rumit ketika hal yang sudah dirouting harus dihapus agar sesuatu yang baru bisa dimasukkan
  • Merindukan autorouter KiCAD

• 95% fokus seharusnya diarahkan untuk mengurangi jumlah iterasi

  • Jika performa masih penting, harus ditulis ulang dalam bahasa tingkat rendah
  • numpy, pandas, OpenCV, TensorFlow diimplementasikan dalam C++/assembly/CUDA berperforma tinggi

• QuadTree dan struktur data tree pada umumnya sangat lambat

  • Tree bukan representasi informasi dari data
  • Pendekatan hashing hanya cocok jika titik-titik terdistribusi merata
  • Algoritme acak berguna ketika ruang pencarian sangat besar

• Hampir semuanya selaras dengan heuristik dalam pengembangan game

  • A*, algoritme Lee, dan sebagainya semuanya keren
  • Menulis flood fill tanpa visualisasi adalah kejahatan
  • Spatial hashing sangat sesuai dengan pengalaman, khususnya

• "indeks hash spasial > struktur data tree" bagus untuk domain ini, tetapi tidak boleh diterima sebagai kebenaran universal

  • Jika titik-titik tidak terdistribusi merata, fungsi hash bisa menjadi buruk

• Masih ingat kata kunci yang dipelajari di universitas

  • Tidak pernah punya kesempatan menggunakan algoritme yang fancy
  • Sebaliknya, yang dibangun adalah komponen UI dan REST API

• Sebagai orang yang tidak terlibat langsung dalam masalah ruang 2D/3D, pelajaran terbesar adalah nilai visualisasi

  • Manusia sangat unggul dalam memahami dan menganalisis gambar
  • Gagasan menggunakan metode probabilistik atau brute-force untuk memahami bentuk masalah itu penting