रिटिमिंग

रिटिमिंग डिजिटल परिपथ में लैच या रजिस्टरों के संरचनात्मक स्थान को स्थानांतरित करने की विधि होती है जिससे इसके प्रदर्शन, क्षेत्र, और/या शक्ति अनुकूलन विशेषताओं को इस तरह से सुधारा जा सकता है| कि इसके आउटपुट पर इसके कार्यात्मक व्यवहार को संरक्षित करता है। 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$