Vzorec přístupu do paměti - Memory access pattern
Ve výpočtech je vzor přístupu do paměti nebo vzor přístupu IO vzor, se kterým systém nebo program čte a zapisuje paměť na sekundární úložiště . Tyto vzory se liší v úrovni lokalizace reference a drasticky ovlivňují výkon mezipaměti a mají také důsledky pro přístup k paralelismu a distribuci pracovní zátěže v systémech sdílené paměti . Dále koherence vyrovnávací paměti problémy mohou mít vliv na víceprocesorových výkon, což znamená, že některé paměťové vzory přístupová umístit strop paralelismus (což manycore přístupy směřují k přetržení).
Paměť počítače se obvykle označuje jako „ náhodný přístup “, ale procházení softwarem bude stále vykazovat vzorce, které lze z důvodu efektivity využít. Existují různé nástroje, které návrhářům systémů a programátorům pomáhají porozumět, analyzovat a vylepšit vzor přístupu k paměti, včetně VTune a Vectorization Advisor , včetně nástrojů pro řešení vzorů přístupu k paměti GPU
Vzory přístupu do paměti mají také důsledky pro zabezpečení , což některé motivuje, aby se pokusili zamaskovat činnost programu z důvodu ochrany soukromí .
Příklady
Sekvenční
Nejjednodušším extrémem je sekvenční přístupový vzor, kde jsou data čtena, zpracovávána a zapisována s přímým inkrementovaným / dekrementovaným adresováním. Tyto přístupové vzory jsou vysoce přístupné předběžnému načtení .
Kráčel
Stridové nebo jednoduché 2D, 3D přístupové vzory (např. Procházení vícerozměrnými poli ) lze podobně snadno předvídat a lze je nalézt v implementacích algoritmů lineární algebry a zpracování obrazu . Obklad smyčky je efektivní přístup. Některé systémy s DMA poskytovaly stridový režim pro přenos dat mezi subtilem větších 2D polí a pamětí zápisníku .
Lineární
Vzor lineárního přístupu úzce souvisí s „stridovaným“, kdy lze adresu paměti vypočítat z lineární kombinace nějakého indexu. Postupné procházení indexů s lineárním vzorem poskytuje stridovaný přístup . Lineární přístupový vzor pro zápisy (s jakýmkoli přístupovým vzorem pro nepřekrývající se čtení) může zaručit, že lze paralelizovat algoritmus, který se využívá v systémech podporujících výpočetní jádra .
Nejbližší soused
Vzory přístupu k paměti nejbližšího souseda se objevují v simulaci a souvisejí se sekvenčními nebo rozkročenými vzory. Algoritmus může procházet datovou strukturu pomocí informací od nejbližších sousedů datového prvku (v jedné nebo více dimenzích) k provedení výpočtu. Ty jsou běžné ve fyzických simulacích pracujících na mřížkách. Nejbližší soused může také odkazovat na komunikaci mezi uzly v klastru; simulace fyziky, které se spoléhají na takové lokální přístupové vzorce, lze paralelizovat s daty rozdělenými do uzlů clusteru, přičemž mezi nimi probíhá čistě nejbližší soused, což může mít výhody pro latenci a šířku pásma komunikace. Tento případ použití se dobře mapuje na topologii sítě torus .
2D prostorově koherentní
Ve 3D vykreslování nejsou přístupové vzory pro mapování textur a rasterizaci malých primitiv (s libovolným zkreslením složitých povrchů) zdaleka lineární, ale stále mohou vykazovat prostorovou lokalitu (např. V prostoru obrazovky nebo v prostoru textury ). To lze proměnit v dobrou paměťovou lokalitu pomocí nějaké kombinace pořadí Mortonů a obkladů pro texturové mapy a data rámcových vyrovnávacích pamětí (mapování prostorových oblastí na řádky mezipaměti) nebo tříděním primitiv prostřednictvím odloženého vykreslování založeného na dlaždicích . Může být také výhodné ukládat matice v Mortonově pořadí do knihoven lineární algebry .
Rozptyl
Bodový přístup do paměti vzor kombinuje sekvenční čtení s indexované / random adresování zápisů. Ve srovnání se shromažďováním může hierarchii mezipaměti méně zatěžovat, protože prvek zpracování může odesílat zápisy způsobem „oheň a zapomenout“ (úplně vynechat mezipaměť), zatímco pro svá zdrojová data používá předvídatelné předběžné načítání (nebo dokonce DMA).
Může však být obtížnější paralelizovat, protože neexistuje žádná záruka, že zápisy nebudou interagovat, a mnoho systémů je stále navrženo za předpokladu, že mezipaměť hardwaru spojí mnoho malých zápisů do větších.
V minulosti se dopředné mapování textury pokoušelo zvládnout náhodnost pomocí „zápisů“, zatímco postupně čte informace o zdrojových texturách.
PS2 konzole použity konvenční inverzní mapování textury, ale manipulováno žádný bodový / shromáždit zpracování „on-chip“ pomocí EDRAM, zatímco 3D model (a hodně textury dat) z hlavní paměti se vede postupně DMA. Proto postrádal podporu indexovaných primitiv a někdy potřeboval ke správě textur „dopředu“ v seznamu zobrazení .
Shromáždit
V přístupovém vzoru pro shromažďování paměti jsou čtení náhodně adresována nebo indexována, zatímco zápisy jsou sekvenční (nebo lineární). Příkladem je inverzní mapování textury , kde lze data zapisovat lineárně přes řádky skenování , zatímco adresy textury s náhodným přístupem se počítají na pixel .
Ve srovnání s rozptylem je nevýhodou to, že ukládání do mezipaměti (a obcházení latencí) je nyní nezbytné pro efektivní čtení malých prvků, je však snazší paralelizovat, protože je zaručeno, že se zápisy nepřekrývají. Jako takový je přístup shromažďování běžnější pro programování gpgpu , kde se masivní threading (umožněný paralelismem) používá ke skrytí latencí čtení.
Kombinovaný sběr a rozptyl
Algoritmus může shromažďovat data z jednoho zdroje, provádět určité výpočty v místní nebo na čipové paměti a rozptýlit výsledky jinde. Jedná se v podstatě o plnou činnost kanálu GPU při provádění 3D vykreslování - shromažďování indexovaných vrcholů a textur a rozptylování stínovaných pixelů v prostoru obrazovky . Rastrování neprůhledných primitiv pomocí hloubkové vyrovnávací paměti je „komutativní“, což umožňuje přeuspořádání, což usnadňuje paralelní provádění. Obecně by byly potřeba synchronizační primitivy.
Náhodný
Na opačném konci je skutečně náhodný vzor přístupu do paměti. Několik multiprocesorových systémů se specializuje na řešení těchto problémů. Přístup PGAS může pomoci tříděním operací podle dat za běhu (užitečné, když problémem * je zjišťování polohy netříděných dat). Datové struktury, které se silně spoléhají na pronásledování ukazatelů, mohou často způsobit špatnou referenční lokalitu , ačkoli třídění může někdy pomoci. Vzhledem ke skutečně náhodnému vzoru přístupu do paměti je možné jej rozdělit (včetně fází rozptylu nebo seskupení nebo jiného mezilehlého třídění), což může celkově vylepšit lokalitu; to je často předpokladem pro paralelizaci .
Přístupy
Datově orientovaný design
Datově orientovaný design je přístup, jehož cílem je maximalizovat referenční lokalitu, a to uspořádáním dat podle toho, jak jsou procházena v různých fázích programu, v kontrastu s běžnějším objektově orientovaným přístupem (tj. Uspořádání tak, aby rozložení dat výslovně zrcadlilo vzor přístupu).
Kontrast s referenční lokalitou
Lokalita odkazu odkazuje na vlastnost vykazovanou vzory přístupu do paměti. Programátor změní vzor přístupu do paměti (přepracováním algoritmů), aby zlepšil lokalitu reference nebo zvýšil potenciál paralelismu. Programátor nebo návrhář systému může vytvářet rámce nebo abstrakce (např. Šablony C ++ nebo funkce vyššího řádu ), které zapouzdřují určitý vzor přístupu k paměti.
Různé úvahy o vzorcích přístupu do paměti se objevují v paralelismu mimo referenční lokalitu, konkrétně oddělení čtení a zápisů. Např .: i když jsou čtení a zápisy „dokonale“ lokální, je nemožné provést paralelizaci kvůli závislostem ; oddělení čtení a zápisů do samostatných oblastí přináší odlišný vzorec přístupu do paměti, možná se zpočátku bude zdát horší z hlediska čistého umístění, ale je žádoucí využít moderní paralelní hardware.
Lokalita odkazu může také odkazovat na jednotlivé proměnné (např. Schopnost kompilátoru ukládat je do mezipaměti v registrech ), zatímco termín vzor přístupu do paměti se týká pouze dat uchovávaných v indexovatelné paměti (zejména v hlavní paměti ).