Dlaczego dodawanie jest tak szybkie, jak operacje bitowe w nowoczesnych procesorach?

Wiem, że operacje bitowe są tak szybkie na nowoczesnych procesorach, ponieważ mogą działać równolegle na 32 lub 64 bitach, więc operacje bitowe zajmują tylko jeden cykl zegara. Jednak dodawanie jest złożoną operacją, która składa się z co najmniej jednej, a być może nawet kilkunastu operacji bitowych, więc naturalnie myślałem, że będzie 3-4 razy wolniejszy. Byłem zaskoczony widząc po prostym teście porównawczym, że dodawanie jest tak szybkie, jak każda z operacji bitowych (XOR, OR, AND itd.). Czy ktoś może rzucić na to światło?

Dodawanie jest szybkie, ponieważ projektanci procesorów umieścili obwody potrzebne do szybkiego. Zajmuje znacznie więcej bramek niż operacje bitowe, ale dość często projektanci procesorów ocenili, że warto. Zobacz https://en.wikipedia.org/wiki/Adder_(electronics) .

Oba mogą być wykonane wystarczająco szybko, aby wykonać je w jednym cyklu procesora. Nie są równie szybkie - dodawanie wymaga więcej bramek i większego opóźnienia niż operacja bitowa - ale jest wystarczająco szybkie, aby procesor mógł to zrobić w jednym cyklu zegara. Narzut na opóźnienie dla instrukcji dla dekodowania instrukcji i logiki sterowania, a opóźnienie jest znacznie większe niż opóźnienie dla wykonania operacji bitowej, więc różnica między nimi zostaje zalana przez ten narzut. Odpowiedź AProgrammera i odpowiedź Paula92 dobrze wyjaśniają te efekty.

Istnieje kilka aspektów.

• Względny koszt operacji bitowej i dodatku. Naiwny sumator będzie miał głębokość bramki, która zależy liniowo od szerokości słowa. Istnieją alternatywne podejścia, bardziej kosztowne pod względem bramek, które zmniejszają głębokość (IIRC głębokość zależy wówczas logarytmicznie od szerokości słowa). Inni podali odniesienia do takich technik, zaznaczę tylko, że różnica jest również mniej ważna niż to, co mogłoby się wydawać, biorąc pod uwagę koszt operacji z powodu potrzeby logiki sterowania, która dodaje opóźnienia.

• Potem jest fakt, że procesory są zwykle taktowane (jestem świadomy pewnych badań lub projektów nie taktowanych specjalnego przeznaczenia, ale nie jestem nawet pewien, czy niektóre są dostępne komercyjnie). Oznacza to, że niezależnie od prędkości operacji, zajmie ona całkowitą wielokrotność cyklu zegara.

• Wreszcie są względy mikrotechniczne: czy jesteś pewien, że mierzysz to, co chcesz? Obecnie procesory są zwykle potokowe, wieloskalowe, z realizacją poza kolejnością i czymkolwiek innym. Oznacza to, że są w stanie wykonać kilka instrukcji jednocześnie, na różnych etapach realizacji. Jeśli chcesz pokazać na podstawie pomiarów, że operacja zajmuje więcej czasu niż inna, musisz wziąć pod uwagę ten aspekt, ponieważ ich celem jest ukrycie tej różnicy. Możesz mieć tę samą przepustowość dla operacji dodawania i operacji bitowych, gdy używasz niezależnych danych, ale miara opóźnienia lub wprowadzenie zależności między operacjami może wskazywać inaczej. Musisz także upewnić się, że wąskim gardłem twojego pomiaru jest wykonanie, a nie na przykład dostęp do pamięci.

Procesory działają cyklicznie. Na każdym cyklu coś się dzieje. Zwykle wykonanie instrukcji zajmuje więcej cykli, ale wiele instrukcji jest wykonywanych jednocześnie, w różnych stanach.

