Transakční paměť - Transactional memory

Ve výpočetní technice a transakční technice se transakční paměť pokouší zjednodušit souběžné programování tím, že umožňuje skupině instrukcí pro načtení a uložení provést atomový způsob. Jedná se o mechanismus řízení souběžnosti analogický s databázovými transakcemi pro řízení přístupu do sdílené paměti při souběžném výpočtu . Transakční paměťové systémy poskytují abstrakci na vysoké úrovni jako alternativu k synchronizaci vláken na nízké úrovni. Tato abstrakce umožňuje koordinaci mezi souběžnými čteními a zápisy sdílených dat v paralelních systémech.

Motivace

Atomicita mezi dvěma paralelními transakcemi s konfliktem

Při souběžném programování je synchronizace vyžadována při pokusu o přístup ke sdílenému prostředku paralelními vlákny. Konstrukce synchronizace vláken na nízké úrovni, jako jsou zámky, jsou pesimistické a zakazují vláknům, která jsou mimo kritickou část, provádění jakýchkoli změn. Proces použití a uvolnění zámků často funguje jako dodatečná režie v úlohách s malým konfliktem mezi vlákny. Transakční paměť poskytuje optimistické řízení souběžnosti tím, že umožňuje paralelní běh vláken s minimálním rušením. Cílem transakčních paměťových systémů je transparentní podpora oblastí kódu označených jako transakce prosazováním atomičnosti , konzistence a izolace .

Transakce je sbírka operací, které lze provádět a provádět změny, pokud není přítomen konflikt. Když je detekován konflikt, transakce se vrátí do původního stavu (před jakýmikoli změnami) a bude spuštěna znovu, dokud nebudou odstraněny všechny konflikty. Před úspěšným potvrzením je výsledek jakékoli operace v rámci transakce čistě spekulativní. Na rozdíl od synchronizace založené na zámku, kde jsou operace serializovány, aby se zabránilo poškození dat, transakce umožňují další paralelismus, pokud se několik operací pokusí upravit sdílený prostředek. Protože programátor není zodpovědný za výslovnou identifikaci zámků nebo pořadí, v jakém jsou získány, programy využívající transakční paměť nemohou způsobit zablokování .

S těmito konstrukty na místě poskytuje transakční paměť abstrakci programování na vysoké úrovni tím, že umožňuje programátorům uzavřít své metody do transakčních bloků. Správné implementace zajišťují, že data nelze sdílet mezi vlákny bez procházení transakcí a vytvářejí serializovatelný výsledek. Kód lze například zapsat jako: 

def transfer_money(from_account, to_account, amount):
    """Transfer money from one account to another."""
    with transaction():
        from_account.balance -= amount
        to_account.balance   += amount

V kódu je blok definovaný „transakcí“ zaručen atomicitou, konzistencí a izolací základní implementací transakční paměti a je pro programátora transparentní. Proměnné v rámci transakce jsou chráněny před vnějšími konflikty a zajišťují, že buď bude převedena správná částka, nebo nebude provedena žádná akce. Chyby související se souběžností jsou stále možné v programech, které používají velký počet transakcí, zejména v softwarových implementacích, kde knihovna poskytovaná jazykem nedokáže vynutit správné použití. Chyby zavedené prostřednictvím transakcí mohou být často obtížně laditelné, protože zarážky nelze umístit do transakce.

Transakční paměť je omezená v tom, že vyžaduje abstrakci sdílené paměti. Přestože programy transakční paměti nemohou způsobit zablokování, programy mohou stále trpět živým zámkem nebo hladověním zdrojů . Například delší transakce se mohou opakovaně vracet v reakci na několik menších transakcí, čímž se ztrácí čas i energie.

Hardware vs. software

Hardwarová transakční paměť využívající bity pro čtení a zápis

