• View
• Edit
• History
• Print

Em caso de dúvidas sobre conceitos básicos de matemática acerca de divisão, π, série, e convergência veja este exercício anterior.

Série de Leibniz para π

π = 4/1 - 4/3 + 4/5 - 4/7 + ...

A série de Leibniz converge lentamente comparado a outras séries conhecidas. Tanto PC como FPGA demoram vários segundos para convergir com menos de 15 dígitos fracionários hexadecimais para o cálculo de π, ou seja, para representar π dentro da capacidade do display LCD que temos ou usando só uma palavra de um processador de PC. Por isso a série de Leibniz foi escolhida para os exercícios a seguir.

Aplicar fator de escala

Empregando um fator de escala t ∈ ℕ para poder usar números inteiros, podemos substituir:

v = π*t, v ∈ ℕ
m = 4*t, m ∈ ℕ

para reformular a série de Leibniz:

v = m/1 - m/3 + m/5 - m/7 +...

Iteração

Em vez de fixar uma quantidade de elementos da série que queremos calcular, como fomos obrigados a fazer quando só sabíamos usar circuitos combinatórios, podemos usar um circuito sequencial para calcular tantos elementos quantos precisamos para atingir um determinado critério de parada.

Podemos usar este pseudo-código para calcular uma aproximação para π*t:

para d = m/a - m/(a+2), a = 1, 5, 9, ...
enquanto d > 0 faça: v = v + d

m, d, a, e v são definidos como sendo numeros naturais incluindo 0, ou seja, nunca assumem um valor negativo.
t e m são parâmetros constantes.
d, a, e v são variáveis.

A expresão d>0 é o critério de parada.

Sobre Python e Systemverilog

Um código em Python pode parecer fazer a mesma coisa do que um código parecido em SystemVerilog, só que o código em SystemVerilog gera um resultado com valores "bonitinhos", enquanto o código em Python gera um resultado diferente com valores "feios".

Veja estes dois pares de exemplos:

Python sem for comparado com SystemVerilog sem for

Python com for comparado com SystemVerilog com for

Qual é a diferença entre um for em software e um for em descrição de hardware?

Python é uma linguagem de software (ela descreve sequência de operações a serem executadas, uma após da outra, usando um circuito dígital já existente), enquanto SystemVerilog é uma linguagem de descrição de hardware, ou seja, ela descreve um conjunto de operadores e elementos memorizantes e as conexões entre eles, ou seja, descreve um circuito digital. O circuito é criado fisicamente, mediante a síntese, dentro da FPGA. Veja também O quê é Computação ?

A implementação em Python é só uma ajuda para entender como funciona a fórmula de Leibniz. Não tente copiar o código do Python para Systemverilog, vai dar coisa estranha. Oriente-se pelo pseudo-código.

Sobre always_comb e always_ff

Forçar o uso de flip-flops, onde não é necessário, só atrapalha. Pode até funcionar, mas de forma torta (mais corretamente, com um atraso suplementar de um ciclo de relógio). Logo, não use always_ff para atribuições para as quais um always_comb resolveria.

Oriente-se pelo pseudo-código e raciocine qual variável pode ser o resultado de uma operação combinatória e qual variável precisa se tornar um registrador (flip-flop).

Pense: uma ULA precisa de flip-flop? Você aprendeu fazer ULA antes de aprender always_ff ou depois?

Sim, eu sei, pouco adianta pedir a alunos de "raciocinar" ou de "pensar": alunos resolvem tudo na tentativa e erro, se o parafuso não entra batendo nele com a chave de boca, eles pegam um martelo, depois uma marreta,... Mas, pensando bem, não seria melhor usar raciocínio?

Sua tarefa

Implemente em FPGA, usando numeros inteiros, a fórmula de Leibniz para até 15 dígitos hexadecimais fracionários.

Implemente a fórmula de Leibniz

Evite o uso de valores mágicos, use a palavra chave parameter.

A quantidade de dígitos hexadecimais deve ser uma constante no código Systemverilog, recomendo usar a palavra chave parameter.

Para depuração recomenda-se o uso de somente 2 dígitos hexadecimais fracionários e deixar o clock mais lento, por exemplo 1 Hz ou 0,5 Hz. Para fazer isso, aumente o parâmetro divide_by no DE0_Nano.sv e/ou no DE0_SOC.sv.

