Introdução

Nos primeiros computadores, a programação era uma tarefa exclusiva dos profissionais. E era muito complicada, pois requeria programá-la diretamente através de Switches e reles. Com o advento da memória, passou-se a armazenar os dados na mesma, facilitando um pouco a vida do programador.

Após verificar-se que a memória (ou unidade de armazenamento) mostrava-se eficiente, pensou-se em disponibilizar também o código a ser utilizado no processamento na memória. Agora, não apenas os dados seriam buscados na memória, mas também as próprias instruções necessárias para manipula-los.

Como agora não é mais o programador quem "dita" as instruções ao hardware, fez-se necessário estabelecer uma certa ordem de execução. Nasceu então o Program Counter (PC), responsável por manter sempre atualizado o endereço da próxima instrução a ser executada. Nasceu o que hoje se conhece por Arquitetura Von Neumann.

Mesmo que na época esta técnica tornou-se um avanço sem precedentes, hoje ela, de certa forma, é um "calcanhar de Aquiles". Com o crescimento da informática em todos os sentidos, passou-se a não mais usar apenas um processador, mas vários. Neste caso, o PC já não é mais tão interessante, pois pretende-se executar não apenas uma, mas várias instruções simultaneamente. Os "remendos" na arquitetura de Von Neumann para possibilitar isso, geram um custo adicional as vezes impraticável, atrapalhando a eficiência da máquina como um todo.

A mentalidade de programação também constitui um empecilho à medida que criou-se aquela idéia de sequencialidade, uma instrução após a outra, tudo bem organizadinho, step-by-step... Com esta política de programação, o código fica, por vezes, impossibilitado de executar em paralelo por causa da dependência de dados e de controle gerado. Dependência de dados é quando, por exemplo, um dado gerado por uma instrução é usado pela instrução seguinte. Neste caso, ambas não podem ser executadas em paralelo, pois a segunda é dependente da primeira. Dependência de controle é quando a ordem de execução é "desrespeitada", ou seja, quando uma instrução atualiza manualmente o PC, fazendo com que a próxima a ser executada não seja a instrução seguinte, mas qualquer uma em qualquer lugar da memória!! Neste caso, como o processador irá executar duas ou mais instruções ao mesmo tempo se não pode garantir que a instrução subseqüente será a próxima?

Técnicas muito sofisticas foram desenvolvidas para resolver estes problemas na velha e conhecida Von Neumann, mas cada uma introduz um custo diretamente proporcional ao número de dependências existentes no código. Estas técnicas trabalham desde a nível de compilador (evitando as dependências) até o nível de hardware (reorganizando as instruções e tentando "prever" qual é a próxima instrução) [FER92].

O melhor mesmo é que estas dependências não existissem e por esta razão que novas arquiteturas, chamadas de Non Von Neumann, foram pesquisadas. Uma destas arquiteturas propõe que a execução não seja mais baseada em instruções, mas controladas pelo fluxo de dados. São as chamadas máquinas DataFlow. Uma destas, chamada de ADAM, tentou incorporar características tanto da Von Neumann (execução ordenada) quanto a do dataflow (execução ordenada pela disponibilidade dos dados).

Inicialmente vamos conhecer um pouco mais desta nova arquitetura. Após, será apresentada a máquina ADAM e de como os seus construtores misturaram estas duas arquiteturas completamente diferentes em uma única.

Arquitetura DataFlow

A busca de arquiteturas não Von Neumann é bastante antiga. Em 1979, Jack B. Dennis apresentou seu modelo, o orientado a dados [DEN79].

As arquiteturas Von Neumann são orientados a instruções, ou seja, há uma seqüência pré-definida de execução. O funcionamento de uma máquina neste caso pode ser resumido da seguinte forma:

- busca instrução;
- busca dados necessários na memória;
- executa a instrução;
- busca nova instrução.

Para controlar a execução, um contador (PC - Program Counter) foi implementado, sendo que o mesmo é incrementado em uma posição a cada instrução executada ou, dependendo da instrução, pode ser redefinido (no caso dos jumps e calls).

