Anar al contingut

Basic Linear Algebra Subprograms

De L'Enciclopèdia, la wikipedia en valencià

Basic Linear Algebra Subprograms (BLAS), en espanyol Subprogramas Bàsics d'Àlgebra Llineal, és una especificació que definix un conjunt de rutines de baix nivell per a realisar operacions comunes d'àlgebra llineal tals com la suma de vectores, multiplicació escalar, producte escalar, combinacions llineals i multiplicació de matrius. Són les rutines estàndar de facto de baix nivell per a biblioteques d'àlgebra llineal, en bindings para C (interfaç CBLAS) i Fortran (interfaç BLAS). Encara que l'especificació de BLAS és general, les implementacions particulars estan a sovint optimisades per a conseguir major acceleració en una màquina o arquitectura particular, de manera que el seu us pot comportar un increment substancial del rendiment. Les implementacions de BLAS es poden aprofitar de l'existència d'hardware especial de punt flotant, tals com a registres vectorials o instruccions SIMD.

Va tindre orige com a biblioteca de Fortran en 1979[1] i el seu interfaç va ser estandardisat pel Fòrum Tècnic BLAS (BLAST), l'últim informe del qual sobre BLAS es pot trobar en el lloc web de netlib.[2] Esta biblioteca es coneix com l'implementació de referència i és de domini públic (a voltes li la coneix de manera confusa com la biblioteca BLAS), encara que no està optimisada en velocitat.


La majoria de les biblioteques que oferixen rutines d'àlgebra llineal s'ajusten a l'interfaç BLAS, lo que permet als usuaris de la biblioteca desenrollar programes independents de la biblioteca BLAS que s'estiga utilisant. Eixemples de biblioteques BLAS inclouen: AMD Core Math Library (ACML), Arm Performance Libraries,[3] ATLAS, Intel Math Kernel Library (MKL) i OpenBLAS. ACML ya no és compatible en el seu productor.[4] ATLAS és una biblioteca portàtil que s'optimisa automàticament per a una arquitectura arbitrària. MKL és una biblioteca de proveïdor de software gratuït[5] i propietària[6] optimisada per a x86 i x86-64 en un émfasis en el rendiment dels processadors Intel.[7] OpenBLAS és una biblioteca de còdic obert que està optimisada manualment per a moltes de les arquitectura populars. Els benchmark de LINPACK es basen en gran mida en la gemm rutina BLAS per a les seues medicions de rendiment.

Moltes aplicacions de software numèric utilisen biblioteques compatibles en BLAS per a realisar càlculs d'àlgebra llineal, com Armadillo, LAPACK, LINPACK, GNU Octave, Mathematica,[8] MATLAB,[9] NumPy,[10] R i Julia.

Antecedents

[editar | editar còdic]

En el advenimiento de la programació numèrica, les biblioteques de subrutina sofisticades es varen tornar útils. Estes biblioteques contindrien subrutina per a operacions matemàtiques comunes d'alt nivell, com a busca de raïls, inversió de matrius i resolució de sistemes d'equacions. L'idioma elegit va ser FORTRAN. La biblioteca de programació numèrica més destacada va ser el Scientific Subroutine Package (SSP) d'IBM.[11] Estes biblioteques de subrutina varen permetre als programadors concentrar-se en els seus problemes específics i evitar tornar a implementar algoritmes coneguts. Les rutines de la biblioteca també serien millors que les implementacions promig; Els algoritmes matriciales, per eixemple, poden usar pivoteo complet per a obtindre una millor precisió numèrica. Les rutines de la biblioteca també tindrien rutines més eficients. Per eixemple, una biblioteca pot incloure un programa per a resoldre una matriu triangular superior. Les biblioteques inclourien versions de precisió simple i doble precisió d'alguns algoritmes.

Inicialment, estes subrutina usaven bucles codificats de forma rígida per a les seues operacions de baix nivell. Per eixemple, si una subrutina necessita realisar una multiplicació de matrius, llavors la subrutina tindria tres bucles anidados. Els programes d'àlgebra llineal tenen moltes operacions comunes de baix nivell (les anomenades operacions "kernel", no relacionades en els sistemes operatius).[12] Entre 1973 i 1977, es varen identificar vàries d'estes operacions del núcleu.[13] Estes operacions del kernel es varen convertir en subrutina definides que les biblioteques matemàtiques podien cridar. Les cridades al núcleu tenien ventages sobre els bucles codificats de forma rígida: la rutina de la biblioteca seria més llegible, hi hauria menys possibilitats d'errors i l'implementació del núcleu podria optimisar-se per a la velocitat. Una especificació per a estes operacions del núcleu usant escalares i vectores, les subrutina d'àlgebra llineal bàsica de nivell 1 (BLAS), es va publicar en 1979.[14] BLAS es va utilisar per a implementar la biblioteca de subrutina d'àlgebra llineal LINPACK.

