Design de firmware FPGA: Quão grande é muito grande?

12

Eu tenho uma transformação de processamento de sinal particularmente grande que precisa ser portada do matlab para o VHDL. Definitivamente requer algum tipo de compartilhamento de recursos. Um pouco de cálculo me deu o seguinte:

  • 512 pés de 64 pontos
  • 41210 operações de adição múltipla

Considerando que o maior FPGA do Virtex 6 possui ~ 2000 blocos DSP48E, eu sei que posso compartilhar recursos para reutilizar os recursos várias vezes. O tempo de execução não é realmente um problema, o tempo de processamento pode demorar relativamente em termos de FPGA.

Observando o uso de recursos, o uso da arquitetura radix-2 lite me dá blocos 4dsp / operação FFT = 2048 blocos DSP, um total de ~ 43k. O maior Virtex FPGA possui 2k blocos, ou 20 operações / mux.

Obviamente, incluir esses muxes grandes no tecido também vai ocupar fatias. Onde encontro a extremidade superior desse limite? Não posso compartilhar infinitamente os recursos do FPGA. Os multiplicadores 41210 são muito grandes? Como calculo o que é muito grande?

Eu também procurei outros recursos (Slices, Brams, etc.). O Radix-2 Lite também fornece 4 x 18k brams / fft = 2048 brams o maior Xilinx FPGA contém 2128 Brams. muito limítrofe. Estou preocupado que meu design seja grande demais.


ATUALIZAR:

Mais algumas informações sobre o design em si. Não posso entrar em detalhes, mas aqui está o que posso dar:

Initial conditions -> 512 ffts -> 40k multipliers ---------|----> output data to host 

                 ^------re-calculate initial conditions----|

output datarate spec: "mais rápido que a simulação matlab"

cálculos sábios, é aqui que estou:

FFT: fácil. Posso implementar 1/2/4/8 FFTs, armazenar os resultados na SDRAM e acessar mais tarde. Relativamente pequeno, mesmo que demore, está tudo bem. usando radix-2 lite, posso obter 2 DSP48Es e 2 18k BRAMS / FFT. o streaming fornece 6 DSP48Es 0BRAMS / FFT. nos dois casos, a FFT de 64 pontos é pequena em termos de recursos do FPGA.

Multiplicadores : este é o meu problema. As entradas de multiplicação são obtidas das tabelas de pesquisa ou dos dados FFT. É realmente apenas um monte de multiplicações. Não há muito para otimizar. Não é um filtro, mas possui características semelhantes a um filtro.

Considerando o compartilhamento de recursos no FPGA, a matemática funciona da seguinte maneira: Um LUT-6 pode ser usado como um mux de quatro direções. A fórmula para um N-way, M bit mux é a seguinte:

N*M/3 = number of luts, or N*M/12 = slices (4 LUTS/slice).

analisar os números da minha implementação não dá bons resultados. 90% da família virtix-6 não possui fatias suficientes para compartilhar seus DSPs de recursos, a fim de executar operações de 40k.

Stanri
fonte
As formas mais eficientes de compartilhamento de recursos são a serialização parcial, na qual você pode acessar dados endereçando a memória. É claro que, no extremo disso, você está de volta a um processador de programa armazenado convencional - a falta de requisitos de alto desempenho começa a apontar para a flexibilidade de uma implementação de software que talvez esteja sendo executada em uma nuvem de computação.
Chris Stratton
1
Isso não faz parte da sua pergunta, mas no cálculo de recursos você não indicou qual operando de tamanho. 512 FFTs x 64 pontos x quantos bits? Em um FPGA, o tamanho do operando depende totalmente de você; portanto, você deve considerá-lo ao descobrir o tamanho do seu problema.
The
Não sei se você percebeu, mas esses grandes FPGAs são muito caros. Alguns podem estar acima de US $ 5k. Talvez você deva considerar isso também, a menos que o custo não seja um problema.
Gustavo Litovsky
1
Infelizmente, além das sugestões de soluções alternativas que você obteve nas respostas até agora, duvido que possamos fazer muito mais por você. Quero dizer, você poderia criar apenas um núcleo de FFT e executar suas 512 entradas através dele, uma após a outra, e obviamente isso caberia até em um FPGA bastante pequeno. Em algum lugar entre isso e fazer tudo em paralelo está o equilíbrio certo de velocidade versus recursos para o seu aplicativo ... mas é difícil para qualquer um, exceto você, dizer onde esse equilíbrio deve estar.
The Photon
1
Você tem um número de orçamento para isso? Como Gustavo apontou, os FPGAs avançados são caros, assim como o desenvolvimento de um PCB para os sentar. Enquanto apenas dobrar (ou quadruplicar ou ...) a quantidade de hardware de computação e continuar usando o já existente (?), O código Matlab provavelmente atenderá às especificações de velocidade fornecidas.
The Photon

