👦 🍷 🧀 मानक कोशिकाओं (एक बाहरी व्यक्ति के नोट्स) की व्यवस्था करना 💼 🤞🏿 😡

लेख " एकाधिकार को नष्ट करना ... " के बाद, लेखक, एक व्यक्ति के रूप में, EDA से बहुत दूर है, लेकिन स्वाभाविक रूप से जिज्ञासु, लिंक का पालन करने के लिए बहुत आलसी नहीं था और खुद को यह सोचकर पकड़ा कि मुख्य तकनीकी समाधान में से एक मानक कोशिकाओं ( मानक सेल) की पंक्तियों का उपयोग है लेआउट) - बहुत विवादास्पद लग रहा है।

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

और निश्चित रूप से, यह भी सवाल उठता है कि क्या वैकल्पिक समाधान हैं ... यदि ऐसा है तो ...

चित्रा 1 मानक कोशिकाओं की विशिष्ट पंक्तियाँ ( यहाँ से )

क्या हुआ अगर

कुल बॉन्ड लंबाई को कम करने के दृष्टिकोण से, कुछ व्यापक पूर्व घटता के साथ मानक कोशिकाओं की व्यवस्था करना उपयोगी होगा: पीनो या हिल्बर्ट।

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

चित्र 2 हिल्बर्ट वक्र, फ़ील्ड 8X8 और 64X64

स्वीपिंग कर्व्स स्व-समान होते हैं, जो समग्र अवधारणा में अच्छी तरह से फिट होते हैं।
उनका एक उच्च इलाका है यानी वक्र पर आस-पास स्थित बिंदुओं को पास और अंतरिक्ष में सबसे अधिक संभावना है।
चैनलों के एक पदानुक्रमित संगठित नेटवर्क को शामिल करें।
लॉजिकल सर्किट के लिए, आप एक उपयुक्त वर्ग या आयत 1x2,2x1 चुन सकते हैं, जिसमें इसे अधिक मात्रा में रखा गया है और इसे इष्टतम ज्यामिति का चयन करने के लिए स्वीपिंग वक्र (चित्र 3 देखें) के साथ "ले जाएँ", क्योंकि यह एक सस्ते सस्ते फ़ंक्शन के साथ स्वतंत्रता का केवल एक डिग्री है। ।
टायरों के कनेक्शन की सुविधा (VDD / GND) रहेगी।
...

चित्र 3 अलग-अलग पारियों के साथ एक हिल्बर्ट वक्र के तीन टुकड़े।

तो:

हम हिल्बर्ट वक्र के साथ प्रयोग करेंगे
हम एक वर्ग 64X64 में प्रयोग करेंगे (चित्र 3)
वक्र के प्रारंभिक चरण में कई मानक कोशिकाएं और स्थान हो सकते हैं - प्रयोग के पैरामीटर कितने और किस क्रम में हैं
सभी प्राथमिक कदमों की पहचान व्यवस्थित रूप से की जाती है
प्रारंभिक चरण एक ओवरलैप के साथ जाते हैं यानी यदि चरण एक मानक सेल से शुरू होता है, तो इसके अंत में एक स्थान होना चाहिए, और इसके विपरीत
सभी रिक्त स्थान और मानक कोशिकाएं समान आकार की हैं - 1X1
सभी कोशिकाओं को किसी क्रम में क्रमबद्ध किया जाता है, यह आदेश भी एक पैरामीटर है
एक और पैरामीटर वक्र (अंक (0,0)) की शुरुआत से पारी है, जिससे हम एक निश्चित क्रम में मानक कोशिकाओं की व्यवस्था करेंगे
मानक कोशिकाओं के बीच बंधन लंबाई की गणना L1 (मैनहट्टन दूरी) के अनुसार की जाती है
सभी बॉन्ड की लंबाई का योग वांछित मान है, न्यूनतम राशि निर्धारित करने पर, हम इष्टतम स्थान प्राप्त करेंगे

और एक प्रयोगात्मक खरगोश के रूप में, आइए एक 8-बिट योजक लें। यह काफी सरल है, लेकिन तुच्छ नहीं। संभावित पेशेवरों और विपक्षों को महसूस करने के लिए इसमें बहुत सारे तत्व और कनेक्शन हैं। इसी समय, उनमें से "घुटने पर" प्रयोग करने में सक्षम होने के लिए पर्याप्त नहीं हैं।

