Algoritmy a jejich implementace

Algoritmy a jejich implementace

2. ledna 2013

Obsah ´ cel pˇ 1 Uˇ redn´ aˇ sky 1.1

2

Pˇr´ıklad – sˇc´ıt´ an´ı matice . . . . . . . . . . . . . . . . . . . . .

2 Jazyk C 2.1

2 2

Typy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2.1.1

Jm´ena typ˚ u . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.2

Obskurdnosti . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.3

Kvalifik´atory . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.4

Storage class . . . . . . . . . . . . . . . . . . . . . . .

4

2.1.5

Inicializ´atory . . . . . . . . . . . . . . . . . . . . . . .

4

V´ yrazy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.2.1

Liter´ aly . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2.2

Oper´atory . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2.3

Konverze . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2.4

Deklarace funkc´ı . . . . . . . . . . . . . . . . . . . . .

6

2.3

Preprocesor . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.4

Standardn´ı knihovna . . . . . . . . . . . . . . . . . . . . . . .

7

2.4.1

limits.h . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4.2

stddef.h . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4.3

stdbool.h, stdint.h . . . . . . . . . . . . . . . . . .

7

2.4.4

inttypes.h . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4.5

stdlib.h . . . . . . . . . . . . . . . . . . . . . . . . .

7

string.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2

2.5

1

3 Pamˇ eti 3.1

3.2

8

Z´akladn´ı model . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.1.1

Plnˇe asociativn´ı cache . . . . . . . . . . . . . . . . . .

8

3.1.2

Optimalizace ˇr´adk˚ u . . . . . . . . . . . . . . . . . . .

8

3.1.3

Pˇr´ımo mapovan´ a cache

. . . . . . . . . . . . . . . . .

9

3.1.4

Mnoˇzinovˇe asociativn´ı cache . . . . . . . . . . . . . . .

9

3.1.5

MMU . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

Parametry RAM . . . . . . . . . . . . . . . . . . . . . . . . .

10

4 Rozs´ıˇ ren´ı GCC

10

5 Profilov´ an´ı

11

5.0.1

Profilovac´ı n´astroje . . . . . . . . . . . . . . . . . . . .

6 V´ıce procesor˚ u

12 12

6.1

Re´ aln´a situace . . . . . . . . . . . . . . . . . . . . . . . . . .

12

6.2

Programov´an´ı paralelizm˚ u . . . . . . . . . . . . . . . . . . . .

13

6.2.1

Synchronizaˇcn´ı primitiva . . . . . . . . . . . . . . . . .

13

6.2.2

Vyh´ yb´an´ı se synchronizaˇcn´ım primitiv˚ um . . . . . . .

13

6.2.3

Atomicita syscall˚ u . . . . . . . . . . . . . . . . . . . .

14

6.2.4

N´ astroje . . . . . . . . . . . . . . . . . . . . . . . . . .

14

6.3

Paralelizace mezi poˇc´ıtaˇci . . . . . . . . . . . . . . . . . . . .

14

6.4

Vektorov´e instrukce

14

. . . . . . . . . . . . . . . . . . . . . . .

7 Procesory

14

8 Paraleln´ı v´ ypoˇ cty

15

8.1

Cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

8.2

GPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

9 Cache-oblivious algoritmy

15

9.1

N´ asoben´ı matic . . . . . . . . . . . . . . . . . . . . . . . . . .

16

9.2

Vyhled´av´an´ı v setˇr´ıdˇen´ ych datech . . . . . . . . . . . . . . . .

16

9.3

Re´ aln´a situace . . . . . . . . . . . . . . . . . . . . . . . . . .

17

9.4

Tˇr´ıdˇen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2

9.5

Dynamick´e struktury . . . . . . . . . . . . . . . . . . . . . . .

3

19

´ cel pˇ Uˇ redn´ aˇ sky

1

Jak pˇrev´est efektivn´ı algoritmus do praxe tak, aby opravdu bˇeˇzel rychle.

1.1

Pˇ r´ıklad – sˇ c´ıt´ an´ı matice

Pamˇet’ je pomalejˇs´ı neˇz cache. Vyplat´ı se po ˇr´adc´ıch, aby nenaˇc´ıtal tak ˇcasto nov´e str´anky. Kop´ırov´an´ı pamˇeti je rychlejˇs´ı, neˇz forcyklov´e vyplˇ nov´an´ı. Lze pouˇz´ıt i mmap (je spoˇzdˇen´ y).

2

Jazyk C

Pouˇz´ıv´ ame normu C99. switch je jen goto na promˇenliv´e n´avˇeˇst´ı. Lze prokl´ adat jin´ ymi vˇecmi, tedy napˇr. while cyklus.

2.1

Typy

Z´akladn´ı: • Celoˇc´ıseln´e typy, jako int, char, r˚ uznˇe velk´e, znam´enk´ ov´e ˇci neznam´enkov´e, Bool. C99 uˇz ˇr´ık´ a i poˇzadovan´e velikosti (char ≥ 8, short, int ≥ 16, long ≥ 32, long long ≥ 64). D´ ale unsigned char je nejmenˇs´ı adresovateln´ a buˇ nka pamˇeti. Na unsigned typech funguje aritmetika modulo nˇejak´e ˇc´ıslo. Existuj´ı tam bity, kter´e jsou souˇc´ast´ı bin´ arn´ıho z´apisu, sm´ı tam b´ yt i nˇeco nav´ıc, mohou m´ıt libovoln´e permutace bit˚ u. • Typy na plovouc´ı ˇc´arky (float, double, long double). Mimo to zav´ad´ı kl´ıˇcov´e slovo Complex, kter´e kdyˇz se nap´ıˇse za jm´eno typu, tak se stane komplexn´ım. • Divn´ y typ void – neobsahuje ˇz´adnou hodnotu, napˇr. kdyˇz funkce nic nevrac´ı, ukazatel do nikam. • V´ yˇctov´e typy se tv´ aˇr´ı tak´e b´ yt z´akladn´ı, je to celoˇc´ıseln´ y typ. Odvozen´e: • Ukazatel. Nelze pˇretypov´avat libovolnˇe. Sm´ı se pˇretypov´avat na unsigned chary. 4

