Paralelización automática de recurrencias en programas secuenciales numéricos

La programació d'aplicacions en màquines paral·leles és un tema d'interès quant a que cada vegada són més les màquines d'aquest tipus disponibles comercialment.Per a això l'usuari disposa de dues opcions: (a) Utilització de llenguatges de programació amb primitives específiques que permetin expressar i aprofitar les possibilitats que ofereix la màquina. (b) Utilització de compiladors que de forma automàtica siguin capaces d'extreure el paral·lelisme del programa escrit en un llenguatge de programació convencional. La segona opció presenta certs avantatges, com per exemple, que el programador només deu preocupar se de l'algorisme a resoldre i no de les operacions que poden realitzar-se de forma simultània. D'altra banda són moltes les aplicacions escrites en llenguatges convencionals i que la seva paral·lelització automàtica evitaria la seva reprogramació manual. Aquests compiladors poden extreure paral·lelisme a nivell de procediments ("coarse grain"), bucles ("medium grain") o sentències ("fine grain") existint per a això alguns mètodes proposats en la literatura. En programes numèrics gran part del temps s'empra en l'execució de bucles. Per això, la paral·lelització a nivell de bucles ha estat la més estudiada i es basa en una detallada anàlisi de les dependències entre les sentències que ho componen. Aquesta tesi se centra en l'estudi i proposta de tècniques de reestructuració per a bucles en programes seqüencials. Els principals problemes tractats són l'existència de recurrències i sentències condicionals en aquests bucles. L'avaluació del paral·lelisme d'un bucle és considerada en primer lloc i es realitza a partir del grat de dependències entre sentències obtingut en temps de compilació. El paral·lelisme avaluat és una bona mesura de l'eficiència del procés de reestructuració realitzat. Es proposa un mètode, Graph Traverse Scheduling (GTS) que incorporat en un compilador permet l'extracció del màxim paral·lelisme del bucle. La planificació ("scheduling") realitzada es basa en recorreguts a través d'un cicle del graf de dependències que compleix unes determinades característiques. L'aplicació de GTS per a multiprocessadors amb memòria compartida permet l'obtenció de tasques independents o sincronitzades segons les dependències existents. Un dels temes considerats és la reducció del nombre de sincronitzacions explícites afegides així com el compromís entre paral·lelisme obtingut i sincronització. L'aplicació de GTS per a màquines vectorials permet l'obtenció operacions vectorials de màxima longitud a partir de les operacions incloses en bucles seqüencials. GTS pot ser aplicat a altres arquitectures com multiprocessadors amb memòria distribuïda i màquines VLIW, encara que aquests temes no han estat considerats en aquesta tesi. Es comparen els resultats obtinguts per GTS amb els obtinguts aplicant altres tècniques de reestructuració ja existents, basant-se aquesta comparança en dades obtingudes a partir de grafs de dependència aleatòriament generats.La programación de aplicaciones en máquinas paralelas es un tema de interés en cuanto a que cada vez son más las máquinas de este tipo disponibles comercialmente. Para ello el usuario dispone de dos opciones: (a) Utilización de lenguajes de programación con primitivas específicas que permitan expresar y aprovechar las posibilidades que ofrece la máquina. (br) Utilización de compiladores que de forma automática sean capaces de extraer el paralelismo del programa escrito en un lenguaje de programación convencional.La segunda opción presenta ciertas ventajas, como por ejemplo, que el programador sólo debe de preocuparse del algoritmo a resolver y no de las operaciones que pueden realizarse de forma simultánea. Por otro lado son muchas las aplicaciones escritas en lenguajes convencionales y cuya paralelización automática evitaría su reprogramación manual. Estos compiladores pueden extraer paralelismo a nivel de procedimientos ("coarse grain"), bucles ("medium grain") o sentencias ("fine grain") existiendo para ello algunos métodos propuestos en la literatura. Enprogramas numéricos gran parte del tiempo se emplea en la ejecución de bucles. Por ello, la paralelización a nivel de bucles ha sido la más estudiada y se basa en un detallado análisis de las dependencias entre las sentencias que lo componen. Esta tesis se centra en el estudio y propuesta de técnicas de restructuración para bucles en programas secuenciales. Los principales problemas tratados son la existencia de recurrencias y sentencias condicionales en estos bucles. La evaluación del paralelismo de un bucle es considerada en primer lugar y se realiza a partir del grato de dependencias entre sentencias obtenido en tiempo de compilación. El paralelismo evaluado es una buena medida de la eficiencia del proceso de reestructuración realizado. Se propone un método, Graph Traverse Scheduling (GTS) que incorporado en un compilador permite la extracción del máximo paralelismo del bucle. El "scheduling' realizado se basa en recorridos a través de un ciclo del grafo de dependencias que cumple unas determinadas características.La aplicación de GTS para multiprocesadores con memoria compartida permite la obtención de tareas independientes o sincronizadas según las dependencias existentes. Uno de los temas considerados es la reducción del número de sincronizaciones explícitas añadidas así como el compromiso entre paralelismo obtenido y sincronización. La aplicación de GTS para máquinas vectoriales permite la obtención operaciones vectoriales de máxima longitud a partir de las operaciones incluidas en bucles secuenciales. GTS puede ser aplicado a otras arquitecturas como multiprocesadores con memoria distribuida y máquinas VLIW, aunque estos temas no han sido considerados en esta tesis. Se comparan los resultados obtenidos por GTS con los obtenidos aplicando otras técnicas de reestructuración ya existentes, basándose esta comparación en datos obtenidos a partir de gráfos de dependencia aleatoriamente generados.Vectorizing and parallelizing compilers exist today for high performance vector and parallel computers in order to execute efficiently sequential programs written in convencional languages such as FORTRAN. In this thesis the author studies and proposes methods for restructuring recurrences as the main problem in such restructuring compilers. The method presented extracts the maximum parallelism or vector operations out of DO loops with tight recurrences including or no conditional statements. The method is named Graph Traverse Scheduling (GTS) and it is devised for producing code for shared memory multiprocessor systems or vector machines. The method is presented for single nested loops including one or several recurrences; the author also shows how parallel and vector code can be generated. Based on the dependence graph, the author first presents its parallelism and vector length evaluation as loop characteristies that will determine the restructuring process. Then the author presentes the application of GTS in order to distribute iterations of a recurrence between tasks or to generate vector operations of a given length. When this methods is applied for parallel code generation, dependences not inciuded in the sequential execution of each task must be explicitely synchronized. Therefore, hardware support for fast synchronization is assumed in the target architecture. When GTS is applied for vector code generation, a sequential loop of vector operations is obtained. Finally the author performs a brief comparison of the resuits btained by the method presentes and other existing methods used restructuring recurrences in sequential loops