Desain firmware FPGA: Seberapa besar terlalu besar?

12

Saya memiliki transformasi pemrosesan sinyal besar yang perlu porting dari matlab ke VHDL. Ini pasti membutuhkan semacam berbagi sumber daya. Sedikit perhitungan memberi saya hal berikut:

  • 512 ffts dari 64-poin
  • 41210 operasi tambah banyak

Mengingat Virtex 6 FPGA terbesar memiliki ~ 2000 blok DSP48E, saya tahu bahwa saya dapat berbagi sumber daya untuk menggunakan kembali sumber daya beberapa kali. Waktu eksekusi tidak terlalu menjadi masalah, waktu pemrosesan dapat berlangsung relatif lama dalam hal FPGA.

Melihat penggunaan sumber daya, menggunakan arsitektur lite radix-2 membuat saya 4dsp blok / operasi FFT = 2048 blok DSP, total ~ 43k. Virtex FPGA terbesar memiliki 2k blok, atau 20 operasi / mux.

Jelas termasuk muxes besar seperti itu ke dalam kain juga akan mengambil irisan. Di mana saya menemukan batas atas batas ini? Saya tidak bisa berbagi sumber daya FPGA tanpa batas. Apakah 41210 pengganda terlalu besar? Bagaimana saya menghitung apa yang terlalu besar?

Saya juga melihat sumber daya lain (Irisan, Brams, dll). Radix-2 Lite juga memberikan 4 x 18r brams / fft = 2048 brams Xilinx FPGA terbesar berisi 2128 Brams. sangat perbatasan. Saya khawatir bahwa desain saya terlalu besar.


MEMPERBARUI:

Beberapa info lebih lanjut tentang desain itu sendiri. Saya tidak bisa menjelaskan secara detail, tetapi inilah yang bisa saya berikan:

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

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

output datarate spec: "lebih cepat dari simulasi matlab"

perhitungan bijak, ini adalah tempat saya:

Tahap FFT: mudah. Saya bisa menerapkan 1/2/4/8 FFT, menyimpan hasilnya di SDRAM dan akses nanti. Relatif kecil, meskipun butuh waktu lama, tidak apa-apa. menggunakan radix-2 lite saya bisa mendapatkan 2 DSP48Es dan 2 18k BRAMS / FFT. streaming memberi 6 DSP48Es 0BRAMS / FFT. dalam kedua kasus, FFT 64 poin kecil dalam istilah sumber daya FPGA.

Pengganda : ini masalah saya. Input multiplikasi diambil dari tabel pencarian atau data FFT. Ini benar-benar hanya sejumlah multiply-add. Tidak banyak yang bisa dioptimalkan. Bukan filter, tetapi memiliki karakteristik yang mirip dengan filter.

Mempertimbangkan pembagian sumber daya pada FPGA, matematika bekerja sebagai berikut: One LUT-6 dapat digunakan sebagai mux 4 arah. Rumus untuk N-way, M bit mux adalah sebagai berikut:

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

menghitung angka untuk implementasi saya tidak memberikan hasil yang baik. 90% dari keluarga virtix-6 tidak memiliki cukup irisan untuk berbagi sumber daya DSP mereka untuk melakukan operasi 40k.

