Cortex M4 sem FPU !!!

[msamsoniuk]

...mas pq ao inves de dividir a/b em 4 ciclos vc nao multiplica pelo reciproco a*(1/b) em 1 ciclo?...

Nesse caso aí, não continuaria tendo de ser feita uma divisão (1/b) ?
Se b fosse um constante inteiro potencia de 2 ( b=2^n ), aí daria para fazer a divisão com 1 operação, já durante a compilação : ( a>>n ).


+++

eu acho que para quem trabalha com DSP esta sub-entendido como funciona... soh coloque a*(1/b) pq tem maluco que sabe o que eh, mas nao conhece pelo nome "reciproco".

[msamsoniuk]

Um dia será possível uma divisão qualquer, não trivial, com a precisão desejada, ser feita em um ciclo, em um multiplicador. Mas ainda não dá.
Certamente, tendo FPU, a engenharia de software do compilador saberá decidir, cada caso, se manda para a FPU ou se faz pelo inverso.

Em 8 bits sempre uso este processo e somente com unsigned. Nunca se usa 1/b (em micros capengas) e sim (1*2^n)/b ou até mesmo em base 10(com mais processamento), quando for algo simples para um display. Basta mudar o ponto decimal, para o ajuste .
No caso base 2, ao final é só deslocar para à direita. Provavelmente, o compilador já dará sua contribuição, transformando em produto com inteiros.

pois eh, depois de decadas vendo DSPs e FPGAs apenas com multiplicadores em hardware, eu acho que mesmo os 4 clocks de uma FPU sao um completo desperdicio de tempo e silicio.

veja que, na real, os bons compiladores hoje em dia jah fazem as otimizacoes automaticamente:

Código: Selecionar todos

int main(int i,char **p)
{
  printf("%d\n",i/1000);
}


vira isso aqui:

Código: Selecionar todos

        movl    $274877907, %edx
        movl    %edi, %eax
        imull   %edx
        sarl    $6, %edx
        sarl    $31, %edi
        subl    %edi, %edx
        movl    %edx, %esi
        leaq    LC0(%rip), %rdi
        xorl    %eax, %eax
        leave
        jmp     _printf


note o "imull" ali. isso em um PC, onde a ALU de m**** desenvolvida pela intel requer varios ajustes. em um DSP ou FPGA vc faz pre-shift, multiplica, faz pos-shift e acumula tudo em um unico clock.

mas bom, tem uns veios ae que ainda querem usar FPU e divisao em pleno seculo XXI neh... hehehe

[RobL]

É esse tal de FPU é blefe. Usam só pra gente gastar mais. Ficam só entulhando o hardware pra aumentar o peso!

[RobL]

O inverso de A é o número que multiplicado por A gera unidade, ou seja : b * 1/b = 1 <=> 1/b é o inverso de b.
O que é o recíproco ?

Motivado pela terceira lei de Newton ou :
1chato + 1chato = chato ^ n

[B-EAGLE]

olha... pra quem precisa fazer cálculos num sistema de baixíssimo consumo médio ( < 5uA ), o que me parece mais adequado é um micro com fpu, a não ser que você tenha que acordar o sistema a cada uma hora pra calcular, agora se for a cada segundo...

não to conseguindo ver outro jeito de fazer cálculo bruto consumindo pouco desse jeito...

[andre_luis]

...em um DSP ou FPGA vc faz pre-shift, multiplica, faz pos-shift e acumula tudo em um unico clock...

Como funciona essa matemática ?


+++

[msamsoniuk]

...em um DSP ou FPGA vc faz pre-shift, multiplica, faz pos-shift e acumula tudo em um unico clock...

Como funciona essa matemática ?
+++

por exemplo, suponha que vc vai lah no software para filtro e marca uns pontos lah, daih vc obtem um filtro da seguinte forma:

Código: Selecionar todos

y[0]=x[0]−1.86*x[1]−0.998*x[2]−1.79*y[1]−0.928*y[2]

bom, ninguem nem discute se o certo eh o coeficiente ser multiplicado ou dividido pq o DSP ou FPGA soh tem multiplicador. soh de olhar os numeros jah dah para ver tb que usar 1/b ou b nao faz diferenca, os numeros sao uma bosta e, de qq forma, nao dah para expressar corretamente.

entao o normal eh multiplicar o coeficiente por 32768 e entao usar um shift de 15 bits p/ direita:

Código: Selecionar todos

y[0]=x[0]−(60948*x[1])>>15−(32702*x[2])>>15−(58645*y[1])>>15−(30408*y[2])>>15

No caso, tem que desmembrar a expressao em quatro instrucoes MAC sequenciais. a notacao varia de DSP para DSP, mas normalmente a instrucao MAC aceita o shift.