Na przykład prosty procesor może mieć 3 kroki dla każdej instrukcji: pobierz, uruchom i zapisz. W dowolnym momencie przetwarzane są 3 instrukcje: jedna jest pobierana, jedna jest wykonywana, a druga zapisuje jej wyniki. Nazywa się to potokiem i ma w tym przykładzie 3 etapy. Nowoczesne procesory mają rurociągi z ponad 15 etapami. Jednak dodawanie, jak również większość operacji arytmetycznych, są zwykle wykonywane w jednym etapie (mówię o operacji dodawania 2 liczb przez ALU, a nie o samej instrukcji - w zależności od architektury procesora instrukcja może wymagać więcej cykli pobierania argumentów z pamięci, wykonywania operacji warunkowych, przechowywania wyników w pamięci).

Czas trwania cyklu zależy od najdłuższej ścieżki krytycznej. Zasadniczo jest to najdłuższy czas niezbędny do ukończenia pewnego etapu rurociągu. Jeśli chcesz przyspieszyć procesor, musisz zoptymalizować ścieżkę krytyczną. Jeśli zmniejszenie ścieżki krytycznej per se nie jest możliwe, można ją podzielić na 2 etapy potoku i możesz teraz taktować procesor prawie dwukrotnie większą częstotliwością (zakładając, że nie ma innej ścieżki krytycznej, która by to uniemożliwiła ). Ale wiąże się to z narzutem: musisz wstawić rejestr między etapami rurociągu. Co oznacza, że ​​tak naprawdę nie zyskujesz 2x prędkości (rejestr potrzebuje czasu do przechowywania danych) i skomplikowałeś cały projekt.

Istnieją już dość wydajne metody wykonywania dodawania (np. Dodawanie antycypujących dodatków) i dodawanie nie jest krytyczną ścieżką dla szybkości procesora, dlatego nie ma sensu dzielenie go na wiele cykli.

Zwróć też uwagę, że chociaż może się to wydawać skomplikowane, w sprzęcie rzeczy mogą być wykonywane równolegle bardzo szybko.

Procesory są taktowane, więc nawet jeśli niektóre instrukcje można wyraźnie wykonać szybciej niż inne, mogą one zająć tę samą liczbę cykli.

Prawdopodobnie okaże się, że zespół obwodów wymagany do przesyłania danych między rejestrami a jednostkami wykonawczymi jest znacznie bardziej skomplikowany niż sumatory.

Zauważ, że prosta instrukcja MOV (rejestracja do rejestracji) wykonuje nawet mniej obliczeń niż logika bitowa, jednak zarówno MOV, jak i ADD zwykle zajmują jeden cykl. Gdyby MOV można było wykonać dwa razy szybciej, procesory byłyby taktowane dwa razy szybciej, a ADD miałyby dwa cykle.

Dodanie jest na tyle ważne, aby nie czekać, aż bit przeniesie się przez 64-bitowy akumulator: terminem tym jest „ add-look -head adder” i są one w zasadzie częścią 8-bitowych procesorów (i ich ALU) i wyżej. Rzeczywiście, nowoczesne procesory zwykle nie potrzebują dużo więcej czasu wykonania do pełnego zwielokrotnienia: carry-lookahead to tak naprawdę naprawdę stare (i stosunkowo niedrogie) narzędzie w zestawie narzędzi projektanta procesora.

Myślę, że trudno byłoby znaleźć procesor, który miałby więcej cykli, które wymagałyby więcej cykli niż operacji bitowych. Częściowo dlatego, że większość procesorów musi wykonać co najmniej jedno dodawanie na cykl instrukcji, aby zwiększyć licznik programu. Zwykłe operacje bitowe nie są aż tak przydatne.

(Cykl instrukcji, a nie cykl zegara - np. 6502 zajmuje minimum dwa cykle zegara na instrukcję ze względu na brak potokowania i brak pamięci podręcznej instrukcji)

Prawdziwą koncepcją, której możesz przegapić, jest ścieżka krytyczna : najdłuższa operacja, którą można wykonać w jednym cyklu, decyduje na poziomie sprzętowym, jak szybko układ może być taktowany.

Wyjątkiem jest (rzadko używana i mało skomercjalizowana) logika asynchroniczna, która naprawdę działa przy różnych prędkościach w zależności od czasu propagacji logiki, temperatury urządzenia itp.

