Oprogramowanie do automatycznej algebry liniowej - Automatically Tuned Linear Algebra Software

ATLAS

Magazyn
Rodzaj	Biblioteka oprogramowania
Licencja	Licencja BSD
Stronie internetowej	atlas matematyczny .sourceforge .net

Oprogramowanie do automatycznej algebry liniowej ( ATLAS ) to biblioteka oprogramowania do algebry liniowej . Zapewnia dojrzałą implementację Open Source API BLAS dla C i Fortran77 .

ATLAS jest często zalecany jako sposób automatycznego generowania zoptymalizowanej biblioteki BLAS. Chociaż jego wydajność często podąża za wydajnością wyspecjalizowanych bibliotek napisanych dla jednej konkretnej platformy sprzętowej , często jest to pierwsza lub nawet jedyna zoptymalizowana implementacja BLAS dostępna w nowych systemach i stanowi duże ulepszenie w stosunku do ogólnego BLAS dostępnego w Netlib . Z tego powodu ATLAS jest czasami używany jako podstawa wydajności do porównania z innymi produktami.

ATLAS działa na większości systemów operacyjnych typu Unix oraz na Microsoft Windows (używając Cygwin ). Jest wydany na licencji w stylu BSD bez klauzuli reklamowej i może z niego korzystać wiele znanych aplikacji matematycznych, w tym MATLAB , Mathematica , Scilab , SageMath i niektóre wersje GNU Octave .

Funkcjonalność

ATLAS zapewnia pełną implementację API BLAS, a także kilka dodatkowych funkcji LAPACK , biblioteki wyższego poziomu zbudowanej na bazie BLAS. W BLAS funkcjonalność jest podzielona na trzy grupy zwane poziomami 1, 2 i 3.

• Poziom 1 zawiera operacje wektorowe formularza

${\ Displaystyle \ mathbf {r} \ leftarrow \ alpha \ mathbf {x} + \ mathbf {y} \!}$

jak skalarnych iloczyn skalarny i norm wektora , między innymi.

• Poziom 2 zawiera operacje macierzowo-wektorowe postaci

${\ Displaystyle \ mathbf {r} \ leftarrow \ alfa A \ mathbf {x} + \ beta \ mathbf {y} \!}$

jak również rozwiązania dla z bycia trójkątne, między innymi.${\ displaystyle T \ mathbf {x} = \ mathbf {y}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle T}$

• Poziom 3 zawiera operacje macierzowo-macierzowe, takie jak szeroko stosowana operacja General Matrix Multiply (GEMM)

${\ Displaystyle C \ leftarrow \ alfa AB + \ beta C \!}$

a także rozwiązywanie między innymi macierzy trójkątnych .${\ Displaystyle B \ leftarrow \ alpha T ^ {- 1} B}$${\ displaystyle T}$

Podejście optymalizacyjne

Optymalizacja podejście nazywa Automated empiryczne Optymalizacja Oprogramowania (AEOS), który określa cztery podstawowe podejścia do optymalizacji komputera wspomaganego których ATLAS zatrudnia trzy:

1. Parametryzacja - przeszukiwanie przestrzeni parametrów funkcji, używana do blokowania współczynnika, krawędzi pamięci podręcznej itp.
2. Wiele implementacji - przeszukiwanie różnych podejść do implementacji tej samej funkcji, np. Pod kątem obsługi SSE, zanim intrinsics udostępni je w kodzie C
3. Generowanie kodu - programy, które piszą programy, wykorzystując ich wiedzę o tym, co zapewni najlepszą wydajność systemu

• Optymalizacja poziomu 1 BLAS wykorzystuje parametryzację i wielokrotną implementację

Każda funkcja ATLAS poziomu 1 BLAS ma swoje własne jądro. Ponieważ utrzymanie tysięcy przypadków w ATLAS byłoby trudne, istnieje niewielka optymalizacja specyficzna dla architektury dla poziomu 1 BLAS. Zamiast tego opiera się na wielu implementacjach, aby umożliwić optymalizację kompilatora w celu uzyskania wysokiej wydajności implementacji systemu.

• Optymalizacja poziomu 2 BLAS wykorzystuje parametryzację i wielokrotną implementację

Przy danych i operacjach do wykonania funkcja jest zwykle ograniczona przepustowością do pamięci, a zatem nie ma zbyt wielu możliwości optymalizacji${\ Displaystyle N ^ {2}}$${\ Displaystyle N ^ {2}}$

Wszystkie procedury w ATLAS poziom 2 BLAS są zbudowane z dwóch jąder poziomu 2 BLAS:

• • GEMV - mnożenie macierzy po wektorze:

${\ Displaystyle \ mathbf {r} \ leftarrow \ alfa A \ mathbf {x} + \ beta \ mathbf {y} \!}$

• • GER - ogólna aktualizacja rangi 1 z produktu zewnętrznego:

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

• Optymalizacja BLAS poziomu 3 wykorzystuje generowanie kodu i dwie pozostałe techniki

