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.
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.
Quando se fala em “coarse grained” (granularidade grossa) é em virtude do tamanho de o problema ser razoavelmente maior que a quantidade de processadores, ou seja, “tamanho do problema” ≥ “número de processadores” (n/p ≥ p).
X