Autorouter बनाना शुरू करने से पहले जो बातें जान लेनी चाहिए थीं

 (blog.autorouting.com)
1 पॉइंट द्वारा GN⁺ 2025-03-29 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • tscircuit के लिए ओपन सोर्स PCB autorouter को लगभग 1 साल तक विकसित करने के अनुभव ने दिखाया कि A*, visualization, spatial partitioning, और caching जैसी तकनीकें, जो search problem को कम करती हैं, performance की कुंजी हैं
  • optimization का फोकस भाषा या एक iteration की speed से ज़्यादा iteration की संख्या घटाने पर होना चाहिए; JavaScript में भी अगर algorithm ज़्यादा स्मार्ट और cacheable हो, तो वह low-level implementation से तेज़ हो सकता है
  • spatial search में QuadTree जैसी general-purpose tree की तुलना में Spatial Hash Index ज़्यादा simple और तेज़ हो सकता है, लेकिन cell size गलत चुनने पर हर lookup में ऊँचा fixed cost आ सकता है
  • जटिल autorouter pipeline में हर stage के input-output को visualize करना और iteration process को animation में देखना ज़रूरी है; recursive functions और Monte Carlo तरीके debugging, optimization, और determinism के लिहाज़ से कमज़ोर पड़ते हैं
  • A* में Weighted A* के Greedy Multiplier का उपयोग करके optimality का कुछ हिस्सा छोड़कर speed को काफ़ी बढ़ाया जा सकता है, और हर stage को ऐसी state बनानी चाहिए जिसे आगे की stages के लिए हल करना आसान हो

A* को डिफ़ॉल्ट search tool की तरह इस्तेमाल करना

  • A* सिर्फ 2D grid के लिए बना algorithm नहीं है, बल्कि यह कई तरह की information-based search (informed search) के लिए इस्तेमाल किया जा सकने वाला base algorithm है
  • BFS सभी neighboring nodes को explore करता है, जबकि A* destination के ज़्यादा क़रीब nodes को पहले explore करता है
    • यह graph के बाहर के distance metric का उपयोग करता है, इसलिए यह informed search में आता है
  • recursive algorithms, depth-first search (DFS) के क़रीब होते हैं, और candidate या neighbors को sort किए बिना चलने वाले loops, BFS के क़रीब होते हैं
  • मौजूदा BFS या DFS जैसे code को A* में बदलने से कई बार performance में बड़ा सुधार मिलता है
  • autorouter में problem के मुताबिक hyperparameters ढूँढने के लिए A* के कई स्तर इस्तेमाल किए जाते हैं
    • हर autorouter setting को एक candidate की तरह चलाया जाता है
    • जो settings अच्छे cost पर routing में सफल होने लगती हैं, उन्हें ज़्यादा iterations दिए जाते हैं
    • यह distance cost और iteration cost दोनों को penalty की तरह इस्तेमाल करने वाला meta-A* जैसा रूप है

भाषा से ज़्यादा algorithm मायने रखता है

  • tscircuit autorouter JavaScript में लिखा जा रहा है, और performance की चर्चा में अक्सर सबसे पहले भाषा पर उंगली उठती है
  • algorithm optimization को मोटे तौर पर दो हिस्सों में बाँटा जा सकता है
    • ज़रूरी iterations की संख्या घटाकर algorithm को ज़्यादा स्मार्ट बनाना
    • हर iteration की execution speed बढ़ाना
  • अगर आप एक iteration की speed सुधारने पर ज़रूरत से ज़्यादा ध्यान देते हैं, तो हो सकता है आप सिर्फ़ गलत approach को और तेज़ चला रहे हों
  • उदाहरण के लिए, overlap check के लिए हर चीज़ को grid में बदलने वाला तरीका भाषा से अलग होकर भी धीमा पड़ सकता है
  • JavaScript में लिखा स्मार्ट algorithm, low-level optimized assembly में लिखे simple algorithm से भी तेज़ हो सकता है
  • development time का 95% iteration count घटाने पर लगाना बेहतर है, और वह भाषा अच्छी है जो आपको सबसे स्मार्ट और cacheable algorithm तक जल्दी पहुँचने दे

Spatial Hash Index, tree से बेहतर हो सकता है

  • multi-dimensional spatial optimization में QuadTree अक्सर सामने आता है, लेकिन general-purpose tree data structures धीमे हो सकते हैं
  • QuadTree को 2D या 3D space में nearby objects search को O(N) से O(log(N)) तक घटाने वाले data structure के रूप में जाना जाता है, लेकिन tree अपने-आप में data का informed representation नहीं है
  • Spatial Hash Index object को नहीं, बल्कि object की location को hash करके उसे cell या nearby buckets में store करता है
  • यह approach, HashSet और HashMap जैसी तेज़ hash-based access को spatial data पर लागू करने जैसा है
  • spatial hash कम लोकप्रिय होने का एक कारण यह है कि इसमें सही cell size चुननी पड़ती है
    • अगर cell size गलत tune हो जाए, तो हर lookup पर ऊँचा fixed cost आता है
    • व्यवहार में, सही cell size चुनना उतना मुश्किल नहीं लगता

