ईडीए में अमेरिका के एकाधिकार को नष्ट करें। इन्नोपोलिस पहला कदम उठाता है

1990 के दशक के बाद से, इसने मुझे चकित कर दिया है कि पूरे वैश्विक डिजिटल माइक्रोइलेक्ट्रॉनिक का डिज़ाइन कैलिफोर्निया में दो कार्यालयों द्वारा नियंत्रित किया जाता है, जो एक दूसरे से 10 मिनट - सिनोप्सिस और ताल हैं। उस समय, दुनिया का एक चौथाई डिजाइन जापान में किया गया था (मुख्य भूमि चीन तब आदिम अवस्था में थी), और इन सभी सोनी, हिताची, फुजित्सु और अन्य दिग्गजों ने अमेरिका को झुकाया और उन कार्यक्रमों के लिए लाखों डॉलर का भुगतान किया जब जापानी डिजाइनरों ने तब उपयोग किया था। अब यह सैमसंग, हुआवेई और यहां तक ​​कि रूसी कार्यालयों के साथ जारी है जो अंतरिक्ष के लिए माइक्रोचिप्स डिजाइन करते हैं।

रूसी भूमि यैंडेक्स बनाम Google को विकसित करने में कामयाब रही, इसलिए माइक्रोचिप्स डिजाइन करने के लिए कुछ कार्यक्रम बनाने की कोशिश क्यों नहीं की गई? आप छोटे शुरू कर सकते हैं: डिजाइन ऑटोमेशन एल्गोरिदम (इलेक्ट्रॉनिक डिजाइन ऑटोमेशन - ईडीए) के विकास के लिए प्रतियोगिताओं और हैकथॉन को लोकप्रिय बनाने के लिए। ये एल्गोरिदम इस बात में सुविधाजनक हैं कि उनके पास कई कठिनाई स्तर हैं: एक छात्र सप्ताहांत में सबसे सरल स्थान और मार्ग कार्यक्रम लिख सकता है, लेकिन एक उन्नत कार्यक्रम के लिए सैकड़ों लोगों और अरबों डॉलर के अनुसंधान और विकास में दशकों के काम की आवश्यकता होगी।

अब कज़ान के पास इन्नोपोलिस में वे "दो सप्ताह के प्रशिक्षण + हैकाथॉन" के प्रारूप में छात्रों के लिए एक कार्यक्रम कर रहे हैं। विषयों में से एक पारंपरिक ईडीए कार्य था - एक इलेक्ट्रॉनिक सर्किट के ग्राफ को मानक कोशिकाओं की पंक्तियों में रखना और अनुरेखण करना। यह देखना दिलचस्प होगा कि सी ++ / जावा / पायथन की बुनियादी समझ के साथ प्रोग्रामर की एक छोटी टीम, जीयूआई का उपयोग करके डेटा संरचनाओं की कल्पना करने के लिए पाठ, ग्राफ एल्गोरिदम और कौशल को पार्स करने के तरीके थोड़े समय में लागू कर सकते हैं।

तो - समस्या का बयान:



इस कार्य में तीन उपकेंद्र होते हैं जिनसे विभिन्न छात्र निपट सकते हैं:

1. एक डिजिटल सर्किट ग्राफ के पाठ प्रतिनिधित्व को पार्स करना।
2. Microcircuit के मानक कोशिकाओं की पंक्तियों पर एक ग्राफ रखकर और इन कोशिकाओं को पटरियों (अनुरेखण) से जोड़ना।
3. परिणामों का विज़ुअलाइज़ेशन - सर्किट ट्रैक और कनेक्शन की स्क्रीन पर प्रदर्शन।

कार्यक्रम का इनपुट वेरिलॉग हार्डवेयर विवरण भाषा के एक बहुत ही सीमित सबसेट में एक टेक्स्ट फ़ाइल है। यह फ़ाइल सर्किट (इनपुट, आउटपुट), आंतरिक कनेक्शन (तार) के लिए इनपुट और आउटपुट का वर्णन करती है और "टाइप उदाहरण-नाम (कनेक्शन की सूची)" प्रारूप में तार्किक तत्वों की एक सूची प्रदान करती है। फ़ाइल को C + C ++ में Lex + Yacc या इसी तरह के प्रोग्राम का उपयोग करके पार्स किया जा सकता है।



