OrthoRoute | Benchoff Design Portfolio

यह दस्तावेज़ Github रिपॉजिटरी में README का पूरक है। README प्रदर्शन, क्षमताओं और परीक्षणों के बारे में जानकारी प्रदान करता है। यह दस्तावेज़ इस बात पर अधिक प्रकाश डालता है कि ऑर्थोरूट का विकास क्यों और कैसे किया गया।

यह आवश्यकता से उत्पन्न एक परियोजना है। एक और चीज़ जिस पर मैं काम कर रहा था उसकी ज़रूरत थी विशाल बैकप्लेन. सोलह कनेक्टर वाला एक पीसीबी, प्रत्येक कनेक्टर पर 1,100 पिन। वह 17,600 व्यक्तिगत पैड और 8,192 एयरवायर हैं जिन्हें रूट करने की आवश्यकता है। यहाँ, बस एक नज़र डालें:

उस गंदगी को देखो. इसे हाथ से रूट करने में महीनों लगेंगे। हंसी के लिए, मैंने KiCad ऑटोराउटर प्लगइन, FreeRouting को आज़माया और इसने सात घंटों में 4% ट्रेस को रूट कर दिया। यदि यह प्रवृत्ति कायम रही, जो कि नहीं रही, तो वह ऑटोरूटिंग का एक महीना होगा। और यह संभवत: अंत में काम नहीं करेगा। मेरे पास कुछ विकल्प थे, जिनमें से सभी में बहुत लंबा समय लगेगा

• मैं बोर्ड को हाथ से रूट कर सकता हूं। यह दर्दनाक होगा और इसमें कई महीने लगेंगे, लेकिन अंत में मुझे एक अच्छा दिखने वाला बोर्ड मिलेगा।
• मैं सब कुछ YOLO कर सकता हूँ और बस FreeRouting ऑटोराउटर को इसे संभालने देता हूँ। इसमें कई हफ्ते लगेंगे, क्योंकि पहले निशान आसान होते हैं, आखिरी निशान में सबसे अधिक समय लगता है। इसका परिणाम एक बदसूरत बोर्ड होगा.
• मैं KiCad के लिए अपना स्वयं का ऑटोराउटर प्लगइन बनाने में एक या दो महीने लगा सकता हूँ। मेरे पास काफी शक्तिशाली जीपीयू है और मैंने सोचा पीसीबी को रूट करना एक बहुत ही समानांतर समस्या है। तैयार उत्पाद को अच्छा दिखाने के लिए मैं अपना स्वयं का रूटिंग एल्गोरिदम भी लागू कर सकता हूं।

जब किसी ऐसे कार्य का सामना करना पड़े जिसमें महीनों लगेंगे, तो हमेशा अधिक दिलचस्प रास्ता चुनें।

एक नया KiCad API, और एक ‘पारंपरिक’ ऑटोराउटर

KiCad, पूर्व-संस्करण 9.0, में SWIG-आधारित प्लगइन सिस्टम था। KiCad 9 के साथ जारी नए IPC प्लगइन सिस्टम की तुलना में इस सिस्टम में गंभीर कमियाँ हैं। SWIG-आधारित सिस्टम KiCad के साथ बंडल किए गए Python वातावरण में लॉक किया गया था। प्रक्रिया अलगाव, थ्रेडिंग और प्रदर्शन बाधाएँ एक समस्या थीं। CuPy या PyTorch के साथ GPU प्रोग्रामिंग करना, हालांकि असंभव नहीं है, कठिन है।

KiCad के लिए नया IPC प्लगइन सिस्टम एक वरदान है। ऑर्थोरूट प्लगइन की मूल संरचना कुछ इस तरह दिखती है:

ऑर्थोरूट प्लगइन यूनिक्स-आई सॉकेट पर आईपीसी एपीआई के माध्यम से KiCad के साथ संचार करता है। यह एपीआई मूल रूप से C++ कक्षाओं का एक समूह है जो मुझे बोर्ड डेटा – नेट, पैड, कॉपर पोर ज्योमेट्री, एयरवायर और बाकी सभी चीजों तक पहुंच प्रदान करता है। यह मुझे पायथन स्क्रिप्ट के अंदर पीसीबी का दूसरा मॉडल बनाने और उसे अपनी इच्छानुसार मॉडल करने की अनुमति देता है। अंदर एक बोर्ड के दूसरे मॉडल के साथ मेरा प्लगइन, मुझे बस बाकी उल्लू का चित्र बनाना है।

