Stavové kódování pro nízkou spotřebu - State encoding for low power

Kódování stavu přiřadí každému definovanému stavu stroje s konečným stavem (FSM) jedinečný vzor jedniček a nul . Kritéria návrhu pro syntézu FSM byla tradičně rychlost, plocha nebo obojí. V souladu s Moorovým zákonem se s technologickým pokrokem exponenciálně zvýšila hustota a rychlost integrovaných obvodů. Tím se nevyhnutelně zvýšil ztrátový výkon na oblast, což donutilo designéry přenosných výpočetních zařízení a vysokorychlostních procesorů, aby při zvažování návrhu považovali ztrátový výkon za kritický parametr.

Pozadí

Syntéza FSM zahrnuje tři hlavní kroky:

  1. Minimalizace stavu: Jak název napovídá, počet států potřebných k reprezentaci FSM je minimalizován. Různé techniky a algoritmy, jako jsou implikační tabulky , shoda řádků, postupný algoritmus dělení, identifikace a odstranění ekvivalentních nebo redundantních stavů.
  2. Přiřazení stavu nebo kódování zahrnuje výběr logických reprezentací vnitřních stavů FSM. Jinými slovy přiřadí každému státu jedinečný binární kód. Výběr správné techniky kódování je velmi kritický. Protože nesprávné rozhodnutí může mít za následek, že FSM používá příliš mnoho logické oblasti, je příliš pomalý nebo spotřebovává více energie nebo jakoukoli jejich kombinaci.
  3. Minimalizace kombinační logiky používá nepřiřazené stavové kódy jako péči, aby se snížila kombinační logika.

Stávající techniky kódování

Následují některé z technik, které se široce používají pro kódování stavu:

  • V jednom horkém kódování je pouze jeden z bitů stavové proměnné „1“ (horký) pro jakýkoli daný stav. Všechny ostatní bity jsou „0“. Hammingova vzdálenost z těchto technik je 2. Jeden hot vyžaduje jeden flip-flop pro každý stát ve FSM. Výsledkem je, že stavový stroj je již „dekódován“, takže stav stroje je určen jednoduše zjištěním, který klopný obvod je aktivní. Tato technika kódování zmenšuje šířku kombinatorické logiky a ve výsledku stavový stroj vyžaduje méně úrovní logiky mezi registry, snižuje jeho složitost a zvyšuje jeho rychlost.
  • V binárním kódování počet bitů (b) na stav závisí na počtu stavů (n). Vztah je definován rovnicí:
   b = log2(n)

V této technice jsou stavy přiřazeny v binární sekvenci, kde jsou stavy očíslovány počínaje binární 0 a vyšší. Je zřejmé, že počet použitých klopných obvodů se rovná počtu bitů (b). Vzhledem k tomu, že binární kódování používá k kódování stroje minimální počet bitů (klopné obvody), jsou klopné obvody maximálně využity. Ve výsledku je pro dekódování každého stavu ve srovnání s One Hot zapotřebí více kombinatorické logiky. Vyžaduje menší počet klopných obvodů ve srovnání s One hot, ale Hammingova vzdálenost může být stejně horší jako počet bitů (b).

V Grayově kódu, známém také jako odražený binární kód, jsou stavy přiřazeny tak, že po sobě jdoucí stavové kódy se liší pouze o jeden bit. V tomto kódování je také definován vztah mezi počtem bitů a počtem stavů 

   b = log2(n)

Počet použitých klopných obvodů a složitost dekódovací logiky je stejná jako u binárního kódování. Ale Hammingova vzdálenost v Gray kódu je vždy 1.

  • Další techniky kódování

Kódování založené na výstupu, MUSTANG, NOVA,

Motivace

Hlavní myšlenkou v návrhu kódování stavu pro nízký výkon je minimalizace Hammingovy vzdálenosti nejpravděpodobnějších přechodů stavu, což snižuje spínací aktivitu. Cenovým modelem pro minimalizaci spotřeby energie tedy je mít Hammingovu vzdálenost s minimální váhou (MWHD).

