Lista de Figuras

1. Rendimento de ponta de alguns dos mais rápidos super-computadores, 1945-1995. O crescimento exponencial estabilizou por volta dos anos 80, mas está de novo a acelerar à medida que se tornam disponíveis computadores maciçamente paralelos. Aqui $o$ são uni-processador, $+$ denota computadores vectoriais modestamente paralelos com (4-16) processadores e $x$ denota computadores maciçamente paralelos com centenas ou milhares de processadores. Tipicamente, computadores maciçamente paralelos atingem uma mais baixa faixa do seu rendimento de pico do que os computadores vectoriais, em aplicações realísticas.
2. Evolução em ciclos de relógio de computador. Os tempos de ciclo dos computadores vectoriais convencionais  (denotados $o$) têm vindo a decrescer apenas de um factor de 3 em dezasseis anos, desde o CRAY-! (12,5 nano-segundos) até ao C90 (4.0). Os microprocessadores RISC (denotados $+$ estão a aproximar-se rapidamente do mesmo rendimento. Ambas as arquitecturas parecem estar a aproximar-se dos limites físicos.
3. Número de processadores em computadores maciçamente paralelos ($o$) e multi-processadores vectoriais ($+$). Em ambos os casos, é aparente um crescimento constante no número de processadores . Uma tendência semelhante está a começar a ocorrer na estações de trabalho e pode esperar-se que os computadores pessoais prossigam a mesma tendência.
4. O computador de Von Neumann. Uma unidade de processamento central (CPU) executa as instruções que efectuam uma sequência de leituras e escritas na memória associada.
5. O multi-computador, um modelo de computador ideal. Cada nodo compreende uma máquina de Von Neumann: um processador e memória. Um nodo pode comunicar com outros nodos através do envio e da recepção de mensagens através de uma rede.
6. Classes de arquitecturas de computadores paralelos. De cima para baixo: um computador de memória distribuída MIMD com uma interconexão em malha, um multi-processador de memória partilhada e um rede em área local (Ethernet, neste caso). Em cada caso, $P$ denota um processador independente.
7. Um modelo de programação simples. A figura mostra um estado instantâneo de uma computação e uma imagem detalhada de uma tarefa simples. A computação compreende um conjunto de tarefas (representadas por círculos) ligados por canais (setas). Uma tarefa esconde um programa e memória local e define um conjunto de portas que definem o seu interface com o meio-ambiente. Um canal é uma fila de mensagens na qual um emissor pode colocar mensagens e de onde um receptor pode retirar mensagens, "bloqueando" se não existirem mensagens disponíveis.
8. As quatro acções básicas das tarefas. Adicionalmente para ler e escrever na memória local, uma tarefa envia uma mensagem, cria novas tarefas (suspendendo-se até que estas terminem) e terminar.
9. Duas soluções para o problema da construção de uma ponte. Ambas representam os lugares de montagem da ponte e da fundição como tarefas separadas, foundry e brigde. A primeira usa um simples canal no qual as vigas produzidas pela fundição são transportadas tão rapidamente quanto são produzidas. Se a fundição produz vigas mais rapidamente do que estas são consumidas pela ponte, então as vigas acumulam-se no local de construção. A segunda solução usa um segundo canal para passar o controlo de mensagens da ponte para a fundição para dessa forma evitar o excesso.
10. A tarefa como bloco de montagem. (a) As tarefas na fundição e ponte são os blocos de construção com interfaces complementares. (b) Assim duas tarefas podem ser ligadas em conjunto para formar um programa completo. (c) As tarefas são permutáveis entre si: outras tarefas com interfaces compatíveis podem ser substituídas para obter um programa diferente.
11. Algoritmo paralelo para um problema de diferenças finitas a uma dimensão. De cima para baixo: o vector uni-direccional $X$, sendo $N=8$; Na estrutura de tarefas mostrando as 8 tarefas, cada uma escondendo um valor de dados simples e ligada aos vizinhos à esquerda e à direita, através de canais; e a estrutura de uma tarefa simples, mostrando as suas duas portas de entrada e de saída.
12. Estruturas de tarefas para calcular pares de interacções para $N=5$. (a) O anel uni-direccional usado pelo algoritmo simples não-simétrico. (b) o anel uni-direccional com canais adicionais usados para recuperar os valores acumulados no algoritmo simétrico; o caminho tomada pelo acumulador usado pela tarefa 0 é apresentado como uma linha sólida.
13. Estruturas de tarefas para o exemplo de pesquisa. cada círculo representa um nodo na árvore de procura e dessa forma uma chamada ao exemplo de pesquisa. É criada uma tarefa por cada nodo na árvore tal como já foi explorado. Num determinado momento, algumas tarefas são activamente envolvidas na expansão em profundidade da árvore (estas estão representadas a sombreado na figura); outras chegaram a nodos solução e estão a terminar, ou estão à espera que os seus descendentes retornem com soluções. As linhas representam os canais usados para retornar soluções.
14. Estruturas de tarefas para o problema de estudo de parâmetros. Os trabalhadores (W) requisitam parâmetros da tarefa de entrada (I) e enviam resultados para a tarefa de saída (O). É de notar as ligações de muitos para um; este programa é não-determinístico na medida em que as tarefas de entrada e de saída recebem dados dos trabalhadores em qualquer que seja a ordem com que são produzidos. Os canais de resposta representados por linhas tracejadas, são usados para comunicar parâmetros da tarefa de entrada para os trabalhadores.
15. PCAM: metodologia de desenho de programas paralelos. A partir da especificação de um problema, desenvolvemos amos uma partição, determinados os requisitos de comunicação, agrupamos tarefas e finalmente fazemos o arranjo de tarefas entre processadores.
16. Ilustração da técnica de decomposição em domínios.
    A decomposição tri-dimensional é a mais flexível
17. Decomposição Mista na simulação do clima da terra.
18. Estrutura de canais e tarefas para um problema de diferenças finitas usando 5 pontos de matriz
19. Eficiência como uma função de $P$ para três algoritmos diferentes (ver texto). A figura superior é para $N = 100$ e a figura inferior é para $N = 1000$. É de notar o uso de escalas logarítmicas. Quando $N = 100$ Os algoritmos (1) e (2) confundem-se.
20. 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. $T$ é o tempo total de execução.
21. O modelo simples de comunicação: $T_{msg}=t_s + t_wL$. 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.
22. 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.
23. 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 $P1$ emite um pedido para o processador $P2$ no instante $t + 2$ e recebe uma resposta no instante $t + 8$. Em ambos os casos, o custo de envio efectivo de uma mensagem assume-se ser $1$ unidade de tempo. Em (a) $P1$ não tem trabalho útil a fazer enquanto espera pela resposta e por isso fica ocioso durante $5$ unidades de tempo depois de ter enviado a mensagem. Em (b) $P1$ comuta para uma outra tarefa logo que o pedido é emitido. Uma vez que esta tarefa requere 5 unidade de tempo para se completar, $P1$ nunca fica ocioso.
24. Escalabilidade de um algoritmo de diferenças finitas 1-D, de acordo com as equações 3.4 e 3.7, quando $t_c = 1\mu$seg, $t_s = 100\mu$seg, $t_w = 0.4\mu$seg e Z = 10; a) tempo de execução como uma função de $P$; b) eficiência como uma função de $P$. De notar que quando $N = 128$, apenas 64 processadores podem ser usados de forma efectiva.
25. Escalabilidade de um algoritmo de diferenças finitas baseada numa decomposição 1-D. Em (a), $N=8$ e $P = 2$. Cada tarefa tem 32 pontos da grelha e deverá comunicar com dois vizinhos. Em (b), $P$ duplica enquanto $N$ 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 $P$ como $N$ duplicam, assegurando dessa forma o aumento dos custos da computação e dos custos de comunicação da componente $t_w$, de um factor de quatro vezes; por isso a eficiência se mantém constante.
26. 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 $t_s = 200\mu$seg, $t_c = 1\mu$seg, $t_w = 0.8\mu$seg e Z = 1 e $N = 512$. Não há tempos de replicação ou de ócio contabilizados.
27. Ajuste de mínimos quadrados simples e ponderado da função $t_cN^210$ 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.
28. Ganhos de uma realização do algoritmo das diferenças finitas, 1-D, quando $N = 512$ e $Z = 10$ 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 $t_s = 200\mu$seg e $t_w = 2\mu$seg.
29. Uma barra transversal não bloquante $4$ x $4$, usada aqui para ligar $4$ 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.
30. Uma rede de interconexão baseada em barramento, usada aqui para realizar um computador paralelo de memória partilhada. Cada processador $P$ 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.
31. 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.
32. Um toro de duas dimensões. Este é uma malha com ligações entre extremidades para que cada processador esteja ligado a quatro vizinhos.
33. Competição pela largura de banda numa malha 1-D. Em (a), os processadores $P0$ e $P1$ comunicam e $P2$ e $P3$ comunicam. Porque as duas comunicações usam fios distintos, ambas podem prosseguir concorrentemente. Em (b), os processadores $P0$ e $P2$ comunicam e $P1$ e $P3$ comunicam. As duas comunicações devem ambas atravessar os fios de ligação $P1$ e $P2$, daí as duas comunicações não poderem prosseguir e $S = 2$. Em (c), os processadores $P0$ e $P2$ comunicam e $P3$ e $P1$ comunicam. Porque cada ligação é bi-direccional, as duas comunicações podem prosseguir concorrentemente.
34. 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 $d$, uma mensagem pode viajar entre qualquer par de processadores num máximo de $d$ saltos.
35. 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 $k = 2$ e $n = 3$; à direita, $k = 4$ e $n = 2$. 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 .
36. 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.
37. O ganho do código das diferenças finitas com $N = 512$ e $Z = 5$ 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 $t_s = 1500\mu$seg e $t_w = 5\mu$seg.
38. 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.
39. 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.
40. Arquitectura de E/S de um computador paralelo idealizado. $P$ processadores estão ligados por múltiplos canais de E/S a $D$ discos.
41. Um grafo directo simples, G, e a sua matriz de adjacências, A.
42. Uma operação fundamental no algoritmo sequencial de Floyd de optimização de percursos. Determina se o caminho que vai de $v_i$ para $v_j$ através de $v_k$ é mais curto do que o melhor dos caminhos conhecidos entre $v_i$ e $v_j$.
43. Versão paralela do algoritmo de Floyd baseado numa decomposição uni-dimensional da matriz $I$. 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 $k$ do algoritmo estão a sombreado: os seus próprios blocos e parte da coluna e linha $k$.
44. Versão paralela do algoritmo de Floyd baseado numa decomposição bi-dimensional da matriz $I$. 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 $k$ do algoritmo estão a sombreado: os seus próprios blocos e a linha $k$.
45. 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 $v_s$ até o vértice $v_t$ é comparado como o caminho que leva de $v_s$ para $v_m$ e depois para $v_t$.
46. O segundo algoritmo paralelo de Dijkstra aloca $P/N$ tarefas a cada uma das $N$ instanciações do algoritmo de optimização de percursos por origem-simples de Dijkstra. Nesta figura, $N = 9$ e $P = 36$, e um conjunto de $P/N=4$ tarefas está a sombreado.