मैनहट्टन रूटिंग इंजन का विकास

मेरे सिर को चारों ओर लपेटने की क्षमता के बाद पढ़ना और लिखना KiCad से आने-जाने वाली बोर्ड जानकारी के लिए, मुझे इस मूर्खतापूर्ण जटिल बैकप्लेन को रूट करने का एक तरीका निकालना था। एक गैर-ऑर्थोगोनल ऑटोराउटर एक अच्छा प्रारंभिक बिंदु है, लेकिन मैंने इसे केवल KiCad आईपीसी एपीआई के चारों ओर अपना सिर लपेटने के अभ्यास के रूप में उपयोग किया है। वास्तविक निर्माण एक ‘मैनहट्टन ऑर्थोगोनल रूटिंग इंजन’ है, जो मेरे बैकप्लेन की गड़बड़ी को दूर करने के लिए आवश्यक उपकरण है।

प्रोजेक्ट पाथफाइंडर

इस ऑटोराउटर के लिए उपयोग किया जाने वाला एल्गोरिदम पाथफाइंडर है: एफपीजीए के लिए एक बातचीत-आधारित प्रदर्शन-संचालित राउटर। पाथफाइंडर का मेरा कार्यान्वयन पीसीबी को एक ग्राफ के रूप में मानता है: नोड्स एक एक्स-वाई ग्रिड पर चौराहे हैं जहां विया जा सकते हैं, और किनारे चौराहों के बीच के खंड हैं जहां तांबे के निशान चल सकते हैं। प्रत्येक किनारे और नोड को एक साझा संसाधन के रूप में माना जाता है।

पाथफाइंडर पुनरावृत्तीय है. पहले पुनरावृत्ति में, सभी नेट (एयरवायर) को रूट किया जाता है लालच सेनोड्स या किनारों के अति प्रयोग को ध्यान में रखे बिना। बाद के पुनरावृत्तियों से भीड़भाड़ होती है, अत्यधिक उपयोग किए गए किनारों की “लागत” बढ़ जाती है और सबसे खराब अपराधियों को फिर से रूट करने के लिए तैयार किया जाता है। समय के साथ, एल्गोरिथ्म अभिसरण एक पीसीबी लेआउट के लिए जहां कोई भी किनारा या नोड एकाधिक नेट द्वारा ओवर-सब्सक्राइब नहीं किया जाता है।

इस आर्किटेक्चर के साथ – एक बहुत बड़े ग्राफ पर पाथफाइंडर एल्गोरिदम, सबसे बड़े एफपीजीए के परिमाण के समान क्रम के भीतर – यह जीपीयू त्वरण के साथ एल्गोरिदम को चलाने के लिए समझ में आता है। इस निर्णय में कुछ कारक शामिल हैं:

1. हर कोई जो विशाल बैकप्लेन को रूट कर रहा है, उसके पास संभवतः एक गेमिंग पीसी है। या आप इस महीने MUNI बस स्टॉप पर जो भी कंपनी विज्ञापन दे रही है, उससे एक GPU किराए पर ले सकते हैं।
2. पाथफाइंडर एल्गोरिदम को प्रत्येक पुनरावृत्ति के लिए सैकड़ों अरबों गणनाओं की आवश्यकता होती है, जिससे सिंगल-कोर सीपीयू गणना बहुत धीमी हो जाती है।
3. CUDA के साथ, मैं एक भारित ग्राफ़ के माध्यम से बहुत तेजी से पथ खोजने के लिए एक SSSP (समानांतर डिज्क्स्ट्रा) लागू कर सकता हूं।

एफपीजीए एल्गोरिदम को पीसीबी में अपनाना

मूल पाथफाइंडर पेपर था, “एफपीजीए के लिए एक बातचीत-आधारित प्रदर्शन-संचालित राउटर” और 1995 से, इसका मतलब शुरुआती FPGAs जैसे Xilinx 3000 श्रृंखला और ट्रिप्टिच द्वारा निर्मित अन्य थे। ये उपकरण सरल थे, और वे कैसे काम करते थे इसका एक अच्छा विचार प्राप्त करने के लिए, केन शिरिफ का ब्लॉग देखें। Xilinx XC2064 का आंतरिक भाग इस प्रकार दिखता है:

यह जटिल दिखता है, लेकिन यह वास्तव में असाधारण रूप से सरल है। सभी LUTs, या तर्क तत्व, तारों से एक दूसरे से जुड़े हुए हैं। जहां तार पार होते हैं, वहां फ़्यूज़ होते हैं। फ़्यूज़ जलाएं और आपने तारों को एक साथ जोड़ दिया है। यह है एक सरल ग्राफ़ और चिप के अंदर वास्तविक पथों की सभी जटिलताएँ दूर हो जाती हैं। सर्किट बोर्ड के लिए, मेरे पास यह सुविधा नहीं है। मुझे यह पता लगाना है कि पीसीबी की ऊपरी परत पर पैड से सिग्नल कैसे प्राप्त करें और ग्रिड में वियास के साथ ‘ड्रिल डाउन’ कैसे करें। मुझे ग्राफ़ के दोनों किनारों और ग्राफ़ के नोड्स को ध्यान में रखने के लिए किसी तरीके के साथ आने की ज़रूरत है, कुछ ऐसा जो पाथफाइंडर एल्गोरिदम के साथ अपठित क्षेत्र है।

इसका पहला चरण पैड एस्केप प्लानर है जो सभी पैड के एस्केप रूटिंग की पूर्व-गणना करता है। क्योंकि संपूर्ण मैनहट्टन रूटिंग इंजन एक बैकप्लेन के लिए डिज़ाइन किया गया है, हम कुछ धारणाएँ बना सकते हैं: सभी घटक एसएमडी होने जा रहे हैं, क्योंकि टीएचटी भाग एक रूटिंग जाली की दक्षता को खत्म कर देंगे। घटकों को एक ग्रिड पर व्यवस्थित किया जा रहा है, और अच्छी बात यह है कि मैं कुछ ‘रैंडमाइजेशन’ चाहूंगा जहां यह ग्रिड में विअस पंचिंग डालता है। भागने की योजना इस प्रकार दिखती है:

कैसे पाथफ़ाइंडर ने मुझे लगभग मार ही डाला, और कैसे मैंने पाथफ़ाइंडर को ख़राब नहीं होने दिया

ऑर्थोरूट को विकसित करते समय मुझे हर कल्पनीय बग मिला। एक के लिए, प्रत्येक पुनरावृत्ति में जालों की भीड़ बढ़ती जाएगी। राउटर पुनरावृत्ति 1 में भीड़ के साथ 9,495 किनारों के साथ ठीक से शुरू होगा। फिर पुनरावृत्ति 2: 18,636 किनारों के साथ। पुनरावृत्ति 3: 36,998 किनारे। अति प्रयोग था बढ़ रहा है अभिसरण के बजाय प्रति पुनरावृत्ति 3× द्वारा। कुछ बुनियादी तौर पर टूट गया था. अपराधी? इतिहास की लागतें थीं खस्ताहाल जमा करने के बजाय. एल्गोरिदम को यह याद रखने की आवश्यकता है कि पिछले पुनरावृत्तियों में कौन से किनारे समस्याग्रस्त थे, लेकिन मेरे कार्यान्वयन में समस्या थी history_decay=0.995इसलिए यह प्रत्येक पुनरावृत्ति में 0.5% समस्या को भूल रहा था। पुनरावृत्ति 10 तक, यह सब कुछ भूल चुका था। कोई स्मृति नहीं = कोई सीख नहीं = विस्फोट।

इतिहास तय होने के बाद, मैंने एक और परीक्षण चलाया। मुझे मिल गया कंपन. एल्गोरिथ्म 12 पुनरावृत्तियों (9,495 → 5,527, 42% सुधार!) के लिए बेहतर होगा, फिर 11,817 तक बढ़ जाएगा, फिर 7,252 तक गिर जाएगा, फिर 14,000 तक बढ़ जाएगा। पैटर्न हमेशा के लिए दोहराया गया. समस्या “अनुकूली हॉटसेट साइज़िंग” थी – जब प्रगति धीमी हो जाती थी, तो एल्गोरिदम 150 से 225 तक पुन: रूट किए जा रहे नेट के सेट को बड़ा कर देता था, जिससे बड़े पैमाने पर व्यवधान उत्पन्न होता था। 100 नेट पर हॉटसेट को ठीक करने से दोलन समाप्त हो गया।

