Basis Lineaire Algebra Subprogramma's - Basic Linear Algebra Subprograms

Basic Linear Algebra Subprogramma's ( BLAS ) is een specificatie die een reeks low-level routines voorschrijft voor het uitvoeren van algemene lineaire algebra- bewerkingen zoals vectoroptelling , scalaire vermenigvuldiging , puntproducten , lineaire combinaties en matrixvermenigvuldiging . Het zijn de de facto standaard low-level routines voor lineaire algebrabibliotheken; de routines hebben bindingen voor zowel C ("CBLAS-interface") als Fortran ("BLAS-interface"). Hoewel de BLAS-specificatie algemeen is, zijn BLAS-implementaties vaak geoptimaliseerd voor snelheid op een bepaalde machine, dus het gebruik ervan kan aanzienlijke prestatievoordelen opleveren. BLAS-implementaties zullen profiteren van speciale drijvende-komma-hardware zoals vectorregisters of SIMD- instructies.

Het is ontstaan ​​als een Fortran-bibliotheek in 1979 en de interface is gestandaardiseerd door het BLAS Technical (BLAST) Forum, waarvan het laatste BLAS-rapport te vinden is op de netlib- website. Deze Fortran-bibliotheek staat bekend als de referentie-implementatie (soms verwarrend de BLAS-bibliotheek genoemd) en is niet geoptimaliseerd voor snelheid, maar bevindt zich in het publieke domein .

De meeste bibliotheken die lineaire algebra-routines aanbieden, voldoen aan de BLAS-interface, waardoor bibliotheekgebruikers programma's kunnen ontwikkelen die onverschillig zijn voor de BLAS-bibliotheek die wordt gebruikt. Voorbeelden van BLAS-bibliotheken zijn: OpenBLAS , BLIS (BLAS-achtige Library Instantiation Software) , Arm Performance Libraries, ATLAS en Intel Math Kernel Library (MKL). BLIS is geoptimaliseerd voor het AMD- platform. ATLAS is een draagbare bibliotheek die zichzelf automatisch optimaliseert voor een willekeurige architectuur. MKL is een freeware en propriëtaire leveranciersbibliotheek die is geoptimaliseerd voor x86 en x86-64 met de nadruk op prestaties van Intel- processors. OpenBLAS is een open-sourcebibliotheek die met de hand is geoptimaliseerd voor veel van de populaire architecturen. De LINPACK-benchmarks zijn gemmvoor hun prestatiemetingen sterk afhankelijk van de BLAS-routine .

Veel numerieke softwaretoepassingen gebruiken BLAS-compatibele bibliotheken om lineaire algebraberekeningen uit te voeren , waaronder LAPACK , LINPACK , Armadillo , GNU Octave , Mathematica , MATLAB , NumPy , R en Julia .

Achtergrond

Met de komst van numerieke programmering werden geavanceerde subroutinebibliotheken nuttig. Deze bibliotheken zouden subroutines bevatten voor algemene wiskundige bewerkingen op hoog niveau, zoals het vinden van wortels, matrixinversie en het oplossen van vergelijkingssystemen. De taal van keuze was FORTRAN . De meest prominente numerieke programmeerbibliotheek was IBM 's Scientific Subroutine Package (SSP). Deze subroutinebibliotheken stelden programmeurs in staat zich op hun specifieke problemen te concentreren en te voorkomen dat bekende algoritmen opnieuw moesten worden geïmplementeerd. De bibliotheekroutines zouden ook beter zijn dan de gemiddelde implementaties; matrixalgoritmen kunnen bijvoorbeeld volledig draaien gebruiken om een ​​betere numerieke nauwkeurigheid te krijgen. De bibliotheekroutines zouden ook efficiëntere routines hebben. Een bibliotheek kan bijvoorbeeld een programma bevatten om een ​​matrix op te lossen die bovenste driehoekig is. De bibliotheken zouden versies met enkele precisie en dubbele precisie van sommige algoritmen bevatten.