stanri
sumber
Bentuk berbagi sumber daya yang paling efisien adalah serialisasi parsial di mana Anda dapat mengakses data dengan mengatasi memori. Tentu saja, pada titik ekstrem ini Anda kembali ke prosesor program tersimpan konvensional - kurangnya persyaratan kinerja yang keras mulai mengarah kembali ke fleksibilitas implementasi perangkat lunak yang mungkin berjalan di cloud komputasi.
Chris Stratton
1
Ini bukan bagian dari pertanyaan Anda, tetapi dalam perhitungan sumber daya Anda, Anda tidak menyatakan ukuran operan apa. 512 FFT x 64 poin x berapa banyak bit? Dalam FPGA, ukuran operan sepenuhnya terserah Anda, jadi Anda harus mempertimbangkannya saat menghitung ukuran masalah Anda.
The Photon
Saya tidak tahu apakah Anda menyadarinya, tetapi FPGA besar itu cukup mahal. Beberapa dapat di atas $ 5k. Mungkin Anda harus mempertimbangkannya juga, kecuali jika biaya tidak menjadi masalah.
Gustavo Litovsky
1
Sayangnya di luar saran solusi alternatif yang Anda dapatkan dalam jawaban sejauh ini, saya ragu apakah kami dapat melakukan lebih banyak untuk Anda. Maksud saya, Anda bisa membuat hanya satu inti FFT dan menjalankan 512 input Anda melaluinya satu demi satu, dan jelas itu akan cocok bahkan dengan FPGA yang cukup kecil. Di suatu tempat antara itu dan melakukan segala sesuatu secara paralel adalah keseimbangan yang tepat antara kecepatan vs sumber daya untuk aplikasi Anda ... tetapi sulit bagi siapa pun kecuali Anda untuk mengatakan di mana keseimbangan itu seharusnya.
The Photon
1
Apakah Anda memiliki nomor anggaran untuk ini? Seperti Gustavo tunjukkan, FPGA high-end mahal, seperti halnya mengembangkan PCB untuk diduduki. Sementara hanya menggandakan (atau empat kali lipat atau ...) jumlah perangkat keras komputasi dan terus menggunakan yang sudah ada, terbukti (?), Kode Matlab mungkin bisa memenuhi spesifikasi kecepatan seperti yang diberikan.
The Photon

Jawaban:

8

Saya ingin tahu apakah ada cara lain untuk melihat masalah?

Memainkan estimasi Anda dari operasi FFT 512 (masing-masing 64 poin) dan operasi MAC 42k ... Saya kira ini yang Anda butuhkan untuk satu kali melewati algoritma?

Sekarang Anda telah menemukan inti FFT menggunakan 4 unit DSP ... tetapi berapa banyak clock cycle yang dibutuhkan per FFT? (throughput, bukan latensi)? Katakanlah 64, atau 1 siklus per poin. Maka Anda harus menyelesaikan operasi 42k Mac dalam 64 siklus - mungkin 1k MAC per siklus, dengan setiap MAC menangani 42 operasi.

Sekarang saatnya untuk melihat sisa algoritma secara lebih rinci: mengidentifikasi bukan MAC tetapi operasi tingkat yang lebih tinggi (penyaringan, korelasi, apa pun) yang dapat digunakan kembali. Bangun inti untuk masing-masing operasi ini, dengan usabilitas ulang (mis. Filter dengan set koefisien yang dapat dipilih berbeda) dan segera Anda mungkin menemukan relatif sedikit multiplexer diperlukan di antara inti yang relatif besar ...

Juga, adakah pengurangan kekuatan mungkin? Saya punya beberapa kasus di mana perkalian dalam loop diperlukan untuk menghasilkan kuadrat (dan lebih tinggi). Membuka gulungannya, saya bisa membuatnya berulang-ulang tanpa multiplikasi: Saya cukup senang dengan diri saya sendiri pada hari saya membangun Difference Engine pada FPGA!

Tanpa mengetahui aplikasinya, saya tidak dapat memberikan rincian lebih lanjut tetapi beberapa analisis semacam itu kemungkinan membuat beberapa penyederhanaan utama menjadi mungkin.

Juga - karena kedengarannya seolah-olah Anda tidak memiliki platform yang pasti - pertimbangkan apakah Anda dapat mempartisi di beberapa FPGA ... lihat board ini atau ini yang menawarkan beberapa FPGA dalam platform yang nyaman. Mereka juga memiliki papan dengan 100 perangkat Spartan-3 ...

(ps saya kecewa ketika orang-orang perangkat lunak menutup pertanyaan lain ini - saya pikir itu setidaknya sesuai di sana)

Sunting: sunting kembali - saya pikir Anda mulai ke sana. Jika semua input pengali adalah output FFT, atau koefisien "tidak-filter", Anda mulai melihat jenis keteraturan yang perlu Anda eksploitasi. Satu input untuk setiap multiplier terhubung ke output FFT, input lainnya ke koefisien ROM (BlockRam diimplementasikan sebagai array konstan).

Mengurutkan operasi FFT yang berbeda melalui unit FFT yang sama akan secara otomatis mengurutkan output FFT melewati pengganda ini. Mengurutkan koefisien yang benar ke dalam input MPY lainnya sekarang "hanya" masalah mengatur alamat ROM yang benar pada waktu yang tepat: masalah organisasi, bukan sakit kepala besar MUXes.

