Paralelización de bucles basada en recurrencias de Cheduling

Abstract

En este trabajo nos centramos en la extracción del paralelismo de bucles doacross para arquitecturas con paralelismo de medio y de bajo nivel. Se ha trabajado sobre un multiprocesador con memoria compartida, que permite sincronizaciones a bajo nivel, y sobre arquitecturas VLIW y superescalares, más orientadas al ILP, que permiten realizar software pipelining de bucles. El origen de este trabajo es la técnica de paralelización de bucles sobre arquitecturas con paralelismo de granularidad media (concretamente multiprocesadores de memoria compartida y procesadores vectoriales) presentada en una tesis del departamento y denominada GTS (Graph Traverse Scheduling) [Aygu89]. La técnica GTS realiza el scheduling a partir de una recurrència hamiltoniana existente en el grafo de dependencias de un bucle (recurrència que visita todos Jos nodos del grafo una sola vez) y genera el código paralelo/vectorial de forma automática. En el capítulo 2 se presentan las ideas y métodos básicos de la paralelización automática, el concepto de paralelismo por sentencia y la técnica GTS. Las aportaciones se organizan en dos secciones: la primera sección se basa en GTS para multiprocesadores y comprende los capítulos 3 y 4; la segunda sección es la extensión del método para extraer el ILP de los bucles doacross y comprende los capítulos 5, 6, 7 y 8.