En los chips informáticos actuales, la gestión de la memoria se basa en lo que los científicos informáticos llaman el principio de localidad: si un programa necesita una porción de datos almacenados en alguna ubicación de la memoria, probablemente también necesite los fragmentos vecinos.
Pero esa suposición se rompe en la era de los grandes datos, ahora que los programas informáticos actúan con más frecuencia en unos pocos elementos de datos dispersos arbitrariamente en grandes conjuntos de datos. Dado que la obtención de datos de sus principales bancos de memoria es el principal cuello de botella de rendimiento en los chips actuales, tener que buscarlo con más frecuencia puede reducir drásticamente la ejecución del programa.
Esta semana, en la Conferencia Internacional sobre Arquitecturas Paralelas y Técnicas de Compilación, los investigadores del Laboratorio de Ciencias de la Computación e Inteligencia Artificial CSAIL del MIT presentan un nuevo lenguaje de programación, llamado Milk, que permite a los desarrolladores de aplicaciones administrar la memoria de manera más eficiente en programas que tratancon puntos de datos dispersos en grandes conjuntos de datos.
En las pruebas realizadas en varios algoritmos comunes, los programas escritos en el nuevo idioma fueron cuatro veces más rápidos que los escritos en los idiomas existentes. Pero los investigadores creen que un mayor trabajo producirá ganancias aún mayores.
La razón por la cual los grandes conjuntos de datos actuales plantean problemas para las técnicas de gestión de memoria existentes, explica Saman Amarasinghe, profesor de ingeniería eléctrica y ciencias de la computación, no es tanto que sean tan grandes como lo que los científicos informáticos llaman "escasos".Es decir, con grandes datos, la escala de la solución no necesariamente aumenta proporcionalmente con la escala del problema.
"En entornos sociales, solíamos ver problemas más pequeños", dice Amarasinghe. "Si nos fijamos en las personas en este edificio [CSAIL], todos estamos conectados. Pero si nos fijamos en la escala del planeta, yo noescale mi número de amigos. El planeta tiene miles de millones de personas, pero todavía tengo solo cientos de amigos. De repente, tienes un problema muy escaso ".
De manera similar, dice Amarasinghe, un librero en línea con, digamos, 1,000 clientes podría querer proporcionar a sus visitantes una lista de sus 20 libros más populares. Sin embargo, no se sigue que un librero en línea con un millón de clientes quierapara proporcionar a sus visitantes una lista de sus 20,000 libros más populares.
Pensando localmente
Los chips de computadora de hoy no están optimizados para datos escasos; de hecho, lo contrario es cierto. Debido a que la obtención de datos del banco de memoria principal del chip es lenta, cada núcleo o procesador de un chip moderno tiene su propio "caché"un banco de memoria relativamente pequeño, local y de alta velocidad. En lugar de recuperar un solo elemento de datos a la vez de la memoria principal, un núcleo obtendrá un bloque completo de datos. Y ese bloque se selecciona de acuerdo con el principio de localidad.
Es fácil ver cómo funciona el principio de localidad con, por ejemplo, el procesamiento de imágenes. Si el propósito de un programa es aplicar un filtro visual a una imagen, y funciona en un bloque de la imagen a la vez, entonces cuandoun núcleo solicita un bloque, debe recibir todos los bloques adyacentes que su caché puede contener, para que pueda trabajar bloque tras bloque sin obtener más datos.
Pero ese enfoque no funciona si el algoritmo está interesado en solo 20 libros de los 2 millones en la base de datos de un minorista en línea. Si solicita los datos asociados con un libro, es probable que los datos asociados con los 100 libros adyacentesserá irrelevante
Ir a la memoria principal para un solo elemento de datos a la vez es lamentablemente ineficiente. "Es como si cada vez que quisiera una cucharada de cereal, abriera el refrigerador, abra el cartón de leche, vierta una cucharada de leche, cierre elcartón, y póngalo de nuevo en la nevera ", dice Vladimir Kiriansky, estudiante de doctorado en ingeniería eléctrica y ciencias de la computación y primer autor del nuevo artículo. Se le unen Amarasinghe y Yunming Zhang, también estudiante de doctorado en ingeniería eléctrica y ciencias de la computación..
procesamiento por lotes
Milk simplemente agrega algunos comandos a OpenMP, una extensión de lenguajes como C y Fortran que hace que sea más fácil escribir código para procesadores multinúcleo. Con Milk, un programador inserta un par de líneas de código adicionales alrededor de cualquier instrucción que se repita a través de ungran recopilación de datos en busca de una cantidad relativamente pequeña de elementos.El compilador de Milk, el programa que convierte el código de alto nivel en instrucciones de bajo nivel, luego descubre cómo administrar la memoria en consecuencia.
Con un programa Milk, cuando un núcleo descubre que necesita un dato, no lo solicita, y una memoria caché de datos adyacentes, de la memoria principal. En cambio, agrega la dirección del elemento de datos a una listade direcciones almacenadas localmente. Cuando la lista es lo suficientemente larga, todos los núcleos del chip agrupan sus listas, agrupan las direcciones que están cerca una de la otra y las redistribuyen a los núcleos. De esa manera, cada núcleo solicita solo elementos de datos que conocenecesidades y eso se puede recuperar de manera eficiente.
Esa es la descripción de alto nivel, pero los detalles se vuelven más complicados. De hecho, la mayoría de los chips de computadora modernos tienen varios niveles diferentes de cachés, cada uno más grande pero también un poco menos eficiente que el anterior. El compilador de Milk tiene que estar al tanto deno solo una lista de direcciones de memoria, sino también los datos almacenados en esas direcciones, y se baraja regularmente entre los niveles de caché. También tiene que decidir qué direcciones se deben conservar porque se puede acceder nuevamente y cuáles descartar.algoritmo que coreografía este complejo ballet de datos es donde los investigadores ven la esperanza de mayores ganancias de rendimiento.
Fuente de la historia :
Materiales proporcionado por Instituto de Tecnología de Massachusetts . Original escrito por Larry Hardesty. Nota: El contenido puede ser editado por estilo y longitud.
Cite esta página :