PROCESSAMENTO CONCORRENTE EM ALGORITMOS COM EXECUÇÃO ORIENTADA A FLUXO DE DADOS EM HARDWARE RECONFIGURÁVEL

Vitor Fiorotto Astolfi

Orientador: Jorge Luiz e Silva

1

PROBLEMAS ENFRENTADOS PELAS INDÚSTRIAS DE PROCESSADORES

Maior barreira – densidade de potência. (W/cm²)

Pentium Pro – densidade de uma chapa quente.

Em 2010 – atingiria a temperatura de um reator nuclear

Porém: em 2004 Intel anuncia que focará nos multi-core. Outras fabricantes seguem.

2

PROBLEMAS ENFRENTADOS PELAS INDÚSTRIAS DE PROCESSADORES

Gargalo – aumento da freqüência dos barramentos não acompanhou aumento da freqüência dos processadores. 7% ao ano.

3

PARALELISMO EM NÍVEL DE INSTRUÇÃO – PROCESSADORES SUPERESCALARES.

Técnicas – pipeline, execução fora-de-seqüência, execução especulativa.

Temos algum processamento dirigido pelo fluxo de dados.

Essas técnicas forneceram aumento de desempenho de 600% na década passada.

4

PARALELISMO EM NÍVEL DE INSTRUÇÃO – LIMITAÇÕES

Aumento indefinido de estágios de pipeline não é uma boa solução Potência consumida Baixo speedup

5

PARALELISMO EM NÍVEL DE INSTRUÇÃO – LIMITAÇÕES

Especulação agressiva aumenta muito o uso de memória Aumento da latência Prejudica

preenchimento dos pipelines.

Aumento da EPI

6

ARQUITETURAS DATAFLOW

Usa todo paralelismo possível Sem considerar execuções especulativas

Elimina gargalo de acesso à memória centralizada Não há necessidade de armazenamento de dados

compartilhado. Arquiteturas Dataflow (anos 70 e 80): problemas

Granularidade fina demais – mais tempo era gasto durante o tráfego que a computação em si dos dados.

Estruturas de dados Linguagens de programação Etc... 7

PROJETO CHIPCFLOW

Compilador da linguagem C para grafos Dataflow (fluxo de dados) Não usa linguagens de programação específicas

das Arquiteturas Dataflow. Multi-tarefa – Uso do paralelismo natural do

hardware Threads – Condições de disputa.

Execução direta em hardware.

Similar ao Impulse C, etc. 8

CPSEQ – DUAS COMPARAÇÕES SIMPLES EM SEQÜÊNCIA./* Programa CpSeq – Duas

comparações em seqüência */ int main () { int a, b, c, d, e, f; int p, q, r, s, t, u;

input(&a, &b, &c, &d, &e); if (a > 0) { f = b + c; } else { f = d – e; } output(f); 

input(&p, &q, &r, &s, &t); if (p < 0) { u = q / r; } else { u = s * t; } output(u);}

9

CPPAR – DUAS COMPARAÇÕES SIMPLES EM PARALELO./* Programa CpPar – Duas

comparações em paralelo */ void F( ) { int a, b, c, d, e, f;

input(&a, &b, &c, &d, &e); if (a > 0) { f = b + c; } else { f = d – e; } output(f);} 

void U ( ) { int p, q, r, s, t, u;

input(&p, &q, &r, &s, &t); if (p < 0) { u = q / r; } else { u = s * t; } output(u);} int main ( ) { thread tf, tu; thread_create(&tf, F); thread_create(&tu, U);}

10

REPRESENTAÇÃO DE AMBOS CPSEQ E CPPAR EM GRAFO DATAFLOW

11

PROBLEMA DO PRODUTOR-CONSUMIDOR (MODIFICADO) – IMPLEMENTAÇÃO INCORRETA/* quantidade máxima de

elementos */#define N 100/* quantidade de elementos no

momento */ int count = 0; int produzir;int consumir;  void produtor ( ) {

input(produzir);while (produzir) { if (count < N) {

count = count + 1; } input(produzir);}

}

void consumidor ( ) { input(consumir); while (consumir) {

if (count > 0) { count = count − 1;

} input(consumir);

}} int main ( ) { thread p; /*1 produtor */ thread c1, c2;/*2 consumidores */ thread_create(&p, produtor); thread_create(&c1, consumidor); thread_create(&c2, consumidor);}

12

PROBLEMA DO PRODUTOR-CONSUMIDOR (MODIFICADO) – GRAFO DATAFLOW INCORRETO

Grafo Inseguro

Grafo com condições de disputa.

Inicialização da variável compartilhada

13

PROBLEMA DO PRODUTOR-CONSUMIDOR (MODIFICADO) – IMPLEMENTAÇÃO COM MONITORES#define N 100

int count = 0;

 monitor produtor_consumidor {

  void insere () {

if (count < N) {

count = count + 1;

}

}

  void remove () {

if (count > 0) {

count = count - 1;

}

}

 }

 void produtor () {

input(produzir);

while (produzir) {

insere();

input(produzir);

}

}

void consumidor ( ) {

input(consumir);

while (consumir) {

remove();

input(consumir);

}

}

 

int main ( ) {

thread p; /* 1 produtor */

thread c1, c2; /* 2 consumidores */

thread_create(&p, produtor);

thread_create(&c1, consumidor);

thread_create(&c2, consumidor);

}

14

PROBLEMA DO PRODUTOR-CONSUMIDOR (MODIFICADO) – GRAFO DATAFLOW COM “DISTRIBUIDOR”

Grafo seguro

Escalonamento round-robin

Problema: limitação do paralelismo (gargalo).

15

PROVA DE CONCEITO – PRODUTOR CONSUMIDOR COM COMPARTILHAMENTO DE DUAS VARIÁVEIS

Count – Número de itens disponíveis

Cons – Número de itens consumidos

Novos operadores em negrito

Distribuidor – envio de dados simultâneo e exclusivo a cada linha de execução

16

PROVA DE CONCEITO – MODULARIZAÇÃO DO PROBLEMA

Criação de operadores produtor e consumidor

Cada um deles testado separadamente.

17

SUPER-BLOCO “CONSUMIDOR” – IMPLEMENTAÇÃO NO XILINX ISE

18

TESTE DO SUPER-BLOCO “CONSUMIDOR”

Blocos INDATA e AOUT:Sincronizar dados de entrada e de saída.

19

TESTE DO SUPER-BLOCO “CONSUMIDOR” - RESULTADOS

20

APÓS CRIAÇÃO DOS BLOCOS DISTRIBUIDOR E PRODUTOR – CIRCUITO FINAL

21

CIRCUITO FINAL – RESULTADO (ATÉ 1000 NS)

22

OBRIGADO

Perguntas?

23