-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 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