Processadores Para o Próximo Milênio - Parte 2

Introdução

Na primeira parte deste artigo abordamos alguns tópicos da história dos computadores. Continuando, vamos estudar os conceitos propostos por um dos nomes que apareceu neste histórico e, em seguida, abordaremos os principais tópicos sobre processamento paralelo.

Postulados de von Neumann

Von Neumann[1], que trabalhou no desenvolvimento do ENIAC e posteriormente empregou sua experiência no projeto do IAS (1952), elaborou as idéias e os conceitos que nortearam a arquitetura dos computadores até os dias de hoje. Seu entendimento é essencial para apreciarmos a atual evolução dos computadores. Iniciemos constatando, de forma óbvia, que as máquinas que usamos nas nossas casas possuem quatro elementos básicos: a CPU, a memória, os dados e as instruções (ou programas). A partir daí, apresentamos os três postulados básicos de von Neumann, que no momento podem parecer triviais, mas que não o eram na década de 50:

1. Um único controle centralizado (uma só CPU);
2. Uma única memória para dados e instruções; e
3. As instruções devem fazer operações elementares sobre os dados.

Cerca de 90% dos computadores atuais usam esses postulados e por isso são chamados de “Arquitetura de von Neumann”, ou “Arquitetura Serial”, pois empregam um único processador. Essa arquitetura, aliada aos avanços da microeletrônica, ofertou-nos o atual mercado de computadores, rápidos e baratos. Porém, tal arquitetura enfrenta um limite de velocidade que é ditado pelas leis da física. O tempo que um sinal elétrico gasta para trafegar entre dois pontos de um circuito eletrônico é muito pequeno, porém não é igual a zero. Em outras palavras, isto corresponde a dizer que existe um limite para a velocidade de relógio das CPUs e, infelizmente, ele não está muito distante. Como então continuar com a evolução dos computadores? Essa é a pergunta que tem ocupado a cabeça de muitos pesquisadores e desde a segunda metade desta década, várias soluções foram propostas.

A principal resposta vem da comparação entre nosso cérebro e um processador. É sabido que o sinal elétrico trafegando por dentro de um CI é muito mais veloz que o trânsito de impulsos nervosos entre nossos neurônios. É claro que, para fazer operações numéricas, comparar e classificar, o computador é mais rápido. Mas, por outro lado, ele é inferior, pois não pensa, não inova e não aprende, apenas segue passos programados. Por exemplo, com um único olhar em uma sala identificamos imediatamente centenas de objetos. Já um computador, mesmo o mais sofisticado, apenas consegue identificar os objetos mais simples.

Somos capazes de dirigir um carro e enquanto andamos por nossas (terríveis) estradas, temos habilidade para escolher o melhor caminho. Será que um computador pode dirigir um carro? Uma das experiências no MIT com um piloto computadorizado, que identificava a rua através das linhas paralelas do meio fio, revelou um grande escalador de árvores, pois ele confundia o contorno do meio fio com o contorno do caule das árvores.

Como será que o cérebro consegue ser superior aos processadores, se o nosso neurônio é muito mais lento que um circuito eletrônico? A resposta é óbvia: porque temos vários bilhões de neurônios operando em paralelo. Ora, por que, ao invés de construirmos CPUs velozes e gigantescas, não usamos várias CPUs, simples e confiáveis, operando em paralelo? Chegamos assim à idéia básica do processamento paralelo, que é a esperança para o próximo milênio

Processamento Paralelo

Sabemos então que devemos usar uma grande quantidade de processadores, mas como controlá-los de forma a que façam alguma coisa de útil? Existem grandes problemas! Para iniciar, vamos trabalhar o conceito de processamento paralelo através de um exemplo bem simples. Se um pedreiro constrói uma casa em um ano, então dois pedreiros constróem a mesma casa em meio ano. Este é conceito básico do processamento paralelo: a divisão das tarefas. Podemos seguir adiante e concluir que cem pedreiros gastam apenas 3,6 dias. Será isto um absurdo?

É claro que há um limite, pois o trabalho dos pedreiros só será eficiente se estiverem perfeitamente sincronizados e equilibrados. Este ponto é importante: todos os pedreiros devem ter a mesma carga de trabalho. Em termos técnicos, usa-se a expressão “Balanceamento da Carga de Trabalho”. Esse balanceamento pode ser feito de dois modos. No primeiro modo, o trabalho de cada pedreiro é idêntico, ou seja, cada um faz 1/100 da casa. No outro modo é usado a especialização, ou seja, alguns pedreiros “viram” cimento enquanto outros assentam tijolos e outros tratam do encanamento, e assim por diante.

