Grunnleggende lineære algebra -delprogrammer - Basic Linear Algebra Subprograms

BLAS
Stabil utgivelse	3.8.0 / 12. november 2017 ; 3 år siden
Skrevet inn	avhenger av implementering
Plattform	Kryssplattform
Type	Bibliotek
Nettsted	www .netlib .org /blas /

Basic Linear Algebra Subprograms ( BLAS ) er en spesifikasjon som foreskriver et sett med rutiner på lavt nivå for å utføre vanlige lineære algebraoperasjoner som vektortilsetting , skalarmultiplikasjon , prikkprodukter , lineære kombinasjoner og matrisemultiplikasjon . De er de facto standard lavnivårutiner for lineære algebrabiblioteker; rutinene har bindinger for både C ("CBLAS -grensesnitt") og Fortran ("BLAS -grensesnitt"). Selv om BLAS -spesifikasjonen er generell, er BLAS -implementeringer ofte optimalisert for hastighet på en bestemt maskin, så bruk av dem kan gi betydelige ytelsesfordeler. BLAS -implementeringer vil dra nytte av spesiell flytende punktmaskinvare som vektorregistre eller SIMD -instruksjoner.

Det oppsto som et Fortran -bibliotek i 1979 og grensesnittet ble standardisert av BLAS Technical (BLAST) Forum, hvis siste BLAS -rapport finnes på netlib -nettstedet. Dette Fortran biblioteket er kjent som den referansen implementeringen (noen ganger forvirrende referert til som den BLAS biblioteket) og er ikke optimalisert for fart, men er i public domain .

De fleste biblioteker som tilbyr lineære algebra -rutiner, er i samsvar med BLAS -grensesnittet, slik at biblioteksbrukere kan utvikle programmer som er likegyldige for BLAS -biblioteket som brukes. Eksempler på BLAS-biblioteker inkluderer: OpenBLAS , BLIS (BLAS-lignende Library Instantiation Software) , Arm Performance Libraries, ATLAS og Intel Math Kernel Library (MKL). BLIS er optimalisert for AMD -plattformen. ATLAS er et bærbart bibliotek som automatisk optimaliserer seg selv for en vilkårlig arkitektur. MKL er et freeware og proprietært leverandørbibliotek optimalisert for x86 og x86-64 med vekt på ytelse på Intel- prosessorer. OpenBLAS er et åpen kildekode-bibliotek som er håndoptimalisert for mange av de populære arkitekturer. De Linpack benchmarks avhengige av BLAS rutine gemmfor sine ytelsesmålinger.

Mange numeriske programmer bruker BLAS-kompatible biblioteker til å gjøre lineære algebraberegninger, inkludert LAPACK , LINPACK , Armadillo , GNU Octave , Mathematica , MATLAB , NumPy , R og Julia .

Bakgrunn

Med ankomsten av numerisk programmering ble sofistikerte subrutinebiblioteker nyttige. Disse bibliotekene vil inneholde underrutiner for vanlige matematiske operasjoner på høyt nivå som rotfunn, matriseinversjon og løsning av ligningssystemer. Valgspråket var FORTRAN . Den mest fremtredende numerisk programmering biblioteket var IBM 's Scientific Delrutine Package (SSP). Disse underrutinebibliotekene tillot programmerere å konsentrere seg om sine spesifikke problemer og unngå å implementere kjente algoritmer på nytt. Bibliotekets rutiner vil også være bedre enn gjennomsnittlige implementeringer; matrisealgoritmer, for eksempel, kan bruke full svingning for å få bedre numerisk nøyaktighet. Biblioteksrutinene ville også ha mer effektive rutiner. For eksempel kan et bibliotek inneholde et program for å løse en matrise som er øvre trekantet. Bibliotekene vil inneholde enkelt-presisjon og dobbel-presisjon versjoner av noen algoritmer.

