Názory k článku
Vyrovnávací paměti (cache)

Diky za zajimavy serial. Chtel jsem se zeptat, jestli planujete take nejake dalsi info o cache se zamerenim na programovani, resp. optimalizaci kodu

Zdravim, ano priste si budeme povidat o tom, jaka je strategie alokace bloku v cache pametech - vetsinou to totiz neni tak, ze jakykoli blok z operacni pameti lze ulozit do jakehokoli bloku v cache (to by vyzadovalo full-asociativni pamet a ta je pomala), takze je na to dobre myslet. Ze strategie alokace take vychazi pozadavky na optimalni programovani, v podstate hlavne na organizaci vlastniho kodu (low level jazyky) i zpusobu pristupu k datum.

Pokud je cache rozdělená na i-cache a d-cache, není z programátorského hlediska neviditelná. Znamená totiž konec automodifikujících se programů.

Jeden z mých programů pro procesor 68000 třeba přestal fungovat s příchodem procesoru 68040.

Procesory take obsahují instrukce k výprázdnění techto cache. Často jsou povinné, například, když se x86 mění režim činnosti procesoru (třeba při vstupu do protect mode). Takže automodifikující se program ano, ale po každé modifikaci je nutné vyprázdnit cache.

Čímž ovšem ztratíme veškeré výhody, které automodifikace přinesla. Vyprázdnění cache ve výsledku stojí více, než ušetřených pár desítek nanosekund.

Takže na moderních procesorech již automodifikaci nelze použít jako prostředek pro urychlení běhu programu. Nanejvýš nako systémový nástroj (např. pro relokaci).

Takové geniální věci jako proměnná, která je zároveň argumentem instrukce, operátor, který je instrukčním kódem, nebo vyskočení ze smyčky přepsáním instrukce jump na konci, jsou dnes již minulostí.

Lispové kompilátory s citlivou automodifikací (tedy nikoli pár instrukcí kolem aktuální hodnoty PC :-)) nemají problémy na žádné platformě (jinak by vůbec nefungovaly :-)), stejně jako nemají problém s ad-hoc generováním kódu (některé implementace CLOSu). Jak přesně by to mohlo dnes sloužit jako prostředek k urychlení běhu programu? Myslím, že by s tím v dnešní době interferovalo víc věcí, nejen cache, ale třeba i branch prediction.

Tento problém se objevil už s příchodem fronty instrukcí (vlastně taková malá neinteligentní a jednosměrná cache :-). Nevím, jak přesně to bylo u platformy 68k, ale na x86 se tak dalo testovat, jestli je program krokovaný (v debuggeru) či ne - snad to dokonce používal nějaký vir pro detekci toho, jestli je na něj puštěnej heuristický detektor.

Opravdu to par viru na konci jejich zlate DOSovske ery pouzivalo. Dokonce jsem pri krokovani takoveho kodu kdysi ztratil relativne spoustu casu nez jsem si ten trik uvedomil. Jako myslenka to v dane dobe a v dane "aplikaci" bylo genialni :-). Rad bych poznal cloveka, ktereho to napadlo jako prvni. Snad to byl nejaky Bulhar - ti byvali v tomto smeru velice plodni.

Existuji dokonce andi-debuggovaci opatreni v programech, ktera toho dokonce vyuzivaji - kod se modifikuje v okamziku, kdy uz je nacteny v instrukcni pipeline. Pokud se zmena projevi, program usoudi, ze bezi v debuggeru.

Na x86 (a asi i x86-64) jsou sebemodifikující-se programy dovolené. 8086 až 80486 mělo několikabytovou frontu instrukcí a synchronizaci s tou frontou neřešilo --- programátor musel udělat JMP, poté, co si modifikoval kód. Pentium a vyšší do své pipeliny umí nacpat i instrukce za tím JMP, takže bylo potřeba vyvinout mechanismus, jak umožnit starým sebemodifikujícím-se programům, které vyprazdňují frontu pomocí JMP, fungovat. Takže všechny procesory od Pentia výš mají složitý mechanismus, který kontroluje, zda se nemodifikují nějaké rozpracované instrukce, a pokud ano, tak se celá pipelina vyprázdní (na Pentium 4 se vyprazdňuje i celá trace cache).

