Conceitos

Computadores Paralelos e Computação

Neste primeiro capítulo revemos o papel do paralelismo na computação e introduzimos os modelos de máquina paralela e de programação que servirão como base para a subsequente discussão do desenho, da análise de rendimento e da implementação de algoritmos.

Depois de estudar este capítulo, o leitor deverá ser sabedor da importância da concorrência, da escalabilidade, da localidade e da modularidade no desenho de programas paralelos. Deverá, também, estar familiarizado com o modelo idealizado do multi-computador para o qual iremos desenhar os algoritmos paralelos e as abstracções de computação e de comunicação que iremos usar quando descrevermos os algoritmos paralelos.

Paralelismo e Computação

Um computador paralelo é um conjunto de processadores capazes de trabalhar cooperativamente para resolver um problema computacional. Esta definição é suficientemente ampla para incluir super-computadores paralelos que têm centenas ou milhares de processadores, redes de estações de trabalho, estação de trabalho multi-processador e sistemas integrados. Os computadores paralelos são interessantes porque oferecem o potencial para concentrar recursos de computação - quer se trate de processadores, de memória, ou de largura de banda de entrada/saída - em problemas computacionais importantes.

O paralelismo tem muitas vezes sido visto como uma estranha e esotérica sub-área da computação, interessante mas de pequena relevância para o programador médio. O estudo das tendências das aplicações, das arquitecturas de computadores, e das redes mostra que esta perspectiva não é mais sustentável. O paralelismo está a tornar-se ubíquo e a programação paralela está a tornar-se central no empreendimento da programação.

Tendências nas Aplicações

À medida que os computadores se vêm tornando cada vez mais rápidos, há a tendência para considerar que estes se poderão tornar suficientemente rápidos e que o apetite pelo aumento de capacidade computacional sairá satisfeito. Contudo a história tem demonstrado que à medida que uma determinada tecnologia satisfaz as aplicações existentes, novas aplicações aparecerão que exigirão o desenvolvimento de novas tecnologias. Como uma divertida ilustração deste fenómeno, um relatório preparado para o governo britânico nos anos 40 conclui que os requisitos computacionais da Grã-Bretanha poderiam ser alcançados com dois, ou talvez três, computadores. Naqueles tempos, os computadores eram usados em primeiro lugar para calcular tabelas balísticas. Os autores do relatório não entraram em consideração com outras aplicações na ciência e na engenharia, deixando de fora as aplicações comerciais que cedo viriam a dominar a computação. Similarmente, as prospecções iniciais da Cray Research previam um mercado para dez supercomputadores; várias centenas foram vendidos, desde aí.

Tradicionalmente, o desenvolvimento de aplicações de elevado desempenho tem vindo a ser motivado pela simulação de sistemas complexos, tais como, previsão meteorológica, clima, dispositivos mecânicos, circuitos electrónicos, processos de fabrico e reacções químicas. Hoje, contudo, os mais significativos condicionantes do desenvolvimento de computadores de elevado desempenho são as aplicações comerciais emergentes que exigem ao computador a capacidade de processar quantidades substanciais de dados, de forma assaz sofisticada. Esta aplicações incluem vídeo-conferências, ambientes de trabalho colaborativos, auxiliares ao diagnóstico na área da medicina, bases de dados paralelas usadas para suporte à decisão e gráficos avançados e realidade virtual, particularmente na indústria do entretimento. Por exemplo, a integração da computação paralela, redes de alta-velocidade e tecnologias multimédia está a levar ao desenvolvimento de servidores de vídeo, computadores projectados para servir centenas ou milhares de pedidos simultâneos de vídeo em tempo real. Cada sequência de vídeo pode envolver taxas de transferência de dados de muitos mega-octetos por segundo e grandes quantidades de processamento para codificação e descodificação. Em gráficos, conjuntos de dados tri-dimensionais aproximam-se, agora, de $10^9$ elementos (1024 numa dimensão). A 200 operações por elemento, um ecrã actualizado 30 vezes por segundo requer um computador capaz de $6,4$ x $10^2$ operações por segundo.

Apesar das aplicações comerciais poderem vir a definir a arquitecturas da maior parte dos computadores paralelos do futuro, as aplicações científicas tradicionais continuarão a ser utilizadores importantes das tecnologias da computação paralela. Na verdade, à medida que os efeitos não lineares definem os limites das perspectivas oferecidas pelas investigações puramente teóricas e a experimentação se torna mais cara ou impraticável, os estudos computacionais dos sistemas complexos estão a tornar-se cada vez mais importantes. Os custos computacionais crescem, tipicamente, na quarta potência, ou mais, da resolução que determina a precisão, assim, estes estudos têm uma visível demanda insaciável por um poder superior de computação. Estes custos são também caracterizados por requisitos de enormes quantidades de memória e de entradas/saídas. Por exemplo, uma simulação do clima da terra, para os próximos dez anos, que recorre a um modelo actual, pode envolver $10^{16}$ operações em vírgula flutuante - dez dias a uma velocidade de execução de $10^{10}$ operações de vírgula flutuante por segundo ( 10 giga flops). Esta mesma simulação pode gerar facilmente um centena de giga-octetos ($10 ^{11}$ octetos), ou mais, de dados. Ainda assim, como a tabela 1.1 mostra, os cientistas podem facilmente imaginar refinamentos aqueles modelos que fariam crescer estes requisitos computacionais em $10 000$ vezes.

Tabela: Vários refinamentos propostos para os modelos de clima e o crescimento computacional requerido associado a esses refinamentos. Os refinamentos, todos em conjunto podem aumentar os requisitos de computação de um factor entre $10^4$ e $10^7$.

Estado Actual	Refinamento	Custo
resolução de 100-km	resolução de 10-km	$10^2$ - $10^3$
representação simples em processos	representação melhorada em processo	2-10
oceano simples	oceano completo	2-5
química atmosférica simples	química atmosférica melhorada	2-5
biosfera limitada	biosfera em compreensão	cerca de 2
dezenas de anos	centenas de anos	10- $10^2$

Em resumo, a necessidade de computadores mais rápidos é conduzida pela demanda tanto em aplicações intensivas de dados no comércio como em aplicações intensivas em ciência e engenharia. Os requisitos destes campos estão a fundir-se, à medida que as aplicações em ciência e em engenharia induzem maiores volumes de dados e as aplicações comerciais requerem cálculos mais sofisticados.

Tendências no Projecto de Computadores

O rendimento dos mais rápidos computadores têm crescido exponencialmente desde 1945 até ao presente, com um factor médio de 10 vezes por quinquénio. Enquanto os primeiros computadores executavam apenas algumas dezenas de operações em vírgula flutuante, por segundo, os computadores paralelos dos anos 90 atingem dezenas de milhões de operações por segundo, (Figura 1.1). Tendências semelhantes podem ser observadas em computadores de baixa gama em diferentes áreas: calculadoras, computadores pessoais e estações de trabalho. Não há nenhum razão para supor que este desenvolvimento possa ter um termo. Contudo, as arquitecturas de computadores usadas para sustentar este crescimento estão a alterar-se radicalmente - de sequenciais para paralelas.

Figura: 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.

A capacidade de um computador depende directamente do tempo necessário para executar uma operação básica e do número daquelas operações que podem ser executadas concorrentemente. O tempo para efectuar uma operação básica é, em última instância, limitado pelo ciclo de relógio do processador que é o tempo necessário para executar a operação mais primitiva. Contudo, os tempos de ciclo de relógio estão a decrescer lentamente e parece estarem a aproximar-se dos limites físicos da velocidade da luz (figura 1.2). Não podemos depender da existência de processadores mais rápidos para promover o aumento do rendimento computacional.

Figura: 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.

Para circunscrever estas limitações, o projectista pode experimentar utilizar a concorrência interna no integrado, por exemplo, operando simultaneamente nos 64 bits de dois números que se pretende multiplicar. Contudo, um resultado fundamental da teoria da complexidade da Integração em Muito Larga Escala (VLSI) estabelece que esta estratégia é onerosa. Os resultados atestam que para certos tipos de computações transitivas (em que cada saída pode depender de qualquer entrada), a área A do integrado e o tempo T requerido para efectuar este cálculo estão relacionados de forma a que ${\bf AT^2}$ deve exceder uma função do tamanho do problema, dependente do próprio problema. Este resultado pode ser explicado informalmente, assumindo que um cálculo obriga a mover uma certa quantidade de informação de uma extremidade de um integrado quadrangular para a outra extremidade. Ora, a quantidade de informação que pode ser movida por unidade de tempo é limitada pela secção transversal do integrado, $\sqrt {A}$. Isto, determina a taxa de transferência $\sqrt{A}*T$ de onde a relação $AT^2$ foi obtida. Para diminuir de um certo factor o tempo necessário para mover a informação, a secção transversal deverá ser aumentada pelo mesmo factor e em consequência a área total deverá crescer no quadrado do mesmo factor.

Este resultado $AT^2$ significa que não só é difícil construir componentes individuais para operar mais rapidamente como pode inclusivamente não ser desejável fazê-lo. Poderá ser mais económico usar um maior número de componentes mais lentos. Por exemplo, se tivermos uma área $n^2*A$ de silício para usar num computador, poderemos, ou construir $n^2$ componentes, cada um de tamanho A, capazes de efectuar uma operação em tempo T, ou construir um único componente capaz de executar a mesma operação em tempo $T/n$. O sistema multi-componente é, potencialmente, mais rápido $n$ vezes.

Os projectistas de computadores usam uma variedade de técnicas para obviar estas limitações no rendimento de um computador isolado, incluindo encadeamento, pipeline, (diferentes estágios de várias instruções em execução concorrente) e múltiplas unidades funcionais (vários multiplicadores, coprocessadores, etc.), são controlados pelo uma única sequência de instruções). E ainda, os projectistas, estão a incorporar múltiplos ``computadores'', cada um com o seu próprio processador, memória e lógica de interconexão associada. Esta abordagem é favorecida pelos avanços na tecnologia VLSI que continua a fazer decrescer o número de componentes necessários para construir um computador. Como o custo de um computador é (muito aproximadamente) proporcional ao número de componentes que contém, o aumento da capacidade de integração também aumenta o número de processadores que podem ser incluídos num computador para um custo particular. O resultado é o contínuo crescimento no número de processadores (Figura 1.3).

Figura: 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.

Tendências em Interconexão

Um outro importante desenvolvimento que está a mudar a face da computação é o extraordinário aumento de capacidade das redes de ligação de computadores. Ainda não há muito tempo, as redes de alta velocidade atingiam os 1.5 Mbits por segundo; nos finais dos anos 90, larguras de banda que ultrapassam os 1000 Mbits por segundo passarão a ser lugares comuns. Esperam-se, também, melhoramentos significativos da fiabilidade. Estas tendências tornam viável desenvolver aplicações que usam recursos físicos distribuídos como se se tratassem de partes do mesmo computador. Uma aplicação típica desta espécie pode utilizar processadores em múltiplos computadores remotos, fazer o acesso a uma selecção de bases de dados remotas, esboçar gráficos, num ou mais computadores, e fornecer uma saída em tempo real e o controlo de uma estação de trabalho.

Realçamos o facto de que a computação em computadores em rede (computação distribuída) não é um mero sub-campo da computação paralela. A computação distribuída está profundamente preocupada com problemas tais como a fiabilidade, a segurança e a heterogeneidade que são, em geral, vistas como tangenciais à computação paralela. (Parafraseando Leslie Lamport ``Num sistema distribuído, a falha de um computador que não sabíamos sequer que existia pode tornar inoperável o nosso próprio computador.) Ainda assim, a tarefa de desenvolver programas que podem executar em muitos computadores, ao mesmo tempo, é um problema da computação paralela. A este respeito, a distinção anterior entre os mundos da computação paralela e da computação distribuída são convergentes.

Resumo de tendências

Este breve levantamento das tendências das aplicações, das arquitecturas de computadores e das redes prenuncia um futuro em que o paralelismo invade não apenas os super-computadores mas também as estações de trabalho, os computadores pessoais e as redes. No futuro, os programas terão de ser capazes de explorar os múltiplos processadores localizados em cada computador e os processadores adicionais disponíveis através de uma rede. Porque a maior parte dos algoritmos existentes foram desenhados para uni-processadores, esta situação obriga à construção de novos algoritmos e estruturas de programas capazes de realizar múltiplas operações simultaneamente. A concorrência torna-se um requisito fundamental dos algoritmos e programas.

Este levantamento também sugere uma segunda lição fundamental. Parece que o número de processadores continuará a crescer - talvez, como acontece em alguns ambientes presentemente, duplicando em cada um ou dois anos. Assim, os sistemas de software podem presumivelmente vir a ser sujeitos a crescimentos substanciais em número de processadores durante o seu tempo de vida. Neste ambiente, a escalabilidade - a capacidade de adaptação ao aumento do número de processadores - é tão importante como a portabilidade como forma de salvaguardar o investimento em software. Um programa capaz de usar apenas um número fixo de processadores é um mau programa, como o é um programa que só pode ser executado num só computador. A escalabilidade é um tema maior que irá ser enfatizado ao longo deste livro.

Modelo de Máquina Paralela

A rápida introdução do computador no comércio, ciência e educação deve muito à rápida normalização em torno de um modelo único de computador, o computador de Von Neumann. Um computador de Von Neumann compreende uma unidade de processamento central (CPU) ligada a uma unidade de armazenamento (memória) (figura 1.4). O CPU executa um programa guardado que especifica a sequência de operações de leitura e escrita na memória. Este modelo simples tem provado uma notável robustez. A sua persistência, ao longo de mais de quarenta anos, tornou possível proceder ao estudo de importantes tópicos tais como os algoritmos e as linguagens de programação, em larga medida, independentemente dos desenvolvimentos das arquitecturas de computadores. Em consequência, os programadores podem ser treinados na arte abstracta da programação em vez de na habilidade da programação da máquinas $X$ e pode desenhar algoritmos para uma máquina abstracta de Von Neumann, confiante que os algoritmos correm na maior parte dos computadores desejados com razoável eficiência.

O nosso estudo da programação paralela poderá ser, no essencial, compensatório se podermos identificar um modelo tão geral e útil, como o modelo sequencial de Von Neumann. Este modelo de máquina deverá ser ao mesmo tempo simples e realístico: simples para facilitar a compreensão e a programação e realístico para poder assegurar que os programas desenvolvidos para o modelo correm com razoável eficiência nos computadores reais.

Figura: 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.

O Multi-Computador

O modelo de máquina paralela designado por multi-computador preenche aqueles requisitos. Como se pode ver na fig. 1.5, um multi-computador compreende um certo número de computadores de Von Neumann, ou nodos, interligados por uma rede de interconexão. Cada computador executa o seu próprio programa. Este pode fazer o acesso a memória local e enviar e receber mensagens através da rede. As mensagens são usadas para comunicar com outros computadores, ou de forma equivalente, ler e escrever nas memórias remotas. Numa rede ideal o custo de enviar uma mensagem entre dois nodos é independente quer da localização dos nodos, quer do tráfego na rede, mas depende do tamanho da mensagem.

Figura: 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.

Um atributo da definição do modelo do multi-computador prevê que os acessos à memória local (mesmo nodo) são menos onerosos que os acessos à memória remota (nodos diferentes). Isto é, as leituras e as escritas são menos onerosas que o envio e a recepção de mensagens. Assim, é desejável que os acessos aos dados sejam mais frequentes que os acessos à memória remota. Esta propriedade, chamada localidade, é o terceiro requisito fundamental do software paralelo, a juntar à concorrência e à escalabilidade. A importância da localidade depende do rácio, custos dos acessos remoto para local. Este rácio que pode variar de 10:1 até a 1000:1, depende do rendimento relativo do computador local, da rede e dos mecanismos usados para transferir dados para a (e da) rede.

Outros Modelos de Máquinas.

Revemos, aqui, arquitecturas importantes de computadores paralelos (vários estão ilustrados na figura 1.6) e discutimos, brevemente, a forma como diferem do modelo idealizado do multi-computador.

O multi-computador é muito semelhante ao que é vulgarmente chamado de computador de memória distribuída MIMD. Esta designação quer significar que cada processador pode executar uma linha separada de instruções sobre os seus dados locais; memória distribuída significa que a memória está espalhada entre processadores ao invés de estar concentrada num local central. A principal diferença entre um multi-computador e um computador MIMD de memória distribuída é que no último, o custos de envio de uma mensagem entre dois nodos pode não ser independente da localização dos nodos e do tráfego na rede. Estes tópicos são discutidos no Capítulo 3. Exemplos desta classe de máquinas incluem o IBM SP, o Intel Paragon, o CM Thinking Machine, o Cray T3D, o Meiko CS-2 e o nCUBE.

Uma outra importante classe de computadores paralelos é o multiprocessador ou computador MIMD de memória partilhada. Nos multiprocessadores, todos os processadores partilham o acesso a uma memória comum, tipicamente, através de um barramento ou de uma hierarquia de barramentos. No modelo idealizado PRAM Máquina Paralela de Acesso Aleatório, frequentemente usado em estudos teóricos de algoritmos paralelos, qualquer processador pode fazer o acesso a qualquer célula de memória na mesma quantidade de tempo. Escalar esta arquitectura, na prática, introduz usualmente alguma forma de hierarquia de memória; em particular, a frequência com que são feitos os acessos à memória pode ser substancialmente reduzida se forem feitas cópias dos dados mais frequentemente usados numa cache associada com cada processador. O acesso a esta cache é muito mais rápido que o acesso à memória partilhada; assim, a localidade é habitualmente importante e as diferenças entre multi-computadores e multi-processadores são, na verdade, questões de escala. Os programas desenvolvidos para multi-computadores podem também ser executados eficientemente nos multi-processadores, porque o modelo por memória partilhada permite a realização eficiente do modelo por passagem de mensagens. Exemplos desta classe de máquinas incluem o Silicon Graphics Challenge, o Sequent Simetry e a maior parte das estações de trabalho multi-processador.

Uma classe mais especializada de computadores paralelos é o computador SIMD, (instrução simples múltiplos dados). Nas máquinas SIMD, todos os processadores executam a mesma linha de instruções sobre diferentes pedaços de dados. Esta abordagem pode reduzir a complexidade, tanto do hardware como do software, mas é, apenas, apropriada para problemas especializados, caracterizados por elevados níveis de regularidade, por exemplo, processamento de imagem e certas simulações numéricas. Os algoritmos para um multi-computador não podem, em geral, ser executados eficientemente em computadores SIMD. O MasPar MP é um exemplo de uma máquina desta classe.

Figura: 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.

Duas classes de sistemas de computadores que são algumas vezes usados como computadores paralelos são as redes de computadores em área locais (LAN), nas quais computadores com relativa proximidade física ( e.g. no mesmo edifício) são ligados por uma rede rápida e as redes de computadores em área extensas (WAN), nas quais estão ligados computadores distribuídos geograficamente. Embora sistemas desta espécie introduzam preocupações adicionais tais como a fiabilidade e a segurança, estes podem ser vistos para muitos efeitos como multi-computadores, apesar dos elevados custos de acesso remoto. A Ethernet e ATM (Modo de transferência assíncrono) são comummente usadas como tecnologias de rede.

Um Modelo de Programação Paralela

O modelo de máquina de Von Neumann assume um processador capaz de executar sequências de instruções. Uma instrução pode especificar, para além de várias operações aritméticas, o endereço de um dado a ser lido ou escrito na memória e/ou o endereço da próxima instrução a executar. Enquanto é possível programar um computador em termos deste modelo básico, escrevendo em linguagem máquina, este método para a maior parte dos casos é proibitivamente complexo, porque é preciso ter debaixo de controlo milhões de posições de memória e organizar a execução de milhões de milhares de instruções máquina. Assim, aplicam-se técnicas de desenho modular, em que programas complexos são construídos de componentes simples e os componentes são estruturados internamente em termos de abstracções de alto-nível tais como estruturas de dados, laços iterativos e procedimentos. As abstracções, tais como os procedimento,s tornam a exploração da modularidade mais fácil permitindo que os objectos possam ser manipulados sem ter de tomar em consideração a sua estrutura interna. É assim nas linguagens de alto-nível tais como o Fortran, o Pascal, o C e a Ada que permitem que os projectos expressos em termos destas abstracções sejam traduzidos automaticamente em código executável.

A programação paralela acrescenta fontes adicionais de complexidade; se fossemos programar ao mais baixo nível, não apenas iríamos aumentar o número de instruções, como iríamos, também, ter de gerir explicitamente a execução de milhares de processadores e coordenar milhões de interacções entre processadores. Por isso, a abstracção e a modularidade são, pelo menos, tão importantes como na programação sequencial. De facto, iremos enfatizar a modularidade como o quarto requisito fundamental da programação paralela, a acrescentar à concorrência, à escalabilidade e à localidade.

Tarefas e Canais

Consideramos a seguir a questão de saber que abstracções são apropriadas e úteis num modelo de programação paralela. Claramente, são necessários mecanismos que favoreçam a discussão explícita da concorrência eda localidade e que facilitem o desenvolvimento de programas escaláveis e modulares. São também necessárias abstracções simples de trabalhar que se ajustem ao modelo arquitectónico do multi-computador.

Figura: 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.

De entre as numerosas possíveis abstracções que poderiam ser consideradas para este efeito, duas preenchem particularmente bem os requisitos: a tarefa e o canal. Estes são ilustrados na figura 1.7 e podem ser resumidos como segue:

1. Uma computação paralela compreende uma ou mais tarefas. As tarefas executam concorrentemente. O número de tarefas pode variar durante a execução do programa.
2. Uma tarefa esconde um programa sequencial e uma memória local. (É, com efeito, uma máquina virtual de Von Neumann.). Adicionalmente um conjunto de portas-de-entrada e portas-de-saída definem o seu interface com o ambiente.
3. Uma tarefa pode efectuar quatro acções básicas, para além de ler e escrever na sua memória local (figura 1.8): enviar mensagens pelas suas portas de saída, receber mensagens, pelas suas portas de entrada, criar novas tarefas e terminar.
4. A operação de envio é assíncrona: completa-se imediatamente. A operação de recepção é síncrona: leva à execução da tarefa ficar bloqueada, até que esteja disponível uma mensagem.
5. Pares de portas de entrada e porta de saída, canais, podem ser ligados por filas de mensagens chamadas canais. Os canais podem ser criados e eliminados e as referências aos canais (portas) podem ser incluídas nas mensagens, por isso a conectividade pode variar dinamicamente.
6. As tarefas podem ser atribuídas a processadores físicos de várias maneiras; a correspondência utilizada não afecta a semântica de um programa. Em particular, múltiplas tarefas podem ser alojadas a um mesmo processador.(Podemos imaginar uma única tarefa a ser alojada a múltiplos processadores, mas essa possibilidade não é considerada aqui.)

A noção de tarefa fornece um mecanismo para a falar acerca da localidade: os dados contidos na memória local, estão perto; os outros dados são remotos. A abstracção canal fornece um mecanismo para indicar que a computação numa tarefa necessita dos dados de uma outra tarefa para poder prosseguir. (Isto é designado por dependência de dados). O seguinte exemplo, simples, ilustra algumas destas características.

Figura: 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.

---------------------------------------------------
$\bullet$ Exemplo 1.1 (Construção de uma ponte) Considere o seguinte problema do mundo real. Uma ponte vai ser montada com vigas que estão a ser construídas numa fundição. Estas duas actividades são organizadas fornecendo camiões para transportar vigas da fundição para o lugar da ponte. A situação é ilustrada na figura 1.9(a), com a fundição e a ponte representadas como tarefas e o fluxo de camiões como um canal. É de notar que esta abordagem permite que a montagem da ponte e a construção das vigas possam prosseguir em paralelo sem coordenação explícita: Os trabalhadores da fundição põem as vigas nos camiões à medida que estes são produzidas e os trabalhadores na montagem juntam vigas à ponte à medida que estas chegam.

Uma desvantagem deste esquema é que a fundição pode produzir vigas mais depressa do que os trabalhadores na montagem podem usá-las. Em alternativa, para evitar que o lugar da ponte fique superlotada com vigas, os trabalhadores na montagem podem encomendar explicitamente mais vigas quando o depósito de vigas baixar de um certo nível. Este refinamento da abordagem é ilustrada na figura 1.9(b), com o fluxo de encomendas representado por um segundo canal. O segundo canal pode, também, ser usado para suspender o fluxo de vigas quando a ponte estiver pronta.
------------------------------------------------

Figura: 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.

Examinamos, agora, algumas outras propriedades do modelo de programação tarefas/canais: rendimento, independência da correspondência, modularidade e determinismo.

Rendimento As abstracções na programação sequencial, tais como, os procedimentos e as estruturas de dados, são efectivas na medida em que podem ser directa e eficientemente realizadas no computador de Von Neumann. A tarefa e o canal tem uma correspondência directa similar no multi-computador. Uma tarefa representa uma porção de código que pode ser executado sequencialmente num único processador. Se duas tarefas que partilham um canal forem alojadas em diferentes processadores, a conexão por canal é realizada como uma comunicação entre processadores; se estiverem alojadas ao mesmo processador, pode ser usado um outro qualquer mecanismo mais eficiente .

Independência Porque as tarefas interagem usando o mesmo mecanismo (canais), independentemente da localização das tarefas, o resultado produzido por um programa não depende do local onde as tarefas executam. Desta forma, os algoritmos podem ser desenhados e implementados sem entrar em consideração com o número de processadores que os irão executar; de facto, os algoritmos são frequentemente desenhados para criar mais tarefas do que processadores. Esta é uma forma directa de atingir a noção de escalabilidade: na medida em que, o número de processadores aumenta, o número de tarefas por processador é reduzido, mas o algoritmo, ele próprio, não necessita de ser modificado. A criação de mais tarefas do que processadores pode também servir para esbater os atrasos das comunicações, fornecendo outras computações que podem ser efectuadas enquanto decorre a comunicação para acesso a dados remotos.

Modularidade Num projecto modular vários componentes de um programa são desenvolvidos separadamente, como módulos independentes, e depois combinados para obter um programa completo. As interacção entre módulos estão circunscritas a interfaces bem definidos. Desta forma, as implementações dos módulos podem mudar sem modificação de outros componentes e as propriedades de um programa podem ser determinadas da especificação dos seus módulos e do código que mantém os módulos juntos. Quando aplicado com sucesso, o desenho modular reduz a complexidade dos programas e facilita a reutilização de código.

A tarefa é um bloco natural para o desenho modular. Tal como é ilustrado na figura 1.10 uma tarefa esconde tanto os dados como o código que opera sobre esses dados; os portos através dos quais envia e recebe mensagens constituem o seu interface. Assim, as vantagens do desenho modular sumariadas no parágrafo anterior estão directamente acessíveis no modelo tarefa/canal que usado convenientemente pode reduzir a complexidade da programação e facilitar a reutilização de código.

Há uma grande semelhança entre o modelo tarefa/canal e o popular paradigma da programação por objectos. As tarefas, como os objectos, escondem os dados e o código que opera sobre esses dados. Características distintivas do modelo tarefa/canal são a sua concorrência, o uso de canais, em vez de chamada a métodos para especificar a interacção e a falta de mecanismos de hierarquia.

Determinismo Um algoritmo ou programa é determinístico se a execução com uma entrada particular produz sempre o mesmo resultado. É não-determinístico se execuções múltiplas com a mesma entrada poder dar diferentes resultados. Apesar do não-determinismo ser algumas vezes útil e poder ser suportado, um modelo de programação que torne fácil a escrita de programas determinístico é altamente desejável. Os programas determinístico tendem a ser mais fáceis de compreender. Também, quando se verifica a sua correcção, é, apenas, necessário considerar uma única sequência de execução, em vez de todas as possíveis execuções.