I utgangspunktet brukte disse underrutinene hardkodede løkker for sine operasjoner på lavt nivå. For eksempel, hvis en subrutine trengte å utføre en matrisemultiplikasjon, ville subrutinen ha tre nestede sløyfer. Lineære algebra-programmer har mange vanlige lavnivåoperasjoner (de såkalte "kjerne" -operasjonene, ikke relatert til operativsystemer ). Mellom 1973 og 1977 ble flere av disse kjerneoperasjonene identifisert. Disse kjerneoperasjonene ble definerte underrutiner som matematiske biblioteker kunne kalle. Kjerneanropene hadde fordeler fremfor hardkodede løkker: biblioteksrutinen ville være mer lesbar, det var færre sjanser for feil, og kjerneimplementeringen kunne optimaliseres for hastighet. En spesifikasjon for disse kjerneoperasjonene ved bruk av skalarer og vektorer , level-1 Basic Linear Algebra Subroutines (BLAS), ble utgitt i 1979. BLAS ble brukt til å implementere det lineære algebra-subrutinebiblioteket LINPACK .

BLAS -abstraksjonen tillater tilpasning for høy ytelse. For eksempel er LINPACK et generelt bibliotek som kan brukes på mange forskjellige maskiner uten endringer. LINPACK kan bruke en generisk versjon av BLAS. For å få ytelse kan forskjellige maskiner bruke skreddersydde versjoner av BLAS. Etter hvert som dataarkitekturer ble mer sofistikerte, dukket det opp vektormaskiner . BLAS for en vektormaskin kan bruke maskinens raske vektoroperasjoner. (Selv om vektorprosessorer til slutt falt i unåde, er vektorinstruksjoner i moderne CPUer avgjørende for optimal ytelse i BLAS -rutiner.)

Andre maskinfunksjoner ble tilgjengelige og kan også utnyttes. Følgelig ble BLAS utvidet fra 1984 til 1986 med nivå 2-kjerneoperasjoner som gjaldt vektormatriseoperasjoner. Minnehierarki ble også anerkjent som noe å utnytte. Mange datamaskiner har hurtigminne som er mye raskere enn hovedminnet; å holde matrisemanipulasjoner lokalisert gir bedre bruk av hurtigbufferen. I 1987 og 1988 ble nivå 3 BLAS identifisert for å utføre matrise-matrise operasjoner. Nivå 3 BLAS oppmuntret til blokkpartisjonerte algoritmer. De LAPACK biblioteket bruker nivå 3 Blas.

Den opprinnelige BLAS gjaldt bare tett lagrede vektorer og matriser. Ytterligere utvidelser av BLAS, for eksempel for sparsomme matriser, har blitt adressert.

Funksjonalitet

BLAS -funksjonaliteten er kategorisert i tre sett med rutiner kalt "nivåer", som tilsvarer både den kronologiske definisjons- og publiseringsrekkefølgen, så vel som graden av polynomet i kompleksiteten til algoritmer; Nivå 1 BLAS -operasjoner tar vanligvis lineær tid , $O (n)$ , nivå 2 operasjoner kvadratisk tid og nivå 3 operasjoner kubikk tid. Moderne BLAS -implementeringer gir vanligvis alle tre nivåene.

Nivå 1

Dette nivået består av alle rutinene beskrevet i den opprinnelige presentasjonen av BLAS (1979), som bare definerte vektoroperasjoner på stridd arrays : prikkprodukter , vektornormer , en generalisert vektortilsetning av skjemaet

{\ displaystyle {\ boldsymbol {y}} \ leftarrow \ alpha {\ boldsymbol {x}}+{\ boldsymbol {y}}}

(kalt " axpy", "ax plus y") og flere andre operasjoner.

Nivå 2

Dette nivået inneholder matrisevektoroperasjoner inkludert, blant annet, en ge neralized m atrix- v Ector multiplikasjon ( gemv):

{\ displaystyle {\ boldsymbol {y}} \ leftarrow \ alpha {\ boldsymbol {A}} {\ boldsymbol {x}}+\ beta {\ boldsymbol {y}}}

samt en løsning for $x$ i den lineære ligningen

{\ displaystyle {\ boldsymbol {T}} {\ boldsymbol {x}} = {\ boldsymbol {y}}}

med $T$ som trekantet. Utformingen av nivå 2 BLAS startet i 1984, med resultater publisert i 1988. Nivå 2-delrutiner er spesielt ment å forbedre ytelsen til programmer som bruker BLAS på vektorprosessorer , der nivå 1 BLAS er suboptimale "fordi de skjuler matrisvektor-naturen til operasjonene fra kompilatoren. "

Nivå 3