Je zde speci´aln´ı void *, je typovˇe kompatibiln´ı s libovoln´ ym ukazatelem. • Pole, v pamˇeti jsou naskl´ adan´e souvisle za sebou. Chov´a se k nim skoro stejnˇe, jako k ukazateli na jeho zaˇc´atek. • Struktury a uniony. Jsou to nˇejak´e r˚ uzn´e poloˇzky, struktura je m´ a za sebou, union pˇres sebe. M˚ uˇze m´ıt paddingy mezi prvky. Dodrˇzuje poˇrad´ı a padding z´avis´ı pouze na vˇecech nad t´ım a nikdy nesm´ı b´ yt pˇred prvn´ım prvkem. Lze pouˇz´ıt pˇri dˇediˇcnosti. Typy mohou b´ yt kompletn´ı a nekompletn´ı. U nekompletn´ıch lze vytv´aˇret ukazatele, nesm´ı se deklarovat promˇenn´ a toho typu, nesm´ı se sizeof. Typ lze upˇresˇ novat, i postupnˇe (napˇr. velikosti pol´ı). 2.1.1

Jm´ ena typ˚ u

Jsou v´ yrazy. int *f(void *x[]) – kdyˇz vezmu f, zavol´am ho s parametrem x (kter´ y, kdyˇz vezmu, zaindexuji a zdereferencuji, dostanu void), to zdereferencuju, tak dostanu int. Tedy to mus´ı b´ yt funkce, kter´a bere pole ukazatel˚ u na void a vrac´ı ukazatel na int. 2.1.2

Obskurdnosti

• Bitov´ a pole – intov´e typy, kter´e maj´ı danou velikost v bitech, sluˇcuj´ı se dohromady. struct { int x:5; int y:3; }; • Flexibiln´ı pole – na konci struktury m˚ uˇze b´ yt pole nezn´am´e d´elky. 2.1.3

Kvalifik´ atory

• const – Objekt, o kter´em se mluv´ı, je kontstantn´ı. Z´aleˇz´ı na jeho poloze, ˇc´ımˇz urˇcuje, co je konstantn´ı. • volatile – Zakazuje optimalizace na objektu. ˇ ık´ • restrict – R´ a o nˇeˇcem, ˇze je to jedin´ y ukazatel na dan´ y objekt (nebo, jedin´ y aktivn´ı), aby pˇrekladaˇc mohl optimalizovat.

5

2.1.4

Storage class

Urˇcuj´ı, jak je to uloˇzen´e. ˇ ı lok´ • auto – Zij´ alnˇe a vidˇet jsou tak´e lok´ alnˇe. Tak se chovaj´ı lok´ aln´ı promˇenn´e, kdyˇz nic nemaj´ı. Nesm´ı se pouˇz´ıt na glob´aln´ı. • extern – Neˇzije to tady, je to viditeln´e glob´alnˇe, ˇzije st´ale. • static – Je lok´ aln´ı pro dan´ y blok/modul a ˇzije celou dobu. • register – Doporuˇcuje ˇz´ıt v registru. Nejde na to vz´ıt ukazatel a podobnˇe, jinak je stejn´ a jako auto. • typedef – Je to typ. Na parametrech sm´ı b´ yt pouze register. U funkce, static znamen´a, ˇze ˇzije jen lok´ alnˇe. Pokud se definuje, tak je to glob´alnˇe viditeln´e, jen pˇri deklaraci se chov´a jako extern. Sm´ı se pouˇz´ıt explicitnˇe. O funkci lze ˇr´ıct jeˇstˇe inline, doporuˇcuje nevol´an´ı, ale vkl´ad´ an´ı. 2.1.5

Inicializ´ atory

Kompletuje datov´e typy (napˇr. urˇcuje d´elku pole, u kter´eho se to zat´ım nevˇedˇelo). Um´ı b´ yt pojmenovan´e, jsou ne´ upln´e v´ yrazy. struct i item = { .a.i = 0, .x = 2 }; Co je neinicializovan´e, tak se defaultuje na nulu, coˇz je rozd´ıl oproti bez inicializovan´e, kde to nula b´ yt nemus´ı.

2.2

V´ yrazy

Vˇetˇsina vˇec´ı jsou v´ yrazy. Kromˇe v´ ysledky mohou m´ıt i vedlejˇs´ı u ´ˇcinky. Pˇri poˇrad´ı poˇc´ıt´ an´ı je to definovan´e, tedy a+b+c, uz´ avorkuje se zleva a napˇr. u float˚ u nemus´ı b´ yt asociativn´ı.

6

Ale side effecty nemaj´ı dan´e poˇrad´ı, jen ˇr´ık´ a, ˇze vˇse probˇehne do nejbliˇzˇs´ıho sequence pointu. Sequence pointy jsou: • Konec pˇr´ıkazu ˇ arka jako oper´ator (ne parametry!) • C´ • Booleovsk´e &&, || • ? • Vstup a v´ ystup z funkce U nˇekter´ ych slibuje, ˇze se nˇeco nevyhodnot´ı (u booleovsk´ ych podm´ınek, otazn´ıku). 2.2.1

Liter´ aly

Napˇr. integerov´e (ˇc´ısla v r˚ uzn´ ych soustav´ach, mohou m´ıt datov´e typy). Znakov´e konstanty jsou typu int. Stringov´e se daj´ı spojovat, napˇr. "str""ing". ˇ z’ ˇci L"k˚ un ˇ". Unicodov´e escapy (L’ Sirok´ e znaky (wchar t), napˇr. L’ˇ u2302’) se mohou vyskytovat i v identifik´atorech. Liter´ al dan´eho typu se d´a udˇelat syntakticky pˇretypov´an´ım inici´ator˚ u ((const char []){ 1, 2, 3 }). 2.2.2

Oper´ atory

P´ar pozn´amek: • ~ je definov´an jen na unsigned. • &* je identita, i kdyby ten ukazatel nechtˇel fungovat (byl by NULL ˇci podobnˇe). • Pointerov´a aritmetika funguje po velikosti toho, na co se ukazuje. Sm´ı se ukazovat na prvky pole a jeden za. • a[b] je tot´eˇz jako *(a+b). • Bitov´e posuny se sm´ı dˇelat jen do velikosti typu (napˇr. o 31 na 32 bitov´em integeru). • Pˇriˇrazovac´ı oper´atory se z´avorkuj´ı zprava. 7

