Retiming - Retiming

Retiming je technika přesunu strukturálního umístění západky nebo se registruje v a digitální obvod zlepšit jeho výkon, oblast a / nebo Napájení charakteristiky takovým způsobem, aby byla zachována jeho funkční chování na jejích výstupech. Retiming poprvé popsal Charles E. Leiserson a James B. Saxe v roce 1983.^[1]

Tato technika používá a řízený graf kde vrcholy představují asynchronní kombinační bloky a směrované hrany představují řadu registrů nebo západek (počet registrů nebo západek může být nula). Každý vrchol má hodnotu odpovídající zpoždění kombinačním obvodem, který představuje. Poté se můžete pokusit optimalizovat obvod tlačením registrů z výstupu na vstup a naopak - podobně tlačení bublin. Lze použít dvě operace - odstranění registru z každého vstupu vrcholu při přidávání registru ke všem výstupům a naopak přidání registru ke každému vstupu vrcholu a odstranění registru ze všech výstupů. Ve všech případech, pokud budou pravidla dodržena, bude mít obvod stejné funkční chování jako před změnou času.

Formální popis

Počáteční formulace problému s retimováním, jak ji popsali Leiserson a Saxe, je následující. Vzhledem k řízený graf ${displaystyle G: = (V, E)}$ jehož vrcholy představují logické brány nebo kombinační zpožďovací prvky v obvodu, předpokládejme, že existuje směrovaná hrana ${displaystyle e: = (u, v)}$ mezi dvěma prvky, které jsou připojeny přímo nebo prostřednictvím jednoho nebo více registrů. Nech hmotnost každé hrany ${displaystyle w (e)}$ být počet registrů přítomných podél okraje ${displaystyle e}$ v počátečním obvodu. Nechat ${displaystyle d (v)}$ být šíření zpoždění skrz vrchol ${displaystyle v}$ . Cílem retimingu je spočítat celé číslo zpoždění hodnota ${displaystyle r (v)}$ pro každý vrchol takový, že vyřazená váha ${displaystyle w_ {r} (e): = w (e) + r (v) -r (u)}$ každá hrana je nezáporná. Existuje důkaz, že se tím zachová výstupní funkce.^[2]

Minimalizace doby hodin s tokem sítě

Nejběžnějším použitím retimingu je minimalizace hodiny. Jednoduchou technikou pro optimalizaci periody hodin je hledání minimální proveditelné periody (např. Pomocí binární vyhledávání ).

Proveditelnost hodinového období ${displaystyle T}$ lze zkontrolovat jedním z několika způsobů. The lineární program níže je proveditelné právě tehdy ${displaystyle T}$ je proveditelné časové období. Nechat ${displaystyle W (u, v)}$ být minimální počet registrů na libovolné cestě z ${displaystyle u}$ na ${displaystyle v}$ (pokud taková cesta existuje) a ${displaystyle D (u, v)}$ je maximální zpoždění na jakékoli cestě z ${displaystyle u}$ na ${displaystyle v}$ s registry W (u, v). Duál tohoto programu je a problém s minimálními náklady na oběh, které lze efektivně vyřešit jako problém se sítí. Omezení tohoto přístupu vyplývají z výčtu a velikosti souboru ${displaystyle W}$ a ${displaystyle D}$ matice.

Dáno	${displaystyle w (e), W (u, v), D (u, v)}$ a období cílového času ${displaystyle T}$
Nalézt	${displaystyle r (v): V o mathbb {Z}}$
Takový
	${displaystyle r (u) -r (v)}$	${displaystyle leq w (e)}$
	${displaystyle r (u) -r (v)}$	${displaystyle leq W (u, v) -1}$ -li ${displaystyle D (u, v)> T}$

Minimalizace doby hodin pomocí MILP

Alternativně proveditelnost hodinového období ${displaystyle T}$ lze vyjádřit jako smíšené celé číslo lineární program (MILP). Bude existovat řešení a platná funkce zpoždění ${displaystyle r (v)}$ budou vráceny, pouze pokud je lhůta proveditelná.