Dette nivået, formelt publisert i 1990, inneholder matrise-matriseoperasjoner , inkludert en "generell matrisemultiplikasjon " ( gemm), av skjemaet

{\ displaystyle {\ boldsymbol {C}} \ leftarrow \ alpha {\ boldsymbol {A}} {\ boldsymbol {B}}+\ beta {\ boldsymbol {C}},}

hvor $A$ og $B$ eventuelt kan transponeres eller hermitisk-konjugeres inne i rutinen, og alle tre matrisene kan skrives. Den vanlige matrisemultiplikasjonen $AB$ kan utføres ved å sette $α$ til en og $C$ til en helt null matrise av passende størrelse.

Rutiner for databehandling er også inkludert i nivå 3

{\ displaystyle {\ boldsymbol {B}} \ leftarrow \ alpha {\ boldsymbol {T}}^{-1} {\ boldsymbol {B}},}

hvor $T$ er en trekantet matrise , blant annet funksjonalitet.

På grunn av allestedsnærværende matrisemultiplikasjon i mange vitenskapelige applikasjoner, inkludert for implementering av resten av nivå 3 BLAS, og fordi raskere algoritmer eksisterer utover den åpenbare gjentakelsen av matrise-vektormultiplikasjon, gemmer et hovedmål for optimalisering for BLAS-implementatorer. For eksempel, ved å dekomponere en eller begge av $A$ , $B$ til blokkmatriser , gemmkan implementeres rekursivt . Dette er en av motivasjonene for å inkludere $β$ -parameteren, slik at resultatene fra tidligere blokker kan akkumuleres. Merk at denne nedbrytning krever spesialtilfellet $β = 1$ hvor mange implementeringer optimalisere for, for derved å eliminere en multiplikasjon for hver verdi av $C$ . Denne dekomponeringen gir bedre lokalitet for referanse både i rom og tid for dataene som brukes i produktet. Dette utnytter i sin tur hurtigbufferen på systemet. For systemer med mer enn ett cache -nivå kan blokkeringen brukes en gang til på rekkefølgen som blokkene brukes i beregningen. Begge disse optimaliseringsnivåene brukes i implementeringer som ATLAS . Mer nylig har implementeringer av Kazushige Goto vist at blokkering bare for L2 -hurtigbufferen , kombinert med forsiktig amortisering av kopiering til sammenhengende minne for å redusere TLB -feil, er bedre enn ATLAS . En svært avstemt implementering basert på disse ideene er en del av GotoBLAS , OpenBLAS og BLIS .

En vanlig variant av gemmer gemm3m, som beregner et komplekst produkt ved å bruke "tre reelle matrisemultiplikasjoner og fem virkelige matrisetillegg i stedet for de konvensjonelle fire virkelige matrisemultiplikasjonene og to virkelige matrisetillegg", en algoritme som ligner på Strassen -algoritmen som først ble beskrevet av Peter Ungar.

Implementeringer

