रिटिमिंग

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

औपचारिक विवरण

लीज़रसन और सक्से द्वारा वर्णित रेटिमिंग समस्या का प्रारंभिक सूत्रीकरण इस प्रकार है। एक निर्देशित ग्राफ दिया $G:=(V,E)$ जिनके शीर्ष सर्किट में तर्क द्वार या संयोजन विलंब तत्वों का प्रतिनिधित्व करते हैं, मान लें कि एक निर्देशित किनारा है $e:=(u,v)$ दो तत्वों के बीच जो सीधे या एक या अधिक रजिस्टरों के माध्यम से जुड़े हुए हैं। प्रत्येक किनारे का वजन होने दें $w(e)$ किनारे पर मौजूद रजिस्टरों की संख्या हो $e$ प्रारंभिक सर्किट में। होने देना $d(v)$ वर्टेक्स के माध्यम से प्रसार विलंब हो $v$. रिटिमिंग में लक्ष्य पूर्णांक लैग मान की गणना करना है $r(v)$ प्रत्येक शीर्ष के लिए जैसे कि retimed वजन $w_{r}(e):=w(e)+r(v)-r(u)$ हर किनारे का गैर-नकारात्मक है। एक प्रमाण है कि यह आउटपुट कार्यक्षमता को संरक्षित करता है।

नेटवर्क प्रवाह के साथ घड़ी की अवधि को कम करना

घड़ी की अवधि को कम करने के लिए रेटिमिंग का सबसे आम उपयोग है। घड़ी की अवधि को अनुकूलित करने की एक सरल तकनीक न्यूनतम व्यवहार्य अवधि (उदाहरण के लिए बाइनरी खोज का उपयोग करके) की खोज करना है।

एक घड़ी अवधि की व्यवहार्यता $T$ कई तरीकों में से एक में जाँच की जा सकती है। नीचे दिया गया रेखीय कार्यक्रम संभव है अगर और केवल अगर $T$ एक व्यवहार्य घड़ी अवधि है। होने देना $W(u,v)$ से किसी भी पथ के साथ रजिस्टरों की न्यूनतम संख्या हो $u$ को $v$ (यदि ऐसा पथ मौजूद है), और $D(u,v)$ से किसी पथ पर अधिकतम विलंब है $u$ को $v$ डब्ल्यू (यू, वी) रजिस्टरों के साथ। इस कार्यक्रम की दोहरी एक न्यूनतम लागत संचलन समस्या है, जिसे नेटवर्क समस्या के रूप में कुशलता से हल किया जा सकता है। इस दृष्टिकोण की सीमाएं गणना और आकार से उत्पन्न होती हैं $W$ और $D$ मैट्रिक्स।

Given	$w(e),W(u,v),D(u,v)$ and a target clock period $T$
Find	$r(v):V\to \mathbb {Z}$
Such that
	$r(u)-r(v)$	$\leq w(e)$
	$r(u)-r(v)$	$\leq W(u,v)-1$ if $D(u,v)>T$

=== MILP === के साथ घड़ी की अवधि को कम करना

वैकल्पिक रूप से, घड़ी की अवधि की व्यवहार्यता $T$ मिश्रित-पूर्णांक रैखिक कार्यक्रम (MILP) के रूप में व्यक्त किया जा सकता है। एक समाधान मौजूद होगा और एक वैध अंतराल समारोह होगा $r(v)$ अगर और केवल अगर अवधि संभव है तो वापस कर दिया जाएगा।

Given	$w(e),d(v)$ and a target clock period $T$
Find	$r(v):V\to \mathbb {Z}$ and $R(v):V\to {\mathcal {R}}$
Such that
	$r(v)-R(V)$	$\leq -d(v)/T$
	$R(v)-r(v)$	$\leq 1$
	$r(u)-r(v)$	$\leq w(e)$
	$R(u)-R(v)$	$\leq w(e)-d(v)/T$

अन्य फॉर्मूलेशन और एक्सटेंशन

वैकल्पिक फॉर्मूलेशन रजिस्टर गिनती को कम करने और देरी की बाधा के तहत रजिस्टर गिनती को कम करने की अनुमति देता है। प्रारंभिक पेपर में ऐसे एक्सटेंशन शामिल हैं जो फैन-आउट शेयरिंग और अधिक सामान्य विलंब मॉडल पर विचार करने की अनुमति देते हैं। बाद के काम ने रजिस्टर में देरी को शामिल करने पर ध्यान दिया है, लोड पर निर्भर विलंब मॉडल,और बाधाओं को पकड़ो।

समस्याएं

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

विकल्प

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

यह भी देखें

• तर्क संश्लेषण
• इलेक्ट्रॉनिक डिजाइन स्वचालन

संदर्भ

• Leiserson, 1C. E.; Saxe, J. B. (1983). "Optimizing Synchronous Systems". Journal of VLSI and Computer Systems. 1 (1): 41–67.

बाहरी संबंध

• Presentation on retiming from MIT
• A Safe and Complete Gate-Level Register Retiming Algorithm