Automaticky vyladěný software lineární algebry - Automatically Tuned Linear Algebra Software

ATLAS

Úložiště
Typ	Softwarová knihovna
Licence	Licence BSD
webová stránka	matematický atlas. sourceforge .net

Automaticky laděný software lineární algebry ( ATLAS ) je softwarová knihovna pro lineární algebru . Poskytuje vyspělou implementaci open source BLAS API pro C a Fortran77 .

ATLAS se často doporučuje jako způsob automatického generování optimalizované knihovny BLAS. I když jeho výkon často sleduje výkon specializovaných knihoven napsaných pro jednu konkrétní hardwarovou platformu , je často první nebo dokonce jen optimalizovanou implementací BLAS dostupnou v nových systémech a představuje velké zlepšení oproti obecnému BLAS dostupnému na Netlib . Z tohoto důvodu se ATLAS někdy používá jako základní úroveň výkonu pro srovnání s jinými produkty.

ATLAS běží na většině operačních systémů podobných Unixu a na Microsoft Windows (pomocí Cygwin ). Je vydáván na základě licence ve stylu BSD bez klauzule o reklamě a může ji používat mnoho známých matematických aplikací včetně MATLAB , Mathematica , Scilab , SageMath a některých sestavení GNU Octave .

Funkčnost

ATLAS poskytuje plnou implementaci BLAS API a také některé další funkce z LAPACK , knihovny vyšší úrovně postavené na BLAS. V BLAS je funkce rozdělena do tří skupin zvaných úrovně 1, 2 a 3.

• Úroveň 1 obsahuje vektorové operace formuláře

${\ displaystyle \ mathbf {y} \ leftarrow \ alpha \ mathbf {x} + \ mathbf {y} \!}$

stejně jako skalární tečkové produkty a vektorové normy , mimo jiné.

• Úroveň 2 obsahuje operace matice s vektorem formuláře

${\ displaystyle \ mathbf {y} \ leftarrow \ alpha A \ mathbf {x} + \ beta \ mathbf {y} \!}$

stejně jako řešení pro bytí s trojúhelníkovým, mimo jiné.${\ displaystyle T \ mathbf {x} = \ mathbf {y}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle T}$

• Úroveň 3 obsahuje operace matice-matice , jako je široce používaná operace GEMM ( General Matrix Multiply )

${\ displaystyle C \ leftarrow \ alpha AB + \ beta C \!}$

a mimo jiné řešení pro trojúhelníkové matice .${\ displaystyle B \ leftarrow \ alpha T ^ {- 1} B}$${\ displaystyle T}$

Optimalizační přístup

Optimalizace přístup je nazýván Automated Empirický Optimalizace Software (AEOS), který identifikuje čtyři základní přístupy k počítačové asistované optimalizace z nichž ATLAS zaměstnává tři:

1. Parametrizace - vyhledávání v parametrickém prostoru funkce, používané pro faktor blokování, hranu mezipaměti atd.
2. Vícenásobná implementace - prohledávání různých přístupů k implementaci stejné funkce, např. Pro podporu SSE, než je vnitřní verze zpřístupní v C kódu
3. Generování kódu - programy, které vytvářejí programy zahrnující jaké znalosti mohou o tom, co přinese nejlepší výkon systému

• Optimalizace úrovně 1 BLAS využívá parametrizaci a vícenásobnou implementaci

Každá funkce BLAS ATLAS úrovně 1 má své vlastní jádro. Vzhledem k tomu, že by bylo obtížné udržovat tisíce případů v ATLAS, existuje malá optimalizace specifická pro architekturu pro úroveň 1 BLAS. Místo toho se spoléhá na vícenásobnou implementaci, která umožňuje optimalizaci kompilátoru k výrobě vysoce výkonné implementace pro systém.

• Optimalizace úrovně 2 BLAS využívá parametrizaci a vícenásobnou implementaci

S daty a operacemi k provedení funkce je obvykle omezena šířka pásma do paměti, a proto zde není mnoho příležitostí k optimalizaci${\ displaystyle N ^ {2}}$${\ displaystyle N ^ {2}}$

Všechny rutiny v BLAS ATLAS úrovně 2 jsou sestaveny ze dvou jader BLAS úrovně 2:

• • GEMV - aktualizace matice vektorovým násobením:

${\ displaystyle \ mathbf {y} \ leftarrow \ alpha A \ mathbf {x} + \ beta \ mathbf {y} \!}$

• • GER — obecná aktualizace 1. úrovně z vnějšího produktu:

${\ displaystyle A \ leftarrow \ alpha \ mathbf {x} \ mathbf {y} ^ {T} + A \!}$

