Un nuevo sistema informático MIT acelera los cálculos que involucran “tensores dispersos”, matrices de datos multidimensionales que consisten principalmente en ceros. El sistema para realizar “álgebra de tensor” ofrece aceleraciones de 100 veces sobre los paquetes de software anteriores.
Vivimos en la era del big data, pero la mayoría de esos datos son “escasos”. Imagínese, por ejemplo, una tabla masiva que mapeó a todos los clientes de Amazon contra todos sus productos, con un “1” por cada producto que un cliente determinado comprado y un “0” de lo contrario. La tabla sería en su mayoría ceros.
Con escasos datos, los algoritmos analíticos terminan haciendo una gran cantidad de suma y multiplicación por cero, lo que es un cálculo desperdiciado. Los programadores evitan esto al escribir código personalizado para evitar la introducción de cero, pero ese código es complejo y, en general, se aplica solo a un pequeño rango de problemas.
En la Conferencia sobre Sistemas, Programación, Idiomas y Aplicaciones de la Asociación de Informática: Software para la Humanidad (SPLASH), investigadores del MIT, la Comisión de Energías Alternativas y Atómica de Francia y Adobe Research presentaron recientemente un nuevo sistema que produce código optimizado automáticamente para escasa información
Ese código ofrece una aceleración de 100 veces sobre los paquetes de software existentes no optimizados. Y su rendimiento es comparable al de un código meticulosamente optimizado a mano para operaciones específicas de datos dispersos, mientras que requiere mucho menos trabajo por parte del programador.
El sistema se llama Taco, para compilador de álgebra tensorial. En el lenguaje informático, una estructura de datos como la tabla de Amazon se llama una “matriz”, y un tensor es simplemente un análogo de mayor dimensión de una matriz. Si esa tabla de Amazon también asignó clientes y productos a las calificaciones de productos de los clientes en el sitio de Amazon y las palabras utilizadas en sus revisiones de productos, el resultado sería un tensor de cuatro dimensiones.
“Las representaciones dispersas han estado ahí por más de 60 años”, dice Saman Amarasinghe, profesor de ingeniería eléctrica e informática (EECS) del MIT y autor principal del nuevo documento. “Pero nadie sabía cómo generar código para ellos automáticamente”. Las personas descubrieron algunas operaciones muy específicas: escasa multiplicación matriz-vector, multiplicación escasa matriz-vector más un vector, multiplicación matriz-matriz dispersa, multiplicación escasa matriz-matriz-matriz. La mayor contribución que hacemos es la capacidad de generar código para cualquier expresión de tensor-álgebra cuando las matrices son dispersas “.
Junto a Amarasinghe en el periódico, se encuentra el primer autor Fredrik Kjolstad, un estudiante graduado del MIT en EECS; Stephen Chou, también estudiante graduado en EECS; David Lugato de la Comisión de Energías Alternativas y Energía Atómica de Francia; y Shoaib Kamil de Adobe Research.
Núcleos personalizados
En los últimos años, la manipulación matemática de los tensores, álgebra tensorial, se ha vuelto crucial no solo para el análisis de datos grandes sino también para el aprendizaje automático. Y ha sido un elemento básico de la investigación científica desde la época de Einstein.
Tradicionalmente, para manejar el álgebra tensorial, el software matemático ha descompuesto las operaciones del tensor en sus partes constituyentes. Así, por ejemplo, si un cálculo requiere dos tensores para ser multiplicadas y luego se añadió a una tercera, el software se ejecute la rutina de tensor de la multiplicación de serie en los dos primeros tensores, almacenar el resultado, y luego seguir su rutina Además tensor estándar.
Sin embargo, en la era del big data, este enfoque consume demasiado tiempo. Para una operación eficiente en conjuntos de datos masivos, explica Kjolstad, cada secuencia de operaciones de tensor requiere su propio “núcleo” o plantilla computacional.
“Si lo haces en un kernel, puedes hacerlo todo de una vez, y puedes hacerlo más rápido, en lugar de tener que poner el resultado en la memoria y luego volver a leerlo para que puedas agregarlo a otra cosa, “Kjolstad dice. “Puedes hacerlo en el mismo ciclo”.
Los investigadores en ciencias de la computación han desarrollado kernels para algunas de las operaciones de tensor más comunes en aprendizaje automático y análisis de big-data, como los enumerados por Amarasinghe. Pero la cantidad de granos posibles es infinita: el núcleo para sumar tres tensores, por ejemplo, es diferente del núcleo para sumar cuatro, y el núcleo para agregar tres tensores tridimensionales es diferente del núcleo para agregar tres cuatro, tensores dimensionales
Muchas operaciones de tensor implican multiplicar una entrada de un tensor por uno de otro. Si cualquiera de las entradas es cero, también lo es su producto, y los programas para manipular matrices grandes y dispersas pueden desperdiciar una gran cantidad de tiempo sumando y multiplicando ceros.
El código optimizado a mano para tensores dispersos identifica entradas nulas y optimiza las operaciones que las involucran, ya sea llevando adelante las entradas distintas de cero añadiendo u omitiendo las multiplicaciones por completo. Esto hace que las manipulaciones de los tensores sean mucho más rápidas, pero requiere que el programador haga mucho más trabajo.
El código para multiplicar dos matrices (un tipo simple de tensor, con solo dos dimensiones, como una tabla) podría, por ejemplo, tomar 12 líneas si la matriz está llena (lo que significa que ninguna de las entradas se puede omitir). Pero si la matriz es escasa, la misma operación puede requerir 100 líneas de código o más, para rastrear omisiones y elisiones.
Entrar en Taco
Taco agrega todo ese código extra automáticamente. El programador simplemente especifica el tamaño de un tensor, ya sea completo o escaso, y la ubicación del archivo desde el que debe importar sus valores. Para cualquier operación dada en dos tensores, Taco construye un mapa jerárquico que indica, primero, qué entradas emparejadas de ambos tensores son distintas de cero y, luego, qué entradas de cada tensor se emparejan con ceros. Todos los pares de ceros simplemente descarta.
Taco también usa un esquema de indexación eficiente para almacenar solo los valores distintos de cero de tensores dispersos. Con cero entradas incluidas, un tensor de Amazon lanzado públicamente, que mapea los números de identificación de los clientes contra las compras y los términos descriptivos seleccionados de las revisiones, toma 107 exabytes de datos, o aproximadamente 10 veces la capacidad de almacenamiento estimada de todos los servidores de Google. Pero con el esquema de compresión de Taco, ocupa solo 13 gigabytes, lo suficientemente pequeño como para caber en un teléfono inteligente.
“Muchos grupos de investigación en las últimas dos décadas han intentado resolver el problema de optimización del compilador y generación de código para cálculos de matrices dispersas, pero han progresado poco”, dice Saday Sadayappan, profesor de informática e ingeniería en la Universidad Estatal de Ohio, quien no estuvo involucrado en la investigación. “Los recientes desarrollos de Fred y Saman representan un avance fundamental en este problema abierto de larga data”.
“Su compilador ahora permite a los desarrolladores de aplicaciones especificar cómputos de matriz dispersiva o de tensor muy complejos en una notación de alto nivel muy fácil y conveniente, a partir de la cual el compilador genera automáticamente código muy eficiente”, continúa. “Para varios cómputos dispersos, el código generado del compilador ha demostrado ser comparable o mejor que las implementaciones manuales minuciosamente desarrolladas. Esto tiene el potencial de ser un verdadero cambio de juego. Es uno de los avances más interesantes en los últimos tiempos en el área de optimización de compiladores “.
Fuente: MIT