Respostas:

8

Gostaria de saber se existe outra maneira de encarar o problema?

Jogando fora a sua estimativa de 512 operações FFT (64 pontos cada) e 42k operações MAC ... Presumo que é isso que você precisa para uma passagem pelo algoritmo?

Agora você encontrou um núcleo FFT usando 4 unidades DSP ... mas quantos ciclos de clock são necessários por FFT? (taxa de transferência, não latência)? Digamos 64, ou 1 ciclo por ponto. Então você precisa concluir essas operações de 42k Mac em 64 ciclos - talvez 1k MACs por ciclo, com cada MAC lidando com 42 operações.

Agora é hora de analisar o restante do algoritmo em mais detalhes: identifique não os MACs, mas as operações de nível superior (filtragem, correlação, qualquer que seja) que possam ser reutilizadas. Crie núcleos para cada uma dessas operações, com capacidade de reutilização (por exemplo, filtros com diferentes conjuntos de coeficientes selecionáveis) e em breve você poderá encontrar relativamente poucos multiplexadores entre núcleos relativamente grandes ...

Além disso, é possível reduzir a força? Eu tive alguns casos em que eram necessárias multiplicações em loops para gerar quadráticos (e superiores). Desenrolando-os, eu poderia gerá-los iterativamente sem multiplicação: fiquei bastante satisfeito comigo mesmo no dia em que construí um Mecanismo de Diferenças no FPGA!

Sem conhecer o aplicativo, não posso fornecer mais detalhes, mas algumas dessas análises provavelmente tornarão possíveis algumas grandes simplificações.

Além disso - como parece que você não tem uma plataforma definida - considere se é possível particionar em vários FPGAs ... dê uma olhada nesta placa ou nesta que oferece vários FPGAs em uma plataforma conveniente. Eles também têm uma placa com 100 dispositivos Spartan-3 ...

(ps Fiquei desapontado quando o pessoal do software encerrou essa outra pergunta - acho que é pelo menos tão apropriado lá)

Editar: re sua edição - acho que você está começando a chegar lá. Se todas as entradas do multiplicador forem saídas FFT ou coeficientes "sem filtro", você começará a ver o tipo de regularidade que precisa explorar. Uma entrada para cada multiplicador se conecta a uma saída FFT, a outra entrada a uma ROM de coeficiente (BlockRam implementado como uma matriz constante).

Seqüenciar operações FFT diferentes pela mesma unidade FFT sequenciará automaticamente as saídas FFT após esse multiplicador. A sequência dos coeficientes corretos nas outras entradas MPY agora é "meramente" uma questão de organizar os endereços ROM corretos no momento correto: um problema organizacional, em vez de uma enorme dor de cabeça de MUXes.

Sobre desempenho: acho que Dave Tweed estava sendo desnecessariamente pessimista - a FFT realizando n * log (n) operações, mas você pode escolher O (n) unidades de borboleta e O (logN) ciclos, ou O (logN) unidades e O ( n) ciclos ou alguma outra combinação para se adequar às suas metas de recursos e velocidade. Uma dessas combinações pode tornar a estrutura multiplicadora pós-FFT muito mais simples do que outras ...

Brian Drummond
fonte
Uma FFT implementada com uma única borboleta de hardware exigirá a conclusão dos ciclos de relógio NlogN; por 512 pontos, seriam 256 * 8 borboletas ou 2048 relógios. Isso significa que os MACs 41210 (ou 32768?) Exigiriam apenas de 8 a 10 multiplicadores de hardware para serem executados na mesma quantidade de tempo.
Dave Tweed
Quero dizer, 16-20 multiplicadores.
Dave Tweed
Desculpe, acabei de perceber que entendi isso de trás para frente. As FFTs individuais são 64 pontos, portanto a implementação de borboleta única exigirá 32 * 5 = 160 relógios. Os MACs podem ser feitos com multiplicadores de hardware 200-250.
Dave Tweed
é isso que me surpreende. Como o xilinx pode projetar um núcleo capaz de realizar 16k / 32k ffts que exigem operações de adição e adição de 400k (NlogN) e, no entanto, estou lutando com meus 41k? deve haver um caminho!
Stanri
@ Dave: Eu acredito que você quer dizer 160 multiplicações, não 160 ciclos, com certeza? Não há nada tão inerentemente serializado em uma FFT ...
Brian Drummond
2

Se esse problema não tiver restrições rígidas em tempo real e parecer que não - você só quer que seja executado "mais rapidamente", parece que pode ser bastante favorável à aceleração em uma ou mais GPUs. Existem várias bibliotecas de software que tornam essa proposição relativamente direta, e isso seria uma ordem de magnitude mais fácil do que ir direto para o hardware FPGA personalizado.

Basta pesquisar no Google para "biblioteca ativada por GPU" ou "biblioteca acelerada por GPU" para começar.

