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

From Vigyanwiki
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}}
{{refimprove|date=July 2014}}
एक और इन्वर्टर ग्राफ (एआईजी) निर्देशित, एसाइक्लिक [[ग्राफ (असतत गणित)]] है जो [[डिजिटल सर्किट]] की तार्किक कार्यक्षमता के संरचनात्मक कार्यान्वयन का प्रतिनिधित्व करता है। एआईजी में [[तार्किक संयोजन]] का प्रतिनिधित्व करने वाले दो-इनपुट नोड्स होते हैं, चर नामों के साथ लेबल किए गए टर्मिनल नोड्स, और किनारों पर वैकल्पिक रूप से मार्कर होते हैं जो [[तार्किक निषेध]] का संकेत देते हैं। लॉजिक फ़ंक्शन का यह प्रतिनिधित्व बड़े सर्किट के लिए शायद ही कभी संरचनात्मक रूप से कुशल होता है, लेकिन [[बूलियन समारोह]] के हेरफेर के लिए कुशल प्रतिनिधित्व है। आमतौर पर, अमूर्त ग्राफ को सॉफ्टवेयर में [[डेटा संरचना]] के रूप में दर्शाया जाता है।
एक और इन्वर्टर ग्राफ (एआईजी) एक निर्देशित, एसाइक्लिक [[ग्राफ (असतत गणित)]] है जो [[डिजिटल सर्किट]] की तार्किक कार्यक्षमता के संरचनात्मक कार्यान्वयन का प्रतिनिधित्व करता है। एक एआईजी में [[तार्किक संयोजन]] का प्रतिनिधित्व करने वाले दो-इनपुट नोड्स होते हैं, चर नामों के साथ लेबल किए गए टर्मिनल नोड्स, और किनारों पर वैकल्पिक रूप से मार्कर होते हैं जो [[तार्किक निषेध]] का संकेत देते हैं। लॉजिक फ़ंक्शन का यह प्रतिनिधित्व बड़े सर्किट के लिए शायद ही कभी संरचनात्मक रूप से कुशल होता है, लेकिन [[बूलियन समारोह]] के हेरफेर के लिए एक कुशल प्रतिनिधित्व है। आमतौर पर, अमूर्त ग्राफ को सॉफ्टवेयर में [[डेटा संरचना]] के रूप में दर्शाया जाता है।
[[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 गेट्स और [[इन्वर्टर (लॉजिक गेट)]] के संदर्भ में व्यक्त किया जाए। इस रूपांतरण से मेमोरी उपयोग और रनटाइम में अप्रत्याशित वृद्धि नहीं होती है। यह AIG को [[ द्विआधारी निर्णय आरेख ]] (BDD) या सम-ऑफ-प्रोडक्ट (ΣoΠ) फॉर्म की तुलना में एक कुशल प्रतिनिधित्व बनाता है।{{citation needed|date=July 2014}} अर्थात्, [[बूलियन बीजगणित (तर्क)]] में [[विहित रूप (बूलियन बीजगणित)]] जिसे वियोगात्मक सामान्य रूप (DNF) के रूप में जाना जाता है। बीडीडी और डीएनएफ को सर्किट के रूप में भी देखा जा सकता है, लेकिन उनमें औपचारिक बाधाएं शामिल हैं जो उन्हें मापनीयता से वंचित करती हैं। उदाहरण के लिए, ΣoΠ अधिकतम दो स्तरों वाले सर्किट होते हैं, जबकि BDD विहित होते हैं, अर्थात, उन्हें सभी पथों पर एक ही क्रम में इनपुट चर का मूल्यांकन करने की आवश्यकता होती है।


एआईजी समेत सरल गेट्स से बना सर्किट एक प्राचीन शोध विषय है। एआईजी में रुचि की शुरुआत एलन ट्यूरिंग के मौलिक 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> तंत्रिका नेटवर्क पर, जिसमें उन्होंने नंद द्वारों के यादृच्छिक प्रशिक्षित नेटवर्क का वर्णन किया। रुचि 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> जो क्षेत्र में सुधार के लिए सर्किट को कम करते हैं और संश्लेषण के दौरान देरी करते हैं, या [[औपचारिक तुल्यता जाँच]] को गति देते हैं। [[आईबीएम]] में कई महत्वपूर्ण तकनीकों की खोज की गई थी, जैसे बहु-इनपुट लॉजिक एक्सप्रेशन और सबएक्सप्रेशन का संयोजन और पुन: उपयोग करना, जिसे अब [[संरचनात्मक हैशिंग]] के रूप में जाना जाता है।
तर्क संश्लेषण और सत्यापन प्रणाली, जैसे डारिंगर एट अल।<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) अपने कई अनुप्रयोगों में मापनीयता की अपनी सीमा तक पहुँच चुके हैं।{{citation needed|date=July 2014}} एक अन्य महत्वपूर्ण विकास बहुत अधिक कुशल [[बूलियन संतुष्टि]] (एसएटी) सॉल्वरों का हालिया उद्भव था। सर्किट प्रतिनिधित्व के रूप में एआईजी के साथ युग्मित होने पर, वे विभिन्न प्रकार की [[बूलियन समस्या]]ओं को हल करने में उल्लेखनीय गति प्रदान करते हैं।{{citation needed|date=July 2014}}
हाल ही में संश्लेषण और सत्यापन में विभिन्न प्रकार के कार्यों के लिए [[कार्यात्मक प्रतिनिधित्व]] के रूप में एआईजी में नए सिरे से दिलचस्पी दिखाई गई है। ऐसा इसलिए है क्योंकि 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> मिशचेंको एट अल। दिखाता है कि एआईजी एक आशाजनक एकीकृत प्रतिनिधित्व है, जो [[तर्क संश्लेषण]], [[प्रौद्योगिकी मानचित्रण]], भौतिक संश्लेषण और औपचारिक सत्यापन को पाट सकता है। यह काफी हद तक एआईजी की सरल और समान संरचना के कारण है, जो समान डेटा संरचना को साझा करने के लिए पुनर्लेखन, सिमुलेशन, मैपिंग, प्लेसमेंट और सत्यापन की अनुमति देता है।
एआईजी को विविध [[ इलेक्ट्रॉनिक डिजाइन स्वचालन |इलेक्ट्रॉनिक डिजाइन स्वचालन]] अनुप्रयोगों में सफल उपयोग मिला। एआईजी और बूलियन संतुष्टि के सुव्यवस्थित संयोजन ने [[औपचारिक सत्यापन]] पर प्रभाव डाला, जिसमें मॉडल जाँच और तुल्यता जाँच दोनों शामिल हैं।<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>
जो सामान्य रूप से अज्ञात हो सकता है) जिसके परिणामस्वरूप डेटा संरचना होती है जो विशेष रूप से [[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://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 OpenAccess गियर]
* गिनी [http://godoc.org/github.com/go-air/gini/logic तर्क पुस्तकालय]
* गिनी [http://godoc.org/github.com/go-air/gini/logic तर्क पुस्तकालय]
Line 30: Line 29:


----
----
यह लेख ACM [http://www.sigda.org SIGDA] [https://web.archive.org/web/20070208034716/http://www.sigda.org/newsletter/index] के एक कॉलम से लिया गया है .html ई-न्यूज़लेटर] [http://www.eecs.berkeley.edu/~alanmi/ एलन मिशचेंको] द्वारा <br/> मूल पाठ उपलब्ध है [http://archive.sigda.org/newsletter/2006/060215 .txt यहाँ]।
यह लेख ACM [http://www.sigda.org SIGDA] [https://web.archive.org/web/20070208034716/http://www.sigda.org/newsletter/index] के कॉलम से लिया गया है .html ई-न्यूज़लेटर] [http://www.eecs.berkeley.edu/~alanmi/ एलन मिशचेंको] द्वारा <br/> मूल पाठ उपलब्ध है [http://archive.sigda.org/newsletter/2006/060215 .txt यहाँ]।


श्रेणी:अनुप्रयोग-विशिष्ट रेखांकन
श्रेणी:अनुप्रयोग-विशिष्ट रेखांकन

Revision as of 21:22, 4 March 2023

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

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

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

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

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

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

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

कार्यान्वयन

संदर्भ

  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=106986’