Crie um contador a. Visualize a na primeira linha do LCD (saída lcd_a). Faça a contar com passos de 4. Use a chave SWI[0] como sinal de reset para inicializar a em 1.

Visualize o resultado da divisão de 4/a na segunda linha do LCD (saída lcd_b), tendo cuidado de usar o mesmo fator de escala t tanto para o valor 4 como para 4/a.

Visualize o resultado da expressão m/a - m/(a+2) na segunda linha do LCD.

Faça o contador a parar quando m/a - m/(a+2) atinge o valor 0.

Crie um "contador" v que inicia com 0 e dá "passos" de 4/a - 4/(a+2). Visualize pi na segunda linha do LCD.

Use a implementação em python ou C para verificar o correto funcionamento da implementação em FPGA.

• Para rodar a implementação em python, abra um terminal X e dê o commando:
  pi.py
>>> pi(<quantidade_de_dígitos>)
• Para rodar a implementação em C, abre um terminal X e dê o commando:
  pi <quantidade_de_dígitos> <quantidade_de_núcleos>
• Quem quer treinar em casa pode pegar os códigos fonte de python e de C. O comando para compilar está na primeira linha.

Para depuração e simulação recomenda-se o uso de somente 2 dígitos hexadecimais fracionários e um clock mais lento de 1 Hz ou 0,5 Hz. Quando estiver funcionando corretamente desta forma, volte para o clock original, aumente o numero de dígitos hexadecimais e deixa o FPGA correr mais rápido, diminuindo o parâmetro divide_by no DE0_Nano.sv e/ou no DE0_SOC.sv.

Análise de Timing

Especifique dentro dos arquivos DE0_Nano.sv, DE0_Nano.sdc, DE0_SOC.sv, e DE0_SOC.sdc o fator de divisão do sinal de relógio divide_by e verifique se a síntese termina com um "setup slack" positivo.

Use pelo menos 12 dígitos e um fator de divisão de clock de no máximo 30.

"Slack" significa folga, no caso é o tempo de ciclo de relógio que está sobrando depois do último sinal de entrada de flip-flop estabilizar.

Enquanto o "setup slack" estiver positivo, pode diminuir o fator de divisão (divide_by) para deixar o sinal de relógio mais rápido.

Verifique o correto funcionamento da implementação mesmo com slack moderadamente negativo (overclock).

Verifique o funcionamento incorreto da implementação para um slack pior.

Bibliografia

Do livro secções 2.9, 3.6 e 3.5 até "Setup Time Constraint" inclusive.

O livro usa como exemplo o processo de fazer biscoitos, processo bem conhecido por quem cresce no chamado "primeiro mundo". Para nossa realidade o processo de ir numa pizzaria é mais conhecido.

Paralelismo espacial

Paralelismo espacial consiste em usar, em vez de um forno doméstico um forno de uma pizzaria. Num forno doméstico cabe no máximo duas pizzas, mas no forno de uma pizzaria cabe meia dúzia de pizzas. Caso se queira fazer somente 2 pizzas, o forno de pizzaria leva o mesmo tempo para fazer-los que o forno doméstico. Porém, para fazer 24 pizzas no forno doméstico leva 12 fornadas, num forno de pizzaria só leva 4 fornadas, três vezes mais rápido.

Trazendo para computação, o forno é a FPGA e as pizzas são os dados a serem processados, no caso, os elementos do somatório de Leibniz. Uma fornada é um ciclo de clock. O forno pequeno corresponde a uma FPGA pequena, ou a um processador de PC de 2 núcleos, enquanto o forno de pizza corresponde a uma FPGA um pouco maior, ou a uma placa mãe com quadro processadores de 6 núcleos cada.

Paralelismo espacial consiste em instanciar, em vez de um só operador, vários operadores. No caso do cálculo de pi, em vez de só 2 operadores de divisão, uma subtração e um somador, podemos instanciar 4 operadores de divisão, dois subtratores e dois somadores, ou 6 operadores de divisão, 3 subtratores e 3 somadores, até não caber mais na FPGA. Assim, a cada ciclo de clock, em vez de calcular só 2 elementos da sequência de Leibniz (pizzas), podemos calcular 4, 6 ou mais elementos da sequência de Leibniz (pizzas) e avançar o contador "a" com um passo maior do que 4, a cada clock.