Abstrakce atomičnosti v transakční paměti vyžaduje hardwarový mechanismus pro detekci konfliktů a zrušení všech změn provedených ve sdílených datech. Hardwarové transakční paměťové systémy mohou zahrnovat úpravy v procesorech, mezipaměti a sběrnicovém protokolu na podporu transakcí. Spekulativní hodnoty v transakci musí být ukládány do vyrovnávací paměti a musí zůstat neviditelné jinými vlákny až do doby potvrzení. Velké vyrovnávací paměti se používají k ukládání spekulativních hodnot a zároveň se vyhýbají šíření zápisu prostřednictvím podkladového protokolu koherence mezipaměti . Tradičně byly vyrovnávací paměti implementovány pomocí různých struktur v rámci hierarchie paměti, jako jsou fronty úložiště nebo mezipaměti. Vyrovnávací paměti dále od procesoru, například mezipaměť L2, mohou obsahovat spekulativnější hodnoty (až několik megabajtů). Optimální velikost vyrovnávací paměti je stále diskutována kvůli omezenému používání transakcí v komerčních programech. V implementaci mezipaměti jsou řádky mezipaměti obecně rozšířeny o bity čtení a zápisu. Když hardwarový řadič obdrží požadavek, použije řadič tyto bity k detekci konfliktu. Pokud je z paralelní transakce zjištěn konflikt serializovatelnosti, spekulativní hodnoty budou zahozeny. Když se používají mezipaměti, systém může představovat riziko falešných konfliktů kvůli použití granularity řádku mezipaměti. Load-link/store-conditional (LL/SC) nabízené mnoha procesory RISC lze považovat za nejzákladnější podporu transakční paměti; LL/SC však obvykle pracuje s daty, která mají velikost nativního strojového slova, takže jsou podporovány pouze jednoslovné transakce. Ačkoli hardwarová transakční paměť poskytuje maximální výkon ve srovnání se softwarovými alternativami, v současné době bylo pozorováno omezené použití.

Softwarová transakční paměť poskytuje sémantiku transakční paměti v softwarové runtime knihovně nebo programovacím jazyce a vyžaduje minimální hardwarovou podporu (obvykle operace atomového porovnávání a odkládání nebo ekvivalent). Temnou stránkou softwarových implementací je obvykle výkonnostní postih ve srovnání s hardwarovými řešeními. Hardwarová akcelerace může snížit některé režijní náklady spojené se softwarovou transakční pamětí.

Vzhledem k omezenější povaze hardwarové transakční paměti (v současných implementacích) může software, který ji používá, vyžadovat poměrně rozsáhlé ladění, aby z ní mohl plně těžit. Například dynamický alokátor paměti může mít významný vliv na výkon a podobně může mít vyplňování struktury vliv na výkon (kvůli problémům s vyrovnáváním mezipaměti a falešným sdílením); v kontextu virtuálního počítače mohou různá vlákna na pozadí způsobit neočekávané přerušení transakce.

Dějiny

Jeden z prvních implementací transakční paměti byl bránou obchod pufr používá v Transmeta je Crusoe a Efficeon procesory. Toto však bylo použito pouze k usnadnění spekulativních optimalizací pro binární překlad, nikoli k jakékoli formě spekulativního multithreadingu , nebo k jeho vystavení přímo programátorům. Azul Systems také implementoval hardwarovou transakční paměť pro zrychlení svých zařízení Java , ale to bylo podobně skryto před cizími lidmi.

Společnost Sun Microsystems implementovala do svého špičkového procesoru Rock hardwarovou transakční paměť a omezenou formu spekulativního multithreadingu . Tato implementace prokázala, že by mohla být použita pro zámkové zámky a složitější hybridní transakční paměťové systémy, kde jsou transakce zpracovávány kombinací hardwaru a softwaru. Procesor Rock byl zrušen v roce 2009, těsně před akvizicí společností Oracle ; zatímco skutečné produkty nebyly nikdy vydány, výzkumníkům byla k dispozici řada prototypových systémů.