Os instrumentos de interacção suportados pelo próprio modelo tarefa/canal tornam o determinismo relativamente fácil de garantir. Tal como veremos na Parte II quando considerarmos os instrumentos de programação, é suficiente verificar que cada canal tem um único emissor e um único receptor e que a tarefa que está a receber no canal fica bloqueada até que a operação de recepção se complete. Estas condições podem ser relaxadas quando se pretender interacção não-determinística.

Se no exemplo de construção da ponte, o determinismo significar que a mesma ponte virá a ser construída independentemente das velocidade a que a fundição constrói vigas e os operários na montagem juntam as vigas. Se os operários na montagem forem à frente da fundição, terão de ficar bloqueados até que estejam disponíveis mais vigas, em vez de tentarem continuar a construção com um número insuficiente de vigas. De forma semelhante, se a fundição produzir vigas mais depressa do que os operários na montagem poderem usa-las, essas vigas irão simplesmente acumular-se até que sejam necessárias. O determinismo seria garantido mesmo se várias pontes estivessem a ser construídas ao mesmo tempo: enquanto as vigas destinadas a diferentes pontes viajarem por canais distintos, não podem ser confundidas.

Figura: 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.

Outros Modelos de Programação

No capítulos subsequentes, o modelo tarefa/canal irá muitas vezes ser usado para descrever algoritmos. Contudo, este modelo não é certamente a única abordagem que pode ser tomada para representar a computação paralela. Muitos outros modelos de programação têm vindo a ser propostos, diferindo na sua flexibilidade, mecanismos de interacção de tarefas, granularidade das tarefas e o suporte para a localidade, escalabilidade e modularidade. Aqui revemos várias alternativas. Passagem de Mensagens O modelo por passagem de mensagens é, hoje, provavelmente o mais largamente utilizado modelo de programação. Os programas por passagem de mensagens, tal como os programas tarefa/canal, criam múltiplas tarefas, com cada tarefa escondendo os seus dados locais. Cada tarefa é identificada por um nome único e as tarefas interagem enviando (e recebendo) mensagens para (de) tarefas nomeadas. Nesta abordagem, a passagem de mensagens é na verdade uma variante menor do modelo tarefa/canal, diferindo apenas no mecanismo usado para transferir os dados. Por exemplo, em vez de enviar uma mensagem pelo ``canal ch'' pode enviar-se uma mensagem para a ``tarefa 17''. Estudaremos com maior detalhe no capítulo 8, o modelo de passagem de mensagens, quando discutirmos o Interface para a Passagem de Mensagens^1.1. Nesse capítulo, iremos explicar que a definição de canais é uma disciplina útil, mesmo no projecto de programas por passagem de mensagens, porque nos força a conceptualizar a estrutura de comunicações de um programa paralelo.

O modelo de passagem de mensagens não exclui a criação dinâmica de tarefas, a execução de múltiplas tarefas por processador, ou a execução de diferentes programas por diferentes tarefas. Contudo, na prática, a maior parte dos sistemas de passagem de mensagens cria um número fixo de tarefas idênticas, no arranque do programa, não permitindo criar ou destruir tarefas durante a execução do programa. Estes sistemas dizem-se realizar o modelo de programação SPMD (um único programa e múltiplos dados) porque cada tarefa executa o mesmo programa mas opera em dados diferentes. Tal como é explicado em capítulos subsequentes o modelo SPMD é suficientemente para um largo espectro de problemas de programação paralela mas impede o desenvolvimento de alguns algoritmos paralelos.
Paralelismo nos Dados Um outro modelo de programação paralela usado comummente, paralelismo nos dados, faz o aproveitamento da concorrência que deriva da aplicação da mesma operação a múltiplos elementos de uma estrutura de dados, por exemplo, ``somar 2 a todos os elementos de uma lista'', ou `` aumentar o salário de todos os empregados, com cinco anos de serviço''. Um programa paralelo nos dados consiste de uma sequência de tais operações. Como cada operação, num determinado elemento de uma estrutura de dados, pode ser pensada como uma tarefa independente, a granularidade da computação paralela nos dados é reduzida, o conceito de localidade dos dados não surge naturalmente. Assim os compiladores de paralelismo nos dados, muitas vezes, obrigam o programador a fornecer informação sobre a forma como os dados deverão ser distribuídos pelos processadores, por outras palavras, como os dados deverão ser distribuídos entre tarefas. O compilador pode então traduzir o programa de paralelismo nos dados numa descrição formulada em SPMD, por meio disso, gerando o código de comunicação automaticamente. Discutimos o modelo de paralelismo nos dados com maior detalhe no capítulo 7 sob o tópico High Performance Fortran. Naquele capítulo mostramos que o desenho de algoritmos e as técnicas de análise desenvolvidas para o modelo tarefa/canal aplicam-se directamente aos programas de paralelismo nos dados; em particular, fornecem os conceitos necessários para compreender a localidade e a escalabilidade dos programas de paralelismo nos dados. Memória Partilhada No modelo de programação por memória partilhada, as tarefas partilham um espaço de endereçamento que lêm e escrevem assincronamente. Vários mecanismos tais como fechos e semáforos podem ser usados para controlar o acesso à memória partilhada. Uma vantagem deste modelo do ponto de vista do programador é que falta a noção de ``propriedade'' e, por isso, não é necessário especificar explicitamente a comunicação dos dados do produtor para o consumidor. Contudo, torna-se muito mais difícil compreender e manipular a localidade, um tópico de grande importância (já antes referido) na maioria das arquitecturas de memória partilhada. Pode também ser mais difícil escrever programas determinístico.

Exemplos de Algoritmos Paralelos

Concluímos este capítulo apresentando alguns exemplos, quatro, de algoritmos paralelos. Não entramos em consideração, aqui, com o processo através do qual aqueles algoritmos foram derivados ou com a sua eficiência; estes temas são discutidos nos capítulos 2 e 3, respectivamente, O objectivo é simplesmente introduzir os algoritmos paralelos e a sua descrição em termos de tarefas e canais.

Os dois primeiros algoritmos descritos têm uma estrutura SPMD, o terceiro cria tarefas dinamicamente durante a execução do programa e o quarto usa um número fixo de tarefas mas tem diferentes tarefas a efectuar funções diferentes.

Diferenças Finitas

Consideramos em primeiro lugar um problema de diferenças finitas a uma dimensão, em que é dado um vector $X^{(0)}$ de tamanho $N$, pretendendo-se calcular $X^{(T)}$, sendo para

$0<i<N-1, 0\leq t <T$

$$X_i^{(t+1)} = X_{i-1}^{(t)} + 2 X_i^{(t)} + X_{i+1} ^{(t)} \over 4$$

Figura: 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.

Isto é, temos de actualizar, repetidamente, cada elemento de $X$, sem que nenhum elemento no passo $t + 1$ possa ser actualizado até que os seus vizinhos tenham sido actualizados no passo $t$.

Um algoritmo paralelo para este problema cria $N$ tarefas, uma por cada ponto, em $X$. A tarefa $i$ toma o valor $X_i^{(0)}$ sendo responsável por calcular, em $T$ passos, os valores de $X_i^{(0)}$, $X_i^{(1)}$, ..., $X_i^{(T)}$. Assim, no passo $t$, tem de obter os valores de $X_{i-1}^{(t)}$ e $X_{i+1}^{(t)}$, das tarefas $i-1$ e $i+1$, Especificamos esta transferência de dados definindo canais que ligam cada tarefa com as vizinhas ``à esquerda'' e ``à direita'', como se mostra na figura 1.11, e requerendo que em cada passo $t$ , cada tarefa $i$, outra que não a tarefa $0$ e tarefa $N-1$

1. enviar os seus dados $X_i^{(t)}$ pelas portas à esquerda e direita
2. receber $X_{i-1}^{(t)}$ e $X_{i+1}^{(t)}$ pelas portas à esquerda e direita, e
3. usar valores acima para calcular $X_i^{(t+1)}$.

É de notar que $N$ tarefas podem executar independentemente, com uma única restrição à execução, na sincronização forçada pelas operações de recepção. Esta sincronização assegura que não é actualizado o valor de nenhum dos dados, até que os valores dos dados nos tarefas vizinhas tenham sido actualizadas no passo $t$. Por isso, a execução é determinística.

Interacções aos Pares

O nosso segundo exemplo usa uma estrutura de canais semelhante mas exige um algoritmo de comunicação mais complexo. Muitos problemas necessitam da computação de todas as $N(N-1)$ pares de interacções $I(X_i, X_j),i \neq j$, entre $N$ dados, $X_0$, ...., $X_{N-1}$. As interacções podem ser simétricas, sendo nesse caso, $I(X_i, X_j) = + -$ e apenas $N(N-1)/2$ interacções necessitam de ser calculadas. Por exemplo, em dinâmica molecular podemos querer a força total do vector $f_i$ a actuar em cada átomo $X_i$ definida como se segue:

$$F_i = \sum_{j=0}^{N-1} F(X_i, X_j).$$

Cada átomo é representado pela sua massa e coordenadas Cartesianas. $F(X_i, X_j)$ denota a atracção ou repulsão mútua entre átomos $X_i$ e $X_j$; neste exemplo, $F(X_i, X_j)$ = - $F(X_i, X_j)$, isto é, as interacções são simétricas.

Um algoritmo paralelo simples para o problema geral de interacções pares pode criar $N$ tarefas. À tarefa $i$ é entregue o dado $X_i$ e é responsável por calcular as interacções ${I(X_i,X_j): i \neq j}$ Poderíamos ser levados a pensar que como cada tarefa necessita de um dado de toda a outra tarefa, seriam necessários $N(N-1)$ canais para efectuar as necessárias comunicações. Contudo, é possível uma estrutura mais económica que usa apenas $N$ canais. Estes canais são usados para ligar $n$ tarefas num anel uni-direccional (figura 1.12(a)). Assim, cada tarefa tem uma porta de entrada e uma porta de saída. Cada tarefa começa por iniciar um tampão (com o valor do seu dado local) e um acumulador que mantém o resultado do cálculo. Então, repetidamente

• envia o valor contido no tampão pela porta de saída
• recebe um dado no tampão pela porta de entrada
• calcula a interacção entre aquele dado e o seu próprio dado, e
• usa a interacção calculada para actualizar o seu acumulador local

Este ciclo envia-recebe-calcula é repetido $N-1$ vezes, tendo como efeito a fluxo dos $N$ dados ao longo do anel. Cada tarefa vê todos os dados e é capaz de calcular todas as $N-1$ interacções que envolvem o seu dado. O algoritmo envolve $N-1$ comunicações por tarefa.

Se as interacções forem simétricas, então, podemos reduzir a metade, tanto o número de interacções efectuadas como o número de comunicações através do refinamento da estrutura de comunicações. Assumamos por simplicidade que $N$ é ímpar. São criados $N$ canais adicionais, ligando cada tarefa à tarefa desviada no anel de $\lfloor N/2\rfloor$ (figura 1.12(b)).

Figura: 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.

Cada vez que é calculada uma interacção $I(X_i,X_j)$ entre um dado local $X_i$ e o dado $X_j$ que chega, este valor é acumulado não apenas no acumulador $X_i$ mas também no outro acumulador que circula com $X_j$. Depois de $\lfloor N/2\rfloor$ passos, o acumulador associado com os valores circulados regressam a tarefa mãe usando os novos canais e são combinados com os acumuladores locais. Assim cada interacção simétrica é efectuada só uma vez: quer como $I(X_i,X_j)$ no nodo que contém $X_i$ ou como $I(X_j,X_i)$ no nodo que contém $X_j$.

Pesquisa

O exemplo seguinte ilustra a criação dinâmica de tarefas e canais durante a execução de programas.

procedimento pesquisa(A)}
início
  se (solução(A) então
     score = eval(A)
     reportar solução e pontuação
  senão
     para-cada descendente (Ai) de A
        pesquisar (A(i))}
     fim-para
  fim-se
fim

Algoritmo 1.1 Uma formulação recursiva de um algoritmo simples de pesquisa. Quando chamada para expandir um nodo da árvore de pesquisa, este procedimento verifica se o nodo em questão representa uma solução. Se não, o algoritmo faz chamadas recursivas ao mesmo prxocedimento para expandir cada um dos nodos descendentes.
O algoritmo 1.1 explora a árvore de pesquisa procurando nodos que correspondam a ``soluções''. Um algoritmo paralelo para este problema pode ser estruturado como segue. Inicialmente, uma única tarefa é criada como raiz da árvore. A tarefa avalia o seu nodo e então, se o nodo não for uma solução, cria uma nova tarefa para cada chamada a pesquisa (sub-árvore). Um canal criado para cada nova tarefa é usado par retornar à tarefa mãe qualquer solução localizada na suas sub-árvores. Assim novas tarefas e canais são criados na crista da vaga à medida que a procura progride na árvore de pesquisa (figura 1.13).

Figura: 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.

Estudo de Parâmetros

Nos chamados problemas embaraçadamente paralelos, um computação consiste de um certo número de tarefas que podem executar mais ou menos independentemente, sem comunicação. Estes problemas são facilmente adaptados para execução paralela. Um exemplo é o estudo de parâmetros, em que o mesmo cálculo tem de ser efectuado usando uma gama de diferentes parâmetros de entrada. Os valores dos parâmetros são lidos de um ficheiro de entrada e os resultados dos diferentes cálculos são escritos num ficheiro de saída. Se o tempo de execução por problema for constante e cada processador tiver o mesmo poder de cálculo, então basta fazer a partição dos problemas existentes em lotes de igual dimensão e alocar cada um daqueles lotes por cada processador. Noutras situações, podemos escolher usar a estrutura ilustrada na figura 1.14. As tarefas de entrada e de saída são responsáveis por ler e escrever os ficheiros de entrada e de saída, respectivamente. Cada tarefa trabalhadora (tipicamente uma por processador) pede, repetidamente, valores de parâmetros da tarefa de entrada, faz cálculos usando estes valores e envia os resultados para a tarefa de saída. Porque os tempos de execução variam, as tarefas de entrada e de saída não podem esperar receber mensagens dos vários trabalhadores em qualquer ordem. Em vez disso, uma estrutura de muitos-para-um é usada para permitir-lhes receber mensagens dos vários trabalhadores por ordem de chegada.

Figura: 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.

A tarefa de entrada responde a um trabalhador através do envio de um parâmetro para esse trabalhador. Assim, o trabalhador que enviou o pedido para a tarefa de entrada espera, simplesmente, pela chegada do parâmetro no seu canal de resposta. Em alguns casos, a eficiência pode ser melhorada por pré-extracção, isto é, pedindo o próximo parâmetro antes deste ser necessário. O trabalhador pode efectuar o cálculo enquanto o pedido está a ser processado pela tarefa de entrada.

Porque este programa usa estruturas de comunicação de muitos-para-um a ordem pela qual os cálculos são efectuados não é necessariamente determinada. Contudo, este não-determinismo afecta apenas a alocação de problemas aos trabalhadores e a ordenação de resultados no ficheiro de saída e não os resultados efectivamente calculados.

Resumo

Este capítulo introduziu quatro atributos desejáveis da programação paralela: concorrência, escalabilidade, localidade e modularidade. A Concorrência refere a habilidade de efectuar muitas acções simultaneamente; isto é essencial se um programa for para ser executado em mais que um processador. A Escalabilidade indica a capacidade de adaptação ao aumento do número de processadores e é igualmente importante, na medida em que, o número de processadores parece estar a crescer na maior parte dos ambientes. A Localidade significa uma elevado taxa de acesso a memória local por acesso a memória remota (comunicações); isto é a chave para o elevado rendimento das arquitecturas de multi-computador. A Modularidade - decomposição de entidades complexos em componentes mais simples - é um aspecto essencial na engenharia do software, tanto em computação paralela como em computação sequencial.

O modelo de máquina paralela do multi-computador e o modelo de programação tarefa/canal introduzido neste capítulo irá ser usado em discussões subsequentes de desenho, análise e implementação de algoritmos paralelos. O multi-computador compreende um mais computadores de Von Neumann ligados através de uma rede de interconexão. É um modelo de máquina simples e realista que fornece uma base para o desenho de programas paralelos, escaláveis e portáveis. Um modelo de programação baseado em tarefas e canais simplifica a programação de multi-computadores fornecendo abstracções que nos permitem falar da concorrência, localidade e comunicação, de uma maneira independente da máquina e fornecendo uma base para a construção modular de programas paralelos.

Desenho de Algoritmos Paralelos

Agora que já discutimos a natureza dos algoritmos estamos, agora preparados para examinar podemos avançar para a análise das formas de os desenhar. Neste capítulo, mostramos como a especificação de um problema é traduzida num algoritmo que exibe concorrência, escalabilidade e localidade. Os temas relacioandos com amodularidade são discutidos no Capítulo 4.

O desenho de algoritmos paralelos não é facilmente reutível a receitas simples. Pelo contrário, requere uma espécie de pensamento integrado, communmente designado por ``criatividade''. Contudo, pode beneficiar de uma abordagem metodológica que maximize a gama de opções consideradas, que forneça os mecanismos necessários à avaliação de alternativas e que reduza os custos de recuperação de más soluções. Apresentamos aquela abordagem e ilustramos com a sua aplicação a uma gama de problemas. Durante o processo esperamos que o leitor desenvolva a intuição do que constitui um bom algorimto paralelo.

Depois de estudar este capítulo, o leitor deverá ser capaz de desenhar algoritmos paralelos simples de uma maneira metódica e reconhecer as nuances de desenho que comprometem a eficiência ou a escalabilidade. Deverá ser capaz de particionar os cálculos, usando amnbas as técnicas de decomprosição em funcões e em domínios e saber reconhecer e implementar estruturas de comunicação, tanto locais como globais, estáticas e dinâmicas, estruturadas e não-estrauturadas, síncronas e assíncronas. Deverá, também, ser capaz de usar o agrupamento como um meio de reduzir os custos de comunicação e de implementação e deverá ficar familiarizado com uma gama de estratégias de balanceameto de carga.

Metodologia

A maior parte dos problemas tem várias soluções paralelas. A melhor solução pode diferir da sugerida pelos algorimtos sequenciais existentes A metodologia que descrevemos tem como propósito fomentar uma abordagem exploratória ao projecto que considera, em primeiro lugar, temas tais como a concorrência, sendo relegados para mais tarde os aspectos do processo de desenho específicos da máquina.

Esta metodologia estrutura o processo de desenho em quatro etapas distintas:partição, comunicação, agrupamento e arranjo. (O acrónimo PCAM pode servir para facilitar a lembrança). Nas duas primeiras etapas, pomos a ênfase na concorrência e na escalabilidade tentamos descobrir algoritmos que possuam estas qualidades. Na terceira e quarta etapas, a atenção é dirigida para a localidade e outros temas relacionados com a eficiência. As quatro etapas são ilustradas na figura 2.1 e pode ser sumariada como segue:

1. Partição. Os cálculos a efectuar e os dados usados são decompostos em pequenas tarefas. São ignoradas aspectos prático, tais como, o número de processadores na arquitectura alvo e a atenção é posta no reconhecimento das oportunidades para a execução paralela.

2. Comunicação. Determinam-se os requisitos de comunicação necessários para coordenar a execução das tarefas e definem-se os algoritmos e as estruturas de comunicação.

3. Agrupamento. Avaliam-se as estruturas de comunicação e as tarefas, definidas nas duas primeiras etapasno que diz respeito aos requisitos de eficiência e custos de realização. Se se revelar necessário as tarefas são combinadas em tarefas maiores para melhor a eficiência ou reduzir os custos de realização.
4. Arranjo. Cada tarefa é atribuída a um processador de forma a tentar satisfazer o objectivo de maximização da utilização dos processadores que compete como o objectivo de minimização dos custos de comunicação. O arranjo pode ser especificado estaticamente ou determinado dinamicamente por algoritmos de balanceamento de carga.

Figura: 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.

O resultado deste processo de desenho pode ser um programa que cria e destrói, dinamicamente, tarefas usando técnicas de balanceamento de carga para controlar o arranjo de tarefas entre processadores. Em alternativa, pode ser um programa SPMD que cria, exactamente, uma tarefa por processador. O messo processo de descoberta de algoritmos é aplicável em ambos os casos, contudo, se o objectivo é produzir um programa SPMD, os temas associados com o arranjo são incorporados na fase de agrupamento do processo de desenho.

O desenho de algoritmos paralelos é apresentado aqui como uma actividade sequencial. Na prática, contudo, é um processo altamente paralelo, com muitas questões consideradas simultaneamente. Embora, tentemos evitar ter de andar para trás, a avaliação, parcial ou completa, de um desenho pode necessitar de alterar decisões de desenho tomadas em etapas anteriores.

As seccões seguintes apresentam um exame promenorizado das quatro etapas do processo de desenho. Apresentamos princípios básicos, usamos exemplos para ilustrar a aplicação destes proncípios e incluímos listas de testes de desenho que podem ser usadas para avaliar os projectos à medida que são desenvolvidos. Nas secções finais deste capítulo usamos três estudos de casos para ilustrar a aplicação técnicas de desenho a problemas realísticos.

Partição

Num projecto a etapa de partição pretende expor as oportunidades para a execução paralela. Assim, a ênfase é posta na definição de um lardo número de pequenas tarfeas de forma a definir o que é designado por grão fino de decomposição de um problema. Tal como a areia fina é mais facilmente vazada do que uma pilha de de tijolos, uma decomposição de grão fino fornece a maior flexibilidade em termos do potencial paralelismo dos algoritmos. Em fases posteriores de desenho, a avaliação das necessidades de comunicação, a arquitectua alvo, ou questões da engenharia do software podem forçar-nos a por de parte oportunidades de execução paralela identificadas nesta etapa. Netss caso, revisitamos a partição originale agrupamos tarefas para aumentar o seu tamanho, ou granularidade. Contudo, nesta primeria etapa, gostariamos de evitar avaliar de antemão estratégias alternativas de partição.

Uma boa partição divide em pequenas partes, tanto a computação associada com um problema e os dados sobre os quais o cálculo é efectuado. Quando se desenha a partição, os programadores, na maior parte dos casos, em primeiro lugar, olham para os dados associados com um problema e, a seguir, determinam uma partição apropriada para os dados e no final trabalham na forma como associar a computação com os dados. Esta técnica de partição é designada por decomposição em domínios. A abordagem alternativa, começa por decompor a computação a ser efectuada e seguidamente trata dos dados - é designada por decomposição em funções. Estas são técnicas complemntares que podem ser aplicadas a a diferentes componentes de um mesmo problema, ou até aplicadas a diferenets mesmo problema, para obter diferentes soluções. Na primeira fase de desenho, procura-se evitar a replicação quer de cálculos quer de dados; ou seja, definem-se as tarefas de forma a dividir tanto os dados como os cálculos em dois conjuntos distintos. Esta opção permite diminuir os requisitos de comunicação.

Decomposição em Domínios

A utilização desta técnica visa decompor os dados associados a um problema de forma a obter pequenas partes, com tamanhos aproximadamente iguais. Seguidamente procura-se dividir os cálculos a executar, associando a cada operação os dados necessários. Esta divisão produz um certo número de tarefas, cada uma das quais comporta alguns dados e um conjunto de operações sobre estes. Se para efectuar uma operação forem precisos dados que estão noutras tarefas, impõe-se o estabelecimento de comunicações que façam a transferência de dados.

A decomposição em domínios compreende a entrada de dados, a saída de dados, ou a manipulação de dados intermédios durante a execução do programa, o que possibilita a criação de diferentes partições, baseadas em diferentes estruturas de dados. Uma regra básica consiste em definir as partições, dirigindo a atenção para as estruturas de dados maiores ou para as que são alvo de acessos mais frequentes. Se em diferentes fases dos cálculos, se opera em diferentes estruturas de dados ou se se exigem diferentes decomposições da mesma estrutura de dados, então, cada fase deverá ser tratada separadamente, determinando a posterior de que maneira os diferentes algoritmos deverão colaborar. A figura 2.2 ilustra a utilização desta técnica.

Figura: Ilustração da técnica de decomposição em domínios.
A decomposição tri-dimensional é a mais flexível

Decomposição em Funções

Esta técnica põe a ênfase nos cálculos, ao contrário da técnica anterior que se concentra nos dados. Se for possível dividir os cálculos num grupo disjunto de diferentes tarefas podem, a partir daí, examinar-se os requisitos de dados em cada tarefa. Se os dados, por sua vez, se revelarem disjuntos, poderemos concluir que a partição foi realizada com êxito. Se os dados se sobrepõem, então, teremos de considerar que um número significativo de comunicações terão se ser desencadeadas para evitar a replicação de dados. Esta última consideração é o ponto de partida para uma abordagem do problema a realizar com base na técnica anterior.

Apesar da decomposição em domínios ser considerada como fundamental, na maior parte dos algoritmos paralelos, a decomposição em funções pode revelar a estrutura de um problema fornecendo a base para uma optimização que de outra forma permaneceria escondida.

Esta técnica, quando associa a decomposição dos cálculos à decomposição do código executável, permite reduzir a complexidade geral de desenvolvimento de um programa. Este é muitas vezes o caso da modelação de um sistema complexo que pode ser estruturado como uma colecção de modelos mais simples, ligados através de interfaces.

Por exemplo, simulação do clima da terra pode compreender vários componentes representando a atmosfera, o oceano, o dióxido carbónico etc. Enquanto cada componente pode ser naturalmente paralelizável usando DD, o algoritmo paralelo, como um todo, é substancialmente mais simples se o sistema for inicialmente dividido usando DF, mesmo que este abordagem não produza um número significativo de tarefas.

Figura: Decomposição Mista na simulação do clima da terra.

Análise de Partições

Apresentamos em seguida um lista de perguntas, que deverão normalmente ser respondidas afirmativa mente, que asseguram que o desenho não contém falhas óbvias:

1. A partição encontrada define um número de tarefas, de pelo menos um ordem de grandeza superior ao número de processadores físicos?. Em caso negativo, poderá concluir-se que a margem de flexibilidade nas etapas posteriores de desenho pode ser diminuta.
2. A partição evita a redundância nos cálculos e requisitos de armazenamento dos dados? Se assim não for, o algoritmo resultante poderá não ser escalável no caso de se pretender lidar com grandes problemas.
3. As tarefas têm todas um tamanho comparável? Em caso negativo, não deverá ser fácil estabelecer o balanceamento de carga.
4. O número de tarefas é proporcional ao tamanho do problema? Espera-se que ao aumento do tamanho de um problema possa fazer-se corresponder o aumento do número de tarefa, ao invés de se aumentar o tamanho das tarefas individualmente. Se este não for o caso o algoritmo poderá não ser capaz de resolver um grande problema mesmo quando se dispõe de um número superior de processadores.
5. É possível identificar mais que uma partição alternativa. Lembrar que as etapas subsequentes de desenho poderão pôr em causa a partição considerada, pelo que se torna desejável explorar alternativas quer em DD quer em DF.

A resposta às questões formuladas acima, poderá sugerir que apesar de se ter cuidadosamente pensado numa partição, as etapas posteriores de desenho podem levar a concluir que a solução não é boa. Nesta circunstância, há um grande risco em prosseguir com a realização do modelo encontrado. A avaliação de rendimento surge então como uma técnica que irá permitir determinar se o desenho corresponde aos objectivos pretendidos apesar das aparentes deficiências. Como alternativa pode-se sempre revisitar a especificação do problema para determinar se existente métodos numéricos, que simplifiquem e optimizem o desenvolvimento da solução final.