Chyt´ aky: • x&1 == y&1 je tot´eˇz jako x&(1 == y)&1. • 1 << 4 + 1 << 5 je tot´eˇz jako 1 << (4 + 1) << 5. 2.2.3

Konverze

• Pole → ukazatel (mimo sizeof a &). • Funkce → ukazatel na fci (mimo sizeof a &). • 0 a NULL jsou zamˇeniteln´e. • Integery menˇs´ı neˇz int na int (pro unsigned obdobnˇe). Konverze podle poˇc´ıt´ an´ı, z integeru na float, kdyˇz je alespoˇ n jeden float a tak podobnˇe. Konverze pˇri pˇretypov´an´ı nebo pˇri pˇriˇrazen´ı. 2.2.4

Deklarace funkc´ı

Vynechan´e parametry – neˇr´ık´ am o parametrech nic. ... – d´ale kolik chce libovoln´ ych parametr˚ u. Pozor, pole se pˇred´ avaj´ı odkazem, i kdyˇz se zadaj´ı velikosti a ned´ a se vracet. Pokud m´ am v´ıcerozmˇern´e pole, pak jde i toto: void sum(int n, int matice[n][n]);, aby bylo vˇedˇet, jak velk´ y je ˇr´adek toho pole. Kvalifik´atory mohou b´ yt uvedeny v hranat´ ych z´avork´ach: int cmp(int x[restrict], int y[restrict]);

2.3

Preprocesor

Pozor, existuj´ı trigraphy, napˇr. ??/ je backslash. Nahrazuje se vˇsude, d´a se nachytat. Dˇel´ a podm´ınˇen´e pˇreklady, nahrazuje definice. V includu se prov´ad´ı expanze maker. Ochrana proti n´ asobn´ emu vloˇ zen´ı: ifndef BLABLA_H define BLABLA_H 8

... endif Direktiva #pragma je implementaˇcnˇe z´avisl´a, ovl´ ad´ a pˇrekladaˇc. Podobnˇe se chov´a i Pragma, ale lze se pouˇz´ıt kdekoliv. V makrech se obˇcas hod´ı konstrukce do { ... } while(0).

Makra s promˇenliv´ ym poˇctem argument˚ u se dˇelaj´ı tak, ˇze se do z´avorek nap´ıˇse trojteˇcka a pouˇzije se VA ARGS .

Makro pracuje na tokenech, tedy pokud m´ am makro E, pak 12E3 je nˇeco jin´eho neˇz 12 E 3.

2.4

Standardn´ı knihovna

Vˇeci jako stddef.h, stdlib.h a podobnˇe. 2.4.1

limits.h

u, r˚ uzn´e INT MAX. Napˇr. CHAR BIT je poˇcet bit˚ 2.4.2

stddef.h

ptrdiff t je rozd´ıl dvou ukazatele, size t je v´ ysledek sizeof, NULL, offsetof() zjiˇst’uje offset prvku ve struktuˇre. 2.4.3

stdbool.h, stdint.h

Napˇr. typy int16 t (pˇresnˇe 16 bit˚ u), int least16 t (nejmenˇs´ı alespoˇ n 16 ale intmax t (nejvˇetˇs´ı integerov´ y) a intptr t (vebitov´ y), int fast16 t. D´ jde se tam ukazatel). 2.4.4

inttypes.h

Form´atovac´ı sekvence pro printf – napˇr. PRId16, pˇr´ıpadnˇe SCN* pro scanf. 2.4.5

stdlib.h

Funkce atexit(), registruj´ı cleanup handlery“. ” Tak´e makra EXIT SUCCESS a EXIT FAILURE. 9

qsort(), bsearch().

2.5

string.h

Napˇr. strcspn().

3

Pamˇ eti

3.1

Z´ akladn´ı model

M´ a procesor pˇripojen´ y ke sbˇernici. Na n´ı ˇzij´ı i dalˇs´ı zaˇr´ızen´ı a ˇradiˇc pamˇeti. K nˇemu je pˇripojen´ a pamˇet’. Tak´e je moˇzn´e, aby zaˇr´ızen´ı komunikovaly s pamˇet´ı pˇr´ımo, ale to lze zanedbat. Pamˇeti existuj´ı pamˇeti statick´e a dynamick´e. Statick´a je klopn´ y obvod, je velk´a, ale velmi rychl´ a. Dynamick´a je zaloˇzen´ a na kondenz´ atorech, je menˇs´ı, ale potˇrebuje nab´ıjen´ı (je tˇreba znovu zapsat) a je pomalejˇs´ı (asi o 2 ˇr´ady neˇz procesor). Proto se dˇelaj´ı hlavn´ı (velk´e) pamˇeti z dynamick´ ych a pˇrid´ avaj´ı se cache z statick´ ych. 3.1.1

Plnˇ e asociativn´ı cache

Nˇekolik ˇr´ adk˚ u, v kaˇzd´em adresa a data, um´ı to pˇr´ımo odpovˇedˇet, kde je v cache dan´ a adresa. Obvykle se na vyhazov´an´ı pouˇz´ıv´ a LRU (Least Recently Used), nejstarˇs´ı vyhazovat. Pokud je cache typu write-through (zap´ıˇsu do obou), nebo ˇcastˇeji, writeback cache. V cache si pamatuji, ˇze nˇekter´a data byla zmˇenˇen´ a, kdyˇz nen´ı co dˇelat nebo vyhazuji zmˇenˇenou poloˇzku, tak ji zap´ıˇsu. 3.1.2

Optimalizace ˇ r´ adk˚ u

Obvykle se cachuje po cel´ ych ˇr´adc´ıch, jeden ˇr´adek m´ a velikost vˇetˇsinou 32 nebo 64 bajt˚ u. Nepotˇrebuji si potom v cache pamatovat vˇsechny bity z adresy. Pamˇeti jsou na toto optimalizovan´e a um´ı ˇc´ıst cel´e ˇr´adky skoro stejnˇe rychle. Pro z´apis osamostatnˇen´eho bajtu je tˇreba napˇred ˇr´adek naˇc´ıst, z´apisy jsou proto pomalejˇs´ı.

10

3.1.3

Pˇ r´ımo mapovan´ a cache

