Publicado em: 01/10/2009

Defesa de Tese de Doutorado dia 05/10 de Rodrigo da Rosa Righi

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL INSTITUTO DE INFORMÁTICA PROGRAMA DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO
————————————————-
DEFESA DE TESE DE DOUTORADO

Aluno: Rodrigo da Rosa Righi
Orientador: Prof. Philippe Olivier Alexandre Navaux Orientador do Estágio Sanduiche: Prof. Hans-Ulrich Heiss – Technische Universität Berlin

Título: MigBSP: A New Approach for Processes Rescheduling Management on Bulk Synchronous Parallel Applications Linha de Pesquisa: Processamento Paralelo e Distribuído

Data: 05/10/2009
Hora: 13h30
Local: Auditório Prof. José Mauro Volkmer de Castilho – Instituto de Informática/UFRGS

Banca Examinadora:
Prof. Dr. Bruno Richard Schulze (LNCC – MCT) Prof. Dr. Adenauer Corrêa Yamin – UFPel Prof. Dr. César Augusto Fonticielha De Rose (PUCRS)

Presidente da Banca: Prof. Dr. Philippe Olivier Alexandre Navaux

RESUMO:

This thesis treats the processes rescheduling problem during application
runtime, offering dynamic load rebalancing among the available resources. Since most distributed computing scenarios involve more and more resources and dynamic applications, the load is a variable measure and an initial processes-processors deployment may not remain efficient with time. The resources and the network states can vary during application execution, as well as the amount of processing and the interactions among the processes. Consequently, the remapping of processes to new processors is pertinent to improve resource utilization and to minimize application execution time. In this context, this thesis presents a  rescheduling model called MigBSP, which controls the processes migration of BSP (Bulk Synchronous Parallel) applications. BSP application model was adopted because it turns parallel programming easier and is very common in scientific applications development scenarios.

Considering the scope of BSP applications, the novel ideas of MigBSP are
threefold: (i) combination of three metrics – Memory, Computation and Communication – in a scalar one in order to measure the potential of migration of each BSP process; (ii) employment of both Computation and Communication Patterns to control processes’ regularity and; (iii) efficient adaptation regarding the periodicity to launch processes rescheduling. In our infrastructure, we are considering heterogeneous (different processor and network speed)  distributed systems. The processes can pass messages among themselves and the parallel machine can gather local area networks and clusters. The proposed model provides a mathematical formalism to decide the following questions about load (BSP processes) balancing: (i) When to launch the processes rescheduling; (ii) Which processes will be candidates for migration and; (iii) Where to put the processes that will be migrated actually.

We used the simulation technique to validate MigBSP. Besides MigBSP, three scientific application were developed and executed using Simgrid simulator. In general, the results showed that MigBSP offers an opportunity to get performance in an effortless manner to the programmer since its does not need modification on application code.
MigBSP makes possible gains of performance up to 20% as well as produces a low overhead when migrations do not take place. Its mean overhead  is lower than 8% of the normal application execution time.
This rate was obtained disabling any processes migration indicated by MigBSP. The results show that union of considered metrics is a good solution to control processes migration. Besides this, they revealed that the developed adaptations are crucial to turn MigBSP execution viable, mainly on unbalanced environments.

Palavras-chave: migration, load-balancing, processes, scheduling, high-performance, grid computing