Autorouter विकसित करने से पहले जो बातें पता होतीं तो बेहतर होता

"दुनिया का सबसे तेज़ automatic router (Autorouter) बनाने के लिए अहम सबक"

A* algorithm का हर जगह उपयोग करें

• A* search problems में सबसे शक्तिशाली और लचीले algorithms में से एक है
• यह सिर्फ़ साधारण 2D grid ही नहीं, बल्कि कई तरह की समस्याओं में इस्तेमाल किया जा सकता है
• A* , BFS की तुलना में तेज़ और अधिक efficient है, क्योंकि यह destination के करीब nodes को पहले खोजने वाला 'information-based search' है
• मौजूदा code में इस्तेमाल हो रहे DFS या BFS को ज़्यादातर मामलों में A* से बदला जा सकता है
• performance सुधारने के लिए कई A* instances चलाकर, जिन settings का प्रदर्शन बेहतर हो उन्हें ज़्यादा resources देने की technique इस्तेमाल की गई

Programming language से ज़्यादा algorithm महत्वपूर्ण है

• autorouter को Javascript में विकसित करना बिल्कुल भी समस्या नहीं थी
• optimization का मूल यह है कि iterations की संख्या कम की जाए
• language performance से ज़्यादा महत्वपूर्ण यह है कि “आप कितना smart algorithm कितनी जल्दी बना सकते हैं”
• Javascript तेज़ iteration से ज़्यादा smart algorithms के लिए अधिक अनुकूल है

Tree structure की तुलना में Spatial Hash Indexing ज़्यादा efficient है

• Quadtree जैसी tree-based data structures आम तौर पर धीमी होती हैं
• Spatial Hash Index objects की position को hash करके spatially पास के objects को समूह में प्रोसेस करता है
• hash-based structure लगभग O(1) के बराबर search performance देता है
• Cell size सही चुनना ज़रूरी है, और उचित size चुनना बहुत मुश्किल नहीं है

Space partitioning और cache, algorithm से 1000 गुना ज़्यादा महत्वपूर्ण हैं

• जटिल circuit boards में भी ज़्यादातर बार-बार दोहराए जाने वाले patterns होते हैं
• game development की तरह precomputed results को cache करके performance में भारी सुधार किया जा सकता है
• cacheable structures और space partitioning भविष्य के autorouter की core बनेंगे
• storage space तेज़ी से सस्ता हो रहा है, और कुछ GB cache से भी performance में बड़ा सुधार संभव है

Visualization के बिना समस्या हल नहीं की जा सकती

• हर समस्या के लिए पहले visualization tools बनाकर काम शुरू किया गया
• visualization के ज़रिए debugging speed को 10 गुना से ज़्यादा बढ़ाया जा सका
• algorithm के साधारण चरणों को भी visualize करने पर समस्या की जड़ जल्दी समझी जा सकती है

Javascript के profiling tools बहुत उपयोगी हैं

• Chrome Developer Tools के Performance tab में code के हिसाब से समय देखा जा सकता है
• किसी अलग framework के बिना भी Flame Chart, memory usage आदि का आसानी से analysis किया जा सकता है
• यह performance debugging के लिए बेहद उपयोगी tool है

Recursive functions का उपयोग न करें

• recursive functions आम तौर पर synchronous होती हैं और उन्हें A* में बदलना मुश्किल होता है
• iterative implementation तेज़ होती है और visited nodes को track करना आसान बनाती है
• recursive functions में state change करना कठिन और inefficient होता है
• जहाँ तक संभव हो, loop-based implementation लिखें

Monte Carlo algorithms से बचें

• randomness-based algorithms non-deterministic होती हैं और debug करना कठिन होता है
• domain-specific heuristics हमेशा बेहतर performance देती हैं
• कोई PCB designer random तरीके से line नहीं खींचता → यह व्यावहारिक approach नहीं है
• हालांकि, शुरुआत में intuition पाने के लिए यह उपयोगी हो सकती है

Algorithm के चरणों को वास्तविक problem space में स्थिर रखें

• sub-algorithms को origin के आधार पर normalize करने से पूरे flow को समझना कठिन हो जाता है
• हर चरण के input/output को visualize करके पता लगाया जा सकता है कि कौन-सा चरण error पैदा कर रहा है
• coordinate system को consistent रखते हुए algorithm flow बनाए रखना महत्वपूर्ण है

Iterative process को animation के रूप में visualize करें

• इससे यह visually समझा जा सकता है कि algorithm कितनी inefficiently search कर रहा है
• animation iterations कम करने और efficiency बढ़ाने में बहुत प्रभावी है
• समस्या की स्थिति को आसानी से पकड़ा जा सकता है (उदाहरण: infinite loop में फँसी search)

Grid के बिना भी intersection-detection math काफ़ी है

• grid का उपयोग करने के बजाय vector math का इस्तेमाल करें तो यह कहीं ज़्यादा तेज़ है
• कई बार memory access की तुलना में mathematical operations तेज़ होती हैं
• LLM की वजह से intersection-detection math को implement करना भी आसान हो गया है
• अनावश्यक grid का उपयोग performance गिरने का कारण बनता है

हर चरण की failure probability मापकर समाधान की संभावना को प्राथमिकता दें