Na poziomie bramki masz rację, że dodawanie zajmuje więcej pracy, a zatem dłużej. Jednak ten koszt jest wystarczająco trywialny, co nie ma znaczenia.

Nowoczesne procesory są taktowane. Nie możesz wykonywać instrukcji w niczym poza wielokrotnościami tego taktowania. Gdyby taktowania zegara zostały zwiększone, aby zmaksymalizować szybkość operacji bitowych, trzeba by wydać co najmniej 2 cykle. Większość tego czasu poświęciłaby na czekanie, ponieważ tak naprawdę nie potrzebowałeś pełnych 2 cykli czasu. Potrzebujesz tylko 1.1 (lub jakiejś takiej liczby). Teraz Twój chip dodaje wolniej niż wszyscy inni na rynku.

Co gorsza, sam czynność dodawania lub wykonywania operacji bitowych to tylko niewielka część tego, co dzieje się podczas cyklu. Musisz mieć możliwość pobierania / dekodowania instrukcji w cyklu. Musisz być w stanie wykonać operacje pamięci podręcznej w cyklu. Wiele innych rzeczy dzieje się w tym samym czasie co zwykłe dodawanie lub operacja bitowa.

Rozwiązaniem jest oczywiście opracowanie ogromnie głębokiego rurociągu, dzielącego te zadania na małe części, które pasują do niewielkiego czasu cyklu określonego przez operację bitową. Pentium 4 doskonale pokazało granice myślenia w tych głębokich terminach. Powstają wszelkiego rodzaju problemy. W szczególności rozgałęzienia stają się niezwykle trudne, ponieważ musisz opróżnić rurociąg, gdy będziesz mieć dane, aby dowiedzieć się, którą gałąź wybrać.

Nowoczesne procesory są taktowane: każda operacja wymaga pewnej integralnej liczby cykli zegara. Projektanci procesora określają długość cyklu zegarowego. Istnieją dwa czynniki: po pierwsze, szybkość sprzętu, na przykład mierzona jako opóźnienie pojedynczej bramki NAND. Zależy to od zastosowanej technologii i kompromisów, takich jak prędkość vs. zużycie energii. Jest niezależny od konstrukcji procesora. Po drugie, projektanci decydują, że długość cyklu zegarowego jest równa n opóźnieniom pojedynczej bramki NAND, gdzie n może wynosić 10, 30 lub dowolną inną wartość.

Ten wybór n ogranicza liczbę złożonych operacji, które można przetwarzać w jednym cyklu. Będą operacje, które można wykonać w 16, ale nie w 15 opóźnieniach NAND. Zatem wybranie n = 16 oznacza, że ​​taka operacja może być wykonana w cyklu, wybranie n = 15 oznacza, że ​​nie można tego zrobić.

Projektanci wybiorą n, aby wiele ważnych operacji można było wykonać w jednym, a może w dwóch lub trzech cyklach. n zostanie wybrane lokalnie optymalnie: jeśli zastąpisz n przez n-1, wtedy większość operacji byłaby nieco szybsza, ale niektóre (te, które naprawdę potrzebują pełnych opóźnień n NAND) byłyby wolniejsze. Gdyby kilka operacji spowolniło, tak że ogólne wykonanie programu jest średnio szybsze, wybrałbyś n-1. Mogłeś także wybrać n + 1. To sprawia, że ​​większość operacji jest nieco wolniejsza, ale jeśli masz wiele operacji, których nie można wykonać w ciągu n opóźnień, ale można wykonać w ciągu n + 1 opóźnień, wówczas procesor byłby ogólnie szybszy.

Teraz twoje pytanie: Dodawanie i odejmowanie są tak powszechnymi operacjami, że chcesz móc je wykonywać w jednym cyklu. W rezultacie nie ma znaczenia, że ​​operatory AND, OR itp. Mogą działać szybciej: nadal potrzebują tego jednego cyklu. Oczywiście jednostka „obliczająca” ORAZ, LUB itd. Ma dużo czasu na przekręcenie kciuków, ale nie można na to poradzić.