Você entendeu? Responde a estas perguntas: O forno doméstico corresponde ao PC ou à FPGA? O forno de uma pizzaria corresponde ao PC ou à FPGA?

Paralelismo temporal

Para uma situação do nosso dia-a-dia que usa paralelismo temporal (também chamado pipelining), veja este video de uma linha de produção, principalmente a partir de 2:30 minutos. Você pode até observar esta linha de produção ao vivo em Campina Grande.

Para entender melhor, assiste esta animação de uma linha de produção. Observe que, se a peça (pizza) ficasse parada no lugar, em vez de passar de um trabalhador para o próximo, o segundo trabalhador teria que esperar o primeiro trabalhador terminar o trabalho dele e o terceiro trabalhador teria que esperar o segundo trabalhador terminar o trabalho dele. Por causa dessas esperas, menos peças (pizzas) seriam produzidas por unidade de tempo. A peça (pizza) está sendo empurrada do posto de trabalho de um trabalhador uma para o posto de trabalho do próximo trabalhador assim que a parte de trabalho do trabalhador anterior estiver terminado, permitindo que o trabalhador anterior já possa trabalhar na próxima peça (pizza).

Trazendo para ciência da computação,

• as pizzas que estão sendo montadas correspondem a dados que estão sendo computados;
• os trabalhadores correspondem a circuitos digitais combinatórios;
• o espaço entre os postos de trabalho corresponde a registros (flip-flop) pelos quais passam os resultados da saída de um circuito combinatório para a entrada do próximo circuito combinatório;
• o empurrão dado à pizza para passar de um posto de trabalho para o próximo corresponde ao sinal de clock.

Observe que o sinal de clock sincroniza o ritmo de trabalho, ou seja, todas as pizzas na linha de produção precisam ser empurradas ao mesmo tempo para não dar uma gororoba de pizzas.

• para entender o uso de paralelismo temporal (pipelining)
• para entender a implementação do divisor com pipelining

A segunda página deste documento foi usado para fazer os vídeos acima.
Aqui o top.sv que pode ser usado no LCC3 ou em casa para gerar a saída usado como exemplo.
Para simular em casa, por causa de limitações do Verilator usado por Ícaro, é preciso usar um divi_pipe.sv alternativo. Observei que a versão 4.010 do Verilator, usado no Xubuntu 19.04, dá um resultado errado para a divisão verde. A versão 3.922 usada no CentOS não apresenta este problema. Recomendo remover a versão 4.010 (comando sudo apt remove verilator) e instalar a versão 3.922 conforme novas instruções.

Os computadores do LCC3 sao leeeeeeentos. Provavelmente você tem acesso a um computador mais rápido em casa. Para experimentar com slack e com aproveitamento de recursos lógicos da FPGA em casa, instale CentOS 7 e Quartus 14.1 (Quartus II Web Edition (Free): Quartus II Software (includes Nios II EDS) + Cyclone IV device support) e use o comando sintesize $PWD da pasta TOP.

Regime remoto - Centavos para o cálculo de uma aproximação de π

Observações: Quem possui um computador mais fraco tem vantagem neste projeto, mas não vale um computador mais fraco do que aqueles listadas na tabela. Os centavos não acumulam, ou seja, no máximo pode-se ganhar 270 centavos neste projeto.

O aparecimento de valores mágicos ou uso indevido de always_ff impedem notas maiores do que 1 ou 3, ou mais do que 20 ou 50 centavos, respetivamente.

As notas 8, 9, e 10 valem para placa DE0_Nano. Quem usa uma placa DE0_SOC, precisa ser 3 vezes mais rápido.

Para calcular o tempo que a FPGA demorou, use a expressão a/passo * 1/(50MHz/divide_by) , na qual a aparece na primeira linha do LCD, passo é o passo de a a cada ciclo de relógio, e divide_by é o valor que se encontra nos arquivos DE0_*.sv e DE0_*.sdc.

