Software de álgebra lineal ajustado automáticamente

Automatically Tuned Linear Algebra Software ( ATLAS ) es una biblioteca de software para álgebra lineal . Proporciona una implementación madura de código abierto de las API de BLAS para C y FORTRAN 77 .

ATLAS se recomienda a menudo como una forma de generar automáticamente una biblioteca BLAS optimizada . Si bien su rendimiento suele ser inferior al de las bibliotecas especializadas escritas para una plataforma de hardware específica , suele ser la primera o incluso la única implementación optimizada de BLAS disponible en nuevos sistemas y supone una gran mejora con respecto al BLAS genérico disponible en Netlib . Por este motivo, ATLAS se utiliza a veces como una línea de base de rendimiento para la comparación con otros productos.

ATLAS funciona en la mayoría de los sistemas operativos tipo Unix y en Microsoft Windows (utilizando Cygwin ). Se publica bajo una licencia de estilo BSD sin cláusula de publicidad y muchas aplicaciones matemáticas conocidas, como MATLAB , Mathematica , Scilab , SageMath y algunas compilaciones de GNU Octave , pueden utilizarlo.

ATLAS proporciona una implementación completa de las API de BLAS, así como algunas funciones adicionales de LAPACK , una biblioteca de nivel superior creada sobre BLAS. En BLAS, la funcionalidad se divide en tres grupos denominados niveles 1, 2 y 3.

• El nivel 1 contiene operaciones vectoriales de la forma

${\displaystyle \mathbf {y} \leftarrow \alpha \mathbf {x} +\mathbf {y} \!}$

así como productos puntuales escalares y normas vectoriales , entre otras cosas.

• El nivel 2 contiene operaciones matriz-vector de la forma

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

así como resolver con siendo triangular, entre otras cosas.${\displaystyle T\mathbf {x} =\mathbf {y} }$${\displaystyle \mathbf {x}}$${\estilo de visualización T}$

• El nivel 3 contiene operaciones matriz-matriz, como la ampliamente utilizada operación de multiplicación de matrices generales (GEMM).

${\displaystyle C\leftarrow \alfa AB+\beta C\!}$

así como resolver matrices triangulares , entre otras cosas.${\displaystyle B\leftarrow \alpha T^{-1}B}$${\estilo de visualización T}$

El enfoque de optimización se denomina Optimización Empírica Automatizada de Software (AEOS), que identifica cuatro enfoques fundamentales para la optimización asistida por computadora, de los cuales ATLAS emplea tres: ^[1]

1. Parametrización : búsqueda en el espacio de parámetros de una función, utilizada para factor de bloqueo, borde de caché, etc.
2. Implementación múltiple: búsqueda a través de varios enfoques para implementar la misma función, por ejemplo, compatibilidad con SSE antes de que los intrínsecos los hicieran disponibles en código C
3. Generación de código : programas que escriben programas incorporando todo el conocimiento que pueden sobre lo que producirá el mejor rendimiento para el sistema.

• La optimización del nivel 1 de BLAS utiliza parametrización e implementación múltiple

Cada función BLAS de nivel 1 de ATLAS tiene su propio núcleo. Dado que sería difícil mantener miles de casos en ATLAS, hay poca optimización específica de la arquitectura para BLAS de nivel 1. En su lugar, se confía en la implementación múltiple para permitir la optimización del compilador para producir una implementación de alto rendimiento para el sistema.

• La optimización del BLAS de nivel 2 utiliza parametrización e implementación múltiple

Con datos y operaciones a realizar la función suele estar limitada por el ancho de banda de la memoria, y por lo tanto no hay mucha oportunidad de optimización$Estilo de visualización N^{2}}$$Estilo de visualización N^{2}}$

Todas las rutinas del BLAS de nivel 2 de ATLAS se construyen a partir de dos núcleos BLAS de nivel 2:

• GEMV: actualización de multiplicación de matriz por vector:

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

• GER: actualización general de rango 1 de un producto externo:

${\displaystyle A\leftarrow \alpha \mathbf {x} \mathbf {y} ^{T}+A\!}$

• La optimización del BLAS de nivel 3 utiliza la generación de código y las otras dos técnicas

Dado que tenemos operaciones solo con datos, existen muchas oportunidades de optimización.$Estilo de visualización N3$$Estilo de visualización N^{2}}$