Em uma arquitetura Dataflow a instrução é executada quando os dados necessários a sua execução estiverem disponíveis. Não existe o conceito de PC. Também não existe o conceito de armazenamento de dados na memória. Os mesmos são "consumidos" (usados) e deixam de existir. Isso introduz um novo conceito de programação completamente diferente do atual.

Podemos considerar o exemplo da figura 2.2. Temos ali a representação gráfica do seguinte código: y=(if x>3 then x*2 else x-1) * 4. Estruturando melhor este código, temos o equivalente a:

If x>3
Then x+2;
Else x-1;
Y = x*4;

Vale lembrar que em dataflow, um comando (instrução) só é executado mediante a disponibilidade do dado. Quando um dado x for disponibilizado na entrada do SW e da condição de maior que 3, o SW irá enviar o mesmo dado X para a saída T ou F, dependendo do comando que receber. Este comando virá, no caso do exemplo, pela execução da instrução ">3". Em caso positivo (T), o comando será T, fazendo com que o SW envie o dado pela saída T.
 

Temos, com isso, que o dado X percorrerá o caminho T, sendo incrementado de 2, ou o caminho F, sendo decrementado de 1, mas nunca os dois simultaneamente. Após, o dado, já atualizado, passa por um MG, que é basicamente o contrário de um SW. O MG irá pegar o dado de uma de suas entradas disponíveis e colocá-lo à saída, dependendo do controle que receber, que no caso é o mesmo dado ao SW. Por fim, o dado X é multiplicado por 4, gerando o Y.

O dado, uma vez dito "consumido" deixa de existir, pois não é, como na Von Neumann, uma referência a memória. Se um mesmo dado precisa ser enviado a mais de uma unidade (como no caso do X inicial e do comando T ou F), mecanismos específicos precisam ser providos. Algumas máquinas possibilitam especificar dois ou mais destinos de um dado.

Da mesma formas, se há uma realimentação do dado (no caso de um laço, por exemplo), um cuidado todo especial deve ser observado para não perdê-lo.

Várias máquinas deste tipo foram criadas, principalmente em laboratórios do Japão e Estados Unidos. Em [HER90] muitas destas são apresentadas e comentadas. Pela referência feita em vários textos, pode-se concluir que a mais famosa foi a Manchester.

Uma delas é a máquina ADAM, que possui características bastante peculiares e difere-se um pouco das máquinas dataflow "tradicionais".

A Máquina ADAM

A arquitetura ADAM (Advanced Dataflow Machine), nascida do projeto EMPRESS, não é uma dataflow pura, sendo um híbrido dataflow/Von Neumann. Possui um modelo de execução bastante rígido, pois não permite que uma função ou até mesmo uma iteração de um loop seja executado sem que os dados estejam disponíveis, o que a caracteriza como dataflow. O projeto EMPRESS pertence ao Lawrence Livermore National Laboratory em Livermore, onde um protótipo em hardware da ADAM foi desenvolvido com 16 processadores. Um simulador também foi construído, possibilitando rodar em um Cluster Transputer ou Machintosh [MIT95]. O próximo capítulo estudará um pouco da arquitetura desta máquina.

Arquitetura

Na parte de exploração do paralelismo, verificou-se que as máquinas que tem uma granulosidade muito fina, a nível de instrução, como é o caso da manchester [TRE84], possuem um overhead muito alto para gerenciar o escalonamento. Na manchester, cada token tem 96 bits, sendo que destes, apenas 37 bits são referentes ao dado necessário à uma única instrução. O restante (59 bits) são preenchidos com informações de destino e origem. A ADAM, porém, usa Blocos de código ao invés de apenas instruções [MAQ95]. Os grafos de dados são transformados em tempo de compilação em blocos de códigos, possibilitando aos mesmos rodarem em vários processadores da máquina. Estes processadores são homogêneos e com memória distribuída.

Podemos ver na figura 3.1 um pequeno diagrama em blocos de um processador da máquina ADAM [MAQ95]. Cada um é composto de quatro blocos principais:
 

  

Sequencer e ALU: Este bloco é responsável pela busca e execução do código gerado pelo compilador e envia pedidos a outros blocos quando encontra instruções especiais. Podemos dizer que é o lado Von-Neumann mais forte desta arquitetura.

