Vivimos en la era de los macrodatos, pero la mayoría de esos datos son "escasos". Imagine, por ejemplo, una tabla masiva que mapea a todos los clientes de Amazon con todos sus productos, con un "1" para cada productodado que el cliente compró y un "0" en caso contrario. La tabla sería mayormente ceros.
Con datos escasos, los algoritmos analíticos terminan haciendo muchas sumas y multiplicaciones por cero, lo que es un cálculo inútil. Los programadores solucionan esto escribiendo código personalizado para evitar entradas de cero, pero ese código es complejo y generalmente se aplica solo auna gama limitada de problemas.
En la Conferencia de la Asociación de Maquinaria de Computación sobre Sistemas, Programación, Lenguajes y Aplicaciones: Software para la Humanidad SPLASH, investigadores del MIT, la Comisión Francesa de Energías Alternativas y Energía Atómica y Adobe Research presentaron recientemente un nuevo sistema que produce código automáticamenteoptimizado para datos escasos.
Ese código ofrece una aceleración 100 veces superior a los paquetes de software no optimizados existentes. Y su rendimiento es comparable al del 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 "matriz", y un tensor es simplemente un análogo de dimensión superior de una matriz. Si ese AmazonLa tabla también mapeó a los clientes y productos con las calificaciones de los productos de los clientes en el sitio de Amazon y las palabras utilizadas en sus reseñas de productos, el resultado sería un tensor de cuatro dimensiones.
"Las representaciones escasas han estado allí durante 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 artículo. "Pero nadie sabía cómo generar código para ellas automáticamente. La gente descubrió algunas operaciones muy específicas: multiplicar matriz-vector dispersa, multiplicar matriz-vector dispersa más un vector, multiplicar matriz-matriz dispersa, multiplicar matriz-matriz-matriz dispersa. La mayor contribución que hacemos es la capacidad de generarcódigo para cualquier expresión tensorial-álgebra cuando las matrices son escasas ".
Junto a Amarasinghe en el artículo están 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 Francesa de Energías Alternativas y Energía Atómica; y Shoaib Kamil de Adobe Research.
kernels personalizados
En los últimos años, la manipulación matemática de tensores álgebra de tensores se ha vuelto crucial no solo para el análisis de big data 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 de matemáticas ha descompuesto las operaciones de tensor en sus partes constituyentes. Entonces, por ejemplo, si un cálculo requiere que se multipliquen dos tensores y luego se agreguen a un tercero, el software ejecutará su rutina estándar de multiplicación de tensoresen los dos primeros tensores, almacene el resultado y luego ejecute su rutina de adición de tensor estándar.
Sin embargo, en la era de los macrodatos, 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 hace en un kernel, puede hacerlo todo a la vez y puede hacerlo más rápido, en lugar de tener que poner el resultado en la memoria y luego volver a leerlo para poder agregarlo a algode lo contrario ", dice Kjolstad." 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 el aprendizaje automático y el análisis de big data, como las enumeradas por Amarasinghe. Pero el número de kernels posibles es infinito: el kernel para sumar tres tensores, porejemplo, es diferente del kernel para sumar cuatro, y el kernel para agregar tres tensores tridimensionales es diferente del kernel para agregar tres tensores tetradimensionales.
Muchas operaciones de tensor implican multiplicar una entrada de un tensor con una 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 perder una gran cantidad de tiempo sumando y multiplicando ceros.
El código optimizado a mano para tensores dispersos identifica entradas cero y agiliza las operaciones que las involucran, ya sea llevando adelante las entradas distintas de cero en adiciones 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 no se puede omitir ninguna de las entradasPero 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.
entra Taco
Taco agrega todo ese código adicional 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 cual debe importar sus valores. Para cualquier operación dada en dos tensores, Taco construyeun mapa jerárquico que indica, en primer lugar, qué entradas emparejadas de ambos tensores son distintas de cero y, luego, qué entradas de cada tensor están emparejadas con ceros. Todos los pares de ceros simplemente se descartan.
Taco también utiliza un esquema de indexación eficiente para almacenar solo los valores distintos de cero de tensores dispersos. Con cero entradas incluidas, un tensor publicado públicamente de Amazon, que relaciona los números de identificación de los clientes con las compras y los términos descriptivos extraídos de las reseñas, ocupa 107 exabytes dedatos, o aproximadamente 10 veces la capacidad de almacenamiento estimada de todos los servidores de Google. Pero usando el esquema de compresión Taco, solo ocupa 13 gigabytes, lo suficientemente pequeño como para caber en un teléfono inteligente.
Fuente de la historia :
Materiales proporcionado por Instituto de Tecnología de Massachusetts . Original escrito por Larry Hardesty. Nota: el contenido se puede editar por estilo y longitud.
cite esta página :