MigCube e MigHull: Heur??sticas para Sele????o Autom??tica de Processos para Migra????o em Aplica????es BSP

Em ambientes paralelos, uma das alternativas para tratar o dinamismo, tanto em n??vel de infraestrutura quanto de aplica????o ?? o uso de migra????o, principalmente em aplica????es que executam em fases utilizando BSP (Bulk Synchronous Parallel). Neste contexto, o modelo de reescalonamento MigBSP foi desenvolvido para tratar da realoca????o de processos em aplica- ????es paralelas. Assim como o modelo BSP, ele considera as tr??s fases de execu????o de uma superetapa: (i) computa????o local, (ii) comunica????o global e (iii) uma barreira de sincroniza- ????o; coletando dados localmente durante a computa????o para efetuar o c??lculo do Potencial de Migra????o (PM) do processo. Com o PM e par??metros adicionais fornecidos no inicio da execu????o da aplica????o, o MigBSP tem condi????es de escolher processos candidatos a migra????o em uma aplica????o paralela executando em um ambiente distribu??do. Entretanto, as duas heur??sticas poss??veis de serem utilizadas hoje, dependem de informa????es fornecidas pelo usu??rio e/ou podem n??o selecionar uma quantidade eficiente de processos no momento do reescalonamento, podendo ser necess??rio v??rias chamadas para balancear o ambiente. Desta forma, esta disserta- ????o apresenta duas novas heur??sticas, MigCube e MigHull. Elas utilizam o MigBSP e efetuam a sele????o autom??tica de processos candidatos ?? migra????o sem a interfer??ncia do programador. As informa????es fornecidas pelo MigBSP s??o utilizadas nas heur??sticas, a combina????o das tr??s m??tricas mensurados, posicionadas em um plano tridimensional, define cada processo como um ponto no espa??o que possui as coordenadas x, y e z, onde cada eixo representa uma m??- trica para tomada de decis??o. A heur??stica MigCube monta um cubo a partir das m??dias das dist??ncias entre os pontos, utilizando o processo com o maior PM como centro do cubo. A heur??stica MigHull segue a defini????o da Envolt??ria Convexa, tentando envolver todos os pontos, por??m utilizando duas adapta????es que se fazem necess??rias para a aplica????o neste trabalho. O MigBSP foi desenvolvido no simulador SimGrid, e este segue sendo utilizado para a cria????o das duas heur??sticas apresentadas nesta disserta????o. Nos testes realizados neste simulador, foi poss??vel verificar um ganho de at?? 45% no tempo de execu????o da aplica????o utilizando a heur??stica MigHull, e at?? 42% utilizando a MigCube, quando comparado a aplica????o sem o modelo de migra????o. Por??m, em simula????es com um maior n??mero de processos, este ganho tende a cair, j?? que um dos maiores problemas do BSP e aplica????es que executam em grades ?? o tempo de sincroniza????o de tarefas, ou seja, quanto mais processos, maior a necessidade de sincroniza????o, e mesmo o balanceamento dos processos acaba tendo um resultado prejudicado.In a parallel environment, one of the alternatives to address the dynamism, both at the infrastructure and application levels, is the use of migration, mostly with applications that execute in steps using BSP (Bulk Synchronous Parallel). In this context, the rescheduling model MigBSP was developed to deal with processes reallocation in parallel applications. As BSP model, MigBSP uses the three steps of a superstep: (i) computation, (ii) communication and (iii) a synchronization barrier; collecting local data during the computation step, to compute the processes??? Potential of Migration (PM). With the PM and additional parameters provided in the beginning of the application???s execution, MigBSP have conditions to choose the processes candidate to migrate in a parallel application running in a distributed system. However, the two heuristics possible to be used today depend of information provided by the user and/or may not select the proper quantity of processes in the rescheduling moment, being necessary many executions to balance the environment. This way, this dissertation present two new heuristics, MigCube and MigHull. They make use of MigBSP, and automatically will choose the processes to migrate without user interference. The information provided by MigBSP are used in the heuristics, the combination of the three measured metrics, positioned in a three-dimensional space, defines each process as a point in space and has the coordinates x, y e z, where each axis represents a metric for decision making. The MigCube heuristic build a cube from the average of the distances between points, using the process with the highest PM as the center of the cube. The MigHull follows the definition of a Convex Hull, trying to involve all points, but using two adaptations that are necessary to implement this work. The MigBSP was developed using SimGrid simulator, and it keeps being used to creation of the two heuristics presented in this dissertation. In the conducted tests in this simulator, was possible to achieve a gain of until 45% on application execution time using MigHull, and until 42% using MigCube, when compared with the application without the migration model. However, simulations with a bigger number of processes, this gain tends to fall, since one of the bigger problems of BSP and applications that run in grid is the time of tasks synchronization, that is, as more processes, more need of synchronization, and even the processes balancing ends up having an impaired outcome