Comunicação

As tarefas definidas por uma determinada partição poderão executar concorrentemente mas podem, em geral, não ter execução independente. Tipicamente, os cálculos efectuados por uma tarefa precisam de dados associados a outras tarefas. Nesta circunstância, os dados deverão ser transferidos entre tarefas de forma a possibilitar a continuação do cálculo.

No desenho de um algoritmo esta informação é especificada na fase de comunicação. À comunicação faz-se corresponder duas fases:

1. Define-se a estrutura de canais que ligam, directa ou indirectamente, as tarefas que precisam de dados (consumidoras), com as tarefas que possuem os dados (produtoras).

2. Especificam-se as mensagens que deverão ser enviadas ou recebidas nos canais.

Depende da tecnologia de realização utilizada a criação, ou não, desses canais durante a codificação do algoritmo. A definição de um canal tem custos intelectuais e físicos associados, por essa razão, é de evitar a criação de canais e comunicações desnecessárias. A procura de um rendimento óptimo, acrescenta ainda a necessidade de definir e organizar operações de comunicação, distribuídas entre várias tarefas, de tal forma que se garanta a execução concorrente.

Se a decomposição é em domínios, poderão ser dificéis de determinar os requisitos de comunicação. Com efeito, quando uma operação precisa de dados que estão em diferentes tarefas, poderá ser difícil organizar as comunicações de forma a que a transferência de dados se produza de forma eficiente. Em contraste com esta perspectiva, a comunicação associada à decomposição em funções corresponde muitas vezes ao fluxo de dados entre tarefas.

Na discussão que se segue pretende-se mostrar como são identificados os requisitos de comunicação e as operações de comunicação necessárias à sua satisfação. Para facilitar a exposição, consideraremos os seguintes eixos de discussão: local/global, estruturado/não-estruturado, estático/dinâmico e assíncrono/síncrono.

• Em comunicação local cada tarefa comunica com um pequeno conjunto de outras tarefas (vizinhas); em comunicação global cada tarefa precisa de comunicar com muitas outras tarefas.
• Em comunicação estruturada uma tarefa em conjunto com todos os seus vizinhos constitui uma estrutura regular; em contraste, as redes de comunicação não estruturada constituem grafos arbitrários.
• Em comunicação estática a identidade dos parceiros comunicantes é fixa, durante toda o programa; em comunicação dinâmica a identificação dos parceiros, que pode ser muito variável, é determinada por cálculos durante a própria execução.
• Numa comunicação síncrona a comunicação entre tarefas é feita coordenadamente; por oposição a este modo, em comunicação assíncrona não há qualquer tipo de coordenação.

Comunicação Local

Uma estrutura de comunicação local resulta de uma operação que precisa de dados de um pequeno número de outras tarefas. Nesta circunstâncias é imediata a definição de canais que liguem as tarefas responsáveis pela operação (consumidores) às tarefas que produzem os dados (produtoras) e a criação de operações apropriadas de recepção e envio, respectivamente.

Consideremos os requisitos de comunicação associados um cálculo simples numérico, o método das diferenças finitas de Jacobi. Neste tipo de problemas uma grelha multidimensional é repetidamente actualizada substituindo o valor em cada ponto, pelo valor de uma função aplicada a um pequeno número fixo de pontos. Ao conjunto de valores necessários para actualizar um ponto da grelha dá-se o nome de pontos de matriz. Se usarmos uma matriz de cinco pontos para cada valor $X_{i,j}$ duma grelha bidimensional $X$, obtemos:

$$X_{i,j}^{t+1}={4X^{(t)}_{i,j} +X^{(t)}_{i-1,} + X^{(t)}_{i+1,j} + X^{(t)}_{i,j-1} + X^{(t)}_{i,j+1} \over 8}.$$

Enquanto a técnica Jacobi é facilmente paralelizável (todos os pontos podem ser actualizados concorrentemente) o mesmo não se passa com a técnica anterior. Felizmente, podem ser usadas ordens de actualização variadas, o que dá um certo grau de liberdade, na escolha da ordem que maximiza o paralelismo existente.

Este exemplo ilustra a importância da estratégia de solução na determinação da eficiência de um programa paralelo.

A fórmula é aplicada repetidamente para calcular todos os valores de $X$, sendo a notação $X^{t}_{i,j}$ usada para referir o valor do ponto $X_{i,j}$ da grelha no passo $t$.

Se usarmos uma partição, com base numa decomposição em domínios, para criar uma tarefa para cada cada ponto na grelha, então, uma tarefa atribuída ao ponto $X_{i,j}$ deverá efectuar $t$ passos sequenciais. E para cada passo deverão ser calculados todos os elementos no numerador da fórmula acima, isto é, por cada uma das quatro tarefas vizinhas. Para que todos estes valores sejam conhecidos definem-se para cada tarefa, tantos canais quanto o número de vizinhos, Fig 2.4.

Figura: Estrutura de canais e tarefas para um problema de diferenças finitas usando 5 pontos de matriz

O algoritmo executado por cada uma das tarefas é:

para $t=0$ até $T-1$
send $X_{i,j}^{(t)}$ para cada vizinho
receive $X_{i-1,j}^{(t)}, X_{i+1,j}^{(t)}, X_{i,j-1}^{(t)}, X_{i,j+1}^{(t)}$ dos vizinhos
calcule $X_{i,j}^{(t)}$ usando a equação anterior
parafim

Tal como anteriormente foi dito o melhor algoritmo sequencial e a solução paralela podem usar diferentes técnicas. Em computação sequencial, a técnica de Gauss-Seidel é usada preferencialmente porque se obtêm soluções de precisão comparável, mas usando menos iterações. Neste caso, a equação anterior pode ser reformulado dando lugar a:

$$X_{i,j}^{t+1}={4X^{(t)}_{i,j} +X^{(t)}_{i-1,j} + X^{(t)}_{i+1,j} + X^{(t+1)}_{i,j-1} + X^{(t+1)}_{i,j+1} \over 8}.$$

Comunicação Global

Este tipo de operação corresponde a uma comunicação que envolve muitas tarefas. Neste caso pode não ser suficiente identificar os pares consumidor/produtor, porque isso resultaria em demasiadas comunicações, ou poderia impôr uma restrição à oportunidade para a execução concorrente. Consideremos, por exemplo, uma operação paralela de redução, isto é, uma operação que reduz $N$ valores distribuídos por $N$ tarefas usando um operador associativo de adição:

$$S=\sum_{i=0}^{N-1} X_i.$$

Se assumirmos que uma simples tarefa mestre precisa do resultado $S$ da operação, então, do ponto de vista estritamente local essa tarefa precisa dos valores $X_0, X_1$ etc... das tarefas $0,1$ etc. Isto, pode corresponder à definição de uma estrutura que torne possível a comunicação independente, entre cada tarefa e a tarefa mestre, sendo esta responsável pela adição dos valores e armazenamento do resultado. Contudo, porque a tarefa mestre apenas pode somar um valor de cada vez, a solução requere um tempo de $O(N)$ para adicionar os $N$ números o que, convenhamos, não parece ser uma boa solução paralela.

O exemplo ilustra dois problemas gerais, que se baseiam numa visão puramente local da comunicação que podem prejudicar a execução eficiente de algoritmos paralelos:

1. Algoritmo centralizado, não distribui nem a computação nem a comunicação. Uma simples tarefa pode estar envolvida em todas as operações.
2. Algoritmo sequencial, não favorece a execução concorrente de múltiplas comunicações e cálculos.

Comunicação e Computação Distribuída

Se pretendermos calcular a soma distribuída de $N$ números, atribuindo a cada tarefa $i, 0<i<N-1$ o cálculo da soma:

$$S_i=X_i+S_{i-1}.$$

As comunicações necessárias a este algoritmo deverão ser satisfeitas ligando as $N$ tarefas numa fila, Fig 2.7. A tarefa $N-1$ envia o seu valor para o seu vizinho na fila. Cada uma das tarefas $1$ a $N-2$ espera até receber a soma parcial do vizinho da direita, soma esse valor ao seu próprio valor e envia o resultado para o vizinho da esquerda. A soma global é calculada pela tarefa $0$ adicionando o seu próprio valor ao valor parcial, recebido da tarefa à direita. O algoritmo distribui as $N-1$ comunicações e somas, mas só permite a execução concorrente se o problema incluir múltiplas operações de soma. Nesta circunstância, a fila de tarefas pode ser usada como uma cadeia, através da qual fluem as somas parciais, que realiza uma soma simples em $N-1$ passos.

Pondo a Descoberto a Concorrência: Dividir para Paralelizar

As oportunidades para a execução e a comunicação concorrente podem muitas vezes ser expostas aplicando aos problemas uma estratégia de Dividir para Paralelizar. Para resolver um problema complexo ( tal com a soma de $N$ números) procura-se dividi-lo em dois ou mais problemas de tamanho idêntico (somar $N/2$ números). Este processo é então aplicado recursivamente, até atingir um conjunto de subproblemas não subdivisíveis (soma de dois números). Esta técnica descrita no algoritmo 2.1 é efectiva em processamento paralelo quando os subproblemas podem ser resolvidos concorrentemente. Se tomarmos como exemplo o a soma de $N$ números pode aproveitar-se a seguinte equação $N=2^n,n>0, n$ inteiro:

$$\sum_{i=0}^{2^n-1} = \sum_{i=0}^{2^{n-1}-1} + \sum_{i=2^{n-1}}^{2^n-1}.$$

Os dois somatórios à direita podem ser executados concorrentemente. Podendo obviamente ser subdivididos se $n>1$, gerando uma estrutura em árvore na fig. 2.8. Os somatórios ao mesmo nível na árvore, à profundidade $n=\log n$, podem ser executados concorrentemente, obtendo, desta forma, um tempo de execução $O(\log n)$ em vez de $O(n)$.

Sumarizando, para obter um algoritmo suficientemente eficiente foram distribuídos os $N-1$ cálculos e comunicações e modificada a ordem de execução, de forma a cada um poder prosseguir concorrentemente. O resultado é uma estrutura regular de comunicação, em que cada tarefa comunica com um pequeno número de tarefas vizinhas.

Comunicação Dinâmica Não Estruturada

A comunicação não estruturada não causa dificuldades conceptuais especiais nas fases iniciais de desenho. O mesmo não acontece em fases mais adiantadas quando se pretende, por exemplo, agrupar ou fazer o arranjo dos processadores. Em particular, pode ser necessário desenvolver algoritmos sofisticados, para determinar a estratégia de agrupamento que crie tarefas de tamanhos aproximadamente iguais e que, ao mesmo tempo, minimize as comunicações, por redução do número de tarefas interactuantes. A juntar a estas dificuldades, se os requisitos de comunicação tiverem carácter dinâmico, há ainda que considerar, se a relação custo/benefício justifica a sobrecarga resultante da execução frequente dos algoritmos.

Comunicação Assíncrona

A necessidade de comunicação assíncrona entre tarefas ocorre frequentemente, em situações em que um conjunto de tarefas tem que fazer acesso, periodicamente, aos elementos de uma estrutura partilhada de dados . Se considerarmos que essa estrutura de dados é demasiadamente grande ou é alvo de acessos, com frequência suficientemente elevada para não justificar o encapsulamento numa única tarefa, o mecanismo capaz de garantir operações assíncronas de leitura e escrita e a distribuição da estrutura de dados deverá assegurar que:

1. a estrutura é distribuída pelas tarefas. E cada tarefa, para além de fazer cálculos, gera pedidos de dados a outras tarefas, interrompendo periodicamente a computação para esperar pela conclusão de pedidos pendentes.
2. a distribuição da estrutura de dados é encapsulada num segundo conjunto de tarefas responsável por responder, apenas, a pedidos de leitura e escrita, Fig 2.10.
3. se o computador se baseia num modelo de programação de memória partilhada, as tarefas poderão aceder aos dados sem que para isso haja necessidade de qualquer arranjo especial. Há no entanto que assegurar que as operações de escrita e leitura são efectuadas numa sequência conveniente.

Cada estratégia possui as suas próprias vantagens e desvantagens e o rendimento depende ainda da máquina disponível.

• A primeira estratégia pode conduzir a programas emaranhados e não modulares, resultantes de operações de polling dispersas pelo código do programa. Há ainda a considerar os custos associados ao polling, em alguns computadores, que conduzem a uma necessária avaliação da relação de custos entre polling frequentes e a resposta imediata a pedidos remotos.

• A segunda estratégia apesar de mais modular, torna mais difícil explorar a localidade dos dados, porque em sentido estrito não há dados locais. Isto é, qualquer operação de leitura ou escrita exige uma comunicação e a comutação entre computação e comunicação poderá ser muito onerosa em alguns computadores.

Análise da Comunicação

Apresentamos em seguida um lista de perguntas, que deverão normalmente ser respondidas afirmativamente, que não têm como propósito encontrar regras rigorosas e imediatas, mas identificar características não escaláveis.

1. O número de operações realizadas por todas as tarefas é aproximadamente igual? Se assim não for, a comunicação faz prever um programa não escalável devendo procurar-se uma redistribuição das operações que conduza a uma distribuição mais equitativa. Se por exemplo, há acessos com uma frequência muita elevada, a uma estrutura de dados encapsulada numa única tarefa, é de considerar a hipótese de distribuir ou replicar essa estrutura.
2. Cada tarefa comunica apenas com um número diminuto de tarefas vizinhas? Em caso negativo, é de considerar a hipótese de a comunicação global ser formulada em termos de uma estrutura de comunicação local. Tal como foi feito no caso do somatório.
3. Será que as comunicações podem ser realizadas concorrentemente? Se assim não for, o algoritmo dificilmente será eficiente e escalável. Nesta circunstância, será melhor experimentar técnicas de dividir para paralelizar que possam expor a concorrência.
4. Será que as várias computações podem ser realizadas concorrentemente. Em caso negativo, o algoritmo dificilmente será eficiente e escalável. Assim, há que considerar a possibilidade de revisitar a especificação ou encontrar uma nova sequência de comunicações e computações que favoreçam a concorrência.

Agrupamento

Nas duas primeiras etapas de desenho, a computação foi dividida num conjunto de tarefas e foi introduzida a comunicação, como meio de fornecer os dados necessários às tarefas. O algoritmo, assim conseguido, continua a ser abstracto no sentido em que não foi desenhado para a execução eficiente num computador específico. De facto, pode até ser altamente ineficiente se, por exemplo, criar mais tarefas do que processadores disponíveis e o computador não tiver sido projectado para a execução eficiente de um pequeno número de tarefas.

Com o agrupamento pretende-se passar do mundo abstracto para a realidade, revendo as decisões feitas nas fases anteriores, de forma a obter um algoritmo que execute eficientemente numa classe específica de computadores paralelos. Considera-se, em particular, a utilidade de combinar ou agrupar as tarefas, identificadas na fase de partição, num grupo mais pequeno de tarefas de maior tamanho Fig 2.11 e determinar até que ponto vale a pena replicar dados e/ou cálculos.

O número de tarefas que resulta desta fase poderá ser, apesar de pequeno, ainda superior ao número processadores. Neste caso, o algoritmo continua a ser de certa forma abstracto na medida em as questões relativas ao arranjo dos processadores permanece por resolver. A alternativa poderá ser agrupar as tarefas, de forma a conseguir obter um número exactamente igual de tarefas e processadores. Este será o caso, que leva a considerar concluído o desenho do algoritmo, se o computador ou o ambiente de programação exigir um programa SPMD; o arranjo já está resolvido se as $P$ tarefas executam em $P$ processadores.

As decisões relativas ao agrupamento e replicação podem por vezes gerar conflitos se os objectivos são:

• a redução dos custos de comunicação por aumento da granularidade, tanto de computação como de comunicação.
• manter a flexibilidade no que diz respeito quer à escalabilidade quer ao arranjo dos processadores.
• a redução dos custos associados ao desenvolvimento das soluções.

Aumentar a Granularidade

Encontrar, na fase de partição, o maior número possível de tarefas é uma disciplina útil que nos força a considerar uma vasta gama de hipóteses de execução paralela. Convém no entanto notar que a definição de um número elevado de tarefas não conduz necessariamente à obtenção de um algoritmo eficiente.

Um ponto crítico que influencia largamente a eficiência são os custos de comunicação. Em muitos computadores é preciso suspender a computação para permitir enviar e receber mensagens. Como na prática o que importa é a computação o aumento de eficiência pode ser conseguido reduzindo o tempo de comunicação. Obviamente que podem ser obtidos resultados idênticos, transferindo menos dados, ou usando menos mensagens, mesmo mantendo fixo o volume total de dados. Esta última consideração resulta da existência de um custo fixo que não depende apenas do volume total de dados, mas do próprio mecanismo de comunicação. Um outro valor a contabilizar é o custo de criação das tarefas.

Efeitos Superfície-Volume

Se o número de participantes numa comunicação for pequeno, pode reduzir-se tanto o número de operações de comunicação, como aumentar o volume global de comunicações, aumentando a granularidade da partição, isto é, agrupando várias tarefas numa única tarefa. No exemplo, Fig. 2.12, a redução dos custos de comunicação é obtida através do efeito superfície-volume. Os requisitos de comunicação de uma tarefa são proporcionais à superfície do subdomínio em que opera, enquanto que os requisitos de computação são proporcionais ao volume do subdomínio. Num problema bidimensional a superfície é escalável em função do tamanho do problema, enquanto o volume é escalável, no quadrado do tamanho do problema. Assim, o aumento da comunicação por unidade de computação (rácio comunicação/computação) diminui à medida que o tamanho das tarefas aumenta. Este efeito é apenas visível quando a partição é obtida usando técnicas de decomposição em domínios.

Uma consequência do efeito superfície-volume é uma elevada decomposição dimensional que produz, tipicamente, uma elevada eficiência, porque reduz a superfície comunicacional requerida, para um determinado volume de computação. Assim, do ponto de vista da eficiência, é normalmente preferível aumentar a granularidade, agrupando tarefas em todas as dimensões, ao invés de reduzir a dimensão da decomposição. O desenho de uma estratégia de agrupamento eficiente pode ser muito dificultada, em problemas em que a comunicação é não estruturada, o que obriga a usar técnicas especializadas.

Replicação da Comunicação

É possível, por vezes, encontrar um compromisso entre computação replicada, para requisitos reduzidos de comunicação, e/ou o tempo de execução. Podemos usar, como exemplo, uma variante do problema do somatório, em que a soma tem que ser replicada em cada uma das $N$ tarefas que contribuem para o somatório.

Pode ser feita uma abordagem simples à distribuição da soma se se usar em primeiro lugar um algoritmo baseado numa estrutura em anel ou árvore, para calcular a soma numa única tarefa e seguidamente difundir, a soma para cada uma das $N$ tarefas. A difusão pode usar a mesma estrutura de comunicação do somatório; assim, a operação completa pode ser executada em $2(N-1)$ ou $2 \log N$ passos, dependendo da estrutura de comunicação usada.

Estes algoritmos são óptimos na medida em que não é realizada qualquer comunicação ou computação desnecessária. A ideia básica é efectuar múltiplas somas concorrentemente, com cada adição produzindo um valor numa tarefa diferente.

Começaremos por considerar uma variante do algoritmo de soma em fila, em que as tarefas são ligadas em anel e executam o mesmo algoritmo, de forma a que as $N$ somas parciais estejam a ser calculadas simultaneamente.

Depois de $N-1$ passos a soma aparece replicada em todas as tarefas. Esta estratégia evita subsequentes operações de difusão, à custa de $(N-1)^2)$ adições redundantes e $(N-1)^2$ comunicações desnecessárias. Contudo, a soma, tal como a difusão completam-se em $N-1$ passos em vez de $2(N-1)$ passos, o que leva a concluir que esta estratégia é mais eficiente do que se os processadores estivessem à espera dos resultados da soma.

O algoritmo da soma em árvore pode ser modificado, de forma idêntica, para evitar difusões em separado. Neste caso, múltiplas somas na árvore são executadas concorrentemente e que depois de $\log N$ passos, cada tarefa tenha uma cópia da soma. O resultado será, tal como no caso do algoritmo em anel, adições e comunicações de $O(N)$. Contudo, neste caso, a redundância, tanto em computação como em comunicação, pode ser explorada para executar a soma em apenas $O(N \log N)$ operações. A estrutura de comunicações resultante, borboleta fig. 2.14, mostra que em cada um dos $\log N$ passos, cada tarefa recebe dados de duas tarefas, executa apenas uma adição e envia o resultado dessa adição para duas tarefas, no passo seguinte.

Evitando a Comunicação

O agrupamento é quase sempre benéfico se a análise dos requisitos de comunicação revelar que um determinado conjunto de tarefas não pode ser executado concorrentemente. Consideremos, por exemplo, as estruturas em árvore das figs. 2.8 e 2.14. Sempre que uma adição simples é efectuada, apenas as tarefas ao mesmo nível, numa dessas estruturas, pode ser executada concorrentemente. Convém no entanto notar que se houver muitas adições a efectuar, então, em princípio, todas as tarefas podem ser mantidas em actividade, canalizando múltiplas operações de soma. Assim, as tarefas nos diferentes níveis podem ser agrupadas, sem que se reduzam as oportunidades para a execução concorrente, o que produz a estrutura de comunicações na fig. 2.15 O hiper-cubo, nesta figura, é uma estrutura de comunicações fundamental usada em muitas aplicações da computação paralela.

Preservação da Flexibilidade

Quando se agrupam tarefas é fácil tomar decisões que limitam desnecessariamente a escalabilidade dos algoritmos. Podemos tomar, por exemplo, a decisão de decompôr uma estrutura de dados multidimensional, numa única dimensão, com a justificação de que essa opção garante concorrência, mais do que a necessária, para o número de processadores disponíveis. Contudo, esta estratégia é de vistas curtas, se em última análise, o programa for para levar para um computador paralelo maior, podendo ainda conduzir a um algoritmo menos eficiente.

A habilidade para criar um número variável de tarefas é um ponto crítico, se se pretender que um programa possa ser escalável e transportável. Um bom algoritmo paralelo deverá ser adaptável à alteração do número de processadores. Esta flexibilidade pode ser também de grande utilidade quando se pretende afinar o código para um computador específico. Se as tarefas bloqueiam frequentemente, à espera de dados remotos, pode ser vantajoso arranjar várias tarefas num único processador. Assim, uma tarefa bloqueada não quer dizer um processador ocioso, uma vez que uma outra tarefa poderá estar pronto para ser actividade, no seu lugar. Esta técnica é vulgarmente chamada de sobreposição da comunicação com a comunicação.

Um terceiro benefício, da criação de mais tarefas do que processadores disponíveis, é que, desta maneira, se aumenta a gama de estratégias de arranjo que permitem o balanceamento da carga computacional pelos vários processadores disponíveis. Pode dizer-se, como regra de mão, que o número de tarefas deverá exceder, numa ordem de grandeza, o número de processadores.

O número óptimo de tarefas é, tipicamente, determinado pela combinação da modelação analítica com o estudo empírico. A flexibilidade não pressupõe necessariamente a criação de um elevado número de tarefas, porque a granularidade pode ser controlada durante a compilação ou através de um parâmetro de evocação do programa. O que é verdadeiramente importante no desenho de um algoritmo é não limitar, desnecessariamente, o número de tarefas que podem ser criadas.

Redução dos Custos de Desenho

Temos vindo a assumir, até agora, que a escolha de uma estratégia de agrupamento é determinada, exclusivamente, pelo desejo de melhorar a eficiência e a flexibilidade dos algoritmos paralelos. Uma preocupação adicional, que pode ser particularmente importante quando se pretende paralelizar código sequencial já existente, são os custos relativos de desenvolvimento, associados às diferentes estratégias de partição.

Teste de Agrupamento

Na fase de agrupamento, as decisões de partição e comunicação, foram reconsideradas, o que teve como efeito o agrupamento das tarefas e das operações de comunicação. O agrupamento de tarefas pode decorrer de uma análise dos requisitos de comunicação que mostre que as tarefas não poderiam executar concorrentemente. Uma outra hipótese de agrupamento decorre da necessidade de aumentar a granularidade da computação e da comunicação e/ou diminuir os custos desenho, mesmo se isso conduzir a uma diminuição da oportunidade de concorrência. Com as perguntas que se seguem pretende-se avaliar a situação actual de desenho.

1. O agrupamento reduziu os custos de comunicação, por aumento da localidade? Em caso negativo, o algoritmo deverá ser reexaminado, para verificar até que ponto é possível utilizar uma estratégia de agrupamento alternativa que conduza a esse objectivo
2. Caso o agrupamento tenha produzido replicação de computação, convém verificar se os benefícios da replicação ultrapassam os custos, para uma gama significativa de dimensões do problema e número de processadores.
3. Em caso de replicação de dados, é preciso verificar que a escalabilidade do problema não fica comprometida pelo algoritmo, por restrição da gama de dimensões do problema, ou do número de processadores em que pode correr.
4. O agrupamento produziu tarefas com custos equitativos de comunicação e de cálculo? Quanto maiores forem as tarefas criadas pelo agrupamento, tanto mais é importante que lhes estejam associadas custos idênticos, isto é ainda mais verdadeiro para o caso em que o número de tarefas iguala o número de processadores.
5. O número de tarefas é proporcional ao tamanho do problema? Em caso negativo o algoritmo não poderá ser usado para resolver grandes problemas, em grandes computadores paralelos.
6. No caso do agrupamento ter diminuído as oportunidades para a execução paralela, será que se garantiu suficiente concorrência, para os computadores futuros e para os actuais? Um algoritmo com concorrência limitada poderá continuar a ser o mais eficiente. Se os algoritmos alternativos tiverem custos excessivos de comunicação; modelos de teste de eficiência deverão avaliar o compromisso.
7. Será possível diminuir o número de tarefas, sem que se introduzam problemas de balanceamento de carga, se aumente o custo de desenvolvimento, ou se reduza a escalabilidade? Em caso afirmativo convirá recordar que os algoritmos que criam um número pequeno de tarefas gordas são muitas vezes mais simples e mais eficientes do que os que geram muitas tarefas finas.
8. No caso de se estar a paralelizar um algoritmo sequencial, já existente, foram considerados os custos de modificação do código? Se os custos forem elevados, há que considerar algoritmos alternativos que aumentem as oportunidades de reutilização de código. Se o algoritmo obtido for menos eficiente, devem usar-se modelos de teste de eficiência para estimar os custos.

Arranjo

No quarta e última das fases do processo de desenho de um algoritmo paralelo especifica-se onde deverão ser executadas as tarefas. O arranjo de processadores não é necessário em máquinas uni-processador ou em computadores de memória partilhada que dispõem de escalonamento automático. Nestes computadores, a definição das tarefas e dos requisitos de comunicação associados é uma especificação suficiente para o algoritmo paralelo; neste caso, pode confiar-se no sistema operativo ou nos mecanismos de hardware para escalonar as tarefas nos processadores disponíveis. Infelizmente, não existem mecanismos automáticos de arranjo, já desenvolvidos, para computadores paralelos escaláveis. Em geral, o processo de arranjo é um problema de grande dificuldade que tem de ser especialmente pensado quando se desenham algoritmos paralelos que procuram minimizar o tempo total de execução. Para atingir esse objectivo podem usar-se as seguintes estratégias:

1. As tarefas que são passíveis de ser executadas concorrentemente, são atribuídas a diferentes processadores, para aumentar a concorrência.
2. As tarefas que estão frequentemente a comunicar são alocadas no mesmo processador, para aumentar a localidade.