Sebemodifikující kód používá např. Quake, pokud se to modifikuje málo často (např. se modifikují konstanty v kódu po změně aspect ratio, po nahrátí mapy, při novém snímku), tak to vyprazdňování pipeliny ani nezpomaluje.

S humornou nadsazkou se take da rict, ze ZX81 cache melo, ale nemelo hlavni pamet, a jelo primo z te cache.

Docela dobrá legrace s cachemi je při programování pro víceprocoserové systémy, kdy dva procesory zapisují na stejnou adresu a každý procesor má vlastní verzi dat v cache.

Bylo by možná dobré zmínit, jak se cache synchronizují, jak funguje odposlouchávání sběrnice, atd :-)

doufám, že to bude někdy příště.

jj, o synchronizaci cache u MP systémů se zmíním. Řešitelné to je, je však nutné zavádět minimálně dvoubitové příznaky ke každému bloku.

Cache v multiprocesorovém systému jsou synchronizované. Čili se nemůže stát, že různé procesory mají ve své cachi různá data. Co není synchronizováno, jsou výkonné jednotky, ty můžou ty přístupy do cache různě přehazovat.

Docela by mě zajímalo, jak funguje ta víceprocesorová synchronizace na Sparc64 s těma jeho cachema indexovanýma virtuálními adresami.

A to tedy prrr, to může. Tedy nevím, jak současný procesory, ale v budoucnu to určitě začne být běžné. Nehledě na to, že s vyšujícím počtem procesorů se paměť sdílí jinak. (nCube, a tak). Nicméně současné procesory umí tzv. memory fence pomocí instrukce LOCK zamknout sběrnici a tím si vynutit většinou operaci READ-MODIFY-WRITE, zároveň se tím ale synchronizuji i cache, protože operace se provede write throw. Používat LOCK má tedy význam i při samotném zápisu (máme jistotu, že data se aktualizují všude) nebo při samotném čtení (čteme skutečný stav paměti, ne cache). Pochopitelně na tom úpí rychlost.

No a novější procesory zavádí protokol Acquire a Release. Vznikl víceméně ze dvou důvodů. První je, že procesor nezaručuje pořadí operací s paměti. Dvě čtecí, či zapisovací operace se mohou stát opačně z hlediska druhého procesoru, než je naprogramováno. No a zároveń zavádí polovční memory fence. Ta zaručí, ze po čtecí operace po Acquire přečte data až po instrukcí čtení a zápisu před Acquire. A naopak data zapsaná před Release se zapíší dřív, než data zapsaná po Release. Ve spolupráci s cache to zaručí, že před Acquire freshnou všechny staré data v cache (pokud tam jsou) a po Release ze flushnou všechny dirty data do paměti. Pakliže oba procesory používají Acquire a Release, a je zaručeno, že jeden procesor udělá Acquire po Release druhého procesoru, je také zaručeno, že data zapsaná před Releasem prvního procesoru budou platná po Acquire druhého procesoru.

I když současné procesory x86 synchronizaci řeší jinak, tahle doba nás v nejbližší době čeká.

Pokud by někdo udělal SMP s nesynchronizovanou cachí, znamenalo by to, že při každém braní spinlocku se cache musí vyprázdnit a těsně před odemčením spinlocku se musí modifikované položky zapsat do paměti. A když se podíváš, kolik spinlocků v tom jádře je, tak taková cache by nezrychlovala, ale zpomalovala (čím větší cache => tím větší čas na braní spinlocku).

Tusim ze pro K6 od amd byla i cache Level 3. Nebylo by mozno se alespon kratce zminit i o ni?

funguje stejne, jako L2, jenom je pomalejsi a vetsi

a najnovsie sa mi zda ju pchaju zase do procakov :)

To je v případě K6-3 (tento procesor mám a momentálně z něj píšu, nahradil jsem ním svoje Pentium 200 :-). K6 a K6-2 měly 32KB L1 cache na kód a 32KB na data. Pak byla na desce L2 cache o velikosti asi 512kB nebo 1MB. Ta L2 zrychlovala celkem dost, asi o třetinu. U K6-3 se dala 256kB L2 cache rovnou na chip, takže z té cache na desce se stala L3. Ale protože většinu přístupů zachytí ta L2, tak L3 už moc nezrychluje, jen asi o 2%.