Módulo 01 - Ordenamentos, o Direito e a Moral.

7 – Modelos BSP e CGM

O modelo Bulk Synchronous Parallel Model (BSP), que em uma tradução simples seria “Modelo Paralelo Síncrono Volumoso”, teve sua proposição feita por Valiant (Leslie Valiant – professor de Harward), no ano de 1990, foi um dos primeiros em levar em consideração os custos da comunicação e não levar em conta as características de uma máquina paralela em um número pequeno de parâmetros. Este modelo tem como objetivo principal servir de ponte entre as necessidades na computação paralela de hardware e software. Conforme a proposição de Leslie Valiant, este é um dos fatores responsáveis pelo sucesso do modelo sequencial de von Neumann.

O modelo de máquina BSP consiste de um conjunto de “p” processadores com memória local, trocando informações por meio de alguma interconexão, gerenciados por um roteador (faz a intermediação entre um ou mais pontos) e com facilidade de sincronização global. Um algoritmo BSP consiste de uma sequência de uma quantidade muito grande de passos (superpassos) separados por barreiras de sincronização.

Há também o modelo Coarse Grained Multicomputer (CGM), que em uma tradução simples seria “Multicomputador com Granularidade Grossa”, teve sua proposição feita por Dehne et al, no ano de 1993.

O modelo CGM é muito parecido com o modelo BSP, no entanto, é definido em apenas dois parâmetros:

n = tamanho do problema e
p número de processadores.

Um algoritmo CGM consiste de sequência alternada de rodadas de computação e rodadas de comunicação, separadas por uma barreira de sincronização. Ao falarmos de um algoritmo CGM, precisamos entender que é uma sequência de rounds (rodadas), com alternância de fases bem definidas de processamento local e estabelecendo uma conexão global. Geralmente, durante uma rodada de computação é feita com a utilização do melhor algoritmo sequencial para o processamento dos dados disponibilizados localmente.

O cálculo do custo de um algoritmo CGM é feito pela soma dos tempos obtidos em termos do número total de rounds de computação local e do número de superpassos, o que seria equivalente ao número total rodadas de comunicação.