Ao imaginarmos todas as tarefas que devam ser executadas para a construção da casa, fica claro que algumas delas não poderão ser paralelizadas. Imagine 100 pedreiros para assentar um porta, ou 100 pedreiros em cima da casa tentando montar o telhado. A casa acabaria por cair! Além disso, deve haver um limite para a quantidade de pedreiros que podem trabalhar em paralelo. A partir deste limite, quanto mais pedreiros colocamos, pioramos o desempenho e em conseqüência, aumentamos o tempo de construção.

Temos então dois grandes problemas: até quanto podemos paralelizar uma tarefa e até quantos processadores devem ser alocados? A partir daí, surgem outras questões: como sincronizar esses processadores de forma a que um não repita o trabalho do outro e como garantir o balanceamento da carga de trabalho? Agora temos condições de entender porque se diz que as dificuldades presentes no projeto do hardware de máquinas paralelas não são tão complexas quando comparados com os problemas de sua programação. Diz-se que os computadores estão sempre uma geração atrasada em relação às nossas necessidades e os programas, duas gerações atrasadas. Em suma, um desafio maior que o projeto de supercomputadores é a sua programação.

Classificação de Computadores Paralelos

É muito difícil a tarefa de classificar computadores paralelos. Já foram feitas diversas sugestões. A classificação definitiva ainda está por vir. Porém, a que trouxe melhores resultados e ainda hoje é usada, é a proposta por Flynn[2]. Essa classificação está baseada em dois conceitos: fluxo de instruções e fluxo de dados. O fluxo de instruções está relacionado com o programa que o processador executa, enquanto que o fluxo de dados está relacionado com os operandos manipulados por essas instruções. O fluxo de instruções e o fluxo de dados são considerados independentes e por isso existem quatro combinações possíveis, como mostrado na Figura 1.

Figura 1: Fluxo de instruções e dados.

Nas Figuras 2 a 5 apresentamos os diagramas de blocos para essas 4 combinações. Nessas figuras, a sigla MM representa o “Módulo de Memória” e a sigla EP representa o “Elemento de Processamento”, ou seja, o processador. Essas quatro arquiteturas serão detalhadas a seguir.

Figura 2: Arquitetura SISD (Single Instruction Single Data).

Figura 3: Aquitetura SIMD (Single Instruction Multiple Data).

Figura 4: Arquitetura MISD (Multiple Instruction Single Data).

Figura 5: Arquitetura MIMD (Multiple Instruction Multiple Data).

SISD - Instrução Única, Dado Único (Single Instruction Single Data)

Essa arquitetura é usada nos computadores que temos em casa. Segue o proposto por von Neumann e é por isso denominada de “Arquitetura de von Neumann”, também chamado de computador serial. Temos um único fluxo de instruções (SI), caracterizado pelo contador de programa da CPU, que opera sobre um único dado (SD) por vez. A Figura 2 apresenta um diagrama de blocos ilustrativo deste caso. Apesar de serem representados como módulos separados, a memória de instruções e a memória de dados são, para este caso, a mesma.

SIMD - Única Instrução, Múltiplos Dados (Single Instruction Multiple Data)

De início esta arquitetura paralela pode parecer estranha, mas como será constatado adiante, ela não só é conhecida, como também já foi muito utilizada. Para facilitar o conceito de um computador que utilize uma única instrução operando sobre uma grande quantidade de dados, devemos consultar o diagrama da Figura 3.

A arquitetura mostrada apresenta N processadores (EP), sendo que cada processador trabalha sobre um dado distinto, que vem de cada um dos N módulos de memória (MD). O ponto importante é que todos os processadores (EPi) trabalham sincronizados e executam todos a mesma instrução, ou seja, cada instrução é passada, ao mesmo tempo, para os N EPs. Assim, os processadores executam a mesma instrução, porém sobre um dado diferente. Como é fácil de concluir, um computador com essa arquitetura é capaz de operar um vetor de dados por vez. Vem daí seu nome de Computador Vetorial, ou “Array Processor”.

Um grande exemplo desta arquitetura são os famosos computadores Cray. Outro exemplo é o conjunto de instruções MMX. Eles são muito usados quando um mesmo programa deve ser executado sobre uma grande massa de dados, como é o caso de prospeção de petróleo. Note que essa arquitetura não sofre com problemas de sincronização, pois existe um único programa em execução.

MISD - Múltiplas Instruções, Dado Único (Multiple Instruction Single Data)

Essa arquitetura é um pouco mais difícil de ser explicada. Tentemos imaginar como é que se pode fazer múltiplas operações (MI) sobre um mesmo dado (SD). Os próprios pesquisadores têm opiniões divergentes sobre esse assunto. Entretanto, não vamos entrar nesses debates teóricos. De forma simples, vamos estudar a Figura 4, onde pode ser visto que, apesar de existir um único fluxo de dados, existem vários dados sendo operados ao mesmo tempo. Essa figura é conhecida na literatura especializada com o nome de “pipeline” ou linha de produção.