निश्चित हॉटसेट के साथ भी, लेट-स्टेज दोलन पुनरावृत्ति 15 के बाद वापस आ गया। क्यों? वर्तमान लागत कारक तेजी से बढ़ता है: pres_fac = 1.15^iteration. पुनरावृत्ति 19 तक, वर्तमान लागत पुनरावृत्ति 1 की तुलना में 12.4× अधिक मजबूत थी, जो इतिहास को पूरी तरह से प्रभावित करती है (जो रैखिक रूप से बढ़ती है)। समाधान: टोपी pres_fac_max=8.0 पूरे अभिसरण के दौरान इतिहास को प्रतिस्पर्धी बनाए रखना।

पाथफाइंडर को FPGAs के लिए डिज़ाइन किया गया है, और प्रत्येक Xilinx XC3000 चिप अन्य XC3000 चिप के समान है। पुराने Xilinx चिप के लिए मापदंडों को कॉन्फ़िगर करने का मतलब है कि हर रूटिंग समस्या होगी शायद उस विशेष चिप पर जुटें। पीसीबी अलग हैं; हर एक पीसीबी हर दूसरे पीसीबी से अलग है। इतिहास, दबाव और क्षय मापदंडों का कोई एक सेट नहीं है जो हर एक पीसीबी पर काम करेगा।

मुझे तुरंत इन मापदंडों का पता लगाना था। तो मैंने वही किया. अभी मैं मैनहट्टन राउटर के लिए बोर्ड-अनुकूली पैरामीटर का उपयोग कर रहा हूं। पाथफाइंडर एल्गोरिदम शुरू करने से पहले यह KiCad में सिग्नल परतों की संख्या, कितने नेट रूट किए जाएंगे, और नेट का सेट कितना सघन है, के लिए बोर्ड का विश्लेषण करता है। यह अटपटा है, लेकिन यह काम करता है।

जहां पाथफाइंडर को एफपीजीए के प्रत्येक परिवार के लिए एक बार ट्यून किया गया था, मैं इसे सर्किट बोर्ड के पूरे वर्ग के लिए ऑटो-ट्यून कर रहा हूं। एक विशाल बैकप्लेन को सावधानीपूर्वक रूटिंग मिलती है और एक Arduino क्लोन को तेज़, आक्रामक रूटिंग मिलती है। उम्मीद यह है कि दोनों एकजुट होंगे – एक वैध रूटिंग समाधान तैयार करेंगे – और शायद यह काम करेगा। शायद ऐसा नहीं है. अभी और भी काम करना बाकी है.

द मॉन्स्टर बोर्ड को रूट करना

“छोटे” बोर्डों (वास्तव में मेरे बड़े बैकप्लेन के 500+ नेट सबसेट, 18 परतों के साथ) के साथ महत्वपूर्ण परीक्षण के बाद, मैंने इस परियोजना के पूरे उद्देश्य, 8000+ नेट, 17000 पैड मॉन्स्टर बोर्ड पर काम शुरू किया। एक महत्वपूर्ण समस्या थी: यह मेरे GPU पर फ़िट नहीं होगा। माना कि मेरे पास केवल 16 जीबी एनवीडिया 5080 है, लेकिन यह भी बड़े बैकप्लेन के लिए बहुत छोटा था।

इसने मुझे ‘क्लाउड रूटिंग समाधान’ विकसित करने के लिए प्रेरित किया। यह OrthoRoute प्लगइन से “OrthoRoute PCB फ़ाइल” निकालने तक सीमित है। वहां से, मैं एक जीपीयू के साथ एक लिनक्स बॉक्स किराए पर लेता हूं और हेडलेस मोड के साथ ऑटोरूटिंग एल्गोरिदम चलाता हूं। यह एक “ऑर्थोरूट सॉल्यूशन फ़ाइल” तैयार करता है। मैं इसे अपनी स्थानीय मशीन पर ऑर्थोरूट प्लगइन चलाकर और समाधान फ़ाइल आयात करके, फिर पुश करके KiCad में वापस आयात करता हूं वह KiCad को.

यहाँ परिणाम है:

बस, यही तैयार बोर्ड है। कुछ विशिष्टताएँ:

