Basic Linear Algebra Subprograms (BLAS), en español Subprogramas Básicos de Álgebra Lineal, es una especificación que define un conjunto de rutinas de bajo nivel para realizar operaciones comunes de álgebra lineal tales como la suma de vectores, multiplicación escalar, producto escalar, combinaciones lineales y multiplicación de matrices. Son las rutinas estándar de facto de bajo nivel para bibliotecas de álgebra lineal, con bindings para C (interfaz CBLAS) y Fortran (interfaz BLAS). Aunque la especificación de BLAS es general, las implementaciones particulares están a menudo optimizadas para conseguir mayor aceleración en una máquina o arquitectura particular, de forma que su uso puede conllevar un incremento sustancial del rendimiento. Las implementaciones de BLAS se pueden aprovechar de la existencia de hardware especial de punto flotante, tales como registros vectoriales o instrucciones SIMD.
Tuvo origen como librería de Fortran en 1979 y su interfaz fue estandarizada por el Foro Técnico BLAS (BLAST), cuyo último informe sobre BLAS se puede encontrar en el sitio web de netlib. Esta librería se conoce como la implementación de referencia y es de dominio público (a veces se la conoce de manera confusa como la librería BLAS), aunque no está optimizada en velocidad.
La mayoría de las librerías que ofrecen rutinas de álgebra lineal se ajustan a la interfaz BLAS, lo que permite a los usuarios de la biblioteca desarrollar programas independientes de la biblioteca BLAS que se esté utilizando. Ejemplos de bibliotecas BLAS incluyen: AMD Core Math Library (ACML), Arm Performance Libraries, ATLAS, Intel Math Kernel Library (MKL) y OpenBLAS. ACML ya no es compatible con su productor. ATLAS es una biblioteca portátil que se optimiza automáticamente para una arquitectura arbitraria. MKL es una biblioteca de proveedor de software gratuito y propietaria optimizada para x86 y x86-64 con un énfasis en el rendimiento de los procesadores Intel. OpenBLAS es una biblioteca de código abierto que está optimizada manualmente para muchas de las arquitecturas populares. Los benchmark de LINPACK se basan en gran medida en la gemm rutina BLAS para sus mediciones de rendimiento.
Muchas aplicaciones de software numérico utilizan bibliotecas compatibles con BLAS para realizar cálculos de álgebra lineal, como Armadillo, LAPACK, LINPACK, GNU Octave, Mathematica, MATLAB, NumPy, R y Julia.
Con el advenimiento de la programación numérica, las bibliotecas de subrutinas sofisticadas se volvieron útiles. Estas bibliotecas contendrían subrutinas para operaciones matemáticas comunes de alto nivel, como búsqueda de raíces, inversión de matrices y resolución de sistemas de ecuaciones. El idioma elegido fue FORTRAN. La biblioteca de programación numérica más destacada fue el Scientific Subroutine Package (SSP) de IBM. Estas bibliotecas de subrutinas permitieron a los programadores concentrarse en sus problemas específicos y evitar volver a implementar algoritmos conocidos. Las rutinas de la biblioteca también serían mejores que las implementaciones promedio; Los algoritmos matriciales, por ejemplo, pueden usar pivoteo completo para obtener una mejor precisión numérica. Las rutinas de la biblioteca también tendrían rutinas más eficientes. Por ejemplo, una biblioteca puede incluir un programa para resolver una matriz triangular superior. Las bibliotecas incluirían versiones de precisión simple y doble precisión de algunos algoritmos.
Inicialmente, estas subrutinas usaban bucles codificados de forma rígida para sus operaciones de bajo nivel. Por ejemplo, si una subrutina necesita realizar una multiplicación de matrices, entonces la subrutina tendría tres bucles anidados. Los programas de álgebra lineal tienen muchas operaciones comunes de bajo nivel (las llamadas operaciones "kernel", no relacionadas con los sistemas operativos). Entre 1973 y 1977, se identificaron varias de estas operaciones del núcleo. Estas operaciones del kernel se convirtieron en subrutinas definidas que las bibliotecas matemáticas podían llamar. Las llamadas al núcleo tenían ventajas sobre los bucles codificados de forma rígida: la rutina de la biblioteca sería más legible, habría menos posibilidades de errores y la implementación del núcleo podría optimizarse para la velocidad. Una especificación para estas operaciones del núcleo usando escalares y vectores, las subrutinas de álgebra lineal básica de nivel 1 (BLAS), se publicó en 1979. BLAS se utilizó para implementar la biblioteca de subrutinas de álgebra lineal LINPACK.
La abstracción BLAS permite la personalización para un alto rendimiento. Por ejemplo, LINPACK es una biblioteca de propósito general que se puede usar en muchas máquinas diferentes sin modificaciones. LINPACK podría usar una versión genérica de BLAS. Para obtener rendimiento, diferentes máquinas pueden usar versiones personalizadas de BLAS. A medida que las arquitecturas informáticas se volvieron más sofisticadas, aparecieron las máquinas vectoriales. BLAS para una máquina vectorial podría utilizar las operaciones vectoriales rápidas de la máquina.
Otras funciones de la máquina estuvieron disponibles y también podrían explotarse. En consecuencia, BLAS se aumentó de 1984 a 1986 con operaciones de kernel de nivel 2 que se referían a operaciones de matriz de vectores. La jerarquía de la memoria también se reconoció como algo para explotar. Muchas computadoras tienen una memoria caché que es mucho más rápida que la memoria principal; mantener las manipulaciones de la matriz localizadas permite un mejor uso de la caché. En 1987 y 1988, se identificaron BLAS de nivel 3 para realizar operaciones matriz-matriz. El BLAS de nivel 3 fomentó los algoritmos de bloques particionados. La biblioteca LAPACK utiliza BLAS de nivel 3.
El BLAS original se refería solo a vectores y matrices densamente almacenados. Se han abordado otras extensiones de BLAS, como para matrices dispersas.
El Automatically Tuned Linear Algebra Software (ATLAS), en español: software de álgebra lineal sintonizado automáticamente, busca una implementación BLAS con mayor rendimiento. ATLAS define muchas operaciones BLAS en términos de algunas rutinas centrales y luego intenta adaptar automáticamente las rutinas centrales para tener un buen rendimiento. Se realiza una búsqueda para elegir buenos tamaños de bloque. Los tamaños de los bloques pueden depender del tamaño y la arquitectura de la memoria caché de la computadora. También se realizan pruebas para ver si la copia de matrices y vectores mejora el rendimiento. Por ejemplo, puede ser ventajoso copiar argumentos para que estén alineados en la línea de caché para que las rutinas proporcionadas por el usuario puedan utilizar instrucciones SIMD.
La funcionalidad BLAS se clasifica en tres conjuntos de rutinas llamadas "niveles", que corresponden tanto al orden cronológico de definición y publicación, como al grado del polinomio en las complejidades de los algoritmos; Las operaciones de BLAS de nivel 1 generalmente toman tiempo lineal, O(n), operaciones de nivel 2 tiempo cuadrático y operaciones de nivel 3 tiempo cúbico. Las implementaciones modernas de BLAS suelen proporcionar los tres niveles.
Este nivel consta de todas las rutinas descritas en la presentación original de BLAS (1979), que definía solo operaciones vectoriales en matrices escalonadas : productos escalares, normas vectoriales, una adición vectorial generalizada de la forma
(llamado "axpy") y muchos otras operaciones.
Este nivel contiene operaciones matriz-vector que incluyen, entre otras cosas, una multiplicación matriz-vector generalizada (gemv):
así como un solucionador de x en la ecuación lineal
siendo T triangular. El diseño del BLAS de nivel 2 se inició en 1984 y los resultados se publicaron en 1988. Las subrutinas de nivel 2 están especialmente destinadas a mejorar el rendimiento de los programas que utilizan BLAS en procesadores vectoriales, donde los BLAS de nivel 1 son subóptimos "porque ocultan la naturaleza matricial-vector de las operaciones del compilador".
Este nivel, publicado formalmente en 1990, contiene operaciones matriz-matriz, incluida una " multiplicación general de matrices " (gemm), de la forma
donde A y B se pueden transponer opcionalmente o conjugar hermitian dentro de la rutina y las tres matrices pueden ser escalonadas. La multiplicación de matrices ordinaria A B se puede realizar estableciendo α en uno y C en una matriz de todos ceros del tamaño apropiado.
También se incluyen en el Nivel 3 rutinas para resolver
donde T es una matriz triangular, entre otras funcionalidades.
Debido a la ubicuidad de las multiplicaciones de matrices en muchas aplicaciones científicas, incluida la implementación del resto del BLAS de nivel 3, y debido a que existen algoritmos más rápidos más allá de la repetición obvia de la multiplicación de matrices y vectores, gemm es un objetivo principal de optimización para Implementadores BLAS. Por ejemplo, al descomponer uno o ambos de A, B en matrices de bloques, gemm se puede implementar de forma recursiva. Esta es una de las motivaciones para incluir el parámetro β, para que se puedan acumular los resultados de los bloques anteriores. Tenga en cuenta que esta descomposición requiere el caso especial β = 1 que optimizan muchas implementaciones, eliminando así una multiplicación por cada valor de C Esta descomposición permite una mejor localidad de referencia tanto en el espacio como en el tiempo de los datos utilizados en el producto. Esto, a su vez, aprovecha la caché del sistema. Para sistemas con más de un nivel de caché, el bloqueo se puede aplicar una segunda vez al orden en que se utilizan los bloques en el cálculo. Ambos niveles de optimización se utilizan en implementaciones como ATLAS. Más recientemente, las implementaciones de Kazushige Goto han demostrado que el bloqueo solo para la caché L2, combinado con una cuidadosa amortización de la copia a la memoria contigua para reducir las fallas de TLB, es superior a ATLAS. Una implementación altamente ajustada basada en estas ideas es parte de GotoBLAS, OpenBLAS y BLIS.
Una variación común de gemm es gemm3m, que calcula un producto complejo usando "tres multiplicaciones de matrices reales y cinco adiciones de matrices reales en lugar de las cuatro multiplicaciones de matrices reales convencionales y dos adiciones de matrices reales", un algoritmo similar al algoritmo de Strassen descrito por primera vez por Peter. Ungar.
Se han sugerido varias extensiones de BLAS para manejar matrices dispersas a lo largo de la historia de la biblioteca; un pequeño conjunto de rutinas de kernel de matriz dispersa se estandarizó finalmente en 2002.
Error en la cita: La etiqueta <ref> definida en las <references> con nombre «Kazushige_2008» no se utiliza en el texto anterior.
Error en la cita: La etiqueta <ref> definida en las <references> con nombre «GotoBLAS2» no se utiliza en el texto anterior.
Escribe un comentario o lo que quieras sobre Basic Linear Algebra Subprograms (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)