पाठ को पार्स करने का परिणाम स्मृति में तत्वों का एक ग्राफ प्रतिनिधित्व होना चाहिए। इस दृश्य का उपयोग प्लेसमेंट और ट्रेसिंग एल्गोरिदम द्वारा किया जाएगा, जो तब एक अन्य संरचना द्वारा बनाया जाएगा। यदि हैकाथॉन टीम में पर्याप्त प्रतिभागी हैं, तो हैकिंग के दौरान प्रारंभिक पार्सिंग के परिणाम को अतिरिक्त कार्य के रूप में देखा जा सकता है। लगभग इस भावना में, भले ही कितना सुंदर न हो:



यदि हैकाथॉन के दौरान पर्याप्त प्रतिभागी नहीं हैं, तो इंटरमीडिएट के दृश्य, अनियोजित ग्राफ़ को बाद के लिए छोड़ दिया जाना चाहिए, और हैकाथॉन के दौरान, केवल अंतिम प्लेसमेंट को स्क्रीन पर प्रदर्शित किया जाना चाहिए।

सामान्य तौर पर, पार्सिंग के कार्य को जटिलता के कई स्तरों के साथ पेश किया जा सकता है:

1. सरलतम मामलों में, ग्राफ़ के सभी नोड्स दो-इनपुट तार्किक तत्व और OR हैं, साथ ही एकल-इनपुट तत्व नहीं हैं। अंतिम प्लेसमेंट पर, उन्हें समान चौड़ाई के मानक कोशिकाओं द्वारा महसूस किया जाता है।
2. अगर हैकाथॉन के लिए पर्याप्त समय है, तो कार्य जटिल हो सकता है:
   
   • तीन और चार इनपुट कोशिकाओं AND3, OR4, आदि का परिचय दें ।;
   • NAND, XOR, D- फ्लिप-फ्लॉप (D-Flip-Flop) को विभिन्न विकल्पों (रीसेट, सक्षम), आदि के साथ जोड़कर नोड प्रकारों के सेट का विस्तार करें;
   • कोशिकाओं की चौड़ाई और अन्य मापदंडों को निर्धारित करने के लिए एक अतिरिक्त पाठ फ़ाइल बनाएं।
   
   
3. हैकाथॉन के बाद, कार्य को वास्तविक दुनिया से जोड़ा जा सकता है, और यह सार नहीं किया जाता है और ओआरएस या पार्स किए जाते हैं, लेकिन एक ही प्रारूप में फ़ाइल, लेकिन 28, 14 या 7 नैनोमीटर के मानक एएसआईसी कोशिकाओं के वास्तविक पुस्तकालयों से कोशिकाओं के साथ, जो ईडीए डेवलपर्स और कारखाने के डिजाइनरों को आपूर्ति की जाती हैं प्रकार TSMC (ताइवान सेमीकंडक्टर विनिर्माण कंपनी)।

एक मानक कोशिका क्या है? यह किसी दिए गए ASIC पुस्तकालय के लिए एक मानक ऊंचाई सेल है, अर्थात्, एक प्रौद्योगिकी का उपयोग करके कारखाने में एक माइक्रोकिरुच निर्माण के लिए एक आदिम पुस्तकालय है। ASIC - एप्लीकेशन स्पेसिफिक इंटीग्रेटेड सर्किट। अब ज्यादातर चिप्स, उदाहरण के लिए, स्मार्टफ़ोन ASIC हैं। एएसआईसी लाइब्रेरी में कोशिकाओं की एक मानक ऊंचाई होती है ताकि उन्हें पंक्तियों में आसानी से बिजली की आपूर्ति की जा सके और ट्रेस एल्गोरिदम की सुविधा प्रदान की जा सके। लाइब्रेरी में विभिन्न कोशिकाएं न केवल आदिम जैसे कि AND और OR को लागू कर सकती हैं, बल्कि अधिक जटिल निर्माण भी कर सकती हैं - मल्टीप्लेक्सर्स, लैचेज, दो या तीन लॉजिक एलिमेंट्स (AND-OR), आदि का संयोजन।