Akselerere: Apples rammeverk for macOS og iOS , som inkluderer tunede versjoner av BLAS og LAPACK .
Arm Performance Libraries: Arm Performance Libraries , som støtter Arm 64 -biters AArch64 -baserte prosessorer, tilgjengelig fra Arm .
ATLAS: Automatisk tunet lineær algebra -programvare , en åpen kildekode -implementering av BLAS APIer for C og Fortran 77 .
BLIS: BLAS-lignende Library Instantiation Software-rammeverk for rask instantiering. Optimalisert for de fleste moderne CPUer. BLIS er en komplett refactoring av GotoBLAS som reduserer mengden kode som må skrives for en gitt plattform.
C ++ AMP BLAS: The C ++ AMP BLAS Library er en åpen kildekode- implementeringen av Blas i Microsofts AMP språk utvidelse for Visual C ++.
cuBLAS: Optimalisert BLAS for NVIDIA -baserte GPU -kort, som krever få ekstra bibliotekanrop.
NVBLAS: Optimalisert BLAS for NVIDIA-baserte GPU-kort, som bare tilbyr nivå 3-funksjoner, men som direkte drop-in-erstatning for andre BLAS-biblioteker.
clBLAS: En OpenCL -implementering av BLAS av AMD. En del av AMD Compute Libraries.
clBLAST: En avstemt OpenCL -implementering av det meste av BLAS api.
Eigen BLAS: Et Fortran 77 og C BLAS -bibliotek implementert på toppen av MPL -lisensiert Eigen -bibliotek , som støtter x86 , x86-64 , ARM (NEON) og PowerPC -arkitekturer.
ESSL: IBMs Engineering and Scientific Subroutine Library, som støtter PowerPC -arkitekturen under AIX og Linux .
GotoBLAS: Kazushige Gotos BSD-lisensierte implementering av BLAS, spesielt tilpasset Intel Nehalem / Atom , VIA Nanoprocessor , AMD Opteron .
GNU Vitenskapelig bibliotek: Multi-plattform implementering av mange numeriske rutiner. Inneholder et CBLAS -grensesnitt.
HP MLIB: HPs mattebibliotek som støtter IA-64 , PA-RISC , x86 og Opteron- arkitektur under HP-UX og Linux .
Intel MKL: Den Intel Math Kernel Library , som støtter x86 32-bits og 64-bits, tilgjengelig fri fra Intel . Inkluderer optimaliseringer for Intel Pentium , Core og Intel Xeon CPUer og Intel Xeon Phi ; støtte for Linux , Windows og macOS .
MathKeisan: NECs mattebibliotek, som støtter NEC SX-arkitektur under SUPER-UX , og Itanium under Linux
Netlib BLAS: Den offisielle referanseimplementeringen på Netlib , skrevet i Fortran 77 .
Netlib CBLAS: Referanse C -grensesnitt til BLAS. Det er også mulig (og populært) å ringe Fortran BLAS fra C.
OpenBLAS: Optimalisert BLAS basert på GotoBLAS, som støtter x86 , x86-64 , MIPS og ARM prosessorer.
PDLIB/SX: NECs Public Domain Mathematical Library for NEC SX-4- systemet.
rocBLAS: Implementering som kjører på AMD GPUer via ROCm .
SCSL: SGI 's Scientific Computing Software Library inneholder BLAS- og LAPACK -implementeringer for SGIs Irix -arbeidsstasjoner.
Sun Performance Library: Optimalisert BLAS og LAPACK for SPARC- , Core- og AMD64 -arkitekturer under Solaris 8, 9 og 10 samt Linux.
uBLAS: Et generisk C ++ malklassebibliotek som tilbyr BLAS -funksjonalitet. En del av Boost -biblioteket . Det gir bindinger til mange maskinvareakselererte biblioteker i en samlende notasjon. Videre fokuserer uBLAS på korrektheten av algoritmene ved hjelp av avanserte C ++ - funksjoner.

Biblioteker som bruker BLAS

Armadillo: Armadillo er et C ++ - lineært algebrabibliotek som tar sikte på en god balanse mellom hastighet og brukervennlighet. Den bruker malklasser og har valgfrie lenker til BLAS/ATLAS og LAPACK. Det er sponset av NICTA (i Australia) og er lisensiert under en gratis lisens.
LAPACK: LAPACK er et høyere nivå lineært algebra -bibliotek bygget på BLAS. I likhet med BLAS eksisterer det en referanseimplementering, men det finnes mange alternativer som libFlame og MKL.
Mir: En LLVM -accelerated generiske numeriske bibliotek for vitenskap og maskinlæring skrevet i D . Det gir generiske lineære algebra -delprogrammer (GLAS). Den kan bygges på en CBLAS -implementering.

Lignende biblioteker (ikke kompatible med BLAS)

Elementær: Elemental er en åpen kildekode-programvare for distribuert-minne tett og sparsom-direkte lineær algebra og optimalisering.
HASEM: er et C ++ - malbibliotek som kan løse lineære ligninger og beregne egenverdier. Det er lisensiert under BSD -lisens.
LAMA: Library for Accelerated Math Applications ( LAMA ) er et C ++ - malbibliotek for å skrive numeriske løsere rettet mot forskjellige typer maskinvare (f.eks. GPUer gjennom CUDA eller OpenCL ) på distribuerte minnesystemer , og skjuler maskinvarespesifikk programmering fra programutvikleren
MTL4: The Matrix Template Library versjon 4 er et generisk C ++ mal bibliotek som gir tynt og tett BLAS funksjonalitet. MTL4 etablerer et intuitivt grensesnitt (ligner MATLAB ) og bred anvendelighet takket være generisk programmering .