Asociativn´ı pamˇeti se vyr´ abˇej´ı tˇeˇzko, proto se kaˇzd´ a adresa ukl´ad´ a na pˇredem dan´e m´ısto. Vˇetˇsinou se pouˇz´ıv´ a dan´ a ˇc´ast adresy. Doch´az´ı ke koliz´ım, ˇr´ık´ a se tomu cache aliasing. 3.1.4

Mnoˇ zinovˇ e asociativn´ı cache

M´ a hashovac´ı funkci, v kaˇzd´e pˇrihr´ adce je jedna mal´ a plnˇe asociativn´ı cache – k-cestnˇe asociativn´ı (m´ am v kaˇzd´e pˇrihr´ adce k ˇr´adk˚ u). Protoˇze je probl´em udˇelat cache, kter´a je z´aroveˇ n dostateˇcnˇe velk´a a dostateˇcnˇe velk´a (i kv˚ uli pˇrenosu k procesoru), pouˇz´ıv´ a se v´ıce´ urovˇ nov´a hierarchie (ˇc´ım bl´ıˇze, t´ım menˇs´ı ale rychlejˇs´ı). Jsou hierarchie inkluzivn´ı (co je v nˇekter´e, je i ve vˇsech vˇetˇs´ıch) nebo exkluzivn´ı (co je v jedn´e nesm´ı b´ yt jinde). Obˇcas b´ yvaj´ı 2 L1 cache (na instrukce a na data). V instrukˇc´ı mohou b´ yt n´apovˇedy. 3.1.5

MMU

Na jedn´e stranˇe je adresn´ı prostor kaˇzd´eho procesu a na druh´e se nach´az´ı fyzick´ y adresn´ı prostor. Obvykle pˇrekl´ad´ a po str´ank´ach (vˇetˇsinou pevn´e velikosti). Dnes napˇr´ıklad 4kB. Kaˇzd´ a str´anka m˚ uˇze m´ıt pr´ava, vlastn´ıka, flagy a podobnˇe. Obvykle se pouˇz´ıv´ a strom na vyhled´ av´an´ı pˇrekladu, kaˇzd´ a ukl´ad´ a, kde je dalˇs´ı tabulka nebo vlastn´ı str´anka. Je tˇreba m´ıt v procesoru uloˇzenou koˇrene. Nˇekter´e procesory um´ı i velk´e str´anky. Napˇr´ıklad 32bit vypad´ a tak, ˇze adresa je rozdˇelen´a na 10, 10, 12. Napˇred se pod´ıv´ a do koˇrene, ve kter´em je 1024 poloˇzek. Tam m˚ uˇze b´ yt bud’ odkaz na 4M B str´anku, nebo na str´anku s dalˇs´ımi 1024 poloˇzkami. D´ ale m´ ame TLB (Translation Lookup Buffer) – cache pro uˇz resolvovan´e adresy str´anky. Obvykle jsou mnoˇzinovˇe asociativn´ı a 2-´ urovˇ nov´e. Nˇekdy se pouˇziv´a jen TLB, zbytek se dˇel´ a softwarovˇe. Kdyˇz by byla cache s fyzick´ ymi adresami, je mnohem m´enˇe probl´em˚ u. Probl´em je, ˇze v dobˇe, kdy chci hledat, tak jeˇstˇe nem´am hotov´ y pˇreklad. Proto se pouˇz´ıv´ a hybrid, index (ta hashovan´ a ˇc´ast) je virtu´aln´ı, tag (ten asociativn´ı prefix) je fyzick´ y. Nav´ıc se star´ am o to, aby tam nebyla jedna fyzick´a str´anka dvakr´at. L2 uˇz b´ yvaj´ı adresovan´e ˇcistˇe fyzicky. 11

3.2

Parametry RAM

Dram je matice, m´ a ˇr´ adkov´ y buffer ve statick´e pamˇeti. Vˇzdy se pˇreˇcte ˇr´adek, t´ım se smaˇze, kdyˇz uˇz nen´ı potˇreba, tak ho vr´at´ı (a obnov´ı) a pˇreˇcte jin´ y. Obvykle se pouˇz´ıv´ a hodinov´ y sign´al na komunikaci. V kaˇzd´em tiku se pos´ıl´a data tam i zpˇet. M˚ uˇzu poslat adresu a pˇr´ıkaz, m˚ uˇzu vymˇen ˇovat data. Pˇr´ıkazy jsou: • NOP – Nˇekter´e pˇr´ıkazy trvaj´ı d´ele, vyplˇ nov´an´ı. • Active – Naˇcten´ı ˇr´ adku do bufferu. Pˇred´ av´a adresu ˇr´adku. • Read – Pˇreˇcten´ı dat z aktu´aln´ıho ˇr´adku. M˚ uˇze pˇreˇc´ıst i v´ıce, m˚ uˇze b´ yt nakonfigurovan´ a na ˇcten´ı po d´avk´ ach v r˚ uznˇe velk´ ych kusech. • Write – Opak read. • Precharge – Vr´ at´ı zp´ atky ˇr´adek. • Setmode – Napˇr. nastaven´ı velikosti d´avky. • Refresh – Obnov´ı jeden, nejstarˇs´ı, ˇr´adek. Obvykle jsou omezen´ı na minim´aln´ı ˇcas ˇcek´an´ı po Active, reakce na Read, ˇcasy mezi Active a Precharge obˇema smˇery. Dnes se pouˇz´ıv´ a nˇeco vylepˇsen´eho, DDR. DDR um´ı pˇren´est dvˇe slova za jeden takt (na n´abˇeˇzn´e i shazovac´ı hranˇe sign´alu). DDR2 m´ a dvakr´at rychlejˇs´ı sbˇernici, neˇz pamˇet’. DDR3 m´ a ˇctyˇrikr´ at rychlejˇs´ı sbˇernici, neˇz pamˇet’. Rozˇs´ıˇren´ı jsou, ˇze lze ˇr´ıct, kter´ ym slovem zaˇc´ıt d´avku (cyklicky). Jsou tam oddˇelen´e banky, pˇri ˇcek´an´ı jednoho m˚ uˇzu dˇelat nˇeco s jin´ ym. D´ale um´ı automatick´ y precharge, je parametr readu. Tak´e um´ı delayed read.

4

Rozs´ıˇ ren´ı GCC

