Akcelerace algoritmů Komparátory studijní text frekventantů předmětu PV 193/3-1 Obsah 3 Komparátory. 2 3.1 Paralelní komparátor 2 3.1.1 Obvod pro zjištění shody dvou operandů. 2 3.1.2 Univerzální komparátor 2 Seznam obrázků. 8 3 Komparátory Komparátory se používají pro hledání shody klíčů v obsahu CACHE pamětí. Z dynamických požadavků vyplývá použití kombinační paralelní komparátory zjišťující shodnost porovnávaných operandů. 3.1 Paralelní komparátor Jak bylo uvedeno dříve, komparátor může být sestaven ve dvou verzích: · zjištění totožnosti dvou slov, tedy relace A º B, · zjištění všech relací mezi dvěma slovy, tedy A > B, A º B nebo A < B. Poněvadž paralelní komparátory pracují s paralelním obrazem dat, setkáváme se u těchto obvodů s problémem efektivní organizace přenosu z nižších do vyšších řádů výsledku. 3.1.1 Obvod pro zjištění shody dvou operandů Tento druh komparátoru je evidentně jednodušším případem a k jeho návrhu postačí fyzikální názor. K tomu, aby dvě čísla A a B byla totožná, musí pro všechny řády čísel platit že a[i] º b[i]. Tuto podmínku vyjadřuje rovnice: K = k[1] k[2] ... k[i] ... k[n] = k[1] k[2] ... k[i] ... k[n] = 1 K = k[1] k[2] ... k[i] ... k[n] = 0 kde pro každý prvek k[i] platí: > k[i] = a[i] b[i] + a[i] b[i] k[i] = a[i] b[i] + a[i] b[i] Rovnici pro vyhodnocení shody dvou operandů lze elegantně realizovat obvody s otevřeným kolektorem, jimiž se snadno tvoří logický součin, viz následující schéma. ^& ^& 1 b[1] a[1] b[1] a[1] ^& ^& 1 b[2] a[2] b[2] a[2] ^& ^& 1 b[n] a[n] b[n] a[n] & K ^& ^& 1 b[1] a[1] b[1] a[1] ^& ^& 1 b[2] a[2] b[2] a[2] ^& ^& 1 b[n] a[n] b[n] a[n] K U[cc] > Obrázek 3.1: Schéma porovnávacího obvodu s logickými členy AND-OR-INVERT a NAND a schéma s obvody AND-OR-INVERT s otevřeným kolektorem (montážní součin) 3.1.2 Univerzální komparátor V tomto případě nás zajímají všechny relace mezi dvěma operandy, ale je zřejmé, že pro určení jedné relace postačuje vyloučit dvě zbývající. Relace A º B je z hlediska tvaru logické rovnice poněkud odlišná od relací A > B a A < B. Je proto snadnější realizovat tyto dvě relace a relaci A º B odvodit vylučovací metodou. Relaci A > B mezi operandy A a B zjistíme odečtením operandu A od operandu B. Relaci B > A mezi těmito operandy zjistíme odečtením operandu B od operandu A. Protože se jedná o obdobné vztahy, bude problematika obou těchto relací popisována společně. Pro obě relace tedy platí, že pokud vznikne zápůjčka, je relace splněna a tedy že je splněn jeden z následujících vztahů: A > B º V B > A º M Nezajímá nás tedy hodnota rozdílu, ale pouze znaménko rozdílu. Pro realizaci tohoto vztahu použijeme větev generující zápůjčku paralelního odečítacího obvodu. Pro jeden řád porovnávaných slov platí následující vztahy: b[i][ ]a[i] V[i-1] V[i] M[i] M[i-1] b[i][ ]a[i] > 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 0 Obrázek 3.2: Postup odvození rovnic relačních funkcí A>B º V a B>A º M Pro odvození logických rovnic komparátoru požijeme substituce: > v[i] = a[i][ ]b[i] = a[i] + b[i] > m[i] = a[i] b[i] = a[i] + b[i] dostáváme vztahy: > V[i] = a[i]b[i] + V[i-1]* (a[i] + b[i]) = v[i] + V[i-1]*m[i] > M[i] = a[i]b[i] + M[i-1]* (a[i] + b[i]) = m[i] + M[i-1]*v[i] Poznámka: Funkci komparátoru může úspěšně plnit aritmetickologická jednotka. Komparace je ekvivalentní rozdílu dvou porovnávaných čísel. Výsledek signalizuje znaménko -záporné znaménko znamená, že větší je operand, který se odečítal. Výsledek roven nule znamená, že oba operandy jsou stejně velké a kladné znaménko a nenulový výsledek znamená, že první operand je větší. & & a[i] b[i] & & V[i-1] M[i-1] & & M[i] V[i] 1 K[i] v[i] m[i] > Obrázek 3.3: Schéma jednoho řádu porovnávacího obvodu Poznámka: Na tomto obrázku je znázorněn princip generování třetího možného výsledku komparace. V případě, že není nastaven ani signál V (významově nižší bity slova A > B) ani signál M (významově nižší bity slova B > A) zbývá poslední možnost, že významově nižší bity obou slov mají tutéž hodnotu a tudíž nastal stav K rovnost obou slov. V[1] = a[1]b[1] = v[1] V[2] = v[2] + V[1]*m[2] V[3] = v[3] + V[2]*m[3] = v[3] + v[2]*m[3] + v[1]*m[2]*m[3] : V[i] = v[i] + V[i-1]*m[i] = v[i] + v[i-1]*m[i] + v[i-2]*m[i-1]*m[i] + ....... + v[1]*m[2]*m[3]*……*m[i] > Výše odvozený vztah pro obecný počet řádů vede k sériové realizaci zápůjčkové větve odečítacího obvodu. Zpoždění zápůjčky přes jeden řád porovnávaných slov činí 2*t[pd]. V řadě případů se je takové zpoždění neúnosné, a proto se volí rychlejší paralelní nebo sérioparalelní generování zápůjčky obdobně jako u aritmetických obvodů. Pro paralelní realizaci zápůjčky lze použít obdobný postup popsaný u aritmetických obvodů založený na substituci a indukci. Rovnice paralelního tvaru zápůjčky má pro relaci A > B tvar: M[1] = a[1]b[1] = m[1] M[2] = m[2] + M[1]*v[2] M[3] = m[3] + M[2]*v[3] = m[3] + m[2]*v[3] + m[1]*v[2]*v[3] : M[i] = m[i] + M[i-1]*v[i] = m[i] + m[i-1]*v[i] + m[i-2]*v[i-1]*v[i] + ....... + m[1]*v[2]*v[3]*……*v[i] > Rovnice pro relaci B > A má tvar: Výše uvedené vztahy lze realizovat se sériovou realizací zápůjčky (viz vztah za prvním rovnítkem každé rovnice každé dílčí relace) nebo paralelně (viz vztah za druhým rovnítkem rovnice každé dílčí relace). Schéma uvedené na obrázku dole – viz Obrázek 3.4 – je mechanickým opakováním schéma jednobitového komparačního odvodu pro porovnávání více (v tomto případě tří) tříbitových slov v paralelním tvaru. Dynamické vlastnosti tohoto typu komparátoru jsou řádově 4t[pd] na každý řád porovnávaných slov. Výjimkou je zpoždění významově nejnižšího řádu porovnávacího obvodu, které činí 3t[pd]. Ze schéma lze vypozorovat, že dvouvstupové hradlo a investor jsou v této významově nejmenší části porovnávacího obvodu redundantní. & & a[2] b[2] & & & & v[2] m[2] M[3] V[3] & & a[1] b[1] v[1] m[1] & & a[3] b[3] & & & & v[3] m[3] M[2] V[2] M[1] V[1] > Obrázek 3.4: Příklad tříbitového komparačního obvodu se sériovou zápůjčkou Zjednodušení prvního řádu porovnávacího obvodu je ukázáno na obrázku dole – viz Obrázek 3.5. & & a[2] b[2] & & & & v[2] m[2] M[3] V[3] a[1] b[1] & & a[3] b[3] & & & & v[3] m[3] M[2] V[2] m[1]ºM[1] v[1]ºV[1] > Obrázek 3.5: Příklad tříbitového komparačního obvodu se sériovou zápůjčkou modifikovaný Poznámka: Výše uvedený postup je návodem na zrychlení funkce komparačního obvodu přes více řádů, což bude probráno v další části této kapitoly. Logická rovnice vyjadřující funkci komparátoru s paralelně generovanou zápůjčkou představuje součet dílčích součinů dílčích zápůjček odvozovaných ze všech řádů porovnávaných slov. Výsledné zpoždění paralelní zápůjčkové větve je sice nezávislé na počtu porovnávaných bitů, ale s délkou porovnávaných slov roste složitost logického výrazu popisujícího generování zápůjčky a tudíž i objem obvodu generujícího tuto zápůjčku. Příklad komparátoru dvou pětibitových paralelních slov s paralelní organizací zápůjčky je uveden na následujícím obrázku – viz Obrázek 3.6. Obrázek 3.6 a[1] 1 1 V b[1] 1 K M E b[2] v[2] a[2] a[3] b[3] & a[4] m[4] b[4] & a[5] v[5] m[5] b[5] m[3] m[2] v[4] v[3] & & & & & & & & & & & & & & > : Příklad pětibitového komparačního obvodu s paralelní zápůjčkou Podle předchozího obrázku lze usuzovat na nárůst složitosti dílčích součinů zápůjčky s rostoucím počtem paralelně porovnávaných bitů slov. Z tohoto důvodu se přistupuje k sérioparalelnímu tvaru generování zápůjčky, jehož tvar pro pětibitový komparátor je uveden na následujícím obrázku. Toto zapojení je kompromisem mezi rychlostí a objemem technického vybavení. Výsledné vztahy jsou ekvivalentní paralelnímu generování zápůjčky, ale výsledné hodnoty komparace jsou generovány pomocí dílčích zápůjček průchozím mechanismem, přičemž pro zjednodušení logických vztahů jsou využívány mintermy, které se v této úloze nemohou vyskytnout (což lze ověřit zpětným odvozením logických rovnic popisujících funkci tohoto konkrétního obvodu). Výše uvedené řešení zápůjčky umožňuje sestavovat moduly (sekce) komparačních obvodů až pro sedm bitů porovnávaných slov, viz výstupní hradla generující signály V a M – viz Obrázek 3.6. Omezení je dáno tím, že prakticky lze vyrobit maximálně osmibitová hradla. Tyto moduly lze použít jako základní modul komparátoru širších slov, který lze sestavit jako kaskádní nebo dvoustupňové zapojení základních modulů. Další možností je sestavit komparční obvod se sérioparalelní zápůjčkou – viz Obrázek 12.9. I toto zapojení poskytuje možnost sestavit moduly komparačních obvodů. Toto zapojení není tak náročné na množství spojů, ale má větší zpoždění. Tato verze zapojení je opět limitována možností prakticky vyrábět maximálně osmibitová hradla pro generování signálů V a M. Jako příklad lze použít pětibitové komparační moduly. Pokud pro označení modulu bude použita níže uvedená schematická značka, pak kaskádní a dvoustupňové schéma má tvar podle obrázku – viz Obrázek 3.8. & a[1] & V b[1] & & M & b[2] & a[2] & a[3] b[3] & a[4] b[4] & & & a[5] v[5] m[5] b[5] & m[4*]v[5] v[4*]m[5] m[3*]v[5*]v[4*]m[5] v[3*]m[5*]m[4*]v[5] > Obrázek 3.7: Příklad pětibitového komparačního obvodu se sérioparalelní zápůjčkou M A B E K V M A B E K V M A B E K V M A B E K V E a[1] a[6] a[10] b[1] b[6] b[10] M K V M A B E K V M A B E K V M A B E K V E a[1] a[6] a[11] b[1] b[6] b[11] M K V M A B E K V log.0 a) b) c > Obrázek 3.8: Příklad pětibitového komparačního obvodu: a) symbolická značka pětibitového modulu b) kaskádní zapojení pětibitových modulů do čtrnáctibitového komparátoru paralelních slov c) dvoustupňové zapojení pětibitových modulů do čtrnáctibitového komparátoru paralelních slov Poznámka: Výstupy M se připojují ke vstupům b[i] a výstupy V ke vstupům a[i], protože zde popisovaný komparátor je navržen pro generování zápůjček pro odečítání čísla B od čísla A, tedy pro operaci A-B. Seznam obrázků Obrázek 3.1: Schéma porovnávacího obvodu s logickými členy AND-OR-INVERT a NAND a schéma s obvody AND-OR-INVERT s otevřeným kolektorem (montážní součin) 2 Obrázek 3.2: Postup odvození rovnic relačních funkcí A>B º V a B>A º M... 3 Obrázek 3.3: Schéma jednoho řádu porovnávacího obvodu. 3 Obrázek 3.4: Příklad tříbitového komparačního obvodu se sériovou zápůjčkou. 4 Obrázek 3.5: Příklad tříbitového komparačního obvodu se sériovou zápůjčkou modifikovaný. 5 Obrázek 3.6: Příklad pětibitového komparačního obvodu s paralelní zápůjčkou. 5 Obrázek 3.7: Příklad pětibitového komparačního obvodu se sérioparalelní zápůjčkou. 6 Obrázek 3.8: Příklad pětibitového komparačního obvodu: 6