रिटिमिंग

रिटिमिंग डिजिटल परिपथ में लैच या रजिस्टरों के संरचनात्मक स्थान को स्थानांतरित करने की विधि होती है जिससे इसके प्रदर्शन, क्षेत्र, और/या शक्ति अनुकूलन विशेषताओं को इस तरह से सुधारा जा सकता है| कि इसके आउटपुट पर इसके कार्यात्मक व्यवहार को संरक्षित करता है। 1983 में चार्ल्स ई. लीजर्सन और जेम्स बी. सक्से द्वारा पहली बार रिटिमिंग का वर्णन किया गया था।

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

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

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

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

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

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

दिया गया	$w(e),W(u,v),D(u,v)$ और एक लक्ष्य समय अवधि $T$
खोज	$r(v):V\to \mathbb {Z}$
ऐसा है कि
	$r(u)-r(v)$	$\leq w(e)$
	$r(u)-r(v)$	$\leq W(u,v)-1$ if $D(u,v)>T$

मिल्प के साथ समय की अवधि को कम करना

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

दिया गया	$w(e),d(v)$ और एक लक्ष्य समय अवधि $T$
खोज	$r(v):V\to \mathbb {Z}$ and $R(v):V\to {\mathcal {R}}$
ऐसा है कि
	$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