1 1 Systemy Dedykowane w Układach Programowalnych Ernest Jamro Dodawanie

2 2 Literatura Omondi A.R Computer Arithmetic Systems. Algorithms Architecture and Implementations, Prentice Hall 1994. Pirsch P., Architectures for Digital Signal Processing, Chichester UK, Wiley 1998. U.Mayer-Baese Digital Signal Processing with Field Programmable Gate Arrays, Springer, Berlin 2001 Keshab K. Parhi VLSI Digital Signal Processing Systems, J.Wiley & sons, 1999 Kazimierz Wiatr Akceleracja Obliczeń w systemach wizyjnych, WNT, W-wa 2003 E. Jamro, K. Wiatr, Układy mnożące przez stały współczynnik implementowane w układach programowalnych FPGA, http://home.agh.edu.pl/~jamro/2001KCM_pl.pdf http://home.agh.edu.pl/~jamro/2001KCM_pl.pdf www.xilinx.com www.altera.com

3 3 Układ dodający ze skrośną propagacją przeniesienia (Ripple Carry Adder) c i-1 \a i,b i 00011110 00101 11010 c i-1 \a i,b i 00011110 00010 10111 sisi cici a i + b i +c i-1 = s i + 2·c i s i = a i  b i  c i-1 c i = a i b i + a i c i-1 + b i c i-1 = a i b i + c i-1 (a i  b i )

4 4 Odejmowanie (a-b) c i-1 \a i,b i 00011110 00101 11010 c i-1 \a i,b i 00011110 00100 11110 sisi cici a i - b i -c i-1 = s i - 2·c i s i = a i  b i  c i-1 na czerwono różnica pomiędzy dodawaniem Kod uzupełnień do dwóch U2 bit znakunegacja każdego bitu Odejmowanie bezpośrednie Dodanie 1 na najmłodszej pozycji Zamiast odejmowania należy dokonać konwersji do kodu U2 liczby b oraz przeprowadzić zwykłą operację dodawania a+b’

5 5 Ripple Carry Adders in FPGAs s i = a i  b i  c i-1 Fragment of Virtex Configurable Logic Block (CLB)

6 6 Carry Skip Adder (CSA) (sumator z przeskokiem przeniesień) T n = A n + B n lub też T n = A n xor B n

7 7 Carry Skip Adder Koszt (powierzchnia – A) m- wielkość bitowa pojedynczego bloku Szybkość (czas propagacji - T) A  T= 1/Wydajność

8 8 Carry Select Adder

9 9 Altera Carry Select Adder układy Apex, Cyclon

10 10 Porównanie układów dodających o szerokości 16 bitów Układ OpóźnienieKoszt (A  T)[10 4 ] tylko Carry Look Ahead473922.94 Ripple CLA (m=4)103360.34 carry select (m=4)69920.6 carry skip152400.36 2-level carry skip123000.36 Ripple Carry312240.69 Układ OpóźnienieKoszt (A  T) [10 4 ] tylko Carry Look Ahead45062420.25 Ripple CLA (m=4)3413344.57 carry select (m=4)626881.61 carry skip299602.50 2-level carry skip2811403.19 Ripple Carry12789611.38 64 bity

11 11 Dodawanie 3-wejściowe z propagacją przeniesienia Carry Propagate Adder (CPA) CPA – układ dodający np. ze skrośną propagacją przeniesienia (Ripple Carry), Carry Look Ahead, Carry Select Adder S= A + B + C Przykład dla Ripple Carry Adder

12 12 Dodawanie 3-wejściowe Zachowywanie przeniesienia. Carry Save Adder (CSA) A+B+C= S + 2 ·T Bitowo a i + b i +c i = s i + 2·t i+1 s i = a i  b i  c i t i+1 = a i b i + a i c i + b i c i = a i b i + c i (a i  b i ) Nie ma propagacji przeniesienia Bardzo szybki układ dodający przy powierzchni podobnej jak Ripple- Carry Adder

13 13 CSA -Dodawanie wielowejściowe 3-wejścia4-wejścia6- wejść Niestety w układach FPGA ze względu na dedykowane układy dodające stosowanie CSA nie jest zalecana Uwaga: T ma wagę 2 i dla bitów najmłodszych i najstarszych powyższa struktura jest zakłócona

14 14 Materiały dodatkowe

15 15 Manchester Adder

16 16 Superblock of carry-skip adder

17 17 Superblock of carry-skip adder Czas propagacji

18 18 Carry Lookahead Adder S i = A i  B i  C i-1 C i = A i B i + A i C i-1 + B i C i-1 = A i B i + C i-1 (A i  B i ) G i = A i B i – Generate- Propagate P i = A i  B i - Propagate bo:- Generate S i = P i  C i-1 C i = G i + P i C i-1 S 0 = P 0  C -1 C 0 = G 0 + P 0 C -1 S 1 = P 1  C 0 C 1 = G 1 + P 1 C 0 = G 1 + P 1 (G 0 + P 0 C -1 )= G 1 + P 1 G 0 + P 1 P 0 C -1 S 2 = P 2  C 1 C 2 = G 2 + P 2 C 1 = G 2 + P 2 G 1 + P 2 P 1 G 0 + P 2 P 1 P 0 C -1

19 19 Carry-lookahead adder Sumator z antycypacją przeniesień

20 20 Ripple Carry-Lookahead Adder

21 21 RCLA koszt i szybkość Koszt A Czas prop. T A  T= 1/Wydajność