Estas duas estratégias geram frequentemente conflitos, pelo que se torna necessário estimar os respectivos custos de aplicação. Para além disso, a limitação de recursos pode restringir o número de tarefas que podem ser alocadas a um único processador.

O problema do arranjo é conhecido como $NP$-completo, querendo com isto dizer, não existe nenhum algoritmo que, em tempo polinomial, possa concluir qual o melhor arranjo possível. Contudo, existem actualmente, para um determinada classe de problemas, um considerável conhecimento de técnicas especializadas e heurísticas efectivas.

Muitos algoritmos desenvolvidos a partir de técnicas de decomposição em domínios exibem um número fixo e do mesmo tamanho, de tarefas e de comunicações estruturadas, locais e globais. Nestes casos, é imediata a obtenção de um arranjo eficiente que corresponda à minimização da comunicação entre processadores fig. 2.16; pode também escolher-se, agrupar tarefas alocadas ao mesmo processador, até atingir um total de tarefas $P$ de médio grão, por cada processador.

Em algoritmos mais complexos, de decomposição em domínios, com quantidades variadas de trabalho por tarefa e/ou padrões de estruturas de comunicação não estruturada, poderão ter de se empregar, normalmente com base em heurísticas, técnicas de balanceamento de carga que procurem identificar agrupamentos eficientes e estratégias de arranjo.

O tempo necessário para executar estes algoritmos deverá ser contabilizado face aos benefícios da redução do tempo de execução. Balanceamento de carga probabilísticos tenderão a causar menos sobrecarga do que os métodos que exploram a estrutura da aplicação. Os problemas mais complexos são aqueles em que tanto o número de tarefas como a grandeza da computação e/ou da comunicação variam dinamicamente durante a execução de um programa. No caso de desenvolvimentos que se baseiam em técnicas de decomposição em domínios, podem usar-se estratégias de balanceamento de carga dinâmico que se baseiam num algoritmo de balanceamento de carga, executado periodicamente, para determinar um novo agrupamento e um novo arranjo. Porque o balanceamento de carga tem de ser executado muitas vezes, durante o tempo de vida de um programa, podem ser preferíveis algoritmos locais que não dependam de um conhecimento global do estado actual do programa.

Os algoritmos que se baseiam em técnicas de decomposição em funções produzem, frequentemente, muitas tarefas pequenas e de curta duração que sincronizam com outras tarefas apenas no inicio e no fim da sua actividade. Neste caso, podem usar-se algoritmos de escalonamento de tarefas que irão atribuir as tarefas aos processadores que estão ociosos ou que estão em vias de se tornar ociosos.

Algoritmos de Balanceamento de Carga

Têm vindo a ser propostas grandes variedades de técnicas de balanceamento de carga, tanto de uso genérico como de uso específico, para serem usadas em algoritmos paralelos que se baseiam na decomposição em domínios. Todas estas técnicas procuram agrupar tarefas finas, definidas numa partição, para promover tarefas de tamanho médio em cada processador. Em alternativa, pode pensar-se nesses técnicas como se pretendessem dividir o domínio de computação para atribuir um subdomínio a cada processador, razão pela qual são muitas vezes designados algoritmos de partição.

Bissecção Recursiva

Esta técnica é usada para dividir um domínio (p.e uma matriz finita de elementos) em subdomínios com custos de computação aproximadamente iguais, ao mesmo tempo, que se tentam diminuir os custos de comunicação, diminuindo o número de canais que cruzam os limites das tarefas. Uma abordagem do tipo dividir para paralelizar é usada para dividir em primeiro lugar o domínio ao longo de uma dimensão produzindo dois subdomínios. Divisões recursivas em novos subdomínios são, então, produzidas até obter tantos subdomínios quantas as tarefas desejadas. Convém notar que, esta estratégia recursiva deverá ser aplicada de tal forma que permita que o próprio algoritmo de partição possa ser executado em paralelo.

A mais imediata das técnicas de bissecção, a bissecção coordenada recursiva, é aplicada, normalmente, a matrizes irregulares que têm sobretudo uma estrutura de comunicação local. Esta técnica estabelece as divisões com base nas coordenadas físicas dos pontos no domínio da matriz. Em cada passo a divisão é feita ao longo da maior das dimensões, p.e. a divisão é feita ao longo do eixo dos $X$, pelo que, os pontos num subdomínio terão a ordenada $x$ maior que os pontos nos outros subdomínios.

Esta abordagem tem a vantagem de ser simples e económica conduzindo a bons resultados de divisão computacional. Uma desvantagem é que não optimiza a eficiência das comunicações. Em particular, pode gerar subdomínio poucos densos, o que, no caso de algoritmo prever um número significativo de comunicações locais resultará em mais mensagens das que seriam produzidas por uma decomposição que gerasse subdomínios quadrados.

Uma variante desta técnica, a bissecção recursiva não balanceada, promove a redução dos custos de comunicação formando submatrizes com melhores rácios. Em vez de dividir mecanicamente uma matriz em duas, começa por considerar as $P-1$ partições obtidas formando submatrizess não-balanceadas com $1/P$ e $(P-1)/ P$ da carga, com $2 / P$ e $(P-2)/ P$ da carga e assim sucessivamente, escolhendo a partição que minimiza o rácio de partições. Este método aumenta os custos de cálculo da partição mas pode reduzir os custos de comunicação.

Uma outra técnica, designada por bissecção por grafo recursivo, pode ser de grande utilidade em estruturas complexas de matrizes não estruturadas, como é o caso de uma rede de elementos finitos. Esta técnica usa informação sobre a conectividade, para reduzir o número de lados da matriz que cruzam limites de subdomínio, reduzindo desta forma os requisitos de comunicação. Uma matriz é tratada como um grafo de $N$ vértices (pontos da matriz) $v_i$. O algoritmo começa por identificar as duas extremidades do grafo, i.e., os dois vértices que estão mais distantes em termos da distância no grafo. Seguidamente, cada vértice é entregue ao subdomínio correspondente à extremidade mais perto. Em muitas circunstâncias, um outro algoritmo, chamado bissecção recursiva espectral, é, em muitas circunstâncias, ainda melhor.

Algoritmos Locais

As técnicas que acabamos de descrever são relativamente pouco económicas porque requerem um conhecimento global do estado da computação. Em contraste, os algoritmos de balanceamento locais compensam as modificações na carga computacional usando apenas a informação obtida de um pequeno número de processadores vizinhos. Por exemplo, os processadores podem estar organizados numa trama lógica; periodicamente, cada processador compara a sua carga computacional com a carga dos seus vizinhos na trama e transfere a computação, se a diferença em carga exceder um determinado limiar. A fig 2.17 mostrar a distribuição de carga produzida por um desses esquemas.

Porque são económicos, os algoritmos locais podem ser de grande utilidade em situações em que a carga varia constantemente. Contudo, são tipicamente menos bons, no balanceamento de carga, que os algoritmos globais e, em particular, podem ser lentos, no ajuste a grandes alterações nas características da carga. Por exemplo, se aparecer um valor elevado de carga num processador, são necessários múltiplas operações de balanceamento de carga local, antes que a carga seja difundida pelos outros processadores.

Métodos Probabilísticos

Uma abordagem particular do balanceamento de carga é a alocação aleatória de processadores. Se o número de processadores for grande, cada processador tomará conta de um valor aproximadamente igual de computação. As vantagens desta estratégia são o baixo custo e a escalabilidade. As desvantagens são os requisitos de comunicação terem de ser, virtualmente para todas tarefa, feitos com os processadores desligados e uma distribuição de carga aceitável só se atinge quando há mais tarefas que processadores. Esta estratégia tende a ser efectiva quando há relativamente pouca comunicação entre tarefas e/ou baixa localidade na comunicação. Nos outros casos, os métodos probabilísticos têm tendência para produzir mais comunicação do que as outras técnicas.

Arranjo Cíclico

Se se souber que a carga computacional varia, em cada ponto da matriz e que há uma localidade espacial suficiente nos níveis de carga, então, pode ser apropriado um arranjo cíclico ou disperso, como é às vezes chamado, de tarefas por processadores. Esta técnica é uma forma de arranjo probabilístico, em que cada um do $P$ processadores é alocado a cada uma das $P$ tarefas, de acordo com uma determinada numeração das tarefas, fig 2.18. O objectivo é, em termos médios, que alocar a cada processador uma carga computacional aproximadamente igual. Os benefícios de um balanceamento melhorado da carga podem necessitar de ser avaliados, em termos do aumento dos custos de comunicação resultantes da redução da localidade. São também possíveis distribuição cíclicas em bloco, em que blocos de tarefas são entregues aos processadores.

Algoritmos de Escalonamento de Tarefas

Estes algoritmos podem ser usados sempre que a decomposição funcional produz muitas tarefas, cada uma quais tem fracos requisitos de localidade. É mantido um lote centralizado ou distribuído de tarefas, onde são colocadas novas tarefas e retiradas outras, para alocar aos processadores. De facto, o algoritmo paralelo é reformulado transformando, o que foi originalmente concebido como uma tarefa, em estruturas de dados. Estas estruturas, representam ``problemas'', a serem resolvidos por tarefas, trabalhadoras,tipicamente entregues cada uma ao seu processador.

O aspecto mais crítico e complicado do algoritmo de escalonamento é a estratégia usada para entregar os problemas às tarefas trabalhadoras. Em geral, a estratégia escolhida representa um compromisso entre os conflitos gerados pela necessidade de operações independentes (para reduzir os custos de comunicação) e o conhecimento global do estado da computação (para melhorar o balanceamento de carga).

Gerente/Trabalhador

A fig. 2.19 ilustra um esquema simples de escalonamento, efectivo para um número moderado de processadores. Nesta estratégia, um tarefa gerente central tem a responsabilidade do problema da alocação. Os trabalhadores efectuam pedidos repetidos ao gerente enquanto executam um problema, ou enviam novas tarefas ao gerente, para alocação de novos trabalhadores. A eficiência desta estratégia depende do número de trabalhadores e dos custos relativos de obtenção e execução de problemas. A eficiência pode ser melhorada utilizando técnicas de pré-busca de problemas, de forma a sobrepôr computação com comunicação. Podem também ser usadas técnicas de cache guardando problemas nos trabalhadores, de forma a que, a comunicação entre gerente e trabalhadores ocorra, apenas, quando não houver problemas para resolver localmente.

Hierarquia Gerente/Trabalhador

Uma variante da técnica anterior consiste em dividir os trabalhadores em conjuntos disjuntos, cada um dos quais com o seu próprio subgerente. Os trabalhadores requerem as tarefas aos subgerentes que comunicam periodicamente com o gerente principal e os outros subgerentes, de forma a balancear a carga entre os conjuntos de processadores pelos quais são responsáveis.

Esquemas Descentralizados

Nos esquemas completamente descentralizados não gerente há principal, em vez disso, cada processador mantém um lote separado de tarefas e os trabalhadores ociosos pedem problemas a outros processadores. De facto, o lote de tarefas transforma-se numa estrutura distribuída de dados acedida pelas diferentes tarefas, de modo assíncrono.

Existe uma grande variedade de políticas de acesso. Por exemplo, um trabalhador pode pedir trabalho de um pequeno número, pré-definido, de vizinhos ou pode seleccionar, ao acaso, outros processadores. Num esquema híbrido centralizado/distribuído, os pedidos são enviados ao gerente principal que os distribui pelos trabalhadores de modo circular. Notar que, apesar de o gerente gerar um engarrafamento se houver um grande número de processadores, terá, de qualquer forma, acessos menos frequentes do que no caso escalonamento gerente/trabalhador, sendo, por isso, um construtor mais escalável.

Tal como já foi anteriormente referido, o acesso a uma estrutura de dados distribuída, tal como os lotes de tarefas no esquema de balanceamento de carga descentralizado, pode ser obtido de muitas formas diferentes. Os trabalhadores podem ser responsáveis tanto pela computação como pela comunicação, ao mesmo tempo, que gerem a fila de problemas. Neste caso, cada trabalhador deve inquirir a existência de pedidos pendentes. Alternativamente, as responsabilidade de computação e de gestão deverão estar embebidas em tarefas separadas.

Detecção de Terminação

Os algoritmos de escalonamento de tarefas têm de ter mecanismos para determinar quando se conclui a busca; caso contrário, os trabalhadores ociosos nunca acabarão de pedir trabalho aos outros trabalhadores. A operação de detecção de terminação é linear nos esquemas centralizados, porque o gerente pode determinar facilmente quando é que todos os trabalhadores estão ociosos. Nos esquemas descentralizados a operação é mais difícil, não só, porque não existe um registo central dos trabalhadores ociosos, mas também, porque as mensagens em trânsito podem conter tarefas, mesmo quando todos os trabalhadores parecem estar ocioso.

Teste de Arranjo

Com a discussão anterior damos por terminado o desenho de um algoritmo paralelo. As decisões de arranjo procuraram balancear os conflitos, entre a necessidade de distribuição de carga equitativa e os baixos custos de comunicação. Sempre que for possível dever-se-á usar um arranjo estático que aloque cada tarefas a um único processador. Contudo, quando o número ou tamanho da tarefa é variável ou desconhecido, no início da execução podem usar-se esquemas de balanceamento dinâmico de carga ou reformular o problema, de forma a que possa ser usada uma estrutura de escalonamento de tarefas, para escalonar a computação. A validação informal do arranjo pode ser obtida a partir das seguintes questões:

1. Em face de um desenho SPMD para um problema complexo, teve em consideração um algoritmo baseado na criação e destruição dinâmica de tarefas? Em caso afirmativo, esta consideração pode conduzir a um algoritmo mais simples, no entanto, é necessário ter em conta os problemas da eficiência.
2. Em face de um desenho baseado na criação e destruição dinâmica de tarefas, teve em consideração um algoritmo SPMD? Em caso afirmativo, esta consideração permite um maior controlo sobre o escalonamento da computação e da comunicação, mas pode ser bem mais complexo.
3. Quando usa um esquema centralizado de balanceamento de carga, verificou se a tarefa gerente não se transformou num ponto de engarrafamento? Neste caso, talvez seja possível reduzir os custos de comunicação se, em vez de passarem as tarefas para o gerente se passarem, apenas, os apontadores para as tarefas.
4. Quando usa um esquema de balanceamento dinâmico, fez a avaliação relativa dos custos das diferentes estratégias? Assim sendo, não esquecer de incluir na análise os custos de realização. Esquemas probabilísticos ou de arranjo cíclicos são simples devendo ser sempre considerados, porque podem evitar a necessidade de operações repetidas de balanceamento de carga.
5. Quando usa métodos probabilísticos ou cíclicos, será que há um número suficientemente grande de tarefas que asseguram um balanceamento de carga razoável? Tipicamente, são necessários pelo menos dez vezes mais tarefas que processadores.

Análise Quantitativa do Desenho

Na programação paralela, como noutra qualquer disciplina de engenharia, o objectivo do desenho não é optimizar apenas uma medida tal como o ganho. Pelo contrário, um bom desenho deverá optimizar uma função de custo específica do problema: tempo de execução, requisitos de memória, custos de realização, custos de manutenção, etc. Esta optimização do desenho envolve compromissos entre simplicidade, rendimento, portabilidade e outros factores.

Tomar decisões fundamentadas de desenho a partir de hipóteses alternativas requer a compreensão dos custos envolvidos. Neste capítulo, mostramos de que maneira este conhecimento pode ser desenvolvido e formalizado em modelos de rendimento matemáticos. Estes modelos podem ser usados para comparar a eficiência de diferentes algoritmos, para avaliar a escalabilidade e para identificar congestionamentos e outras ineficiências, tudo isto, antes que investamos um esforço substancial na implementação. Os modelos de rendimento podem também ser usados para orientar os esforços de implementação mostrando onde se deve proceder a optimizações.

Depois de estudar este capítulo, o leitor deverá saber como desenvolver modelos de rendimento para algoritmos paralelos e ser capaz de usar estes modelos para avaliar a escalabilidade e escolher entre algoritmos alternativos. Deverá ainda saber como obter dados empíricos fiáveis e como usar estes dados para validar os modelos e as suas implementações. E, ainda, compreender como é que a topologia da rede pode afectar o rendimento dos modelos de comunicação e saber como entrar em consideração com esses efeitos nos modelos. Finalmente, deverá ser capaz de reconhecer e contabilizar outros factores, para além do rendimento, factores tais como os custos de implementação que influenciam as escolhas de desenho.

Definição de rendimento

A tarefa do engenheiro de software é desenhar e realizar programas que satisfaçam os requisitos de correcção e de rendimento do utilizador. Contudo, o ``rendimento'' de um programa paralelo é um tema complexo e multi-facetado. Necessitamos de considerar, para além do tempo de execução e da escalabilidade dos núcleos de computação, os mecanismos através dos quais os dados são gerados, armazenados, transmitidos através das redes, movidos de e para os discos, e passados entre diferentes estágios de uma computação. Devemos considerar os custos que incorrem em diferentes fases do ciclo de desenho, incluindo o desenho, a implementação, a execução, e a manutenção. Assim, as métricas através das quais medimos o rendimento podem ser tão diversas como o tempo de execução, a eficiência paralela, os requisitos de memória, o tempo de execução^3.1, o desempenho^3.2, os atrasos, as taxas de entrada/saída, o desempenho da rede, os custos de desenho, os custos de realização, os custos de verificação, o potencial de reutilização, os requisitos de equipamento, os custos do equipamento, os custos de manutenção, a portabilidade e a escalabilidade.

A importância relativa das diversas métricas irá variar conforme a natureza do problema em mãos. Uma especificação pode fornecer números rigorosos para algumas métricas, impor a optimização de outras, ou até ignorá-las. Por exemplo, a especificação de desenho de um sistema operacional de previsão de clima pode estabelecer o tempo de execução máximo (``a previsão deverá estar completada em 4 horas''), os custos do equipamento e os custos de realização e requerer que a fiabilidade do modelo seja maximizada dentro desses limites. Cumulativamente, a fiabilidade é de importância particularmente elevada, tal como pode ser a escalabilidade para futuras gerações de computadores.

Em contraste, um grupo de engenheiros que estão a desenvolver um programa de pesquisa numa base de dados, para o seu próprio uso ocasional, podem ficar satisfeitos com qualquer coisa que corra mais depressa do que um programas sequencial já existente, mas podem ficar extremamente constrangidos pelo tempo que é necessário gastar na sua implementação. Aqui, a escalabilidade é menos crítica, mas o código deverá adaptar-se facilmente às alterações tanto do sistema de bases de dados, como das tecnologias dos computadores.

Como um terceiro exemplo, consideremos uma cadeia de processamento de imagens consistindo de vários estágios concorrentes, cada um executando uma transformação diferente numa sequência de imagens. Aqui, devemos estar preocupados não com o tempo total requerido para processar um certo número de imagens mas, em vez disso, com o número de imagens que podem ser processadas por segundo (desempenho), ou com o tempo que uma simples imagem demora a passar através da cadeia (tempo de execução). O desempenho seria importante numa aplicação de compressão de imagens vídeo, enquanto que o atraso seria importante se o programa fizesse parte de um sistema de detecção que tem que reagir, em tempo real, aos eventos detectados numa série de imagens.

Noutras situações, o rácio tempo de execução custo do sistema pode ser importante. Por exemplo, consideremos um banco que gasta todas as noites duas horas do tempo do seu sobrecarregado computador central para correr um programa de análise à procura de transações fraudulentas. Uma versão que corra em seis horas num computador paralelo que custa um vigésimo do preço, pode constituir uma solução bem mais interessante mesmo que o tempo de execução total seja superior.

Grande parte do material do resto do capítulo está relacionado com a modelação e a medição de apenas dois aspectos do rendimento de algoritmos: o tempo de execução e a escalabilidade paralela. Enfatizamos estes tópicos porque estes estão frequentemente entre os aspectos mais problemáticos do desenho de programas paralelos e porque estes são mais facilmente formalizáveis em modelos matemáticos. Contudo, estes tópicos devem ser examinados no contexto de um processo de desenho mais abrangente que também contemple os restantes temas listados nesta secção.

Abordagens à Modelação de Rendimento

Introduzimos o tópico de modelação de rendimento através da descrição de três técnicas usadas, algumas vezes, para caracterizar o rendimento de algoritmos paralelos. Explicamos porque razão cada uma delas é inadequada para os nossos propósitos.

Lei de Amdahl

Uma observação comum a propósito do processamento paralelo é que todo o algoritmo paralelo tem uma componente sequencial que limita, eventualmente, o ganho que pode ser conseguido por um computador paralelo. (O ganho, tal como em breve definiremos mais formalmente, é a razão entre o tempo de execução num único processador e o tempo de execução em múltiplos processadores.) Esta observação é muitas vezes codificada como a lei de Amdahl que pode ser expressa como se segue: se a componente sequencial de um algoritmo gasta $1/s$ do tempo de execução do programa, então, o ganho máximo que pode ser alcançado num computador paralelo é $s$. Por exemplo, se a componente sequencial é de 5 por cento , então o máximo ganho que pode ser alcançado é $20$.

Nos primórdios da computação paralela acreditava-se que este efeito limitaria a utilidade da computação paralela a um pequeno número de aplicações especializadas. Contudo, a experiência prática demonstra que esta maneira inerentemente sequencial de pensar é de pequena relevância em problemas reais. Para compreender porquê, consideremos um problema não computacional.

Se assumirmos que $999$ dos $1000$ trabalhadores de um projecto de construção de uma auto-estrada estão sem fazer nada, enquanto um único trabalhador completa uma ``componente sequencial'' do projecto. Não iremos ver isto como uma propriedade intrínseca do problema a ser resolvido, mas a uma falha de gestão. Por exemplo, se o tempo necessário a um camião para despejar betão num único ponto provoca congestionamento, podemos sempre argumentar que a estrada deveria estar a ser construída em vários pontos, simultaneamente. Fazendo isto, introduz-se sem margem para dúvidas alguma ineficiência - por exemplo, alguns camiões teriam de viajar mais longe para chegar ao seu local de trabalho -- mas iria permitir que a empreitada no seu conjunto terminasse mais rapidamente. Da mesma forma, parece que quase todos os problemas computacionais admitem soluções paralelas. A escalabilidade de algumas da soluções pode estar limitada mas, isto é devido aos custos de comunicação, aos tempos de espera, ou à replicação da computação, mais do que à existência de `` componentes sequenciais''.

A lei de Amdhal pode ser relevante quando os programas sequenciais são paralelizados incrementalmente. Nesta abordagem ao desenvolvimento de programas paralelos, um programa sequencial é inicialmente analisado para identificar os componentes com requisitos computacionais. Esses componentes são depois adaptados para execução paralela, um após outro, até se atingir uma rendimento aceitável. A lei de Amdahl aplica-se claramente nesta situação, porque os custos da computação dos componentes que não são paralelizáveis determinam o limite inferior do tempo de execução do programa paralelo. Por isso, esta estratégia de paralelização, ``parcial'' ou ``incremental'', é geralmente efectiva apenas em pequenos computadores paralelos. A lei de Amdahl pode, também, ser útil quando se analisa o rendimento de programas com paralelismos nos dados, em que alguns componentes podem não ser adaptáveis a uma formulação de paralelismo nos dados (ver capítulo 7).

Observar para Extrapolar

As descrições de algoritmos paralelos caracterizam muitas vezes o rendimento afirmando qualquer coisa como o que segue: implementámos o algoritmo no computador paralelo $X$ e atingimos um ganho de $10,8$ em $12$ processadores para um problema de tamanho $N=10$.

Presumivelmente, este ponto único de dados, num pequeno número de processadores, pretende ser uma medida da qualidade do algoritmo. Um ganho de $10,8$ em $12$ processadores pode ser, ou não ser, entendido como sendo ``bom''. Contudo, uma única medição de rendimento (ou mesmo várias medições) serve apenas para determinar o rendimento numa região estreita do que é um vasto espaço multi-dimensional e é, muitas vezes, um indicador pobre de rendimento noutras situações. O que acontece com $1000$ processadores? E se $N=10$ ou $N = 1000$? E se os custos de comunicação forem dez vezes superiores? Responder a estas questões obriga a uma compreensão mais profunda do algoritmo paralelo.

As três equações que se seguem põem a enfâse nas limitações da observação como um instrumento para a compreensão do rendimento paralelo. Cada uma é um modelo de rendimento simples que especifica o tempo de execução $T$ como uma função do número de processadores $P$ e do tamanho do problema $N$. Em cada um dos casos, assumimos que o tempo total de computação executado por um algoritmo sequencial optimizado aumenta com $N+N^2$.

1. $T=N+N^2/P$. Este algoritmo divide os requisitos de computação em ${\cal O}(N^2)$ componentes do algoritmo mas replica os ${\cal O}(N)$ componentes em cada processador. Não há outras fontes de sobrecarga.
2. $T= (N+N^2)/ P + 100$. Este algoritmo divide toda a computação mas introduz um custo adicional de $100$.
3. $T=(N+N^2)/P + 0.62P^2$. Este algoritmo também divide toda a computação mas introduz um custo adicional de $0.62P^2.$

Todos estes algoritmos atingem ganhos de cerca $10.8$ quando $P=12$ e $N = 100$. Contudo, estes comportam-se diferentemente em outras situações, como é ilustrado na figura 3.1. Com $N = 100$, os três algoritmos executam pobremente para valores grandes de $P$, apesar do algoritmo(3) ser significativamente pior que os outros dois. Quando $N = 1000$, o algoritmo (2) é significativamente superior ao algoritmo (1) para valores grandes de $P$.

Figura: 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.

Análise Assimptótica

Os livros caracterizam frequentemente o rendimento de um algoritmo paralelo através de afirmações como a que segue:
A análise assimptótica revela que o algoritmo requere um tempo de ${\cal O}(N \log N)$ em ${\cal O}(N)$ processadores.

Isto é, existe um valor constante $c$ e um tamanho mínimo $N_0$, tal que, para todo o $N > N_0$, o $custo(N) \leq c N \log N$, em $N$ processadores. Esta relação mostra de que forma o custo varia com $N$ quando $N$ e $P$ são grandes.

Apesar desta informação ser interessante, é muitas vezes não directamente relevante para a tarefa de desenvolver um programa paralelo eficiente. Porque diz respeito a valores elevados de $N$ e $P$, ignora os termos de baixa ordem que podem ser significativos para dimensões de problemas e números de processadores com interesse prático. Por exemplo, o custo efectivo de um algoritmo com complexidade assimptótica $N \log N$ pode ser $10N + N \log N$. O componente $10N$ é maior para $N<1024$ e deverá ser incorporado no modelo de rendimento se existirem problemas interessantes, neste regime. Uma segunda deficiência da análise assimptótica é que nada é dito sobre os custos absolutos. A análise assimptótica sugeriria que um algoritmo com custo $1000N \log N$ é superior a um algoritmo com custo $10N^2$. Contudo, este último é mais rápido para $N<996$ que de novo pode ser o regime de interesse prático. Uma terceira deficiência é que estas análises assumem frequentemente modelos idealizados de máquinas que são muito diferentes dos computadores físicos para os quais desenvolvemos programas. Por exemplo, aqueles podem assumir o modelo PRAM^3.3 , no qual os custos de comunicação são considerados nulos.

A análise assimptótica tem um papel a desempenhar no desenho de programas. Contudo, quando se avaliam os resultados assimptóticos, devemos identificar cuidadosamente o modelo de máquina para os quais os resultados são obtidos, os coeficientes apropriados para aplicar, e o regime para o qual os valores de $N$ e $P$ se verificam.

