अंर्तवर्तक ग्राफ

From Vigyanwiki

अंर्तवर्तक ग्राफ (एआईजी) ऐसे निर्देशित एसाइक्लिक ग्राफ (असतत गणित) होते हैं जो डिजिटल परिपथ की तार्किक कार्यक्षमता के संरचनात्मक कार्यान्वयन का प्रतिनिधित्व करते हैं। एआईजी में तार्किक संयोजन का प्रतिनिधित्व करने वाले दो-इनपुट नोड्स होते हैं, जिनके चर (वैरिेयेबल) के नामों के साथ लेबल किए गए टर्मिनल नोड्स, और किनारों पर उपस्थित वैकल्पिक प्रकारों से मार्क किया जाता हैं जो तार्किक 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=108962’