fastroute: KiCad için Hızlı, Açık Kaynak PCB Otomatik Yönlendirici (Freerouting'i Rust'a Taşımak)

Bir baskı devre kartını (PCB) tasarlamanın en uzun süren kısmı çoğu zaman yollamadır: yüzlerce bağlantının, birbirine belirli bir mesafeden fazla yaklaşmadan, katmanlar arasında via'larla geçerek bakır izlere dönüşmesi. KiCad kullananların bu iş için yıllardır başvurduğu açık kaynak araç Freerouting, Java ile yazılmış bir otomatik yönlendirici (autorouter). fastroute, Freerouting'in Rust'a taşınmış hâli: aynı algoritmalar, aynı giriş ve çıkış (Specctra .dsn → .ses), aynı komut satırı; ama Java olmadan, birkaç kat daha hızlı ve belleğin küçük bir kısmıyla.

Bu yazıda projeyi baştan sona anlatacağım: neden ve nasıl taşıdığımı, Java ile "bayt bayt aynı" sonuç üretmenin ne demek olduğunu, sonucu değiştirmeden yapılan hızlandırmaları, düzeltilen hataları ve Freerouting'de olmayan yeni özellikleri (uzunluk eşitleme, diferansiyel çiftler, kontrollü empedans, canlı izleme). Yazıdaki canlı izleme ekran görüntülerini projeyi kendi makinemde çalıştırarak aldım; ölçümlerin hangisinin benim, hangisinin projenin dokümanlarından olduğunu her yerde belirttim.