Existuje jich hodnˇe, tady jsou nˇekter´e ˇcasto pouˇz´ıvan´e: • Pˇ r´ıkazov´ e v´ yrazy – define, kter´ y m´ a promˇenn´e, zaˇc´ın´ a ({, pak je blok, posledn´ı v´ yraz je n´avratov´a hodnota a ukonˇcen´e pomoc´ı }). define MIN(a,b) ({ \ int _a = (a), _b = (b); _a < _b ? _a : _b; })

12

• Vnoˇren´e funkce, vid´ı lok´ aln´ı promˇenn´e. Jdou dokonce d´avat ukazatele na ni. • a ?: b • Bin´arnˇe zapisovan´e liter´ aly (0b00100010). • case 1...5: • Vkl´ ad´ an´ı assembleru: asm("KUS ASM":V´ ystup:Vstup). • Atributy funkc´ı –

attribute ((noreturn)).

• Zabudovan´e funkce, napˇr. nota v´ yrazu je nˇejak´ a.

5

builtin expect – ˇr´ık´ a, ˇze oˇcek´avan´ a hod-

Profilov´ an´ı

Procesor obsahuje registry. EAX aˇz EDX jsou na obecn´e pouˇzit´ı, jsou menˇs´ı varianty a pot´e nˇejak´e speci´aln´ı. M´ a tak´e flagy, ud´avaj´ı stav procesoru. Napˇr´ıklad: • Sign flag (znam´enko) • Zero flag (posledn´ı vyˇsla nula) • Carry flag (pˇreteˇcen´ı) M´ ame tak´e z´asobn´ık, jsou na manipulaci instrukce a registry (ESP ukazuje nakonec, EBP za n´avratovou adresu). Ukl´ adaj´ı se sem funkce a jejich lok´ aln´ı promˇenn´e. Na intelu roste smˇerem dol˚ u. Pˇr´ıkaz objdump um´ı napˇr´ıklad disassemblovat. Assembler lze z´ıskat tak´e pˇr´ımo z gcc. Promˇenn´ a MALLOC CACHE – potom kontroluje, ˇze se nevol´a free dvakr´at a podobnˇe. Program ElectricFence odchyt´ av´a pˇr´ıstup za alokovanou pamˇet’ a podobnˇe. Nejmocnˇejˇs´ı je asi valgrind. • memcheck – kontrola pamˇeti • helgrind – zamyk´ an´ı pamˇeti • massif – grafy, kolik je pamˇeti spotˇrebovan´e • cachegrind – cachemissy 13

• callgrind – vyuˇzit´ı cache, profilov´an´ı k´odu D´ ale lze pˇridat flagy -fprofile-generate a -fprofile-use. 5.0.1

Profilovac´ı n´ astroje

Napˇr. gprof (jednou za nˇejakou dobu se pod´ıv´ a, kter´a funkce zrovna bˇeˇz´ı), oprofile, kter´ y k tomu pouˇz´ıv´ a kernel a HW podporu. AMD um´ı nˇeco zvan´e Instruction-Based Sampling. Sleduje vˇzdy jednu instrukci pˇri cel´em jej´ım zpracov´an´ı a zaznamen´ avaj´ı se jej´ı ud´alosti (napˇr. cache-miss, poˇcet tik˚ u).

6

V´ıce procesor˚ u

Model: procesory a pamˇet’ov´ y ˇradiˇc pˇripojen´ y ke sbˇernici (SMP). Kaˇzd´ y m´ a nˇejakou cache. Probl´em je, ˇze je potˇreba cache synchronizace. Lze ˇreˇsit pomoc´ı toho, ˇze procesory odposlouch´avaj´ı sbˇernici. Write-back cache lze vyˇreˇsit tak, ˇze max. 1 procesor m´ a data nacachovan´ a, v pˇr´ıpadˇe, ˇze jich potˇrebuje v´ıce, tak je write-trough. Stavy ˇr´ adk˚ u: • Invalid (nic) • Shared (aktu´ aln´ı data, m´ a je i nˇekdo jin´ y) • Exclusive (aktu´ aln´ı data, m´ am je j´a) • Modified (aktu´ aln´ı data, kter´a nejsou v RAM, m´ am je jen j´ a) Toto je tˇreba udrˇzovat v pr˚ ubˇehu v´ ypoˇctu u kaˇzd´eho ˇr´adku, v pˇr´ıpadˇe ˇcten´ı m˚ uˇze jin´ y zas´ahnout a ˇr´ıct, ˇze to m´ am j´a. Pokud se sd´ıl´ı ˇr´adek pˇri z´apisech, je to pomal´e, pokud maj´ı kaˇzd´e svoje a nelezou si do zel´ı. Druh´ y probl´em je, ˇze je to pomal´e tak, jak je pomal´ a pamˇet’ – napˇr. kdyˇz jeden ˇcte zmˇenˇen´ y ˇr´adek, mus´ı se poˇckat, aˇz pˇredchoz´ı zap´ıˇse. Vylepˇseno – nov´ y stav Owned“ – data nejsou v hlavn´ı pamˇeti a patˇr´ı ” aktu´aln´ımu procesoru. Rozˇs´ıˇren´ y stav Shared“, takhle nˇekomu patˇr´ı a mus´ı ” je na konci zapsat.

6.1

Re´ aln´ a situace

Procesor je pˇripojen pˇres FSB (Front Side Bus) k NorthBridge, ten uˇz se star´ a o komunikaci s rychl´ ymi zaˇr´ızen´ımi (DRAM, PCIe). D´ ale je k nˇemu pˇripojen jeˇstˇe SouthBridge, ten komunikuje s pomal´ ymi zaˇr´ızen´ımi (porty, karty). 14