Dáno	${displaystyle w (e), d (v)}$ a období cílového času ${displaystyle T}$
Nalézt	${displaystyle r (v): V o mathbb {Z}}$ a ${displaystyle R (v): V o {mathcal {R}}}$
Takový
	${displaystyle r (v) -R (V)}$	${displaystyle leq -d (v) / T}$
	${displaystyle R (v) -r (v)}$	${displaystyle leq 1}$
	${displaystyle r (u) -r (v)}$	${displaystyle leq w (e)}$
	${displaystyle R (u) -R (v)}$	${displaystyle leq w (e) -d (v) / T}$

Další formulace a rozšíření

Alternativní formulace umožňují minimalizaci počtu registrů a minimalizaci počtu registrů při omezení zpoždění. Počáteční článek obsahuje rozšíření, která umožňují uvažovat o sdílení fanoušků a obecnější model zpoždění. Následující práce se zabývaly zahrnutím zpoždění registrů,^[3] modely zpoždění závislé na zatížení,^[3] a držet omezení.^[4]

Problémy

Retiming našel průmyslové využití, i když sporadické. Jeho primární nevýhodou je, že kódování stavu obvodu je zničeno, což podstatně ztěžuje ladění, testování a ověřování. Některé retimingy mohou také vyžadovat komplikovanou inicializační logiku, aby byl obvod spuštěn ve stejném počátečním stavu. A konečně, změny v topologii obvodu mají důsledky v dalších logických a fyzických krocích syntézy, které provedou designové uzavření obtížný.

Alternativy

Plánování zkosení hodin je související technika pro optimalizaci sekvenčních obvodů. Zatímco retiming přemisťuje strukturální polohu registrů, plánování zkosení hodin posune jejich časovou polohu naplánováním času příjezdu hodinových signálů. Dolní mez dosažitelné minimální doby periody obou technik je maximální střední doba cyklu (tj. Celkové kombinační zpoždění podél libovolné cesty dělené počtem registrů podél ní).

Viz také

Poznámky

^ Charles E. Leiserson, Flavio M. Rose, James B. Saxe (1983). Msgstr "Optimalizace synchronních obvodů retimováním". Třetí konference Caltech o integraci ve velkém měřítku. Springer: 87–116. doi:10.1007/978-3-642-95432-0_7.CS1 maint: více jmen: seznam autorů (odkaz)
^ Charles E. Leiserson James B. Saxe (červen 1991). "Retimování synchronních obvodů". Algorithmica. Springer. 6 (1): 5–35. doi:10.1007 / BF01759032.
^ ^A ^b K. N. Lalgudi, M. C. Papaefthymiou, Retimování obvodů spouštěných hranou u obecných modelů zpoždění, Transakce IEEE na počítačově podporovaném návrhu integrovaných obvodů a systémů, sv. 16, č. 12, str. 1393-1408, prosinec 1997.
^ M. C. Papaefthymiou, Asymptoticky efektivní retimování v rámci nastavení a omezení omezení, IEEE / ACM International Conference on Computer-Aided Design, 1998.

Reference

Leiserson, 1C. E.; Saxe, J. B. (1983). "Optimalizace synchronních systémů". Journal of VLSI and Computer Systems. 1 (1): 41–67.

externí odkazy

[1] Charles E. Leiserson, Flavio M. Rose, James B. Saxe (1983). Msgstr "Optimalizace synchronních obvodů retimováním". Třetí konference Caltech o integraci ve velkém měřítku. Springer: 87–116. doi:10.1007/978-3-642-95432-0_7.CS1 maint: více jmen: seznam autorů (odkaz)

[one-2] Charles E. Leiserson James B. Saxe (červen 1991). "Retimování synchronních obvodů". Algorithmica. Springer. 6 (1): 5–35. doi:10.1007 / BF01759032.

[two-3] A ^b K. N. Lalgudi, M. C. Papaefthymiou, Retimování obvodů spouštěných hranou u obecných modelů zpoždění, Transakce IEEE na počítačově podporovaném návrhu integrovaných obvodů a systémů, sv. 16, č. 12, str. 1393-1408, prosinec 1997.

[three-4] M. C. Papaefthymiou, Asymptoticky efektivní retimování v rámci nastavení a omezení omezení, IEEE / ACM International Conference on Computer-Aided Design, 1998.

[1]

[2]

[3]

[4]