na FPGA a coisa eh eh mais ou menos assim:

Código: Selecionar todos

wire [15:0] X; // variavel entrada 16 bits sinalizado
wire [15:0] K; // coeficiente*32768
wire [31:0] MUL = X*K; // multiplica 16x16 bits e obtem 32 bits
wire [15:0] SHF = MUL[30:15]; // jah divide por 32768

reg  [15:0] Y; // acumulador

always@(posedge CLK)
  Y <= Y + MUL[30:15]; // jah divide X*K por 32768 e acumula

[andre_luis]

Marcelo,


Esse procedimento que você mencionou é exatamente o que citei anteriormente para o caso de a/b.
Porém o que você exemplificou só funciona com divisor b constante em tempo de compilação.


+++

[msamsoniuk]

Marcelo,

Esse procedimento que você mencionou é exatamente o que citei anteriormente para o caso de a/b.
Porém o que você exemplificou só funciona com divisor b constante em tempo de compilação.

+++

ueh, se vc sabe como funciona, pq perguntou se continuaria sendo feita a divisao 1/b? :B

mas note que quando falo que a/b pode ser substituido por a*(1/b), estou falando que vc vai usar a*c, onde c = 1/b, embora essa ultima informacao deva ser *ignorada*: a/b eh como goto, sempre te um jeito de escrever a mesma coisa de uma forma mais elegante, rapida e facil. tb nao estamos falando necessariamente em b constante ou em otimizacao em tempo de compilacao, bem pq nao existe esse tipo de otimizacao automatica em verilog (o operando / nao eh sintetizavel). de fato, se vc procurar no vasto mercado low-end (microcontroladores de 8 bits), vc praticamente nao encontra suporte a multiplicacao e divisao. ao mesmo tempo, se vc procurar no lucrativo mercado high-end (DSPs e FPGAs), vc soh encontra suporte a multiplicadores, obviamente pq ninguem tem necessidade de divisores. mas alem de ser uma limitacao de software e hardware, tem que pensar em algo muito mais obvio: no proprio exemplo do filtro, o que seria melhor? usar x*1.86 ou usar x/0.537? o coeficiente nem precisa ser calculado em realtime e para mim nao refresca em nada a parte de realtime se eu nao tenho suporte a ponto flutuante. e disso fica facil concluir que a/b nao eh realmente uma necessidade real. ao inves disso, converter numeros de ponto flutuante em ponto fixo eh algo muito mais importante, dada a vasta disponibilidade de hardware otimizado para isso.

de qq forma, mesmo que ponto flutuante nao fosse o problema, seria mais eficiente fazer x*1.86.

e nem eh um problema novo, a galera de supercomputacao jah chegou a mesma conclusao na decada de 70: no cray-1, existia um tal de "Reciprocal Approximation Unit", que calculava o reciproco c = 1/b e entao usava a*c, justamente pq o calculo do reciproco alem de demorar 14x mais, era muito raramente utilizado !

[chrdcv]

Marcelo SAM*,

Eu sou burro, e não sei como vc chegou que 1.86*x[1] ~ (60948*x[1])>>15 .
Além de explicar por gentileza como chegou a essa aproximação, teria como indicar livros onde consigo formalmente tais artifícios? Pq. não 60928 ou 61183 já que o shift à esquerda manda todos os outros bits para o saco?

Obrigado!

[andre_luis]

...que calculava o reciproco c = 1/b e entao usava a*c, justamente pq o calculo do reciproco alem de demorar 14x mais, era muito raramente utilizado...

Agora é que entendi o que você quiz dizer com o tal recíproco, mas confesso que foi por dedução.

Nada mais é que a busca de valores numa tabela ( look-up table ), mas isso não é propriamente um cálculo.
Além disso, quanto maior fosse a precisão necessária, mais gigantesca teria de ser a magnitude da memória.


+++

[pbernardi]

Marcelo SAM*,

Eu sou burro, e não sei como vc chegou que 1.86*x[1] ~ (60948*x[1])>>15 .
Além de explicar por gentileza como chegou a essa aproximação, teria como indicar livros onde consigo formalmente tais artifícios? Pq. não 60928 ou 61183 já que o shift à esquerda manda todos os outros bits para o saco?

Obrigado!

chrdcv, é nada mais do que multiplicar por 32768/32768, ou seja, 1: ((1.86*32768*x[1]) / 32768) => (60984*x[1]) >> 15. O shift a esquerda é feito por último na operação para manter a precisão.

[msamsoniuk]

...que calculava o reciproco c = 1/b e entao usava a*c, justamente pq o calculo do reciproco alem de demorar 14x mais, era muito raramente utilizado...