AMD m´ a m´ısto FSB nˇeco, ˇcemu ˇr´ık´ a HyperTransport, pamˇeti pˇr´ımo na procesoru. HyperTransport um´ı vˇetven´ı do stromu. V pˇr´ıpadˇe, ˇze je v´ıce procesor˚ u, tak v prvn´ım pˇr´ıpadˇe jsou pˇripojeny k NorthBridgi. Um´ı se to aˇz se 4 procesory. U AMD m´ a kaˇzd´ y procesor v´ıce hypertransport˚ u, propojuj´ı se mezi sebou. Pamˇeti jsou lok´ aln´ı pro procesor, tedy jsou r˚ uznˇe rychl´e (z´ aleˇz´ı, jestli je lok´ aln´ı). Vyr´ab´ı se tak´e v´ıcej´ adrov´e procesory (v´ıce procesor˚ u na jednom ˇcipu). Kaˇzd´e j´adro m´ a vlastn´ı L1 cache, ostatn´ı cache jiˇz nˇekdy b´ yvaj´ı spoleˇcn´e. Z pohledu programu se chov´a podobnˇe, jako oddˇelen´e procesory, jen je trochu komplikovan´ y ˇcas na pˇr´ıstup k dat˚ um jin´ ych procesor˚ u. Pamˇet’ov´ y ˇradiˇc m´ıvaj´ı spoleˇcn´ y. Existuje tak´e HyperThreading – ˇr´ıd´ıc´ı ˇc´ast je tam dvakr´at, ale v´ ykonn´e jednotky sd´ıl´ı. Bohuˇzel to nefunguje, vyhazuj´ı si data z L1 cache.

6.2

Programov´ an´ı paralelizm˚ u

• V´ıce proces˚ u. Jednoduch´e, samo se to vyv´aˇz´ı, ale m´ alo spolu komunikuj´ı. Nehod´ı se, pokud je potˇreba pˇridˇelovat dynamicky nebo kdyˇz maj´ı nˇejak´ a sd´ılen´ a data. Moˇznost vyˇreˇsit sd´ılenou pamˇet´ı. • Vl´akna, coˇz jsou v podstatˇe jen procesy se sd´ılen´ ym adresn´ım procesem. Probl´em napsat spr´ avnˇe, je potˇreba synchronizovat. 6.2.1

Synchronizaˇ cn´ı primitiva

Prvn´ı je Mutex (Mutable Execution). Lze to zamknout a zamknut´e to sm´ı m´ıt max. jedno vl´ akno. Zamknut´ı ˇcek´a, dokud nen´ı odemˇceno. Verze je RW-mutex, kter´ y dovoluje m´ıt zamˇceno pro ˇcten´ı u v´ıce procesor˚ u. Pak jsou semafory – podobnˇe, jako mutex, ale um´ı poˇc´ıtat a jeho hodnota je vˇzdy nez´ aporn´e ˇc´ıslo. Up zv´ yˇs´ı o 1, down sn´ıˇz´ı o 1, ˇcek´a, pokud to nejde. Tyto operace jsou drah´e, protoˇze nejdou cachovat. Lze implementovat nˇejak´e rozdˇelov´an´ı pr´ace napˇr. pomoc´ı fronty. Ta jde implementovat pomoc´ı mutexu a semaforu. 6.2.2

Vyh´ yb´ an´ı se synchronizaˇ cn´ım primitiv˚ um

Existuj´ı atomick´e operace, kter´e umoˇzn ˇuj´ı vyhnout se takov´ ymto vˇecem. Je to nebezpeˇcn´e, mohou se prohazovat z´apisy a podobnˇe. 15

6.2.3

Atomicita syscall˚ u

Nˇekter´a systemov´a vol´an´ı jsou atomick´a. Napˇr´ıklad z´apisy do souboru. 6.2.4

N´ astroje

Napˇr´ıklad lze pouˇz´ıt OpenMP, kter´e pˇrid´ av´a nˇekter´a #pragma instrukce. Ty pak dovol´ı paralelizovat kusy k´odu.

6.3

Paralelizace mezi poˇ c´ıtaˇ ci

Lze paralelizovat jeˇstˇe pˇres v´ıce poˇc´ıtaˇc˚ u. Je tˇreba zaruˇcit jeˇstˇe rozumnou komunikaˇcn´ı sloˇzitost – kolik dat se pˇren´ aˇs´ı.

6.4

Vektorov´ e instrukce

Napˇr´ıklad SSE (Streaming SIMD Extension). Pracuj´ı se 128 bitov´ ymi registry. D´ a se s nimi pot´e pracovat jako s horou ˇc´ısel za sebou. Napˇr´ıklad PADDW – sˇc´ıt´ an´ı 16-bitov´ ych integer˚ u, PMINB – minimum z bajt˚ u, ˇci porovn´av´an´ı (PCMPEQB). D´ ale tu jsou permutaˇcn´ı instrukce. Pˇri programov´an´ı lze pouˇz´ıvat bud’ GCC buildiny, tedy napˇr: int pak je to 128 bit˚ u rozdˇelen´ ych na 16. bitov´e integery.

attribute (vector(16)),

Pˇr´ıpadnˇe to m˚ uˇze <emmintrin.h> d´av´a lepˇs´ı jm´ena.

7

Procesory

Kroky: • Naˇcten´ı instrukce • Dek´ odov´an´ı instrukce • Z´ısk´ an´ı parametr˚ u • Vykon´ an´ı • Zaps´an´ı v´ ysledk˚ u Snaˇz´ı se to paralelizovat. Od 486 existuje pipelina, nˇekdy mus´ı poˇckat na spoˇc´ıt´ an´ı pˇredchoz´ı instrukce. Od pentia se prov´ad´ı v´ıce instrukc´ı z´aroveˇ n (paraleln´ı execuˇcn´ı jednotky). Zaˇc´ın´ a odhadovat skoky. 16

Pro h´ad´ an´ı skok˚ u se pouˇz´ıvaly statick´e heuristiky a dynamick´e odhady. M´ıvaj´ı return stack, pro pˇr´ıpad skoku n´avratu, loop predictor. Pouˇz´ıvaj´ı se virtu´aln´ı registry a m´ a k dispozici v´ıce exekuˇcn´ıch jednotek.

8 8.1

Paraleln´ı v´ ypoˇ cty Cell

Z´akladn´ı, kontroln´ı, j´adro je PPC (rozum´ı instrukc´ım) vˇcetnˇe rozˇs´ıˇren´ı altivec (vektorov´e instrukce). M´ a velmi jednoduch´e j´adro, napˇr´ıklad nem´a outof-order pipeline, je tˇreba optimalizovat k´od. Norm´alnˇe skrz cache pˇripojen´ y do pamˇeti. M´ a tak´e tzv. synergic processing elements“, obvykle 8. Ke kaˇzd´emu je ” pˇripojen´ y jeden local store“ (256 kb), cel´e pˇripojen´e pˇres sbˇernici EIB“.Kaˇzd´e ” ” toto SPE m´ a 128 128 bitov´ ych registr˚ u, m´ a vlastn´ı (oˇcesanou) instrukˇcn´ı sadu, vektorov´e instrukce odpov´ıdaj´ıc´ı altivecu. Local store je explicitn´ı.