Ponieważ operujemy wyłącznie z danymi, istnieje wiele możliwości optymalizacji${\ Displaystyle N ^ {3}}$${\ Displaystyle N ^ {2}}$

Poziom 3 BLAS

Większość BLAS poziomu 3 pochodzi z GEMM , więc jest to główny cel optymalizacji.

${\ Displaystyle O (n ^ {3})}$operacje a dane${\ Displaystyle O (n ^ {2})}$

Intuicja, że operacje będą dominować nad dostępem do danych, działa tylko w przypadku mniej więcej kwadratowych macierzy. Rzeczywistą miarą powinien być rodzaj powierzchni do objętości. Różnica staje się ważna w przypadku bardzo niekwadratowych macierzy. ${\ Displaystyle n ^ {3}}$${\ displaystyle n ^ {2}}$

Czy stać go na kopiowanie?

Kopiowanie danych wejściowych pozwala na uporządkowanie danych w sposób zapewniający optymalny dostęp dla funkcji jądra, ale odbywa się to kosztem przydzielenia tymczasowej przestrzeni oraz dodatkowego odczytu i zapisu danych wejściowych.

Zatem pierwsze pytanie, przed którym stoi GEMM, brzmi: czy stać go na kopiowanie danych wejściowych?

W takim razie,

• Umieść w głównym formacie bloku z dobrym wyrównaniem
• Skorzystaj z jądra i czyszczenia dostarczonego przez użytkowników
• Obsługuj przypadki transpozycji z kopią: zamień wszystko na TN (transponuj - bez transpozycji)
• Zajmij się α w kopii

Jeśli nie,

• Użyj wersji nocopy
• Nie rób żadnych założeń na temat kroku macierzy A i B w pamięci
• Jawnie obsługuj wszystkie przypadki transpozycji
• Brak gwarancji zgodności danych
• Obsługa określonego kodu α
• Ryzyko problemów z TLB , złych kroków itp.

Właściwa decyzja jest podejmowana za pomocą prostej heurystyki, która sprawdza, czy nie występują „chude przypadki”.

Krawędź pamięci podręcznej

W przypadku blokowania pamięci podręcznej drugiego poziomu używany jest pojedynczy parametr krawędzi pamięci podręcznej. Wysoki poziom wybiera kolejność przechodzenia przez bloki: ijk, jik, ikj, jki, kij, kji . Nie musi to być ta sama kolejność, w jakiej produkt jest wykonywany w bloku.

Zazwyczaj wybierane zamówienia to ijk lub jik . Dla jik sytuacja Ideałem byłoby skopiować A i NB szeroki panel B . Dla IJK zamienić rolę A i B .

Wybór większego M lub N dla zewnętrznej pętli zmniejsza ślad kopii. Ale dla dużego K ATLAS nie przydziela nawet tak dużej ilości pamięci. Zamiast tego definiuje parametr Kp , aby zapewnić najlepsze wykorzystanie pamięci podręcznej L2. Długość paneli jest ograniczona do Kp . Najpierw próbuje przydzielić (w przypadku jik ) . Jeśli to się nie powiedzie, próbuje . (Jeśli to się nie powiedzie, używa wersji GEMM bez kopiowania, ale ten przypadek jest mało prawdopodobny dla rozsądnego wyboru krawędzi pamięci podręcznej). Kp jest funkcją krawędzi pamięci podręcznej i NB . ${\ Displaystyle M \ cdot p + NB \ cdot Kp + NB \ cdot NB}$${\ Displaystyle 2 \ cdot Kp \ cdot NB + NB \ cdot NB}$

LAPACK

Podczas integracji ATLAS BLAS z LAPACK ważną kwestią jest wybór czynnika blokującego dla LAPACK. Jeśli współczynnik blokowania ATLAS jest wystarczająco mały, współczynnik blokowania LAPACK można ustawić tak, aby odpowiadał współczynnikowi ATLAS.

Aby skorzystać z rekurencyjnej faktoryzacji, ATLAS zapewnia procedury zastępcze dla niektórych procedur LAPACK. Te po prostu nadpisują odpowiednie procedury LAPACK z Netlib .

Konieczność instalacji

Instalacja ATLAS na określonej platformie jest trudnym procesem, który jest zwykle wykonywany przez dostawcę systemu lub lokalnego eksperta i udostępniany szerszej publiczności.

W przypadku wielu systemów dostępne są domyślne parametry architektury; są to zasadniczo zapisane wyszukiwania oraz wyniki dostrojenia ręcznego. Jeśli domyślne ustawienia arch działają, prawdopodobnie uzyskają o 10-15% lepszą wydajność niż wyszukiwanie instalacji. W takich systemach proces instalacji jest znacznie uproszczony.

Bibliografia

Linki zewnętrzne

• Oprogramowanie do automatycznej algebry liniowej na SourceForge.net
• Wkład użytkownika do ATLAS
• Wspólny przewodnik po programowaniu ATLAS
• FAQ linki do szybkiej poradnik Blas i szybki odniesieniu do ATLAS Lapack odniesienia API
• Microsoft Visual C ++ Howto dla ATLAS