Object Manager: Responsável pelo acesso a dados externos e pelo próprio gerenciamento da memória.

Context Manager: gerencia os processos da máquina.

Token Manager: Esta pode-se dizer que é o lado dataflow da máquina. Responsável pela comunicação entre os demais processadores, é este bloco também o responsável pelo correto balanceamento de carga dos blocos de código.

Cada bloco possui, ainda uma ou mais memórias caches para agilizar o acesso a memória. São ao todo cinco caches, OC, SC, CC e TC. A comunicação entre os blocos, memória e IO é feita por dois bus, C-bus e D-bus.

Blocos de Código

Normalmente, como visto antes, as máquinas dataflow só executam uma instrução quando todos os dados para aquela instrução estiverem disponíveis. Em virtude da quantidade de bits necessários para gerenciar corretamente cada token, a máquina ADAM trabalha com uma granulosidade um pouco mais alta, denominada Codeblocs.

Estes blocos de código são gerados por um compilador e cada um deles é executado de forma sequencial no processador, mas podem ser executados de forma concorrente. Este é o principal diferencial entre as outras máquinas dataflow, já que estas consideram cada token para uma única instrução enquanto que a ADAM considera como token este bloco de instruções. Difere também das máquinas controlflow (Von Neumann) pelo fato de que chamadas a funções não causam a parada da execução, mas ela continua se os dados necessários estão presentes. Com isso, pode-se obter um nível de paralelismo bem eficiente, desde que os blocos de código sejam gerados de forma satisfatória. Na figura 3.2 podemos ver a geração de três blocos de códigos para a seguinte função:

f(a,b,c) = (c+2) * (c-3) - g(a) * g(b)

Sendo que:

g(x) = sqr(x-1)

É neste ponto que sua arquitetura foge completamente da conhecida Von Neumann e contempla características da dataflow. Conforme podemos ver na figura, três blocos de código foram gerados e podem ser executados concorrentemente. Ao executar, a máquina dispara os três blocos simultaneamente em seus processadores, sendo que cada instrução dentro do código, será executada se os dados existirem.

 
Se, na instrução t4 = mul(r1,r2) estes dados ainda não estiverem disponíveis, o processador responsável por este bloco irá aguardar a chegada destes dados (r1, r2) que estão sendo calculados por outros, só depois, então prosseguindo.

Escalonamento de Blocos

Quando o sequencer executa uma instrução de leitura a um dado externo, ele envia este pedido para o object manager (figura 3.1), marca o lugar da memória onde aguardará o resultado e continua a execução. Cabe ao object manager, então, procurar o dado referido comunicando-se com os demais processadores. É claro que se o dado ainda não estiver disponível, a execução do bloco de código que gerou a chamada irá parar e aguardar por ele. Podemos perceber que o papel do compilador como otimizador do código é vital para um perfeito paralelismo. No caso do exemplo da figura 3.2, de nada adiantaria se as duas chamadas de funções g(x) fossem feitas uma instrução antes de sua resposta ser usada. O compilador, no caso, providenciou para que todas as chamadas de funções fossem colocadas no início de cada bloco, para que quando seus resultados forem requeridos, os mesmos já estejam disponíveis.

Podemos, então, identificar alguns estados nos quais um bloco de código possa estar. Estes estados podem ser vistos na figura 3.3.

 

O processamento deve ter iniciado, em algum lugar, com uma chamada de função. Esta chamada gera um token, que diferente do token existente na máquina dataflow original, este possui todos os dados necessários a execução do bloco de código que representa. Na verdade é a mesma idéia do dataflow, apenas aumentando a granulosidade que era a nível de instruções ULA para estes, aqui chamados, blocos de código. O "context manager" irá, então, expandir este token para o seu referido bloco de código, criando um espaço em memória para o mesmo (chamado de frame) e inserindo-o na lista de blocos prontos para executar. Quando a carga de algum dos processadores disponíveis possibilitar, o mesmo entra em execução.