spatial partitioning और caching performance बदल देते हैं

  • iPhone के अंदर जैसी circuit boards में लगभग 10,000 से 20,000 traces हो सकती हैं, और top-level EDA tools के साथ भी टीमों को routing में महीनों लग सकते हैं
  • autorouting problem में एक महत्वपूर्ण सरल विचार यह है कि जो चीज़ पहले से route हो चुकी है, वह पहले भी route की जा चुकी है
  • game developers search meshes को पहले से bake करते हैं, और LLMs retrieval के लिए internet को weights में compress करते हैं
  • अगली पीढ़ी के autorouters problem को spatial तरीके से बाँट सकते हैं और पहले से हल किए गए answers वाले बड़े cache का उपयोग कर सकते हैं
  • अगर autorouting problem का 99% हिस्सा पहले से cache में हल हो, तो algorithm की raw speed उतनी महत्वपूर्ण नहीं रह जाती
  • अभी कई algorithms cache reusability और spatial partitioning पर पर्याप्त ध्यान नहीं देते
  • storage और caching की लागत, compute speedup की तुलना में और तेज़ी से घटती दिख रही है; autorouter को 50% तेज़ बनाने के लिए 1GB cache इस्तेमाल करना बड़ी बात नहीं होनी चाहिए

visualization और profiling से समस्या को सीधे देखना

  • यह सिद्धांत महत्वपूर्ण है कि visualization के बिना समस्या हल नहीं की जा सकती
  • सिर्फ़ numbers देखकर debugging करना मुश्किल है, और हर छोटे subproblem के लिए visualization बनाने से समस्या बहुत जल्दी समझ में आती है
  • autorouter development में कई बार problem solving की शुरुआत visualization से ही होती है
  • 45-degree path खोजने वाले sub-algorithm को भी visualize किया गया, जो autorouter के लगभग आख़िरी stage, Path Simplification Phase, में इस्तेमाल होता है
  • JavaScript profiling tools यह दिखाते हैं कि code की हर line पर कुल कितना समय milliseconds में खर्च हुआ
    • browser में JavaScript चलाकर Performance tab खोलना काफ़ी है
    • flame chart और memory usage features भी मिलते हैं
  • संबंधित छोटा वीडियो: youtube short

recursion और Monte Carlo से बचना

  • performance-oriented code में recursive functions से बचना बेहतर है
    • वे लगभग हमेशा synchronous ढंग से चलते हैं, इसलिए animation के लिए बीच में रोकना मुश्किल होता है
    • वे मूल रूप से DFS होते हैं और उन्हें A* में बदलना आसान नहीं होता
    • iteration count track करना आसान नहीं होता
    • recursive functions में mutability अप्राकृतिक लगती है, जबकि performance के लिए mutability महत्वपूर्ण हो सकती है
  • iteration-based implementation, visitedNodes set बनाए रखकर और search से पहले nodes को जाँचकर ज़्यादा तेज़ हो सकती है
  • Monte Carlo algorithms randomness के ज़रिए answer तक पहुँचते हैं, लेकिन deterministic न होने के कारण debugging कठिन हो जाती है, और heuristic approaches की तुलना में वे शायद ही optimal साबित होते हैं
  • जब यह पता हो कि candidates को कैसे evaluate करना है, लेकिन यह न पता हो कि answer तक पहुँचना कैसे है, तब Monte Carlo approach intuition पाने में मदद कर सकती है
  • जैसे ही cost function के क़रीब कुछ बन जाए, Monte Carlo या Simulated Annealing जैसी random techniques की जगह बेहतर तरीक़ा अपनाना चाहिए
  • अगर local minima के प्रति sensitivity हो, तो hyperparameters या ज़्यादा complex cost function पर विचार किया जा सकता है
  • जिस तरह PCB designer circuit board पर random lines नहीं खींचता, उसी तरह इस domain में बेहतर heuristics ढूँढी जा सकती हैं

intermediate algorithms को एक ही coordinate system में रखना

  • autorouter इस समय 13 stages और लगभग 20 sub-algorithms वाली pipeline से बना है
  • spatial partitioning decisions या independently autorouted regions की boundaries पर path simplification जैसे कामों में iteration counts को मापा जाता है
  • अगर हर stage के input और output को overlap करके visualize किया जाए, तो मौजूदा problem का context समझना आसान हो जाता है
  • downstream stages, ख़ासकर high density routing stage की समस्याएँ, कई बार पहले के stages के output को सुधारकर हल हो जाती हैं
  • sub-algorithm बनाते समय problem को सबसे simple form में अलग करने और coordinates को (0, 0) के आसपास normalize करने का लालच होता है
  • normalization या complex transformations, शुरुआती stages के नतीजों का बाद की stages पर असर जल्दी देखना कठिन बना सकते हैं
  • पूरे algorithm lifecycle में coordinate space को consistent रखना फ़ायदेमंद है
  • हर stage को क्रम से देखकर और zoom करके उस stage को ढूँढने में मदद मिलती है जो failed Design Rule Check का कारण बनी