Aanvankelijk gebruikten deze subroutines hard-coded loops voor hun low-level operaties. Als een subroutine bijvoorbeeld een matrixvermenigvuldiging moet uitvoeren, dan zou de subroutine drie geneste lussen hebben. Lineaire algebra-programma's hebben veel algemene bewerkingen op laag niveau (de zogenaamde "kernel" -bewerkingen, niet gerelateerd aan besturingssystemen ). Tussen 1973 en 1977 werden verschillende van deze kernbewerkingen geïdentificeerd. Deze kernelbewerkingen werden gedefinieerde subroutines die wiskundige bibliotheken konden aanroepen. De kernel-aanroepen hadden voordelen ten opzichte van hardgecodeerde lussen: de bibliotheekroutine zou beter leesbaar zijn, er waren minder kansen op bugs en de kernel-implementatie kon worden geoptimaliseerd voor snelheid. Een specificatie voor deze kernelbewerkingen met behulp van scalairen en vectoren , de niveau-1 Basic Linear Algebra Subroutines (BLAS), werd gepubliceerd in 1979. BLAS werd gebruikt om de lineaire algebra-subroutinebibliotheek LINPACK te implementeren .

De BLAS-abstractie maakt maatwerk mogelijk voor hoge prestaties. LINPACK is bijvoorbeeld een bibliotheek voor algemene doeleinden die zonder aanpassingen op veel verschillende machines kan worden gebruikt. LINPACK zou een generieke versie van BLAS kunnen gebruiken. Om de prestaties te verbeteren, kunnen verschillende machines aangepaste versies van BLAS gebruiken. Naarmate computerarchitecturen geavanceerder werden, verschenen vectormachines . BLAS voor een vectormachine zou de snelle vectorbewerkingen van de machine kunnen gebruiken. (Hoewel vectorprocessors uiteindelijk uit de gratie raakten, zijn vectorinstructies in moderne CPU's essentieel voor optimale prestaties in BLAS-routines.)

Andere machinefuncties kwamen beschikbaar en konden ook worden uitgebuit. Bijgevolg werd BLAS van 1984 tot 1986 uitgebreid met niveau-2-kernelbewerkingen die betrekking hadden op vectormatrixbewerkingen. Geheugenhiërarchie werd ook erkend als iets om te exploiteren. Veel computers hebben cachegeheugen dat veel sneller is dan het hoofdgeheugen; door matrixmanipulaties gelokaliseerd te houden, kan de cache beter worden gebruikt. In 1987 en 1988 werden de BLAS van niveau 3 geïdentificeerd om matrix-matrixoperaties uit te voeren. De BLAS van niveau 3 moedigde blokgepartitioneerde algoritmen aan. De LAPACK- bibliotheek gebruikt niveau 3 BLAS.

Het oorspronkelijke BLAS betrof alleen dichtbewaarde vectoren en matrices. Verdere uitbreidingen van BLAS, zoals voor schaarse matrices, zijn aangepakt.

Functionaliteit

BLAS-functionaliteit is onderverdeeld in drie sets routines die "niveaus" worden genoemd, die overeenkomen met zowel de chronologische volgorde van definitie en publicatie, als de mate van het polynoom in de complexiteit van algoritmen; Niveau 1 BLAS-bewerkingen nemen doorgaans lineaire tijd , O ( n ) , niveau 2-bewerkingen kwadratische tijd en niveau 3-bewerkingen kubieke tijd in beslag . Moderne BLAS-implementaties bieden doorgaans alle drie de niveaus.

Niveau 1

Dit niveau bestaat uit alle routines die zijn beschreven in de oorspronkelijke presentatie van BLAS (1979), die alleen vectorbewerkingen op strided arrays definieerde : puntproducten , vectornormen , een gegeneraliseerde vectortoevoeging van de vorm

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

(genaamd " axpy", "ax plus y") en verschillende andere bewerkingen.

Level 2

Dit niveau bevat matrix-vectorbewerkingen waaronder, onder andere, een ge neralized m atrix- v ector vermenigvuldiging ( gemv):

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

evenals een oplosser voor x in de lineaire vergelijking

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

waarbij T driehoekig is. Het ontwerp van de Level 2 BLAS begon in 1984 en de resultaten werden in 1988 gepubliceerd. De Level 2 subroutines zijn vooral bedoeld om de prestaties van programma's die BLAS gebruiken op vectorprocessors te verbeteren , waar Level 1 BLAS suboptimaal is "omdat ze de matrix-vectoraard van de bewerkingen van de compiler."

Niveau 3

Dit niveau, formeel gepubliceerd in 1990, bevat matrix-matrixbewerkingen , waaronder een "algemene matrixvermenigvuldiging " ( gemm), van de vorm

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

waarbij A en B optioneel kunnen worden getransponeerd of hermitisch geconjugeerd binnen de routine, en alle drie matrices kunnen worden gespreid. De gewone matrixvermenigvuldiging AB kan worden uitgevoerd door α in te stellen op één en C op een matrix met alle nullen van de juiste grootte.

Ook inbegrepen in niveau 3 zijn routines voor computergebruik

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

waarbij T een driehoekige matrix is , naast andere functionaliteit.

Vanwege de alomtegenwoordigheid van matrixvermenigvuldigingen in veel wetenschappelijke toepassingen, inclusief voor de implementatie van de rest van niveau 3 BLAS, en omdat er snellere algoritmen bestaan ​​dan de voor de hand liggende herhaling van matrix-vectorvermenigvuldiging, gemmis dit een belangrijk doel van optimalisatie voor BLAS-uitvoerders. Bijvoorbeeld door ontleding van een of beide A , B in blok matrices , gemmkunnen worden recursief uitgevoerd . Dit is een van de redenen om de parameter β op te nemen , zodat de resultaten van eerdere blokken kunnen worden geaccumuleerd. Merk op dat deze decompositie het speciale geval β = 1 vereist waarvoor veel implementaties optimaliseren, waardoor één vermenigvuldiging voor elke waarde van C wordt geëlimineerd . Deze decompositie zorgt voor een betere referentielocatie, zowel in ruimte als in tijd, van de gegevens die in het product worden gebruikt. Dit maakt op zijn beurt gebruik van de cache op het systeem. Voor systemen met meer dan één cacheniveau kan de blokkering een tweede keer worden toegepast in de volgorde waarin de blokken in de berekening worden gebruikt. Beide optimalisatieniveaus worden gebruikt in implementaties zoals ATLAS . Meer recentelijk hebben implementaties van Kazushige Goto aangetoond dat het blokkeren van alleen de L2-cache , gecombineerd met het zorgvuldig afschrijven van het kopiëren naar aaneengesloten geheugen om TLB- missers te verminderen , superieur is aan ATLAS . Een sterk afgestemde implementatie op basis van deze ideeën maakt deel uit van de GotoBLAS , OpenBLAS en BLIS .

Een veel voorkomende variant van gemmis de gemm3m, die een complex product berekent met behulp van "drie reële matrixvermenigvuldigingen en vijf reële matrixoptellingen in plaats van de conventionele vier reële matrixvermenigvuldigingen en twee reële matrixoptellingen", een algoritme vergelijkbaar met het Strassen-algoritme dat voor het eerst werd beschreven door Peter Ungar.

Implementaties

Versnellen

Apple 's framework voor macOS en iOS , inclusief afgestemde versies van BLAS en LAPACK .

Bibliotheken met armprestaties

Arm Performance Libraries , die Arm 64-bit AArch64- gebaseerde processors ondersteunen, verkrijgbaar bij Arm .

ATLAS

Automatisch afgestemde lineaire algebrasoftware , een open source- implementatie van BLAS API's voor C en Fortran 77 .

BLIS

BLAS-achtig Library Instantiation Software-framework voor snelle instantiatie. Geoptimaliseerd voor de meeste moderne CPU's. BLIS is een complete refactoring van de GotoBLAS die de hoeveelheid code die voor een bepaald platform moet worden geschreven, vermindert.

C++ AMP BLAS

De C++ AMP BLAS-bibliotheek is een open source- implementatie van BLAS voor Microsoft's AMP-taalextensie voor Visual C++.

cuBLAS

Geoptimaliseerde BLAS voor op NVIDIA gebaseerde GPU-kaarten, waarvoor weinig extra bibliotheekoproepen nodig zijn.

NVBLAS

Geoptimaliseerde BLAS voor op NVIDIA gebaseerde GPU-kaarten, die alleen functies van niveau 3 bieden, maar als directe vervanging voor andere BLAS-bibliotheken.

clBLAS

Een OpenCL- implementatie van BLAS door AMD. Onderdeel van de AMD Compute Libraries.

clBLAST

Een afgestemde OpenCL- implementatie van de meeste BLAS-api.

Eigen BLAS

Een Fortran 77- en C BLAS-bibliotheek geïmplementeerd bovenop de MPL- gelicentieerde Eigen-bibliotheek , die x86- , x86-64- , ARM- (NEON) - en PowerPC- architecturen ondersteunt.

ESSL

IBM 's Engineering and Scientific Subroutine Library, die de PowerPC- architectuur onder AIX en Linux ondersteunt .

Ga naarBLAS

Kazushige Goto 's BSD-gelicentieerde implementatie van BLAS, speciaal afgestemd voor Intel Nehalem / Atom , VIA Nanoprocessor , AMD Opteron .

GNU wetenschappelijke bibliotheek

Multi-platform implementatie van vele numerieke routines. Bevat een CBLAS-interface.

HP MLIB

HP 's Math-bibliotheek die IA-64 , PA-RISC , x86 en Opteron- architectuur ondersteunt onder HP-UX en Linux .

Intel MKL

De Intel Math Kernel Library , die x86 32-bits en 64-bits ondersteunt, is gratis verkrijgbaar bij Intel . Bevat optimalisaties voor Intel Pentium , Core en Intel Xeon CPU's en Intel Xeon Phi ; ondersteuning voor Linux , Windows en macOS .

WiskundeKeisan

NEC 's wiskundebibliotheek, die NEC SX-architectuur ondersteunt onder SUPER-UX en Itanium onder Linux

Netlib BLAS

De officiële referentie-implementatie op Netlib , geschreven in Fortran 77 .

Netlib CBLAS

Referentie C- interface naar de BLAS. Het is ook mogelijk (en populair) om de Fortran BLAS van C.

OpenBLAS

Geoptimaliseerde BLAS op basis van GotoBLAS, met ondersteuning voor x86- , x86-64- , MIPS- en ARM- processors.

PDLIB/SX

NEC 's Public Domain Mathematical Library voor het NEC SX-4- systeem.

rocBLAS

Implementatie die draait op AMD GPU's via ROCm .

SCSL

SGI 's Scientific Computing Software Library bevat BLAS- en LAPACK-implementaties voor SGI's Irix- werkstations.

Sun Performance-bibliotheek

Geoptimaliseerd BLAS en LAPACK voor SPARC , Core en AMD64 architecturen onder Solaris 8, 9 en 10 en Linux.

uBLAS

Een generieke C++- sjabloonklassebibliotheek die BLAS-functionaliteit biedt. Onderdeel van de Boost-bibliotheek . Het biedt bindingen aan veel hardware-versnelde bibliotheken in een uniforme notatie. Bovendien richt uBLAS zich op de juistheid van de algoritmen met behulp van geavanceerde C++-functies.

Bibliotheken die BLAS . gebruiken

Gordeldier

Armadillo is een C++ lineaire algebra-bibliotheek die streeft naar een goede balans tussen snelheid en gebruiksgemak. Het maakt gebruik van sjabloonklassen en heeft optionele koppelingen naar BLAS/ATLAS en LAPACK. Het wordt gesponsord door NICTA (in Australië) en is gelicentieerd onder een gratis licentie.

LAPACK

LAPACK is een lineaire algebra-bibliotheek van een hoger niveau, gebouwd op BLAS. Net als BLAS bestaat er een referentie-implementatie, maar er zijn veel alternatieven zoals libFlame en MKL.

Mir

Een LLVM- versnelde generieke numerieke bibliotheek voor wetenschap en machine learning, geschreven in D . Het biedt generieke lineaire algebra-subprogramma's (GLAS). Het kan worden gebouwd op een CBLAS-implementatie.

Vergelijkbare bibliotheken (niet compatibel met BLAS)

Elementair

Elemental is open source software voor gedistribueerde geheugendichte en schaars-directe lineaire algebra en optimalisatie.

HASEM

is een C++ sjabloonbibliotheek die lineaire vergelijkingen kan oplossen en eigenwaarden kan berekenen. Het is gelicentieerd onder BSD-licentie.

LAMA

De Library for Accelerated Math Applications ( LAMA ) is een C++-sjabloonbibliotheek voor het schrijven van numerieke solvers gericht op verschillende soorten hardware (bijv. GPU's via CUDA of OpenCL ) op gedistribueerde geheugensystemen , waarbij de hardwarespecifieke programmering wordt verborgen voor de programmaontwikkelaar

MTL4

De Matrix-sjabloonbibliotheek versie 4 is een generieke C++- sjabloonbibliotheek die schaarse en dichte BLAS-functionaliteit biedt. MTL4 zorgt voor een intuïtieve interface (vergelijkbaar met MATLAB ) en brede toepasbaarheid dankzij generieke programmering .

Dunne BLAS

In de loop van de geschiedenis van de bibliotheek zijn verschillende uitbreidingen van BLAS voor het omgaan met schaarse matrices voorgesteld; een kleine set van schaarse matrixkernelroutines werd uiteindelijk in 2002 gestandaardiseerd.

Zie ook

• Lijst met numerieke bibliotheken
• Math Kernel Library , wiskundebibliotheek geoptimaliseerd voor de Intel- architectuur; omvat BLAS, LAPACK
• Numerieke lineaire algebra , het type probleem dat BLAS oplost

Referenties

Verder lezen

• BLAST Forum (2001-08-21), Basic Linear Algebra Subprogramma's Technische (BLAST) Forum Standard , Knoxville, TN: Universiteit van Tennessee
• Dodson, DS; Grimes, RG (1982), "Opmerking over algoritme 539: Basic Linear Algebra Subprogramma's voor Fortran gebruik", ACM Trans. Wiskunde. Zachtw. , 8 (4): 403-404, doi : 10.1145/356012.356020 , S2CID  43081631
• Dodson, DS (1983), "Rectificatie: Opmerking over "Algoritme 539: Basic Linear Algebra Subroutines voor FORTRAN gebruik " ", ACM Trans. Wiskunde. Zachtw. , 9 : 140, doi : 10.1145/356022.356032 , S2CID  22163977
• JJ Dongarra, J. Du Croz, S. Hammarling en RJ Hanson, algoritme 656: een uitgebreide set FORTRAN Basic Linear Algebra Subprogramma's, ACM Trans. Wiskunde. Softw., 14 (1988), blz. 18-32.
• JJ Dongarra, J. Du Croz, IS Duff en S. Hammarling, een set van Level 3 Basic Linear Algebra Subprogramma's, ACM Trans. Wiskunde. Softw., 16 (1990), blz. 1-17.
• JJ Dongarra, J. Du Croz, IS Duff en S. Hammarling, Algorithm 679: Een set van Level 3 Basic Linear Algebra Subprogramma's, ACM Trans. Wiskunde. Softw., 16 (1990), blz. 18-28.

Nieuwe 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, Een bijgewerkte set van Basic Linear Algebra Subprogramma's (BLAS), ACM Trans. Wiskunde. Softw., 28-2 (2002), blz. 135-151.
• J. Dongarra, Basic Linear Algebra Subprogramma's Technical Forum Standard, International Journal of High Performance Applications and Supercomputing, 16(1) (2002), pp. 1-111, en International Journal of High Performance Applications and Supercomputing, 16(2) ( 2002), blz. 115-1999.

Externe links

• BLAS-homepage op Netlib.org
• Veelgestelde vragen over BLAS
• BLAS Quick Reference Guide van LAPACK Users' Guide
• Lawson Oral History Een van de oorspronkelijke auteurs van de BLAS bespreekt de totstandkoming ervan in een interview over mondelinge geschiedenis. Charles L. Lawson Mondeling geschiedenisinterview door Thomas Haigh, 6 en 7 november 2004, San Clemente, Californië. Vereniging voor Industriële en Toegepaste Wiskunde, Philadelphia, PA.
• Dongarra Oral History In een interview over mondelinge geschiedenis onderzoekt Jack Dongarra de vroege relatie van BLAS met LINPACK, de creatie van BLAS-versies van een hoger niveau voor nieuwe architecturen, en zijn latere werk aan het ATLAS-systeem om BLAS automatisch te optimaliseren voor bepaalde machines. Jack Dongarra, Oral history interview door Thomas Haigh, 26 april 2005, University of Tennessee, Knoxville TN. Vereniging voor Industriële en Toegepaste Wiskunde, Philadelphia, PA
• Hoe krijgt BLAS zulke extreme prestaties? Tien naïeve 1000×1000 matrixvermenigvuldigingen (10 ¹⁰ drijvende-komma vermenigvuldigingen) duren 15,77 seconden op een 2,6 GHz-processor; BLAS-implementatie duurt 1,32 seconden.
• Een overzicht van de schaarse elementaire lineaire algebra-subprogramma's: de nieuwe standaard van het BLAS Technical Forum [2]