Desenvolvimento de Modelos

Um bom modelo de rendimento, tal como uma boa teoria científica, pode explicar as observações realizadas e prever as circunstâncias futuras, ao mesmo tempo que põe de parte detalhes pouco importantes. A lei de Amdahl, as observações empíricas e a análise assimptótica não satisfazem o primeiro daqueles requisitos. Por outro lado, as técnicas de modelação de sistemas em computadores convencionais que envolvem, tipicamente, simulações detalhadas dos componentes individuais do equipamento introduzem demasiados pormenores para serem de utilidade prática aos programadores de paralelismo. No resto deste capítulo, apresentamos técnicas de modelação de rendimento que fornecem um nível intermédio de detalhe. Estas técnicas não são certamente adequadas para todos os propósitos: estas são especializadas para a arquitectura do multi-computador e não tomam em consideração, por exemplo, o comportamento da cache. Contudo, estas técnicas têm vindo a provar a sua utilidade no desenho de um largo espectro de algoritmos paralelos. O capítulo não apresenta referências a outras abordagens.

Os modelos de rendimento considerados aqui especificam uma métrica, tal como o tempo de execução, $T$, como uma função do tamanho do problema $N$, do número de processadores $P$, do número de tarefas $U$ e outras características algorítmicas e físicas.

$$T=f(N,P,U,...).$$

Definimos o tempo de execução de uma programa paralelo como o tempo que decorre desde que o primeiro processador inicia a execução do problema, até que o último processador completa a execução. Esta definição não é inteiramente apropriada para um computador paralelo em tempo partilhado mas é suficiente para os nossos propósitos. Durante a execução, cada processador $i$ está em computação, em comunicação, ou ocioso, tal como é ilustrado pela figura 3.2. $T^i_{comp}$, $T^i_{com}$ e $T^i_{\acute ocio}$, são os tempos gastos a computar, a comunicar e em ócio, respectivamente. Assim, o tempo total de execução $T$ pode ser definido de duas formas: como a soma dos tempo de computação, da comunicação e de ócio de um processador $j$ arbritário

$$T=T^j_{comp} +T^j_{com} +T^j_{\acute ocio}.$$

ou como a soma desses termos em todos os processadores dividida pelo número de processadores $P$.

$$\begin{eqnarray*} T &= &\frac{1} {P} (T_{comp} + T_{com} + T_{\acute ocio}) \\ ... ...-1}_{i=0} Tî_{com} + \sum ^{P-1}_{i=0} Tî_{\acute ocio} \right). \end{eqnarray*}$$

Figura: 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.

Esta última definição é muitas vezes mais útil, uma vez que, é tipicamente mais fácil determinar a computação e a comunicação totais, efectuada por um algoritmo paralelo, do que o tempo gasto em computação e comunicação em processadores individuais.

Assim, o objectivo é desenvolver expressões matemáticas que especificam o tempo de execução como uma função de $N$, de $P$, etc. Estes modelos deverão ser tão simples quanto possível, sem deixarem de ter uma precisão aceitável. Usamos as seguintes técnicas para reduzir a complexidade dos modelos:

• Baseamos os nossos modelos na arquitectura idealizada do multi-computador introduzido no capítulo 1. Os detalhes físicos de baixo nível, tais como, as hierarquias de memória e a topologia da rede de interconexão são considerados, se a evidência provar que estas são importantes. (Este último tópico é discutido na secção 3.7.)
• Usamos análise de importância para identificar os efeitos insignificantes que podem ser ignorados na análise. Por exemplo, se um algoritmo tem uma etapa de iniciação seguida por vários milhares de iterações de uma fase de computação, então, a menos que o tempo de iniciação seja deveras significativo consideramos apenas a fase de computação na nossa análise.
• Usamos estudos empíricos para calibrar modelos simples ao invés de desenvolver de raíz modelos mais complexos.

Tempo de Execução

Começamos por examinar os três componentes do tempo total de execução: o tempo de computação, o tempo de comunicação e o tempo de ócio.

Tempo de Computação O tempo de computação de um algoritmo ($T_{comp}$) é o tempo gasto a efectuar cálculos sem contar a comunicação e a ociosidade. Se tivermos um programa sequencial que executa a mesma computação que um algoritmo paralelo podemos determinar o $T_{comp}$ cronometrando aquele programa. Doutra forma, temos que realizar chaves de medição directa.

O tempo de computação depende, normalmente, em alguma medida, do tamanho do problema, quer o tamanho seja representado por um único parâmetro $N$ ou por um conjunto de parâmetros $N_1,N_2...N_m$. Se o algoritmo paralelo replicar a computação, então o tempo de computação depende também do número de tarefas ou de processadores. Num computador paralelo heterogéneo (tal como uma rede de estações de trabalho) o tempo de computação pode variar em função do processador em que a computação é efectuada.

O tempo de computação depende, também, das características dos processadores e dos sistemas de memória. Por exemplo, a variação do tamanho do problema ou do número de processadores pode alterar a rendimento da cache ou a eficiência do encadeamento dos processadores. Como consequência, não é possível assumir, automaticamente, que o tempo total de computação se mantém constante à medida que se altera o número de processadores.

Tempo de Comunicação O tempo de comunicação de um algoritmo ($T_{com}$) é o tempo que as tarefas gastam a enviar e a receber mensagens. Podem distinguir-se dois tipos diferentes de comunicação: a comunicação inter-processadores e a comunicação intra-processador. Na comunicação inter-processadores, as duas tarefas em comunicação estão localizadas em diferentes processadores. Este será sempre o caso se um algoritmo cria uma tarefa por processador. Na comunicação intra-processador, as duas tarefas em comunicação estão localizadas no mesmo processador. Por simplicidade, assumimos que os custos da comunicação inter-processadores e intra-processador são comparáveis. Talvez surpreendentemente, esta assunção não é descabida em muitos multi-computadores, a menos que a comunicação intra-processador esteja altamente optimizada. Isto, porque os custos de copia memória-para-memória e a comutação de contextos efectuada num implementação típica de comunicação intra-processador é muitas vezes comparável com o custo da comunicação inter-processadores. Noutros ambientes, tais como estações de trabalho ligadas por Ethernet, a comunicação intra-processador é muito mais rápida.

Na arquitectura idealizada de um multi-computador, o custo do envio de uma mensagem entre duas tarefas localizadas em diferentes processadores pode ser representado por dois parâmetros: o tempo de estabelecimento da mensagem, $t_s$, que é o tempo necessário para iniciar a comunicação, e o tempo de transferência por palavra (tipicamente 4-octetos), $t_w$, determinado pela largura de banda física do canal de comunicação que liga os processadores origem e destino. Tal como é ilustrado pela figura 3.3, o tempo necessário para enviar uma mensagem de tamanho $L$ palavras é então

$$T_{msg}=t_s + t_wL.$$ (3.1)

Este modelo idealizado de rendimento da comunicação é apropriado para muitos casos mas não cobre todas as situações. Modelos mais detalhados são apresentados na secção 3.7.

Figura: 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.

A tabela 3.1 lista os valores aproximados de $t_s$ e $t_w$ para alguns computadores paralelos: Porque esses valores tendem a mudar rapidamente à medida que os equipamentos e o software evoluem, estes devem ser verificados antes de serem usados em modelos de rendimento. É de salientar a variação considerável tanto nos valores de $t_s$ como de $t_w$. Nitidamente, computadores diferentes têm características de rendimento de comunicação muito diferentes .

Os valores na tabela 3.1 obtidos, quer da literatura quer por ajuste da equação 3.1 aos tempos de comunicação, foram medidos através de um pequeno programa de teste que envia mensagens para a frente e para trás entre dois processadores.

Máquina	$t_s$	$t_w$
IBM SP2	40	0.11
Intel DELTA	77	0.54
Intel Paragom	121	0.07
Meiko CS-2	87	0.08
nCUBE-2	154	2.4
Thinking Machines CM-5	82	0.44
Estações de Trabalho em Ethernet	1500	5.0
Estações de Trabalho em FDDI	1150	1,1

Tabela: Valores aproximados dos parâmetros da máquina para alguns computadores paralelos, em micro-segundos ($\mu$seg.). Alguns dos dados foram fornecidos por T. Dunigam.

A figura 3.4 apresenta alguns valores experimentais representativos de dados obtidos com este programa. Estes tempos são para uma viagem simples de ida e de volta, pelo que são duplos dos obtidos pela equação 3.1. O impacto dos custos de estabelecimento e de transmissão por palavra nos tempos de comunicação é claramente visível. São de realçar as irregularidades tanto em Ethernet como em FDDI para pequenas mensagens e os saltos periódicos nos tempos do Paragom. Estes são devidos às especificidades dos protocolos de comunicação e das estratégias de gestão dos tampões de memória usados pelas bibliotecas de comunicação. Apesar de tudo, vemos que a equação 3.1 é uma representação razoavelmente precisa dos custos de comunicação, particularmente no caso de mensagens grandes.

Figura: 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.

Os valores do quadro da tabela 3.1 representam o ``melhor rendimento alcançavel'' e podem em geral ser usados como limites inferiores dos custos de comunicação quando se estima o rendimento. Aplicações com padrões de comunicação menos regulares ou menos estruturados podem ter rendimentos inferiores. Notar, também, que os valores do quadro da tabela 3.1 não incluem outros custos, tais como, a gestão dos tampões de memória associados à passagem de mensagens. Contudo, esses custos são normalmente proporcionais ao número e tamanho das mensagens transmitidas. Assim, é, em geral, possível, através do ajuste da equação 3.1 aos dados empíricos, obter valores para $t_s$ e para $t_w$ dependentes do sistema e do algoritmo, para os quais a equação 3.1 é válida, para um largo espectro de problemas e de tamanhos de máquinas. Este procedimento é aplicado, mais adiante, em vários exemplos neste capítulo.

Tempo de ócio Tanto os tempos de comunicação como os de computação são especificados explicitamente num algoritmo paralelo; daí que é geralmente imediato determinar as suas contribuições para o tempo total de execução. Contudo, o tempo de ócio ( $T_{\acute ocio}$) pode ser mais difícil de determinar, uma vez que depende muitas vezes da ordem pela qual as operações são efectuadas.

Figura: 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.

Um processador pode estar ocioso devido à falta de computação ou falta de dados. No primeiro caso, o tempo de ócio pode ser evitado usando técnicas de balanceamento de carga, tais como as introduzidas na secção 2.5.1. No segundo caso, o processador está ocioso enquanto a computação e a comunicação necessárias para gerar dados remotos estão a ser efectuados. Este tempo de ócio pode algumas vezes ser evitado estruturando o programa de forma a que os processadores efectuem outros cálculos ou comunicações, enquanto esperam pelos dados remotos. Esta técnica, é designada por sobreposição de computação e comunicação, uma vez que a computação local é efectuada concorrentemente com a comunicação e a computação remotas (figura 3.5). Tal sobreposição pode ser alcançada de duas formas. Uma abordagem simples é criar múltiplas tarefas em cada processador. Quando uma tarefa bloqueia à espera dos dados remotos, o processador pode comutar para uma outra tarefa para qual já há dados disponíveis. Esta abordagem tem a vantagem da simplicidade mas só é eficiente se o custo do escalonamento de uma nova tarefa for inferior ao tempo de ócio que se procura evitar. Em alternativa, uma tarefa simples pode ser estruturada de forma que os pedido de dados remotos sejam entremeados explicitamente com outra computação.
---------------------------------------------------
$\bullet$ Exemplo 3.1 (Diferenças Finitas) Neste capítulo, usamos um algoritmo paralelo de diferenças finitas semelhante ao modelo de atmosfera considerado na secção 2.6, para ilustrar como os modelos de rendimento são desenvolvidos e usados. Por simplicidade, assumimos uma malha de tamanho $N * N * Z$ pontos, sendo $Z$ o número de pontos na dimensão vertical. Inicialmente assumimos que a malha é decomposta ao longo da dimensão horizontal e repartida entre $P$ tarefas, com cada tarefa responsável por uma sub-malha de tamanho $N * (N/P) * Z$ pontos. Cada tarefa efectua os mesmos cálculos em cada ponto e em cada iteração. Porque o algoritmo paralelo não replica a computação, podemos modelar o tempo de computação em cada iteração como

$$T_{comp} = t_cN^2Z.$$ (3.2)

onde $t_c$ é o tempo de computação médio num ponto simples da malha.

Tal como na secção 2.6 consideramos um stencil de 9 pontos, o que significa que cada tarefa deve trocar $2NZ$ pontos de dados com duas tarefas vizinhas, para um total de duas mensagens e $4NZ$ dados. (Assumimos que a cada processador está alocado uma malha com pelo menos $2 * N$ pontos; caso contrário, são necessárias comunicações com mais do que dois vizinhos. Daí, o modelo de rendimento que desenvolvemos não é aplicável a mais do que $N/2$ processadores.) O custo total das comunicações, acumulado através dos $P$ processadores é

$$T_{com} = 2P(t_s + t_w2NZ).$$ (3.3)

Se $P$ dividir $N$ e a quantidade de computação por ponto da malha for uma constante, o tempo esperado de ócio pode ser negligenciável no exemplo. Nestas circunstâncias, podemos combinar as equações 3.2 e  3.3 para obter o seguinte modelo de rendimento:

$$T_{1d} = \frac {T_{comp} +T_{com}} {P}$$

$$= t_c \frac { N^2Z} {P} + t_s2 + t_w4NZ.$$ (3.4)

Eficiência e Ganho

O tempo de execução nem sempre é a métrica mais conveniente de avaliação do rendimento de um algoritmo paralelo. Como o tempo de execução tende a variar com o tamanho do problema, os tempos de execução têm de ser normalizados para comparação do rendimento do algoritmo para diferentes tamanhos de um problema. A eficiência - a fracção de tempo que os processadores gastam a fazer trabalho útil - é uma métrica relacionada que pode, muitas vezes, fornecer uma medida mais conveniente da qualidade de um algoritmo paralelo. Esta, caracteriza o uso efectivo pelo algoritmo dos recursos de um computador paralelo de uma maneira independente do tamanho do problema. Definimos a eficiência relativa como

$$E_{relativa}=\frac {T_1} {PT_P},$$ (3.5)

sendo $T_1$ o tempo de execução num único processador e $T_P$ o tempo de execução em $P$ processadores. A quantidade relacionada ganho relativo,

$$S_{relativa}=PE.$$ (3.6)

é o factor de redução do tempo de execução para $P$ processadores.

As quantidades definidas pelas equações 3.5 e  3.6 são chamadas eficiência e ganho relativas porque estas são definidas com respeito à execução do algoritmo paralelo num único processador. Estas são úteis quando se explora a escalabilidade de um algoritmo mas não constituem um valor de mérito absoluto. Por exemplo, se assumirmos que um algoritmo paralelo demora $10.000$ segundos, em $1$ processador, e $20$ segundos em $1.000$ processadores. Um outro algoritmo demora $1000$ segundos em $1$ processador e $5$ segundos em $1000$ processadores. Claramente, o segundo algoritmo é superior, para $P$ entre $1$ e $1000$. Apesar de atingir um ganho de apenas $200$ quando comparado com o ganho de $500$ para o primeiro algoritmo.

Quando se comparam dois algoritmos pode ser útil ter um métrica diferente do tempo de execução, independente do algoritmo. Por isso, definimos a eficiência absoluta e o ganho absoluto usando como base $T_1$ o tempo de um uni-processador para o melhor dos algoritmos conhecidos. Deste ponto em diante, usaremos frequentemente os termos eficiência e ganho sem os qualificar como relativos ou absolutos. Contudo, o contexto tornará sempre claro o significado a atribuir.
---------------------------------------------------
$\bullet$ Exemplo 3.2 (Eficiência do algoritmo das diferenças finitas) No algoritmo das diferenças finitas, $T_1 = t_cN^2Z$ e, assim, da equação 3.4 temos o seguinte modelo para a eficiência na ausência de desajustes de carga e quando $P$ divide $N$:

$$E = \frac {t_c N^2Z} {t_c N^2Z + t_s2P + t_w4NZP}.$$ (3.7)

Porque o algoritmo para o uni-processador é idêntico ao algoritmo paralelo quando $P =1$ esta equação representa a eficiência absoluta.

Análise de Escalabilidade

Os modelos de rendimento do tipo desenvolvido nas secções anteriores são instrumentos que podemos usar para explorar e refinar o desenho de um algoritmo paralelo. Estes modelos podem ser usados sem um tratamento mais profundo para efectuar a análise qualitativa do rendimento. Por exemplo, a partir das equações 3.4 e 3.7 podem fazer-se as seguintes observações acerca do algoritmo de diferenças finitas.

• A eficiência diminui com valores crescentes de $P$, $t_s$ e $t_w$.
• A eficiência aumenta com valores crescentes de $N$, $Z$ e $t_c$.
• O tempo de execução diminui para valores crescentes de $P$ mas é limitado inferiormente pelo custo de trocar duas secções da lista.
• O tempo de execução aumenta para valores crescentes de $N$, $Z$, $t_c$, $t_s$ e $t_w$.

Estas observações dão indicações interessantes sobre as características do algoritmo. Contudo, não constituem uma base suficiente para tomar compromissos de desenho. Esta tarefa necessita de resultados quantitativos que, pelo seu lado, nos obrigam a substituir pelos valores numéricos específicos de cada máquina os vários parâmetros do modelo de rendimento. Em geral, procuramos obter esses valores númericos através de estudos empíricos, tal como será discutido na secção 3.5. Uma vez de posse dos dados empíricos, podemos usar os modelos para responder a questões tais como as que seguem:

• O algoritmo cumpre os requisitos de desenho (de tempo de execução, de memória, etc.) do computador paralelo específico?
• Quão adaptável é o algoritmo? Isto é, adapta-se bem ao aumento do tamanho do problema e do número de processadores? Qual é o grau de sensibilidade à alteração de parâmetros, tais como, $t_s$ e $t_w$?
• Que comparações se podem fazer com outros algoritmos para o mesmo problema? Que diferenças para os tempos de execução podem ser esperados para os diferentes algoritmos?

É importante recordar que os modelos de rendimento são abstracções de problemas bem mais complexos. A partir do momento em que se concretiza o algoritmo, estamos em condições de validar os modelos e assim aumentar a confiança na sua qualidade. Contudo, nas primeiras etapas do desenho do algoritmo, devemos ser necessariamente cautelosos, especialmente se estivermos a fazer previsões quantitativas, ou se o computador específico tiver uma arquitectura muito diferente do modelo idealizado do multi-computador.

Escalabilidade em Problemas de Tamanho Fixo

Um aspecto importante da análise de rendimento é o estudo da variação do rendimento de um algoritmo com parâmetros tais como o tamanho do problema, o número de processadores e o custo de arranque de uma mensagem. Em particular, podemos avaliar a escalabilidade de um algoritmo paralelo, isto é, quão efectivamente podemos usar um número crescente de processadores. Uma abordagem à quantificação da escalabilidade é a determinação da forma como o tempo de execução $T$ e a eficiência $E$ variam com o aumento do número de processadores $P$, para um problema fixo em tamanho e parâmetros da máquina. Esta análise de um problema fixo permite-nos responder a questões do tipo: - Quão rapidamente pode ser resolvido o problema $A$ no computador $X$?, e ainda, - Qual o número máximo de processadores que podem ser usados quando se pretender manter a eficiência a 50 porcento? Esta última questão pode ter interesse se o computador for partilhado e houver encargos para cada processador usado.

É importante considerar tanto $E$ como $T$ quando se avalia a escalabilidade. Apesar de $E$, em geral, diminuir monotonamente com $P$, na verdade $T$ pode crescer se o modelo de rendimento incluir um termo proporcional a uma potência positiva de $P$. Nestes casos, pode não ser produtivo usar mais do que um número máximo de processadores, para um determinado tamanho de problema e parâmetros da máquina.
---------------------------------------------------
$\bullet$ Exemplo 3.3 (Escalabilidade do Algoritmo de Diferenças Finitas) A figura 3.6 ilustra a análise de problemas fixos aplicada ao algoritmo das diferenças finitas (equações 3.4 e 3.7). Esta figura representa graficamente $T$ e $E$ como uma função de $P$ e de $N$, usando os parâmetros característicos de um multi-computador de grão relativamente fino. O custo de computação $t_c = 1\mu$seg foi obtido experimentalmente, da forma descrita no exemplo 3.5. Recordar que, porque o algoritmo obriga a cada tarefa conter pelo menos duas colunas da grelha, podem usar-se com productividade no máximo 64 processadores quando $N = 128$ e $256$ processadores quando $N = 512$. No capítulo, mais adiante, veremos como estas previsões podem ser comparadas com o rendimento obervado.

Figura: 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.

Escalabilidade em Problemas de Tamanho Variável

Os grandes computadores paralelos são frequentemente usados, não apenas, para resolver rapidamente problemas de tamanho fixo, mas também, para resolver problemas maiores. Esta consideração encoraja uma abordagem diferente à análise de algoritmos, chamada análise de problemas escaláveis, em que consideramos não o modo como $E$ varia com $P$, mas de que forma deverá crescer a quantidade de computação com $P$ para manter $E$ constante. Esta função de $N$ é chamada função de iso-eficiência de um algoritmo e pode fornecer um conhecimento valioso sobre o comportamento do algoritmo. Um algoritmo com uma função de iso-eficiência de ${\cal O}(P)$ é altamente escalável, uma vez que, a quantidade de computação, só, necessita de crescer linearmente com respeito a $P$, para manter a eficiência $E$ constante. Em contraste, um algoritmo com uma função de iso-eficiência quadrática ou exponencial seria muito pobremente escalável.

Recordar que a eficiência $E$ é definida como a razão entre o tempo de execução num só processador e o tempo total de execução de todos os $P$ processadores.

$$E=\frac{T_1} {T_{comp} +T_{com} +T_{\acute ocio}}.$$

Assim, para manter constante a eficiência $E$, para valores crescentes de $P$ deverá ser mantida a seguinte relação:

$$T_1= E (T_{comp} +T_{com} +T_{\acute ocio}).$$

Isto é, o tempo num uni-processador deverá crescer na mesma proporção que o tempo paralelo total, ou equivalentemente, a quantidade de computação efectiva deverá crescer na mesma proporção das sobrecargas introduzidas pela replicação da computação, pela comunicação e pelo tempo de ócio.

A análise de problemas escaláveis não faz sentido para todos os tipos de problemas. Restrições temporais reais, por exemplo na previsão de clima, obrigam a que a computação se complete num intervalo de tempo fixo. Noutras aplicações, não é possível escalar, por restrições físicas do tamanho do próprio problema. Por exemplo, na modelação molecular, o número de átomos numa molécula é finito, tal como é fixo o número de pixéis em aplicações de processamento de imagens.
---------------------------------------------------
$\bullet$ Exemplo 3.4 (Iso-eficiência dos algoritmos de diferenças finitas) Usamos a análise da iso-eficiência para examinar a escalabilidade de dois algoritmos de diferenças finitas. Recordar que a iso-eficiência de um algoritmo baseado numa decomposição 1-D de uma grelha $N$ * $N$ * $N$ é dada pela equação 3.7. Para uma eficiência constante, a função de $P$ quando substituída por $N$, deverá satisfazer a seguinte relação, para valores crescentes de $P$ e $E$ constante:

$$t_cN^2Z \approx E(t_c N^2Z + t_s2P + t_w4NZP).$$

A função $N = P$ satisfaz os requisitos e dá origem à seguinte relação que é válida para todos os valores de $P$, excepto para pequenos valores quando o termo $t_s$ se torna significativo:

$$t_cZ \approx E(t_cZ + t_s\frac{2}{P}+t_w4Z).$$

Porque o algoritmo de diferenças finitas opera numa malha quadrada, quando se escala $N$ com $P$ o resultado é que o número de pontos da malha e, em consequência, a quantidade de computação escala com $P^2$. Daí, podermos dizer que, a função de iso-eficiência para este algoritmo é de ${\cal O}(P^2)$ o que significa que a quantidade de computação deverá crescer com o quadrado do número de processadores de forma a poder manter constante a eficiência. A figura 3.7 mostra porque é que isto acontece.

Figura: 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.

Como um segundo exemplo, consideremos uma decomposição a duas dimensões do problema das diferenças finitas. Neste caso cada tarefa é responsável por $(\frac{N}{\sqrt{P}})(\frac{N}{\sqrt{P}})Z$ e deve trocar, em cada passo, $2(\frac{N}{\sqrt{P}})Z$ pontos com cada um dos quatro vizinhos. Assim,

$$E = \frac {t_cN^2Z} {t_c N^2Z + t_s4P + t_w8NZ\sqrt{P}}.$$ (3.8)

Para uma eficiência constante, uma função de $P$, quando substituída por $N$, deverá satisfazer a seguinte relação para valores crescentes de $P$:

$$t_cN^2Z \approx E(t_c N^2Z + t_s4P + t_w8NZ\sqrt{P}).$$

A função $N = \sqrt{P}$ satisfaz os requisitos e dá lugar à seguinte relação, para todos os valores de $P$:

$$t_cZ \approx E(t_cZ + t_s4 + t_w8Z).$$

Porque a computação total é de novo proporcional a $N^2$, a função de iso-eficiência é de ${\cal O}(P)$. A análise revela que a decomposição 2-D é mais escalável que a decomposição 1-D.

Este exemplo ilustra uma regra geral: A decomposição num elevado número de dimensões tende a ser mais eficiente que a decomposição num número reduzido de dimensões. Para compreender as razões, consideremos as equações 3.7 e 3.8. Enquanto a decomposição 2-D envia um número maior, mas não significativo, de mensagens ( quatro em vez de duas), o volume de dados é reduzido de um factor de $\sqrt{P}$, de ${\cal O}(NP)$ para ${\cal O}(N\sqrt{P})$. Os custos totais das comunicações são reduzidos, a menos que $P$ e $N$ sejam pequenos ou $t_s$ seja muito maior do que $t_w$.

Perfis de Execução

Se a análise de escalabilidade sugerir que o rendimento é pobre para tamanhos de problemas e computadores de interesse, podemos usar os modelos para identificar as origens da ineficiência e em consequência as áreas em que um algoritmo pode ser melhorado.

Um rendimento pobre pode ser provocado por uma excessiva replicação da computação, pelo tempo de ócio, pelo arranque das mensagens, pelos custos de transferência de dados, ou qualquer combinação destes factores. Um primeiro passo, importante quando se pretende melhorar um algoritmo, é a identificação de qual daqueles factores é dominante. Podemos fazer isto, calculando para o algoritmo um perfil esperado de execução que indique a contribuição daqueles diferentes factores para o tempo de execução como uma função de $N$ e/ou de $P$.

Esta abordagem é ilustrada na figura 3.8 para um algoritmo 1-D de diferenças finitas. O modelo prevê que quando este algoritmo é executado num multi-computador com apenas uma camada vertical $(Z=1)$, a transferência de dados domina o tempo de execução quando $P$ é grande; o custo de arranque das mensagens é também significativo. Se o número de camadas verticais aumentar, os custos de arranque das mensagens passam a ser insignificantes, melhorando a eficiência em geral.

Figura: 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.

