Imagen: Imágenes de Istockphoto editadas por MIT News

Los gráficos -estructuras de datos que muestran la relación entre objetos- son muy versátiles. Es fácil imaginar un gráfico que represente la red de conexiones de una red social. Pero los gráficos también se utilizan en programas tan diversos como la recomendación de contenidos (¿qué ver a continuación en Netflix?) y la navegación (¿cuál es la ruta más rápida a la playa?). Como resume Ajay Brahmakshatriya: "los gráficos están básicamente en todas partes".

Brahmakshatriya ha desarrollado un software para ejecutar con mayor eficacia las aplicaciones de gráficos en una gama más amplia de hardware informático. El software amplía GraphIt, un lenguaje de programación de grafos de última generación, para que funcione en unidades de procesamiento gráfico (GPU), un hardware que procesa muchos flujos de datos en paralelo. Este avance podría acelerar el análisis de grafos, especialmente en aplicaciones que se benefician del paralelismo de la GPU, como los algoritmos de recomendación.

Brahmakshatriya, estudiante de doctorado del Departamento de Ingeniería Eléctrica y Ciencias de la Computación del MIT y del Laboratorio de Ciencias de la Computación e Inteligencia Artificial, presentará el trabajo en el Simposio Internacional sobre Generación y Optimización de Código que se celebra este mes. Entre los coautores se encuentran el asesor de Brahmakshatriya, el profesor Saman Amarasinghe, así como el profesor asistente de desarrollo profesional de tecnología de software Douglas T. Ross, Julian Shun, el postdoc Changwan Hong, el reciente estudiante de doctorado del MIT Yunming Zhang PhD ´20 (ahora en Google) y Shoaib Kamil, de Adobe Research.

Cuando los programadores escriben código, no hablan directamente con el hardware del ordenador. El propio hardware funciona en binario (1 y 0), mientras que el programador escribe en un lenguaje estructurado de "alto nivel" compuesto por palabras y símbolos. La traducción de ese lenguaje de alto nivel a un binario legible para el hardware requiere programas llamados compiladores. "Un compilador convierte el código en un formato que pueda ejecutarse en el hardware", dice Brahmakshatriya. Uno de estos compiladores, especialmente diseñado para el análisis de gráficos, es GraphIt.

Los investigadores desarrollaron GraphIt en 2018 para optimizar el rendimiento de los algoritmos basados en gráficos, independientemente del tamaño y la forma del gráfico. GraphIt permite al usuario no solo introducir un algoritmo, sino también programar cómo se ejecuta ese algoritmo en el hardware. "El usuario puede ofrecer diferentes opciones de programación hasta que descubra lo que mejor le funciona", dice Brahmakshatriya. "GraphIt genera un código muy especializado adaptado a cada aplicación para que se ejecute de la forma más eficiente posible".

Tanto las nuevas empresas como las compañías tecnológicas establecidas han adoptado GraphIt para ayudar a su desarrollo de aplicaciones gráficas. Pero Brahmakshatriya dice que la primera iteración de GraphIt tenía un defecto: Sólo se ejecuta en unidades centrales de procesamiento o CPU, el tipo de procesador de un ordenador portátil típico.

"Algunos algoritmos son masivamente paralelos", dice Brahmakshatriya, "lo que significa que pueden utilizar mejor el hardware como una GPU que tiene 10.000 núcleos para la ejecución". Señala que algunos tipos de análisis de gráficos, incluidos los algoritmos de recomendación, requieren un alto grado de paralelismo. Por eso, Brahmakshatriya ha ampliado GraphIt para que el análisis de gráficos pueda prosperar en las GPU.

El equipo de Brahmakshatriya conservó la forma en que los usuarios de GraphIt introducen los algoritmos, pero adaptó el componente de programación para una gama más amplia de hardware. "Nuestra principal decisión de diseño al ampliar GraphIt a las GPU fue mantener la representación de los algoritmos exactamente igual", afirma Brahmakshatriya. "En cambio, añadimos un nuevo lenguaje de programación. Así, el usuario puede mantener los mismos algoritmos que había escrito antes [para las CPU], y sólo cambiar la entrada de programación para obtener el código de la GPU".

Esta nueva programación optimizada para GPU da un impulso a los algoritmos de grafos que requieren un alto grado de paralelismo, como los algoritmos de recomendación o las funciones de búsqueda en Internet que examinan millones de sitios web simultáneamente. Para confirmar la eficacia de la nueva extensión de GraphIt, el equipo llevó a cabo 90 experimentos en los que se comparaba el tiempo de ejecución de GraphIt con el de otros compiladores de gráficos de última generación en las GPU. Los experimentos incluían una amplia gama de algoritmos y tipos de gráficos, desde redes de carreteras hasta redes sociales. GraphIt fue el más rápido en 65 de los 90 casos y quedó muy cerca del algoritmo principal en el resto de las pruebas, lo que demuestra su velocidad y versatilidad.

GraphIt "avanza en este campo al conseguir rendimiento y productividad simultáneamente", afirma Adrian Sampson, informático de la Universidad de Cornell que no ha participado en la investigación. "Las formas tradicionales de hacer análisis de gráficos tienen una cosa o la otra: O bien se puede escribir un algoritmo sencillo con un rendimiento mediocre, o bien se puede contratar a un experto para que escriba una implementación extremadamente rápida, pero ese tipo de rendimiento rara vez está al alcance de los simples mortales". La extensión GraphIt es la clave para que la gente común pueda escribir algoritmos abstractos de alto nivel y, sin embargo, obtener un rendimiento de nivel experto en las GPU".

Sampson añade que el avance podría ser especialmente útil en campos que cambian rápidamente: "Un campo apasionante como éste es la genómica, donde los algoritmos evolucionan tan rápidamente que las implementaciones de expertos de alto rendimiento no pueden seguir el ritmo de los cambios. Me entusiasma que los profesionales de la bioinformática tengan en sus manos GraphIt para ampliar los tipos de análisis genómicos que son capaces de hacer".

Brahmakshatriya afirma que la nueva extensión de GraphIt supone un avance significativo en el análisis de gráficos, ya que permite a los usuarios pasar de la CPU a la GPU con un rendimiento de vanguardia con facilidad. "Hoy en día, el campo es una competencia a muerte. Cada día aparecen nuevos frameworks", afirma. Pero subraya que la recompensa por una mínima optimización merece la pena. "Las empresas gastan millones de dólares cada día para ejecutar algoritmos gráficos. Incluso si haces que se ejecuten sólo un 5 por ciento más rápido, estás ahorrando muchos miles de dólares".

Esta investigación ha sido financiada, en parte, por la National Science Foundation, el Departamento de Energía de EE.UU., el Applications Driving Architectures Center y la Defense Advanced Research Projects Agency.

Autor

MIT

Promover la investigación, las innovaciones, la enseñanza y los eventos y las personas de interés periodístico del MIT a la comunidad del campus, los medios de comunicación y el público en general, Comunicar anuncios del Instituto, Publicar noticias de la comunidad para profesores, estudiantes, personal y ex alumnos del MIT. Proporcionar servicios de medios a los miembros de la comunidad, incluido el asesoramiento sobre cómo trabajar con periodistas, Responder a consultas de los medios y solicitudes de entrevistas...