iteration animation और grid से बचाव

  • क्योंकि iteration count घटाना महत्वपूर्ण है, algorithm iterations को animation में देखने से wasted search सहज रूप से समझ में आती है
  • animation, ख़ासकर Greedy Multiplier tune करते समय, बहुत मददगार होती है
  • एक simple trace के ऐसे case को, जहाँ उसे तुरंत fail होना चाहिए था लेकिन वह बाहर की ओर लगातार समाधान ढूँढने की कोशिश करता रहा, animation के बिना पकड़ना मुश्किल था
  • दो traces A और B के overlap का पता लगाने के broadly दो तरीके हैं
    • A और B के हर segment को देखकर intersection check करना
    • B जिन grids में मौजूद है उन्हें mark करना, फिर यह देखना कि A जिन grids से गुज़रता है वहाँ B है या नहीं
  • grid वाला तरीका आसानी से 1000 गुना धीमा हो सकता है
  • तेज़ vector math के साथ, एक single grid cell check के लिए memory access करने से दो segments के intersection के लिए dot product निकालना तेज़ हो सकता है
  • सख़्ती से कहें तो, उचित clearance सुनिश्चित करने के लिए segment-to-segment distance calculation इस्तेमाल करनी चाहिए; यह intersection check से थोड़ा ज़्यादा जटिल है, लेकिन बहुत अलग नहीं

failure probability और Weighted A*

  • spatial partitioning stage में हर stage की solve failure probability को leading indicator की तरह मापा जा सकता है
  • Unravel Autorouter, pipeline की हर मुख्य stage पर हर Capacity Node की failure probability track करता है
  • हर stage, neighboring node reconfiguration या rerouting के ज़रिए failure probability कम करने पर ध्यान देती है
  • failure probability को वास्तव में मापा जा सकता है, और algorithm बदलने पर prediction भी सुधर सकती है
  • हर stage को इस दिशा में काम करना चाहिए कि आगे की stages में failure की संभावना कम हो
  • बहुत ज़्यादा constraints एक साथ डालने की बजाय solvability को प्राथमिकता देना बेहतर है
  • एक बार board हल हो जाए, तो शुरू से optimal answer बनाने की तुलना में मौजूदा answer को improve करना कई बार आसान होता है

Greedy Multiplier से speed और optimality के बीच संतुलन

  • बेसिक A* optimal answer की guarantee देता है, लेकिन अगर speed ज़्यादा महत्वपूर्ण हो, तो f(n) को थोड़ा बदलकर Weighted A* इस्तेमाल किया जा सकता है
  • सामान्य A*: f(n) = g(n) + h(n)
  • Weighted A*: f(n) = g(n) + w * h(n)
  • Weighted A* problem को ज़्यादा greedily solve करता है और आमतौर पर काफ़ी तेज़ चलता है
  • यह तरीका optimality का कुछ हिस्सा छोड़कर A* performance को काफ़ी बढ़ाने वाले Greedy Multiplier की तरह काम करता है
  • Weighted A* और A* के दूसरे variants के बारे में weighted A* and other A* variants here पर और देखा जा सकता है
  • game developers, autorouting developers जैसी कई समस्याओं से जूझते हैं, इसलिए संबंधित research खोजते समय game development papers देखना उपयोगी हो सकता है