• 44,233 अंधे और दबे हुए मार्ग। 68,975 ट्रैक खंड।
• 80जीबी ए100 जीपीयू पर रूट किया गया, विशाल.आईओ पर किराए पर लिया गया। इस बोर्ड को रूट करने के लिए आवश्यक कुल वीआरएएम 33.5 जीबी थी, जो 32 जीबी से कम होने के करीब थी और मुझे एक सस्ता जीपीयू किराए पर लेने की इजाजत थी।
• इस बोर्ड को पूरा करने में कुल 41 घंटे का समय लगा। यह इस बोर्ड को रूट करने में फ्रीरूटिंग में लगने वाले महीनों की तुलना में कहीं बेहतर है, लेकिन यह अभी भी तेज़ नहीं है।
• रूटिंग परिणाम है अच्छा लेकिन नहीं महान. एक बड़ी समस्या एस्केप पैड योजना के बारे में डीआरसी-जागरूकता है। ऐसे निशान हैं जो बिल्कुल ओवरलैप नहीं होते हैं, लेकिन एस्केप रूट प्लानर द्वारा उत्पन्न ज्यामिति के कारण वे सख्त डीआरसी पास नहीं करते हैं। इसे भविष्य के संस्करणों में ठीक किया जा सकता है. पाथफाइंडर ने जो उत्पन्न किया उसमें कुछ ओवरलैपिंग निशान भी हैं। बहुत नहीं, लेकिन कुछ।

हालाँकि मेरे ऑटोराउटर से आउटपुट सही नहीं है, कोई भी ऑटोराउटर से आउटपुट की उम्मीद नहीं करेगा उत्तम परिणाम, उत्पादन के लिए तैयार। यह एक ऑटोराउटर है, जिस पर आपको भरोसा नहीं करना चाहिए। ऑर्थोरूट के परिणाम को डीआरसी-अनुपालक बोर्ड में बदलने में कुछ दिन लग गए, लेकिन यह शुरुआत में मेरे सामने आई आठ हजार एयरवायरों की कठिन समस्या से कहीं अधिक आसान था।

ऑर्थोरूट का भविष्य

मैंने इसे एक कारण से बनाया: अपने पैथोलॉजिकल रूप से बड़े बैकप्लेन को रूट करने के लिए। मिशन पूरा हुआ। और रास्ते में, मैंने गलती से अपनी अपेक्षा से अधिक उपयोगी कुछ बना लिया।

ऑर्थोरूट साबित करता है कि जीपीयू-त्वरित रूटिंग केवल सैद्धांतिक नहीं है, और एफपीजीए को रूट करने के लिए डिज़ाइन किए गए एल्गोरिदम को सर्किट बोर्डों के अधिक सामान्य वर्ग के लिए अनुकूलित किया जा सकता है। यह तेज़ भी है. मैनहट्टन जाली दृष्टिकोण उच्च-घनत्व वाले डिज़ाइनों को संभालता है जो पारंपरिक ऑटोराउटर्स को अवरुद्ध कर देते हैं। और पाथफाइंडर कार्यान्वयन बोर्डों पर मिनटों में परिवर्तित हो जाता है जिसमें सीपीयू-आधारित दृष्टिकोण के साथ घंटों या दिन लगेंगे।

इससे भी महत्वपूर्ण बात यह है कि आर्किटेक्चर मॉड्यूलर है। कठिन भाग-कीकैड आईपीसी एकीकरण, जीपीयू त्वरण ढांचा, डीआरसी-जागरूक रूटिंग स्पेस जेनरेशन पूरा हो गया है। इस फाउंडेशन के शीर्ष पर नई रूटिंग रणनीतियाँ जोड़ना सीधा है। कोई व्यक्ति अलग-अलग एल्गोरिदम लागू कर सकता है, विशिष्ट बोर्ड प्रकारों के लिए अनुकूलन कर सकता है, या फ्लेक्स पीसीबी को संभालने के लिए इसका विस्तार कर सकता है।

कोड GitHub पर उपलब्ध है। मैं वास्तव में उत्सुक हूं कि अन्य लोग इसके साथ क्या करेंगे। क्या आप विभिन्न रूटिंग रणनीतियाँ जोड़ना चाहते हैं? आरएफ बोर्डों के लिए अनुकूलन? इसे फ्लेक्स पीसीबी तक विस्तारित करें? पीआर का स्वागत है, योगदानकर्ताओं का स्वागत है।

और हाँ, आपको अभी भी महत्वपूर्ण संकेतों को मैन्युअल रूप से रूट करना चाहिए। लेकिन सैकड़ों सांसारिक बिजली और डेटा नेट वाले घने डिजिटल बोर्ड के लिए? जब आप कॉफ़ी लें तो GPU को इसे संभालने दें। ऑटोरूटर्स इसी लिए हैं।

ऑटोराउटर पर कभी भरोसा न करें. लेकिन कम से कम यह तेज़ है।

पीछे