पंक्तियों में माइक्रोकिरिच लाइन पर सेल ( चार्ल्स दंचेक के व्याख्यान से स्लाइड)



पंक्तियों के बीच चैनल (रूटिंग चैनल) हैं जिसमें कनेक्शन पास होते हैं। कनेक्शनों में भीड़ बनने पर चैनलों की चौड़ाई को बदला जा सकता है। पंक्तियों में, आप कोशिकाओं के बीच अंतराल बना सकते हैं:



हैकथॉन के लिए, कार्य को एक वैक्यूम में एक गोलाकार घोड़े के स्तर तक सरल किया जा सकता है:

• सेल प्रकारों को सीमित करें। शुरुआत के लिए, आप आम तौर पर दो-इनपुट नंद का सिर्फ एक ग्राफ रख सकते हैं।
• सभी कोशिकाओं पर समान चौड़ाई का विचार करें।
• कोशिकाओं की भौतिक प्रकृति के सभी पहलुओं को अनदेखा करें, जिसमें सिग्नल में देरी और बिजली की खपत शामिल है।

यहां, "उपेक्षा" का अर्थ है कि प्रशिक्षण अभ्यास में आप प्लेसमेंट और ट्रेसिंग की गुणवत्ता का आकलन करते समय सेल भौतिकी को ध्यान में नहीं रख सकते हैं। इसके साथ शुरू करने के लिए, यह केवल ज्यामिति पर विचार करने के लिए पर्याप्त है, उदाहरण के लिए, जोड़ों की कुल लंबाई और उन परतों की संख्या को कम करने के लिए जिन पर जोड़ों को बनाया जाता है। एक नई परत की आवश्यकता तब उत्पन्न होती है जब दो कंडक्टरों को पार किए बिना उन्हें रखना असंभव है।

हैकाथॉन में, मानक कोशिकाओं को "ब्लैक बॉक्स" के रूप में माना जाता है और स्क्रीन पर उन्हें ऊपर के आंकड़ों के रूप में प्रदर्शित किया जाता है। या तार्किक तत्वों की छवियों के साथ, इगोर मार्कोव के व्याख्यान से एक स्लाइड पर:



यद्यपि यदि आप कोशिकाओं के अंदरूनी हिस्सों के साथ प्रदर्शित करते हैं, तो चित्र अधिक सजावटी हैं। चार्ल्स दंचेक के व्याख्यान से एक स्लाइड:



इनसाइड और कोशिकाओं के अनुरेखण + अनुरेखण के साथ इंटरनेट से एक और तस्वीर:



लेकिन पंक्तियों में कोशिकाओं को कैसे जगह दें, पंक्तियों के बीच चैनलों का विस्तार और संकीर्ण करें, कनेक्शन बनाएं, नई परतों को पेश करें, परिणामों की अनुकूलता का मूल्यांकन करें और विकल्पों के माध्यम से सॉर्ट करें? खैर, ये विशुद्ध रूप से एल्गोरिथम और प्रोग्रामिंग कार्य हैं, इनोपॉलिस में वे शायद यही सिखाते हैं, इसलिए मैं अपने विचारों या विचारों को पेड़ पर नहीं फैलाऊंगा। ट्रेसिंग के लिए प्रारंभिक प्रेरणा के रूप में, आप वेव ट्रेसिंग की प्राचीन पद्धति का उपयोग कर सकते हैं, जो कि RUSNANO के स्कूली बच्चों के लिए पाठ्यक्रम के तीसरे भाग में वर्णित है । यद्यपि यह विधि पंक्तियों में व्यवस्थित मानक कोशिकाओं के लिए नहीं है, लेकिन कम संख्या में घटकों के साथ आदेश के मामले में:

2.10। यह कैसे करें: तरंग अनुरेखण एल्गोरिथ्म।

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