Interessante notar que um token na ADAM contém todas as informações necessárias a execução de um bloco. Carga entre os vários processadores podem ser trocadas apenas trocando-se tokens entre eles, desde de que os mesmos não estejam expandidos, ou seja, um bloco que começou já a sua execução, terminará naquele processador onde começou. Quando o bloco precisa de um dado que ainda não está disponível, este entra no estado de espera até que o mesmo chegue.

A tarefa de distribuir os tokens entre os processadores cabe ao bloco token manager (figura 3.1). Estes tokens são distribuídos de acordo com as informações de carga recebidos dos seus processadores vizinhos. Se, por exemplo, um token manager possui muitos tokens em seu buffer ainda não expandidos e recebeu a informação de um dos processadores pedindo tokens, este enviará uns dos seus. Isto é conhecido na literatura como "iniciado pelo Receptor", pois é quem está com pouca carga que procura um "receptor" [EL-94] e [PIN95]. Esta técnica se mostra mais interessante, pois um nodo sobrecarregado não precisa procurar por "doadores", sendo que os mesmo se manifestarão automaticamente. Como a "carga" de cada token é variável, o fato de um processador ter uma quantidade maior de tokens não significa, necessariamente que está com carga maior do que um outro que está com apenas um.

Por este motivo, além de decidir quando enviar um token a outro processador e a qual deles, também é importante decidir qual é o melhor token a ser enviado. Na literatura isto é conhecido como "Política de Seleção" [PIN95].

Politica de Seleção
Para ilustrar a importância de uma correta escolha de política, vamos analisar o exemplo da figura 3.4. Como estamos analisando uma máquina dataflow, devemos ter em mente que a execução não pára quando uma chamada de função é feita, mas quando o dado que ela iria fornecer for requisitado e ainda não está disponível. Assim sendo, podemos assumir que o bloco 1 executará em paralelo com o 2 e o 3 até que use os dados e assim sucessivamente.

Observe que dependendo da ordem da execução destes tokens, comportamentos diferentes podem ser obtidos. Por exemplo, o token 1 gera outros dois tokens, o 2 e o 3. Digamos que ambos estes sejam prontamente escalonados, sendo que cada um gerou mais dois (4 e 5, 6 e 7), que também são escalonados, gerando os oito finais. Estes últimos não tem dependência e podem, então, serem executados em paralelo até o fim sem interrupções. Chegará um momento, talvez, em que os nodos 4, 5, 6 e 7 necessitarão dos dados gerados por seus "filhos", ficando bloqueados se ainda não estiver disponível. Teremos, então, um máximo de oito blocos executando simultaneamente nos processadores.

Agora, digamos que o escalonamento tivesse sido um pouco diferente. Ao gerar os blocos 2 e 3, apenas o 2 foi expandido, gerando os 4 e 5, e que destes, apenas o 4 foi expandido, gerando o 8 e 9. Teríamos uma ordem de escalonamento nesta sequencia: 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 14, 15. Neste caso, apenas quatro blocos executarão até o fim simultaneamente, sem esperar dados.

O primeiro exemplo de escalonamento é conhecido como "breadth-first" enquanto que o segundo como "depth-first".

A ADAM utiliza os dois métodos de escalonamentos mostrados acima da seguinte forma:

Os tokens são colocados em um buffer em anel, com acesso em ambos os lados, dependendo do origem e do destino do token. Tokens novos gerados pelo sequencer do processador são inseridos e removidos pelo lado esquerdo e tokens trocados entre os processadores são colocados e tirados pelo lado direito do buffer. Para os tokens locais, o buffer funciona como uma pilha, sendo que os últimos tokens gerados são os primeiros a ser escalonados, mas para tokens recebidos de outros processadores, o buffer funciona com uma fila FIFO. Com isso, os tokens locais são executados antes dos trocados com os demais processadores. Vale lembrar que mesmo que um processador esteja sobrecarregado, ele continuará processando até que um receptor (processador com pouca carga) se manifeste requerendo tokens para processar. Isso só ocorrerá quando o buffer estiver vazio.

Linguagens disponíveis