Agora é que entendi o que você quiz dizer com o tal recíproco, mas confesso que foi por dedução.

Nada mais é que a busca de valores numa tabela ( look-up table ), mas isso não é propriamente um cálculo.
Além disso, quanto maior fosse a precisão necessária, mais gigantesca teria de ser a magnitude da memória.

+++

com lookup table daria para fazer a/b em dois clocks: 1 clock para achar c=1/b e 1 clock para fazer a*c. mas a lookup table teria que ser proporcional ao tamanho do inteiro: para 16 bits, teria 128KB, o que eh um grande desperdicio. provavelmente seria possivel ter uma lookup table menor e interpolar, mas a perda de precisao eh obvia. ao inves disso, existe um metodo que eu acho bem interessante, eh o metodo que costuma ser utilizado para multiplicar por microcodigo, que no caso consiste em um loop com shift e add. por exemplo 1100 x 1001, vc tem 1100 q eh o valor a ser multiplicado e entao multiplica bit a bit pelo outro operando:

1100 x 0001 = 00001100
1100 x 0000 = 00000000
1100 x 0000 = 00000000
1100 x 1000 = 01100000

na pratica o outro operando bit a bit eh sempre um valor 2^n, portanto vira um shift. somando os resultados vc tem o resultado final: 01101100. e de fato, 0xc x 0x9 = 0x6c. se tiver poucos recursos, implementa passo a passo (shift + add) e 16x16=32 bits vao resultar em 16 clocks. se tiver hardware suficiente, pode fazer em paralelo, em um clock.

no caso da divisao, temos um shift e sub, por exemplo 01101100 / 1100, teriamos que shiftar o cara que divide para ter as parcelas e subtrair condicionalmente do cara a ser dividido:

01101100 - 01100000 = 00001100 -> mascara = 1000 -> q = 1000
00001100 - 00110000 menor q zero, mascara 0100 descartada
00001100 - 00011000 menor q zero, mascara 0010 descartada
00001100 - 00001100 = 00000000 -> mascara = 0001 -> q = 1001

e temos 01101100 / 1100 = 1001. bom, em uma primeira instancia, nao vejo como paralelizar isso, entao tem q ir na sequencia, com os shifts e subs condicionais. se imaginar 32/16=16 bits, daria para trabalhar deterministicamente com 16 clocks. nao me parece tao ruim em termos de performance e nao gasta tanta memoria quanto uma lookup table. daria ateh p/ juntar as duas coisas: monta uma cache de reciprocos, consumindo uma fracao do tamanho da lookup table: se o numero esta na cache, ele obtem em 1 clock, senao ele calcula e armazena na cache. assim a divisao a/b com ambos variaveis seria de 1 a 16 clocks para achar c = 1/b e entao 1 clock para fazer a*c.

[msamsoniuk]

Marcelo SAM*,

Eu sou burro, e não sei como vc chegou que 1.86*x[1] ~ (60948*x[1])>>15 .
Além de explicar por gentileza como chegou a essa aproximação, teria como indicar livros onde consigo formalmente tais artifícios? Pq. não 60928 ou 61183 já que o shift à esquerda manda todos os outros bits para o saco?

Obrigado!

chrdcv, é nada mais do que multiplicar por 32768/32768, ou seja, 1: ((1.86*32768*x[1]) / 32768) => (60984*x[1]) >> 15. O shift a esquerda é feito por último na operação para manter a precisão.

http://www.elin.ttu.ee/~olev/lect1.pdf

o documento eh legal de forma geral, mas na pagina 28 tem a descricao do formato de ponto fixo "Q15"

[RobL]

Então:
O que o Marcelo quis dizer, com toda sua boa preleção, com 32 bits, para operações eventuais com ponto flutuante, faz-se uma FPU por software, com bom desempenho.
Não sejam induzidos a pensar que modernas FPUs operem com os pilares básicos apresentados que por outro lado enriqueceu o post e foi de bom proveito para muitos.
Se você precisar seguir um evento ou fenômeno cinemático, com previsão probabilística de trajetória em várias ciências, como das partículas, astronomia , radares militares ou até mesmo em certos games e fosse necessário pensar no consumo de energia, como no caso de aplicação em satélites ou em bases (locais) sem energia de concessionária, uma FPU pode tornar viável a aplicação, especialmente se necessitar de custo, da ordem de um Kinetis, usando um simples mortal como um Cortex M4 com FPU. Lembramos que nestas aplicações, com FPU, o núcleo fica liberado para outras tarefas.
Portanto, não perca seu emprego ou oportunidade :- Nunca diga ao seu chefe que FPU é coisa de veio.