L'abstracció BLAS permet la personalisació per a un alt rendiment. Per eixemple, LINPACK és una biblioteca de propòsit general que es pot usar en moltes màquines diferents sense modificacions. LINPACK podria usar una versió genèrica de BLAS. Per a obtindre rendiment, diferents màquines poden usar versions personalisades de BLAS. A mida que les arquitectura informàtiques es varen tornar més sofisticades, varen aparéixer les màquines vectorials. BLAS per a una màquina vectorial podria utilisar les operacions vectorials ràpides de la màquina.[15]


Atres funcions de la màquina varen estar disponibles i també podrien explotar-se. En conseqüència, BLAS es va aumentar de 1984 a 1986 en operacions de kernel de nivell 2 que es referien a operacions de matriu de vectores. La jerarquia de la memòria també es va reconéixer com alguna cosa per a explotar. Moltes computadores tenen una memòria caché que és molt més ràpida que la memòria principal; mantindre les manipulacions de la matriu localisades permet un millor us de la caché. En 1987 i 1988, es varen identificar BLAS de nivell 3 per a realisar operacions matriu-matriu. El BLAS de nivell 3 va fomentar els algoritmes de blocs particionados. La biblioteca LAPACK utilisa BLAS de nivell 3.[16]

El BLAS original es referia solament a vectores i matrius densament almagasenats. S'han abordat atres extensions de BLAS, com per a matrius disperses.[17]

ATLAS

[editar | editar còdic]

El Automatically Tuned Linear Algebra Software (ATLAS), en espanyol: software d'àlgebra llineal sintonizado automàticament, busca una implementació BLAS en major rendiment. ATLAS definix moltes operacions BLAS en térmens d'algunes rutines centrals i després intenta adaptar automàticament les rutines centrals per a tindre un bon rendiment. Es realisa una busca per a elegir bons tamanys de bloc. Els tamanys dels blocs poden dependre del tamany i l'arquitectura de la memòria caché de la computadora. També es realisen proves per a vore si la còpia de matrius i vectores millora el rendiment. Per eixemple, pot ser ventajós copiar arguments per a que estiguen alineats en la llínea de caché per a que les rutines proporcionades per l'usuari puguen utilisar instruccions SIMD.

Funcionalitat

[editar | editar còdic]

La funcionalitat BLAS es classifica en tres conjunts de rutines anomenades "nivells", que corresponen tant a l'orde cronològic de definició i publicació, com al grau del polinomi en les complexitat dels algoritmes; Les operacions de BLAS de nivell 1 generalment prenen temps llineal, O(n), operacions de nivell 2 temps quadràtic i operacions de nivell 3 temps cúbic.[18]<span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: Plantilla:R/where  Les implementacions modernes de BLAS solen proporcionar els tres nivells.

Nivell 1

[editar | editar còdic]

Este nivell consta de totes les rutines descrites en la presentació original de BLAS (1979),[1] que definia solament operacions vectorials en matrius escalonades : productes escalares, normes vectorials, una adició vectorial generalisada de la forma

𝒚←α𝒙+𝒚

(cridat "axpy") i moltes atres operacions.

Nivell 2

[editar | editar còdic]

Este nivell conté operacions matriu-vector que inclouen, entre atres coses, una multiplicació matriu-vector generalisada (gemv):

𝒚←α𝑨𝒙+β𝒚

aixina com un solucionador de x en l'equació llineal

𝑻𝒙=𝒚

sent T triangular. El disseny de el BLAS de nivell 2 es va iniciar en 1984 i els resultats es varen publicar en 1988. Les subrutina de nivell 2 estan especialment destinades a millorar el rendiment dels programes que utilisen BLAS en processadors vectorials, a on els BLAS de nivell 1 són subóptimos "perque oculten la naturalea matricial-vector de les operacions del compilador".[19]

Nivell 3

[editar | editar còdic]

Este nivell, publicat formalment en 1990,[18] conté operacions matriu-matriu, inclosa una " multiplicació general de matrius " (gemm), de la forma

𝑪←α𝑨𝑩+β𝑪

a on A i B es poden transponer opcionalment o conjugar hermitian dins de la rutina i les tres matrius poden ser escalonades. La multiplicació de matrius ordinària A B es pot realisar establint α en un i C en una matriu de tots zeros del tamany apropiat.

També s'inclouen en el Nivell 3 rutines per a resoldre

𝑩←α𝑻−1𝑩