ली एल्गोरिथ्म उन ब्लॉकों का प्रतिनिधित्व करता है जिन्हें कनेक्ट होने की जरूरत है, एक सीमित विमान पर आंकड़े के रूप में, "बॉक्स में" चिह्नित। एक ब्लॉक के आउटपुट से दूसरे ब्लॉक के आउटपुट तक का सबसे छोटा रास्ता खोजने के लिए, ली एल्गोरिथ्म दो पास का उपयोग करता है:

• पहले पास को तरंग प्रसार कहा जाता है। हम एक इकाई के साथ पहले आउटपुट पर सभी "सेल" या एक सेल को चिह्नित करते हैं। उसके बाद, नंबर N के साथ लेबल किए गए प्रत्येक सेल के लिए, हम सभी पड़ोसी मुक्त गैर-लेबल वाली कोशिकाओं को N + 1 के साथ चिह्नित करते हैं। मार्कअप को तब तक दोहराएं जब तक कि हम या तो दूसरे ब्लॉक के निष्कर्ष पर नहीं पहुंच जाते हैं या "लहर" फैलाने का अधिक अवसर नहीं है।
• दूसरे पास को "पथ की बहाली" कहा जाता है। यदि दूसरे ब्लॉक में सेल को चिह्नित किया जाता है, तो हम अपने पड़ोसियों के बीच एक सेल को चुनेंगे जो वर्तमान सेल में संख्या से 1 कम चिह्नित है। पथ में एक पड़ोसी सेल जोड़ें, इसमें जाएं और अपने पड़ोसियों को देखना शुरू करें, जो 1 और कम चिह्नित हैं। हम इसे तब तक दोहराते हैं जब तक कि हम पहले ब्लॉक के निष्कर्ष पर नहीं आते हैं।

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

अधिक गंभीर एल्गोरिदम के लिए, आप इगोर मार्कोव की सामग्री में विचारों की खोज कर सकते हैं। लेकिन सबसे अच्छी बात रचनात्मक होगी - क्या होगा अगर आप कुछ ऐसी चीज़ों के साथ आते हैं जो हजारों गणितीय-समझदार एल्गोरिथम प्रोग्रामर नहीं हैं, जो हर सुबह Synopsys और ताल कार्यालयों में 101 वें, 880 वें और 237 वें फ्रीवे पर ट्रैफिक जाम के साथ आते हैं। सैन जोस, सनीवेल और माउंटेन व्यू, कैलिफोर्निया के शहरों में।

संदर्भ (सरल से जटिल तक):

1. इन्नोपोलिस में डिजिटल डिजाइन की मूल बातें पर परिचयात्मक व्याख्यान: 1 , 2 ।
2. ओलंपियाड प्रकार के उन्नत स्कूली बच्चों के लिए डिजिटल इलेक्ट्रॉनिक्स और ईडीए में परिचयात्मक पाठ्यक्रम। RUSNANO से: 1 , 2 , 3 ।
3. पाठ्यपुस्तक हैरिस और हैरिस ।
4. चार्ल्स दंचेक द्वारा व्याख्यान के स्लाइड ।
5. मिशिगन विश्वविद्यालय से इगोर मार्कोव द्वारा पाठ्यक्रम । उन्होंने मास्को स्टेट यूनिवर्सिटी में इस कोर्स को पढ़ा।

मैं आशा व्यक्त करता हूं कि एल्गोरिथम प्रतियोगिताओं में इन्नोपोलिस की पहल का विस्तार होगा। EDA क्षेत्र गणितीय रूप से दिलचस्प और अच्छी तरह से भुगतान किया गया है। Synopsys ने आर्मेनिया में एक शाखा खोली और वहां के प्रमुख नियोक्ताओं में से एक बन गया: "आज, Synopsys 650 से अधिक कर्मचारियों (600 से अधिक इंजीनियरों सहित) के साथ आर्मेनिया में सबसे बड़े आईटी नियोक्ताओं में से एक है।" मैं ध्यान देता हूं कि रूस आर्मेनिया से बड़ा है और शायद वह अपना खुद का Synopsys बना सकता है। अंत में, रूस में कई प्रोग्रामर हैं, गणितज्ञ भी हैं, और सिनोप्स + कैडेंस का वर्तमान बाजार पूंजीकरण लगभग सोची ओलंपिक की लागत के बराबर है।