• Optimalizace úrovně 3 BLAS využívá generování kódu a další dvě techniky

Protože máme operace pouze s daty, existuje mnoho příležitostí k optimalizaci${\ displaystyle N ^ {3}}$${\ displaystyle N ^ {2}}$

Úroveň 3 BLAS

Většina úrovně 3 BLAS je odvozena od GEMM , takže je to primární zaměření optimalizace.

${\ displaystyle O (n ^ {3})}$operace vs. data${\ displaystyle O (n ^ {2})}$

Intuice, že operace budou dominovat nad přístupem k datům, funguje pouze u zhruba čtvercových matic. Skutečným měřítkem by měl být nějaký druh povrchu k objemu. Rozdíl se stává důležitým pro velmi ne-čtvercové matice. ${\ displaystyle n ^ {3}}$${\ displaystyle n ^ {2}}$

Může si dovolit kopírovat?

Kopírování vstupů umožňuje uspořádat data způsobem, který poskytuje optimální přístup k funkcím jádra, ale to je za cenu přidělení dočasného prostoru a extra čtení a zápisu vstupů.

První otázka, které čelí GEMM, tedy je, může si dovolit kopírovat vstupy?

Pokud ano,

• Vložte do bloku hlavní formát s dobrým zarovnáním
• Využijte výhod uživatelských jader a vyčištění
• Zpracujte případy transpozice s kopií: vše udělejte do TN (transpozice - bez transpozice)
• Zabývejte se α v kopii

Pokud ne,

• Použijte verzi nocopy
• Neprovádějte žádné předpoklady o kroku matice A a B v paměti
• Zpracujte všechny případy transpozice explicitně
• Žádná záruka sladění údajů
• Podpora specifického kódu α
• Riskujte problémy s TLB , špatnými kroky atd.

Skutečné rozhodnutí je učiněno pomocí jednoduché heuristiky, která kontroluje „hubené případy“.

Okraj mezipaměti

Pro blokování mezipaměti 2. úrovně se používá jeden okrajový parametr mezipaměti. Vysoká úroveň zvolí pořadí pro procházení bloky: ijk, jik, ikj, jki, kij, kji . Nemusí to být stejné pořadí, v jakém se produkt provádí v rámci bloku.

Typicky vybrané objednávky jsou ijk nebo jik . Pro Jik ideální situace by byla pro kopírování A a NB široký panel B . Pro IJK prohodit role A a B .

Výběr většího z M nebo N pro vnější smyčku snižuje stopu kopie. Ale pro velké K ATLAS ani nepřiděluje takové velké množství paměti. Místo toho definuje parametr Kp , který nejlépe využije mezipaměť L2. Délka panelů je omezena na Kp . Nejprve se pokusí přidělit (v případě jik ) . Pokud se to nepodaří, zkusí to . (Pokud se to nepodaří, použije verzi GEMM bez kopírování, ale tento případ je nepravděpodobný pro rozumný výběr okraje mezipaměti.) Kp je funkce okraje mezipaměti a NB . ${\ displaystyle M \ cdot p + NB \ cdot Kp + NB \ cdot NB}$${\ displaystyle 2 \ cdot Kp \ cdot NB + NB \ cdot NB}$

LAPACK

Při integraci ATLAS BLAS s LAPACK je důležitým faktorem volba blokovacího faktoru pro LAPACK. Pokud je blokovací faktor ATLAS dostatečně malý, lze blokovací faktor LAPACK nastavit tak, aby odpovídal faktoru ATLAS.

Aby bylo možné využít výhod rekurzivní faktorizace, poskytuje ATLAS náhradní rutiny pro některé rutiny LAPACK. Jednoduše přepíší odpovídající rutiny LAPACK z Netlib .

Potřeba instalace

Instalace ATLAS na konkrétní platformu je náročný proces, který obvykle provádí prodejce systému nebo místní odborník a je k dispozici širšímu publiku.

U mnoha systémů jsou k dispozici výchozí architektonické parametry; jedná se v podstatě o uložená vyhledávání plus výsledky ručního ladění. Pokud výchozí nastavení oblouku bude fungovat, pravděpodobně získá o 10–15% lepší výkon než instalační vyhledávání. Na takových systémech je proces instalace značně zjednodušený.

Reference

externí odkazy

• Automaticky vyladěný software lineární algebry na SourceForge.net
• Příspěvek uživatele do ATLAS
• Společný průvodce vývojem ATLAS
• FAQ má vazby na Stručný návod k referenčnímu Blas a rychlá reference API ATLAS LAPACK
• Microsoft Visual C ++ Howto pro ATLAS