8.2

GPU

Grafick´a karta lze zneuˇz´ıt i k tomu, aby poˇc´ıtala nˇeco, co se pˇr´ımo nezobrazuje. Lze vyuˇz´ıt napˇr´ıklad tak, ˇze framebuffer nemus´ı b´ yt na obrazovku, ale i na texturu. A v´ ypoˇcty lze trochu programovat (tzv. shadery). Nˇejak´ a funkce se pust´ı na kaˇzd´ y pixel v´ ysledku, takˇze lze vyuˇz´ıt k paraleln´ım v´ ypoˇct˚ u. Branche je moˇzn´e simulovat pomoc´ı Z-bufferu. Je trochu ˇs´ılen´ a inicializace a podobnˇe. To se snaˇz´ı vyˇreˇsit OpenCL, ale jeˇstˇe nen´ı implementovan´ y.

9

Cache-oblivious algoritmy

Zp˚ usob, jak navrhovat algoritmy tak, aby nez´ avisely na parametrech cache, ale pouˇz´ıvaly ji dobˇre. Pokud se pod´ıv´ ame na n´avrh, kdy jsou data ve vnˇejˇs´ı pamˇeti. Je vnitˇrn´ı a ’ vnˇejˇs´ı pamˇet , vnitˇrn´ı m´ a velikost M , vstup a v´ ystup prob´ıh´ a po bloc´ıch velikosti B. Pˇribude vstupnˇe-v´ ystupn´ı sloˇzitost (v´ ystup lze zanedbat, protoˇze to nˇekdy budu muset urˇcitˇe pˇreˇc´ıst). Tento model lze pouˇz´ıvat na modelov´an´ı cache a pamˇeti, vnˇejˇs´ı pamˇet’ je RAM, vnitˇrn´ı je cache, bloky jsou ˇr´adky cache. Pˇredpokl´ adejme, ˇze cache se chov´a zcela optim´alnˇe. Potom IO model dˇel´ a horn´ı odhad, kolik dat proteˇce.

17

Pokud algoritmus funguje bez znalosti M a B jen konstantnˇe-kr´ at pomalejˇs´ı neˇz s jejich znalostmi, pak je cache-oblivious. Takov´ y algoritmus je napˇr´ıklad scan pole (kaˇzdou vˇec jednou pˇreˇcteme, ˇcte se postupnˇe, kdyˇz nezn´a parametry cache, tak se mu m˚ uˇze st´at, ˇze bude ne´ upln´ y blok na obou stran´ ach, takˇze pˇreˇcteme o max. 1 blok v´ıce). Stejnˇe tak otoˇcen´ı pole (pokud M ≥ 2B).

9.1

N´ asoben´ı matic

Kdyˇz budeme n´asobit matice a budeme m´ıt matice uloˇzen´e obvykl´ ym“ ” zp˚ usobem po ˇr´ adc´ıch, tak bude z druh´e matice vyhazovat data (ˇctu sloupeˇcek). Pokud budu m´ıt ale prvn´ı matici  3  po ˇr´adc´ıch a druhou po sloupc´ıch, jsem 3 sn´ıˇzil poˇcet ˇcten´ı z N na Θ NB .

ˇ Casto pom´ah´ a metoda rozdˇel a panuj“, protoˇze od urˇcit´e velikosti se uˇz ” probl´em vejde do cache. Zde je to velmi podobn´e strasserovu algoritmu. Hod´ı se ale, aby se menˇs´ı probl´em byl vˇzdy pohromadˇe. Jednoduˇse se (rekurentnˇe) ukl´ ad´ a po bloc´ıch/ˇctvrtin´ ach. 

AB CD



. Bude to uloˇ e jako ABCD. a ˇc´ast vˇzdy pohromadˇe. Celkovˇe zen´  Pot´e je kaˇzd´ 3 N2 N to vyjde O B + √M ·B + 1 . Pokud se udˇel´ a optimalizace ze strasserova algoritmu, tak prostˇredn´ı ˇclen bude

log 7 N √ 2 . M ·B

Pokud by nebylo pouˇzito toto uloˇzen´ı, vznik´ a horˇs´ı odhad. Obvykle se uvaˇzuje, ˇze poˇcet ˇr´adk˚ u cache je alespoˇ n tolik, kolik je velikost cache (ˇr´ık´ a se tomu ˇ st´ıhl´ a cache). Tedy, pokud by bylo norm´aln´ı uloˇzen´ı matice, tak pro ˇst´ıhlou cache bude stejn´ y.

9.2

Vyhled´ av´ an´ı v setˇ r´ıdˇ en´ ych datech

Pokud udˇel´ ame bin´ arn´ı vyhled´ av´an´ı, tak sk´aˇceme“ a v niˇcem to nepom˚ uˇze. ” Mohli bychom udˇelat B−strom. Probl´em je, ˇze nezn´ame B. Bin´arn´ı√strom lze pˇreskl´adat tak, aby se dobˇre cacheoval a nebo m˚ uˇzeme arnˇe, ale opˇet v takov´emto udˇelat N −−strom, ale kl´ıˇce budou ne line´ stromu (ˇr´ık´ a se tomu van-ende-boasovo uspoˇr´ad´ an´ı, nˇeco takov´eho je popsan´e v grafov´ ych algoritmech). V tomto pˇr´ıpadˇe potˇrebujeme tolik pˇr´ıstup˚ u,

18

kolik je d´elka cesty aˇz dol˚ u dˇeleno v´ yˇskou jednoho stromu, kter´ y se vejde do B. (Vyjde to 4 · logB N ).

9.3

Re´ aln´ a situace

• Strategie nen´ı optim´aln´ı • V´ıce u ´rovn´ı cache • Nen´ı plnˇe asociativn´ı • Nˇekdy to m´ a ruˇcn´ı obsluhu Mˇejme posloupnost poˇzadavk˚ u P , C jsou poˇcty ˇcten´ı a N jsou velikosti cache. Potom: CLRU

 = O COP T ·

