MigBSP++: balanceamento de carga eficiente para aplica????es paralelas em fases

A migra????o de processos ?? uma t??cnica utilizada no remapeamento de um processo para um processador mais r??pido ou para aproxim??-lo de outros processos com os quais se comunica frequentemente. Esta disserta????o descreve o MigBSP++, um modelo de reescalonamento de processos que utiliza a t??cnica de migra????o para realizar o balanceamento de carga em sistemas paralelos. Direcionado ??s aplica????es do tipo Bulk-Synchronous Parallel (BSP), o modelo apresentado redistribui os processos com o intuito de reduzir o tempo de cada super-passo. De modo similar ao MigBSP, o MigBSP++ combina m??ltiplas m??tricas a fim de decidir as migra????es necess??rias para que o sistema entre em equil??brio sem a interven????o do usu??rio. As m??tricas utilizadas s??o: computa????o, comunica????o e sobrecusto de migra????o. Atrav??s de sua fun????o de decis??o, chamada Potencial de Migra????o (PM), essas m??tricas s??o utilizadas para eleger os processos mais prop??cios a trazer o equil??brio ao sistema. O MigBSP++ responde as quest??es necess??rias para a pol??tica de migra????o de processos: quando realizar a migra????o de processos; quais processos s??o candidatos ?? migra????o e; para onde migrar os processos selecionados. Como contribui????o cient??fica, o MigBSP++ introduz as solu????es para duas quest??es que est??o em aberto no MigBSP: (a) a detec????o de desbalanceamento de carga quando h?? mais processos do que processadores e; (b) a defini????o de quantos processos ir??o migrar de fato. Para a quest??o (a), prop??e-se altera????o do modo de detec????o de desbalanceamento utilizada, observando o tempo total de computa????o de cada processador. Para a quest??o (b) ?? apresentado um algoritmo chamado de Algoritmo de Predi????o BSP (APBSP). Os dados de entrada do APBSP s??o os processos eleitos pela t??cnica de PM e a sa??da ?? uma lista de processos que ir??o, de fato, migrar proporcionando a redu????o do tempo do pr??ximo super-passo. Para demonstrar os resultados da aplica????o deste modelo, foram desenvolvidas duas aplica????es BSP com o aux??lio da biblioteca Adaptive Message Passing Interface (AMPI). Essa ferramenta oferece um arcabou??o uniforme que, atrav??s da migra????o de processos, permite o balanceamento de carga de forma transparente ao usu??rio. Foram desenvolvidas as estrat??gias de balanceamento de carga, baseadas no MigBSP e no MigBSP++, para a realiza????o da compara????o entre elas e com as estrat??gias j?? existentes no sistema. Os resultados apontam que, nos casos onde a granularidade da tarefa ?? maior, os ganhos em tempo de execu????o s??o mais evidentes, podendo ser de at?? 46% em rela????o ?? aplica????o sem balanceamento e de at?? 37% em rela????o ??s estrat??gias nativas do AMPI. Esses n??meros sugerem que o modelo MigBSP++ tem aplica????o pr??tica e pode produzir resultados satisfat??rios.Process migration is a technique used in the remapping of a process to a faster processor or in the approaching from the processes which already have some communication among themselves. This essay describes the MigBSP++, a rescheduling process model that uses the technique of migration to perform load balancing in parallel systems. Directed to the BulkSynchronous Parallel (BSP) applications, the model redistributes the processes with the purpose of reducing the time of each super-step. Similar to MigBSP way, MigBSP++ combines multiple metrics to decide which migrations should be chosen in order to balance the entire system without the user intervention. The metrics used by the model are: computing, communication and extra costs of migration. Through its decision function, called Potential Migration (PM), these metrics are used to choose the most appropriate processes that will balance the system. MigBSP++ answers the questions about the policy process migration issues: when to perform the migration process, which processes are candidates for migration and where to migrate the selected processes. As scientific contribution, MigBSP++ introduces the solutions to two issues that were missing at MigBSP: (a) the detection of imbalance load when there are more processes than processors, and (b) the definition of how many processes will migrate indeed. On the question (a), a change of the mode of detection of imbalance is proposed, noting the total computation time for each processor. On the second question (b) an algorithm called the Prediction Algorithm BSP (PABSP) is presented. The input data of PABSP are elected process by the PM technique and the output is a list of processes that will, indeed, migrate providing a time reduction of the next super-step. To demonstrate the results of applying this model, two BSP applications have been developed with the assistance of Adaptive Message Passing Interface (AMPI) library. This tool provides a uniform framework that, through the migration process, allows a transparent load balancing to the user. Based on MigBSP and MigBSP++, load balancing strategies have been developed for the performance and comparison among new strategies and among the ones which were already in the system.The results indicate that, in cases where the granularity of the task, the gains in runtime are more evident, reaching up to 46% compared to the application without balancing, and 37% when compared to native strategies AMPI. These numbers suggest that the model MigBSP++ has practical application and can produce satisfactory results