Grundläggande linjära algebra -delprogram - Basic Linear Algebra Subprograms

BLAS
Stabil frisättning	3.8.0 / 12 november 2017 ; 3 år sedan
Skrivet i	beror på genomförandet
Plattform	Plattformsoberoende
Typ	Bibliotek
Hemsida	www .netlib .org /blas /

Basic Linear Algebra Subprograms ( BLAS ) är en specifikation som föreskriver en uppsättning lågnivårutiner för att utföra vanliga linjära algebraoperationer som vektortillägg , skalär multiplikation , punktprodukter , linjära kombinationer och matrismultiplikation . De är de de facto- standardrutiner på låg nivå för linjära algebrabibliotek; rutinerna har bindningar för både C ("CBLAS -gränssnitt") och Fortran ("BLAS -gränssnitt"). Även om BLAS -specifikationen är allmän, är BLAS -implementeringar ofta optimerade för hastighet på en viss maskin, så att använda dem kan ge betydande prestandafördelar. BLAS -implementeringar kommer att dra nytta av speciell flytande punkt -hårdvara, till exempel vektorregister eller SIMD -instruktioner.

Det uppstod som ett Fortran -bibliotek 1979 och dess gränssnitt standardiserades av BLAS Technical (BLAST) Forum, vars senaste BLAS -rapport finns på netlibs webbplats. Denna Fortran bibliotek kallas referensimplementering (ibland förvirrande kallas den BLAS bibliotek) och är inte optimerad för hastighet, men är i det offentliga rummet .

De flesta bibliotek som erbjuder linjära algebra -rutiner överensstämmer med BLAS -gränssnittet, vilket gör att biblioteksanvändare kan utveckla program som är likgiltiga för att BLAS -biblioteket används. Exempel på BLAS-bibliotek inkluderar: OpenBLAS , BLIS (BLAS-liknande Library Instantiation Software) , Arm Performance Libraries, ATLAS och Intel Math Kernel Library (MKL). BLIS är optimerad för AMD -plattformen. ATLAS är ett bärbart bibliotek som automatiskt optimerar sig för en godtycklig arkitektur. MKL är ett freeware och proprietärt leverantörsbibliotek optimerat för x86 och x86-64 med betoning på Intel- processorer. OpenBLAS är ett bibliotek med öppen källkod som är handoptimerat för många av de populära arkitekturerna. De riktmärken Linpack är starkt beroende av BLAS rutin gemmför sina prestandamätningar.

Många numeriska program använder BLAS-kompatibla bibliotek för att göra linjära algebraberäkningar, inklusive LAPACK , LINPACK , Armadillo , GNU Octave , Mathematica , MATLAB , NumPy , R och Julia .

Bakgrund

Med tillkomsten av numerisk programmering blev sofistikerade subrutinbibliotek användbara. Dessa bibliotek skulle innehålla subrutiner för vanliga matematiska högnivåoperationer som rotfynd, matrisinversion och lösning av ekvationssystem. Valet språk var FORTRAN . Det mest framstående numeriska programmeringsbiblioteket var IBM : s Scientific Subroutine Package (SSP). Dessa subrutinbibliotek tillät programmerare att koncentrera sig på sina specifika problem och undvika att återimplementera välkända algoritmer. Biblioteksrutinerna skulle också vara bättre än genomsnittliga implementeringar; matrisalgoritmer kan till exempel använda full svängning för att få bättre numerisk noggrannhet. Biblioteksrutinerna skulle också ha effektivare rutiner. Till exempel kan ett bibliotek innehålla ett program för att lösa en matris som är övre triangulär. Biblioteken skulle innehålla enkelprecision och dubbelprecision av vissa algoritmer.

Ursprungligen använde dessa underrutiner hårdkodade slingor för sina lågnivåoperationer. Till exempel, om en subrutin behövde utföra en matrismultiplikation, skulle subrutinen ha tre kapslade slingor. Linjära algebraprogram har många vanliga lågnivåoperationer (de så kallade "kärnoperationerna", inte relaterade till operativsystem ). Mellan 1973 och 1977 identifierades flera av dessa kärnverksamheter. Dessa kärnverksamheter blev definierade underrutiner som matematiska bibliotek kunde anropa. Kärnanropen hade fördelar jämfört med hårdkodade loopar: biblioteksrutinen skulle vara mer läsbar, det fanns färre chanser för buggar och implementeringen av kärnan kunde optimeras för hastighet. En specifikation för dessa kärnoperationer med skalare och vektorer , nivå 1-linjära algebra subrutiner (BLAS), publicerades 1979. BLAS användes för att implementera det linjära algebra-subrutinbiblioteket LINPACK .