Pada kinerja: Saya pikir Dave Tweed sedang pesimis sia-sia - FFT mengambil n * log (n) operasi, tetapi Anda bisa memilih O (n) unit kupu-kupu dan siklus O (logN), atau unit O (logN) dan O ( n) siklus, atau kombinasi lain yang sesuai dengan sumber daya dan sasaran kecepatan Anda. Salah satu kombinasi tersebut dapat membuat struktur multiply pasca-FFT jauh lebih sederhana daripada yang lain ...

Brian Drummond
sumber
FFT yang diimplementasikan dengan satu kupu-kupu perangkat keras akan membutuhkan siklus clock NlogN untuk diselesaikan; untuk 512 poin, itu akan menjadi 256 * 8 kupu-kupu, atau 2048 jam. Itu berarti bahwa 41210 (atau 32768?) MAC hanya akan membutuhkan 8-10 pengganda perangkat keras untuk dilakukan dalam jumlah waktu yang sama.
Dave Tweed
Maksud saya, 16-20 pengganda.
Dave Tweed
Maaf, saya baru sadar bahwa saya mendapatkannya mundur. FFT indiivdual adalah 64 poin, jadi implementasi single-butterfly akan membutuhkan 32 * 5 = 160 jam. MAC kemudian dapat dilakukan dengan pengganda perangkat keras 200-250.
Dave Tweed
inilah yang membuatku bingung. Bagaimana xilinx mendesain inti yang mampu melakukan 16k / 32k ffts yang membutuhkan 400k operasi penambahan-tambah (NlogN), namun saya masih berjuang dengan 41k saya? pasti ada jalan!
stanri
@ Dave: Saya yakin maksud Anda adalah 160 perkalian, bukan 160 siklus, tentunya? Tidak ada yang secara inheren bersambung dalam FFT ...
Brian Drummond
2

Jika masalah ini tidak memiliki kendala realtime yang sulit, dan sepertinya tidak - Anda hanya ingin menjalankannya "lebih cepat", maka sepertinya itu mungkin cukup menerima akselerasi pada satu atau lebih GPU. Ada beberapa pustaka perangkat lunak yang membuat ini proposisi yang relatif mudah, dan ini akan menjadi sekitar urutan besarnya lebih mudah daripada langsung ke perangkat keras FPGA kustom.

Hanya Google untuk "perpustakaan yang mengaktifkan GPU" atau "perpustakaan yang dipercepat GPU" untuk memulai.

Dave Tweed
sumber
Yang cukup menarik, saya menyebutkan GPU kepada klien ketika saya mendengar tentang proyek ini, dan dia tidak tertarik.
stanri
@StaceyAnneRieck: Apa dia bilang kenapa?
Dave Tweed
Dia tidak benar-benar mengatakan mengapa, hanya saja dia telah melihatnya sebelum menggunakan FPGA sepertinya kurang berhasil, tampaknya. Saya harus membawanya lagi.
stanri
@stanri: Bahkan jika Anda akhirnya berakhir dalam implementasi FPGA, menurut saya GPU mungkin merupakan cara yang baik untuk "papan tempat memotong roti" arsitektur sistem secara keseluruhan. Apakah Anda memiliki (dan dapatkah Anda membagikan?) Semacam grafik aliran data tingkat tinggi untuk algoritme, dan dapatkah Anda memberi kami gambaran tentang jumlah data yang terlibat? Tanpa jawaban untuk pertanyaan seperti ini, akan sangat sulit untuk memberi Anda apa pun selain saran yang sangat umum.
Dave Tweed
Sebenarnya ini adalah algoritma yang sangat sangat sederhana, hanya skala yang membuatnya sangat rumit. Pada dasarnya sebagai berikut: kondisi awal -> 512 ffts secara paralel -> 32768 operasi berlipat ganda pada keluaran FFT -> sesuaikan kondisi awal -> bilas dan ulangi
stanri
1