V roce 2009 AMD navrhlo Advanced Synchronization Facility (ASF), sadu rozšíření x86, které poskytují velmi omezenou podporu hardwarové transakční paměti. Cílem bylo poskytnout hardwarová primitiva, která by mohla být použita pro synchronizaci na vyšší úrovni, jako je softwarová transakční paměť nebo bezzámkové algoritmy. Společnost AMD však neoznámila, zda bude ASF používán v produktech, a pokud ano, v jakém časovém rámci.

Nedávno společnost IBM v roce 2011 oznámila, že společnost Blue Gene/Q má hardwarovou podporu jak pro transakční paměť, tak pro spekulativní multithreading. Transakční paměť lze konfigurovat ve dvou režimech; první je neuspořádaný režim s jednou verzí, kde zápis z jedné transakce způsobí konflikt s jakýmikoli transakcemi, které čtou stejnou adresu paměti. Druhý režim je pro spekulativní multithreading, který poskytuje uspořádanou transakční paměť s více verzemi. Spekulativní vlákna mohou mít různé verze stejné adresy paměti a hardwarová implementace sleduje věk každého vlákna. Mladší vlákna mohou přistupovat k datům ze starších vláken (ale ne naopak) a zápisy na stejnou adresu jsou založeny na pořadí vláken. V některých případech mohou závislosti mezi vlákny způsobit, že se mladší verze přeruší.

Intel ‚s Transakční Synchronizace Extensions (TSX) je k dispozici v některých Skylake procesorů. Dříve byl implementován také v procesorech Haswell a Broadwell , ale implementace se v obou případech ukázaly jako vadné a podpora pro TSX byla deaktivována. Specifikace TSX popisuje API transakční paměti pro použití vývojáři softwaru, ale sděluje podrobnosti o technické implementaci. Architektura ARM má podobné rozšíření.

Od GCC 4.7 je k dispozici experimentální knihovna pro transakční paměť, která využívá hybridní implementaci. Varianta PyPy Pythonu také zavádí do jazyka transakční paměť.

Dostupné implementace

Viz také

Reference

Další čtení

  • Harris, Tim; Larus, James R .; Rajwar, Ravi (prosinec 2010), Transactional Memory, 2. vydání , Synthesis Lectures on Computer Architecture, 5 , Morgan & Claypool, s. 1–263, doi : 10,2200/S00272ED1V01Y201006CAC011
  • McKenney, Paul E .; Michael, Maged M .; Triplett, Josh; Walpole, Jonathan (červenec 2010). „Proč tráva na druhé straně nemusí být zelenější: srovnání zamykání vs. transakční paměti“. SIGOPS Oper. Syst. Rev . New York, NY, USA: ACM . 44 (3): 93–101. doi : 10,1145/1842733.1842749 . ISSN  0163-5980 .
  • Dave Dice, Yossi Lev, Mark Moir, Dan Nussbaum a Marek Olszewski. (2009) „Počáteční zkušenosti s implementací komerční hardwarové transakční paměti.“ Technická zpráva Sun Microsystems (60 stran) SMLI TR-2009-180. Na ASPLOS'09 doi se objevila krátká verze : 10.1145/1508244.1508263
  • Amy Wang, Matthew Gaudet, Peng Wu, José Nelson Amaral, Martin Ohmacht, Christopher Barton, Raul Silvera a Maged Michael. „ Hodnocení hardwarové podpory Blue Gene/Q pro transakční paměti “. In Sborník z 21. mezinárodní konference o paralelních architekturách a kompilačních technikách, s. 127–136. ACM, 2012.
  • Jacobi, C., Slegel, T., & Greiner, D. (2012, prosinec). „ Architektura a implementace transakční paměti pro IBM System z “. In Microarchitecture (MICRO), 45. výroční mezinárodní sympozium IEEE/ACM dne (str. 25–36). IEEE.
  • Harold W. Cain, Maged M. Michael, Brad Frey, Cathy May, Derek Williams a Hung Le. „Robustní architektonická podpora pro transakční paměť v architektuře Power.“ In ISCA '13 Proceedings of the 40th Annual International Symposium on Computer Architecture, pp. 225–236, ACM, 2013. doi : 10.1145/2485922.2485942

externí odkazy