BLAS -abstraktionen möjliggör anpassning för hög prestanda. Till exempel är LINPACK ett allmänt bibliotek som kan användas på många olika maskiner utan modifiering. LINPACK kan använda en generisk version av BLAS. För att få prestanda kan olika maskiner använda skräddarsydda versioner av BLAS. När datorarkitekturer blev mer sofistikerade dök vektormaskiner upp. BLAS för en vektormaskin kan använda maskinens snabba vektoroperationer. (Även om vektorprocessorer så småningom blev ofördelaktiga, är vektorinstruktioner i moderna processorer avgörande för optimal prestanda i BLAS -rutiner.)

Andra maskinfunktioner blev tillgängliga och kan också utnyttjas. Följaktligen förstärktes BLAS från 1984 till 1986 med nivå 2-kärnoperationer som gällde vektormatrisoperationer. Minneshierarki erkändes också som något att utnyttja. Många datorer har cacheminne som är mycket snabbare än huvudminnet; Att hålla matrismanipulationerna lokaliserade möjliggör bättre användning av cachen. 1987 och 1988 identifierades nivå 3 BLAS för att utföra matris-matrisoperationer. Nivå 3 BLAS uppmuntrade blockpartitionerade algoritmer. De LAPACK biblioteks användningar nivå 3 BLAS.

Den ursprungliga BLAS gällde endast tätt lagrade vektorer och matriser. Ytterligare tillägg till BLAS, till exempel för glesa matriser, har behandlats.

Funktionalitet

BLAS -funktionen är kategoriserad i tre uppsättningar rutiner som kallas "nivåer", som motsvarar både den kronologiska ordningsföljden för definition och publicering, liksom graden av polynomet i komplexiteten hos algoritmer; Nivå 1 BLAS -operationer tar vanligtvis linjär tid , $O (n)$ , nivå 2 -operationer kvadratisk tid och nivå 3 -operationer kubik tid. Moderna BLAS -implementeringar ger vanligtvis alla tre nivåerna.

Nivå 1

Denna nivå består av alla rutiner som beskrivs i den ursprungliga presentationen av BLAS (1979), som endast definierade vektoroperationer på striderade matriser : prickprodukter , vektornormer , en generaliserad vektortillägg av formen

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

(kallas " axpy", "ax plus y") och flera andra operationer.

Nivå 2

Denna nivå innehåller matris-vektoroperationer inkluderande, bland annat, en GE neralized m atrix- v ector multiplikation ( gemv):

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

samt en lösare för $x$ i den linjära ekvationen

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

med $T$ som triangulär. Utformningen av nivå 2 BLAS startade 1984, med resultat publicerade 1988. Nivå 2-delrutinerna är särskilt avsedda att förbättra prestanda för program som använder BLAS på vektorprocessorer , där nivå 1 BLAS är suboptimala "eftersom de döljer matrisvektorn hos operationerna från kompilatorn. "

Nivå 3

Denna nivå, formellt publicerad 1990, innehåller matris-matrisoperationer , inklusive en "allmän matrismultiplikation " ( gemm), av formuläret

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

där $A$ och $B$ valfritt kan transponeras eller hermitisk konjugeras inuti rutinen, och alla tre matriserna kan stridas. Den vanliga matrismultiplikationen $AB$ kan utföras genom att sätta $a$ till en och $C$ till en all-nollmatris av lämplig storlek.

I nivå 3 ingår också rutiner för datorer

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

där $T$ är en triangulär matris , bland annat funktionalitet.

På grund av matrismultiplikationernas allestädes närvarande i många vetenskapliga tillämpningar, inklusive för implementering av resten av nivå 3 BLAS, och eftersom snabbare algoritmer existerar bortom den uppenbara upprepningen av matrisvektormultiplikation, gemmär det främsta målet för optimering för BLAS-implementatörer. Till exempel, genom att sönderdela en eller båda av $A$ , $B$ till blockmatriser , gemmkan implementeras rekursivt . Detta är en av motiveringarna för att inkludera $β$ -parametern, så att resultaten från tidigare block kan ackumuleras. Notera att denna sönderdelning kräver specialfallet $β = 1$ vilket många implementeringar optimera för, varigenom man eliminerar en multiplikation för varje värde på $C$ . Denna sönderdelning möjliggör bättre lokalisering av referens både i utrymme och tid för data som används i produkten. Detta utnyttjar i sin tur cacheminnet på systemet. För system med mer än en nivå av cacheminne kan blockeringen tillämpas en andra gång på den ordning som blocken används i beräkningen. Båda dessa optimeringsnivåer används i implementeringar som ATLAS . Mer nyligen har implementeringar av Kazushige Goto visat att blockering endast för L2 -cachen , i kombination med noggrann amortering av kopiering till sammanhängande minne för att minska TLB -missar, är överlägsen ATLAS . En starkt inställd implementering baserad på dessa idéer är en del av GotoBLAS , OpenBLAS och BLIS .