Dimungkinkan untuk menggunakan perangkat keras khusus atau FPGA (atau bahkan CPLD) untuk sangat mempercepat beberapa jenis operasi matematika. Hal utama yang perlu diingat ketika mencoba merancang perangkat keras (sirkuit atau logika FPGA) untuk mempercepat operasi matematika adalah untuk mencari tahu data pesanan apa yang perlu masuk dan keluar dari perangkat Anda. Perangkat dengan tata letak I / O yang efisien dapat menawarkan kinerja yang jauh lebih baik daripada yang memiliki tata letak yang tidak efisien, bahkan jika perangkat yang terakhir membutuhkan lebih banyak sirkuit.

Saya belum mencoba merancang desain bantuan perangkat keras untuk FFT, tetapi yang saya lihat adalah bantuan perangkat keras untuk operasi multiplikasi besar (seperti yang mungkin digunakan untuk enkripsi RSA). Banyak mikrokontroler, bahkan yang memiliki hardware perkalian cepat khusus, tidak terlalu efisien pada operasi seperti itu karena mereka memerlukan banyak pengocokan register. Perangkat keras yang dirancang untuk meminimalkan swapping register dapat mencapai kinerja yang jauh lebih baik dengan operasi multiplikasi multi-presisi, bahkan jika perangkat keras itu sendiri tidak secanggih itu. Sebagai contoh, perangkat keras yang dapat melakukan perkalian 16xN pipelined dua bit pada satu waktu (menggeser dalam dua bit lebih rendah dari multipland, dan menggeser keluar dua bit atas hasil) dapat mencapai kinerja yang lebih baik daripada perangkat keras yang dapat melakukan penggandaan 8x8 dalam satu siklus, meskipun yang pertama mungkin membutuhkan lebih sedikit sirkuit (dan, berdasarkan pipelining, memiliki jalur data kritis yang lebih pendek). Kuncinya adalah untuk mencari tahu seperti apa "loop dalam" dari kode yang diperlukan akan terlihat, dan mencari tahu apakah ada inefisiensi yang dapat dengan mudah dihilangkan.

supercat
sumber
Jenis operasi apa yang sangat cocok untuk bentuk optimasi ini? Saya telah mengedit pertanyaan di atas untuk sedikit lebih detail tentang sifat operasi penggandaan. Desain hardware-assist terdengar sangat menarik!
stanri
0

Seberapa kecil masalah waktu eksekusi kami?

Ini benar-benar tampak seperti situasi di mana Anda harus benar-benar mengimplementasikan soft-MCU, FPGA dengan hard-MCU terintegrasi, atau bahkan perangkat MCU terpisah, dan membuat serial semua operasi Anda.

Dengan asumsi Anda memiliki waktu eksekusi, melakukan FFT Anda dalam perangkat lunak akan jauh lebih mudah untuk di-debug, dan mungkin jauh lebih mudah untuk dirancang juga.

Connor Wolf
sumber
1
Melakukan perhitungan berat dalam CPU soft core pada FPGA itu konyol; jika Anda akan melakukan perhitungan dalam arsitektur program yang tersimpan (sesuatu yang harus dipertimbangkan), karena itu pada cpu kinerja tinggi / dolar di mana Anda tidak membayar penalti kecepatan dari logika fleksibel melalui perbandingan-fab- logika keras generasi.
Chris Stratton
@ ChrisStratton - Poin bagus. Menambahkan catatan tambahan untuk efek itu.
Connor Wolf
1
Bahkan built-in hard-CPU tidak akan tahan untuk komoditas konvensional prosesor / GPU untuk tugas-tugas berbasis perangkat lunak, dan akan menelan biaya lebih drastis.
Chris Stratton
@ ChrisStratton - Saya pikir arsitektur hard-CPU terintegrasi yang paling umum adalah ARM atau POWER? Dalam hal ini, itu pada dasarnya adalah CPU komoditas.
Connor Wolf
1
Dengan pertanyaan FPGA Anda yang lain, membangun papan FPGA kemungkinan merupakan pengalaman belajar yang biayanya sedikit lebih besar dari perkiraan. Saya pikir hal yang harus dilakukan pada saat ini adalah memberi klien beberapa harga keras / angka kinerja dari cloud run komputasi percobaan (yang akhirnya bisa menjadi perangkat keras yang dibeli), vs beberapa gagasan tentang harga yang lebih tinggi dan risiko yang jauh lebih tinggi dari upaya FPGA .
Chris Stratton