Distribucion automatica de datos en multiporocesadores

Resumen

Los modernos multiprocedadores tienden hacia arquitecturas tipo NUMA. Programar estas maquinas requiere un importante esfuerzo por parte del usuario. Numerosos experimentos enla literatura demuestran la improtancia de explotar la localidad de las referencias a memoria en este tipo de arquitecturas. Como lo que nos interesa es explotar paralelismo a nivel de lzao, la localidad se consigue seleccionando las apropiadas distribuciones de iteraciones y datos que se encarguen de alojar en la memoria local de los procesadores los datos requeridos por estos. Seleccionar estas distribuciones y generar el codigo paralelo que las implementa es una tarea ardua que creemos debe dejarse en manos de un paralelizador para que, de manera automatica, género el código paralelo que explota localidad, en cada tipo de arquitectura, sin intervención del usuario. Sin embargo hemos comprobado que en este campo aun queda mucho por hacer. En esta Tesis proponemos un método de distribución automática de iteraciones y datos que cubre importantes aspectos no resueltos aun por las técnicas actuales. En primer lugar, hemos definido una notación que nos permite representar de forma precisa la región de un array que se accede cada iteración de un lazo paralelo. Los hemos llamado descriptor de iteraciones). A partir de esta inforamción, hemos desarrollado un algoritmo de análisis de localidad que identifica cuales sonlas condiciones que deben de verificar las distribuciones de interaciones que seleccionemos para dos anidamientos y las distribuciones de datos que construyamos para estos, de manera que todas las referenica a memoria puedan satifacerse localmente sin comunicaciones. Tras la aplicación de este algoritmo, el paralelizador generan un grafo llamado Grafo de Localidad-Comunicación que representa cuando es posible explotar localidad sin comunicaciones, y cuando no para todos los arrays y en todos los anidamientos. Con la información que simi