जल्द जारी होने वाला autorouter

  • tscircuit के लिए autorouter अब release के क़रीब पहुँच रहा है
  • यह काम MIT license वाले ओपन सोर्स के रूप में उपलब्ध कराया जाएगा
  • autorouting को हल करना physical world innovation के लिए बड़ा रास्ता खोल सकता है, और electronics के “vibe-building” को संभव बनाने वाला एक अहम हिस्सा हो सकता है
  • संबंधित अकाउंट: follow me on twitter.

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-03-29
Hacker News की राय

  • आम तौर पर मैं autorouter पर भरोसा नहीं करता, और इस क्षेत्र में आ रहे AI tools के बारे में भी यही सोच है, लेकिन eCAD में layout के कुछ हिस्सों को तेज़ी से बनाने का बड़ा अवसर है, इससे इनकार करना मुश्किल है
    पूरी तरह automated tools के बजाय मैं शायद co-creation tools ज़्यादा इस्तेमाल करूँगा। design की शुरुआत में components की placement अक्सर final नहीं होती, और placement का routing पर बड़ा असर पड़ता है। पेज पर मुझे यह नहीं दिखा कि placement को algorithm में शामिल किया गया है या नहीं। push-and-shove या कभी-कभी auto-complete जैसे tools तो हम पहले से इस्तेमाल कर रहे हैं
    यह market छोटा है, tools fragmented हैं, मौजूदा vendors सुस्त बड़ी कंपनियाँ हैं, और users picky enthusiasts हैं। KiCad को मैं किसी भी हाल में नहीं छोड़ सकता। autorouter JavaScript में लिखा है, इस बात पर मेरी कोई बड़ी राय नहीं है, लेकिन जानना चाहूँगा कि क्या CAD vendors या open-source tool ecosystem से जुड़ने की योजना है, या फिर लोगों को किसी और नए ecosystem में खींचने की कोशिश है

    • KiCad support हम ज़रूर करेंगे। placement को लेकर भी बड़े plans हैं, लेकिन पहले एक बहुत तेज़ और cache-friendly autorouter को आधार बनाना अहम मानता हूँ
      cache-friendly होने पर components को move करने और अलग layouts आज़माने की speed बहुत बढ़ जाती है। JavaScript अब QuickJS या Proffor जैसे छोटे runtimes तक के साथ काफ़ी portable है, और मुझे लगता है कि इसे local में run करके बड़े caches सीधे बनाए जा सकते हैं
      EDA में lock-in और ecosystem fragmentation ऐसी चीज़ें हैं जिनकी चिंता सबको करनी चाहिए, लेकिन tscircuit और यह autorouter MIT permissive license वाली technologies हैं, इसलिए EDA में दुर्लभ रूप से इन्हें सबके साथ interoperable बनाया जा सकता है
    • बहुत पहले गायब हो चुके और जिन्हें शायद ज़्यादा लोग miss भी नहीं करते, OrCAD Layout में netlist को spreadsheet की तरह देखने वाली screen थी, और autorouting constraints set करने के लिए वह ठीक-ठाक interface था
      footprints, placement, constraints और manually routed nets को fix कर देने के बाद आप बहुत तेज़ी से iterate कर सकते थे
      Cadence ने 90s में SPECCTRA acquire किया, उसके बाद से PCB autorouters काफ़ी ठहरे हुए रहे हैं, इसलिए अच्छा है कि कोई इस field को फिर से छू रहा है। मेरी याद में SPECCTRA बनाने वाले लोग VLSI की तरफ चले गए और वापस नहीं आए; लगता है नाम और पैसा वहीं था। कुछ समय तक यह patent minefield भी रहा होगा, और शायद अब भी हो
      auto-placement तब भी पूरी तरह मुश्किल problem थी और आज भी वैसी ही लगती है, लेकिन generative AI approach अच्छी fit हो सकती है। अच्छी generative AI-based initial component placement कुल समय घटा सकती है। सबसे बड़ी समस्या ज़िद्दी लोगों को यह समझाना है कि perfect न होने पर भी यह sufficiently good हो सकती है
      schematic-as-code करने की कोशिशें मुझे थोड़ी अजीब लगती हैं। backend format के रूप में अगर यह अच्छा चले तो ठीक है, और खासकर jitx की तरह app notes और datasheet-level design rules को component models में encode करने वाली progress अच्छी लगती है। commercial design के लिए ज़रूरी स्तर पर सभी datasheets पढ़ना जितना लगता है उससे कहीं ज़्यादा काम है, और junior engineers को वह process सिखाना भी वैसा ही है, इसलिए automation फ़ायदेमंद है
      लेकिन approaches की जड़ में यह सोच लगती है कि schematic layout के लिए data input है, यानी एक तरह का source code। schematic एक design document भी है, जिसकी अपनी सावधानी से विकसित visual language है और जो उन लोगों के लिए भी accessible होनी चाहिए जिनके पास EDA suite install नहीं है। Adafruit/Sparkfun/Shenzhen style की तरह explicit wiring को minimize करने वाली schematics पढ़कर सीखने वाले लोग शायद अच्छी schematic की value ठीक से न समझें
      एक और बात यह है कि analogy पर बहुत ज़्यादा निर्भर होकर PCB-level design को VLSI design जैसा बनाने की tendency है। मैं इसे पूरी तरह असंभव नहीं मानता। DRC और verification tools बेहतर हों तो component-level design भी VLSI के ज़्यादा करीब आ सकता है। लेकिन design, EDA/CAM/simulation, verification, manufacturer, assembler, component vendor और regulatory/certification agencies के बीच coupling इतनी loose है कि इनमें से किसी एक कोने को भी सही से कर लेना बड़ी उपलब्धि है
    • autorouter से मिलने वाला फायदा अक्सर बाद में project cost के रूप में लौट आता है
      आजकल impedance-controlled UHF design domain-specific simulation tools के साथ किया जाता है। इसलिए पहले critical traces manually route करते हैं, island poles बनाते हैं, और अंत में power connections handle करते हैं
      KiCad layout न होने से थोड़ा बेहतर है, लेकिन उसे एक और आधा-अधूरा simulation tool बनाने की कोशिश करना हास्यास्पद लगता है
    • पिछले 5 सालों में KiCad development सचमुच शानदार रहा है। हाल की दो releases में दो बड़े features आए हैं जो professional CAD tools में थे लेकिन KiCad में नहीं थे
      database support और outjob feature। बाकी बात adoption और users इस feature का कैसे उपयोग करते हैं, इस पर ज्यादा निर्भर है, और database के साथ आम तौर पर data cleanup को लेकर internal bureaucracy ज़्यादा आती है
      layout को तेज़ करने वाले workflow के लिहाज़ से KiCad भी पहले से कुछ हद तक उसी दिशा में जा रहा है, ऐसा लगता है। उदाहरण के लिए 7.0 के आसपास आया “trace auto-complete” feature है। pcbnew में shortcut शायद F था; यह मौजूदा placement में track की trace बिछा देता है। “route from the other side of track” shortcut E के साथ इस्तेमाल करने पर, अलग-अलग दो ballout grids के बीच काम करते समय productivity काफ़ी बढ़ जाती है
      version 9 में buses या कई tracks को drag किया जा सकता है, जिससे यह flow और तेज़ हो सकता है
      सच कहूँ तो अगर satisfactory placement तक पहुँचा जा सके और autorouter को routing position constraints दिए जा सकें, तो design का बड़ा हिस्सा autorouter को सौंपा जा सकता है। उदाहरण के लिए पिछले साल मैंने NXP iMX8MP और eMMC वाला board किया था; processor periphery ballout eMMC ballout से अच्छी तरह match कर रहा था, इसलिए chips align करके बस lines draw करनी थीं। अगर autorouter को सिर्फ यह पता होता कि data bus को top layer पर रखना है, तो उसने 10 मिनट का काम कुछ seconds में कर दिया होता
      autorouter projects के साथ success criteria की समस्या होती है। लगता है वे तभी “complete” माने जाते हैं जब board की हर चीज़ handle कर सकें, लेकिन एक practicing electrical engineer के तौर पर मैं यह नहीं चाहता। मैं ऐसा autorouter चाहता हूँ जो design के छोटे-छोटे chunks मेरे साथ handle करे, review करने का समय दे, फिर अगले chunk पर जाए
      अगर layer-crossing constraints तक दिए जा सकें तो यह powerful होगा। उदाहरण के लिए, “D0-7 नाम के सभी nets को layer 1 और 3 पर रखो, उनकी lengths एक-दूसरे से 5mm के भीतर match करो, और D0 को length reference बनाओ” जैसा। अगर यह कर सके तो DRAM length tuning solve हो गया, और कहीं ज़्यादा complex designs सामान्य users के लिए भी संभव हो जाएँगे
      समय मिला तो मैं demo में दिखाना चाहूँगा कि मेरा मतलब क्या है
    • एक बार मुझे autorouted prototype PCB लेकर bring-up करना पड़ा था। CPU और DRAM के बीच traces board के तीन चक्कर लगा रही थीं

  • बिंदु 8 में Monte Carlo method को बहुत जल्दी खारिज कर देना बड़ी गलती थी
    Monte Carlo का मूल यही है कि आप accuracy और speed के बीच trade-off कर सकते हैं। algorithm को जितनी देर चलाएँगे, यह उतना ही ज़्यादा accurate होगा
    इससे भी दिलचस्प बात यह है कि इसका उल्टा भी अक्सर काम आता है। आप बहुत inaccurate नतीजा बहुत तेज़ी से पा सकते हैं। सभी paths explore करने के बजाय random चुना हुआ सिर्फ एक path explore करना, कुछ ऐसा
    यह तरीका algorithm के सबसे अंदर वाले nested loop में डालने पर सबसे ज़्यादा चमकता है। उदाहरण के लिए, अगर automatic routing सीखने वाला neural network train करना हो, तो outer loop neural network parameters update करता है, और inner loop graph से होकर जाने वाला path compute करता है
    Monte Carlo इस्तेमाल करने पर, अगर bias न हो, तो accuracy control करने वाले इस inner loop को 1 iteration तक घटाया जा सकता है। variance बढ़ जाएगा, इसलिए outer loop धीमा होगा, लेकिन machine learning “सैद्धांतिक रूप से” सीख सकती है
    इसलिए chess या Go की तरह intuitively सही फैसले चुनने वाली policy बनाई जा सकती है। AlphaGo Zero, AlphaChess Zero, AlphaRouter Zero जैसे Monte Carlo tree search variants में, search हिस्सा न भी हो तो neural network parameters में encoded विशाल cache, training के बाद neural network के एक pass में, यानी constant time में, best estimated path compute कर सकता है। इस constant को parameters बढ़ाकर या ज़्यादा देर train कराके memory और speed के बीच आसानी से trade किया जा सकता है

    • लेख पढ़ते समय MC को खारिज करने वाले हिस्से पर मेरी भी बिल्कुल वही प्रतिक्रिया थी
      MC ऐसा algorithm है जो reality check देता है। यह धीमा है, लेकिन लगभग हमेशा implementation बहुत simple होता है, और यह बहुत भरोसेमंद तरीके से, बहुत high confidence के साथ दोबारा जाँच सकता है कि आप पूरी तरह गलत दिशा में तो नहीं भटक गए
    • हालांकि लेखक ने simulated annealing का ज़िक्र किया है, इसलिए SA की gradient compute न करने वाली प्रकृति देखते हुए, संभवतः वे neural network आज़मा नहीं रहे थे

  • automatic routing पर बेहतरीन चर्चा है, लेकिन आखिर में “electronics के vibe-building को संभव बनाने वाला key piece” कहकर खत्म हुआ, तो थोड़ा चुभा
    routing अपने-आप में आसान है। जैसे ही नया route डालने के लिए पहले से बिछाई गई चीज़ों को उखाड़ना पड़े, complexity बढ़ती है और combinatorial explosion टूट पड़ता है
    पहले KiCad में जो autorouter था, उसकी याद आती है। वह अस्पष्ट intellectual property वजहों से हटा दिया गया था, क्योंकि उसके लेखक ने कभी एक autorouting company में काम किया था। उसे वापस डालने की माँग करने वाले users को “असली मर्द autorouter इस्तेमाल नहीं करते” जैसी प्रतिक्रिया मिलती थी
    https://forum.kicad.info/t/autorouting-and-autoplacement/185...

    • “vibe-*” पर सही प्रतिक्रिया शायद सहम जाना ही है। आजकल जब भी कोई vibe-coded app promote करता है, मैं थोड़ा सहम जाता हूँ, लेकिन जब मैं अपने coding शुरू करने के दिनों को याद करता हूँ, तो पुराने ActionScript forums पर लोगों से अपना code ठीक कराने के लिए लगातार परेशान करता था, और किसी भी field में लोगों को जल्दी शुरुआत करने में सक्षम बनाना बहुत बड़ा potential रखता है
      उम्मीद है कि यह autorouter और इसके बाद आने वाले tools लोगों को बहुत सारे guidance या formal education के बिना अपना पहला electronics product launch करने में मदद करेंगे
      बेशक अच्छा autorouter experts के लिए भी useful होना चाहिए, इसलिए उम्मीद है कि उस हिस्से में भी मदद मिलेगी
    • मैं चाहता हूँ कि ये लोग सफल हों, और अच्छा होगा अगर autorouter KiCad में integrate हो जाए
      लेकिन उन चिड़चिड़े पुराने लोगों में से एक होने के नाते, जो KiCad को autorouter पर ज़्यादा effort लगाते देखना नहीं चाहते, PCB autorouters हमेशा सिरदर्द रहे हैं और ठीक से काम नहीं करते
      ऐसा क्यों है, यह VLSI autorouters को देखकर समझा जा सकता है। VLSI autorouters भी सिरदर्द थे और ठीक से काम नहीं करते थे। फिर VLSI में बहुत सारे layers हो गए, और vertical routing के लिए layer, horizontal routing के लिए layer, power के लिए layer अलग allocate करने के बाद भी global vertical connections, global horizontal connections और global power के लिए कुछ और layers रख पाना संभव हो गया
      PCB autorouting की बुनियादी समस्या यह है कि PCB में VLSI chip की तुलना में obstacles कहीं ज़्यादा होते हैं। पहला, components खुद obstacles और bottlenecks होते हैं। दूसरा, PCB vias लगभग हमेशा board के सभी layers को block करते हैं, जबकि VLSI vias सिर्फ उन दो layers को block करते हैं जिन्हें वे connect करते हैं। तीसरा, PCB vias आम तौर पर routing metal की width से बड़े होते हैं। चौथा, PCB में इस्तेमाल होने वाले layers की संख्या VLSI से बहुत कम होती है। आम तौर पर 4-layer होते हैं, जिनमें से general routing के लिए ठीक से सिर्फ 2 ही इस्तेमाल होते हैं; cost की वजह से 2-layer भी बहुत हैं और उन्हें autoroute करना और कठिन है, जबकि 6-layer बहुत कम होते हैं
      नतीजतन PCB autorouting, VLSI autorouting से कहीं ज़्यादा complex काम है

  • लेख में visualization और cache effects को खास तौर पर अहमियत देना अच्छा लगा
    लेकिन कुछ बातें खटकती हैं। “recursive algorithm depth-first search होता है, और candidates या neighbors को sort किए बिना explore करने वाला loop breadth-first search होता है” — यह बात गलत है या शायद intuition छूट गई है। DFS और BFS दोनों को loop या recursion से लिखा जा सकता है; असली फर्क यह है कि अगला candidate stack के ऊपर से निकाला जाता है या नीचे से, यानी stack (FILO) इस्तेमाल होता है या queue (FIFO)
    A* को सभी information-based search का सबसे अच्छा आधार कहना भी context मांगता है। जब लक्ष्य तक की कोई आसानी से calculate होने वाली “distance” की अवधारणा हो और उसी graph पर सिर्फ कुछ queries चलानी हों, तब यह pathfinding में उपयोगी है। अगर road network जैसे लगभग static graph पर बहुत सारी queries चलाने की योजना है, तो contraction hierarchy जैसे preprocessing algorithms बेहतर हो सकते हैं। Travelling Salesman Problem की तरह optimization करनी हो लेकिन लक्ष्य तय न हो, तो 2-opt जैसी दूसरी local search heuristics बेहतर हो सकती हैं
    “BFS सभी adjacent nodes explore करता है और A* destination के करीब nodes को priority देता है” — यह फर्क तो है, लेकिन बड़ा फर्क यह है कि A* एक dynamic algorithm है। इसलिए shortest path मिल गया है, इस भरोसे के साथ वह जल्दी terminate कर सकता है। BFS शायद पूरे graph को explore किए बिना आश्वस्त न हो पाए, और graph बहुत बड़ा हो सकता है

    • Recursion का DFS के करीब लगना इस intuition से आता है कि लोग आम तौर पर algorithm को recursion में तब लिखते हैं जब वह stack के top से interact करने वाली structure पर आसानी से map हो जाता है
      ज्यादातर languages में external stack लेकर सोचने की तुलना में इसे इस तरह express करना आसान होता है। इसलिए असली code में recursion दिखे तो उसके DFS के करीब होने की संभावना ज्यादा है, लेकिन यह कोई कड़ा नियम नहीं है
    • BFS, DFS, A* को एक ही algorithm माना जा सकता है, जिसमें बस unexplored nodes को track करने वाली data structure अलग होती है
      BFS FIFO queue इस्तेमाल करता है, DFS LIFO stack, और A* आम तौर पर heap से implement की गई priority queue इस्तेमाल करता है
    • BFS का मतलब यह नहीं कि पूरा graph अनिवार्य रूप से explore करना पड़े। जिस पल किसी node तक पहली बार पहुंचते हैं, उसी पल 100% पता होता है कि वह path shortest path है
      यह BFS के सही result देने वाले मूल invariants में से एक है, इसलिए सभी targets तक पहुंच जाने पर जल्दी terminate किया जा सकता है
      A* और BFS का फर्क यह है कि BFS दो points के बीच shortest path नहीं, बल्कि single start point से graph के हर point तक shortest path ढूंढता है। A* एक कमजोर सवाल का जवाब देने के बदले individual queries को तेज करने वाला trade-off है
      अगर problem structure अनुमति दे, तो हजारों A* calls को एक BFS या Dijkstra call से बदलने भर से भी बड़ा speedup मिल सकता है। एक और अहम फर्क यह है कि BFS केवल उन graphs में काम करता है जहां सभी edge lengths समान हों, जबकि A* अलग-अलग edge lengths support करता है। दोनों एक-दूसरे के substitutes नहीं हैं, ठीक वैसे ही जैसे list में minimum element ढूंढना list sorting का substitute नहीं होता

  • “quadtree और सभी general-purpose tree data structures बेहद धीमे हैं”, “tree data के बारे में जानकारी वाली representation नहीं है”, “हर बार tree इस्तेमाल करते समय आप O(~1) hash algorithm की जगह ज्यादा जटिल O(log N) algorithm इस्तेमाल कर रहे होते हैं” — ये बातें काफी गलत दिशा में जाती हैं
    hashing approach तब ठीक है जब points uniformly distributed हों और आप चुने हुए fixed partition के करीब वाले regions ही query कर रहे हों। नहीं तो वह O(1), O(n) में ढह सकता है
    जब data distribution पता न हो, tree एक informative representation होता है
    randomized algorithms भी ऐसे ही हैं। अगर search space खरबों या उससे अधिक items या possibilities से बना हो तो क्या करेंगे? अगर heuristic भी न हो? brute force संभव न हो और clever algorithm भी इस्तेमाल न कर सकें, तब randomized algorithm बचाव बन जाता है
    इस specific application में इसकी जरूरत न हो सकती है, लेकिन generalized assertions से बचना बेहतर है

    • Measure, measure, measure जरूरी है। हर case अलग होता है
      ज्यादा गंभीरता से कहें तो tree-based algorithms को overrate करने की tendency है, और लोग Big-O behavior में इतना फंस जाते हैं कि भूल जाते हैं कि constant factors लाखों elements तक भी बहुत मायने रखते हैं। data locality जैसी चीजें भी ऐसी ही हैं। कभी-कभी ज्यादा complex structure की bookkeeping करने की बजाय sequential scan से सीधे गुजर जाना तेज होता है
      कुल मिलाकर operations को छोटे wrappers में लपेटना, पहले आसान implementation बनाना और फिर measurement से फैसला करना बेहतर है
      worst case में बेहतर performance के लिए किसी दूसरी structure के हिसाब से पूरा program फिर से लिखना पड़ सकता है, लेकिन अनुभव के मुताबिक file को शुरू से दोबारा लिखने पर कई मुफ्त improvements भी साथ मिल जाते हैं
    • 3D में octree बहुत प्रभावी और तेज था। मेरे implementation में tree को regenerate किए बिना भी items को move किया जा सकता है
      अभी तक 2D या 3D points store करने और nearby points query करने का संतोषजनक तरीका नहीं मिला। kD tree अच्छा है, लेकिन मैं fixed set पर structure बनाने के बजाय points को चलते-चलते add करना चाहता हूं

  • लगभग सारी बातें मेरी गेम डेवलपमेंट heuristics से मेल खाती हैं। JavaScript चुनना भी समझ में आता है
    मैं अभी Lisp-स्टाइल S-expressions पर चलने वाला एक गेम modding framework बना रहा हूँ, और मुझे समझ आया है कि creative iteration time घटाने वाली optimization सबसे ज़्यादा अहम है
    A*, Lee algorithm जैसी चीज़ें सब शानदार हैं। किसी भी तरह के flood fill के साथ visualization न बनाना लगभग अपराध जैसा है। यह dopamine की बहुत बर्बादी है
    यह लेख देखकर मुझे उत्सुकता हुई कि जो techniques मैंने नहीं पढ़ीं लेकिन game development के आसपास हैं, क्या वे ऐसे problems में भी काम आ सकती हैं। शायद मैं पहला व्यक्ति नहीं हूँ जिसे लगा हो कि boids router काफी मज़ेदार होगा। ज़्यादा गंभीरता से कहूँ तो jump flooding आधारित signed distance field बहुत power दे सकता है
    खासकर spatial hashing वाली बात मेरे अनुभव से मेल खाती है। लगभग 20 सालों में मैंने बहुत कम बार देखा है कि tree structures अपने लगाए गए समय के लायक रहे हों। एक अपवाद है: मेरा बनाया Lovecraftian text editor responsiveness संभालने के लिए trie का काफी इस्तेमाल करता है। 45,000 शब्दों को event handling के लिए compressed state machine में बदलने का यह अच्छा तरीका था

    • boids router बनाना वाकई मज़ेदार idea है। इसे बाद के लेख के लिए बचाकर रखना चाहिए
      मैंने पहले recursive pattern autorouter के बारे में लिखा था, जहाँ solution space छोटा है, इसलिए मौजूदा machine learning algorithms से predict करना अपेक्षाकृत आसान है। autorouting में अभी भी बहुत सारे दिलचस्प unexplored areas हैं
      मुझे jump flooding के बारे में पता नहीं था। दूसरों के लिए जोड़ दूँ: यह distance fields को तेज़ी से parallel में approximate करने वाला algorithm है। यह निश्चित रूप से रोचक हो सकता है, बताने के लिए धन्यवाद
    • पहले memory और cache छोटे होते थे, इसलिए trees कहीं ज़्यादा उपयोगी रहे होंगे। मुझे लगता है preprocessing में वे अब भी उपयोगी हो सकते हैं, लेकिन fixed grid और smart sizing को trees के मुकाबले सीधे benchmark करना पड़ेगा
      Trees recursive algorithms के साथ भी अच्छी तरह फिट होते हैं, और लेखक ने कहा कि iterative algorithms को recursive से चुनने की वजह है, इसलिए ये सलाहें आपस में जुड़ी हुई हैं
      व्यापक रूप से देखें तो “recursive” और “non-recursive” का फर्क कुछ हद तक artificial है। असली सवाल है: “flow control कोई पहले से बना algorithm, जिसके कठोर rules हैं, संभालता है या मैं संभालता हूँ?” अगर performance की बहुत चिंता है, तो जवाब होना चाहिए कि मैं संभालूँ; और जब execution state runtime environment द्वारा दिए गए stack में abstract हो जाती है, जिससे runtime पर उसे अजीब तरीकों से बदलना मुश्किल हो जाता है, तो वह बाधा बनने लगती है

  • “focus का 95% iteration count घटाने पर होना चाहिए। इसलिए language मायने नहीं रखती” बात कुछ हद तक सही है, लेकिन अगर आप playful और expressive interpreted/abstract/slow language में बेहतरीन और performant algorithm बना लेते हैं और फिर भी performance अहम है, तो उसी चीज़ को किसी performant low-level language में फिर से लिख सकते हैं, और ज़रूरत पड़े तो architecture-specific assembly तक लिख सकते हैं
    numpy, pandas, OpenCV, TensorFlow के pure Python में न लिखे जाने की वजह है। Python की भूमिका high-performance C++/assembly/CUDA आदि में implemented कामों को निर्देश देने की है
    problem space explore करने और efficient algorithm खोजकर ब्लॉग लिखने पर चाहे जितना गर्व हो, अगर आप pure Python या JavaScript में ही लिखने पर अड़े रहते, तो लोकप्रिय numerical computing library बनना मुश्किल होता
    लेख दिलचस्प है, लेकिन अगर लेखक की algorithmic insight से pure JavaScript HEVC encoder प्रति frame 1 दिन से घटकर 3 घंटे पर आया होता, तो शायद वही निष्कर्ष निकालना कठिन होता

  • कॉलेज के समय याद किए हुए keywords बहुत दिख रहे हैं। काश famous और cool algorithms इस्तेमाल करने का मौका मिले
    असल में मैं बस UI components और REST API बनाकर Elasticsearch results दिखाने का काम कर रहा हूँ। सारी दिलचस्प चीज़ें black box के अंदर दबी हुई हैं

    • LLMs को geometry heuristics काफी याद हैं, इसलिए इन दिनों algorithms कहीं ज़्यादा मज़ेदार हो गए हैं
      game development में कई algorithms से बचना मुमकिन नहीं होता, इसलिए अगर algorithms बनाना चाहते हैं तो tower defense जैसी चीज़ बनाकर देखें; उसमें कई classic algorithms से सामना होगा
    • मुख्य समस्या academic curriculum और real hiring market की demand के बीच गंभीर mismatch है, और यह भी कि कंपनियाँ risk filter करने और ADA/anti-discrimination laws को bypass करने के proxy metric के रूप में “college degree required” का इस्तेमाल करती हैं। दोनों economy के लिए बड़ा waste हैं
      कम से कम मौजूदा computer science degree को तोड़ना चाहिए। cool math वाला हिस्सा अलग degree होना चाहिए और शायद AI से जुड़ी नई degree के साथ जोड़ा जा सकता है। database और network theory भी अलग degrees होनी चाहिए, और low-level assembly भी। electronic components, NAND gates, Boolean algebra आदि कैसे काम करते हैं, यह electrical engineering में जाना चाहिए
      market को सबसे ज़्यादा जिन लोगों की जरूरत है—जो CRUD apps बना सकें—अगर insist करना है कि उनके लिए academic knowledge जरूरी है, तो उसके लिए अलग degree बनाएं या इसे vocational education में ले जाएं
      साथ ही hiring requirements की gatekeeping को भी कानून से handle करना चाहिए। ऐसी degrees मांगने की अनुमति नहीं होनी चाहिए जिनका वास्तविक job से लगभग कोई संबंध नहीं है। अभी यह बच्चों से उनकी जिंदगी के कई साल बर्बाद कराता है, उन्हें पाँच से छह अंकों के डॉलर debt में डालता है, और सिर्फ कंपनियों के लिए लोगों को filter करना आसान बनाता है

  • मैं 2D/3D spatial problems को सीधे handle नहीं करता, लेकिन सबसे बड़ा सबक visualization की value है
    इंसान images को समझने और analyze करने में बहुत अच्छे होते हैं। एक और बात यह है कि पहले probabilistic methods या brute force से problem का shape समझा जाए, फिर सिर्फ pure theoretical understanding पर नहीं, बल्कि उसी के हिसाब से बेहतर तरीका चुना जाए

  • “implementation language मायने नहीं रखती” इस field में सही हो सकता है, लेकिन अगर इसे general software engineering पर लागू करें, तो यह assumption कि language choice speed और आवश्यक iteration count को प्रभावित नहीं करती, मुझे काफी गलत लगता है

    • Big-O स्तर के algorithm improvements खोजते समय तेज़ या धीमी language execution से बनने वाला effective constant factor premature optimization हो सकता है—यह argument valid है
      अगर आप exponential या polynomial terms को control करने वाले stage में हैं, तो Rust या hardcoded assembly और JavaScript या VisualBasic के बीच का फर्क काफी meaningless हो सकता है
    • मुझे लगता है JavaScript autorouter को small-scale designs या बहुत लंबे processing times तक सीमित कर सकता है, लेकिन मैंने tscircuit इस्तेमाल नहीं किया है, इसलिए मैं गलत भी हो सकता हूँ