Bir FPGA üzerindeki ikili işlem ağacının alan gereksinimini, bant genişliği pahasına, 2'den daha az bir faktörle azaltmak mümkün mü?

Question

Her saat döngüsünde, hesaplanacak N 32 bit girişlerin bulunduğu bir devrem var. İki 32-bit giriş alan ve bir 32-bit çıktı veren bir ikili işlem var. Bu işlem ilişkiseldir ve bir 32-bit çıktı elde etmek için onu tüm N 32-bit girişlerine uygulamak istiyorum. Şu anda bunu boru hattı ikili işlem ağacını uygulayarak gerçekleştiriyorum. varsayarak bir somut bir örnek olarak

, N = 4 ve daha sonra aşağıdaki yapacağını giriş {a, b, c, d} vardır:

a op b => reg1 
c op d => reg2 
reg1 op reg2 => result 

ağacındaki bir aşama ile bölünebilir değildir 2, ben sadece 1 giriş alır 1 üretim çıktı aynı gecikme ile bir kukla işlemi eklemek. Ben

sorun N'in girişler {9, 25, 49, 81, 121} birkaç boyutları ile am ilgili olmasıdır. Diğer tüm boyutlar kolayca sığarken, N, 121'in en büyük boyutu, FPGA kumaşımda% 110 lut gerektirir. Bu ikili operasyonların ağacı, tasarımımdaki en büyük lutsur tüketicisidir.

benim gemide ikamet eden op devrelerinin sayısını yarıya indirme yoluyla neredeyse yarı yarıya LUTS'un kullanımını azaltmak ve onların girişlerini multiplexing'i olabilir farkındayım. Ne yazık ki, bu sadece her saat döngüsünün sonucunu almak ve bant genişliğini yarıya indirmek anlamına gelir. tam ağaç tahtası teklifler daha sadece ~% 10 daha fazla kaynak gerektirdiğinden

, bant genişliği% 50 azalma bir vuruş çok önemli gibi görünüyor. Bant genişliğinde ince taneli küçültme için daha ince taneli küçültme işleminin yapılabildiği bir mimari var mı?

Answer 1

Tamam, 9 girişleri ile örnek aldı ve ikili operatörlerin% 75 ile ikili ağaç sorunu çözmek için çalıştı.

Ben girişleri a,b,c,d,e,f,g,h,i isim. Giriş değerlerini zaman içinde ayırt etmek için, a.

a' = a at time 1 
a''' = a at time 3 
(ab)' = result of a' and b' 

9 giriş 8 ikili işlem gerektirir. İşlem planımı 6 operatörle sınırlandırıyorum, bu yüzden gerekli operatörlerin% 75'ini kullanıyor. Aşağıdaki şemadaki her satır bir operatör temsil eder.

time 1  time 2   time 3   time 4    | time 1+4 
a'b'  (abcd)'(efgh)' (ab)''(cd)''  e'''f'''   | a'b' 
c'd'  (abcdefgh)'i' (ef)''(gh)''  g'''h'''   | c'd' 
e'f'  a''b''   (abcd)''(efgh)'' (ab)'''(cd)'''  | e'f' 
g'h'  c''d''   (abcdefgh)''i'' (ef)'''(gh)'''  | g'h' 
(ab)'(cd)' e''f''   a'''b'''   (abcd)'''(efgh)''' | (ab)'(cd)' 
(ef)'(gh)' g''h''   c'''d'''   (abcdefgh)'''i''' | (ef)'(gh)' 

4 döngüden sonra, şema yinelenir. Böylece 3 giriş kümesinin işlenmesi 4 döngü gerektirir:
=>% 33 ek yük.

Bu şema sıralanabilir, böylece her satır yalnızca 2 farklı giriş gerçekleştirir:
=> giriş 2: 1 çoklayıcı ile karıştırılabilir.

time 1  time 2   time 3   time 4    | time 1+4 
a'b'  a''b''   a'''b'''   (ab)'''(cd)'''  | a'b' 
c'd'  c''d''   c'''d'''   (ef)'''(gh)'''  | c'd' 
e'f'  e''f''   (ab)''(cd)''  e'''f'''   | e'f' 
g'h'  g''h''   (ef)''(gh)''  g'''h'''   | g'h' 
(ab)'(cd)' (abcd)'(efgh)' (abcd)''(efgh)'' (abcd)'''(efgh)''' | (ab)'(cd)' 
(ef)'(gh)' (abcdefgh)'i' (abcdefgh)''i'' (abcdefgh)'''i''' | (ef)'(gh)' 

Ben hiç hata yapmadı olursa, bu işlem ağı olmalıdır:

(tıklanabilir)

Answer 2

Eğer 3, 4, 5 veya 6 giriş operatörleri kullanarak düşündünüz mü? Mevcut Altera ve Xilinx FPGA'larındaki LUT'ler 6 girdidir. senin operatörler (eğer boru hattının her aşamasını kayıt varsayarak sadece 6 giriş işlevi yerine bir 2 giriş işlevini kullanarak mevcut uygulamada olan versiyonlarını çok israf olabilir (XOR, yani. AND, OR) gerçekten basit ise). Bu, ikili ağacınızı k-ary işlem ağacına dönüştürür. senin rakamlarla

N.

seçimine bağlı olarak pek çok LUT'u harcayayım ki burada mantıklıdır K seçimlerdir:

N | K | LUTs/bit | LUTs | LUTs/bit @k=2 | LUTs @k=2 
-----|---|----------|------|---------------|----------- 
9 | 3 |  4 | 128 |  11  | 352 
25 | 5 |  6 | 192 |  25  | 800 
49 | 5 | 13 | 416 |  50  | 1600 
81 | 6 | 18 | 576 |  75  | 2400 
121 | 6 | 26 | 832 |  123  | 3936