योजक

4 पूर्ण एकल-बिट योजक का एक योजनाबद्ध आरेख है

चित्रा 5 तो इस ग्राफ उपयोगिता Neato graphwiz से देखता है

6 8-बिट हस्ताक्षरित योजक, यहां लिया गया

लेकिन हम केवल पूर्णांक के साथ काम करेंगे, बिना त्रुटि ध्वज W के।

अंजीर। 7 तो 8-बिट योजक ग्राफविज़ की डॉट उपयोगिता देखता है।

यह थोड़ा हंसों के नृत्य की तरह दिखता है।

फिगर 8 का उपयोग एक ही ग्राफ है जो कि अनुकूलन के बाद नीट का उपयोग करता है।

डॉट काउंट

सुगम योग 8
a_0;
a_1;
a_2;
a_3;
a_4;
a_5;
a_6;
a_7;

b_0;
b_1;
b_2;
b_3;
b_4;
b_5;
b_6;
b_7;

s_0;
s_1;
s_2;
s_3;
s_4;
s_5;
s_6;
s_7;

p0;
p1;

and1_0;
and1_1;
and1_2;
and1_3;
and1_4;
and1_5;
and1_6;
and1_7;

and2_0;
and2_1;
and2_2;
and2_3;
and2_4;
and2_5;
and2_6;
and2_7;

and3_0;
and3_1;
and3_2;
and3_3;
and3_4;
and3_5;
and3_6;
and3_7;

and4_0;
and4_1;
and4_2;
and4_3;
and4_4;
and4_5;
and4_6;
and4_7;

or1_0;
or1_1;
or1_2;
or1_3;
or1_4;
or1_5;
or1_6;
or1_7;

or2_0;
or2_1;
or2_2;
or2_3;
or2_4;
or2_5;
or2_6;
or2_7;

or3_0;
or3_1;
or3_2;
or3_3;
or3_4;
or3_5;
or3_6;
or3_7;

or4_0;
or4_1;
or4_2;
or4_3;
or4_4;
or4_5;
or4_6;
or4_7;

not1_0;
not1_1;
not1_2;
not1_3;
not1_4;
not1_5;
not1_6;
not1_7;

a_0 -> और1_0;
a_1 -> और1_1;
a_2 -> और1_2;
a_3 -> और1_3;
a_4 -> और1_4;
a_5 -> और1_5;
a_6 -> और1_6;
a_7 -> और1_7;

b_0 -> और1_0;
b_1 -> और1_1;
b_2 -> और1_2;
b_3 -> और1_3;
b_4 -> और1_4;
b_5 -> और1_5;
b_6 -> और1_6;
b_7 -> और1_7;

a_0 -> or1_0;
a_1 -> or1_1;
a_2 -> or1_2;
a_3 -> or1_3;
a_4 -> or1_4;
a_5 -> or1_5;
a_6 -> or1_6;
a_7 -> or1_7;

b_0 -> or1_0;
b_1 -> या1_1;
b_2 -> or1_2;
b_3 -> or1_3;
b_4 -> or1_4;
b_5 -> or1_5;
b_6 -> or1_6;
b_7 -> or1_7;

और 1_0 -> या 3_0;
और 1_1 -> या 3_1;
और1_2 -> या3_2;
और 1_3 -> या 3_3;
और 1_4 -> या 3_4;
और 1_5 -> या 3_5;
और 1_6 -> या 3_6;
और 1_7 -> या 3_7;

और 1_0 -> और -3_0;
और 1_1 -> और 3_1;
और १-२ -> और ३-२;
और1_3 -> और -3_3;
और 1_4 -> और -3_4;
और 1_5 -> और -3_5;
और 1_6 -> और -3_6;
और 1_7 -> और -3_7;

or1_0 -> और -2_0;
or1_1 -> और2_1;
or1_2 -> और 2_2;
or1_3 -> और -2_3;
or1_4 -> और -2_4;
or1_5 -> और -2_5;
or1_6 -> और -2_6;
or1_7 -> और -2_7;

or1_0 -> or2_0;
or1_1 -> or2_1;
or1_2 -> or2_2;
or1_3 -> or2_3;
or1_4 -> or2_4;
or1_5 -> or2_5;
or1_6 -> or2_6;
or1_7 -> or2_7;