A informação dos custos desta espécie pode ser usada para reorientar o desenho de um algoritmo. Esta, pode muitas vezes motivarmos para reconsiderar decisões tomadas cedo demais no processo de desenho. Por exemplo, se a replicação da computação provocar uma redução de rendimento, então pode ser a altura de reavaliar um algoritmo, anteriormente abandonado, que evitava a replicação da computação à custa do aumento das comunicações. Em alternativa, custos elevados de estabelecimento de mensagens podem sugerir novos agrupamentos de forma a aumentar a granularidade. De forma idêntica, se os custos de transferência de dados forem elevados, podemos procurar replicar a computação ou enviar mais mensagens curtas se, ao fazermos isto, podermos reduzir o volume total de dados transferidos.

Estudos Experimentais

A discussão nas secções anteriores põe a enfâse nos modelos analíticos de rendimento. Todavia, a programação paralela é em primeiro lugar, e antes de mais nada, uma disciplina experimental. A flexibilidade e a facilidade de modificar o software, por um lado, e a complexidade dos sistemas de computação paralelos, por outro lado, impedem que a abordagem à programação paralela, para poder ser efectiva, se possa basear inteiramente na teoria. O papel de um modelo é muitas vezes o de assistir ao que é essencial no processo de experimentação, guiando o experimento e ajudando a explicar os resultados.

Estudos experimentais podem ser usados nas primeiras fases de desenho para determinar os valores dos parâmetros usados nos modelos de rendimento, tais como o tempo de computação por ponto de uma malha, a profundidade média de pesquisa numa árvore, ou os custos de arranque e de transferência de mensagens. Estes valores podem também ser usados para comparar, posteriormente, o rendimento observado com os modelos de rendimento.

No que se segue são revisitados vários tópicos, subtis, que podem vir à superfície durante a realização dos estudos experimentais.

Desenho Experimental

O primeiro passo a seguir num estudo experimental é a identificação dos dados que pretendemos obter. Por exemplo, quando se calibra um modelo de rendimento podemos estar interessados em determinar o tempo de execução de uma versão sequencial da nossa aplicação, em função do tamanho do problema, para determinar $t_c$. Ou, podemos necessitar de medir o tempo de execução de um programa simples de teste de passagem de mensagens para podermos calcular $t_s$ e $t_w$.

Geralmente, os experimentos são realizados para uma variedade de dados - diferentes tamanhos de problemas e/ou número de processadores. Maximizando o número de pontos obtidos reduzimos o impacto dos erros resultantes das medições individuais. Quando se usam dados empíricos para avaliar a qualidade de uma determinada realização, a variedade de pontos permite também estimar a precisão do modelo e identificar os regimes para os quais o modelo é inadequado.

O passo seguinte num estudo experimental é o desenho dos experimentos que irão ser usados para obter os dados requeridos. A questão crucial é assegurar que o experimento mede o que pretendemos medir. Por exemplo, se um programa compreende um passo inicial seguido por uma longa série de iterações e, o nosso modelo de rendimento trata apenas dos custos de uma iteração, então, é isso mesmo que é necessário medir.

Obtenção e Validação dos Dados Experimentais

O principal desafio numa experiência é a obtenção de resultados precisos e reprodutíveis. Os tempos de execução podem ser obtidos seguindo vários caminhos; saber qual o melhor irá depender, simultaneamente, dos requisitos e das facilidades disponíveis no computador a estudar. Uma abordagem imediata mas potencialmente dispendiosa é a que incorpora código no próprio programa que evoca rotinas de tempo de sistema para determinar o tempo gasto. Em princípio as evocações deverão ser realizadas em cada processador e a partir daí escolher o valor máximo. Contudo, pode muitas vezes identificar-se um processador que nem começa nem acaba significativamemente mais tarde, ou mais cedo, do que os outros e fazer as medições com base apenas neste processador. Em alternativa, pode usar-se uma ferramenta de traçados ou de perfis que obtém os dados automaticamente.

As experiências devem ser sempre repetidas para podermos verificar se os resultados são reprodutíveis. Em geral, os resultados não deverão variar acima duma pequeno quantidade - 2 ou 3 por cento é um valor muito grande se se pretende um ajuste fino dos algoritmos. Possíveis causas de variação incluem o seguinte:

• Algoritmo não determinístico. Os programas podem usar números aleatórios, ou podem explorar um espaço de pesquisa ou alocar tarefas a processadores de uma forma dependente do tempo (como é o caso do algoritmo pesquisa da secção 2.7). O não determinismo com origem nos números aleatórios pode ser controlado usando um gerador paralelo reprodutível (capítulo 10). O não determinismo provocado por execuções dependentes do tempo é mais problemático. Uma solução é realizar um elevado número de tentativas. Uma outra alternativa é a normalização dos tempos de execução dividindo-os por alguma medida da quantidade de trabalho realizado, tal como o número de nodos visitados num algoritmo de pesquisa.
• Relógio de baixa precisão. O relógio usado para obter os tempos de execução pode ter uma resolução limitada ou ser pouco preciso. No primeiro caso, pode aumentar-se a precisão aumentando o tempo de execução, realizando, por exemplo, um maior número de iterações ou resolvendo o mesmo problema várias vezes. No outro caso, é necessário encontrar uma outra maneira de medir os tempos de execução.
• Custos de arranque e de paragem. O tempo requerido pelas funções de gestão de sistema que dizem respeito ao arranque dos processadores, ao carregamento de código, à alocação de memória virtual, à desactivação de processadores, etc., podem variar significativamente dependendo do estado do sistema. Os tempos são normalmente mais precisos se os componentes dependentes do sistema forem excluídos. Assim, podemos ligar relógio a seguir ao carregamento do programa e pará-lo mal se tenha obtida uma solução.
• Interferência de outros programas. Numa máquina não dedicada, podem existir outros utilizadores a competir entre si por recursos partilhados, tais como, processadores, largura de banda da rede, ou largura de banda de entrada e saída de dados. As medições de tempo podem, também, ser distorcidas pela execução das funções do sistema, como é o caso da contabilização de recursos ou das cópias de segurança activadas ocasionalmente. É de notar que a competição pode ocorrer mesmo quando os processadores estão dedicados a uma só aplicação. Por exemplo, um computador em que os processadores estão ligados numa malha a duas dimensões pode estar dividido em sub-malhas disjuntas (ver secção 3.7.2). Além disso, os pedidos de E/S gerados pelos programas que estão a ser executados numa das sub-malhas podem ter de atravessar outra sub-malha para chegar aos próprios dispositivos de E/S, ocupando desta forma uma parte da largura de banda de E/S.
• Congestionamento. Em alguns computadores, o tempo necessário para uma operação de comunicação pode aumentar quando há vários processadores a comunicar ao mesmo tempo. Por exemplo, uma rede local que use Ethernet só pode transportar uma mensagem de cada vez, assim, em caso de colisão de mensagens os emissores têm de recuperar e reenviar as mensagens. Um escalonamento infeliz pode ter como resultado sucessivas repetições de envios, aumentando desta forma o tempo de execução.
• Alocação aleatória de recursos. Os sistemas de exploração podem usar uma estratégia aleatória de arranjo de processadores que irá afectar os tempos de execução se os custos de comunicação dependerem da localização do processador na rede (ver secção 3.7). Se for possível deve usar-se sempre a mesma alocação em todos os experimentos.

O estudo da variabilidade dos resultados experimentais pode ajudar-nos a identificar as origens possíveis dos erros ou das incertezas das nossas medições. Contudo, mesmo quando os resultados são reprodutíveis, nunca teremos a certeza que estão correctos. A confiança nos resultados pode aumentar se medirmos a mesma coisa de diferentes maneiras confirmando que as medições redundantes são consistentes entre si. Por exemplo, para além de medir o tempo de um componente individual de um programa, podemos medir o tempo total para o programa.

Ajuste de Dados aos Modelos

Quando a realização dos estudos experimentais tem como objectivo a calibração, ajustamos os resultados às funções de interesse para obter valores para os parâmetros desconhecidos. O ajuste pode ser obtido graficamente traçando pontos e estimando o ajuste. Por exemplo, se a função é

$$T_{msg} = t_s + t_wL,$$

podemos traçar os pontos $T_{msg}(i)$ como uma função de $L$ e desenhar uma linha que se ajuste a esse pontos. A inclinação desta linha será $t_w$ e a intersecção do eixo $T_{msg}$ quando $L=0$ será $t_s$.

Em alternativa, e de forma mais precisa, podemos realizar, recorrendo às medições, um ajuste de mínimos de quadrados da função. (Há pacotes matemáticos tais como: Mathematica e Matlab que disponibilizam funções de ajuste.) Um ajuste de mínimos de quadrado envolve uma minimização da soma dos quadrados das diferenças entre os valores observados, $obs(i)$, e os valores da função correspondente, $f(i)$:

$$\sum _i (obs(i) - f(i))^2.$$

Por exemplo, quando se ajusta a função $T=t_cN^2Z$ com as observações de $T$ para diferentes valores de $N$ para calcular o valor de $t_c$, minimizamos:

$$\sum _i (T(i) -t_ci^2Z)^2.$$

Quando se ajustam os tempos de execução para diferentes números de processadores, o método que acabamos de descrever dá menos peso aos (presumivelmente mais curtos) tempos para um número elevado de processadores, apesar de estes serem tipicamente os valores de maior interesse. Por essa razão, pode usar-se um ajuste de mínimos quadrados ponderado, para o qual a diferença entre os valores observados e os valores da função são calculados da seguinte forma:

$$\sum _i \left ( \frac{obs(i) - f(i)} {obs(i)}\right )^2.$$

---------------------------------------------------
$\bullet$ Exemplo 3.5 (Determinação do tempo de computação ($t_c$)) Consideremos o problema da determinação do custo da computação por ponto da malha do algoritmo das diferenças finitas. Recordar que o custo é calculado através da fórmula (Equação 3.2) seguinte:

$$T_{comp} = t_cN^2Z.$$

Nesta equação, $t_c$ é o parâmetro que pretendemos determinar e $N$ é o valor que podemos variar enquanto medimos o rendimento (Por simplicidade mantemos o valor de $Z$ fixo). O quadro na tabela 3.2 mostra os tempos de execução medidos numa estação de trabalho Sun SPARC 2. A experiência foi feita quando a máquina estava ociosa sem estar em modo utilizador-único; por isso pode existir uma reduzida actividade de manutenção de sistema. Cada experimento foi repetido três vezes para poder estudar a variabilidade; o quadro lista, também, a média de cada conjunto de três valores. A repetição das experiências mostra uma pequena variação no tempo de execução total.

N	T1	T2	T3	Média
2	0.477	0.471	0.479	0.476
4	1.75	1.73	1.73	1.74
8	6.62	6.63	6.68	6.64
16	26.9	26.9	26.4	26.7
32	112	112	112	112
64	459	459	460	459
128	1930	1929	1934	1931
256	7949	7873	7897	7906

Tabela: Tempo de execução em mili-segundos para uma iteração simples do algoritmo das diferenças finitas executado numa estação de trabalho Sun SPARC 2, com $Z$ = 10.

A figura 3.9 mostra o ajuste simples e ponderado da equação 3.2 para os dados da tabela 3.2. Os dois ajustes correspondem aos valores de $t_c$ de $0.0120 \mu$seg e $0.0112 \mu$seg, respectivamente.

Figura: 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.

Os tempos de execução previstos pelos dois modelos são apresentados na tabela 3.3. Tal como era de esperar, o ajuste simples é mais preciso para valores elevados de $N$, enquanto que o ajuste ponderado é melhor para valores mais pequenos de $N$; ambos são suficientemente bons para efeitos práticos. Estes resultados sugerem que o modelo de rendimento teórico, $T=t_cN^2Z$ caracteriza apropriadamente o tempo de computação do algoritmo das diferenças finitas.

Modelo de Rendimento
N	Obervado	Simples	Ponderado
2	0.476	0.480	0.448
4	1.74	1.92	1.79
8	6.64	7.68	7.16
16	26.7	30.7	28.7
32	112	123	115
64	459	491	459
128	1931	1966	1835
256	7906	7864	7340

Tabela: Tempos previstos de execução, para o código do algoritmo das diferenças finitas executado numa estação de trabalho Sun SPARC 2, com $Z$ = 10 (mili-segundos).

Avaliação das Realizações

Os modelos de rendimento desempenham, também, um papel de grande importância depois de concluído o desenho, quando se inicia a escrita do programa. Comparações entre os tempos de execução observados e os previsíveis podem fornecer uma informação valiosa tanto do algoritmo como da sua realização.

Mesmo que se seja extremamente cauteloso no desenho e na realização das experiências, a natureza idealizada do modelo faz esperar uma discrepância entre os tempos de execução observados e os previsíveis. Quando as discrepâncias são significativas isso pode querer significar que, ou o modelo é errado, ou a realização do código inadequada. No primeiro caso, os resultados experimentais servem para determinar as deficiências do modelo; esta informação habilita-nos a de novo tomar em consideração o peso dos argumentos usados para justificar o desenho. No segundo caso, pode usar-se o modelo para identificar as áreas nas quais a implementação pode ser melhorada.

Número de Processadores
Componentes	1	2	4	8	16	32
le	17.78	13.08	6.59	5.15	1.87	1.08
fock	3124.52	1588.35	816.00	420.04	213.29	109.80
diag	3.31	3.29	3.43	3.46	3.51	3.54
mxm	0.41	0.40	0.34	0.40	0.39	0.40
dadd	0	0.02	0.01	0.02	0.02	0.8
zero	0	0.02	0.01	0.02	0.02	0.06
copy	0	0.01	0.01	0.01	0.02	0.03
init	86.37	54.29	31.14	17.37	11.19	9.05
other	1.25	0.37	0.08	0.17	0.23	0.42
Total	3233.65	1659.85	857.64	446.69	230.57	124.47

Tabela: Um perfil de execução simples para um único passo de execução de um programa paralelo de química que incorpora o algoritmo da construção da matriz de Fock da secção 2.8, como código base executado num computador IBM SP. O perfil mostra o tempo de execução gasto nas diferentes partes do programa fazendo variar o número de processadores e o tempo total de execução. A escalabilidade é razoavelmente boa, apesar de ser evidente que a rotina diag não foi paralelizada. A rotina init não escala bem, mas este custo é menos importante porque normalmente o código corre durante muitos passos.

Quando postos perante uma diferença significativa entre os tempos previstos pelo modelo e os tempos de execução, o primeiro passo a seguir deverá ser testar tanto o modelo de rendimento como o nosso desenho experimental para poder verificar não apenas a correcção de cada um deles, mas também se estão a medir a mesma coisa.

O próximo passo deverá ser a obtenção de um perfil de execução do código paralelo (em contraste com o perfil discutido na secção 3.4.3, este perfil de execução deve ser baseado em valores medidos). O objectivo deverá ser obter uma visão mais detalhada do comportamento do programa medindo, por exemplo, o tempo gasto na iniciação, o tempo gasto nas diferentes fases da computação, o tempo total de ociosidade e os totais em número e volume de mensagens trocadas. Idealmente, os dados deverão ser obtidos de entre uma vasta gama de tamanhos de problemas e de número de processadores. Os quadros das tabelas 3.4 e  3.5 mostram valores típicos dos dados de perfis de execução, o exemplo é o da execução de um programa paralelo de química que incorpora o algoritmo da construção da matriz de Fock da secção 2.8 como código base. Estes dados foram obtidos usando instrumentos de medição inseridos manualmente no programa.

Um vez obtido um perfil de execução podemos compará-lo com o modelo de rendimento para identificar tanto as deficiências do modelo, como as deficiências da realização. Nas próximas secções identificamos vários problemas que podem ser revelados pela análise de um perfil de execução.

Processador
Componentes	0	1	2	3	4	5
Frequências:
get	9404	9837	5143	10237	10359	9948
accum	9398	9397	5143	10237	10359	9948
put	2502	2496	2496	2496	2496	2496
barrier	85	85	85	85	85	85
zero	8	8	8	8	8	8
add	4	4	4	4	4	4
scale	3	3	3	3	3	3
Tempos:
get	17.483	17.336	10.848	18.095	18.773	18.039
accum	2.794	3.127	4.427	3.005	3.043	2.884
put	0.740	0.961	1.514	0.790	1.406	1.001
barrier	5.403	7.001	4.742	2.409	4.049	4.342
zero	0.062	0.069	0.069	0.069	0.068	0.068
gemm	0.415	0.414	0.416	0.415	.0415	0.415
add	0.034	0.034	0.00	0.033	0.033	0.033
scale	0.030	0.027	0.027	0.027	0.029	0.030
Total	241.648	241.467	241.440	241.466	241.447	241.450

Tabela: Um perfil de execução mais detalhado para o código da tabela 3.4. Aqui apresentamos frequências e tempos de execução para várias rotinas de comunicação em cada processador. Para sermos breves, apenas 6 dos primeiros 16 processadores são considerados. A carga dos instrumentos de medição fazem aumentar o tempo de 230 segundos na tabela 3.4 para 241 segundos. As rotinas get, accum, put lêem e escrevem dados em listas de dados globais. Uma operação de get que bloqueia à espera de uma resposta a um pedido remoto, leva cerca de 1.7 mili-segundos em média. Uma vez que cada uma das transferências de dados é relativamente pequena e que o $t_w$ para o IBM SP é baixo, esta medida deve incluir um tempo substancial de ócio, provavelmente em sobreposição com a computação local. A segunda maior contribuição para os custos de comunicação é a operação barrier, usada para assegurar que as actualizações de uma lista de dados global é completada antes de se darem início às leituras. Talvez seja conveniente analisar o programa para determinar até que ponto são necessárias 85 barreiras por passo de execução.

Problemas Inesperados

Começamos por considerar os problemas que podem levar a observar tempos de execução superiores aos previstos por um modelo. Muitas vezes, uma tal situação ocorre porque o modelo de rendimento está incompleto: foi negligenciado um qualquer aspecto, supostamente insignificante, de um algoritmo, ou de uma realização do mesmo que demonstrou na prática a sua importância na determinação do tempo de execução.

• Desequilíbrio da carga. Um algoritmo pode ter desequilíbrios na carga de computação ou de comunicação que não tenham sido considerados no modelo de rendimento. Estes problemas podem ser revelados a partir do estudo da variação dos custos em cada processador.
• Computação Replicada. As disparidades entre os tempos observados e os previstos podem também indiciar problemas na realização. Por exemplo, podemos ter falhado na paralelização de um qualquer componente, na convicção que o custo de replicação da sua computação em todo o processador seria insignificante. Quando se trabalha com um elevado número de processadores esta consideração pode não ser válida. A detecção deste tipo de problemas pode ser conseguida pelo estudo dos custos em diferentes partes de um programa e para números variáveis de processadores.
• Desajuste Algoritmos/Instrumentos. Os instrumentos disponíveis para realizar o algoritmo podem introduzir ineficiências. Por exemplo, a linguagem ou a biblioteca de rotinas usadas para executar um algoritmo que cria múltiplas tarefas por processador para promover a sobreposição da comunicação com a computação, podem não permitir obter uma realização eficiente das tarefas.
• Competição na Largura de Banda. A equação 3.1 que permite calcular o tempo gasto para transmitir uma mensagem pode não caracterizar adequadamente a rede de comunicações em que o programa está a ser executado. Em particular, a existência de comunicações concorrentes que competem na mesma banda da rede podem aumentar os custos de comunicação. Estes tópicos são discutidos na secção 3.7.

Anomalias do Ganho

Uma determinada realização pode ser mais rápida que a prevista pelo modelo. Se este efeito se for acentuando à medida que o número de processadores aumenta, o fenómeno é designado por anomalia do ganho - o valor obervado do ganho é superior ao previsto. Por vezes, podemos encontrar um ganho maior do que linear sendo então chamada de super-linear. Situações deste tipo podem ocorrer nos seguintes casos:

• Efeitos da Cache. Em muitos computadores paralelos, cada processador tem para além de uma elevada quantidade de memória convencional, uma outra memória (cache), de grandeza muito inferior, para acesso muito rápido. Quando um programa é executado num elevado número de processadores, uma maior quantidade de dados pode residir nesta memória rápida. Como resultado o tempo total de computação $(T_{comp})$ tende a diminuir. Se a redução em $T_{comp}$ a partir deste efeito cache contrabalancear os aumentos de $T_{com}$ e de $T_{\acute ocio}$ provocados pelo uso de mais processadores, então, a eficiência irá ser superior a $1$ e o ganho será super-linear. De forma semelhante, o aumento do tamanho da memória convencional pode reduzir os custos de acesso à memória porque evita os acessos à memória virtual.
• Anomalias na Pesquisa. Este fenómeno é observável em alguns tipos de algoritmos de pesquisa, tais como o branch-and-bound da secção 2.7. Se uma árvore de pesquisa tem soluções de profundidades variáveis, então múltiplas pesquisas do tipo depth search exploram, em média, menos nodos da árvore antes de encontrar uma solução do que uma pesquisa depth search estritamente sequencial. É de notar que, neste caso, o algoritmo paralelo executado não é igual ao sequencial. De facto, o melhor algoritmo sequencial para um uni-processador poderá ser o que segue várias pistas, concorrentemente.

---------------------------------------------------
$\bullet$ Exemplo 3.6 (Avaliação do programa das diferenças finitas) Consideramos o comportamento de uma realização do algoritmo das diferenças finitas, 1-D. A figura 3.10 mostra o rendimento observado, rendimento previsto pela equação 3.4 e o rendimento previsto por um modelo mais refinado que apresentaremos a seguir. Apresentamos ganhos em vez de tempos de execução absolutos de forma a revelar de forma clara os resultados para valores elevados de $P$. A curva de previsão de rendimento usa valores de parâmetros para a máquina obtidos por um processo de ajuste para poder tomar em consideração sobrecargas adicionais não contabilizadas pelos ``melhores'' valores dos parâmetros da tabela 3.1. A comparação dos dois conjuntos de valores dos parâmetros ($t_s = 200\mu$seg versus $77\mu$seg, $t_w = 2\mu$seg versus $0.54\mu$seg) indicam que a realização do algoritmo incorre em sobrecargas significativas. O que sugere a existência de oportunidades para optimização.

Figura: 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.

A figura 3.10 mostra que a equação é pouco precisa para $N = 512$ e valores elevados de $P$. O ganho observado não cresce continuamente, ao contrário do previsto, mas em degrau. Esta observação sugere que o modelo é incorrecto na assunção de que alguns aspectos do rendimento do programa variam continuamente com $P$. Examinando a equação 3.4, vemos que apenas o custo de computação depende de $P$; tanto o número de mensagens como o tamanho das mensagens por processador são constantes e por isso independentes de $P$. Parece pois claro o problema. A equação 3.4 assume que cada processador tem $N/P$ colunas da malha. Na realidade $P$ não é sempre divisível por $N$. Mais especificamente, algumas das tarefas conterão $\lceil N/P \rceil NZ$ pontos da malha enquanto outras conterão $\lfloor N/P \rfloor NZ$. Por exemplo, se $N=8$, Z = 1, e $P = 3$, algumas terão $3.8.1 = 24$ e outras $2.8.1 = 16$ pontos da malha. Assim enquanto o tempo total de computação é dado pela equação 3.4, o máximo custo de computação em cada processador é o seguinte:

$$T_{max}comp = \left \lceil \frac {N} {P} \right \rceil NZ.$$

Esta distribuição não balanceada da computação leva à existência de tempos de ócio, uma vez que em cada iteração os processadores com menos carga deverão terminar antes dos que têm carga superior. O tempo total de ócio é a diferença entre o tempo máximo de computação e o tempo de computação médio, multiplicado pelo número de processadores:

$$\begin{eqnarray*} T_{\acute ocio} &=& \sum _{i=0} ^{P-1} ( T_{max} comp - T^i_{comp} )\\ &=& PT_{max} comp - T_{comp}. \end{eqnarray*}$$

Incorporando este tempo de ócio na equação 3.4, obtemos o modelo de rendimento mais geral:

$$T = t_cNZ \left \lceil\frac{N}{P}\right \rceil + t_s2 + t_w4NZ.$$ (3.9)

A segunda curva de previsão de rendimento da figura 3.10 é obtida usando este modelo mais refinado. De notar que os dois modelos são equivalentes para $N$ múltiplo inteiro de $P$.

Um Modelo Refinado dos Custos de Comunicação

Em seguida examinamos a forma como o modelo ideal de custos de comunicação, usado nas secções anteriores, pode ser estendido para tomar em consideração as características realistas da redes de interconexão. Passaremos em revista uma gama de arquitecturas de rede e desenvolveremos um modelo mais detalhado de rendimento das comunicação que toma em consideração o impacto da competição pela largura de banda, nos custos de comunicação. Este modelo apesar de mais detalhado continua a ser idealizado mas pode ser significantemente mais preciso em alguma circunstâncias.

Concorrência pela Largura de Banda

No modelo do multi-computador apresentado no capítulo 1, o tempo necessário para enviar uma mensagem entre processadores era independente da localização do processador e do número de processadores que eventualmente estariam em comunicação ao mesmo tempo. Esta assunção encontra reflexo no seguinte modelo de custos de comunicação, equação 3.1:

$$T_{msg}=t_s + t_wL.$$

Apesar de suficientemente preciso para muitos algoritmos e em muitas arquitecturas, este modelo pode falhar no caso da rede de interconexão de computadores ter propriedades diferentes das ideais, particularmente no caso de uma aplicação que gera muitas mensagens. Nestes casos, é necessário desenvolver um modelo mais detalhado da rede de interconexão.

Muitas redes de interconexão usam menos do que $N^2$ fios para ligar os $N$ processadores. Assim, terão de incluir nodos de encaminhamento, ou comutadores, para encaminhar as mensagens do processador origem para o processador destino. Um nodo de comutação pode bloquear ou reencaminhar mensagens quando várias mensagens requerem o acesso ao mesmo fio simultaneamente. O número de fios que têm que ser atravessados para ir de um processador a outro é designado por distância entre esses dois processadores (a distância é igual ao número de comutadores mais uma unidade). A máxima distância de um qualquer processador a um outro qualquer processador é designada por diâmetro da rede. A distância entre dois processadores e o comprimento dos fios que os ligam não são normalmente factores significativos na determinação do rendimento, apesar de ser normalmente mais caro construir redes com fios muito longos. (O comprimento dos fios pode ser importante nas redes que se estendem por dezenas ou milhares de quilómetros, onde a velocidade da luz - cerca de 5 $\mu$seg por quilómetro em cabo óptico - coloca um limite inferior no atraso da comunicação.)

Um factor que pode ter um impacto significativo no rendimento da comunicação e que estudaremos com alguma profundidade é a concorrência pela largura de banda. Dois processadores podem necessitar de enviar dados pela mesma linha ao mesmo tempo. Tipicamente, só uma mensagem pode ser transmitida em cada momento, razão pela qual a transmissão da outra mensagem tem de ser retardada. Contudo, para muitos casos práticos é suficiente pensar que os dois processadores partilham a largura de banda disponível. Assim, o termo correspondente ao volume de dados da equação 3.1 passa a depender de um factor $S$ que representa o número de processadores que necessitam de transmitir concorrentemente informação pelo mesmo fio.

$$T_{msg limitado pela largura de banda} = t_s + t_wSL.$$ (3.10)

O factor reflecte a ideia que a largura de banda efectivamente disponível para cada processador é $1/S$ da largura de banda real.