A figura mostra que N processadores operam sobre K diferentes dados. Façamos uma analogia com uma linha de montagem de carros. Vamos supor que um carro leve 6 horas para ser montado e que a tarefa de montagem possa ser dividida em 12 equipes, numeradas em seqüência de 1 até 12, cada uma gastando meia hora. É fácil de ver que não precisamos esperar que a última equipe termine de montar um carro para a equipe 1 inicie a montagem do carro seguinte. Na verdade, todas elas trabalham simultaneamente, montando vários carros ao mesmo tempo. Por isso, com alguma liberdade, é costume classificá-la de paralelismo temporal. Então, apesar do tempo de montagem consumir 6 horas, a saída da linha de produção entrega um carro a cada meia hora. Agora é fácil voltar aos computadores e ver que temos um único fluxo de dados (SD), porém vários instruções (MI) processam esses dados, ao mesmo tempo.

MIMD - Múltiplas Instruções, Múltiplos Dados (Multiple Instruction Multiple Data)

Essa é a arquitetura que esperaríamos encontrar em um computador paralelo. Temos vários dados (MD) sendo operados por vários instruções (MI), simultaneamente. Essa é a arquitetura mais usada pelos modernos supercomputadores. Nesse caso, é importante que os processadores possam se comunicar entre si para fazer a sincronização e trocar informações. Além disso, é necessário ter uma memória, chamada de global, onde todos processadores possam disponibilizar, para os demais, os resultados intermediários. A Figura 5 apresenta uma solução genérica para essa arquitetura MIMD.

Note que agora temos N processadores e dois tipos de memória: a local e a global. A memória global pode ser acessada por qualquer um dos processadores, por isso existe a chamada “Estrutura de Comunicação”, que disponibiliza a memória global para qualquer um dos processadores. Uma única memória global criaria um grande gargalo, pois só um processador poderia acessá-la por vez. Por isso, a figura apresenta duas memórias globais e, com isso, dois processadores podem ser atendidos ao mesmo tempo.

Para evitar uma quantidade excessiva de acessos a essa memória, os processadores possuem a chamada memória local, onde está a maioria das suas instruções e dos dados que devam ser operados. Essa memória local evita que a estrutura de comunicação se transforme num enorme gargalo. Os processadores precisam trocar informações e, no caso desta figura, a própria estrutura de comunicação se encarrega desta tarefa.

Uma simples análise da arquitetura MIMD da Figura 5 mostra que agora existe um fluxo de múltiplos dados (MD) sendo operado por um fluxo de múltiplas instruções (MI). Agora sim é necessária a genialidade dos programadores, pois como conseguir que uma estrutura deste tipo, imagine 1.024 processadores, trabalhe de forma sincronizada para gerar algum resultado? Se já é difícil escrever e depurar programas seriais, imagine fazer isso em um computador com 1.024 diferentes programas trabalhando sobre 1.024 dados diferentes.

Ganho de Velocidade

Como medir o quanto se ganhou com a execução de uma tarefa em um computador paralelo? É intuitivo que devemos usar o tempo de execução para medir esse desempenho, já que nosso principal objetivo é aumentar a velocidade de processamento. Uma solução boa é verificarmos a relação entre os tempos gastos para executar essa tarefa em um computador serial e em um computador paralelo. A expressão a seguir é usada para o cálculo do Ganho de Velocidade, que é abreviado pela sigla GV.

Por exemplo, uma determinada tarefa, quando executada em um computador convencional consome 200 s e quando executada em uma máquina paralela (24 processadores) consome 10 s, então o ganho de velocidade é GV = 200/10 = 20.

Gostaríamos que o Ganho de Velocidade fosse igual à quantidade de Elementos de Processamento (EP) empregados, mas isso é raro de acontecer pois quando se escreve um programa para rodar em máquinas paralelas, invariavelmente se necessita colocar trechos extras (de programa) para sincronização dos diversos EP e troca de informações. Esses trechos extras recebem o nome de custo de paralelização. Dependendo da tarefa a ser executada, pode haver uma necessidade de sincronização e troca informações tão grande que venha a inviabilizar o processamento paralelo.

O ideal é que um aumento no número de processadores traga um igual aumento de desempenho (GV). A Figura 6 apresenta 4 casos, onde se calcula o Ganho de Processamento em função do número de processadores. A curva em vermelho mostra o caso ideal, onde há um ganho linear em função do número de processadores. A curva em verde traz um caso mais real onde o ganho não acompanha a quantidade de processadores, ou seja, ao dobramos a quantidade de processadores, não dobramos o ganho de velocidade. A curva em azul traz um caso de saturação em 85 processadores, ou seja, é inútil utilizar mais do que 85 processadores. A curva em negro apresenta um caso ainda pior, pois nota-se que há um limite em 25 processadores, qualquer processador que se adicione além desse valor, só atrasará o processamento.