Para tirar 8, é preciso ter obtido a nota 7 antes. Volte a trabalhar com um slack positivo, mas de valor pequeno. Use paralelismo espacial, ou seja, incorpore a solução da nota 8 da primeira tabela de notas desse guia.

Pode se inspirar do código python com relação à condição de parada, qualquer uma dessas soluções serve.

Recomendo usar 12 dígitos hexadecimais fracionários. Usando menos, termina muito rápido, usando mais, demora muito.

Para tirar 9, é preciso ter obtido a nota 7 antes e trabalhar com 15 dígitos fracionários, e usar paralelismo temporal (pipelining). Trabalhe a partindo da solução sem paralelismo espacial (solução para nota 6). Não é preciso você criar o pipelining, só usar-lo.

Temos a disposição duas implementações de operadores de divisão que usam pipelining: o primeiro foi concebido pelos engenheiros da Altera, a empresa que desenvolveu a FPGA (hoje ela se chama Intel porque a Intel comprou a Altera), o segundo foi eu.

O primeiro tem entradas e saídas já dimensionadas para trabalhar com até 15 dígitos fracionários, faz 16 estágios de pipelining, e é instanciado assim:

divi (.aclr(reset), .clock(clk_2),
      .numer(m), .denom(a), .quotient(qa) );

O sinal reset é o da SWI[0]. A saída (resultado da divisão) é qa. Antes do primeiro resultado válido, qa sai com valor zero.

No LABARC não é preciso copiar nenhum arquivo. Para simular em casa use um equivalente funcional simplificado divi.sv.

Implemente esta máquina de estados finitos:

O estado encher serve para encher o pipeline do divisor e o estado somar representa o funcionamento contínuo do pipeline. Em ambos estes estados os valores de a e pi devem ser atualizados. No estado parar não deve ser feito nada.

O segundo foi usado para fazer os vídeos acima, pode ser dimensionado para quaisquers tamanhos de entradas e saídas, usa tantos estágios de pipelining quanto tem bits no resultado, e pode ser instanciado assim:

divi_pipe #(.NBITS_DEND( ), .NBITS_SOR( ), .NBITS_Q( )) d1 (.dend(m), .sor(a), .q(qa), .rst(reset), .clk(clk_2), .valid(valid));
                        ^              ^            ^             ^        ^      ^   
                        |              |            |             |        |      |

quantidade de bits do numerador

quantidade de bits do denominador

quantidade de bits do quociente

entrada para o numerador

entrada para o denominador

saída do quociente

O sinal reset é o da SWI[0]. A saída v indica se a saída q estiver válida. Obviamente, a condição de parada só deve ser considerada quando a saída q for válida.

No LABARC não é preciso copiar nenhum arquivo. O simulador não funciona bem, estou corrrigindo. Para simular em casa, por causa de limitações do Verilator usado por Ícaro, é preciso usar um divi_pipe.sv alternativo. Observei que a versão 4.010 do Verilator, usado no Xubuntu 19.04, dá um resultado errado para a divisão verde. A versão 3.922 usada no CentOS não apresenta este problema. Recomendo remover a versão 4.010 (comando sudo apt remove verilator) e instalar a versão 3.922 conforme novas instruções.

Para depuração, seja qual for o divisor escolhido, volte a usar divide_by=50_000_000 e 2 dígitos hexadecimais e use o simulador.

Na FPGA, com 15 dígitos fracionários, veja como o parâmetro divide_by pode ser reduzido sem que o slack fique negativo.

Para tirar 10, trabalhe com 15 dígitos fracionários e use tanto paralelismo espacial como temporal (combine a solução da nota 8 com a solução da nota 9).

Como assim ??

Um sisteminha do tamanho de 4 caixas de fósforo, lançado em 2011, custando 61 US$, com clock de 50 MHz, tirando menos de 2W de energia, fazendo uma computação numérica de 64 bit, consegue superar um desktop com processador de 64 bit, lançado em 2017, custando 3000 R$, com clock de mais de 1 GHz, alimentado por um adaptador de 65W ? Como isso é possível ??

A arquitetura de von Newman é muito, muito ineficiente.

Mas é fácil - um adolescente de 13 anos aprende Python, se quiser.

As máquinas do LCC3 são lentas

pi 15 4

Síntese para DE0-Nano da solução para tirar nota 10

time make