A equação 3.10 não toma em atenção os custos adicionais de congestionamento que podem incorrer quando as mensagens colidem e têm de ser retransmitidas. (Os investigadores na área das redes têm vindo a desenvolver técnicas sofisticadas de simulação para poder contabilizar esses custos. Contudo, a experiência tem demonstrado que a equação 3.10 é suficientemente precisa para muitos casos práticos.

O impacto da concorrência pela largura de banda é mais acentuado nos algoritmos que executam sincronamente i.e., os algoritmos em que todos os processadores enviam e recebem mensagens aproximadamente ao mesmo tempo e nos quais os processadores não podem prosseguir com a computação enquanto estão à espera de mensagens. O problema das diferenças finitas e muitos outros algoritmos SPMD possuem esta propriedade. Em algoritmos, tais como os de pesquisa e na construção da matriz de Fock descritos no capítulo 2, os processadores executam assincronamente estando menos sujeitos a ter de competir pela largura de banda.

Redes de Interconexão

O valor de $S$ na equação 3.10 pode depender quer das propriedades do algoritmo paralelo quer da rede de interconexão subjacente. Na discussão que se segue usamos dois exemplos para ilustrar como os padrões de comunicação dum algoritmo particular podem ser analisados para determinar um valor aproximado para $S$ em diferentes redes de interconexão. Em primeiro lugar consideramos as propriedades das redes de interconexão.

Rede de Comutação por Barra Transversal Uma comutação por barra transversal evita a competição pela largura de banda pelo uso de ${\cal O}(N^2)$ comutadores para ligar $N$ entradas a $N$ saídas (figura 3.11). Neste caso, $S=1$. Apesar de ser altamente não escalável este tipo de comutação é muito popular quando se pretende ligar um pequeno número de estações de trabalho, tipicamente, 20 ou menos. Por exemplo, o comutador DEC GIGA pode ligar até 22 estações. Apesar de ser possível construir grandes comutadores de barra transversal (por exemplo, o Fujitsu VPP 500 usa um comutador de 224 x 224 para ligar 224 processadores) estes são extremamente dispendiosos.

Figura: 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.

Redes Baseadas em Barramento Nas redes que se baseiam em barramentos, os processadores partilham um único recurso de comunicação, (o barramento). Um barramento é uma arquitectura altamente não escalável porque apenas um processador pode usar o barramento de cada vez. O factor de competição $S$ é igual ao número de processadores que tentam comunicar simultaneamente.

Os barramentos são comummente utilizados em computadores paralelos de memória partilhada para comunicar pedidos de leitura e de escrita a uma memória global partilhada (figura 3.12). Em princípio o uso de memória global num computador de memória partilhada simplifica a programação paralela tornando a localidade um tópico a não considerar. Contudo, tal como foi discutido na secção 1.2.2, a maior parte dos computadores paralelos de memória partilhada usam caches numa tentativa de reduzir o tráfego no barramento; daí que a localidade continua a ser importante.

Figura: 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.

Ethernet A rede Ethernet, usada muitas vezes em LANs para ligar estações de trabalho ou computadores pessoais ao nível do departamento, é um outro exemplo de uma rede baseada em barramentos. Tal como é mostrado na tabela 3.1 uma rede Ethernet standard pode fornecer larguras de banda até 1 Mbytes por segundo. Todos os computadores ligados via Ethernet partilham um único canal de comunicação (figura 3.13). Um computador que necessite de enviar informação tem de esperar até que o canal esteja livre, para poder depois enviar as suas mensagens; se for detectada uma colisão, tem que esperar algum tempo e depois retransmiti-la. Uma vez que cada computador requer o uso exclusivo do canal para poder emitir, qualquer algoritmo que necessite de mais que um processador comunique simultaneamente, sofre uma redução efectiva da largura de banda. Assim, o termo S na equação 3.10, tal como noutras redes de barramento iguala o número de emissores simultâneos. O impacto da limitação da largura de banda imposta pela Ethernet ao rendimento é ilustrado pelos exemplos que se seguem.

Figura: 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.

Redes em Malha Uma rede em malha pode ser pensada como uma rede de comutação por barra transversal (figura 3.11) no qual os processadores estão associados com os elementos de comutação em vez de estarem colocados nas extremidades da malha. Numa malha de dimensão $D$, cada processador não posicionado nas extremidades da malha está ligado a $2D$ vizinhos. As ligações são tipicamente estabelecidas através de dois fios, um para cada sentido. Malhas com duas e três dimensões são comuns em computação paralela. Têm a vantagem sobre as topologias mais sofisticadas de poderem ser construídas no espaço tri-dimensional sem fios longos. Numa malha 2-D, uma mensagem é passada do processador $(i, j)$ para o processador $(k, l)$ em $\vert i - k\vert + \vert j - l\vert$ passos. Malhas cúbicas uni-, bi-, e tri- dimensionais de $P$ processadores tem diâmetros de $P-1$, $2\sqrt{P} -1$ e $3 (\sqrt [3] {P} -1)$ e contêm $2(P -1)$, $4(P -\sqrt {P})$ e $6(P - P^{2/3)}$) fios, respectivamente. Tal como é ilustrado pela figura 3.14 estes diâmetros podem ser reduzidos a metade se estendermos a malha com ligações em toro, de forma a que os processadores nas extremidades possam estar também ligados aos vizinhos. Contudo o toro tem duas desvantagens. A primeira, são necessários fios mais longos para a ligação entre vizinhos nas extremidades. (Esta necessidade pode ser evitada num toros 2-D, dobrando a malha.) A segunda, é que um sub-conjunto de um toro não é um toro, por isso as vantagens das ligações toroidais perdem-se se um computador com uma topologia em toro for repartido por vários utilizadores.

A competição pela largura de banda numa rede em malha ocorre sempre que dois ou mais processadores tentam transmitir através do mesmo fio, ao mesmo tempo (figura 3.15). A análise usada para determinar $S$ para um algoritmo particular é ilustrada nos exemplos a seguir.

Figura: Um toro de duas dimensões. Este é uma malha com ligações entre extremidades para que cada processador esteja ligado a quatro vizinhos.

Figura: 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.

Rede Hipercubo A rede em hipercubo foi introduzida na secção 2.4.1. Tal como numa malha, os processadores numa rede hipercubo estão associados com os elementos de comutação. Um hipercubo $d$-dimensional liga cada um dos $2^d$ processadores a outros $d$ processadores. O hipercubo pode ser definido recursivamente tal como se segue (figura 3.16). Um hipercubo $0$-dimensional representa um simples processador e um hipercubo $1$-dimensional liga dois hipercubos $0$-dimensional. Genericamente, um hipercubo de dimensão $d +1$ é construído ligando os processadores correspondentes de dois hipercubos de dimensão $d$. Tal como com a malha, o factor $S$ de competição pela largura de banda é dependente do algoritmo, embora o maior número de fios num hipercubo signifique que a competição pela largura de banda tende a ocorrer menos vezes.

As muitas e interessantes propriedades dos hipercubos estão para além dos objectivos da nossa abordagem (mas ver capítulo 11). Contudo, sublinhamos que dois processadores quando marcados como na (figura 3.16), estão ligados se e só se, a representação binária das suas marcações diferirem apenas numa única posição. Exploramos esta propriedade quando se especificam algoritmos que usam uma estrutura de comunicação em hipercubo. Uma outra importante característica de um hipercubo é que contém uma malha: este pode ser considerado uma malha com ligações adicionais de longa distância. A conectividade adicional reduz o diâmetro $d$ e aumenta o número de fios disponíveis, especialmente no caso de comunicações não locais. Uma desvantagem das ligações num hipercubo, do ponto de vista da engenharia, é ser mais complexo do que a malha. Em particular, requer fios mais longos e em maior número, uma vez que um hipercubo de dimensão superior a três não pode ser representado num espaço tri-dimensional, pelo que, os fios apenas ligam processadores fisicamente adjacentes.

Figura: 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.

Redes de Interconexão Multi-Estágios Numa rede de interconexão multi-esta'gios, (MIN), tal como numa rede de comutação por barra transversal, os elementos de comutação são distintos dos processadores. Contudo, menos que ${\cal O}(P^2)$ comutadores são usados para ligar os $P$ processadores. Em vez disso, as mensagens passam através de uma série de estágios de comutação. A figura 3.17 ilustra duas MINs representativas de uma classe geral de redes caracterizadas pelos parâmetros $n$ e $k$. Estas redes são por vezes chamadas de raíz $k$, dimensão $n$ borboletas, ou $n$-volantes de $k$-aridade. Ligações em $n$ estágios de $k^{n-1} k$ * $k$ e $n$ comutadores de barra transversal uni-direccionais ligam $P= k^n$ processadores, ou $n$ estágios de $k^{n-1} k$ * $k$ e $n$ comutadores de barra transversal bi-direccionais ligam $P=2k^n$ processadores. Neste último caso, cada ligação compreende dois canais que transportam os dados em sentidos opostos e cada barra de comutação pode encaminhar os dados que chegam em qualquer um dos $2k$ entradas para qualquer uma das $2k$ saída. De notar que, cada nível da rede liga $P$ entradas a $P$ saídas, apesar de nem toda a entrada estar directamente ligada a toda a saída em cada nível.

Numa rede MIN uni-direccional, todas as mensagens têm de atravessar o mesmo número de fios, desta forma o custo de envio de uma mensagem é independente da posição do processador. Com efeito, todos os processadores estão equi-distantes.

Numa rede MIN bi-direccional, o número de fios atravessados depende, de alguma forma, da posição do processador, apesar de em menor grau, do que o que se passa num malha ou num hipercubo (figura 3.18).

O facto de as mensagens enviadas a diferentes destinatários poderem necessitar de passar através do mesmo fio, significa que a MIN não está imune à competição pela largura de banda. De qualquer forma, uma rede MIN que liga $P$ processadores fornece $P$ fios em cada nível, pelo que em princípio deve ser possível organizar as comunicações de forma a minimizar a competição.

Figura: 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 .

---------------------------------------------------
$\bullet$ Exemplo 3.7 (Competição pela largura de banda no algoritmo das diferenças finitas) No primeiro dos dois exemplos consideramos o impacto da competição pela largura de banda num algoritmo com um alto grau de localidade; o algoritmo das diferenças finitas 1-D examinado nas secções anteriores. Recordar da equação 3.3 que de acordo com o modelo idealizado da equação 3.1, os custos da comunicação por processador são

$$T_{ideal} = t_s2 + t_w4NZ.$$

A competição pela largura de banda não é um tema nas malhas ou hipercubos porque a estrutura de comunicação baseada em anel do problema das diferenças finitas 1-D pode ser embebido nestas redes usando apenas a ligação ao vizinho mais perto. Numa rede por barramento, só um dos $P$ processadors pode comunicar em cada momento; se asumirmos que na fase de comunicação do algoritmo, de cada vez, metade dos processadores necessita de enviar (a outra metade está a receber), então $S = P/2$ e o volume de comunicações deve ser aumentado de um factor de $P/2$, dando

$$T_{barramento com df } = t_s2 + t_w2PNZ.$$ (3.11)

Figura: 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.

A figura 3.19 ilustra quer o impacto que as limitações da largura de banda podem ter no rendimento mesmo no caso de um algoritmo simples de diferenças finitas quer o melhoramento da precisão do modelo de rendimento refinado. A figura mostra o rendimento medido em estações de trabalho ligadas em Ethernet de acordo com o previsto pelas equações 3.3 e  3.11. Vemos que o modelo mais sofisticado é razoavelmente preciso.

Figura: 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.

---------------------------------------------------
$\bullet$ Exemplo 3.8 (Competição pela largura de banda em borboleta) Como um segundo exemplo consideramos um algoritmo em que $P$ tarefas usam uma estrutura de comunicação em borboleta (ou hipercubo) e a maior precisão do modelo de rendimento refinado ilustrado pela figura 2.14 para efectuar $\log P$ transferências de $N/P$ dados. O algoritmo de soma apresentado na secção 2.4.1 tem esta forma. Outros algoritmos com características similares são descritos no capítulo 11.

Os custos de comunicação por processador associados com este algoritmo são, na ausência de competição pela largura de banda,

$$T_{com ideal borboleta} = \log P \left ( t_s + t_w\frac{N}{P} \right).$$

O algoritmo pode, evidentemente, executar sem competição pela largura de banda num comutador por barra transversal. Talvez menos óbvio é que este pode também executar sem competição pela largura de banda num hipercubo de $P$-processadores: A computação e a comunicação podem ser organizadas de forma a que cada um dos $\log P$ processadores com os quais um processador tem de comunicar é um vizinho, numa das ligações do hipercubo. Numa rede por barramento, só um processador pode comunicar em cada momento; daí que, como no algoritmo de diferenças finitas considerado no exemplo 3.7, assumimos $S = P/2$ e da equação 3.10 temos

$$T_{com barramento em borboleta} = \log P \left ( t_s + t_w\frac{N}{2} \right).$$

Numa malha, o número limitado de fios torna-se uma questão. Por exemplo, numa malha 1-D de $P$ processadores, cada processador gera mensagens que deverão dar $1, 2, ..., 2^{p-1}$ pulos nos $p$ passos do algoritmo (fig 3.20). Estas mensagens dão um total de $P\sum_{i=0}^{p-1} 2^i = P(P-1)$ pulos. Isto representa o número de fios a que cada processador necessita de ter acesso exclusivo durante a execução da soma.

Figura: 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.

Como uma malha bi-direcccional a 1-D fornece apenas $2(P -1)$ fios, vemos que o algoritmo paralelo não pode possivelmente prosseguir em menos do que $P/2$ passos em vez dos $\log P$ passos previstos atrás.

Máquina	$T1$	$N$	$t_s$	$t_w$
Intel DELTA	$8.5 10^6$	$1.7 10^6$	200	0.6
RS/6000 & Ethernet	$4.4 10^6$	$1.7 10^6$	1500	5.0

Tabela: Parâmetros de rendimento no estudo do algoritmo em borboleta ($N$ em palavras, tempos em $\mu$seg).

Com efeito, este pode prosseguir em $P/2$ passos apenas se podermos definir um escalonamento da comunicação que mantenha sempre todos os fios ocupados. Assim, o modelo que segue representa o limite inferior dos custos de comunicação:

$$T_{1d malha com borboleta} \geq t_s \log P +t_w\frac{N}{2}.$$

A figura 3.21 compara os ganhos observados com os previstos pelos modelos de rendimento simples e de largura de banda limitada numa malha uni-dimensional e em Ethernet. Estes resultados foram tomados do código de modelação da atmosfera que usa a transformada de Fourier paralela (FFT) para paralelizar, um método numérico chamada de transformação espectral. Os pormenores do método numérico não são relevantes, aqui; o que é relevante é que em cada passo, o código deverá efectuar duas operações de comunicação em borboleta (especificamente FFT) numa lista de dados de grandes dimensões. Os detalhes dos dois experimentos são dados pelo quadro da tabela 3.6.(O termo $t_w$ usado pelo DELTA é significantemente mais pequeno, do que o código de diferenças finitas do exemplo 3.6; isto reflecte o facto de que o código de comunicação da realização da FFT no DELTA foi cuidadosamente optimizado.)

Figura: 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.

Entrada/Saída

Um factor determinante do rendimento em muitos programas paralelos é o tempo requerido para transferir os dados entre a memória principal e a secundária, isto é, o tempo requerido para a entrada/saída (E/S). As aplicações com requisitos substanciais de E/S de dados, incluem o seguinte:

• Pontos de Teste. Muitos dos cálculos realizados em computadores paralelos executam durante longos períodos. Pontos de teste periódicos do estado da computação são essenciais para reduzir o custo das falhas do sistema. Em grandes computadores paralelos o estado da computação pode ser muito grande (muitos Giga-bytes).
• Dados da Simulação. Simulações científicas e de engenharia que calculam, periodicamente, a evolução temporal de sistemas físicos e guardam o estado do sistema para análise ou visualização subsequente. Alguma simulações podem gerar enormes quantidades de dados - centenas de giga-bytes ou mais numa única corrida.
• Memória Insufuciente. Alguns programas têm de operar em estruturas de dados que são maiores do que a memória base disponível. Em princípio um sistema de memória virtual pode efectuar a necessária paginação de dados de/para o disco. Na prática, nem todos os computadores paralelos disponibilizam memória virtual. Mesmo quando isso acontece, o rendimento da aplicação pode ser muitas vezes melhorado por gestão explícita do movimento dos dados.
• Análise de Dados Muitas aplicações envolvem a análise de enormes quantidades de dados. Por exemplo, os dados de saída dos modelos de clima obtidos via satélite podem ser examinados para detectar ``eventos extremos'', tais como, valores elevados de temperatura, ou uma base de dados de transacções em cartões pode ter de ser examinada para detectar operações fraudulentas. Estas aplicações de análise de dados são muito exigentes, do ponto de vista da E/S de dados, porque é efectuada uma, relativamente, reduzida computação em cada um dos dados trazidos do disco.

É difícil fazer um discussão geral da E/S paralela porque os diferentes computadores paralelos têm arquitecturas radicalmente diferentes de E/S, e também diferentes mecanismos de E/S. Contudo, podemos estabelecer vários pontos que têm uma extensa aplicação.

Podemos muitas vezes ganhar um conhecimento razoável do custo de uma operação de E/S pensando nela como uma comunicação entre o processador que realiza a operação e um ou mais discos. O custo de uma operação E/S de disco pode ser aproximado por um custo de arranque e um custo de transferência por palavra, de forma muita idêntica à comunicação inter-processadores. (Contudo o tempo de estabelecimento é tipicamente mais elevado.) Tal como na comunicação inter-processadores, a chave para um bom rendimento está na maximização da utilização de percursos dispoestágios e a minimização dos tempos de arranque.

Se um computador tem um único disco ou se múltiplos discos estão ligados a apenas um processador, muito pouco pode ser feito para optimizar o rendimento da E/S. Contudo, na prática, a maior parte dos computadores paralelos dispõem de múltiplos percursos dos processadores para os discos, quer através da disponibilização de múltiplos ``nodos de E/S'', quer através da ligação directa dos discos aos processadores (figura  3.22). Nas arquitecturas deste tipo, procuramos organizar as operações de E/S de maneira a que múltiplos processadores leiam e escrevam simultaneamente, usando percursos múltiplos. Assim, as estratégias centralizadas de E/S que obrigam os dados a passar por um único processador dificilmente serão eficientes e são certamente não escaláveis.

A acrescentar à maximização da concorrência das operações de E/S, necessitamos de considerar o número de pedidos de leituras e de escritas distintos, necessários para transferir os dados entre a memória dos processador e o disco. Isto pode ter muitas vezes um impacto maior no rendimento da E/S do que a quantidade de dados transferidos. O número de pedidos de E/S depende, parcialmente, da forma como os dados estão distribuídos pelos discos e pela memória. A distribuição pela memória é determinada, presumivelmente, pela aplicação; a distribuição pelo disco, tanto pode ser da responsabilidade do programador, como ser seleccionada pelo sistema de gestão de ficheiros. Os dados podem, muitas vezes, estar dispersos pelos discos dispoestágios para reduzir a probabilidade de vários processadores tentarem ter acesso ao mesmo disco simultaneamente.

Se as distribuições pelo disco e pela memória diferem, então, um elevado número de leituras e escritas podem ser necessárias para realizar a transferência de dados. Este problema é análogo ao que acontece quando se transferem estruturas de dados entre dois componentes de um programa paralelo que requerem diferentes distribuições. Tal como será discutido no capítulo 4, nesta situação são possíveis pelo menos duas abordagens: podemos modificar um ou ambos os componentes para usar diferentes distribuições, ou podemos redistribuir os dados, explicitamente, antes ou durante a sua transferência. Como os pedidos de E/S tendem a ser mais onerosos do que a comunicação inter-processadores, é muitas vezes melhor efectuar uma distribuição explícita dos dados em memória para minimizar o número de pedidos de E/S. Isto conduz a uma estratégia de acesso em duas fases, em que as distribuições de dados usadas em memória e em discos são desemparelhadas. O mérito destas várias abordagens pode ser explorado analiticamente com modelos de rendimento.

Figura: Arquitectura de E/S de um computador paralelo idealizado. $P$ processadores estão ligados por múltiplos canais de E/S a $D$ discos.

Estudo de Casos: Algoritmos de Optimização de Percursos

Concluímos este capítulo usando modelos de rendimento para comparar quatro algoritmos paralelos diferentes para o problema de optimização de percursos para todos os pares. Este é um importante problema da teoria dos grafos com aplicação em comunicações, transportes e problemas electrónicos. É interessante porque a análise mostra que três dos quatro algoritmos podem ser óptimos em diferentes circunstâncias, dependendo do compromisso entre os custos de comunicação e de computação.

O problema da optimização de percursos envolve a procura do caminho mais curto entre todos os pares de vértices de um grafo. Um grafo $G = (V, E)$ compreende um conjunto $V$ de $N$ vértices, $\{v_i\}$ e um conjunto $E \subseteq V$x$V$ de arcos ligando vértices em $V$. Num grafo dirigido, cada ramo tem também uma direcção, de forma que os ramos $(v_i, v_j)$ e $(v_j, v_i)$, $i\not = j$, são distintos. Um grafo pode ser representado como uma matriz de adjacências $A$ para a qual cada elemento $(i, j)$ representa um ramo entre o elemento $i$ e o elemento $j$. $A_{ij} = 1$ se houver um ramo $(v_i, v_j)$; doutra forma, $A_{ij} = 0$ (Figura 3.23).

Um percurso do vértice $v_i$ para o vértice $v_j$ é uma sequência de ramos $v_i,v_k$, $v_k,v_l$, ... $v_m,v_j$ de $E$ para o qual nenhum dos vértices aparece mais do que uma vez. Por exemplo, $(1,3),(3,0)$ é um percurso do vértice $1$ para o vértice $0$ na figura 3.23. O percurso mais curto entre os dois vértices $v_i$ e $v_j$ de um grafo é o caminho que tem o número menor de ramos. O problema da optimização de percursos de origem simples requer que encontremos o percurso mais curto entre todos os pares de vértices de um grafo. Consideramos este problema e apresentamos quatro algoritmos paralelos diferentes, dois baseados num algoritmos sequencial devido a Floyd e os outros dois baseados num algoritmo sequencial devido a Dijkstra. Todos os quatro algoritmos tomam como entrada de dados uma matriz $A$ de adjacências $N$ x $N$ e calculam uma matriz $S$, $N$x$N$, sendo $S_{ij}$ o comprimento do percurso mais curto de $v_i$ para $v_j$, ou um valor $\infty$ se não existir caminho.

Figura: Um grafo directo simples, G, e a sua matriz de adjacências, A.

Algoritmo de Floyd

O algoritmo de Floyd para os caminhos mais curtos entre todos os pares é apresentado como o algoritmo 3.1. Calcula a matriz $S$ em $N$ passos, construindo em cada passo $k$ uma matriz intermédia $I(k)$ contendo a distância mais curta conhecida entre cada par de nodos. Para começar cada $I_{ij}(0)$ é iniciado com o comprimento do ramo $(v_i, v_j)$, se o ramo existir e com $\infty$ no caso contrário. O passo $k$ do algoritmo considera cada $I_{ij}$ à vez e determina se o melhor caminho conhecido de $v_i$ para $v_j$ é mais longo do que os comprimentos combinados dos melhores percursos conhecidos de $v_i$ para $v_k$ e de $v_k$ para $v_j$. Em caso afirmativo, a entrada $I_{ij}$ é actualizada para reflectir o percurso mais curto (figura 3.24).

procedimento floyd-sequencial


início

$I_{ij}(0) = 0$ se $i = j$

$I_{ij}(0) =$ comprimento $(( v_i, v_j))$ se  exitir ramo e $i\not = j$

$I_{ij}(0) = \infty$ senão


para  $k = 0$ até $N-1$


para $i = 0$ até $N-1$


para $j = 0$ até $N-1$ 

$I_{ij}(k+1)$ = min($I_{ij}(k), I_{ik}(k)+ I_{kj}(k)$)


arap


arap


arap

$S=I(N)$


fim

$\bullet$ Algoritmo 3.1 Algoritmo de Floyd para os caminhos mais curtos entre todos os pares.

Esta operação de comparação é efectuada um total de $N^3$ vezes; por isso, podemos aproximar o custo sequencial deste algoritmo a $t_cN^3$, sendo $t_c$ o custo de uma operação simples de comparação.

Figura: 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$.

Floyd Paralelo 1

O primeiro algoritmo paralelo Floyd é baseado numa decomposição uni-dimensional em linha por domínios, da matriz intermédia $I$ e da matriz de saída $S$. É de notar que isto quer dizer que o algoritmo pode usar no máximo $N$ processadores. Cada tarefa possui uma ou mais colunas adjacentes de $I$ e é responsável por efectuar calculos nessas colunas. Isto é, executa a seguinte operação.

para $k = 0$ até $N-1$


para $i =$ i-inicial até i-final


para $j = 0$ até $N-1$

$I_{ij}(k+1) =$ min$(I_{ij}(k), I_{ik}(k)+I_{kj}(k)$)


arap


arap


arap

No $k$ passo, cada tarefa requer, para além dos seus dados locais, os valores $I_{k1}, I_{k2}, ... I_{kN}$, isto é, a coluna $k$ de $I$ (Figura 3.25). Assim, especificamos que a tarefa com esta linha difunde para todas as outras tarefas. Esta comunicação pode ser efectuada usando uma estrutura em árvore em $\log P$ passos. Porque existem $N$ difusões e cada mensagem tem tamanho $N$, o custo é

$$T_{Floyd 1} = t_c\frac{N^3}{P}+N\log P(t_s+t_wN).$$ (3.12)

É de notar que cada tarefa serve como nodo raíz para pelo menos uma operação de difusão (assumindo $P\leq N$). Em vez de definir $P$ estruturas binárias em árvore, é suficiente ligar as $P$ tarefas usando uma estrutura em hipercubo (Capítulo 11), a qual tem a útil propriedade de permitir que cada nodo possa difundir para todos os outros nodos em $\log P$ passos.

Figura: 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$.

Floyd Paralelo 2

Uma versão alternativa do algoritmo de Floyd usa uma decomposição bi-dimensional de várias matrizes. Esta versão permite o uso de até $N^2$ processadores e exige que cada tarefa execute a seguinte lógica.

para $k = 0$ até $N-1$


para $i =$ i-inicial até i-final


para $j =$ j-inicial até j-final

$I_{ij}(k+1) =$ min$(I_{ij}(k), I_{ik}(k)+I_{kj}(k)$)


arap


arap


arap

Em cada um dos $N$ passos cada tarefa requer, a acrescentar aos seus dados locais, $N/\sqrt P$ valores de duas tarefas localizadas na mesma linha e coluna da lista bi-dimensional de tarefas (Figura  3.26). Assim, os requisitos de comunicação em cada passo $k$ podem ser estruturados como duas operações de difusão: de cada uma das tarefas por linha que possuem parte da coluna $k$ para todas as outras tarefas nessa linha, e de cada uma dada tarefas por coluna que possuem parte da linha $k$ para todas as outras tarefas nesa coluna.

Em cada um dos $N$ passos, $N/\sqrt P$ valores devem ser difundidos para as $\sqrt P$ tarefas em cada linha e coluna, sendo o custo total

$$T_{Floyd 2} = t_c\frac{N^3}{P}+2N\log \sqrt P\left(t_s+t_w\frac{N}{\sqrt P}\right)$$

$$= t_c\frac{N^3}{P}+N\log P\left(t_s+t_w\frac{N}{\sqrt P}\right).$$ (3.13)

É de notar que cada tarefa serve como nodo raíz durante pelo menos uma difusão para cada tarefa na mesma linha e coluna da lista 2-D de tarefas. Os requisitos de comunicação podem ser satisfeitos lignado tarefas na mesma linha ou coluna numa estrutura em hipercubo.

Figura: 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$.

Algoritmo de Dijkstra