और 2_0 -> या 3_0;
और 2_1 -> या 3_1;
and2_2 -> or3_2;
और 2_3 -> या 3_3;
और 2_4 -> या 3_4;
और 2_5 -> या 3_5;
और 2_6 -> या 3_6;
और 2_7 -> या 3_7;

or2_0 -> और4_0;
or2_1 -> और4_1;
or2_2 -> और4_2;
or2_3 -> और4_3;
or2_4 -> और4_4;
or2_5 -> और4_5;
or2_6 -> और4_6;
or2_7 -> और4_7;

और 3_0 -> या 4_0;
और 3_1 -> या 4_1;
and3_2 -> or4_2;
और 3_3 -> या 4_3;
और 3_4 -> या 4_4;
और 3_5 -> या 4_5;
और 3_6 -> या 4_6;
और 3_7 -> या 4_7;

or3_0 -> not1_0;
or3_1 -> not1_1;
or3_2 -> not1_2;
or3_3 -> not1_3;
or3_4 -> not1_4;
or3_5 -> not1_5;
or3_6 -> not1_6;
or3_7 -> not1_7;

not1_0 -> और4_0;
not1_1 -> और4_1;
not1_2 -> और4_2;
not1_3 -> और4_3;
not1_4 -> और4_4;
not1_5 -> और4_5;
not1_6 -> और4_6;
not1_7 -> और4_7;

और 4_0 -> या 4_0;
और 4_1 -> या 4_1;
और 4_2 -> या4_2;
और 4_3 -> या 4_3;
और 4_4 -> या 4_4;
और 4_5 -> या 4_5;
और 4_6 -> या 4_6;
और 4_7 -> या 4_7;

or4_0 -> s_0;
or4_1 -> s_1;
or4_2 -> s_2;
or4_3 -> s_3;
or4_4 -> s_4;
or4_5 -> s_5;
or4_6 -> s_6;
or4_7 -> s_7;

p0 -> और 2_0;
p0 -> or2_0;
p0 -> और3_0;

or3_0 -> और -2_1;
or3_0 -> or2_1;
or3_0 -> और3_1;

or3_1 -> और 2_2;
or3_1 -> or2_2;
or3_1 -> और3_2;

or3_2 -> और 2_3;
or3_2 -> or2_3;
or3_2 -> और3_3;

or3_3 -> और -2_4;
or3_3 -> or2_4;
or3_3 -> और3_4;

or3_4 -> और -2_5;
or3_4 -> or2_5;
or3_4 -> और3_5;

or3_5 -> और -2_6;
or3_5 -> or2_6;
or3_5 -> और3_6;

or3_6 -> और -2_7;
or3_6 -> or2_7;
or3_6 -> और3_7;

or3_7 -> पी 1;
}

प्रयोग १

हिल्बर्ट वक्र का प्रारंभिक चरण - (पास, सेल, सेल, पास)
ग्राफ कोने (इकाई कोशिकाओं) वर्णानुक्रम में हल किया

अंजीर। X पर - शुरुआत से शिफ्ट, वाई पर - सभी रास्तों की लंबाई

207 की शिफ्ट में न्यूनतम दूरी (पहली), (सभी बॉन्ड की कुल लंबाई 1968 है), आइए देखें कि यह सबसे इष्टतम क्या लगता है।

चित्रा 10 शिफ्ट 207 के लिए इष्टतम ग्राफ है, यह बहुत अच्छा नहीं लगता है।

प्रयोग २

हिल्बर्ट वक्र का प्रारंभिक चरण - (पास, सेल, सेल, पास)
प्राकृतिक क्रम में ग्राफ (इकाई कोशिकाओं) के कोने (जैसा कि ग्राफ के विवरण में आया था, ऊपर दिए गए ग्राफ का विवरण देखें) -

11 एक्स पर - शुरुआत से शिफ्ट, वाई पर - सभी रास्तों की लंबाई

अंजीर। कतरनी 11 लंबाई 750 के लिए 12 इष्टतम ग्राफ

प्रयोग ३