Figura 6: Influência do custo de paralelização.

Assim, um tópico interessante é determinar qual a quantidade ótima de processadores para uma determinada tarefa. É claro que esse valor é fortemente influenciado pelo algoritmo e pela técnica de programação empregada. A arquitetura paralela também influencia muito. Por exemplo, algumas arquiteturas têm gargalos para a comunicação entre os processadores e outras penalizam muito os acessos à memória global. É claro que nem toda tarefa é indicada para ser executada em máquinas paralelas, como veremos no próximo tópico.

Lei de Amdhal

Apesar do quanto promissor a computação paralela possa parecer, ela não é uma solução para todo o problema de processamento. Existem tarefas que são eminentemente seqüenciais e que não tiram proveito de um computador paralelo. Voltando ao nosso exemplo da construção de uma casa, apesar dela ser executada em paralelo, existe por detrás uma seqüência que deve ser obedecida. Nessa construção, não podemos fazer o telhado antes de termos as paredes prontas e também não podemos construir as paredes antes do alicerce. Assim, é comum que as tarefas a serem executadas possuam porções paralelizáveis e porções que precisam ser executadas de forma seqüencial. Note que um computador paralelo operando de forma seqüencial é um grande desperdício, pois enquanto um processador trabalha no trecho serial, todos os demais ficam ociosos.

Abordando esse tema, Amdahl propôs uma expressão para esse problema, que ficou conhecida como Lei de Amdahl[3] e que está representada a seguir. A explicação é muito simples. Imaginemos uma tarefa que executada em uma máquina seqüencial gaste "T" segundos. Porém, quando preparada para execução em uma máquina paralela, ela tem uma porção que obrigatoriamente deve ser executada de forma serial. Digamos que "p" represente a porção serial, em conseqüência "(1-p)" representa a porção paralelizável. Quando executado em uma máquina paralela com N processadores, o tempo gasto será igual a "".

Somente o trecho paralelizável tira partido dos "N" processadores. Assim o Ganho de Processamento é dado por: ou que é a forma consagrada da Lei de Amdahl. Deve-se notar que estamos ignorando os custos de sincronização e de troca de parâmetros entre os processadores. Vejamos em um gráfico o desempenho de alguns programas, segundo essa lei. A Figura 7 apresenta 4 casos. A curva em vermelho é a de uma tarefa 100% paralelizável, ou seja, p = 0. Nesse caso o aumento do número de processadores reflete linearmente no desempenho. A curva em verde ilustra o caso de p = 0,001 ou 0,1%, ou seja, apenas 0,1 % das tarefas não puderam ser paralelizadas. A curva em azul é para o caso onde 1% (p = 0,01) da tarefa precisa ser executada de forma serial. Nota-se uma grande queda de desempenho para grande quantidade de processadores. A última curva representa o caso de uma tarefa onde 10% (p = 0,1) precisam ser executadas de forma serial. Nota-se que há uma saturação, e que o aumento de processadores, por exemplo, de 50 para 100 processadores, pouca diferença traz para o desempenho.

Devem ser ressaltados dois pontos importantes. O primeiro é que, exceto para o caso de p = 0, todos os demais casos irão apresentar saturação em algum ponto. Se p é pequeno, a saturação só ocorre com um elevado número de processadores. O segundo ponto é que, contrastando com a Figura 7, a Lei de Amdahl não prevê queda no desempenho, no pior caso, ele fica fixo em algum valor.

Figura 7: Exemplos da Lei da Amdahl.

Conclusão Parcial

Assim terminamos o este rápido estudo de processamento paralelo. Esperamos ter elucidado diversos conceitos básicos. Nas próximas partes dessa série de artigos ilustraremos nosso estudo abordando diversas arquiteturas paralelas propostas pelos gigantes de mercado para o próximo milênio.

Bibliografia

[1] IEEE "Annals of the History of Computing" magazine, Volume 15, Number 4, 1993, page 28.
[2] “Some Computer Organizations and their Effectiveness”, M. J. Flynn, IEEE Transactions on Computers, vol C-21, pp. 948-960, Setembro, 1972.
[3] “Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities”, G. Amdahl, AFIPS Conference Proceeding, vol. 30, Abril, 1967, Thompson Books, Washington DC.
[4] “Structured Computer Organization”, Andrew S. Tanenbaum, 4a Edição.

É expressamente proibida a reprodução total ou parcial do conteúdo deste site e dos textos disponíveis, seja através de mídia eletrônica, impressa, ou qualquer outra forma de distribuição. Os infratores serão indiciados e punidos com base na lei nº 9.610 de 19/02/1998.

Não nos responsabilizamos por danos materiais e/ou morais de qualquer espécie promovidos pelo uso das informações contidas no Clube do Hardware.