En vanlig variant av gemmär gemm3m, som beräknar en komplex produkt med hjälp av "tre verkliga matrismultiplikationer och fem verkliga matristillägg istället för de konventionella fyra verkliga matrismultiplikationerna och två verkliga matristillägg", en algoritm som liknar Strassen -algoritmen som först beskrivs av Peter Ungar.

Implementeringar

Accelerera: Apples ramverk för macOS och iOS , som inkluderar tunade versioner av BLAS och LAPACK .
Arm Performance Libraries: Arm Performance Libraries , som stöder Arm 64 -bitars AArch64 -baserade processorer, tillgängliga från Arm .
ATLAS: Automatiskt inställd Linear Algebra Software , en öppen källkod implementering av BLAS API: er för C och Fortran 77 .
BLIS: BLAS-liknande bibliotek Instantiation Software ram för snabb instans. Optimerad för de flesta moderna processorer. BLIS är en komplett ombyggnad av GotoBLAS som minskar mängden kod som måste skrivas för en given plattform.
C ++ AMP BLAS: Den C ++ AMP BLAS Library är en öppen källkod genomförandet av BLAS för Microsofts AMP språktillägg för Visual C ++.
cuBLAS: Optimerad BLAS för NVIDIA -baserade GPU -kort, som kräver några ytterligare bibliotekssamtal.
NVBLAS: Optimerad BLAS för NVIDIA-baserade GPU-kort, som bara tillhandahåller nivå 3-funktioner, men som en direkt inlämningsersättning för andra BLAS-bibliotek.
clBLAS: En OpenCL -implementering av BLAS av AMD. En del av AMD Compute Libraries.
clBLAST: En avstämd OpenCL -implementering av de flesta av BLAS api.
Eigen BLAS: Ett Fortran 77 och C BLAS -bibliotek implementerat ovanpå det MPL -licensierade Eigen -biblioteket , som stöder x86 , x86-64 , ARM (NEON) och PowerPC -arkitekturer.
ESSL: IBM : s Engineering and Scientific Subroutine Library, som stöder PowerPC -arkitekturen under AIX och Linux .
GotoBLAS: Kazushige Gotos BSD-licensierade implementering av BLAS, särskilt anpassad för Intel Nehalem / Atom , VIA Nanoprocessor , AMD Opteron .
GNU Scientific Library: Multiplattformsimplementering av många numeriska rutiner. Innehåller ett CBLAS -gränssnitt.
HP MLIB: HP : s matematikbibliotek som stöder IA-64 , PA-RISC , x86 och Opteron- arkitektur under HP-UX och Linux .
Intel MKL: Den Intel Math Kernel Library , stödja x86 med 32 bitar och 64 bitar, finns tillgänglig fritt från Intel . Inkluderar optimeringar för Intel Pentium- , Core- och Intel Xeon -processorer och Intel Xeon Phi ; stöd för Linux , Windows och macOS .
MathKeisan: NEC : s mattebibliotek, som stöder NEC SX-arkitektur under SUPER-UX , och Itanium under Linux
Netlib BLAS: Den officiella referensimplementeringen på Netlib , skriven i Fortran 77 .
Netlib CBLAS: Referens C -gränssnitt till BLAS. Det är också möjligt (och populärt) att ringa Fortran BLAS från C.
OpenBLAS: Optimerad BLAS baserad på GotoBLAS, stöder x86 , x86-64 , MIPS och ARM- processorer.
PDLIB/SX: NEC : s Public Domain Mathematical Library för NEC SX-4- systemet.
rocBLAS: Implementering som körs på AMD -GPU: er via ROCm .
SCSL: SGI : s Scientific Computing Software Library innehåller BLAS- och LAPACK -implementeringar för SGI: s Irix -arbetsstationer.
Sun Performance Library: Optimerad BLAS och LAPACK för SPARC- , Core- och AMD64 -arkitekturer under Solaris 8, 9 och 10 samt Linux.
uBLAS: Ett generiskt C ++ mallklassbibliotek med BLAS -funktionalitet. En del av Boost -biblioteket . Det ger bindningar till många hårdvaruaccelererade bibliotek i en samlande notation. Dessutom fokuserar uBLAS på att algoritmerna är korrekta med hjälp av avancerade C ++ - funktioner.

Bibliotek som använder BLAS

Armadillo: Armadillo är ett C ++ - linjärt algebrabibliotek som syftar till en bra balans mellan hastighet och användarvänlighet. Den använder mallklasser och har valfria länkar till BLAS/ATLAS och LAPACK. Det är sponsrat av NICTA (i Australien) och är licensierat under en gratis licens.
LAPACK: LAPACK är ett linjärt algebra -bibliotek på högre nivå byggt på BLAS. Liksom BLAS finns det en referensimplementering, men många alternativ som libFlame och MKL finns.
Mir: En LLVM -accelerated generiska numeriska bibliotek för vetenskap och maskininlärning skriven i D . Det ger generiska linjära algebra -delprogram (GLAS). Det kan byggas på en CBLAS -implementering.