NLRU

NLRU − NOP T + 1



Pokud vezmeme 2· vˇetˇs´ı cache bude LRU jen konstanta-kr´at pomalejˇs´ı. Vz´ıt dvakr´at vˇetˇs´ı cache nen´ı probl´em, protoˇze vˇsechny tyto algoritmy z´avis´ı na velikosti cache rozumˇe“ (ztrat´ı se to v O). ” Tyto algoritmy se chovaj´ı optim´alnˇe ke kaˇzd´e cache zvl´aˇst’ a pokud je cache hierarchie navrˇzen´ a dobˇre, tak se chov´a optim´alnˇe k celku. Na zbyl´e dva body lze postavit redukce, kter´e to pˇrev´ ad´ı, ale potˇrebuj´ı vˇedˇet uˇz vlastnosti cache. Vˇ eta 1 Pro libovolnou posloupnost poˇzadavk˚ u je:   nLRU #LRU = O #OP T · nLRU − nOP T + 1 D˚ ukaz: Na prvn´ım poˇzadavku je to nastejno. Pokud v Si LRU mine na 2 stejn´ ych poˇzadavc´ıch, tak probˇehlo alespoˇ n nLRU + 1 r˚ uzn´ ych poˇzadavk˚ u. OP T minul alespoˇ n nLRU − nopt + 1 kr´at. Pokud LRU mine na p, v Si je ≥ nLRU + 1 r˚ uzn´ ych str´anek, OPT mine alespoˇ n nLRU − nOP T + 1.

Jinak LRU mine na nl ru r˚ uzn´ ych str´ank´ach nav´ıc r˚ uzn´ ych od p, OPT mine alespoˇ n na nLRU − nOP T + 1. 19

9.4

Tˇ r´ıdˇ en´ı

Kdyˇz udˇel´ ame n-cestn´ y merge-sort (n = R (n) = Θ



M B ).

Potom:

n N · log M B B B



To je ale pro pˇr´ıpad, kdy zn´ ame parametry. Udˇel´ ame si k-trycht´ yˇ r. Ten bude sl´evat k posloupnost´ı ocelkov´e d´elcek 3 k3 k3 v ˇcase O(k 3 · logk) a prostoru O(k 2 ) a poˇctem pˇr´ıstup˚ u O log M B + k . B

Potom udˇel´ ame trycht´ yˇrov´e tˇr´ıdˇen´ı, coˇz bude rekurzivnˇe tˇr´ıdit za pomoci 1 n 3 -cestn´eho sl´ev´ an´ı pomoc´ı trycht´ yˇre. 1 3

2 3

R(n) = n · R(n + O



1 N n · log M + n3 B B B



Rekurzi zastav´ıme, kdyˇz tˇr´ıd´ıme bloky B 2 , kter´e uˇz se vejdou do ˇst´ıhl´e cache, naˇcteme na O(B) pˇr´ıstup˚ u. Po upoˇc´ıt´ an´ı vyjde, ˇze pokud m´ ame k dispozici trycht´ yˇr, um´ıme to stejnˇe rychle, jako se znalost´ı parametr˚ u cache. Algoritmus 1 (Trycht´ yˇ r): Myˇslenka je takov´a, ˇze trycht´ yˇr je strom, kter´ y m´ a na hran´ ach buffery. Listy naˇc´ıtaj´ı z vstupn´ıch soubor˚ u, v´ ystup pad´ a z koˇrene. Vrcholy sl´evaj´ı ze sv´ ych syn˚ u do bufferu nad sebou, kdyˇz nˇeco dojde, tak zavolaj´ı rekurzivnˇe naplnˇen´ı“ na synovi. ” √ Udˇel´ ame na tom van-ende-boassovu reprezentaci – nahoˇre je jeden k√ trycht´ yˇr, pod nimi jsou dalˇs´ı k-trycht´ yˇre. Spojeno je to buffery velikosti 3 2 k . Po upoˇc´ıt´ an´ı zabere O(k 2 ) pamˇeti, ˇcasov´a sloˇzitost je O(k 3 · logk ).

Pro v´ ypoˇcet poˇctu pˇr´ıstup˚ u vybereme j takov´e, ˇze zab´ır´ a≤ √ 1 se nevejde. Tedy j bude nˇekdy mezi M a M 4

M 4 ,

ale vˇetˇs´ı uˇz

Pˇredpokl´ ad´ ame ˇst´ıhlou cache. Nahr´an´ı jednoho trycht´ yˇre bude trvat O



3

J2 B

v listech). To se udokazuje, ˇze vyjde O( JB ).

 + J (J za prvn´ı bloky buffer˚ u

Kdyˇz dojdou data a spust´ıme jin´ y trycht´ yˇr, tak pˇrijdeme o tento v cache. 3 Ale do bufferu uˇz pˇrijde dostatek dat (J prvk˚ u). Po upoˇc´ıt´ an´ı vyjde nˇeco, co je potˇreba upoˇc´ıtat, ˇze vyjde stejnˇe, jak chceme. 20

,

9.5

Dynamick´ e struktury

Budeme stavˇet datovou strukturu, kter´a bude umˇet pˇridat kamkoliv, odebrat odkudkoliv a proj´ıt sekvenˇcnˇe. Udˇel´ ame to jako ˇr´ıdk´e pole (mohou nˇekter´e ˇc´asti chybˇet). Algoritmus 2 (Dynamick´ a datov´ a vyhled´ avac´ı struktura): Potom z toho p˚ ujde pomoc´ı van-ende-boass stromu postavit struktura, kter´a um´ı dˇelat jak stromov´e hled´an´ı, tak u ´pravy a sekvenˇcn´ı proch´azen´ı. Pˇredstav´ıme si strom nad prvky, ud´av´a intervaly povolen´e hustoty pole. Tyto intervaly se zpˇr´ısˇ nuj´ı“ smˇerem ke koˇreni. ” Invariant m˚ uˇze neplatit, kdyˇz se to nepotk´a (nikdo si toho nevˇsimne). Kdyˇz najdeme nˇejak´ y, pokraˇcujeme v hled´an´ı nahoru, neˇz naraz´ıme na jeden, kter´ y je v poˇr´ adku. Potom pˇrebudujeme tu ˇc´ast, kterou potˇrebujeme. ,

21