Sparsom BLAS

Flere utvidelser av BLAS for håndtering av sparsomme matriser har blitt foreslått i løpet av bibliotekets historie; et lite sett med sparsomme matrisekjernrutiner ble endelig standardisert i 2002.

Se også

Liste over numeriske biblioteker
Math Kernel Library , mattebibliotek optimalisert for Intel -arkitekturen; inkluderer BLAS, LAPACK
Numerisk lineær algebra , typen problem BLAS løser

Referanser

Videre lesning

BLAST Forum (2001-08-21), Basic Linear Algebra Subprograms Technical (BLAST) Forum Standard , Knoxville, TN: University of Tennessee
Dodson, DS; Grimes, RG (1982), "Bemerkning om algoritme 539: Grunnleggende lineære algebra -delprogrammer for Fortran -bruk", ACM Trans. Matte. Softw. , 8 (4): 403–404, doi : 10.1145/356012.356020 , S2CID 43081631
Dodson, DS (1983), "Rettelse: Bemerkning om" Algoritme 539: Basic Linear Algebra Subroutines for FORTRAN use " ", ACM Trans. Matte. Softw. , 9 : 140, doi : 10.1145/356022.356032 , S2CID 22163977
JJ Dongarra, J. Du Croz, S. Hammarling og RJ Hanson, algoritme 656: Et utvidet sett med FORTRAN Basic Linear Algebra Subprograms, ACM Trans. Matte. Softw., 14 (1988), s. 18–32.
JJ Dongarra, J. Du Croz, IS Duff og S. Hammarling, Et sett med nivå 3 grunnleggende lineære algebra delprogrammer, ACM Trans. Matte. Softw., 16 (1990), s. 1–17.
JJ Dongarra, J. Du Croz, IS Duff og S. Hammarling, Algorithm 679: A set of Level 3 Basic Linear Algebra Subprograms, ACM Trans. Matte. Softw., 16 (1990), s. 18–28.

Ny BLAS

LS Blackford, J. Demmel, J. Dongarra, I. Duff, S. Hammarling, G. Henry, M. Heroux, L. Kaufman, A. Lumsdaine, A. Petitet, R. Pozo, K. Remington, RC Whaley, Et oppdatert sett med grunnleggende lineære algebra -delprogrammer (BLAS), ACM Trans. Matte. Softw., 28-2 (2002), s. 135–151.
J. Dongarra, Basic Linear Algebra Subprograms Technical Forum Standard, International Journal of High Performance Applications and Supercomputing, 16 (1) (2002), s. 1–111, og International Journal of High Performance Applications and Supercomputing, 16 (2) ( 2002), s. 115–199.

Eksterne linker

BLAS hjemmeside på Netlib.org
BLAS Vanlige spørsmål
BLAS Hurtigreferanse fra LAPACK Brukerhåndbok
Lawson Oral History En av de opprinnelige forfatterne av BLAS diskuterer opprettelsen i et muntlig historieintervju. Charles L. Lawson muntlig historieintervju av Thomas Haigh, 6. og 7. november 2004, San Clemente, California. Society for Industrial and Applied Mathematics, Philadelphia, PA.
Dongarra Oral History I et muntlig historieintervju utforsker Jack Dongarra det tidlige forholdet mellom BLAS og LINPACK, etableringen av BLAS -versjoner på høyere nivå for nye arkitekturer, og hans senere arbeid med ATLAS -systemet for å automatisk optimalisere BLAS for bestemte maskiner. Jack Dongarra, muntlig historieintervju av Thomas Haigh, 26. april 2005, University of Tennessee, Knoxville TN. Society for Industrial and Applied Mathematics, Philadelphia, PA
Hvordan får BLAS så ekstrem ytelse? Ti naive 1000 × 1000 matrisemultiplikasjoner (10 ¹⁰ flytepunkt multipliser-legger) tar 15,77 sekunder på 2,6 GHz prosessor; BLAS -implementering tar 1,32 sekunder.
En oversikt over de sparsomme grunnleggende lineære algebra -delprogrammene: Den nye standarden fra BLAS Technical Forum [2]

Languages

In other projects