Autorouter geliştirmeden önce bilseydim iyi olurdu dediğim şeyler
(blog.autorouting.com)- tscircuit için yaklaşık 1 yıl boyunca açık kaynaklı PCB autorouter geliştirme deneyimi; A*, görselleştirme, mekânsal bölümleme ve önbellekleme gibi arama problemini küçülten tasarımların performansın anahtarı olduğunu gösteriyor
- Optimizasyonda odak, dil veya tek bir iterasyonun hızından çok iterasyon sayısını azaltmak olmalı; JavaScript bile daha akıllı ve önbelleklenebilir bir algoritmayla düşük seviyeli bir implementasyondan hızlı olabilir
- Mekânsal aramada QuadTree gibi genel amaçlı ağaçlar yerine Spatial Hash Index daha basit ve hızlı olabilir; ancak hücre boyutu yanlış seçilirse her sorguda yüksek sabit maliyet oluşur
- Karmaşık autorouter pipeline’larında her aşamanın girdisi ve çıktısı görselleştirilmeli, iterasyon süreci animasyonla izlenmeli; özyinelemeli fonksiyonlar ve Monte Carlo yaklaşımları hata ayıklama, optimizasyon ve determinizm açısından dezavantajlıdır
- A*, Weighted A*’ın Greedy Multiplier değeriyle optimaliteden kısmen vazgeçip hızı ciddi biçimde artırabilir; her aşama, sonraki aşamaların çözmesini kolaylaştıracak bir durum oluşturarak başarısızlık olasılığını düşürmelidir
A*’ı temel arama aracı yapmak
- A*, 2D ızgaraya özel bir algoritma değil; birçok farklı bilgiye dayalı arama (informed search) türü için kullanılabilen temel bir algoritmadır
- BFS tüm komşu düğümleri ararken, A* hedefe daha yakın düğümlere öncelik verir
- Grafiğin dışındaki bir mesafe metriğini kullandığı için bilgiye dayalı arama sayılır
- Özyinelemeli algoritmalar derinlik öncelikli aramaya (DFS) yakındır; adayları veya komşuları sıralamadan arayan döngüler ise BFS’e yakındır
- Mevcut BFS veya DFS tarzındaki kodu A*’a çevirmek çoğu zaman büyük performans artışı sağlar
- Autorouter’da, probleme uygun hiperparametreleri bulmak için A*’ın birden çok seviyesi kullanılır
- Her autorouter ayarı aday olarak çalıştırılır
- İyi bir maliyetle routing’de başarılı olmaya başlayan ayarlara daha fazla iterasyon ayrılır
- Mesafe maliyeti ile iterasyon maliyetini birlikte ceza olarak kullanan bir meta-A* biçimidir
Dilden çok algoritma önemlidir
- tscircuit autorouter JavaScript ile yazılıyor ve performans tartışmalarında çoğu zaman ilk olarak dil hedef alınıyor
- Algoritma optimizasyonu kabaca iki eksene ayrılır
- Gerekli iterasyon sayısını azaltarak algoritmayı daha akıllı hale getirmek
- Her iterasyonun çalışma hızını artırmak
- Tek bir iterasyonun hızını iyileştirmeye aşırı odaklanmak, yanlış yaklaşımı hızlı çalıştırmaktan ibaret kalabilir
- Örneğin çakışma kontrolü için her şeyi ızgaraya dönüştürme yöntemi, dilden bağımsız olarak yavaşlayabilir
- Düşük seviyede optimize edilmiş assembly’deki basit bir algoritmadan, JavaScript’teki akıllı bir algoritma daha hızlı olabilir
- Geliştirme zamanının %95’ini iterasyon sayısını azaltmaya harcamak daha iyidir; en akıllı ve önbelleklenebilir algoritmaya hızlı ulaşmayı sağlayan dil iyi bir seçimdir
Spatial Hash Index ağaçtan daha iyi olabilir
- Çok boyutlu mekânsal optimizasyonda QuadTree sık sık karşımıza çıkar, ancak genel amaçlı ağaç veri yapıları yavaş olabilir
- QuadTree, 2D/3D uzayda yakındaki nesneleri aramayı
O(N)’denO(log(N))’e indiren bir veri yapısı olarak bilinir; ancak ağaçlar veriye ilişkin bilgiye dayalı bir temsil değildir - Spatial Hash Index, nesnenin kendisini değil nesnenin konumunu hash’leyerek hücrelere veya yakın nesnelerin bucket’larına kaydeder
- Bu yaklaşım, HashSet ve HashMap gibi hızlı hash tabanlı erişimi mekânsal veriye uygulamaktır
- Spatial hash’in daha az popüler olmasının nedeni uygun hücre boyutunu seçmek zorunda olmanızdır
- Hücre boyutu yanlış ayarlanırsa her sorguda yüksek sabit maliyet oluşur
- Pratikte makul bir hücre boyutu seçmenin o kadar da zor olmadığı düşünülüyor
Mekânsal bölümleme ve önbellekleme performansı değiştirir
- iPhone içi gibi devre kartlarında kabaca 10.000–20.000 trace bulunabilir ve en üst düzey EDA araçlarıyla bile ekipler routing için aylar harcayabilir
- Autorouting probleminde önemli ve basit fikir şudur: Zaten route edilmiş olan şey, geçmişte de route edilmiştir
- Oyun geliştiricileri navigation mesh’leri önceden bake eder; LLM’ler ise arama için interneti ağırlıklara sıkıştırır
- Yeni nesil autorouter’lar problemi mekânsal olarak bölebilir ve daha önce çözülmüş yanıtları içeren büyük bir önbellekten yararlanabilir
- Autorouting probleminin %99’u önbellekte önceden çözülmüşse algoritmanın kendi hızı daha az önemli hale gelir
- Günümüzde birçok algoritma önbellek yeniden kullanımı ve mekânsal bölümlemeye yeterince odaklanmıyor
- Depolama ve önbellekleme maliyetleri, hesaplama hızındaki artıştan daha hızlı düşüyor gibi görünüyor; bir autorouter’ı %50 hızlandırmak için 1 GB önbellek kullanmak büyük bir sorun sayılmaz
Görselleştirme ve profillemeyle problemi doğrudan görmek
- Bir probleme dair görselleştirme yoksa onu çözemeyeceğiniz ilkesi önemlidir
- Sadece sayılara bakarak hata ayıklamak zordur; küçük alt problemlerin her biri için görselleştirme yapmak problemi çok daha hızlı anlamayı sağlar
- Autorouter geliştirmede problem çözümüne çoğu zaman görselleştirmeyle başlanır
- 45 derecelik yol bulan alt algoritma da görselleştirildi; bu, autorouter’ın neredeyse son aşaması olan Path Simplification Phase’te kullanılıyor
- JavaScript profiling araçları, her kod satırında harcanan toplam süreyi milisaniye cinsinden gösterir
- JavaScript’i tarayıcıda çalıştırıp Performance sekmesini açmak yeterlidir
- Flame chart ve bellek kullanımı özellikleri de sunulur
- İlgili kısa video: youtube short
Özyinelemeden ve Monte Carlo’dan kaçınmak
- Performans odaklı kodda özyinelemeli fonksiyonlardan kaçınmak daha iyidir
- Neredeyse her zaman senkron çalışırlar; animasyon için ortada durdurmak zordur
- Özünde DFS’tir ve A*’a kolayca dönüştürülemez
- İterasyon sayısını takip etmek kolay değildir
- Özyinelemeli fonksiyonlarda değişebilirlik doğal değildir; oysa performans için değişebilirlik önemli olabilir
- İterasyon tabanlı implementasyon,
visitedNodeskümesini tutup aramadan önce düğümü kontrol edebildiği için daha hızlı olabilir - Monte Carlo algoritmaları rastgelelikle çözüme yaklaşır; ancak deterministik olmadıkları için hata ayıklaması zordur ve heuristiklere kıyasla nadiren optimal oldukları düşünülür
- Adayı nasıl değerlendireceğinizi biliyor ama çözüme nasıl ulaşacağınızı bilmiyorsanız Monte Carlo yaklaşımı sezgi kazanmanıza yardımcı olabilir
- Maliyet fonksiyonuna yakın bir şey ortaya çıktığında Monte Carlo veya Simulated Annealing gibi rastgele yöntemler yerine daha iyi bir yöntem kullanılmalıdır
- Yerel minimumlara duyarlıysanız hiperparametreleri veya daha karmaşık bir maliyet fonksiyonunu değerlendirebilirsiniz
- PCB tasarımcılarının devre kartı üzerine rastgele çizgiler çekmemesi gibi, bu alanda daha iyi heuristic’ler bulunabileceği düşünülüyor
Ara algoritmaları aynı koordinat sisteminde tutmak
- Autorouter şu anda 13 aşama ve yaklaşık 20 alt algoritmadan oluşan bir pipeline’dır
- Mekânsal bölümleme kararları veya bağımsız autoroute edilmiş bölgelerin sınırlarında path simplification gibi işlerde iterasyon sayısı ölçülür
- Her aşamanın girdisini ve çıktısını üst üste görselleştirmek, o anda çözülmekte olan problemin bağlamını anlamayı sağlar
- Downstream aşamalardaki, özellikle high density routing aşamasındaki sorunlar çoğu zaman önceki aşamanın çıktısını iyileştirerek çözülür
- Alt algoritma oluştururken problemi en basit biçimine ayırıp koordinatları
(0, 0)çevresine normalize etme isteği doğabilir - Normalizasyon veya karmaşık dönüşümler, erken aşamaların sonuçlarının sonraki aşamaları nasıl etkilediğini hızlıca görmeyi zorlaştırabilir
- Algoritmanın tüm yaşam döngüsü boyunca koordinat uzayını tutarlı tutmak avantajlıdır
- Her aşamayı sırayla görüp yakınlaştırmak, başarısız Design Rule Check’e neden olan aşamayı bulmaya yardımcı olur
İterasyon animasyonu ve ızgaradan kaçınma
- İterasyon sayısını azaltmak önemli olduğu için, algoritma iterasyonlarını animasyon olarak görmek boşa giden aramayı sezgisel biçimde fark etmeyi sağlar
- Animasyon özellikle Greedy Multiplier ayarlanırken yardımcı olur
- Basit bir trace’in başarısız olması gereken durumda hemen başarısız olmak yerine dışa doğru sonsuzca çözüm aramaya çalıştığı örnek, animasyon olmadan fark edilmesi zor bir durumdu
- İki trace A ve B’nin çakışıp çakışmadığını belirlemenin kabaca iki yolu vardır
- A ve B’nin her segmentine bakıp kesişmeyi kontrol etmek
- B’nin bulunduğu ızgarayı işaretleyip A’nın geçtiği ızgara hücrelerinde B olup olmadığını kontrol etmek
- Izgara yöntemi kolayca 1000 kat yavaşlayabilir
- Hızlı vektör matematiği kullanıldığında, tek bir ızgara hücresini kontrol etmek için bellek erişimi yapmaktansa iki segmentin kesişimini belirlemek için dot product hesaplamak daha hızlı olabilir
- Kesin olarak, uygun açıklığı garanti etmek için segmentler arası mesafe hesabı kullanılmalıdır; bu kesişimden biraz daha karmaşıktır ama çok farklı değildir
Başarısızlık olasılığı ve Weighted A*
- Mekânsal bölümleme aşamasında, her aşamanın çözümde başarısız olma olasılığı öncü gösterge olarak ölçülebilir
- Unravel Autorouter, ana pipeline aşamalarının her birinde her Capacity Node için başarısızlık olasılığını izler
- Her aşama, komşu düğümleri yeniden yapılandırma veya rerouting yoluyla başarısızlık olasılığını azaltmaya odaklanır
- Başarısızlık olasılığı gerçekten ölçülebilir ve algoritma değiştikçe tahminler de iyileştirilebilir
- Her aşama, sonraki aşamaların başarısız olma ihtimalini düşürecek yönde çalışabilir
- Bir anda çok fazla kısıt eklemek yerine çözülebilirliğe öncelik vermek daha iyidir
- Kart bir kez çözüldüğünde, çoğu zaman mevcut çözümle çalışmak en baştan optimal çözüm üretmekten daha kolaydır
Greedy Multiplier ile hız ve optimalite dengesi
- Temel A* optimal çözümü garanti eder; ancak hız daha önemliyse
f(n)biraz değiştirilerek Weighted A* kullanılabilir - Normal A*:
f(n) = g(n) + h(n) - Weighted A*:
f(n) = g(n) + w * h(n) - Weighted A* problemi daha greedily çözer ve genellikle çok daha hızlı çalışır
- Bu yöntem, optimaliteden kısmen vazgeçme karşılığında A* performansını ciddi biçimde artıran bir Greedy Multiplier görevi görür
- Weighted A* ve diğer A* varyantları hakkında daha fazlası için weighted A* and other A* variants here bağlantısına bakılabilir
- Oyun geliştiricileri autorouting geliştiricilerine benzer birçok problemle uğraştığından, ilgili araştırmaları ararken oyun geliştirme makalelerine bakılabilir
Yakında yayınlanacak autorouter
- tscircuit için autorouter yayın aşamasına yaklaşıyor
- Çalışma MIT lisanslı açık kaynak olarak sunulacak
- Autorouting’i çözmek fiziksel dünyadaki inovasyonu büyük ölçüde açığa çıkarabilir ve elektronik ürünlerde “vibe-building”i mümkün kılan kilit parçalardan biri olarak görülüyor
- İlgili hesap: follow me on twitter.
1 yorum
Hacker News yorumları
Genel olarak otomatik yönlendiricilere güvenmeyen taraftayım; bu alana giren yapay zeka araçları için de aynı şey geçerli. Yine de eCAD’de yerleşimin bazı kısımlarını hızla oluşturmak için büyük bir fırsat olduğunu inkâr etmek zor
Tam otomatik araçlardan ziyade birlikte üretim araçlarını kullanma ihtimalim daha yüksek. Tasarımın başında bileşen yerleşimi çoğu zaman kesinleşmemiş olur ve yerleşim, yönlendirmeyi büyük ölçüde etkiler. Sayfada yerleşimin algoritmaya dâhil edilip edilmediğini görmedim. Zaten push-and-shove veya zaman zaman otomatik tamamlama gibi araçlar kullanıyorum
Bu pazar küçük, araçlar parçalı, mevcut oyuncular hantal dev şirketler ve kullanıcılar da titiz meraklılar. KiCad’den ölsem de vazgeçemem. Otomatik yönlendiricinin JavaScript ile yazılmış olması konusunda başlı başına güçlü bir görüşüm yok; ama CAD sağlayıcılarına veya açık kaynak araç ekosistemine eklemlenme planı mı var, yoksa insanları yine başka yeni bir ekosisteme mi çekmeye çalışıyorlar, merak ediyorum
Önbellek dostu olursa bileşenleri taşımak ve farklı yerleşimleri denemek çok daha hızlı olur. JavaScript artık QuickJS veya Proffor gibi küçük çalışma zamanlarına da sahip olduğu için oldukça taşınabilir; yerelde çalışıp devasa bir önbelleği doğrudan oluşturabileceğini düşünüyorum
EDA’da kilitlenme ve ekosistem parçalanması herkesin kaygılanması gereken konular; ancak tscircuit ve bu otomatik yönlendirici MIT izinli lisans teknolojileri olduğu için, EDA’da ender görülen biçimde herkesle birlikte çalışabilir hâle getirilebilir
Footprint’leri, yerleşimi, kısıtları ve elle yönlendirilmiş netleri sabitledikten sonra çok hızlı yineleme yapılabiliyordu
Cadence 90’larda SPECCTRA’yı satın aldığından beri PCB otomatik yönlendiricileri epey durgun kaldı; bu yüzden birinin bu alanı yeniden ele alması sevindirici. SPECCTRA’yı yapanlar hatırladığım kadarıyla VLSI tarafına gidip geri dönmediler; itibar ve para da oradaydı sanırım. Bir süre patent mayın tarlası olmuş olabilir, belki hâlâ öyledir
Otomatik yerleşim o zaman da tamamen baş edilmesi zor bir problemdi, şimdi de öyle görünüyor; ama üretken yapay zeka yaklaşımı buna iyi uyabilir. Üretken yapay zekaya dayalı iyi bir ilk bileşen yerleşimi toplam süreyi azaltabilir. En büyük sorun, mükemmel olmasa bile yeterince iyi olabileceğine inatçı insanları ikna etmek
Kod olarak şematik girişimleri bana biraz tuhaf geliyor. Arka uç formatı olarak iyi çalışırsa güzel olur; özellikle jitx tarafındaki gibi uygulama notu ve veri sayfası düzeyindeki tasarım kurallarını bileşen modellerine kodlama yönündeki ilerleme iyi görünüyor. Ticari tasarım için gereken düzeyde tüm veri sayfalarını okumak sanıldığından çok daha fazla iş; genç mühendislere bu süreci öğretmek de öyle, dolayısıyla otomasyon faydalı
Ancak yaklaşımların, şematiği yerleşim için veri girişi, bir tür kaynak kod olarak görme fikrine kök saldığı anlaşılıyor. Şematik aynı zamanda, EDA ürün paketi kurulu olmayan kişilerin de erişebilmesi gereken, özenle evrilmiş bir görsel dile sahip bir tasarım belgesidir. Adafruit/Sparkfun/Shenzhen tarzı, açık kablolamayı en aza indiren şematikleri çözerek öğrenenler iyi bir şematiğin değerini pek bilmeyebilir
Bir diğer nokta da analojiye fazla yaslanıp PCB düzeyi tasarımı VLSI tasarımı gibi yapma eğilimi. Bunun tamamen imkânsız olduğunu düşünmüyorum. DRC ve doğrulama araçları iyileştikçe bileşen düzeyi tasarım da VLSI’a daha çok yaklaşabilir. Ancak tasarım, EDA/CAM/simülasyon, doğrulama, üretici, montajcı, bileşen tedarikçisi ve düzenleyici/sertifikasyon kurumları arasındaki bağlar o kadar gevşek ki, bunlardan yalnızca bir köşeyi bile doğru yapmak büyük başarıdır
Bugünlerde empedans kontrollü UHF tasarımlar alan odaklı simülasyon araçlarıyla birlikte yapılıyor. Bu yüzden önce kritik izler elle yönlendiriliyor, island pole’lar oluşturuluyor, en son da güç bağlantıları ele alınıyor
KiCad yerleşimi hiç olmamasından biraz daha iyi; ama onu bir başka yarım yamalak simülasyon aracına çevirmeye çalışmak komik görünüyor
Bunlar veritabanı desteği ve outjob özelliği. Bunun dışı daha çok benimseme ve kullanıcıların bu özelliği nasıl değerlendireceği meselesi; veritabanları da genelde veri düzenine dair kurum içi bürokrasiyi daha çok beraberinde getirir
Yerleşimi hızlandıran iş akışı açısından KiCad’in de zaten bir ölçüde o yöne gittiğini düşünüyorum. Örneğin 7.0 civarında gelen “iz otomatik tamamlama” özelliği var. pcbnew’de kısayolu sanırım F idi; o anda yerleştirmekte olduğunuz track’in izini seriyor. “track’in karşı tarafından yönlendir” kısayolu E ile birlikte kullanınca, iki farklı ballout grid’i arasında çalışırken üretkenlik ciddi biçimde artıyor
Sürüm 9’da bus veya birden çok track sürüklenebilir hâle geldiği için bu akış daha da hızlanabilir
Açıkçası tatmin edici bir yerleşime ulaşabiliyorsam ve otomatik yönlendiriciye yönlendirme konumu kısıtları verebiliyorsam, tasarımın önemli bir bölümünü otomatik yönlendiriciye bırakabileceğimi düşünüyorum. Örneğin geçen yıl NXP iMX8MP ve eMMC kullanan bir kart yaptım; işlemci çevresindeki ballout eMMC ballout’u ile iyi örtüştüğü için çipleri hizalayıp çizgileri çekmek yeterli oldu. Veri yolunu en üst katmanda tutması gerektiğini bilseydi, otomatik yönlendirici 10 dakika süren işi birkaç saniyede yapardı
Otomatik yönlendirici projelerinin yaşadığı bir başarı ölçütü sorunu var. Karttaki her şeyi halledebilmesi gerekiyormuş gibi “tamamlandı” sayılıyor; ama pratikte çalışan bir elektrik mühendisi olarak ben bunu istemiyorum. Tasarımın küçük parçalarını tek tek benimle birlikte ele alan, incelemem için zaman veren ve sonra sonraki parçaya geçen bir otomatik yönlendirici istiyorum
Katmanları aşan kısıtlar da verilebilirse çok güçlü olur. Örneğin “D0-7 adlı tüm netleri 1. ve 3. katmanlarda tut, uzunluklarını birbirine 5 mm içinde eşitle ve D0’ı uzunluk referansı olarak al” gibi. Bunu yapabiliyorsa DRAM uzunluk ayarlamasını çözmüş demektir ve çok daha geniş karmaşıklıkta tasarımlar sıradan kullanıcılar için de mümkün hâle gelir
Zaman bulursam bunun ne anlama geldiğini bir demo ile göstermek isterim
Monte Carlo’nun özü, doğruluk ile hız arasında takas yapabilmesidir. Algoritmayı ne kadar uzun çalıştırırsanız o kadar doğru hale gelir
Daha ilginci, bunun tersinin de sık sık kullanılabilmesidir. Çok yanlış bir sonucu çok hızlı elde edebilirsiniz. Tüm yolları aramak yerine rastgele seçilen tek bir yolu aramak gibi
Bu yöntem, algoritmanın en içteki iç içe döngüsüne konduğunda parlar. Örneğin otomatik yönlendirmeyi öğrenen bir sinir ağını eğitmek istiyorsanız, dış döngü sinir ağı parametrelerini günceller, iç döngü ise grafikten geçen yolu hesaplar
Monte Carlo kullanırsanız, sapma yoksa doğruluğu kontrol eden bu iç döngüyü tek bir yinelemeye indirebilirsiniz. Varyans artacağı için dış döngü yavaşlar, ama makine öğrenmesi “teorik olarak” öğrenebilir
Böylece satrançta veya Go’da olduğu gibi sezgisel olarak doğru kararları seçen bir politika oluşturabilirsiniz. AlphaGo Zero, AlphaChess Zero, AlphaRouter Zero gibi Monte Carlo ağaç araması varyantlarında, arama kısmı olmasa bile sinir ağı parametrelerinde kodlanmış devasa önbellek, eğitimden sonra sinir ağından tek geçişle, yani sabit zamanda en iyi tahmini yolu hesaplayabilir. Bu sabit, parametreleri artırarak veya daha uzun eğiterek bellek ile hız arasında kolayca takas edilebilir
MC, gerçeklik hissini yerli yerine oturtan bir algoritmadır. Yavaştır ama neredeyse her zaman uygulanması çok basittir ve tamamen alakasız bir yere sapmadığınızı çok yüksek bir güvenle yeniden doğrulamak için güvenilirdir
Otomatik yönlendirme üzerine harika bir tartışma, ama sonunda “elektronik ürünlerde vibe-building’i mümkün kılan kilit parça” diye bitmesi biraz canımı acıttı
Yönlendirme kendi başına kolaydır. Yeni bir hattı eklemek için daha önce döşenmiş olanı sökmeniz gerektiği anda işler karmaşıklaşır ve kombinatoryal patlama üstünüze çöker
Eskiden KiCad’de bulunan otomatik yönlendiriciyi özlüyorum. Muğlak fikri mülkiyet nedenleriyle kaldırılmıştı; çünkü yazarı bir dönem otomatik yönlendirme şirketinde çalışmıştı. Geri getirilmesini isteyen kullanıcılara “gerçek erkekler otomatik yönlendirici kullanmaz” türünden tepkiler verilmişti
https://forum.kicad.info/t/autorouting-and-autoplacement/185...
Umarım bu otomatik yönlendirici ve ardından gelecek diğer araçlar, insanların çok fazla yol haritası ya da resmi eğitim olmadan ilk elektronik ürünlerini piyasaya sürebilmelerini sağlar
Elbette iyi bir otomatik yönlendirici uzmanlar için de faydalı olmalı; umarım o tarafta da yardımcı olur
Ancak KiCad’in otomatik yönlendiriciye çok enerji harcamasını pek görmek istemeyen huysuz eski kafalılardan biri olarak, PCB otomatik yönlendiricileri her zaman baş belasıdır ve düzgün çalışmaz
Nedenini VLSI otomatik yönlendiricilerine bakınca anlayabilirsiniz. VLSI otomatik yönlendiricileri de baş belasıydı ve düzgün çalışmıyordu. Sonra VLSI’da katman sayısı çok arttı; dikey yönlendirme için katman, yatay yönlendirme için katman, güç için katman ayrı ayrı ayrıldıktan sonra bile küresel dikey bağlantılar, küresel yatay bağlantılar ve küresel güç için birkaç katman daha koymak mümkün hale geldi
PCB otomatik yönlendirmenin temel sorunu, PCB’lerde VLSI çiplerine göre çok daha fazla engel bulunmasıdır. Birincisi, bileşenlerin kendileri hem engel hem de darboğazdır. İkincisi, PCB via’ları neredeyse her zaman kartın tüm katmanlarını bloke ederken VLSI via’ları yalnızca bağlandıkları iki katmanı bloke eder. Üçüncüsü, PCB via’ları genellikle yönlendirme metali genişliğinden daha büyüktür. Dördüncüsü, PCB’de kullanılan katman sayısı VLSI’a göre çok daha azdır. Yaygın olan 4 katmandır; bunun içinde genel yönlendirme için gerçekten kullanılan yalnızca 2 katmandır. Maliyet nedeniyle 2 katmanlı kartlar da çoktur ve otomatik yönlendirme daha zordur; 6 katman ise oldukça azdır
Sonuç olarak PCB otomatik yönlendirme, VLSI otomatik yönlendirmeden çok daha karmaşık bir iştir
Yazıda görselleştirme ve önbellek etkisini özellikle önemli ele alması iyi
Ancak birkaç nokta takılıyor. “Özyinelemeli algoritma derinlik öncelikli aramadır; adayları veya komşuları sıralamadan arayan döngü ise genişlik öncelikli aramadır” sözü yanlış ya da sezgiyi kaçırıyor gibi. DFS ve BFS ikisi de döngüyle ya da özyinelemeyle yazılabilir; asıl fark, bir sonraki adayı yığının üstünden mi altından mı aldığınız, yani stack (FILO) mu queue (FIFO) mu kullandığınızdır
A*'ın bilgiye dayalı tüm aramaların en iyi temeli olduğu sözü de bağlam gerektirir. Hedefe kadar hesaplaması kolay bir “mesafe” kavramı varsa ve aynı graf üzerinde yalnızca birkaç sorgu çalıştırıyorsanız yol bulmada yararlıdır. Yol ağı gibi neredeyse statik bir graf üzerinde çok sayıda sorgu çalıştırmayı planlıyorsanız contraction hierarchy gibi ön işleme algoritmaları daha iyi olabilir. Gezgin satıcı problemi gibi, optimizasyon yapıp hedefin belirli olmadığı durumlarda 2-opt gibi başka yerel arama sezgiselleri daha iyi olabilir
“BFS tüm komşu düğümleri arar, A* ise hedefe yakın düğümlere öncelik verir” bir farktır; ama daha büyük fark A*'ın dinamik bir algoritma olmasıdır. Bu yüzden en kısa yolu bulduğundan emin olup erken sonlandırabilir. BFS ise tüm grafı arayana kadar emin olamayabilir ve graf devasa olabilir
Çoğu dilde bunu böyle ifade etmek, dışarıdan bir yığın getirip düşünmekten daha kolaydır. Bu yüzden gerçek kodda özyineleme görürseniz DFS'e daha yakın olma ihtimali yüksektir; ama bu katı bir kural değildir
BFS FIFO queue, DFS LIFO stack, A* ise genellikle heap ile uygulanmış bir priority queue kullanır
Bu, BFS'in doğru sonuç vermesini sağlayan temel invariant'lardan biridir; dolayısıyla tüm hedeflere ulaşıldığında erken sonlandırabilirsiniz
A* ile BFS arasındaki fark, BFS'in iki nokta arasındaki en kısa yolu değil, tek bir başlangıç noktasından grafın tüm noktalarına en kısa yolu bulmasıdır. A* ise daha zayıf bir soruya yanıt verip tekil sorguları hızlandıran bir ödünleşimdir
Problem yapısı izin veriyorsa binlerce A* çağrısını tek bir BFS veya Dijkstra çağrısına çevirmek bile büyük hız artışı sağlayabilir. Bir diğer önemli fark da BFS'in yalnızca tüm kenar uzunluklarının aynı olduğu graflarda çalışması, A*'ın ise farklı kenar uzunluklarını desteklemesidir. İkisi birbirinin yerine geçebilir şeyler değildir; tıpkı bir listede en küçük elemanı bulmanın liste sıralamanın yerine geçmemesi gibi
“Quadtree ve tüm genel amaçlı ağaç veri yapıları delicesine yavaştır”, “ağaçlar veriye dair bilgi içeren bir temsil değildir”, “ağaç kullandığınız her seferinde O(~1) hash algoritması yerine daha karmaşık bir O(log N) algoritması kullanıyorsunuz” sözleri oldukça yanlış bir yöne gidiyor
Hashing yaklaşımı, noktalar eşit dağılıyorsa ve yalnızca seçtiğiniz sabit bölmeye yakın alanları sorguluyorsanız uygundur. Aksi halde o O(1), O(n)'e çökebilir
Veri dağılımını bilmediğinizde ağaç bilgi içeren bir temsildir
Rastgele algoritmalar da benzer. Arama uzayı trilyonlarca ya da daha fazla öğe veya olasılıktan oluşuyorsa ne yapacaksınız? Sezgisel de yoksa? Kaba kuvvetin de olmadığı, akıllı algoritma da kullanamadığınız bir durumda rastgele algoritmalar kurtarıcı olur
Bu belirli uygulama için gerekli olmayabilir; ama genelleştirilmiş kesin ifadelerden kaçınmak daha iyidir
Daha ciddi söylemek gerekirse, ağaç tabanlı algoritmaların abartılma eğiliminde olduğunu ve insanların Big-O davranışına fazla kapılıp sabit katsayının yüz binlerce öğede bile çok önemli olduğunu unuttuğunu düşünüyorum. Veri yerelliği gibi şeyler de aynı şekilde. Bazen daha karmaşık bir yapının defter tutma işini yapmaktansa sıralı taramayla geçmek daha hızlı olabilir
Genel olarak işlemleri küçük bir wrapper'a sarmak, önce kolay uygulamayı yapmak ve kararı ölçüme bırakmak daha iyidir
En kötü durumda daha iyi performans için başka bir yapıya göre tüm programı yeniden yazmanız gerekir; ama deneyimlerime göre bir dosyayı baştan yazınca beraberinde epey ücretsiz iyileşme de gelir
2D veya 3D noktaları saklayıp yakındaki noktaları sorgulamak için hâlâ tatmin edici bir yöntem bulamadım. kD tree iyi; ama sabit bir küme alıp yapı kurmak yerine noktaları ilerledikçe eklemek istiyorum
Neredeyse her şey benim oyun geliştirme sezgisellerimle örtüşüyor. JavaScript seçimini de anlayabiliyorum.
Şu anda Lisp tarzı S-ifadeleriyle çalışan bir oyun modlama framework’ü geliştiriyorum ve yaratıcı yineleme süresini kısaltan optimizasyonun her şeyden önemli olduğunu fark ettim.
A*, Lee algoritması gibi şeylerin hepsi harika. Herhangi türden bir flood fill için yanında görselleştirme yapmamak neredeyse suç sayılır. Dopamini fazlasıyla boşa harcamak demek.
Bu yazıyı görünce, benim okumadığım ama oyun geliştirmeye yakın tekniklerin bu tür problemlerde de işe yarayıp yaramayacağını merak ettim. Bir boids router’ın epey eğlenceli olacağını düşünen ilk kişi muhtemelen ben değilimdir. Daha ciddi olarak, jump flooding tabanlı işaretli uzaklık alanlarının çok güçlü olabileceğini düşünüyorum.
Özellikle uzamsal hashing kısmı kendi deneyimimle örtüşüyor. Neredeyse 20 yıldır ağaç yapıların harcanan zamana değdiği çok fazla durum görmedim. Bir istisna var: yaptığım Lovecraftvari metin editörü, tepki işleme için trie’ları epey yoğun kullanıyor. 45.000 kelimeyi olay işleme için sıkıştırılmış bir durum makinesine dönüştürmenin iyi bir yoluydu.
Daha önce özyinelemeli desen otomatik yönlendiricileri hakkında yazmıştım; çözüm uzayı küçük olduğu için mevcut makine öğrenimi algoritmalarıyla tahmin etmesi görece kolay. Otomatik yönlendirmede hâlâ keşfedilmemiş çok ilginç alanlar var.
jump flooding’i bilmiyordum. Başkaları için ekleyeyim: uzaklık alanlarını hızlıca paralel olarak yaklaşık hesaplayan bir algoritma. Kesinlikle ilginç olabilir; haber verdiğin için teşekkürler.
Ağaçlar özyinelemeli algoritmalara da iyi uyar; yazar da yinelemeli algoritmaları özyinelemeye tercih etmek için nedenler olduğunu söylediğine göre bu tavsiyeler birbiriyle bağlantılı.
Geniş açıdan bakınca “özyinelemeli” ve “özyinelemeli olmayan” ayrımı biraz yapay. Asıl soru şu: “Sıkı kuralları olan önceden yazılmış bir algoritma mı akış kontrolünü üstleniyor, yoksa ben mi üstleniyorum?” Performansı çok önemsiyorsanız yanıt benim üstlenmem olmalı; yürütme durumu çalışma ortamının sağladığı stack’in içine soyutlanıp çalışma zamanında garip biçimde değiştirilmesi zorlaşınca bu engel olmaya başlar.
“Odaklanmanın %95’i yineleme sayısını azaltmaya harcanmalı. Bu yüzden dil önemli değildir” sözü bir ölçüde doğru; ama oyuncu, ifade gücü yüksek, yorumlanan, soyut ve yavaş bir dille harika ve performanslı bir algoritma yaptıktan sonra performans hâlâ önemliyse, aynı şeyi performanslı düşük seviyeli bir dille yeniden yazar, gerekirse mimariye özel assembly bile yazarsınız.
numpy, pandas, OpenCV, TensorFlow’un saf Python ile yazılmamış olmasının bir nedeni var. Python, yüksek performanslı C++/assembly/CUDA vb. ile uygulanmış işleri yönlendirme rolünü üstlenir.
Problem uzayını keşfedip verimli bir algoritma bulup bunu blogda yazmış olmakla ne kadar gurur duyulursa duyulsun, yalnızca saf Python ya da JavaScript ile yazmakta ısrar edilseydi popüler bir sayısal hesaplama kütüphanesine dönüşmesi zor olurdu.
Eğlenceli bir yazı ama yazarın algoritmik içgörüleriyle saf JavaScript bir HEVC encoder kare başına 1 günden 3 saate düşseydi aynı sonuca varmak zor olurdu.
Üniversiteden hatırladığım bir sürü anahtar kelime görüyorum. Ünlü ve havalı algoritmaları kullanma fırsatım olsa keşke.
Gerçekteyse tek yaptığım UI bileşenleri ve REST API’leri yazıp Elasticsearch sonuçlarını göstermek. İlginç şeylerin hepsi kara kutunun içine gömülü.
Oyun geliştirmede kaçınılmaz çok algoritma var; algoritma yapmak istiyorsanız tower defense gibi bir şey yapmayı deneyin, çok sayıda klasik algoritmayla uğraşırsınız.
En azından mevcut bilgisayar bilimi diplomasının parçalanması gerektiğini düşünüyorum. Havalı matematik tarafı ayrı bir diploma olmalı ve yapay zekâ ile ilgili yeni bir diplomayla birleştirilebilir. Veritabanları ve ağ teorisi de ayrı diploma olmalı; düşük seviyeli assembly de öyle. Elektronik bileşenlerin, NAND kapılarının, Boole cebrinin vb. nasıl çalıştığı elektronik mühendisliğine taşınmalı.
Piyasanın en çok ihtiyaç duyduğu, CRUD uygulamaları çıkarabilen kişiler için akademik bilginin şart olduğu iddia edilecekse ya ayrı bir diploma yapılmalı ya da mesleki eğitime taşınmalı.
Aynı zamanda işe alım şartlarının bekçiliği de yasayla ele alınmalı. Fiilî işle neredeyse ilgisi olmayan diplomaların istenmesi engellenmeli. Şu anda çocuklara hayatlarının birkaç yılını boşa harcatıyor, beş haneli ila altı haneli dolar borç yüklüyor ve yalnızca şirketlerin insanları elemesini kolaylaştırıyor.
2D/3D uzay problemleriyle doğrudan uğraşmıyorum ama en büyük ders görselleştirmenin değeri.
İnsanlar görselleri anlamakta ve analiz etmekte çok iyidir. Bir diğer fikir de, problemin şeklini önce olasılıksal yöntemlerle ya da kaba kuvvetle kavrayıp ardından yalnızca saf teorik anlayışa değil buna göre daha iyi yöntemi seçmektir.
“Uygulama dili önemli değildir” sözü bu alanda doğru olabilir; ama genel yazılım mühendisliğine uygulandığında, dil seçiminin hızı ve gereken yineleme sayısını etkilemediği varsayımının ciddi biçimde yanlış olduğunu düşünüyorum.
Üstel ya da polinom terimi kontrol etmeye çalıştığınız aşamadaysanız Rust veya elle yazılmış assembly ile JavaScript ya da VisualBasic arasındaki fark epey anlamsızlaşabilir.