Como pode ser visto anteriormente, o compilador tem uma participação crucial no desempenho da máquina. É ele quem gera os blocos de código e reordena as chamadas de funções de maneira a possibilitar um paralelismo próximo do ideal. Três linguagens foram desenvolvidas para a ADAM, sendo que em [MIT95] é estudado com alguns detalhes a SISAL (Streams and Iteration in a Single-Assignment Language) e em [MAQ95] outras duas são citadas: HLA (High-Level Assembler) e a FOOL (Funcional Object-Oritented Language). Interessante também, no que diz respeito a máquinas dataflow em geral, é o proposto em [WAI95], onde comenta-se da dificuldade em absorver um novo conceito de programação, agora orientado a dados, em troca das já tradicionais linguagens imperativas. Baseado neste problema, é proposto tradutores de linguagens imperativas para as máquinas dataflow, geralmente para a linguagem SISAL.

Conclusão

As máquinas dataflow foram tidas como revolucionárias quando idealizadas. Na prática, porém, estão ainda ineficientes. A ineficiência se deve ao fato de que as Von Neumann, mesmo com todos os seus problemas e com o custo necessário para resolvê-los ou evitá-los, ainda se mostra incrivelmente mais rápida. A Dataflow, mesmo que tenha se livrado de alguns destes problemas, ainda executa de forma lenta e tem outros problemas, como, por exemplo, a estrutura de dados necessárias para gerenciar o próprio dado que agora deve conter o dado e uma informação (cabeçalho) para contextualizá-lo no sistema, já que é o dado quem procura a instrução e não a instrução quem procura seus dados.

A máquina ADAM foi inovadora no sentido de aumentar então, a granulosidade do token (que inicialmente era o mero dado), gerando bloco de códigos. Com estes blocos, minimiza-se os custos para gerenciá-lo, mas volta-se a ter os problemas de Von Neumann dentro de cada bloco. O lado Dataflow da mesma pode ser observado nas chamadas não bloqueantes de função e da execução de laços e funções somente com a disponibilidade dos dados. A alternativa de se fazer uma fusão entre as duas arquiteturas trouxe características desejáveis, mas não eliminou os problemas por completo.

Referências Bibliográficas
[DEN79] DENNIS, Jack B. The Varieties of Data flow computers. In: IEEE Computer Society. 1986. Pag 51-60.

[EL-94] EL-REWINI, Heshan; LEWIS, Theodore G.; ALI, Heshan H. Task Scheduling in Parallel and Distributed Systems. Prentice Hall, New Jersey. 1994.290p.

[FER92] FERNANDES, Edil S. T.; SANTOS, Anna Dolesjsi. Arquiteturas Super Escalares: Detecção e Esploração do Paralelismo de Baixo nível. In: VIII Escola de Computação, Gramado-RS. Instituto de Informática. UFRGS.Porto Alegre, 1992.

[HER90] HERATH, Jayantha; YAMAGUCHI, Yoshinori; HERATH, Susantha. Data-Flow Computing Models, Logic and Funcional Languages, and Data-Flow Machines for Intelligence Computations. In Computers for Artificial Intelligenc processing. Edited by Benjamin W. Wah. Wiley-Interscience, New York. 1990. Pags 209-268.

[MAQ95] MAQUELIN, Oliver C. Load Balancing and Resource Management in the ADAM Machine. In: Advanced Topics in Dataflow Computing and Multithreading. IEEE Computer Society Press, Los Alamitos. 1995. Pag 307-323.

[MIT95] MITROVIC, Srdjan. Programming the ADAM Architecture with SISAL. In: Advanced Topics in Dataflow Computing and Multithreading. IEEE Computer Society Press, Los Alamitos. 1995. Pag 211-228.

[PIN95] PINEDO, Michael. Scheduling: Theory, Algorithms and Systems. Prentice Hall, New Jersey. 1995. 378p.

[TRE84] TRELIEVEN, P.C. Descentralised Computer Architeccture. In New Computer Architectures. Intenation Lecture Series in Computer Science. Academic Press, London. 1984. Pgs 1-55.

[WAI95] WAIL, Simon F.; ABRAMSON, David. Can Dataflow Machines be Programmed with an Imperative Language? In: Advanced Topics in Dataflow Computing and Multithreading. IEEE Computer Society Press, Los Alamitos. 1995. Pag 229-265.