Proje sitesi: fastroute.baltavista.com · kaynak kod: github.com/parisxmas/fastroute. (İsim benzerliğine dikkat: entegre devre tasarımında OpenROAD'un kullandığı FastRoute global yönlendiricisiyle ilgisi yok.)

Neden Freerouting'i yeniden yazmak?

Freerouting iyi bir yönlendirici; yıllar içinde olgunlaşmış, birçok gerçek kartta denenmiş algoritmaları var. Ama kullanırken üç şey sürekli karşıma çıktı:

1. Java. KiCad eklentisini kullanmak için ayrı bir Java çalışma zamanı gerekiyor; kurulum, sürüm uyumsuzlukları ve büyük kartlarda gigabaytlarca bellek.
2. Hız. Orta büyüklükteki bir kart dakikalar, büyük bir kart saatler sürebiliyor.
3. Hatalar. Kodu okudukça, sonucu doğrudan etkileyen ve yıllardır orada duran hatalar buldum. Örneğin otomatik yönlendirici kendi kendini durdurduğunda optimizer hiç çalışmıyor, çünkü durdurma isteği açık kalıyor ve her optimizer adayı "durduruldu" diye başarısız oluyor.

Sıfırdan yeni bir yönlendirici yazmak yerine Freerouting'i birebir taşımayı seçtim. Bunun en büyük avantajı ölçülebilir olması: taşıma doğru mu sorusunun kesin bir cevabı var. Aynı kartı aynı ayarlarla verdiğinizde Java ile aynı çıktıyı üretiyorsa doğrudur. Hızlandırmaları ve iyileştirmeleri ancak bu sağlam zeminin üstüne koydum.

Proje yapısı

fastroute bir Cargo çalışma alanı; yaklaşık 70 bin satır Rust ve KiCad eklentisi için yaklaşık 2.400 satır Python:

Taşıma aşağıdan yukarı birimler hâlinde ilerledi: önce Java uyumluluk katmanı, veri yapıları, kurallar ve kütüphane; sonra kart nesneleri ve arama ağaçları (~13 bin Java satırı), DRC ve puanlama, optimizasyon ve yönlendirme kartı, otomatik yönlendirme çekirdeği (genişleme odaları, labirent araması, yol bulma) ve en son işlem hattı. Projenin ilk commit'i 27 Eylül'de; 82 commit sonra 7 Ekim'de 0.1.13 sürümü çıktı.

"Bayt bayt aynı" ne demek?

--parity modunda fastroute, Freerouting'in deterministik modunun (tek iş parçacıklı optimizer, sayaç tabanlı süre sınırları) ürettiği SES dosyasını bayt bayt aynı üretiyor. Bu iddiayı yazmadan önce kendim denedim. KiCad demolarından interf_u kartını Apple M4 makinemde fastroute 0.1.13 ile --parity modunda yönlendirdim ve çıktıyı projede saklanan Java referans çıktısıyla karşılaştırdım:

$ fastroute -de interf_u.dsn -do interf.ses --parity
...
   12.563 INFO  routing finished in 12.55 s

$ cmp reference/parity-baseline/interf_u.ses interf.ses && echo IDENTICAL
IDENTICAL
$ shasum -a 256 reference/parity-baseline/interf_u.ses interf.ses
2e174236513ccab65daa…  reference/parity-baseline/interf_u.ses
2e174236513ccab65daa…  interf.ses

Bunu sağlamak, algoritmaları doğru taşımaktan çok daha fazlasını gerektiriyor. Yönlendiricinin sonucu, Java'nın standart kütüphanesinin en ince davranışlarına bağlı. Örneğin:

• Rastgele sayılar. Optimizer ve sıralama karıştırmaları java.util.Random ve Collections.shuffle kullanıyor. Aynı sırayı üretmek için 48 bitlik doğrusal eşlik üretecinin ve nextInt(bound)'un taşmaya dayanan reddetme döngüsünün birebir aynısı gerekiyor.
• Geçişsiz karşılaştırıcılar. Bazı yerlerde Java'nın TreeMap'i, matematiksel olarak geçişli olmayan karşılaştırıcılarla kullanılıyor. Sonuç, ağacın kırmızı-siyah yapısına göre değişiyor; bu yüzden TreeMap kendi başına, aynı dengeleme kurallarıyla yeniden yazıldı.
• Hash sırası. HashMap<Integer, …> üzerinde yinelemenin sırası tek bir yerde sonucu etkiliyor; o yerde Java'nın iterasyon sırası taklit ediliyor.
• Kayan noktalı sayılar. İşlem sırası korunuyor, mul_add (birleşik çarp-topla) kullanılmıyor; puanlar Java'daki gibi f32 ile ve aynı dönüşümlerle hesaplanıyor; DoubleStream.sum'un telafili toplaması ve trigonometri için fdlibm (libm) kullanılıyor.
• Metin karşılaştırma. String.compareTo UTF-16 kod birimleri üzerinden çalışıyor.
• Arama ağacının şekli. Bazı geometrik sorgular ağacı kendileri yürüyor ve yürürken sorguyu küçültüyor; ziyaret sırası üretilen odaları değiştiriyor. Bu yüzden Rust'taki MinAreaTree, Java'daki ağacın tam şeklini yeniden üretiyor.

İşte fr-jcompat içindeki java.util.Random taşımasından bir parça. Java'nın tamsayı taşmasına dayanan reddetme koşulu, Rust'ta wrapping_sub ve wrapping_add ile açıkça yazılıyor:

/// `protected int next(int bits)`, `1 <= bits <= 32`.
#[inline]
pub fn next(&mut self, bits: u32) -> i32 {
    debug_assert!((1..=32).contains(&bits));
    self.seed = self.seed.wrapping_mul(Self::MULTIPLIER).wrapping_add(Self::ADDEND) & Self::MASK;
    // (int) (nextseed >>> (48 - bits))
    ((self.seed as u64) >> (48 - bits)) as i32
}

/// `Random.nextInt(int bound)`. Panics if `bound <= 0` (Java throws `IllegalArgumentException`).
pub fn next_int_bound(&mut self, bound: i32) -> i32 {
    assert!(bound > 0, "bound must be positive");
    let mut r = self.next(31);
    let m = bound - 1;
    if (bound & m) == 0 {
        // power of two
        r = ((bound as i64 * r as i64) >> 31) as i32;
    } else {
        let mut u = r;
        loop {
            r = u % bound;
            // Java relies on int overflow to reject values from the incomplete last range.
            if u.wrapping_sub(r).wrapping_add(m) >= 0 {
                break;
            }
            u = self.next(31);
        }
    }
    r
}

Doğruluk katman katman sınandı: yüklemeden sonra kartın kanonik dökümü, istatistiklerin bit düzeyinde eşitliği, bağlantı başına iz işaretleri, tur başına hash ve puan, en sonda da SES farkı. İlk büyük kilometre taşı, yönlendirme kapalıyken yazılan "yönlendirilmemiş" SES'in 20 karşılaştırma kartının hepsinde Java ile aynı olmasıydı; DSN okuyucu da 2.470 örnek dosyayla sınandı. Sonra tam işlem hattı geldi: --parity modunda 20 kartın 20'si Java ile bayt bayt aynı.

Bilinçli olarak taşınmayan tek şey Java'daki DSN okuyucu hataları. JFlex tarayıcısı, örnek dosyaların 12'sinde adlardaki ASCII dışı harfleri düşürüyor, bazı tırnaklı metinlerde senkronu kaybediyor ya da bir pin adının bir karakterini bir sonraki pine kaydırıyor. fastroute bunları doğru okuyor; o kartlar bu yüzden Java ile karşılaştırılamıyor.

Canlı izleme

Freerouting'de olmayan ilk şey: kartın yönlendirilişini tarayıcıda izlemek. --live ile fastroute, internet gerektirmeyen yerel bir sayfa açıyor. İzlerin belirişi ve sökülüşü, kalan bağlantılar (airlines), her turun ilerlemesi, tur başına kalan bağlantı grafiği, mesafe ihlalleri, puan ve günlük orada. Yakınlaştırma, katman açma/kapama, ağ (net) vurgulama ve en iyi sonucu saklayarak durduran bir "Stop" düğmesi var. Sonuçlar canlı izlemeyle de izlemesiz de aynı.

Yukarıdaki kare, interf_u kartının 4. turundan. Yeşil izler o turda yeni yerleştirilenler, beyaz çizgiler henüz yönlenmemiş bağlantılar. 159 bağlantıyla başlayan kart ilk turda 20'nin altına iniyor; sağdaki grafik bunu gösteriyor. Kapak görselindeki son durumda 159 bağlantının hepsi yönlenmiş, ihlal yok.

Daha zor bir örnek olarak 6 katmanlı CM5_MINIMA_3 kartını (bir Raspberry Pi Compute Module 5 taşıyıcı kartı) çalıştırdım. Bu kart tamamen yönlenemiyor. fastroute kalan bağlantılar için çoklu başlangıç (multi-start) aşamasında farklı sıralamalarla paralel olarak yeniden deniyor:

Çalışma benim makinemde 41 saniyede bitti ve 88 bağlantıdan 7'si kaldı. Bu, projenin dokümanındaki "CM5: 8 → 7 yönlenmemiş" iyileştirmesiyle birebir aynı; kalan tek ihlal ise yüklenen tasarımda zaten var olan, sabit iki öğe arasındaki bir ihlal.

Sonucu değiştirmeden hızlandırmak

Taşıma doğru çalıştıktan sonra hızlandırma başladı. Kural basitti: hiçbir adım sonucu değiştiremez. Her adımdan sonra tüm testler, 10 kartta tam işlem hattı ve paralel optimizerin 1 ve 8 iş parçacığıyla aynı sonucu verdiği kontrol edildi. FASTROUTE_VERIFY_CACHES=1 ile her önbelleğe alınmış ya da indekslenmiş sonuç eski yoldan da hesaplanıp karşılaştırılıyor. Öne çıkan adımlar:

• Ezberlenmiş temas listeleri. Öğe deposunun ve arama ağacının içerik "dönemlerine" (epoch) göre önbelleğe alınıyor. CM5: 22,7 → 13,7 sn; fanout aşaması tek başına 18,9 → 1,8 sn.
• Arama ağacında katman maskeleri. Her yaprak kendi katmanının bitini, iç düğümler birleşimini taşıyor; başka katmanla ilgilenmeyen sorgular alt ağaçları atlıyor. CM5: 13,4 → 10,5 sn.
• İkincil uzaysal indeks. Yaprak aralıkları üzerinde hiyerarşik, katman başına bir ızgara; Java'daki sıralı sonuç aynen korunuyor.
• Geometride kopyasız kesişim testleri, itme kontrollerinde O(n²)'den kurtulma, mimalloc ayırıcısı.
• Paralel optimizerde akış: adaylar sırayla iş parçacıklarına dağıtılıyor ve sonuçlar kesinlikle aday sırasıyla tüketiliyor; böylece sonuç iş parçacığı sayısından bağımsız.
• Profil güdümlü optimizasyon (PGO): kendi kartlarıyla eğitilmiş bir derleme, %13–18 ek kazanç.

Projenin kendi ölçümlerinde (M serisi Mac, birebir uyum modu, JVM açılışı dahil) 20 kartın toplamı 2.102 saniyeden 420 saniyeye iniyor; bu yaklaşık 5 kat. Kart başına hızlanma 3 ile 60 kat arasında değişiyor. Kendi ölçümüm interf_u için:

Varsayılan mod optimizeri paralel çalıştırıyor. Sonuçları Java ile birebir aynı değil, ama hangi iş parçacığı sayısıyla çalışırsa çalışsın deterministik. Paralel modun bellek kullanımı da ayrıca ele alındı: bir kart kopyası eskiden 37 MB'lık derin bir kopyaydı. Öğeler ve ağaç düğümleri, yazıldığında kopyalanan 64'lük parçalara (CowVec) bölündü ve bir kopyanın maliyeti 1–3 MB'a indi. 874 parçalı, 6 katmanlı bir test kartında tepe bellek 2.593 MB'tan 1.103 MB'a düştü.

Düzeltilen hatalar

Birebir taşımanın güzel bir yan etkisi, Java kodundaki hataların açıkça görünmesi oldu. Bunlar varsayılan olarak düzeltiliyor (--parity ise Freerouting'in davranışını aynen koruyor). Bir kısmı:

Daha iyi bir yönlendirici

Hataların ötesinde yönlendirme ve optimizasyon da iyileştirildi:

• Paralel yönlendirme turları. Freerouting bir turdaki bağlantıları sırayla yönlendiriyor. fastroute her iş parçacığında aynı anda iki bağlantıya kadar, bağlantının başladığı andaki kartın bir kopyası üzerinde çalışıyor ve sonuçları başlangıç sırasıyla işliyor. 874 parçalı test kartında yönlendirme aşaması 8 iş parçacığıyla 1.413 → 508 sn.
• Çoklu başlangıç (--multi-start). Bağlantılar kalırsa yönlendirici karıştırılmış sıralarla paralel olarak yeniden çalışıyor ve en iyi sonuç tutuluyor (bm05: 7 → 2, StickHub: 3 → 1 yönlenmemiş).
• Kötü turları geri alma. En iyi turdan çok daha kötü biten bir tur geri alınıyor; Java kötü karttan devam ediyordu.
• Kısmen yönlenmiş kartlarda optimizer (Freerouting bir bağlantı bile kalsa optimizer'ı atlıyor) ve her turda yalnızca en iyi adayı değil, iyileştiren diğer adayları da uygulayan açgözlü geçişler.
• Kontrol noktaları ve süre sınırları. Oturum dosyası her zaman şimdiye kadarki en iyi kartı tutuyor; --max-time, Ctrl+C ya da SIGTERM çalışmayı durdurup sonucu saklıyor.
• Teşhis. --report her yönlenmemiş bağlantıyı ve ihlali içeren bir JSON özeti yazıyor. --diagnose ise her yönlenmemiş bağlantıyı tek başına yeniden deneyip sebebini sınıflandırıyor: başka izler mi yolu kapatıyor (tıkanıklık), yoksa geometri ya da kurallar mı engelliyor.

Uzunluk eşitleme

Freerouting'de uzunluk eşitleme yok. fastroute, yönlendirme ve optimizasyondan sonra ağ gruplarını (örneğin bir bellek veri yolu) eşitleyebiliyor. Hedef, grubun en uzun ağı ya da verilen bir uzunluk. Kısa ağların en uzun düz bölümlerine yılankavi kıvrımlar (meander) ekleniyor. Her kıvrım bir kart kopyası üzerinde deneniyor ve biraz daha geniş bir sonda iziyle hiçbir mesafe ihlali yoksa tutuluyor; böylece sonuç KiCad'in DRC'sinde de temiz kalıyor. Uzunluklara, KiCad'in yaptığı gibi via'ların katmanlar arası yüksekliği de ekleniyor.

Diferansiyel çiftler

Freerouting bir çiftin iki ağını birbirinden bağımsız yönlendiriyor, bu yüzden nadiren yan yana gidiyorlar. --pairs ile fastroute çiftleri boş kartta önce yönlendiriyor ve bir ağın diğerini çift aralığında izlemesini sağlıyor. Öndeki ağın izleri birleştirilip yan tarafa kaydırılıyor, kaydırılan yol 0,2 mm'lik parçalarda mesafe kontrolünden geçiriliyor, boş kalan parçalar izleyen ağın izleri oluyor ve labirent yönlendirici bunları pinlerle birleştiriyor. Değişiklik yalnızca hiçbir bağlantı kaybolmazsa ve "eşleşen uzunluk − 0,5 × uzunluk farkı" puanı iyileşirse tutuluyor. Sonunda kısa ağa, iki uzunluk tolerans içine girene kadar kıvrımlar ekleniyor.

Projenin STM32H7 test kartında (4 katman, USB ve 2 Ethernet çifti) çift içi uzunluk farkları 1,8 / 2,7 / 14,5 mm'den 0,1 / 0,25 / 0,25 mm'ye indi; yönlenmemiş bağlantı ve KiCad DRC hatası kalmadı.

Kontrollü empedans

Freerouting'de her ağ sınıfı ve katman için tek bir iz genişliği var; empedans kavramı yok. fastroute'un KiCad eklentisindeki impedance_cli.py, kartın katman yapısından (stackup) iz genişliklerini hesaplıyor. Dış katmanlar mikroşerit (Hammerstad–Jensen, Wadell kalınlık düzeltmesi), iç katmanlar şerit hat (Wheeler) olarak hesaplanıyor; diferansiyel çiftlere IPC-2141 bağlaşım terimi ekleniyor. Hesaplanan genişlikler KiCad'in DRC'sinin kontrol ettiği .kicad_dru kurallarına yazılıyor. Yönlendirici bu sınıflarda pinlerdeki daralmayı (neck-down) kapatıyor; aksi hâlde genişlik bozuluyordu. Test kartında 50 Ω sınıfındaki 30 genişlik hatası sıfıra indi.

KiCad eklentisi

Eklenti kartı dışa aktarıyor, KiCad'in Specctra dışa aktarımındaki boşlukları dolduruyor, yönlendiriciyi çalıştırıyor ve sonucu geri alıyor. Bu iş ilk bakışta göründüğünden çok daha fazla ayrıntı gerektiriyor:

• .kicad_dru kuralları taşınıyor: sınıflar arası mesafeler, katman başına iz genişlikleri, uzunluk ve uzunluk farkı (skew) kuralları, diferansiyel çift aralıkları; en küçük iz genişliği ve bakırın kart kenarına mesafesi de.
• KiCad her bölgeyi (zone) bir güç düzlemi, her kural alanını da bir yasak bölge olarak dışa aktarıyor. Eklenti bunları düzeltiyor ve yönlendirmeden sonra bölgeleri yeniden dolduruyor. Hiçbir şey yasaklamayan kural alanlarının kanalları kapatması yüzünden multichannel_mixer demosunda Freerouting 160 bağlantıyı yönlendiremiyordu; eklentiyle sıfır.
• Bakır metinler, deliklerin mesafe kuralları ve ağı olmayan pedlerin yerel mesafeleri yasak bölgelere dönüşüyor; bölge dikiş via'ları korunuyor.
• Sonuç KiCad'in kendi DRC'siyle kontrol ediliyor. KiCad demolarında, sıfırdan yeniden yönlendirildikten sonraki sonuçlar:

Kalan ihlaller (kart kenarına yakın pedler, termal bağlantılar) özgün tasarımlarda da var.

fastroute ile yönlenmiş kartlar

Sitedeki örnek kartların hepsi fastroute ile yönlendirildi. STM32H7 kontrol kartı (4 katman, 158 ağ, SDRAM, Ethernet, USB) yaklaşık üç dakikada, sıfır yönlenmemiş bağlantı ve sıfır KiCad DRC hatasıyla yönlendi:

Kurulum

KiCad 7 ve sonrası için eklenti paketi GitHub'daki sürümler sayfasında. KiCad'in "Plugin and Content Manager" penceresinde "Install from File" ile kuruluyor; Windows, macOS (Apple Silicon ve Intel) ve Linux (x64 ve ARM64) ikilileri pakette hazır, Java gerekmiyor. fastroute komut satırından tek başına da, herhangi bir Specctra DSN dosyasıyla çalışıyor:

# yönlendir, sonucu board.ses dosyasına yaz
fastroute -de board.dsn -do board.ses

# 10 dakika sonra dur, en iyi sonucu sakla
fastroute -de board.dsn -do board.ses --max-time=600

# tarayıcıda canlı izle
fastroute -de board.dsn -do board.ses --live

# Freerouting ile birebir aynı sonuç
fastroute -de board.dsn -do board.ses --parity

Freerouting'in seçenekleri (-mp, --router.*) aynen çalışıyor. Kaynaktan derlemek için cargo build --release -p fastroute yeterli; scripts/build-pgo.sh ise %15 kadar daha hızlı bir derleme üretiyor.

Sonuç

fastroute bana bir şeyi tekrar gösterdi: büyük bir yazılımı taşırken en değerli araç, kesin bir doğruluk ölçütü. "Java ile bayt bayt aynı" hedefi işi zorlaştırdı; Java'nın rastgele sayı üretecinden TreeMap'in dengeleme kurallarına kadar her şeyi taklit etmek gerekti. Ama bu hedef sayesinde her hızlandırmanın sonucu bozmadığını kanıtlayabildim, her hatayı da "bu bir taşıma hatası mı, yoksa Freerouting'in kendi hatası mı?" diye ayırt edebildim. Sonuçta ortaya aynı kartları 5 kat daha hızlı, Java olmadan ve çok daha az bellekle yönlendiren, üstüne gerçek kartların ihtiyaç duyduğu özellikleri ekleyen bir araç çıktı.

fastroute GPL-3.0-or-later lisanslı özgür bir yazılım ve Freerouting'den türetilmiş bir çalışma; yönlendirme algoritmalarının hakkı Freerouting yazarlarına ait. Boş zamanımda geliştiriyorum. İşinize yaradıysa GitHub Sponsors ya da Open Collective üzerinden destek olabilirsiniz; sorunu gösteren bir kartla gelen hata bildirimleri de en az onun kadar değerli (bir .dsn dosyası yeterli). Sorularınızı bana X ya da LinkedIn üzerinden iletebilirsiniz.