हिल्बर्ट वक्र का प्रारंभिक चरण - (पास, सेल, सेल, पास)
शीर्षकों का क्रम ग्राफ की चौड़ाई का पता लगाकर निर्धारित किया जाता है, सूची की शुरुआत में लिंक के बिना कोने, अंत तक सप्ताहांत

Fig.13 X पर - शुरुआत से शिफ्ट, Y - सभी रास्तों की लंबाई पर

अंजीर। 14 इष्टतम व्यवस्था - पारी 3, कुल लंबाई 1451
शुरुआत में सभी इनपुट कोने डालें और अंत में आउटपुट बहुत अच्छा नहीं था
एक विचार।

प्रयोग ४

हिल्बर्ट वक्र का प्रारंभिक चरण - (पास, सेल, सेल) सिसिली!
शीर्ष क्रम प्राकृतिक है, जैसा कि प्रयोग 2 में है

Fig.15 X पर - शुरुआत से शिफ्ट, Y - सभी रास्तों की लंबाई पर

अंजीर। 16 इष्टतम व्यवस्था - पारी 10, कुल लंबाई 503

प्रयोग ५

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

हिल्बर्ट वक्र का प्रारंभिक चरण - (छोड़ें, सेल, सेल)
कोने के क्रम को चौड़ाई में देखकर निर्धारित किया जाता है, लेकिन बिना IO कोने के

X पर Fig.17 शुरुआत से पारी है, Y सभी रास्तों की लंबाई है

अंजीर। 18 इष्टतम स्थान 607, 484 की कुल लंबाई, औसत 3.33793 है

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

प्रयोग ६

पैरामीटर प्रयोग 5 में समान हैं, हम क्षेत्र का अनुकूलन करते हैं।

Fig.19 X पर - शुरुआत से शिफ्ट, Y - सभी रास्तों की लंबाई पर

अंजीर। 20 इष्टतम व्यवस्था - शिफ्ट 966, कुल लंबाई 639, औसत 3.30345

आयत काफी लम्बी हो गई। लेकिन क्या होगा अगर हम आयत के क्षेत्र को नहीं, बल्कि कर्ण के वर्ग को मानते हैं, हमें और अधिक चौकोर आकार में धकेलते हैं?

प्रयोग 7

पैरामीटर प्रयोग 5 में समान हैं, हम कर्ण के वर्ग का अनुकूलन करते हैं।

X पर Fig.21 शुरुआत से पारी है, Y सभी रास्तों की लंबाई है

अंजीर। 22 इष्टतम व्यवस्था - शिफ्ट 70, कुल लंबाई 702, औसत 3.46207

प्रयोग 8

हिल्बर्ट वक्र का प्राथमिक चरण - (सेल, स्किप) सिसिली!
कोने के क्रम को चौड़ाई में देखकर निर्धारित किया जाता है, लेकिन बिना IO कोने के

हम मानते हैं कि वाई में चलने की लागत एक्स की तुलना में दोगुनी है, यह वास्तविकता के करीब है।

X पर Fig.23 शुरुआत से पारी है, Y सभी रास्तों की लंबाई है

अंजीर। 24 इष्टतम व्यवस्था - पारी 344, कुल लंबाई 650, औसत 3.8

निष्कर्ष

प्रारंभिक "संपादकों की पसंद" - प्रयोग 6।

IO वर्टिकल की व्यवस्था करना अच्छा होगा, लेकिन इसके लिए साइड से एक संकेत की आवश्यकता होती है,
जहां बिल्कुल (दिशा) इस वर्ग के कोने स्थित होने चाहिए।

लेकिन पहले मैं विशेषज्ञों की राय सुनना चाहूंगा।

पुनश्च : एक पलटा नकारात्मक प्रतिक्रिया की कमी के लिए यूरीपंचुल और andy_p के लिए धन्यवाद।

UPD (11/02/2019): जोड़ा गया "प्रयोग 8", जहां मानक कोशिकाएं हिल्बर्ट वक्र के नोड्स पर स्थित हैं, अर्थात एक वर्ग जाली पर सख्ती से। इसके अलावा, एक ओर, वे पारंपरिक पंक्तियों में संयुक्त होते हैं, और दूसरी ओर, वे हिल्बर्ट वक्र के साथ स्थित होते हैं।

मानक कोशिकाओं (एक बाहरी व्यक्ति के नोट्स) की व्यवस्था करना