अंर्तवर्तक ग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Graph representing an implementation of the logical functionality of a network}}
{{short description|Graph representing an implementation of the logical functionality of a network}}
एक और इन्वर्टर ग्राफ (एआईजी) निर्देशित, एसाइक्लिक [[ग्राफ (असतत गणित)]] है जो [[डिजिटल सर्किट]] की तार्किक कार्यक्षमता के संरचनात्मक कार्यान्वयन का प्रतिनिधित्व करता है। एआईजी में [[तार्किक संयोजन]] का प्रतिनिधित्व करने वाले दो-इनपुट नोड्स होते हैं, चर नामों के साथ लेबल किए गए टर्मिनल नोड्स, और किनारों पर वैकल्पिक रूप से मार्कर होते हैं जो [[तार्किक निषेध]] का संकेत देते हैं। लॉजिक फ़ंक्शन का यह प्रतिनिधित्व बड़े सर्किट के लिए शायद ही कभी संरचनात्मक रूप से कुशल होता है, लेकिन [[बूलियन समारोह]] के हेरफेर के लिए कुशल प्रतिनिधित्व है। आमतौर पर, अमूर्त ग्राफ को सॉफ्टवेयर में [[डेटा संरचना]] के रूप में दर्शाया जाता है।
अंर्तवर्तक ग्राफ (एआईजी) ऐसे निर्देशित एसाइक्लिक [[ग्राफ (असतत गणित)]] होते हैं जो [[डिजिटल सर्किट|डिजिटल परिपथ]] की तार्किक कार्यक्षमता के संरचनात्मक कार्यान्वयन का प्रतिनिधित्व करते हैं। एआईजी में [[तार्किक संयोजन]] का प्रतिनिधित्व करने वाले दो-इनपुट नोड्स होते हैं, जिनके चर (वैरिेयेबल) के नामों के साथ लेबल किए गए टर्मिनल नोड्स, और किनारों पर उपस्थित वैकल्पिक प्रकारों से मार्क किया जाता हैं जो [[तार्किक निषेध|तार्किक]] NOT का संकेत देते हैं। तार्किक फ़ंक्शन का यह प्रतिनिधित्व बड़े परिपथ के लिए संभवतः कुछ स्थितियों में संरचनात्मक रूप से कुशल हो सकता हैं, लेकिन [[बूलियन समारोह|बूलियन फंक्शन]] के परिवर्तन के लिए कुशल प्रतिनिधित्व करता है। सामान्यतः अमूर्त ग्राफ को सॉफ्टवेयर में [[डेटा संरचना]] के रूप में दर्शाया जाता है।
[[Image:And-inverter-graph.svg|thumb|400px|फ़ंक्शन f(x1, x2, x3) = x2 * ( x1 + x3 ) के लिए दो संरचनात्मक रूप से भिन्न AIGs]][[ तर्क द्वार ]]्स के नेटवर्क से एआईजी में रूपांतरण तेज और स्केलेबल है। इसके लिए केवल यह आवश्यक है कि प्रत्येक गेट को AND गेट्स और [[इन्वर्टर (लॉजिक गेट)]] के संदर्भ में व्यक्त किया जाए। इस रूपांतरण से मेमोरी उपयोग और रनटाइम में अप्रत्याशित वृद्धि नहीं होती है। यह AIG को [[ द्विआधारी निर्णय आरेख |द्विआधारी निर्णय आरेख]] (BDD) या सम-ऑफ-प्रोडक्ट (ΣoΠ) फॉर्म की तुलना में कुशल प्रतिनिधित्व बनाता है। अर्थात्, [[बूलियन बीजगणित (तर्क)]] में [[विहित रूप (बूलियन बीजगणित)]] जिसे वियोगात्मक सामान्य रूप (DNF) के रूप में जाना जाता है। बीडीडी और डीएनएफ को सर्किट के रूप में भी देखा जा सकता है, लेकिन उनमें औपचारिक बाधाएं शामिल हैं जो उन्हें मापनीयता से वंचित करती हैं। उदाहरण के लिए, ΣoΠ अधिकतम दो स्तरों वाले सर्किट होते हैं, जबकि BDD विहित होते हैं, अर्थात, उन्हें सभी पथों पर ही क्रम में इनपुट चर का मूल्यांकन करने की आवश्यकता होती है।
[[Image:And-inverter-graph.svg|thumb|400px|फ़ंक्शन f(x1, x2, x3) = x2 * ( x1 + x3 ) के लिए दो संरचनात्मक रूप से भिन्न AIGs]][[ तर्क द्वार | तर्क]] गेट के नेटवर्क से एआईजी में रूपांतरण तेज गति और स्केलेबल विधि से होता हैं। इसके लिए केवल यह आवश्यक है कि प्रत्येक गेट को AND गेट्स और [[इन्वर्टर (लॉजिक गेट)|अंर्तवर्तक (लॉजिक गेट)]] के संदर्भ में व्यक्त किया जाए। इस रूपांतरण से मेमोरी उपयोग और रनटाइम में अप्रत्याशित वृद्धि नहीं होती है। यह एआईजी को [[ द्विआधारी निर्णय आरेख |द्विआधारी निर्णय आरेख]] (BDD) या सम-ऑफ-प्रोडक्ट (ΣoΠ) फॉर्म की तुलना में कुशल प्रतिनिधित्व बनाता है। इसका अर्थ यह हैं कि [[बूलियन बीजगणित (तर्क)]] में [[विहित रूप (बूलियन बीजगणित)]] जिसे वियोगात्मक सामान्य रूप (DNF) के रूप में जाना जाता है। बीडीडी और डीएनएफ को परिपथ के रूप में भी देखा जा सकता है, लेकिन उनमें औपचारिक बाधाएं सम्मिलित रहती हैं जो इनको मुख्य रूप से इसकी मापनीयता से वंचित करती हैं। उदाहरण के लिए, ΣoΠ अधिकतम दो स्तरों वाले परिपथ होते हैं, जबकि बीडीडी विहित होते हैं, जिसका अर्थ हैं कि उन्हें सभी गेट्स के लिए क्रम में इनपुट वैरियेबल के मान का अंकन करने की आवश्यकता होती है।