• हर space-partitioning node पर failure probability का अनुमान लगाया जा सकता है
• बाद के चरणों में fail होने की संभावना वाले nodes को पहले reconstruct या re-search किया जा सकता है
• failure probability को स्पष्ट रूप से मापा जा सकता है, और इसमें heuristics की तुलना में सुधार की संभावना ज़्यादा है
• कुल solvability बढ़ाना, optimization को लक्ष्य बनाने से ज़्यादा प्रभावी हो सकता है

Weighted A* से 100 गुना speedup संभव है

• basic A* optimal path की गारंटी देता है, लेकिन इसकी speed धीमी होती है
• Weighted A* ज़्यादा greedy तरीके से search करता है, जिससे speed में बड़ा सुधार हो सकता है
• इसे सिर्फ़ f(n) = g(n) + w * h(n) के weight setting से लागू किया जा सकता है
• optimality में थोड़ा समझौता करके भी समस्या को बहुत तेज़ी से हल किया जा सकता है
• यह game development में भी अक्सर इस्तेमाल होने वाली technique है और देखने लायक है

[GN⁺]

Hacker News राय

• Monte-Carlo method को जल्दी खारिज कर देना बड़ी गलती है

  • Monte-Carlo method की खासियत यह है कि इसमें accuracy और speed के बीच trade-off किया जा सकता है
  • algorithm को जितनी देर चलाया जाए, वह उतना अधिक accurate होता जाता है
  • इसके उलट, जल्दी inaccurate result भी प्राप्त किए जा सकते हैं
  • सभी paths को explore करने के बजाय, यह केवल एक randomly selected path को explore करता है
  • algorithm के सबसे deeply nested loop में Monte-Carlo का उपयोग करना प्रभावी होता है
  • उदाहरण के लिए, neural network को train करते समय outer loop neural network parameters को update करता है और inner loop graph के through path की गणना करता है
  • Monte-Carlo का उपयोग करके inner loop की accuracy को एक iteration तक घटाया जा सकता है
  • इससे सहज रूप से ऐसी policy बनाना संभव होता है जो हमेशा सही decision लेती है
  • chess या Go में Monte-Carlo tree search के variants का उपयोग करके optimal path की गणना की जा सकती है

• मेरी राय "autorouter पर भरोसा मत करो" वाली है

  • eCAD क्षेत्र में layout speed बढ़ाने का बड़ा अवसर है
  • पूरी automation tool की बजाय co-creation tool इस्तेमाल किए जाने की संभावना अधिक है
  • design की शुरुआत में placement तय नहीं होता, और इसका routing पर बड़ा प्रभाव पड़ता है
  • पेज में यह स्पष्ट नहीं है कि placement algorithm का हिस्सा है या नहीं
  • JavaScript में लिखे गए AR की योजना के बारे में जिज्ञासा है

• लेख visualization और cache effects के बारे में महत्वपूर्ण बात करता है

  • recursive algorithms depth-first search होते हैं
  • DFS और BFS को iterative या recursive दोनों तरह से लिखा जा सकता है
  • A* pathfinding के लिए उपयोगी है
  • BFS सभी adjacent nodes को explore करता है, जबकि A* destination के करीब वाले nodes को प्राथमिकता देता है
  • A* एक dynamic algorithm है, जो shortest path मिलने पर confidence के साथ जल्दी terminate कर सकता है

• autorouting पर शानदार चर्चा है

  • routing खुद में आसान है
  • जटिलता तब बढ़ती है जब कुछ नया fit करने के लिए पहले से routed चीजों को हटाना पड़े
  • KiCAD के autorouter की याद आती है

• 95% फोकस iterations की संख्या घटाने पर होना चाहिए

  • अगर performance तब भी महत्वपूर्ण रहे, तो low-level language में फिर से लिखना चाहिए
  • numpy, pandas, OpenCV, TensorFlow high-performance C++/assembly/CUDA में implement किए गए हैं

• QuadTree और सामान्य tree data structures बहुत धीमे हैं

  • tree, data का information representation नहीं है
  • hashing approach केवल तब उपयुक्त है जब points समान रूप से distributed हों
  • random algorithms तब उपयोगी होते हैं जब search space बहुत बड़ा हो

• लगभग सब कुछ game development की heuristics से मेल खाता है

  • A*, Lee's algorithm आदि सब शानदार हैं
  • visualization के बिना flood fill लिखना अपराध है
  • spatial hashing वाला बिंदु खास तौर पर अनुभव से मेल खाता है

• "spatial hash indexing > tree data structure" इस domain में अच्छा हो सकता है, लेकिन इसे सार्वभौमिक सत्य नहीं मानना चाहिए

  • अगर points समान रूप से distributed न हों, तो hash function खराब हो सकता है

• विश्वविद्यालय में सीखे गए keywords याद हैं

  • fancy algorithms इस्तेमाल करने का मौका नहीं मिलता
  • उसकी जगह UI components और REST API बनाता हूँ

• जो लोग सीधे 2D/3D spatial problems में शामिल नहीं हैं, उनके लिए visualization का मूल्य सबसे बड़ा सबक है

  • इंसान चित्रों को समझने और उनका विश्लेषण करने में बेहद अच्छे होते हैं
  • समस्या के आकार को समझने के लिए probabilistic या brute-force methods का उपयोग करने का विचार महत्वपूर्ण है