U čítačů poskytuje šedé kódování minimální spínací aktivitu, a proto je vhodné pro návrhy s nízkou spotřebou. Šedé kódování se hodí nejlépe, když jsou změny stavu postupné. Při libovolné změně stavu selže kód FSM Gray u návrhů s nízkou spotřebou. U takových FSM zaručuje jednosměrné kódování přepínání dvou bitů při každé změně stavu. Ale protože počet potřebných stavových proměnných se rovná počtu stavů, jak se stavy zvyšují, stává se kódování za horka nepraktickým řešením, hlavně proto, že se zvýšeným počtem vstupů a výstupů do obvodu se zvyšuje složitost a kapacitní zátěž. Binární kódování je nejhorší pro nízkou spotřebu, protože maximální Hammingova vzdálenost se rovná počtu stavových proměnných.

Potřeba mít řešení pro libovolnou změnu stavu FSM vedla k několika technikám kódování stavu, které se zaměřují na snížení přepínací aktivity během přechodů stavu.

Techniky

Sloupcový přístup pro přiřazování stavu nízké spotřeby

Tento přístup si klade za cíl snížit ztrátový výkon sekvenčními obvody výběrem přiřazení stavu, které minimalizuje přepínací aktivitu mezi přechody stavu. Kombinační část FSM má tedy nižší pravděpodobnost přechodu na vstup a spíše se jí líbí syntéza s nízkým rozptylem energie. Tento algoritmus používá booleovskou matici s řádky odpovídajícími stavovým kódům a sloupcem odpovídajícím stavovým proměnným. Proměnná s jedním stavem se zvažuje najednou a pokusí se přiřadit její hodnotu ke každému stavu ve FSM způsobem, který pravděpodobně minimalizuje přepínací aktivitu pro úplné přiřazení. Tento postup se opakuje pro další proměnnou. Vzhledem k tomu, že se metoda minimalizace používá sloupec po sloupci, tato technika se nazývá sloupcová.

Přiřazení stavu více kódů

Technika přiřazování stavů více kódů implementuje prioritní kódování omezením redundantních stavů. Stav lze tedy kódovat pomocí méně stavových proměnných (bitů). Dále mohou být klopné obvody odpovídající těmto nepřítomným stavovým proměnným hodinově blokovány.

Přiřazení stavu založené na profilování

Tato technika využívá informace dynamické smyčky extrahované z dat profilování FSM pro přiřazení stavu, aby se snížila aktivita přepínání. Následuje postup, který tato technika používá:

  1. Profilování stavu FSM shromažďuje informace o dynamickém chování FSM pro relevantní sadu vstupních dat
  2. Detekce smyčky vyhledá smyčky ve stopě stavu a každá smyčka se uloží a spočítá, aby se získala frekvence smyček.
  3. Přiřazení stavu přiřadí stavové proměnné každému stavu na základě dat shromážděných v prvních dvou krocích, aby se minimalizovala přepínací aktivita. Existují tři algoritmy pro přiřazení stavových proměnných,
  • Základní algoritmus přiřazení stavu DFS
  • Algoritmus přiřazení stavu DFS založený na smyčce
  • Smyčkový algoritmus přiřazení heuristického stavu podle stavu

Další techniky

  • Některé techniky kódují stavový přechodový graf (STG) k výrobě dvouúrovňových a víceúrovňových implementací zaměřených na nízkou spotřebu
  • Bylo navrženo překódování stávajících sekvenčních obvodů na logické úrovni pro optimalizaci výkonu
  • Kódování stavu na základě stromu, metoda Depth_First, metoda minimální vzdálenosti, metoda 1_Level, metoda 1_level_tree, kde se opět zaměřuje na přiřazování stavových proměnných různým stavům, aby se snížila aktivita přepínání v důsledku přechodu stavu.
  • Kromě pouhého kódování stavů pro nízkou spotřebu některé techniky zahrnují rozklad FSM na dva nebo více dílčích strojů, takže pouze jeden z nich je většinu času aktivní. S využitím toho může být další dílčí stroj buď s hodinovým hradlem, nebo s energetickým hradlem.

Viz také

Reference