Liknande bibliotek (inte kompatibla med BLAS)

Elementär: Elemental är en öppen källkodsprogramvara för distribuerat-minne tät och gles-direkt linjär algebra och optimering.
HASEM: är ett C ++ - mallbibliotek som kan lösa linjära ekvationer och beräkna egenvärden. Den är licensierad enligt BSD -licens.
LAMA: Library for Accelerated Math Applications ( LAMA ) är ett C ++ - mallbibliotek för att skriva numeriska lösare som är inriktade på olika typer av hårdvara (t.ex. GPU: er via CUDA eller OpenCL ) på distribuerade minnessystem , vilket döljer hårdvaruspecifik programmering från programutvecklaren
MTL4: Den Matrix mallbibliotek version 4 är en generisk C ++ mallsbiblioteket tillhandahåller glesa och täta BLAS funktionalitet. MTL4 upprättar ett intuitivt gränssnitt (liknande MATLAB ) och bred tillämpning tack vare generisk programmering .

Gles BLAS

Flera tillägg till BLAS för hantering av glesa matriser har föreslagits under bibliotekets historia; en liten uppsättning glesa matriskärnrutiner standardiserades slutligen 2002.

Se även

Lista över numeriska bibliotek
Math Kernel Library , mattebibliotek optimerat för Intel -arkitekturen; inkluderar BLAS, LAPACK
Numerisk linjär algebra , den typ av problem BLAS löser

Referenser

Vidare läsning

BLAST Forum (2001-08-21), Basic Linear Algebra Subprograms Technical (BLAST) Forum Standard , Knoxville, TN: University of Tennessee
Dodson, DS; Grimes, RG (1982), "Anmärkning om algoritm 539: Grundläggande linjära algebra -delprogram för Fortran -användning", ACM Trans. Matematik. Softw. , 8 (4): 403–404, doi : 10.1145/356012.356020 , S2CID 43081631
Dodson, DS (1983), "Corrigendum: Remark on" Algorithm 539: Basic Linear Algebra Subroutines for FORTRAN usage " ", ACM Trans. Matematik. Softw. , 9 : 140, doi : 10.1145/356022.356032 , S2CID 22163977
JJ Dongarra, J. Du Croz, S. Hammarling och RJ Hanson, algoritm 656: En utökad uppsättning FORTRAN Basic Linear Algebra Subprograms, ACM Trans. Matematik. Softw., 14 (1988), s. 18–32.
JJ Dongarra, J. Du Croz, IS Duff och S. Hammarling, En uppsättning nivå 3 grundläggande linjära algebra delprogram, ACM Trans. Matematik. Softw., 16 (1990), s. 1–17.
JJ Dongarra, J. Du Croz, IS Duff och S. Hammarling, algoritm 679: En uppsättning nivå 3 grundläggande linjära algebra -delprogram, ACM Trans. Matematik. 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, En uppdaterad uppsättning grundläggande linjära algebra -delprogram (BLAS), ACM Trans. Matematik. 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, och International Journal of High Performance Applications and Supercomputing, 16 (2) ( 2002), s. 115–199.

externa länkar

BLAS hemsida på Netlib.org
BLAS FAQ
BLAS Snabbreferensguide från LAPACK Användarhandbok
Lawson Oral History En av de ursprungliga författarna till BLAS diskuterar dess skapande i en muntlig historiaintervju. Charles L. Lawson Muntlig historiaintervju av Thomas Haigh, 6 och 7 november 2004, San Clemente, Kalifornien. Society for Industrial and Applied Mathematics, Philadelphia, PA.
Dongarra Oral History I en muntlig historiaintervju undersöker Jack Dongarra det tidiga förhållandet mellan BLAS och LINPACK, skapandet av BLAS -versioner på högre nivå för nya arkitekturer och hans senare arbete med ATLAS -systemet för att automatiskt optimera BLAS för specifika maskiner. Jack Dongarra, muntlig historiaintervju av Thomas Haigh, 26 april 2005, University of Tennessee, Knoxville TN. Society for Industrial and Applied Mathematics, Philadelphia, PA
Hur får BLAS så extrema prestanda? Tio naiva 1000 × 1000 matrismultiplikationer (10 ¹⁰ flytande multiplikations-tillägg) tar 15,77 sekunder på 2,6 GHz-processor; BLAS -implementering tar 1,32 sekunder.
En översikt över de sparsamma grundläggande linjära algebra -delprogrammen: Den nya standarden från BLAS Technical Forum [2]

Languages

In other projects