-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- Eficiência como uma função de
para três algoritmos diferentes (ver texto). A figura superior é para
e a figura inferior é para
. É de notar o uso de escalas logarítmicas. Quando
Os algoritmos (1) e (2) confundem-se.
- Representação da actividade durante a execução de um programa paralelo em oito processadores. Cada processador gasta o seu tempo em computação, em comunicando ou à espera.
é o tempo total de execução.
- O modelo simples de comunicação:
. Neste traçado de tempo versus comprimento de mensagens, a inclinação da linha corresponde ao custo por palavra transmitida e a intercepção-y ao custo de estabelecimento das mensagens.
- Tempo simples de ida e volta para uma mensagem entre dois processadores como uma função do comprimento da mensagem, em estações de trabalho ligados por Ethernet e FDDI, Intel Parageon e IBM SPI. Dados fornecidos por W. Gropp.
- Sobreposição da comunicação com a computação. As linhas sólidas representam a computação e as linhas a tracejado as operações de comunicação. Tanto em (a) como em (b), o processador
emite um pedido para o processador
no instante
e recebe uma resposta no instante
. Em ambos os casos, o custo de envio efectivo de uma mensagem assume-se ser
unidade de tempo. Em (a)
não tem trabalho útil a fazer enquanto espera pela resposta e por isso fica ocioso durante
unidades de tempo depois de ter enviado a mensagem. Em (b)
comuta para uma outra tarefa logo que o pedido é emitido. Uma vez que esta tarefa requere 5 unidade de tempo para se completar,
nunca fica ocioso.
- Escalabilidade de um algoritmo de diferenças finitas 1-D, de acordo com as equações 3.4 e 3.7, quando
seg,
seg,
seg e Z = 10; a) tempo de execução como uma função de
; b) eficiência como uma função de
. De notar que quando
, apenas 64 processadores podem ser usados de forma efectiva.
- Escalabilidade de um algoritmo de diferenças finitas baseada numa decomposição 1-D.
Em (a),
e
. Cada tarefa tem 32 pontos da grelha e deverá comunicar com dois vizinhos.
Em (b),
duplica enquanto
se mantém constante. O custo da computação total mantém-se constante mas os custos de comunicação duplicam, por isso a eficiência é reduzida. Em (c), tanto
como
duplicam, assegurando dessa forma o aumento dos custos da computação e dos custos de comunicação da componente
, de um factor de quatro vezes; por isso a eficiência se mantém constante.
- Contribuição dos custos de computação, de arranque de mensagens e de comunicação para o tempo total de execução de um algoritmo de diferenças finitas 1-D, de acordo com as equações 3.4 e 3.7, quando
seg,
seg,
seg e Z = 1 e
. Não há tempos de replicação ou de ócio contabilizados.
- Ajuste de mínimos quadrados simples e ponderado da função
para os tempos de execução do algoritmo das diferenças finitas executado numa estação de trabalho Sun SPARC 2. É de notar o uso de escalas logarítmicas.
- Ganhos de uma realização do algoritmo das diferenças finitas, 1-D, quando
e
medidos num Intel DELTA de acordo com as previsões de um modelo de rendimento simples que não toma em consideração o não balanceamento da carga e um modelo mais sofisticado que o faz; ambos os modelos assumem
seg e
seg.
- Uma barra transversal não bloquante
x
, usada aqui para ligar
processadores. À direita, dois elementos de comutação expandidos; o elemento acima permite a passagem de mensagens e o elemento abaixo faz a comutação das mensagens. É de notar que cada processador é representado duas vezes e que qualquer par de processadores pode comunicar sem evitar que outro par de processadores possa comunicar.
- Uma rede de interconexão baseada em barramento, usada aqui para realizar um computador paralelo de memória partilhada. Cada processador
está liga ao barramento, o qual por sua vez está ligado à memória global. Uma cache associada com cada processador guarda os valores mais recentemente obtidos da memória, com intenção de reduzir o trâfego no barramento.
- Uma LAN Ethernet. Múltiplos computadores estão ligados a um único cabo Ethernet, o qual actua como um barramento de comunicação que transporta um único sinal em cada momento.
- Um toro de duas dimensões. Este é uma malha com ligações entre extremidades para que cada processador esteja ligado a quatro vizinhos.
- Competição pela largura de banda numa malha 1-D. Em (a), os processadores
e
comunicam e
e
comunicam. Porque as duas comunicações usam fios distintos, ambas podem prosseguir concorrentemente. Em (b), os processadores
e
comunicam e
e
comunicam. As duas comunicações devem ambas atravessar os fios de ligação
e
, daí as duas comunicações não poderem prosseguir e
. Em (c), os processadores
e
comunicam e
e
comunicam. Porque cada ligação é bi-direccional, as duas comunicações podem prosseguir concorrentemente.
- Hipercubos de dimensões zero a quatro. Os processadors dos hipercubos de dimensões 1, 2 e 3 são etiquetados com inteiros, aqui representados por números binários. É de notar que dois processadores são vizinhos se e só se os seus valores binários diferirem só numa dimensão. É de notar que nm hipercubo de dimensão
, uma mensagem pode viajar entre qualquer par de processadores num máximo de
saltos.
- Exemplo de uma rede de interconexão de múltiplos estágios. Os círculos sombreados representam processadores e os não sombreados representam comutadores por barra transversal. A rede à esquerda tem
e
; à direita,
e
. A rede pode ser construída a partir de comutadores e ligações uni-direccionais, dobrada para permitir que os processadores à esquerda e à direita sejam os mesmos. Alternativamente, pode ser construído por comutadores e ligações bi-direccionais, sendo distintos os processadores à esquerda e à direita .
- Comunicação numa rede de licação multi-estágios (MIN). A comunicação mostrada em (a) envolve processadores ligados à mesma barra; usa apenas dois pulos e passa apenas por um único comutador. A comunicação em (b) necessita de três pulos e passa através de dois comutadores.
- O ganho do código das diferenças finitas com
e
tal como foi medido e previsto, quer por um modelo de rendimento que não toma em consideração a competição pela largura de banda, quer por um modelo mais sofisticado, numa rede de estações de trabalho IBM RS 6000 ligadas por Ethernet. Ambos os modelos assumem que
seg e
seg.
- Execuação do algoritmo da soma em borboleta com oito processadores numa malha a uma dimensão. O sombreado é usado para marcar uma única tarefa e os padrões de comunicação, que são de um, dois e quatro pulos de distância.
- Rendimento de um algoritmo paralelo para a FFT de um código de transformação espectral numa em malha a uma dimensão num Intel DELTA e numa rede Ethernet de processadores RS/6000 e . O modelo simples não toma em consideração a competição por largura de banda; o modelo refinado fá-lo ajustando-se melhor ao rendimento observado.
- Arquitectura de E/S de um computador paralelo idealizado.
processadores estão ligados por múltiplos canais de E/S a
discos.
- Um grafo directo simples, G, e a sua matriz de adjacências, A.
- Uma operação fundamental no algoritmo sequencial de Floyd de optimização de percursos. Determina se o caminho que vai de
para
através de
é mais curto do que o melhor dos caminhos conhecidos entre
e
.
- Versão paralela do algoritmo de Floyd baseado numa decomposição uni-dimensional da matriz
. Em (a), os dados alocados a uma tarefa simples estão a sombreado: uma sub-matriz contígua. Em (b), os dados necessários a esta tarefa no passo
do algoritmo estão a sombreado: os seus próprios blocos e parte da coluna e linha
.
- Versão paralela do algoritmo de Floyd baseado numa decomposição bi-dimensional da matriz
. Em (a), os dados alocados a uma tarefa simples estão a sombreado: uma sub-matriz contígua. Em (b), os dados necessários a esta tarefa no passo
do algoritmo estão a sombreado: os seus próprios blocos e a linha
.
- A operação de comparação efectuada no algoritmo de optimização de percursos por origem-simples de Dijkstra. O melhor caminho conhecido desde o vértice
até o vértice
é comparado como o caminho que leva de
para
e depois para
.
- O segundo algoritmo paralelo de Dijkstra aloca
tarefas a cada uma das
instanciações do algoritmo de optimização de percursos por origem-simples de Dijkstra. Nesta figura,
e
, e um conjunto de
tarefas está a sombreado.
2000-05-22