O algoritmo de optimização de percursos por origem-simples de Dijkstra calcula todos os caminhos a partir de um vértice, $v_s$. Pode também ser usado para o problema de todos os pares de caminhos mais curtos, através do expediente simples de aplicá-lo $N$ vezes - uma vez a cada vértice $v_0, ...,v_{N-1}$.

O algoritmo sequencial de optimização de percursos por origem-simples de Dijkstra é dado no Algoritmo 3.2. Mantém um conjunto de vértices $T$ para o qual os caminhos mais curtos ainda não foram encontrados, sendo $d_i$ o caminho mais curto conhecido de $v_s$ para o vértice $v_i$. Inicialmente, $T = V$ e todos os $d_i =\infty$. Em cada passo do algoritmo, o vértice $v_m$ em $T$ com o valor mais pequeno $d$ é removido de $T$. Cada vizinho de $v_m$ em $T$ é examinado para ver se um caminho através de $v_m$ pode ser mais curto do que o melhor conhecido presentemente (Figura 3.27).

$\bullet$ Algoritmo 3.2 Algoritmo de optimização de percursos por origem-simples de Dijkstra.

procedimento dijkstra-sequencial

ínicio

$d_s = 0$

$d_i =\infty$, para $i\not =s$

$T = V$


para $i = 0$ até $N-1$


encontrar $V_m\in T$ com mínimo $d_m$


para cada ramo $(v_m, v_t)$ com $v_t \in T$


se $(d_t > d_m + L_{mt})$ então $d_t = d_m + L_{mt}$


arap

$T = T - v_m$


arap


fim

Um algoritmo todos-os-pares efectua $N$ vezes o Algoritmo 3.2 uma vez para cada vértice. Isto envolve $\cal {O} (N^3)$ comparações e demora o tempo $N^3t_cF$, sendo $t_c$ o custo de uma comparação simples no algoritmo de Floyd e $F$ uma constante. Estudos empíricos mostram que $F\approx1.6$; isto é, o algoritmo de Dijkstra é ligeiramente mais dispendioso do que o algoritmo de Floyd.

Figura: 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$.

Dijkstra Paralelo 1

O primeiro algoritmo paralelo de Dijkstra replica o grafo em cada uma das $P$ tarefas. Cada tarefa executa o algoritmo sequencial para $N/P$ vértices. Este algoritmo não requer comunicação mas pode usar no máximo $N$ processadores. Porque o algoritmo sequencial de Dijkstra é $1.6$ vezes mais lento do que o algoritmo sequencial de Floyd, a execução do algoritmo é

$$T_{Dijkstra 1} = t_cF\frac{N^3}{P}.$$

Dijkstra Paralelo 2

O segundo algoritmo paralelo de Dijkstra é usado quando $P>N$. Defimos $N$ conjuntos de $P/N$ tarefas. A cada conjunto de tarefas é dado o grafo completo e é responsável pelo cálculo de caminho mais curto para um único vértice (Figura 3.28. Dentro de cada um dos conjuntos de tarefas, s vértices do grafo são particionados. Assim, a operação

Encontrar $v_m \in T$ com $d_m$ mínimo
requer em primeiro lugar uma computação local para encontrar o vértice local com $d$ mínimo e em segundo lugar uma operação de redução envolvendo todas os $P/N$ tarefas no mesmo conjunto de forma a determinar o $d_m$ mínimo global. A redução pode ser obtida usando a estrutura de comunicação em borboleta da secção 2.4.1, em $\log P/N$ passos. Assim, uma vez que a redução é efectuada $N$ vezes e involve dois valores, o custo total do algoritmo é

$$T_{Dijkstra 2} = t_cF\frac{N^3}{P} + N\log\frac{P}{N} (t_s +2t_w).$$

Figura: 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.

Resumo dos algoritmos de optimização de percursos

A tabela 3.7 resume os modelos de rendimento desenvolvidos para os quatro algoritmos, do camiho mais curto para todos-os-pares. Claramente, o Floyd 2 será sempre mais efeciente do que o Floyd 1. Ambos os algoritmos têm os mesmo custos de computacão e enviam o mesmo número de mensagens, mas o Floyd 2 comunica um volume consideravelmente inferior de dados. Por outro lado, o Floyd 1 é mais fácil de implementar. Os algoritmos de Dijkstra 1 e 2 serão mais eficientes do que o Floyd 2 em certas circunstâncias. Por exemplo, Dijkstra 1 é mais eficiente que Floyd 2 se $P\leq N$ e

$$t_c(F -1)\frac{N^3}{P}>t_sN\log P + t_wN^2\frac{\log P}{\sqrt P}.$$

A juntar a estes factores devemos considerar o facto de que os algoritmos de Dijkstra 1 e 2 replicam o grafo $P$ e $P/N$ vezes, respectivamente. Esta replicação pode comprometer a escalabilidade destes algoritmos. Também, o custo de replicar um grafo originalmente distribuído deve ser considerado se (presumivelmente) o algoritmo de optimização de percursos fizer parte de um programa mais vasto no qual o grafo é representado como uma estrutura de dados distribuída.

Claramente, a escolha do algoritmo de optimização de percursos para um problema particular envolve compromissos complexos entre a flexibilidade, escalabilidade, rendimento e a complexidade da implementação. Os modelos de rendimento desenvolvidos neste caso de estudo fornecem uma base para avaliação dos compromissos.

Algoritmo	$t_c$	$t_s$	$t_w$	Máximo $P$
Floyd 1	$N^3/P$	$N\log P$	$N^2\log P$	$N$
Floyd 2	$N^3/P$	$N\log P$	$N^2\log P/\sqrt P$	$N^2$
Dijkstra 1	$N^3F/P$	0	0	$N$
Dijkstra 2	$N^3F/P$	$N\log(P/N)$	$2N\log(P/N)$	$N^2$

Tabela: Rendimento dos quatro algoritmos de optimização de percursos.

Sumário

Neste capítulo vimos como desenvolver modelos matemáticos de rendimento que caracterizam o tempo de execução, a eficiência e a escalabilidade de um algoritmo paralelo em termos de parâmetros simples tais como o tamanho do problema, o número de processadores e os parâmetros de comunicação. Vimos, também, como estes modelos podem ser usados durante as fases de desenho e de realização.

• Na fase inicial de desenho, caracterizamos os requisitos de computação e comunicação dos nossos algoritmos paralelos, construindo modelos simples de rendimento. Estes modelos podem ser usados para escolher entre algoritmos alternativos, para delimitar áreas de problemáticas do desenho e para verificar se os algoritmo atingem os requisitos de rendimento.
• Mais tarde, no processo de desenho, refinamos os nossos modelos de rendimento e efectuamos experiência simples para determinar parâmetros desconhecidos (tais como o tempo de computação ou os custos de comunicação) ou validar pressupostos. Os modelos refinados podem ser usados para aumentar a nossa confiança na qualidade do desenho antes da realização.
• Durante a realização comparamos o rendimento do programa paralelo com o seu modelo de rendimento. Procedendo desta forma pode ajudar a identificar os erros da realização e a melhorar a qualidade do modelo.

Um modelo de rendimento dá informação sobre um aspecto do desenho de um algoritmo: o seu rendimento paralelo esperado. Podemos usar esta informação, quando é combinada com estimativas de custo de realização, etc., para fazer escolhas informadas entre alternativas de desenho.

Junção de Componentes

Em capítulos anteriores, centramo-nos no problema de desenvolver algoritmos paralelos eficientes para componentes individuais de programas, tais como a pesquisa e o cálculo de diferenças finitas. No entanto, os programas completos podem incorporar múltiplos algoritmos paralelos, cada um dos quais pode operar em diferentes estruturas de dados e estabelecer diferentes partições, comunicações ou estratégias de arranjo que permitam atingir uma execução eficiente.

A experiência mostra que a complexidade associada à construção de programas de grande dimensão pode ser controlada pela aplicação de técnicas de desenho modular. A ideia chave é encapsular a complexidade ou os aspectos variáveis do desenho em componentes separados, ou módulos , com interfaces bem definidos que indiquem os modos de interacção como o ambiente. Desenvolvem-se os programas completos encaixando os vários módulos ou compondo esses módulos. O desenho modular pode aumentar a fiabilidade e reduzir os custos porque torna mais fácil a construção de programas, a sua adaptação à alteração de requisitos e a reutilização de de componentes em novos programas.

O objectivo deste capítulo é introduzir alguns das questões de desenho que surgem quando se desenvolvem grandes programas paralelos.

Desenho Modular Revisitado

A ideia básica de suporte ao desenho modular é organizar um sistema complexo (circuito electrónico, dispositivo mecânico, programa complexo) como um conjunto de componentes distintos que podem ser desenvolvidos separadamente que são depois ligados em conjunto. Apesar de parecer uma ideia simples, a experiência tem mostrado que a efectividade desta técnica depende de forma crítica na maneira de dividir um sistema em componentes e dos mecanismos usados para os encaixar. Os princípios que a seguir se enunciam são particularmente relevantes para a programação paralela.

Interfaces Simples

Interfaces simples reduzem o número de interacções que devem ser considerados quando se pretende verificar que um sistema realiza as funções pretendidas, facilitando a reutilização dos componentes em diferentes circunstâncias. A reutilização reduz os factores de custo não só porque diminui o tempo dedicado ao desenho, codificação e teste, mas também porque permite amortizar o custo espalhando-o por vários projectos. Numerosos estudos têm demonstrados que a reutilização é de longe a técnica mais efectiva que pode ser usada para diminuir os custos de desenvolvimento.

Como exemplo, a realização de sistema de modelação das condições climatéricas fig. 2.3 pode assentar em módulos distintos para a atmosfera, para os oceanos, etc. Os interfaces de cada módulo podem compreender um pequeno conjunto de procedimentos que acedem dados limítrofes, fazem avançar a simulação etc. Assim, não é necessário ao utilizador familiarizar-se com a realização dos vários módulos que no seu conjunto podem perfazer centenas de procedimentos e dezenas de milhares de linhas de código.

Assegurar que os Módulos Encobrem Informação

As vantagens da modularidade não decorrem automaticamente da divisão de um programa. A forma como um programa é decomposto pode ser decisiva na possibilidade de um programa ser realizado e modificado. A experiência tem mostrado que cada módulo deverá encapsular informação que não seja acessível ao resto do programa. Esta ocultação de informação reduz o custo das alterações subsequentes do desenho. Por exemplo, um módulo pode encapsular:

• funções relacionáveis que tiram proveito de uma realização comum ou que são usadas em muitas partes do sistema,
• funcionalidades passíveis de ser modificadas em desenhos posteriores ou em caso de desdobramento,
• aspectos de um problema que são particularmente complexos e/ou
• código que se espera poder reutilizar noutros programas.

Convém notar que não se diz que um módulo deverá conter funções que são logicamente relacionadas porque, por exemplo, elas resolvem a mesma parte de um problema. Este tipo de decomposição não facilita, normalmente a manutenção ou promove a reutilização de código.

Uso de Ferramentas Apropriadas

Enquanto que o desenho modular pode em princípio ser feito em qualquer linguagem de programação, a realização é mais fácil se a linguagem suportar a ocultação de informação permitindo o encapsulamento do código e das estruturas de dados. Os mecanismo fundamentais a que deveremos prestar atenção incluem: para encapsulamento de código; o procedimento ( subrotinas ou função) com variáveis e lista de argumentos de extensão local, para encapsulamento de dados; os tipo de dados definíveis pelo utilizador. A alocação dinâmica de memória está também incluída para dotar os subprogramas da possibilidade de requerer espaço de memória sem envolvimento directo do programa. Estas particularidades são disponibilizadas pelo maior parte das linguagens modernas ( C++, Ada etc..)! o que não é verdade para outras linguagens mais antigas (Fortran 77).

Lista de Teste do Desenho

Cada questão deverá ser respondida afirmativamente.

1. O desenho identifica claramente os módulos definidos?
2. Todos os módulos têm objectivos precisos? (É possível descrevê-los sucintamente?)
3. os interfaces de cada módulo são suficientemente abstractos para não ser necessário pensar na realização par poder compreende-los? Cada módulo oculta os detalhes de realização dos outros módulos?
4. o nível de subdivisão dos módulos é tão profunda quanto possível?
5. Verifica-se que entre os vários módulos não há replicação de funcionalidade?
6. Os aspectos de desenho mais dependentes do hardware, mais complexos ou mais susceptíveis de de modificação, estão identificados e isolados?

Modularidade e Computação Paralela

Os princípios de desenho revistos anteriormente aplicam-se directamente à programação paralela. Contudo, o paralelismo também introduz preocupações adicionais. Um módulo sequencial encapsula o código que realiza as funções disponível através do interface e das estruturas de dados a que essas funções acedem. Em Programação Paralela, é preciso considerar não apenas o código e os dados mas também as tarefas criadas por um módulo, a forma como as estruturas de dados são particionadas e entregues aos processadores e as estruturas de comunicação internas. A distribuição dos dados é provavelmente o tópico mais importante.

Uma outra diferença entre programação sequencial e paralela, é que na primeira os módulos podem ser compostos de uma forma única: sequencial. A execução de um programa conduz a uma sequência de chamadas a funções definidas em módulos diferentes. Esta abordagem composição sequencial também pode ser usada em programação paralela, sendo fundamental no modelo de programação SPMD, usado em muitos programas paralelos. Contudo, precisam-se, muitas vezes, compôr os componente de um programa de outras formas (fig. 4.1). Em composição paralela, os diferentes módulos correm concorrentemente nos em conjuntos disjuntos de processadores. Esta estratégia pode enriquecer a modularidade e melhorar a escalabilidade e a localidade. Em composição concorrente os diferentes módulos executam concorrentemente nos mesmos processadores, sendo a execução de um módulo, particular, autorizada pela existência de dados. Esta forma de composição concorrente podem ambas reduzir a complexidade do desenho e permitindo sobrepôr computação e comunicação.

É possível distinguir entre sequencial, paralelo e composição concorrente porque são formas distintas de pensar nos programas e porque nem todas as ferramentas de programação paralela contemplam as três formas composicionais. As linguagens de paralelismo nos dados ( tais como HPF) tendem para contemplar apenas a composição sequencial. As bibliotecas de passagem de mensagens ( tais como o MPI) contemplam tanto a composição sequencial como a paralela mas não permitem composição concorrente. Outras linguagens e bibliotecas ( CC++ e Fortran M) contemplam as três formas de composição.

Distribuição de Dados

Na discussão anterior mostrou-se que a distribuição das estruturas de dados entre tarefas e processadores ( i.e. a forma como as estruturas de dados são divididas e atribuídas aos processadores) é um aspecto importante no desenho de algoritmos paralelos. Também se mostrou como conceber a partição de dados de forma a maximizar o rendimento e/ou minimizar os custos de desenvolvimento do software.

A distribuição de dados pode tornar-se um tópico mais complexo num +programa construído a partir de vários componentes. A escolha simples de uma distribuição óptima para cada componente pode resultar em diferentes módulos que usam diferentes distribuições de dados. Por exemplo, um módulo pode produzir um estrutura de dados vectorial distribuída por colunas, enquanto que outro módulo espera por uma entrada de dados distribuídos por linhas. Quando se compõem os dois módulos um dos módulos tem que ser modificado, caso contrário os dados terão de ser explicitamente redistribuídos na passagem de um módulo para o outro. As diferentes soluções podem ter características e custos de rendimento diferenciados.

Tanto a afinação do rendimento como a reutilização de programas é facilitada se os módulos forem concebidos de forma a serem neutros na distribuição de dados, isto é, se podem adaptar-se a diferentes distribuições de dados. Pode atingir-se esta neutralidade se a distribuição de uma determinada estrutura for especificada como um parâmetro de execução ou da própria estrutura. Por exemplo, os dois módulos anteriormente referidos podem ser definidos de forma a adaptarem-se com uma decomposição bidimensional arbitrária. O programa resultante pode assim usar uma decomposição em linhas ou em colunas, ou em última instância, uma decomposição bidimensional.

A concepção de um módulo como neutro na distribuição de dados não é necessariamente fácil. Nalguns casos distribuições diferentes de dados podem obrigar a diferentes.

Composição Sequencial

Num programa paralelo construído usando apenas composição sequencial, cada processador executa inevitavelmente o mesmo programa, que por sua vez realiza uma série de chamadas a diferentes componentes do programa. Estes componentes podem por sua vez comunicar e sincronizar mas não podem criar novas tarefas. Assim, a computação na sua totalidade desloca-se sequencialmente de uma para outra operação sequencial.

Como um exemplo, considere-se o seguinte programa, que pode ser executado por cada uma das tarefas num programa S*MD de diferenças finitas.

while (not done) do
finite_difference(localgrid, localmax)
global_maximum(localmax, globmax)
if(globmax < threshold) done = true
enddo
Este programa é estruturado como uma composição sequencial de duas chamadas de procedimentos e uma instrução sequencial. Em cada passo, cada tarefa começa por evocar o procedimento finite_difference para fazer avan'ar a simulação. Esta evocação actualiza localgrid e retorna um valor estimado do erro localmax. Seguidamente, cada tarefa evoca global_maximum para obter o valor global máximo do erro que será usado para determinar se a simulação converge. Num computador paralelo, tanto a rotina finite_difference como a global_maximum têm de comunicar ( para transferir os dados necessários pelo stencil de diferença finita e calcular o máximo global), mas esta actividade é ocultado do resto do programa.

Este exemplo ilustra uma importante vantagem da composição sequencial e do modelo SPMD: o programa executado por cada processo tem uma leitura mais directa e limpa, e muitas técnicas de programação sequencial podem ser usadas indiferenciadamente. Por exemplo, os procedimentos finite_differences e global_maximum podem ser definidos em grelhas separadas e módulos reduzidos, cada um dos quais pode encapsular estruturas internas de dados ( e estruturas de comunicações).

Uma segunda vantagem da composição sequencial é que se módulos diferentes usarem a mesma distribuição de dados, não é necessário transferência de dados ( isto é comunicação) para o interface dos dados. Por exemplo, a estrutura ao nível superior de um sistema de modelação de clima pode ser da seguinte forma. Os procedimentos dos módulos oceano e atmosfera são evocados repetidamente de forma intervalada, como os dados gerados pelo módulo oceano sendo transferidos para o módulo atmosfera e vice-versa. A comunicação é precisa apenas dentro dos dois componentes

initialize_ocn(ocn_grid)
initialize_atm(atm_grid)
while(not done) do
ocean(atm_grid, ocn_grid)
atmosphere(ocn_grid, atm_grid, done)
enddo

Tal como se mostra neste exemplos uma biblioteca desenhad para ser usada num ambiente de programação SPMD pode utilizar um interface quase idêntico ao que é usado numa biblioteca sequencial comparável. A preocupação principal é que as rotinas da biblioteca sejam capazes de tratar com uma variedade de distribuições de dados ( distribuição neutra de dados) e que os detalhes da realização paralela tais como as estruturas de dados e as operações de comunicação sejam ocultadas do interface. A simplicidade da composição sequencial e da programação SPMD tem vindo a estimular alguns dos maiores projectos de desenvolvimento de bibliotecas. Um, exemplo, que pode ser apresentado para ilustrar a forma coma a distribuição neutra de dados é definida é o ScaLAPACK, uma versão da popular biblioteca de álgebra linear LAPACK concebida para executar em computadores paralelos escaláveis. O ScaLAPCK contempla uma vasta gama de operações em matrizes ''dense'' e ``bande'' tais como multiplicação, transposta e factorização. As rotinas operam em objectos de dados que representam matrizes bidimensionais decompostas usando uma distribuição em blocos,cíclica.

A distribuição de um vector é especificada por quatro parâmetros, $P$, $Q$, $r$ e $c$ onde $P$ e $Q$ são o número de processadores e $r$ e $c$ o tamanho do bloco em cada dimensão fig 4.2. Em princípio, toda a rotina pode ser evocada com qualquer valor para os parâmetros, de forma a que programador possa experimentar distribuições de dados alternativas por simples modificação do parâmetros de evocação do programa. Esta abordagem fornece um elevado nível de independência no arranjo, de forma que faz lembrar as directivas de distribuição de dados empregues na linguagem (HPF). Na prática, certas limitações são colocadas nos valores permitidas para os parâmetros para simplificar o software. Por exemplo, a rotina d factorização TU precisa que os blocos sejam quadrados. Internamente, as rotinas ScaLAPACK podem incorporar múltiplos algoritmos paralelos que seleccionam entre esses algoritmos os que se baseiam na distribuição, no tamanho do problema e no tamanho da máquina. Contudo, esses detalhes são ocultados do utilizador.

Não é todavia de estranhar que a composição sequencial tenha também limitações como técnica de programação estruturada para os programas paralelos.

Composição Paralela

A composição paralela pode ser vista como uma generalização do modelo de programação SPMD em que diferentes partes de um computador executam diferentes programas. Pode também ser pensada como um caso especial de composição concorrente em que a que as tarefas que executam concorrentemente têm de ser executadas em conjuntos disjuntos de processadores. Uma composição paralela especifica quais os componentes a executar em que parte do computador e de que forma os componentes vão trocar dados.

Em princípio, qualquer programa descrito como uma composição paralela pode ser convertido numa composição sequencial que intervala a execução dos vários componentes do programa de forma apropriada. Contudo, o uso da composição paralela pode enriquecer a escalabilidade e a localidade. Por exemplo, se dois componentes de um programa ( atmosfera e oceano ) podem executar concorrentemente, então o seu localização em conjunto disjuntos processadores aumenta a escalabilidade promovendo oportunidades adicionais para a execução paralela. Se a localidade aumenta com a granularidade então esta composição paralela pode fazer também uso mais eficiente da cache, memória e da largura de banda das comunicações, do que pode ser obtido pela composição sequencial. A composição paralela pode também reduzir os requisitos totais de memória pela redução da quantidade de código e de dados replicados em cada processador.

Composição Concorrente

A composição concorrente é a mais geral das formas de composição consideradas. São especificados os componentes do programa que deverão ser executados concorrentemente numa relação produtor/consumidor e o arranjo de processadores pelos componentes. Os componentes executam conduzido pelos dados, em função da disponibilidade dos dados nos outros componentes. Estas ideias correspondem ao modelo de programação tarefa/canal em que a composição concorrente especifica um conjunto de tarefas e um conjunto de canais que ligam essas tarefas e o arranjo de tarefas pelos processadores.

A composição concorrente tem vantagens e desvantagens em relação aos outros modos de composição. Um importante vantagem é que desta forma se facilita a ocultação de informação e dessa forma o desenvolvimento de programas modulares. Isto porque o interface neste modo de composição consiste inteiramente de canais que ligam os vários componentes. Os detalhes de realização internos que dizem respeito ao código, às estruturas de dados, à concorrência e à comunicação estão escondidos. Desta forma os componentes podem ser desenvolvidos separadamente mesmo quando são executados em diferentes processadores.

A composição concorrente pode também simplificar o desenho permitindo que as decisões sobre o arranjo e o escalonamento sejam prorrogadas ou até evitadas. Porque a semântica do programa especificado pela composição concorrente é independente da forma como os componentes são distribuídos pelos processadores, as decisões de arranjo podem ser prorrogadas até à fase final do desenho. No que diz respeito ao escalonamento como a execução é determinada pela disponibilização dos dados a ordem de execução não necessita de ser especificada pelo programador.

Uma desvantagem da composição concorrente, em alguns ambientes, é o custo de um modelo de execução conduzido pelos dados. Apesar de tanto os compiladores como os sistemas em tempo de execução poderem reduzir drasticamente os custos inerentes à comutação entre tarefas, estes custos podem ser significativos se as tarefas comutarem frequentemente.

Regras de Desenho

Apresentam-se seguidamente um conjunto de regras que podem ser usadas para determinar como compôr módulos e os tipos de interface a desenhar.

1. Conceber módulos que manuseiem múltipla distribuições de dados. Esta característica pode aumentar a reutilização.
2. Incorporar informação sobre a distribuição de dados na estruturas de dados e não nos interfaces. Esta abordagem simplifica os interfaces e maximiza as oportunidades para reutilização de código.
3. Usar composição sequencial quando se desenha para um sistema de programação SPMD tal como é o caso do HPF e do MPI.
4. Considerar a composição sequencial quando: os componentes dos programas não poderem executar concorrentemente ou necessitarem de partilhar muitos dados.
5. Considerar a composição concorrente se os componentes de um programa poderem executar concorrentemente, os custos de comunicação forem elevados e for possível sobrepôr comunicação com computação.
6. considerar a composição paralela se a memória tiver um valor superior ao normal, ou se os custos de comunicação intracomponentes forem superiores aos custos de comunicação intercomponentes.

Análise de Rendimento

Quando se compõem componentes para construir um programa é necessário também considerar como se deverá fazer a composição dos seus modelos de rendimento. Por exemplo, considere-se um programa que combina dois componentes $a$ e $b$ com modelos de rendimento como os seguintes:

$$T^a=T^a_{comp} + T^a_{comp} + T^a_{ócio} T^b=T^b_{comp} + T^b_{comp} + T^b_{ócio}$$

No caso da composição sequencial $a$ e $b$ não têm necessidade redistribuição de dados, pelo que o modelo de rendimento do programa resultante pode ser obtido somando ambos os componentes:

$$T^{a+b} = T^a + T^b$$

Na prática a análise de rendimento construída com base em múltiplos módulos é muitas vezes complicada por uma série de factores que felizmente podem ser acauteladas usando as técnicas de modelação anteriormente apresentadas.

aumento da computação A transferência de dados entre módulos pode precisar de computação o que irá aumentar os custos totais de computação. Menos frequentemente a junção de dois módulos pode permitir a redução dos custos de computação porque podem ser eliminadas operações que seriam comuns aos dois componentes.

redução do tempo de ócio O tempo de ócio pode ser reduzido na composição concorrente se a computação e a comunicação poder prosseguir noutros módulos que partilham o mesmo processador. aumento de comunicação A composição obriga muitas vezes a mais comunicação. em composição sequencial, pode ser necessário comunicação para redistribuir estruturas de dados pelos componentes. Em composição paralela é necessário comunicação para transferir dados entre os módulos que correm em diferentes processadores. aumento de granularidade A composição paralela tende a aumentar a granularidade da computação e da comunicação porque cada um executa dentro de um subconjunto dos processadores disponíveis. Este efeito pode aumentar o rendimento global.

Desiquilíbrio de Carga A composição paralela tende a aumentar o tempo de ócio se os recursos de computação atribuídos aos diferentes componentes não permitirem as mesmas velocidades de execução. Nesta situação um módulo irá completar uma qualquer fase de uma computação antes que um outro componente devendo manter em repouso até que o outro módulo forneça os dados necessários para que aquele continue a execução.

Sumário

As técnicas de desenho modular são fundamentais para uma boa prática da engenharia de software. Seguem os pontos principais.

1. Os dogmas principais do desenho modular, tais como interfaces simples e ocultação de informação, aplicam-se à programação paralela de forma semelhante à usada na programação sequencial.
2. A distribuição de dados é um importante detalhe de realização que se poder ser abstraído do interface do módulo pode facilitar a reutilização de código. É útil a distinção entre composição sequencial, paralela e concorrente de módulos paralelos. A primeira é simples mas inflexível. A segunda pode ser usada para aumentar a escalabilidade e a localidade. A última é a forma mais geral.
3. Os modelos de rendimento podem ser compostos, mas é preciso ter muito cuidado quando se contabilizam os custos de comunicação ao nível do interface, a sobreposição de comunicação e da computação e outros factores.