रिटिमिंग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
रिटिमिंग एक [[डिजिटल सर्किट|डिजिटल परिपथ]] में | रिटिमिंग एक [[डिजिटल सर्किट|डिजिटल परिपथ]] में लैच या रजिस्टरों के संरचनात्मक स्थान को स्थानांतरित करने की विधि है जिससे इसके प्रदर्शन, क्षेत्र, और/या [[शक्ति अनुकूलन (EDA)|शक्ति अनुकूलन]] विशेषताओं को इस तरह से सुधारा जा सके कि इसके आउटपुट पर इसके कार्यात्मक व्यवहार को संरक्षित करता है। 1983 में चार्ल्स ई. लीजर्सन और जेम्स बी. सक्से द्वारा पहली बार रिटिमिंग का वर्णन किया गया था।<ref>{{cite journal|journal= Third Caltech Conference on Very Large Scale Integration|publisher=Springer|title=रिटिमिंग द्वारा सिंक्रोनस सर्किटरी का अनुकूलन|author=Charles E. Leiserson, Flavio M. Rose, JamesB. Saxe|date=1983|page=87–116|doi=10.1007/978-3-642-95432-0_7}}</ref> | ||
विधि एक [[निर्देशित ग्राफ]] का उपयोग करती है जहां शिखर अतुल्यकालिक संयोजन ब्लॉकों का प्रतिनिधित्व करते हैं और निर्देशित किनारे रजिस्टरों या लैच की एक श्रृंखला का प्रतिनिधित्व करते हैं (रजिस्टरों या लैच की संख्या शून्य हो सकती है)। प्रत्येक शीर्ष का | विधि एक [[निर्देशित ग्राफ]] का उपयोग करती है जहां शिखर अतुल्यकालिक संयोजन ब्लॉकों का प्रतिनिधित्व करते हैं और निर्देशित किनारे रजिस्टरों या लैच की एक श्रृंखला का प्रतिनिधित्व करते हैं (रजिस्टरों या लैच की संख्या शून्य हो सकती है)। प्रत्येक शीर्ष का मान होता है जो संयोजन परिपथ के माध्यम से विलंब का प्रतिनिधित्व करता है। ऐसा करने के बाद, आउटपुट से इनपुट तक रजिस्टरों को धक्का देकर परिपथ को अनुकूलित करने का प्रयास कर सकते हैं और इसके विपरीत - [[ बुलबुला धक्का | बबल पुशिंग]] की तरह। दो ऑपरेशनों का उपयोग किया जा सकता है - सभी आउटपुट में एक रजिस्टर जोड़ते समय एक वर्टेक्स के प्रत्येक इनपुट से एक रजिस्टर को हटाना, और इसके विपरीत वर्टेक्स के प्रत्येक इनपुट में एक रजिस्टर जोड़ना और सभी आउटपुट से एक रजिस्टर को हटाना। सभी स्थितियों में, यदि नियमों का पालन किया जाता है, तो परिपथ का वही कार्यात्मक व्यवहार होगा जैसा कि रेटिमिंग से पहले था। | ||
== औपचारिक विवरण == | == औपचारिक विवरण == | ||
लीज़रसन और सक्से द्वारा वर्णित रेटिमिंग समस्या का प्रारंभिक सूत्रीकरण इस प्रकार है। एक निर्देशित ग्राफ | लीज़रसन और सक्से द्वारा वर्णित रेटिमिंग समस्या का प्रारंभिक सूत्रीकरण इस प्रकार है। एक निर्देशित ग्राफ <math>G:=(V,E)</math> दिया गया है| जिनके शीर्ष परिपथ में [[ तर्क द्वार |लॉजिक गेट्स]] या संयोजन विलंब तत्वों का प्रतिनिधित्व करते हैं, मान लें कि सीधे जुड़े हुए दो तत्वों के बीच एक निर्देशित किनारा <math>e:=(u,v)</math> है एक या अधिक रजिस्टरों के माध्यम से जुड़े हुए हैं। प्रत्येक किनारे का वजन <math>w(e)</math> प्रारंभिक परिपथ किनारे <math>e</math> के साथ उपस्थित रजिस्टरों की संख्या होने दें। <math>d(v)</math> वर्टेक्स <math>v</math>. के माध्यम से प्रसार विलंब हो रिटिमिंग में लक्ष्य पूर्णांक लैग मान की गणना करना है <math>r(v)</math> प्रत्येक शीर्ष के लिए जैसे कि रेटिमेड वजन <math>w_r(e):=w(e)+r(v)-r(u)</math> हर किनारे का गैर-नकारात्मक है। एक प्रमाण है कि यह आउटपुट कार्यक्षमता को संरक्षित करता है।<ref name="one">{{cite journal|title=Retiming synchronous circuitry | ||
|date=June 1991|journal=Algorithmica|publisher=Springer|author=Charles E. LeisersonJames B. Saxe |volume=6|number=1|page=5–35|doi=10.1007/BF01759032|s2cid=18674287 }}</ref> | |date=June 1991|journal=Algorithmica|publisher=Springer|author=Charles E. LeisersonJames B. Saxe |volume=6|number=1|page=5–35|doi=10.1007/BF01759032|s2cid=18674287 }}</ref> | ||
=== नेटवर्क प्रवाह के साथ [[घड़ी की अवधि|समय की अवधि]] को कम करना === | |||
समय की अवधि को कम करने के लिए रेटिमिंग का सबसे आम उपयोग है। समय की अवधि को अनुकूलित करने की एक सरल विधि न्यूनतम व्यवहार्य अवधि (उदाहरण के लिए बाइनरी खोज का उपयोग करके) की खोज करना है। | |||
एक समय अवधि की व्यवहार्यता <math>T</math> कई विधि में से एक में जाँच की जा सकती है। नीचे दिया गया रेखीय कार्यक्रम संभव है यदि और केवल यदि <math>T</math> एक व्यवहार्य समय अवधि है। होने देना <math>W(u,v)</math> से किसी भी पथ के साथ रजिस्टरों की न्यूनतम संख्या हो <math>u</math> को <math>v</math> (यदि ऐसा पथ उपस्थित है), और <math>D(u,v)</math> से किसी पथ पर अधिकतम विलंब है <math>u</math> को <math>v</math> डब्ल्यू (यू, वी) रजिस्टरों के साथ। इस कार्यक्रम की दोहरी एक [[न्यूनतम लागत संचलन समस्या|न्यूनतम निवेश संचलन समस्या]] है, जिसे नेटवर्क समस्या के रूप में कुशलता से हल किया जा सकता है। इस दृष्टिकोण की सीमाएं गणना और आकार से उत्पन्न होती हैं <math>W</math> और <math>D</math> मैट्रिक्स। | |||
एक | |||
{| | {| | ||
| Line 34: | Line 32: | ||
वैकल्पिक रूप से, | MILP के साथ समय की अवधि को कम करना | ||
वैकल्पिक रूप से, समय की अवधि की व्यवहार्यता <math>T</math> मिश्रित-पूर्णांक रैखिक कार्यक्रम (MILP) के रूप में व्यक्त किया जा सकता है। एक समाधान उपस्थित होगा और एक वैध अंतराल फलन होगा <math>r(v)</math> यदि और केवल यदि अवधि संभव है तो वापस कर दिया जाएगा। | |||
{| | {| | ||
| Line 76: | Line 75: | ||
== विकल्प == | == विकल्प == | ||
क्लॉक स्कू शेड्यूलिंग अनुक्रमिक परिपथ को अनुकूलित करने के लिए एक संबंधित विधि है। जबकि रिटिमिंग रजिस्टरों की संरचनात्मक स्थिति को स्थानांतरित करता है, क्लॉक स्क्यू शेड्यूलिंग क्लॉक सिग्नल के आगमन समय को निर्धारित करके उनकी अस्थायी स्थिति को स्थानांतरित करता है। दोनों विधि ों की प्राप्त करने योग्य न्यूनतम | क्लॉक स्कू शेड्यूलिंग अनुक्रमिक परिपथ को अनुकूलित करने के लिए एक संबंधित विधि है। जबकि रिटिमिंग रजिस्टरों की संरचनात्मक स्थिति को स्थानांतरित करता है, क्लॉक स्क्यू शेड्यूलिंग क्लॉक सिग्नल के आगमन समय को निर्धारित करके उनकी अस्थायी स्थिति को स्थानांतरित करता है। दोनों विधि ों की प्राप्त करने योग्य न्यूनतम समय अवधि की निचली सीमा अधिकतम औसत चक्र समय है (अर्थात किसी भी पथ के साथ कुल संयोजन विलंब इसके साथ रजिस्टरों की संख्या से विभाजित)। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 16:15, 4 March 2023
रिटिमिंग एक डिजिटल परिपथ में लैच या रजिस्टरों के संरचनात्मक स्थान को स्थानांतरित करने की विधि है जिससे इसके प्रदर्शन, क्षेत्र, और/या शक्ति अनुकूलन विशेषताओं को इस तरह से सुधारा जा सके कि इसके आउटपुट पर इसके कार्यात्मक व्यवहार को संरक्षित करता है। 1983 में चार्ल्स ई. लीजर्सन और जेम्स बी. सक्से द्वारा पहली बार रिटिमिंग का वर्णन किया गया था।[1]
विधि एक निर्देशित ग्राफ का उपयोग करती है जहां शिखर अतुल्यकालिक संयोजन ब्लॉकों का प्रतिनिधित्व करते हैं और निर्देशित किनारे रजिस्टरों या लैच की एक श्रृंखला का प्रतिनिधित्व करते हैं (रजिस्टरों या लैच की संख्या शून्य हो सकती है)। प्रत्येक शीर्ष का मान होता है जो संयोजन परिपथ के माध्यम से विलंब का प्रतिनिधित्व करता है। ऐसा करने के बाद, आउटपुट से इनपुट तक रजिस्टरों को धक्का देकर परिपथ को अनुकूलित करने का प्रयास कर सकते हैं और इसके विपरीत - बबल पुशिंग की तरह। दो ऑपरेशनों का उपयोग किया जा सकता है - सभी आउटपुट में एक रजिस्टर जोड़ते समय एक वर्टेक्स के प्रत्येक इनपुट से एक रजिस्टर को हटाना, और इसके विपरीत वर्टेक्स के प्रत्येक इनपुट में एक रजिस्टर जोड़ना और सभी आउटपुट से एक रजिस्टर को हटाना। सभी स्थितियों में, यदि नियमों का पालन किया जाता है, तो परिपथ का वही कार्यात्मक व्यवहार होगा जैसा कि रेटिमिंग से पहले था।
औपचारिक विवरण
लीज़रसन और सक्से द्वारा वर्णित रेटिमिंग समस्या का प्रारंभिक सूत्रीकरण इस प्रकार है। एक निर्देशित ग्राफ दिया गया है| जिनके शीर्ष परिपथ में लॉजिक गेट्स या संयोजन विलंब तत्वों का प्रतिनिधित्व करते हैं, मान लें कि सीधे जुड़े हुए दो तत्वों के बीच एक निर्देशित किनारा है एक या अधिक रजिस्टरों के माध्यम से जुड़े हुए हैं। प्रत्येक किनारे का वजन प्रारंभिक परिपथ किनारे के साथ उपस्थित रजिस्टरों की संख्या होने दें। वर्टेक्स . के माध्यम से प्रसार विलंब हो रिटिमिंग में लक्ष्य पूर्णांक लैग मान की गणना करना है प्रत्येक शीर्ष के लिए जैसे कि रेटिमेड वजन हर किनारे का गैर-नकारात्मक है। एक प्रमाण है कि यह आउटपुट कार्यक्षमता को संरक्षित करता है।[2]
नेटवर्क प्रवाह के साथ समय की अवधि को कम करना
समय की अवधि को कम करने के लिए रेटिमिंग का सबसे आम उपयोग है। समय की अवधि को अनुकूलित करने की एक सरल विधि न्यूनतम व्यवहार्य अवधि (उदाहरण के लिए बाइनरी खोज का उपयोग करके) की खोज करना है।
एक समय अवधि की व्यवहार्यता कई विधि में से एक में जाँच की जा सकती है। नीचे दिया गया रेखीय कार्यक्रम संभव है यदि और केवल यदि एक व्यवहार्य समय अवधि है। होने देना से किसी भी पथ के साथ रजिस्टरों की न्यूनतम संख्या हो को (यदि ऐसा पथ उपस्थित है), और से किसी पथ पर अधिकतम विलंब है को डब्ल्यू (यू, वी) रजिस्टरों के साथ। इस कार्यक्रम की दोहरी एक न्यूनतम निवेश संचलन समस्या है, जिसे नेटवर्क समस्या के रूप में कुशलता से हल किया जा सकता है। इस दृष्टिकोण की सीमाएं गणना और आकार से उत्पन्न होती हैं और मैट्रिक्स।
| Given | and a target clock period | |
| Find | ||
| Such that | ||
| if | ||
MILP के साथ समय की अवधि को कम करना
वैकल्पिक रूप से, समय की अवधि की व्यवहार्यता मिश्रित-पूर्णांक रैखिक कार्यक्रम (MILP) के रूप में व्यक्त किया जा सकता है। एक समाधान उपस्थित होगा और एक वैध अंतराल फलन होगा यदि और केवल यदि अवधि संभव है तो वापस कर दिया जाएगा।
| Given | and a target clock period | |
| Find | and | |
| Such that | ||
अन्य फॉर्मूलेशन और एक्सटेंशन
वैकल्पिक फॉर्मूलेशन रजिस्टर गिनती को कम करने और देरी की बाधा के अनुसार रजिस्टर गिनती को कम करने की अनुमति देता है। प्रारंभिक पेपर में ऐसे एक्सटेंशन सम्मिलित हैं जो फैन-आउट शेयरिंग और अधिक सामान्य विलंब मॉडल पर विचार करने की अनुमति देते हैं। बाद के काम ने रजिस्टर में देरी को सम्मिलित करने पर ध्यान दिया है,[3] लोड पर निर्भर विलंब मॉडल,[3]और बाधाओं को पकड़ो।[4]
समस्याएं
छिटपुट यद्यपि, रिटिमिंग का औद्योगिक उपयोग हुआ है। इसका प्राथमिक दोष यह है कि परिपथ का स्टेट एन्कोडिंग नष्ट हो जाता है, डिबगिंग, परीक्षण और सत्यापन को और अधिक कठिन बना देता है। परिपथ को एक समान प्रारंभिक अवस्था में प्रारंभिक करने के लिए कुछ रेटिमिंग्स को जटिल प्रारंभिक तर्क की आवश्यकता हो सकती है। अंत में, परिपथ की टोपोलॉजी में परिवर्तन के परिणाम अन्य तार्किक और भौतिक संश्लेषण चरणों में होते हैं जो डिजाइन बंद बंद करना कठिनाई बनाते हैं।
विकल्प
क्लॉक स्कू शेड्यूलिंग अनुक्रमिक परिपथ को अनुकूलित करने के लिए एक संबंधित विधि है। जबकि रिटिमिंग रजिस्टरों की संरचनात्मक स्थिति को स्थानांतरित करता है, क्लॉक स्क्यू शेड्यूलिंग क्लॉक सिग्नल के आगमन समय को निर्धारित करके उनकी अस्थायी स्थिति को स्थानांतरित करता है। दोनों विधि ों की प्राप्त करने योग्य न्यूनतम समय अवधि की निचली सीमा अधिकतम औसत चक्र समय है (अर्थात किसी भी पथ के साथ कुल संयोजन विलंब इसके साथ रजिस्टरों की संख्या से विभाजित)।
यह भी देखें
टिप्पणियाँ
- ↑ Charles E. Leiserson, Flavio M. Rose, JamesB. Saxe (1983). "रिटिमिंग द्वारा सिंक्रोनस सर्किटरी का अनुकूलन". Third Caltech Conference on Very Large Scale Integration. Springer: 87–116. doi:10.1007/978-3-642-95432-0_7.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ↑ Charles E. LeisersonJames B. Saxe (June 1991). "Retiming synchronous circuitry". Algorithmica. Springer. 6 (1): 5–35. doi:10.1007/BF01759032. S2CID 18674287.
- ↑ 3.0 3.1 K. N. Lalgudi, M. C. Papaefthymiou, Retiming edge-triggered circuits under general delay models, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.16, no.12, pp.1393-1408, Dec. 1997.
- ↑ M. C. Papaefthymiou, Asymptotically efficient retiming under setup and hold constraints, IEEE/ACM International Conference on Computer-Aided Design, 1998.
संदर्भ
- Leiserson, 1C. E.; Saxe, J. B. (1983). "Optimizing Synchronous Systems". Journal of VLSI and Computer Systems. 1 (1): 41–67.