Zauważ, że nie chodzi tylko o to, czy operację można wykonać w ciągu n opóźnień NAND, czy nie: Dodatek można na przykład przyspieszyć, ponieważ jest on nieco sprytny, jeszcze szybciej, ponieważ jest bardzo sprytny, wciąż nieco szybciej, inwestując nadzwyczajne ilości sprzętu , a wreszcie procesor może mieć mieszankę bardzo szybkich, bardzo drogich i nieco wolniejszych i tańszych obwodów, więc istnieje możliwość wykonania jednej operacji wystarczająco szybko, wydając na nią więcej pieniędzy.

Teraz już mogła sprawić, że tak wysokie taktowania / cykl tak krótki, że tylko proste operacje bitowe wykonać w jednym cyklu i wszystko inne w dwóch lub więcej. To najprawdopodobniej spowolniłoby procesor. W przypadku operacji, które wymagają dwóch cykli, zwykle istnieje narzut, aby przenieść niepełną instrukcję z jednego cyklu do następnego, więc dwa cykle nie oznaczają, że masz dwa razy więcej czasu na wykonanie. Aby wykonać dodawanie w dwóch cyklach, nie można było podwoić szybkości zegara.

Pozwól, że poprawię kilka rzeczy, które nie zostały wymienione wyraźnie w twoich istniejących odpowiedziach:

Wiem, że operacje bitowe są tak szybkie na nowoczesnych procesorach, ponieważ mogą działać na 32 lub 64 bitach równolegle,

To prawda. Oznaczenie procesora jako bitu „XX” zwykle (nie zawsze) oznacza, że ​​większość jego wspólnych struktur (szerokości rejestrów, adresowalna pamięć RAM itp.) Ma rozmiar XX bitów (często „+/- 1” lub jakoś tak). Ale jeśli chodzi o twoje pytanie, możesz bezpiecznie założyć, że procesor 32-bitowy lub 64-bitowy wykona dowolną podstawową operację bitową na 32 lub 64 bitach w stałym czasie.

więc operacje bitowe zajmują tylko jeden cykl zegara.

Taki wniosek niekoniecznie ma miejsce. Szczególnie procesory z bogatymi zestawami instrukcji (Google CISC vs. RISC) mogą z łatwością zająć więcej niż jeden cykl nawet dla prostych poleceń. Dzięki przeplataniu nawet proste polecenia mogą rozbić się na fetch-exec-store z 3 zegarami (jako przykład).

Jednak dodawanie jest złożoną operacją

Nie, dodawanie liczb całkowitych jest prostą operacją; odejmowanie również. Bardzo łatwo jest wdrożyć sumatory w pełnym sprzęcie, a oni robią swoje rzeczy tak szybko, jak podstawowe operacje bitowe.

który składa się z co najmniej jednej i prawdopodobnie kilkunastu bitowych operacji, więc naturalnie pomyślałem, że będzie 3-4 razy wolniejszy.

Zajmie to 3-4 razy więcej tranzystorów, ale w porównaniu do dużego obrazu, który jest pomijalny.

Byłem zaskoczony widząc po prostym teście porównawczym, że dodawanie jest dokładnie tak szybkie, jak każda z operacji bitowych (XOR, OR, AND itd.). Czy ktoś może rzucić na to światło?

Tak: dodawanie liczb całkowitych jest operacją bitową (z kilkoma więcej bitami niż inne, ale nadal). Nie trzeba nic robić etapami, nie potrzeba skomplikowanych algorytmów, zegarów ani niczego innego.

Jeśli chcesz dodać więcej bitów niż architektura procesora, poniesiesz karę za konieczność robienia tego etapami. Ale jest to na innym poziomie złożoności (poziom języka programowania, a nie poziom asemblera / kodu maszynowego). Był to powszechny problem w przeszłości (lub dziś na małych wbudowanych procesorach). W przypadku komputerów PC itp. Ich 32 lub 64 bity są wystarczające, aby najpopularniejsze typy danych mogły stać się punktem spornym.