Dave Tweed
fonte
Curiosamente, mencionei GPUs para o cliente quando soube desse projeto, e ele não estava interessado.
Stanri
@StaceyAnneRieck: Ele disse por quê?
Dave Tweed
Ele realmente não disse o porquê, apenas que ele examinou antes de usar um FPGA, aparentemente, parecia menos trabalhoso. Vou ter que trazer isso à tona novamente.
stanri
@stanri: Mesmo que você acabe em uma implementação de FPGA, parece-me que a GPU pode ser uma boa maneira de "integrar" a arquitetura geral do sistema. Você tem (e poderia compartilhar?) Algum tipo de gráfico de fluxo de dados de alto nível para o algoritmo e pode nos dar uma idéia da quantidade de dados envolvidos? Sem respostas para perguntas como essas, será realmente difícil dar a você algo além de conselhos muito genéricos.
Dave Tweed
Na verdade, é um algoritmo muito, muito simples, é apenas a escala que o torna tão complicado. Basicamente o seguinte: condições iniciais -> 512 FFTs em paralelo -> 32768 operações de multiplicar-se sobre a saída FFT -> ajustar as condições iniciais -> Enxágüe e repita
stanri
1

É possível usar um hardware especializado ou um FPGA (ou mesmo um CPLD) para acelerar bastante certos tipos de operações matemáticas. O principal aspecto a ser lembrado ao tentar projetar hardware (circuito ou lógica FPGA) para acelerar as operações matemáticas é descobrir em que ordem os dados precisarão entrar e sair do seu dispositivo. Um dispositivo com um layout de E / S eficiente pode oferecer desempenho muito melhor do que um com um layout ineficiente, mesmo se o último dispositivo exigir muito mais circuitos.

Não tentei elaborar um design de assistência de hardware para uma FFT, mas observei a assistência de hardware para grandes operações de multiplicação (como pode ser usado para criptografia RSA). Muitos microcontroladores, mesmo aqueles com hardware especial de multiplicação rápida, não são muito eficientes nessas operações, porque exigem muito embaralhamento de registros. O hardware projetado para minimizar a troca de registros poderia obter um desempenho muito melhor com operações de multiplicação de precisão múltipla, mesmo que o hardware em si não fosse tão sofisticado. Por exemplo, o hardware que pode executar uma multiplicação de 16xN em pipeline, dois bits de cada vez (alternando dois bits inferiores de várias plataformas e alternando dois bits superiores de resultado) pode obter um desempenho melhor do que o hardware que pode executar uma multiplicação 8x8 em um ciclo, mesmo que o primeiro possa usar menos circuitos (e, em virtude do pipelining, ter um caminho de dados críticos mais curto). A chave é descobrir como será o "loop interno" do código necessário e descobrir se há alguma ineficiência que possa ser facilmente eliminada.

supercat
fonte
Que tipos de operações são particularmente adequados para essa forma de otimização? Editei a pergunta acima para detalhar um pouco mais a natureza da operação de multiplicação. O design de assistência de hardware parece realmente interessante!
Stanri
0

Quão pouco nos importa o tempo de execução?

Isso realmente parece uma situação em que você realmente deve implementar um soft-MCU, um FPGA com um hard-MCU integrado ou até um dispositivo MCU separado e serializar todas as suas operações.

Supondo que você tenha tempo de execução, executar suas FFTs em software será muito mais fácil de depurar e provavelmente muito mais simples de projetar.

Connor Wolf
fonte
1
Fazer computação pesada em uma CPU de núcleo leve em um FPGA é bobagem; se você for fazer o cálculo em uma arquitetura de programa armazenada (algo que deve ser considerado), devido a CPU (s) de alto desempenho / dólar em que você não paga a penalidade de velocidade da lógica flexível em comparação com fab lógica rígida de geração.
Chris Stratton
@ ChrisStratton - Bom ponto. Adicionada uma nota adicional para esse efeito.
Connor Lobo
1
Mesmo as CPUs rígidas incorporadas não serão suficientes para processar processadores / GPUs convencionais para tarefas baseadas em software e custarão drasticamente mais.
Chris Stratton
@ ChrisStratton - Eu pensei que as arquiteturas de CPU rígida integradas mais comuns eram ARM ou POWER? Nesse caso, que basicamente é um CPU commodity.
Connor Wolf
1
Dada a sua outra pergunta sobre FPGA, a criação do quadro FPGA provavelmente será uma experiência de aprendizado que custará um pouco mais do que o estimado. Acho que o melhor a ser feito nesse momento seria fornecer ao cliente alguns números rígidos de preço / desempenho das execuções experimentais da nuvem de computação (que podem eventualmente se tornar o hardware adquirido), versus alguma idéia do preço mais alto e do risco muito maior do esforço do FPGA .
precisa saber é o seguinte