एआईजी समेत सरल गेट्स से बना सर्किट प्राचीन शोध विषय है। एआईजी में रुचि की शुरुआत एलन ट्यूरिंग के मौलिक 1948 के पेपर से हुई<ref>Turing's 1948 paper has been re-printed as Turing AM. Intelligent Machinery. In: Ince DC, editor. ''Collected works of AM Turing — Mechanical Intelligence.'' Elsevier Science Publishers, 1992.</ref> तंत्रिका नेटवर्क पर, जिसमें उन्होंने नंद द्वारों के यादृच्छिक प्रशिक्षित नेटवर्क का वर्णन किया। रुचि 1950 के दशक के अंत तक जारी रही<ref>{{cite journal|author =L. Hellerman|title=तीन-चर या-इन्वर्टर और एंड-इन्वर्टर लॉजिकल सर्किट की एक सूची|journal=IEEE Trans. Electron. Comput.|volume=EC-12|date=June 1963|pages=198–223|doi=10.1109/PGEC.1963.263531|issue=3}}</ref> और 1970 के दशक में जारी रहा जब विभिन्न स्थानीय परिवर्तन विकसित किए गए थे। ये परिवर्तन कई में लागू किए गए थे
एआईजी समेत सरल गेट्स से बना परिपथ पुराने शोध का विषय है। एआईजी में रुचि का प्रारंभ एलन ट्यूरिंग के मौलिक पेपर द्वारा 1948 में हुई थी,<ref>Turing's 1948 paper has been re-printed as Turing AM. Intelligent Machinery. In: Ince DC, editor. ''Collected works of AM Turing — Mechanical Intelligence.'' Elsevier Science Publishers, 1992.</ref> इस प्रकार के नेटवर्क में जिसमें उन्होंने NAND गेट के यादृच्छिक प्रशिक्षित नेटवर्क का वर्णन किया है। इसके कारण 1950 के दशक के अंत तक इसे प्रस्तुत किया गया था<ref>{{cite journal|author =L. Hellerman|title=तीन-चर या-इन्वर्टर और एंड-इन्वर्टर लॉजिकल सर्किट की एक सूची|journal=IEEE Trans. Electron. Comput.|volume=EC-12|date=June 1963|pages=198–223|doi=10.1109/PGEC.1963.263531|issue=3}}</ref> और 1970 के दशक तक प्रस्तुत रहा, जब इसके विभिन्न स्थानीय परिवर्तन विकसित किए गए थे। ये परिवर्तन कई प्रकार से लागू किए गए थे।
तर्क संश्लेषण और सत्यापन प्रणाली, जैसे डारिंगर एट अल।<ref>{{cite journal|author1=A. Darringer |author2=W. H. Joyner, Jr. |author3=C. L. Berman |author4=L. Trevillyan |author-link4=Louise Trevillyan |title=स्थानीय परिवर्तनों के माध्यम से तर्क संश्लेषण|journal=IBM Journal of Research and Development|volume=25|issue=4|date=Jul 1981|pages=272–280|doi=10.1147/rd.254.0272|citeseerx=10.1.1.85.7515 }}</ref> और स्मिथ एट अल।,<ref>{{cite journal|author1=G. L. Smith |author2=R. J. Bahnsen |author3=H. Halliwell |title=हार्डवेयर और फ़्लोचार्ट की बूलियन तुलना|journal=IBM Journal of Research and Development|volume=26|issue=1|date=Jan 1982|pages=106–116|doi=10.1147/rd.261.0106|citeseerx=10.1.1.85.2196 }}</ref> जो क्षेत्र में सुधार के लिए सर्किट को कम करते हैं और संश्लेषण के दौरान देरी करते हैं, या [[औपचारिक तुल्यता जाँच]] को गति देते हैं। [[आईबीएम]] में कई महत्वपूर्ण तकनीकों की खोज की गई थी, जैसे बहु-इनपुट लॉजिक एक्सप्रेशन और सबएक्सप्रेशन का संयोजन और पुन: उपयोग करना, जिसे अब [[संरचनात्मक हैशिंग]] के रूप में जाना जाता है।


