रिटिमिंग: 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>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> प्रत्येक शीर्ष के लिए जैसे कि retimed वजन <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> | ||
| Line 10: | Line 11: | ||
=== नेटवर्क प्रवाह के साथ [[घड़ी की अवधि]] को कम करना === | === नेटवर्क प्रवाह के साथ [[घड़ी की अवधि]] को कम करना === | ||
घड़ी की अवधि को कम करने के लिए रेटिमिंग का सबसे आम उपयोग है। घड़ी की अवधि को अनुकूलित करने की एक सरल | घड़ी की अवधि को कम करने के लिए रेटिमिंग का सबसे आम उपयोग है। घड़ी की अवधि को अनुकूलित करने की एक सरल विधि न्यूनतम व्यवहार्य अवधि (उदाहरण के लिए बाइनरी खोज का उपयोग करके) की खोज करना है। | ||
एक घड़ी अवधि की व्यवहार्यता <math>T</math> कई | एक घड़ी अवधि की व्यवहार्यता <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 35: | Line 36: | ||
=== MILP === के साथ घड़ी की अवधि को कम करना | === MILP === के साथ घड़ी की अवधि को कम करना | ||
वैकल्पिक रूप से, घड़ी की अवधि की व्यवहार्यता <math>T</math> मिश्रित-पूर्णांक रैखिक कार्यक्रम (MILP) के रूप में व्यक्त किया जा सकता है। एक समाधान | वैकल्पिक रूप से, घड़ी की अवधि की व्यवहार्यता <math>T</math> मिश्रित-पूर्णांक रैखिक कार्यक्रम (MILP) के रूप में व्यक्त किया जा सकता है। एक समाधान उपस्थित होगा और एक वैध अंतराल फलन होगा <math>r(v)</math> यदि और केवल यदि अवधि संभव है तो वापस कर दिया जाएगा। | ||
{| | {| | ||
| Line 66: | Line 67: | ||
=== अन्य फॉर्मूलेशन और एक्सटेंशन === | === अन्य फॉर्मूलेशन और एक्सटेंशन === | ||
वैकल्पिक फॉर्मूलेशन रजिस्टर गिनती को कम करने और देरी की बाधा के | वैकल्पिक फॉर्मूलेशन रजिस्टर गिनती को कम करने और देरी की बाधा के अनुसार रजिस्टर गिनती को कम करने की अनुमति देता है। प्रारंभिक पेपर में ऐसे एक्सटेंशन सम्मिलित हैं जो फैन-आउट शेयरिंग और अधिक सामान्य विलंब मॉडल पर विचार करने की अनुमति देते हैं। बाद के काम ने रजिस्टर में देरी को सम्मिलित करने पर ध्यान दिया है,<ref name="two">K. N. Lalgudi, M. C. Papaefthymiou, {{doi-inline|10.1109/43.664222|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.</ref> लोड पर निर्भर विलंब मॉडल,<ref name="two"/>और बाधाओं को पकड़ो।<ref name="three">M. C. Papaefthymiou, {{doi-inline|10.1145/288548.289060|Asymptotically efficient retiming under setup and hold constraints}}, IEEE/ACM International Conference on Computer-Aided Design, 1998.</ref> | ||
== समस्याएं == | == समस्याएं == | ||
छिटपुट यद्यपि, रिटिमिंग का औद्योगिक उपयोग हुआ है। इसका प्राथमिक दोष यह है कि | छिटपुट यद्यपि, रिटिमिंग का औद्योगिक उपयोग हुआ है। इसका प्राथमिक दोष यह है कि परिपथ का स्टेट एन्कोडिंग नष्ट हो जाता है, डिबगिंग, परीक्षण और सत्यापन को और अधिक कठिन बना देता है। परिपथ को एक समान प्रारंभिक अवस्था में प्रारंभिक करने के लिए कुछ रेटिमिंग्स को जटिल प्रारंभिक तर्क की आवश्यकता हो सकती है। अंत में, परिपथ की टोपोलॉजी में परिवर्तन के परिणाम अन्य तार्किक और भौतिक संश्लेषण चरणों में होते हैं जो [[डिजाइन बंद]] बंद करना कठिनाई बनाते हैं। | ||
== विकल्प == | == विकल्प == | ||
क्लॉक स्कू शेड्यूलिंग अनुक्रमिक | क्लॉक स्कू शेड्यूलिंग अनुक्रमिक परिपथ को अनुकूलित करने के लिए एक संबंधित विधि है। जबकि रिटिमिंग रजिस्टरों की संरचनात्मक स्थिति को स्थानांतरित करता है, क्लॉक स्क्यू शेड्यूलिंग क्लॉक सिग्नल के आगमन समय को निर्धारित करके उनकी अस्थायी स्थिति को स्थानांतरित करता है। दोनों विधि ों की प्राप्त करने योग्य न्यूनतम घड़ी अवधि की निचली सीमा अधिकतम औसत चक्र समय है (अर्थात किसी भी पथ के साथ कुल संयोजन विलंब इसके साथ रजिस्टरों की संख्या से विभाजित)। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 15:39, 4 March 2023
रिटिमिंग एक डिजिटल परिपथ में कुंडी (इलेक्ट्रॉनिक) या रजिस्टरों के संरचनात्मक स्थान को स्थानांतरित करने की विधि है जिससे इसके प्रदर्शन, क्षेत्र, और/या शक्ति अनुकूलन (EDA)ईडीए) विशेषताओं को इस तरह से सुधारा जा सके कि इसके आउटपुट पर इसके कार्यात्मक व्यवहार को संरक्षित किया जा सके। रेटिमिंग को पहली बार 1983 में चार्ल्स ई। लीजरसन और जेम्स बी सक्से द्वारा वर्णित किया गया था।[1]
विधि एक निर्देशित ग्राफ का उपयोग करती है जहां शिखर अतुल्यकालिक संयोजन ब्लॉकों का प्रतिनिधित्व करते हैं और निर्देशित किनारे रजिस्टरों या लैच की एक श्रृंखला का प्रतिनिधित्व करते हैं (रजिस्टरों या लैच की संख्या शून्य हो सकती है)। प्रत्येक शीर्ष का एक मान होता है जो संयोजन परिपथ के माध्यम से विलंब का प्रतिनिधित्व करता है। ऐसा करने के बाद, आउटपुट से इनपुट तक रजिस्टरों को पुश करके परिपथ को अनुकूलित करने का प्रयास कर सकते हैं और इसके विपरीत - बुलबुला धक्का की तरह। दो ऑपरेशनों का उपयोग किया जा सकता है - सभी आउटपुट में एक रजिस्टर जोड़ते समय एक वर्टेक्स के प्रत्येक इनपुट से एक रजिस्टर को हटाना, और इसके विपरीत वर्टेक्स के प्रत्येक इनपुट में एक रजिस्टर जोड़ना और सभी आउटपुट से एक रजिस्टर को हटाना। सभी स्थितियों में, यदि नियमों का पालन किया जाता है, तो परिपथ का वही कार्यात्मक व्यवहार होगा जैसा कि रेटिमिंग से पहले था।
औपचारिक विवरण
लीज़रसन और सक्से द्वारा वर्णित रेटिमिंग समस्या का प्रारंभिक सूत्रीकरण इस प्रकार है। एक निर्देशित ग्राफ दिया जिनके शीर्ष परिपथ में तर्क द्वार या संयोजन विलंब तत्वों का प्रतिनिधित्व करते हैं, मान लें कि एक निर्देशित किनारा है दो तत्वों के बीच जो सीधे या एक या अधिक रजिस्टरों के माध्यम से जुड़े हुए हैं। प्रत्येक किनारे का वजन होने दें किनारे पर उपस्थित रजिस्टरों की संख्या हो प्रारंभिक परिपथ में। होने देना वर्टेक्स के माध्यम से प्रसार विलंब हो . रिटिमिंग में लक्ष्य पूर्णांक लैग मान की गणना करना है प्रत्येक शीर्ष के लिए जैसे कि retimed वजन हर किनारे का गैर-नकारात्मक है। एक प्रमाण है कि यह आउटपुट कार्यक्षमता को संरक्षित करता है।[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.