La mayor parte del BLAS de nivel 3 se deriva de GEMM , por lo que ese es el enfoque principal de la optimización.

${\displaystyle O(n^{3})}$Operaciones vs. datos${\displaystyle O(n^{2})}$

La intuición de que las operaciones dominarán sobre los accesos a los datos sólo funciona para matrices aproximadamente cuadradas. La medida real debería ser algún tipo de relación entre el área de la superficie y el volumen. La diferencia se vuelve importante para matrices muy no cuadradas. ${\estilo de visualización n^{3}}$${\estilo de visualización n^{2}}$

Copiar las entradas permite organizar los datos de una manera que proporciona un acceso óptimo para las funciones del kernel, pero esto implica asignar espacio temporal y una lectura y escritura adicional de las entradas.

Entonces, la primera pregunta que enfrenta GEMM es: ¿puede permitirse copiar las entradas?

En ese caso,

• Colocar en bloque el formato principal con buena alineación
• Aproveche los kernels aportados por los usuarios y la limpieza
• Manejar los casos de transposición con la copia: convertir todo en TN (transposición - no transposición)
• Tratar con α en la copia

Si no,

• Utilice la versión sin copia
• No haga suposiciones sobre el paso de la matriz A y B en la memoria
• Manejar todos los casos de transposición explícitamente
• No hay garantía sobre la alineación de los datos
• Admite un código específico
• Corre el riesgo de tener problemas con el TLB , malos pasos, etc.

La decisión real se toma a través de una heurística simple que busca "casos flacos".

Para el bloqueo de caché de segundo nivel se utiliza un único parámetro de borde de caché. El nivel superior elige un orden para recorrer los bloques: ijk, jik, ikj, jki, kij, kji . No es necesario que sean el mismo orden, ya que el producto se realiza dentro de un bloque.

Los órdenes elegidos normalmente son ijk o jik . Para jik, la situación ideal sería copiar A y el panel ancho NB de B. Para ijk, intercambiar el rol de A y B.

Elegir el mayor de M o N para el bucle externo reduce el espacio ocupado por la copia. Pero para un valor de K grande, ATLAS ni siquiera asigna una cantidad de memoria tan grande. En su lugar, define un parámetro, Kp , para dar el mejor uso de la caché L2. Los paneles están limitados a Kp en longitud. Primero intenta asignar (en el caso de jik ) . Si eso falla, intenta . (Si eso falla, utiliza la versión sin copia de GEMM, pero este caso es poco probable para elecciones razonables de borde de caché). Kp es una función del borde de caché y NB . ${\displaystyle M\cdot p+NB\cdot Kp+NB\cdot NB}$${\displaystyle 2\cdot Kp\cdot NB+NB\cdot NB}$

Al integrar ATLAS BLAS con LAPACK, una consideración importante es la elección del factor de bloqueo para LAPACK. Si el factor de bloqueo de ATLAS es lo suficientemente pequeño, el factor de bloqueo de LAPACK podría configurarse para que coincida con el de ATLAS.

Para aprovechar la factorización recursiva, ATLAS proporciona rutinas de reemplazo para algunas rutinas LAPACK. Estas simplemente sobrescriben las rutinas LAPACK correspondientes de Netlib .

La instalación de ATLAS en una plataforma particular es un proceso desafiante que generalmente lo realiza un proveedor de sistemas o un experto local y lo pone a disposición de un público más amplio.

En muchos sistemas, están disponibles los parámetros arquitectónicos predeterminados; estos son, en esencia, búsquedas guardadas más los resultados de los ajustes manuales. Si los valores predeterminados de la arquitectura funcionan, es probable que obtengan un rendimiento entre un 10 y un 15 % mejor que la búsqueda de instalación. En dichos sistemas, el proceso de instalación se simplifica enormemente.

• Software de álgebra lineal ajustado automáticamente en SourceForge
• Contribución de los usuarios a ATLAS
• Una guía colaborativa para el desarrollo de ATLAS
• Las preguntas frecuentes tienen enlaces a la Guía de referencia rápida de BLAS y a la Referencia rápida de la API de ATLAS LAPACK
• Microsoft Visual C++ Howto Archivado el 28 de septiembre de 2007 en Wayback Machine para ATLAS