हाल ही में संश्लेषण और सत्यापन में विभिन्न प्रकार के कार्यों के लिए [[कार्यात्मक प्रतिनिधित्व]] के रूप में एआईजी में नए सिरे से दिलचस्पी दिखाई गई है। ऐसा इसलिए है क्योंकि 1990 के दशक में लोकप्रिय अभ्यावेदन (जैसे BDDs) अपने कई अनुप्रयोगों में मापनीयता की अपनी सीमा तक पहुँच चुके हैं। अन्य महत्वपूर्ण विकास बहुत अधिक कुशल [[बूलियन संतुष्टि]] (एसएटी) सॉल्वरों का हालिया उद्भव था। सर्किट प्रतिनिधित्व के रूप में एआईजी के साथ युग्मित होने पर, वे विभिन्न प्रकार की [[बूलियन समस्या]]ओं को हल करने में उल्लेखनीय गति प्रदान करते हैं।
इस प्रकार तर्क संश्लेषण और सत्यापन प्रणाली, जैसे डारिंगर एट अल<ref>{{cite journal|author1=A. Darringer |author2=W. H. Joyner, Jr. |author3=C. L. Berman |author4=L. Trevillyan |author-link4=Louise Trevillyan |title=स्थानीय परिवर्तनों के माध्यम से तर्क संश्लेषण|journal=IBM Journal of Research and Development|volume=25|issue=4|date=Jul 1981|pages=272–280|doi=10.1147/rd.254.0272|citeseerx=10.1.1.85.7515 }}</ref> और स्मिथ एट अल<ref>{{cite journal|author1=G. L. Smith |author2=R. J. Bahnsen |author3=H. Halliwell |title=हार्डवेयर और फ़्लोचार्ट की बूलियन तुलना|journal=IBM Journal of Research and Development|volume=26|issue=1|date=Jan 1982|pages=106–116|doi=10.1147/rd.261.0106|citeseerx=10.1.1.85.2196 }}</ref> के द्वारा जो क्षेत्रों में सुधार के लिए परिपथ को कम करते हैं और संश्लेषण के समय देरी करते हैं, या [[औपचारिक तुल्यता जाँच]] को गति देते हैं। [[आईबीएम]] में कई महत्वपूर्ण विधियों की खोज की गई थी, जैसे बहु-इनपुट लॉजिक एक्सप्रेशन और सबएक्सप्रेशन का संयोजन और पुन: उपयोग करना, जिसे अब [[संरचनात्मक हैशिंग]] के रूप में जाना जाता है।


