Istnieje wiele szczegółów na temat dodatków typu lookahead, takich jak Kogge-Stone, Lander-Fischer itp. Na kursach CS uczelni. Są one określane jako „powszechne w branży”. Jednak nie mogę znaleźć żadnych dowodów (poza być może łańcuchem do noszenia w Manchesterze) z ostatnich czasów, że są one właściwie używane gdziekolwiek konkretnie. Wyszukiwarka Google zwraca tylko strony czasopism i badań naukowych. Podaje się co najwyżej hipotetyczne implementacje.
Moje pytanie brzmi: czy są jakieś konkretne miejsca / wdrożenia, które są używane add-lookahead? Czy są one nieistotne dla prawdziwego świata?
Odpowiedzi:
To proste pytanie z bardzo złożoną odpowiedzią.
Po pierwsze, trochę tła.
Rzeczywista konstrukcja VLSI jest niezwykle techniczną dziedziną, w której stale zmienia się równowaga kompromisów. Czas, który obwód zajmuje do obliczenia odpowiedzi, rzadko jest jedynym ważnym czynnikiem. Istnieje również pobór mocy i obszar fizyczny, a także szereg czynników, które ujawniają, że projektowane obwody są w rzeczywistości analogowe (np. Rezystancja drutu, pojemność pasożytnicza). Wszystkie te są ważne w rzeczywistym obwodzie i mogą mieć wpływ na wybór projektu.
Po drugie, musisz wziąć pod uwagę cały cykl życia projektu. Dodatek odpowiedni dla realizacji VLSI może nie być odpowiedni dla realizacji FPGA. Jeśli projekt przejdzie fazę testowaną na FPGA ... otrzymujesz obraz.
Po trzecie, nie każdy sumator jest równy. Na typowym procesorze jest wiele dodatków, które wykonują różne zadania; prawdopodobnie istnieje kilka liczb całkowitych ALU, zmiennoprzecinkowy sumator mantysy, sumator, który dokonuje obliczenia adresu, sumator, który oblicza cele gałęzi i tak dalej. To nie liczy dodawania przeniesienia, które można znaleźć w nowoczesnych jednostkach mnożenia. Każda ma swoje osobliwości i ograniczenia.
Na przykład obliczanie celu rozgałęzienia zwykle obejmuje dodanie małej stałej do pełnego słowa, co sugeruje inny projekt sumatora niż ten, który dodaje dwa pełne słowa razem. Podobnie dodawanie zmiennoprzecinkowe wymaga etapu zaokrąglania po dodaniu, który może zająć mniej niż cykl, więc nie ma powodu, dla którego nie mógłbyś ukraść reszty cyklu, aby zakończyć dodawanie.
Wreszcie, a może przede wszystkim, duzi gracze (np. Intel, AMD, NVIDIA) są dość szczerzy na temat szczegółów implementacji niskiego poziomu z oczywistych powodów, chyba że uważają, że mogą uzyskać z tego papier i / lub patent. Nawet wtedy często nie jesteś pewien, co właściwie zrobili bez inżynierii odwrotnej.
To powiedziawszy, jest kilka rzeczy, które wiemy.
Kluczową rzeczą, którą musisz zdać sobie sprawę, jest to, że metody „noszenia z wyprzedzeniem” są elementami składowymi, a niekoniecznie metodami same w sobie. Analogia może być tutaj słuszna.
Jeśli myślisz o klasach algorytmów, prawdopodobnie nauczyłeś się kilku algorytmów sortowania, takich jak szybkie sortowanie, scalanie, wstawianie itd. W prawdziwym świecie, jeśli sortowanie jest wąskim gardłem w wydajności, każdy porządny inżynier pomyślałby o nich jako prymitywnych elementach, z których można zbudować „prawdziwy” rodzaj.
Na przykład algorytm sortowania ze standardowej biblioteki GNU C ++ używa szybkiego sortowania, używając wstawiania sortowania, gdy odstępy stają się wystarczająco małe. Jeśli jednak po kilku przejściach wygląda na to, że szybkie sortowanie partycjonowania uderzyło w zachowanie patologiczne, wraca do sortowania sterty. To trzy różne algorytmy sortowania, które pozwalają uzyskać jeden rodzaj siły przemysłowej.
To samo dotyczy obwodów sumujących. Wiadomo na przykład, że jednostka całkowita Pentium 4 zastosowała sumator Han-Carlsona, który jest mieszanką Kogge-Stone i Brent-Kung. (Han-Carlson jest szczególnie interesujący, ponieważ jest to „słaby punkt” w kompromisie między opóźnieniem propagacji a obszarem matrycy, który jest również dość energooszczędny.) Często opłaca się stosować kombinację kilku metod.
„Czyste” sumatory przenoszenia są nadal bardzo normą w obwodach syntezowanych (np. Jeśli podajesz operator Verilog „+” do Cadence lub Synopsys), jeśli chodzi o ręczne projektowanie, nowoczesne wysokiej klasy procesory z ich superskalarnymi wyjściami- Wydaje się, że silniki realizacji zamówień wydają się zmierzać w kierunku nieco innej konstrukcji swoich jednostek całkowitych.
Sumatory spekulacyjne to obwody, które mają wyjątkowo małe opóźnienie propagacji, ale działają poprawnie tylko przez pewien czas (typowo 95% czasu), i można bardzo mało logicznie stwierdzić, czy sumator spekulacyjny zwraca poprawny wynik, czy nie. Chodzi więc o to, aby wykonać spekulacyjny dodatek i połowę dodatku noszącego równolegle, w jednym cyklu. Jeśli dodatek spekulacyjny zwrócił poprawną odpowiedź, instrukcja jest wykonywana. W przeciwnym razie zablokuj rurociąg i wykonaj drugą połowę dokładnego dodania.
Ponieważ wiesz, że wolna ścieżka zajmie dwa cykle, projektanci mogliby zastosować więcej miejsca i energooszczędną metodę, nawet jeśli byłaby zbyt wolna do ogólnego użytku.
źródło
Tak, wiele komputerów używa dodatków typu carry-lookahead. Przeprojektowałem niektóre stare mikroprocesory i mogę podać kilka przykładów.
ALU na Intel 8008 (ich pierwszy 8-bitowy procesor) zawierał duży obwód przeniesienia, zaimplementowany z dynamiczną logiką. Obwód ten zajmował tyle samo przestrzeni na kości co sam ALU. Carry lookahead pokazano na arkuszu danych 8008 , rysunek 3. Nie widziałem żadnych innych procesorów z lat 70. ubiegłego wieku z funkcją look -head dla ALU, więc 8008 jest pod tym względem nieco niezwykły.
6502 wykorzystuje prymitywny element typu carry-lookahead dla modułu zwiększającego licznik programów (PC). Wykrywa, czy nastąpi przeniesienie z dolnego bajtu komputera i używa go do zwiększenia górnego bajtu. Zmniejsza to przenoszenie tętnienia z potencjalnie 16 bitów do 8 bitów. ALU 6502 używa przenoszenia tętnienia, chociaż logika przenoszenia jest odwrócona dla bitów naprzemiennych, co odcina falownik od ścieżki i czyni go nieco szybszym.
Z-80 ma 16-bitowy moduł zwiększania / zmniejszania używany do aktualizacji komputera, instrukcji inc / dec oraz licznika pętli. Wykorzystuje strukturę przenoszenia-przeskakiwania, więc przeniesienia są obliczane dla grup dwóch bitów. Ponadto wykorzystuje pewne przeniesienie lookahead do wygenerowania przeniesienia z bitów 0-7, 7-11 i 12-14. Inne linie są obliczane za pomocą fali tętnienia ( szczegóły ). Co zaskakujące, ALU Z-80 ma 4 bity, więc każda 8-bitowa operacja wykonuje dwa przejścia przez ALU.
Z drugiej strony model 8085 wykorzystuje funkcję tętnienia do 16-bitowego modułu inkrementującego / dekrementującego. Ale podobnie jak 6502, robi się to trochę przyspieszone, odwracając logikę przenoszenia na przemian.
ARM-1 ma ALU 32-bitową bez carry-uprzedzona, tylko tętnienia Carry. Wykorzystuje także sztuczkę polegającą na odwracaniu przenoszenia w naprzemiennych bitach.
W świecie minikomputerów wiele procesorów zbudowano z dobrze znanego 4-bitowego układu ALU 74181, który miał wewnętrzny układ przeniesienia. Przykłady obejmują Data General Nova, Xerox Alto, VAX-11/780 i TI-990. (Zobacz dłuższą listę na Wikipedii .) Niektóre z tych używanych tętnień przenoszą pomiędzy każdym 4-bitowym układem, a niektóre wykorzystują układ 74182 przenoszenia z wyprzedzeniem dla pełnego spojrzenia.
Podsumowując, różne mikroprocesory stosują różne techniki przenoszenia w zależności od ich celów wydajnościowych i operacji na krytycznej ścieżce. ALU może korzystać z pełnej anteny (np. 8008), a nawet może być o połowę mniejszy (jak Z-80). Inkrementator może stanowić problem z wydajnością, ponieważ zazwyczaj ma 8 bitów w 8-bitowym procesorze, co powoduje dwukrotne opóźnienie tętnienia. Inkrementator może mieć funkcję przenoszenia tętnienia (8085), jedną funkcję przenoszenia z wyprzedzeniem (6502) lub kilka etapów przenoszenia z wyprzedzeniem (Z-80).
źródło