a on T és una matriu triangular, entre atres funcionalitats.

Per l'ubiqüitat de les multiplicacions de matrius en moltes aplicacions científiques, inclosa l'implementació del restant de el BLAS de nivell 3, i degut a que existixen algoritmes més ràpits més allà de la repetició òbvia de la multiplicació de matrius i vectores, gemm és un objectiu principal d'optimisació per a Implementadores BLAS. Per eixemple, en descompondre un o abdós de A, B en matrius de blocs, gemm es pot implementar de forma recursiva. Esta és una de les motivacions per a incloure el paràmetro β, per a que es puguen acumular els resultats dels blocs anteriors. Tinga en conte que esta descomposició requerix el cas especial β = 1 que optimisen moltes implementacions, eliminant aixina una multiplicació per cada valor de C Esta descomposició permet una millor localitat de referència tant en l'espai com en el temps de les senyes utilisades en el producte. Açò, a la seua volta, aprofita la caché del sistema.[20] Per a sistemes en més d'un nivell de caché, el bloqueig es pot aplicar una segona volta a l'orde en que s'utilisen els blocs en el càlcul. Abdós nivells d'optimisació s'utilisen en implementacions com ATLAS. Més recentment, les implementacions de Kazushige Goto han demostrat que el bloqueig sol per a la caché L2, combinat en una cuidadosa amortisació de la còpia a la memòria contigua per a reduir les falles de TLB, és superior a ATLAS. Una implementació altament ajustada basada en estes idees és part de GotoBLAS, OpenBLAS i BLIS.

Una variació comuna de Plantilla:Code és Plantilla:Code, que calcula un producte complex usant "tres multiplicacions de matrius reals i cinc adició de matrius reals en lloc de les quatre multiplicacions de matrius reals convencionals i dos adició de matrius reals", un algoritme similar al algoritme de Strassen descrit per primera volta per Peter. Ungar.[21]

Vore també

[editar | editar còdic]

Referències

[editar | editar còdic]
  1. ↑ 1,0 1,1 ACM Trans. Math. Softw..5(3)
    308–323.doi:10.1145/355841.355847.
  2. ↑ «BLAS Technical Forum». netlib.org. Consultat el 2017-07-07.
  3. ↑ «Arm Performance Libraries». Arm. Consultat el 2020-06-02.
  4. ↑ «ACML – AMD Core Math Library». AMD. Archivat des d'el original, el 2015-09-05. Consultat el 2015-08-26.
  5. ↑ «No Cost Options for Intel Math Kernel Library (MKL), Support yourself, Royalty-Free». Intel. Consultat el 2015-08-31.
  6. ↑ «Intel Math Kernel Library (Intel MKL)». Intel. Consultat el 2015-08-25.
  7. ↑ «Optimization Notice». Intel. Consultat el 2013-04-10.
  8. ↑ MSOR Connections.The Higher Education Academy.3(4)
  9. ↑ Cleve Moldre. «MATLAB Incorporates LAPACK». MathWorks. Archivat des d'el original, el 29 de maig de 2023. Consultat el 2013-10-26.
  10. ↑ Computing in Science and Engineering.13(2)
    22–30.doi:10.1109/MCSE.2011.37.
  11. ↑ (2000).Mathematics and Computers in Simulation.54(4–5)
    227–241.doi:10.1016/S0378-4754(00)00185-3.
  12. ↑ Even the SSP (which appeared around 1966) had some basic routines such as RADD (add rows), CADD (add columns), SRMA (scale row and add to another row), and RINT (row interchange). These routines apparently were not used as kernel operations to implement other routines such as matrix inversion. See Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..
  13. ↑ BLAST Forum, 2001, p. 1.
  14. ↑ Lawson et al., 1979.
  15. ↑ Si ben els processadors vectorials finalment varen caure en desgràcia, les instruccions vectorials en les CPU modernes són essencials per a un rendiment òptim en les rutines BLAS.
  16. ↑ BLAST Forum, 2001, pp. 1–2.
  17. ↑ BLAST Forum, 2001, p. 2.
  18. ↑ 18,0 18,1 ACM Transactions on Mathematical Software.16(1)
    1–17.ISSN 0098-3500.doi:10.1145/77626.79170.
  19. ↑ ACM Trans. Math. Softw..14
    1–17.doi:10.1145/42288.42291.
  20. ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
  21. ↑ ACM Transactions on Mathematical Software.44(1)
    1–36.doi:10.1145/3086466.


Referències

[editar | editar còdic]


Obtingut de «https://www.lenciclopedia.org/w/index.php?title=Basic_Linear_Algebra_Subprograms&oldid=831530»