एआईजी को विविध [[ इलेक्ट्रॉनिक डिजाइन स्वचालन |इलेक्ट्रॉनिक डिजाइन स्वचालन]] अनुप्रयोगों में सफल उपयोग मिला। एआईजी और बूलियन संतुष्टि के सुव्यवस्थित संयोजन ने [[औपचारिक सत्यापन]] पर प्रभाव डाला, जिसमें मॉडल जाँच और तुल्यता जाँच दोनों शामिल हैं।<ref>{{cite journal|author1=A. Kuehlmann |author2=V. Paruthi |author3=F. Krohm |author4=M. K. Ganai |title=तुल्यता जाँच और कार्यात्मक संपत्ति सत्यापन के लिए मजबूत बूलियन तर्क|journal=IEEE Trans. CAD|volume=21|issue=12|year=2002|pages=1377–1394|doi=10.1109/tcad.2002.804386|citeseerx=10.1.1.119.9047 }}</ref> अन्य हालिया काम से पता चलता है कि एआईजी का उपयोग करके कुशल सर्किट संपीड़न तकनीकों का विकास किया जा सकता है।<ref>{{cite conference|author1=Per Bjesse |author2=Arne Borälv |title=औपचारिक सत्यापन के लिए डीएजी-जागरूक सर्किट संपीड़न|book-title=Proc. ICCAD '04|pages=42–49|date=2004|url=http://www.perbjesse.com/iccad04.pdf}}</ref> बढ़ती समझ है कि कार्यात्मक गुणों (जैसे समरूपता) की गणना करने के लिए सिमुलेशन और बूलियन संतुष्टि का उपयोग करके तर्क और भौतिक संश्लेषण की समस्याओं को हल किया जा सकता है।<ref>{{cite conference|author1=K.-H. Chang |author2=I. L. Markov |author3=V. Bertacco |title=कार्यात्मक समरूपता के लिए संपूर्ण खोज द्वारा पोस्ट-प्लेसमेंट रिवाइरिंग और रीबफ़रिंग|book-title=Proc. ICCAD '05|pages=56–63|date=2005|url=http://web.eecs.umich.edu/~imarkov/pubs/misc/iwls05-rew.pdf}}</ref> और नोड लचीलेपन (जैसे कि देखभाल न करने की शर्तें, [[पुनर्स्थापन]], और विशिष्ट किए जाने वाले कार्यों के जोड़े के सेट)।<ref>{{cite journal|author1=A. Mishchenko |author2=J. S. Zhang |author3=S. Sinha |author4=J. R. Burch |author5=R. Brayton |author6=M. Chrzanowska-Jeske |title=बूलियन नेटवर्क में लचीलेपन की गणना करने के लिए सिमुलेशन और संतुष्टि का उपयोग करना|journal=IEEE Trans. CAD|volume=25|issue=5|date=May 2006|pages=743–755|url=http://www.eecs.berkeley.edu/~alanmi/publications/2005/tcad05_s%26s.pdf |doi=10.1109/tcad.2005.860955|citeseerx=10.1.1.62.8602 }}</ref><ref>{{cite book |author1=S. Sinha |author2=R. K. Brayton | contribution=Implementation and use of SPFDs in optimizing Boolean networks | title=प्रक्रिया। आईसीसीएडी|  pages=103–110 | date=1998 |citeseerx = 10.1.1.488.8889}}</ref><ref>{{cite book | contribution-url=http://www.kecl.ntt.co.jp/csl/car/members/ger/mypaper/pdf/iccad96.pdf |author1=S. Yamashita |author2=H. Sawada |author3=A. Nagoya | contribution=A new method to express functional permissibilities for LUT based FPGAs and its applications |  title=Proc. ICCAD | pages=254–261 | date=1996 }}</ref> मिशचेंको एट अल। दिखाता है कि एआईजी आशाजनक एकीकृत प्रतिनिधित्व है, जो [[तर्क संश्लेषण]], [[प्रौद्योगिकी मानचित्रण]], भौतिक संश्लेषण और औपचारिक सत्यापन को पाट सकता है। यह काफी हद तक एआईजी की सरल और समान संरचना के कारण है, जो समान डेटा संरचना को साझा करने के लिए पुनर्लेखन, सिमुलेशन, मैपिंग, प्लेसमेंट और सत्यापन की अनुमति देता है।
वर्तमान समय में संश्लेषण और सत्यापन में विभिन्न प्रकार के कार्यों के लिए [[कार्यात्मक प्रतिनिधित्व]] के रूप में एआईजी में नए सिरे से रूचि दिखाई गई है। ऐसा इसलिए है क्योंकि 1990 के दशक में लोकप्रिय अभ्यावेदन (जैसे BDDs) अपने कई अनुप्रयोगों में मापनीयता की अपनी सीमा तक पहुँच चुके हैं। अन्य महत्वपूर्ण विकास बहुत अधिक कुशल [[बूलियन संतुष्टि]] (एसएटी) सॉल्वरों का वर्तमान समय में उद्भव हुआ था। परिपथ प्रतिनिधित्व के रूप में एआईजी के साथ युग्मित होने पर वे विभिन्न प्रकार की [[बूलियन समस्या]]ओं को हल करने में उल्लेखनीय गति प्रदान करते हैं।


कॉम्बिनेशन लॉजिक के अलावा, एआईजी को अनुक्रमिक लॉजिक और अनुक्रमिक परिवर्तनों पर भी लागू किया गया है। विशेष रूप से, संरचनात्मक हैशिंग की विधि एआईजी के लिए स्मृति तत्वों (जैसे फ्लिप-फ्लॉप (इलेक्ट्रॉनिक्स) # डी फ्लिप-फ्लॉप | डी-टाइप फ्लिप-फ्लॉप प्रारंभिक स्थिति के साथ काम करने के लिए विस्तारित की गई थी,
एआईजी को विविध [[ इलेक्ट्रॉनिक डिजाइन स्वचालन |इलेक्ट्रॉनिक डिजाइन स्वचालन]] अनुप्रयोगों में सफल उपयोग मिला हैं। इस प्रकार एआईजी और बूलियन संतुष्टि के सुव्यवस्थित संयोजन ने [[औपचारिक सत्यापन]] पर प्रभाव डाला हैं, जिसमें मॉडल जाँच और तुल्यता जाँच दोनों सम्मिलित हैं।<ref>{{cite journal|author1=A. Kuehlmann |author2=V. Paruthi |author3=F. Krohm |author4=M. K. Ganai |title=तुल्यता जाँच और कार्यात्मक संपत्ति सत्यापन के लिए मजबूत बूलियन तर्क|journal=IEEE Trans. CAD|volume=21|issue=12|year=2002|pages=1377–1394|doi=10.1109/tcad.2002.804386|citeseerx=10.1.1.119.9047 }}</ref> अन्य वर्तमान स्थितियों के कार्य से पता चलता है कि एआईजी का उपयोग करके कुशल परिपथ संपीड़न विधियों का विकास किया जा सकता है।<ref>{{cite conference|author1=Per Bjesse |author2=Arne Borälv |title=औपचारिक सत्यापन के लिए डीएजी-जागरूक सर्किट संपीड़न|book-title=Proc. ICCAD '04|pages=42–49|date=2004|url=http://www.perbjesse.com/iccad04.pdf}}</ref> इसकी बढ़ती समझ को देखते हुए इनके कार्यात्मक गुणों (जैसे समरूपता) की गणना करने के लिए सिमुलेशन और बूलियन संतुष्टि का उपयोग करके तर्क और भौतिक संश्लेषण की समस्याओं को हल किया जा सकता है।<ref>{{cite conference|author1=K.-H. Chang |author2=I. L. Markov |author3=V. Bertacco |title=कार्यात्मक समरूपता के लिए संपूर्ण खोज द्वारा पोस्ट-प्लेसमेंट रिवाइरिंग और रीबफ़रिंग|book-title=Proc. ICCAD '05|pages=56–63|date=2005|url=http://web.eecs.umich.edu/~imarkov/pubs/misc/iwls05-rew.pdf}}</ref> इसके अनुसार नोड के लचीलेपन जैसे कि देखभाल न करने की शर्तें, [[पुनर्स्थापन]], और विशिष्ट किए जाने वाले कार्यों के जोड़े के सेट को संलग्न किया जाता हैं।<ref>{{cite journal|author1=A. Mishchenko |author2=J. S. Zhang |author3=S. Sinha |author4=J. R. Burch |author5=R. Brayton |author6=M. Chrzanowska-Jeske |title=बूलियन नेटवर्क में लचीलेपन की गणना करने के लिए सिमुलेशन और संतुष्टि का उपयोग करना|journal=IEEE Trans. CAD|volume=25|issue=5|date=May 2006|pages=743–755|url=http://www.eecs.berkeley.edu/~alanmi/publications/2005/tcad05_s%26s.pdf |doi=10.1109/tcad.2005.860955|citeseerx=10.1.1.62.8602 }}</ref><ref>{{cite book |author1=S. Sinha |author2=R. K. Brayton | contribution=Implementation and use of SPFDs in optimizing Boolean networks | title=प्रक्रिया। आईसीसीएडी|  pages=103–110 | date=1998 |citeseerx = 10.1.1.488.8889}}</ref><ref>{{cite book | contribution-url=http://www.kecl.ntt.co.jp/csl/car/members/ger/mypaper/pdf/iccad96.pdf |author1=S. Yamashita |author2=H. Sawada |author3=A. Nagoya | contribution=A new method to express functional permissibilities for LUT based FPGAs and its applications |  title=Proc. ICCAD | pages=254–261 | date=1996 }}</ref> मिशचेंको एट अल के नियम में यह दिखता है कि एआईजी आशाजनक एकीकृत प्रतिनिधित्व है, जो [[तर्क संश्लेषण]], [[प्रौद्योगिकी मानचित्रण]], भौतिक संश्लेषण और औपचारिक सत्यापन को विलोपित कर सकते है। यह अधिक सीमा तक एआईजी की सरल और समान संरचना के कारण है, जो समान डेटा संरचना को साझा करने के लिए पुनर्लेखन, सिमुलेशन, मैपिंग, प्लेसमेंट और सत्यापन की अनुमति देता है।
जो सामान्य रूप से अज्ञात हो सकता है) जिसके परिणामस्वरूप डेटा संरचना होती है जो विशेष रूप से [[retiming]] से संबंधित अनुप्रयोगों के लिए तैयार की जाती है।<ref>{{cite conference|author1=J. Baumgartner |author2=A. Kuehlmann |title=फ्लेक्सिबल सर्किट स्ट्रक्चर्स पर मिन-एरिया रिटिमिंग|book-title= Proc. ICCAD'01|pages=176–182|date=2001|url=http://public.dhe.ibm.com/software/es/info/iwls01_ret.pdf}}</ref>
 
चल रहे शोध में पूरी तरह से एआईजी पर आधारित आधुनिक तर्क संश्लेषण प्रणाली को लागू करना शामिल है। [http://www.eecs.berkeley.edu/~alanmi/abc/ ABC] नामक प्रोटोटाइप में एआईजी पैकेज, कई एआईजी-आधारित संश्लेषण और समकक्ष-जांच तकनीक, साथ ही अनुक्रमिक संश्लेषण का प्रयोगात्मक कार्यान्वयन शामिल है। ऐसी ही तकनीक अनुकूलन चरण में प्रौद्योगिकी मानचित्रण और रीटिमिंग को जोड़ती है। इन अनुकूलनों को स्वैच्छिक फाटकों से बने नेटवर्क का उपयोग करके कार्यान्वित किया जा सकता है, लेकिन एआईजी का उपयोग उन्हें अधिक मापनीय और लागू करने में आसान बनाता है।
कॉम्बिनेशन लॉजिक के अलावा, एआईजी को अनुक्रमिक लॉजिक और अनुक्रमिक परिवर्तनों पर भी लागू किया गया है। विशेष रूप से, संरचनात्मक हैशिंग की विधि एआईजी के लिए स्मृति तत्वों (जैसे फ्लिप-फ्लॉप (इलेक्ट्रॉनिक्स) डी फ्लिप-फ्लॉप या डी-टाइप फ्लिप-फ्लॉप प्रारंभिक स्थिति के साथ कार्य करने के लिए विस्तारित की गई थी, जो सामान्य रूप से अज्ञात हो सकता है तथा जिसके परिणामस्वरूप डेटा की संरचना होती है जो विशेष रूप से [[retiming|रेटीमिंग]] से संबंधित अनुप्रयोगों के लिए तैयार की जाती है।<ref>{{cite conference|author1=J. Baumgartner |author2=A. Kuehlmann |title=फ्लेक्सिबल सर्किट स्ट्रक्चर्स पर मिन-एरिया रिटिमिंग|book-title= Proc. ICCAD'01|pages=176–182|date=2001|url=http://public.dhe.ibm.com/software/es/info/iwls01_ret.pdf}}</ref>
 
इस प्रकार चल रहे शोध में पूर्ण रूप से एआईजी पर आधारित आधुनिक तर्क संश्लेषण प्रणाली को लागू करना सम्मिलित है। इस प्रकार [http://www.eecs.berkeley.edu/~alanmi/abc/ ABC] प्रोटोटाइप में एआईजी पैकेज, कई एआईजी-आधारित संश्लेषण और समकक्ष-जांच तकनीक के साथ ही अनुक्रमिक संश्लेषण का प्रयोगात्मक कार्यान्वयन भी सम्मिलित है। ऐसी तकनीक अनुकूलन चरण में प्रौद्योगिकी मानचित्रण और रीटिमिंग को संयोजित करती हैं। इन अनुकूलनों को स्वैच्छिक फाटकों से बने नेटवर्क का उपयोग करके कार्यान्वित किया जा सकता है, लेकिन एआईजी का उपयोग उन्हें अधिक मापनीय और लागू करने में सरल बनाता है।


== कार्यान्वयन ==
== कार्यान्वयन ==
* तर्क संश्लेषण और सत्यापन प्रणाली [http://www.eecs.berkeley.edu/~alanmi/abc/ ABC]
* तर्क संश्लेषण और सत्यापन प्रणाली [http://www.eecs.berkeley.edu/~alanmi/abc/ ABC]
* एआईजी के लिए उपयोगिताओं का सेट [http://fmv.jku.at/aiger/index.html AIGER]
* एआईजी के लिए उपयोगिताओं के लिए समुच्चय [http://fmv.jku.at/aiger/index.html AIGER]
* [https://web.archive.org/web/20150924101539/http://www.si2.org/openeda.si2.org/help/group_ld.php?group=73 OpenAccess गियर]
* ओपेन एक्सेस [https://web.archive.org/web/20150924101539/http://www.si2.org/openeda.si2.org/help/group_ld.php?group=73 गियर]
* गिनी [http://godoc.org/github.com/go-air/gini/logic तर्क पुस्तकालय]
* गिनी [http://godoc.org/github.com/go-air/gini/logic तर्क लाइब्रेरी]


==संदर्भ==
==संदर्भ==

Revision as of 22:11, 4 March 2023

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

फ़ंक्शन f(x1, x2, x3) = x2 * ( x1 + x3 ) के लिए दो संरचनात्मक रूप से भिन्न AIGs

तर्क गेट के नेटवर्क से एआईजी में रूपांतरण तेज गति और स्केलेबल विधि से होता हैं। इसके लिए केवल यह आवश्यक है कि प्रत्येक गेट को AND गेट्स और अंर्तवर्तक (लॉजिक गेट) के संदर्भ में व्यक्त किया जाए। इस रूपांतरण से मेमोरी उपयोग और रनटाइम में अप्रत्याशित वृद्धि नहीं होती है। यह एआईजी को द्विआधारी निर्णय आरेख (BDD) या सम-ऑफ-प्रोडक्ट (ΣoΠ) फॉर्म की तुलना में कुशल प्रतिनिधित्व बनाता है। इसका अर्थ यह हैं कि बूलियन बीजगणित (तर्क) में विहित रूप (बूलियन बीजगणित) जिसे वियोगात्मक सामान्य रूप (DNF) के रूप में जाना जाता है। बीडीडी और डीएनएफ को परिपथ के रूप में भी देखा जा सकता है, लेकिन उनमें औपचारिक बाधाएं सम्मिलित रहती हैं जो इनको मुख्य रूप से इसकी मापनीयता से वंचित करती हैं। उदाहरण के लिए, ΣoΠ अधिकतम दो स्तरों वाले परिपथ होते हैं, जबकि बीडीडी विहित होते हैं, जिसका अर्थ हैं कि उन्हें सभी गेट्स के लिए क्रम में इनपुट वैरियेबल के मान का अंकन करने की आवश्यकता होती है।

एआईजी समेत सरल गेट्स से बना परिपथ पुराने शोध का विषय है। एआईजी में रुचि का प्रारंभ एलन ट्यूरिंग के मौलिक पेपर द्वारा 1948 में हुई थी,[1] इस प्रकार के नेटवर्क में जिसमें उन्होंने NAND गेट के यादृच्छिक प्रशिक्षित नेटवर्क का वर्णन किया है। इसके कारण 1950 के दशक के अंत तक इसे प्रस्तुत किया गया था[2] और 1970 के दशक तक प्रस्तुत रहा, जब इसके विभिन्न स्थानीय परिवर्तन विकसित किए गए थे। ये परिवर्तन कई प्रकार से लागू किए गए थे।

इस प्रकार तर्क संश्लेषण और सत्यापन प्रणाली, जैसे डारिंगर एट अल[3] और स्मिथ एट अल[4] के द्वारा जो क्षेत्रों में सुधार के लिए परिपथ को कम करते हैं और संश्लेषण के समय देरी करते हैं, या औपचारिक तुल्यता जाँच को गति देते हैं। आईबीएम में कई महत्वपूर्ण विधियों की खोज की गई थी, जैसे बहु-इनपुट लॉजिक एक्सप्रेशन और सबएक्सप्रेशन का संयोजन और पुन: उपयोग करना, जिसे अब संरचनात्मक हैशिंग के रूप में जाना जाता है।

वर्तमान समय में संश्लेषण और सत्यापन में विभिन्न प्रकार के कार्यों के लिए कार्यात्मक प्रतिनिधित्व के रूप में एआईजी में नए सिरे से रूचि दिखाई गई है। ऐसा इसलिए है क्योंकि 1990 के दशक में लोकप्रिय अभ्यावेदन (जैसे BDDs) अपने कई अनुप्रयोगों में मापनीयता की अपनी सीमा तक पहुँच चुके हैं। अन्य महत्वपूर्ण विकास बहुत अधिक कुशल बूलियन संतुष्टि (एसएटी) सॉल्वरों का वर्तमान समय में उद्भव हुआ था। परिपथ प्रतिनिधित्व के रूप में एआईजी के साथ युग्मित होने पर वे विभिन्न प्रकार की बूलियन समस्याओं को हल करने में उल्लेखनीय गति प्रदान करते हैं।

एआईजी को विविध इलेक्ट्रॉनिक डिजाइन स्वचालन अनुप्रयोगों में सफल उपयोग मिला हैं। इस प्रकार एआईजी और बूलियन संतुष्टि के सुव्यवस्थित संयोजन ने औपचारिक सत्यापन पर प्रभाव डाला हैं, जिसमें मॉडल जाँच और तुल्यता जाँच दोनों सम्मिलित हैं।[5] अन्य वर्तमान स्थितियों के कार्य से पता चलता है कि एआईजी का उपयोग करके कुशल परिपथ संपीड़न विधियों का विकास किया जा सकता है।[6] इसकी बढ़ती समझ को देखते हुए इनके कार्यात्मक गुणों (जैसे समरूपता) की गणना करने के लिए सिमुलेशन और बूलियन संतुष्टि का उपयोग करके तर्क और भौतिक संश्लेषण की समस्याओं को हल किया जा सकता है।[7] इसके अनुसार नोड के लचीलेपन जैसे कि देखभाल न करने की शर्तें, पुनर्स्थापन, और विशिष्ट किए जाने वाले कार्यों के जोड़े के सेट को संलग्न किया जाता हैं।[8][9][10] मिशचेंको एट अल के नियम में यह दिखता है कि एआईजी आशाजनक एकीकृत प्रतिनिधित्व है, जो तर्क संश्लेषण, प्रौद्योगिकी मानचित्रण, भौतिक संश्लेषण और औपचारिक सत्यापन को विलोपित कर सकते है। यह अधिक सीमा तक एआईजी की सरल और समान संरचना के कारण है, जो समान डेटा संरचना को साझा करने के लिए पुनर्लेखन, सिमुलेशन, मैपिंग, प्लेसमेंट और सत्यापन की अनुमति देता है।

कॉम्बिनेशन लॉजिक के अलावा, एआईजी को अनुक्रमिक लॉजिक और अनुक्रमिक परिवर्तनों पर भी लागू किया गया है। विशेष रूप से, संरचनात्मक हैशिंग की विधि एआईजी के लिए स्मृति तत्वों (जैसे फ्लिप-फ्लॉप (इलेक्ट्रॉनिक्स) डी फ्लिप-फ्लॉप या डी-टाइप फ्लिप-फ्लॉप प्रारंभिक स्थिति के साथ कार्य करने के लिए विस्तारित की गई थी, जो सामान्य रूप से अज्ञात हो सकता है तथा जिसके परिणामस्वरूप डेटा की संरचना होती है जो विशेष रूप से रेटीमिंग से संबंधित अनुप्रयोगों के लिए तैयार की जाती है।[11]

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

कार्यान्वयन

  • तर्क संश्लेषण और सत्यापन प्रणाली ABC
  • एआईजी के लिए उपयोगिताओं के लिए समुच्चय AIGER
  • ओपेन एक्सेस गियर
  • गिनी तर्क लाइब्रेरी

संदर्भ

  1. ↑ Turing's 1948 paper has been re-printed as Turing AM. Intelligent Machinery. In: Ince DC, editor. Collected works of AM Turing — Mechanical Intelligence. Elsevier Science Publishers, 1992.
  2. ↑ L. Hellerman (June 1963). "तीन-चर या-इन्वर्टर और एंड-इन्वर्टर लॉजिकल सर्किट की एक सूची". IEEE Trans. Electron. Comput. EC-12 (3): 198–223. doi:10.1109/PGEC.1963.263531.
  3. ↑ A. Darringer; W. H. Joyner, Jr.; C. L. Berman; L. Trevillyan (Jul 1981). "स्थानीय परिवर्तनों के माध्यम से तर्क संश्लेषण". IBM Journal of Research and Development. 25 (4): 272–280. CiteSeerX 10.1.1.85.7515. doi:10.1147/rd.254.0272.
  4. ↑ G. L. Smith; R. J. Bahnsen; H. Halliwell (Jan 1982). "हार्डवेयर और फ़्लोचार्ट की बूलियन तुलना". IBM Journal of Research and Development. 26 (1): 106–116. CiteSeerX 10.1.1.85.2196. doi:10.1147/rd.261.0106.
  5. ↑ A. Kuehlmann; V. Paruthi; F. Krohm; M. K. Ganai (2002). "तुल्यता जाँच और कार्यात्मक संपत्ति सत्यापन के लिए मजबूत बूलियन तर्क". IEEE Trans. CAD. 21 (12): 1377–1394. CiteSeerX 10.1.1.119.9047. doi:10.1109/tcad.2002.804386.
  6. ↑ Per Bjesse; Arne Borälv (2004). "औपचारिक सत्यापन के लिए डीएजी-जागरूक सर्किट संपीड़न" (PDF). Proc. ICCAD '04. pp. 42–49.
  7. ↑ K.-H. Chang; I. L. Markov; V. Bertacco (2005). "कार्यात्मक समरूपता के लिए संपूर्ण खोज द्वारा पोस्ट-प्लेसमेंट रिवाइरिंग और रीबफ़रिंग" (PDF). Proc. ICCAD '05. pp. 56–63.
  8. ↑ A. Mishchenko; J. S. Zhang; S. Sinha; J. R. Burch; R. Brayton; M. Chrzanowska-Jeske (May 2006). "बूलियन नेटवर्क में लचीलेपन की गणना करने के लिए सिमुलेशन और संतुष्टि का उपयोग करना" (PDF). IEEE Trans. CAD. 25 (5): 743–755. CiteSeerX 10.1.1.62.8602. doi:10.1109/tcad.2005.860955.
  9. ↑ S. Sinha; R. K. Brayton (1998). "Implementation and use of SPFDs in optimizing Boolean networks". प्रक्रिया। आईसीसीएडी. pp. 103–110. CiteSeerX 10.1.1.488.8889.
  10. ↑ S. Yamashita; H. Sawada; A. Nagoya (1996). "A new method to express functional permissibilities for LUT based FPGAs and its applications" (PDF). Proc. ICCAD. pp. 254–261.
  11. ↑ J. Baumgartner; A. Kuehlmann (2001). "फ्लेक्सिबल सर्किट स्ट्रक्चर्स पर मिन-एरिया रिटिमिंग" (PDF). Proc. ICCAD'01. pp. 176–182.


यह भी देखें

  • बाइनरी निर्णय आरेख
  • तार्किक संयोजन

यह लेख ACM SIGDA [1] के कॉलम से लिया गया है .html ई-न्यूज़लेटर] एलन मिशचेंको द्वारा
मूल पाठ उपलब्ध है .txt यहाँ।

श्रेणी:अनुप्रयोग-विशिष्ट रेखांकन श्रेणी: आरेख श्रेणी:विद्युत परिपथ श्रेणी:इलेक्ट्रॉनिक डिजाइन स्वचालन श्रेणी:औपचारिक तरीके

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अंर्तवर्तक_ग्राफ&oldid=106987’