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

72

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?

SoloNasus
źródło
1
Tak, mnożenie też było dość szybkie w moich testach. Było to tylko około 2x wolniej niż dodawanie, podczas gdy podział był około 30x (!) Razy wolniejszy.
SoloNasus
Kompaktowy przegląd najnowocześniejszych równoległych dodatków drzewa prefiksów: Taksonomia sieci równoległych prefiksów autorstwa Davida Harrisa: pages.hmc.edu/harris/research/taxonomy.pdf
Franki
Bardziej rozwinięte: praca doktorska Jun Chena „Struktury równoległe-prefiksów dla dodatków binarnych i modulo {2n − 1, 2n, 2n + 1}" digital.library.okstate.edu/etd/Chen_okstate_0664D_10070.pdf
Franki

Odpowiedzi:

104

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.

DW
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
DW
38

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.

AProgrammer
źródło
6
+1. Tak, większość procesorów jest taktowana, ale kilka procesorów bez zegara jest dostępnych w handlu.
David Cary
2
Inną możliwością jest to, że procesor może przechowywać 64-bitowy rejestr jako jeden 16-bitowy kawałek i trzy 17-bitowy kawałek, przy czym dodatkowe bity każdego elementu trzymającego odroczone przenoszą się od dołu. Dodanie, po którym następuje operacja bitowa lub magazyn, może wymagać 1-2 dodatkowych cykli, aby propagować przeniesienie, ale dodanie, po którym następuje kolejne dodanie, nie byłoby. Ponadto, w przypadku „sklepu”, dodatkowy czas propagacji może opóźnić działanie sklepu, ale nie byłoby potrzeby, aby kod „czekał” na niego.
supercat
3
@ superuper Pentium 4 zrobił coś takiego, z podwójną szybkością (w stosunku do reszty procesora) ALU, która miałaby niskie 16 lub 32 bity gotowe do kolejnej operacji na pół cyklu przed bitami górnej połowy.
Jeffrey Bosboom
2
czy jesteś pewien, że mierzysz to, co chcesz? W tym przypadku wniosek OP z pomiarów okazuje się być poprawny dla zdecydowanej większości procesorów. Dodawanie jest tak powszechne, że procesory superskalarne mają jednostki dodawane na wszystkich portach wykonawczych, a booleany są tak tanie w implementacji (w liczbie tranzystorów), że są również obecne na wszystkich portach. Zatem dodawanie i booleany prawie zawsze mają taką samą przepustowość (np. 4 na zegar w Intel Haswell).
Peter Cordes
2
Jednak dodawanie liczb całkowitych SIMD jest często mniejszą przepustowością niż wartość logiczna SIMD, chociaż zwykle mają takie same opóźnienia. Procesory Intel od PentiumII do Broadwell mogą uruchamiać tylko dodawanie wektora-int (np. paddw) Przy 2 na zegar, ale logiczne (jak pand) przy 3 na zegar. (Skylake umieszcza sumator wektorowy na wszystkich trzech portach wykonywania wektorów).
Peter Cordes
24

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.

Paul92
źródło
3
Duże koszty ogólne związane z dłuższymi rurociągami to więcej cykli do odzyskania po nieprzewidzianych oddziałach! Wydatkowanie tranzystorów na buforowanie danych między etapami jest obecnie niewielkie. Nawet prosty procesor potokowy musi pobierać / dekodować przed faktycznie wykonanymi instrukcjami. Jeśli procesor odkryje, że front-end pracował na niewłaściwym kodzie, ponieważ gałąź poszła inną drogą niż przewidywano (lub inną błędną spekulację), musi odrzucić tę pracę i zacząć od właściwej instrukcji. Gorzej jest tylko z superskalarnymi procesorami poza kolejnością, które mogą mieć wiele lotów w locie.
Peter Cordes
12

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.

James Hollis
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Gilles
1
Podsumowanie dyskusji: niektóre niedziałające procesory obsługują MOV specjalnie przy zmianie nazw rejestrów, przy zerowym opóźnieniu. Widzisz, czy MOV x86 naprawdę może być „darmowy”? Dlaczego w ogóle nie mogę tego odtworzyć? po szczegółowe informacje o tym, ile naprawdę kosztuje MOV.
Peter Cordes
12

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.

użytkownik72735
źródło
Mnożenie liczb całkowitych to zdecydowanie większe opóźnienie i mniejsza przepustowość niż ADD na x86. Jest jednak zadziwiająco szybki, biorąc pod uwagę liczbę dodatków potrzebnych do zbudowania szybkiego mnożnika: np. Na Intel od Nehalem i AMD od Ryzen, 8/16/32/64-bitowa liczba całkowita skalarna ma opóźnienie 3 cykli, z jednym przepływem na 1c (jedna w pełni potokowa jednostka wykonawcza). Jest to do kitu w porównaniu do przepustowości ADD wynoszącej 3 lub 4 na zegar, ale jest niesamowite w porównaniu z 9-cyklowym opóźnieniem IMUL w Intel Pentium P5. Podobnie jest w przypadku SIMD: mnożenie wektora-int ma większe opóźnienie i mniejszą przepustowość niż dodawanie, ale nadal szybkie.
Peter Cordes
Tak więc, mnożenie kiedyś było znacznie droższe w porównaniu do innych instrukcji niż obecnie. Unikanie go kosztem więcej niż 2 instrukcji zwykle nie jest tego warte, a czasem nawet nie jest warty substytut 2 instrukcji (np. Z leainstrukcją shift + dodaj ).
Peter Cordes
9

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.

pjc50
źródło
Nie jest to kontrolowane przez użytkownika operacje bitowe, ale niektóre instrukcje na 8086 (np. Usuwanie flagi przerwania ) zajmowały mniej cykli niż dodawanie liczb całkowitych. Mówiąc bardziej abstrakcyjnie, system RISC, w którym wszystkie instrukcje mają rozmiar jednego słowa, mógłby użyć prostego licznika binarnego na PC, co byłoby znacznie szybszym obwodem niż sumator ogólnego przeznaczenia.
Mark
Dodawanie licznika programu wydaje się być bardzo proste w porównaniu do dodatkowej instrukcji arytmetycznej, ponieważ jeden z operandów jest mały (albo rozmiar instrukcji, albo względne przesunięcie skoku, które również jest ograniczone rozmiarem)
Ben Voigt
6502 został potokowany - odczytuje pierwszy bajt następnej instrukcji podczas ostatniego cyklu poprzedniego. W przeciwnym razie pobieranie / dekodowanie / wykonywanie wymagałoby co najmniej trzech cykli.
gnasher729
8

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ć.

Cort Ammon
źródło
7

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.

gnasher729
źródło
6

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.

AnoE
źródło
Warto zauważyć, że zmniejszenie kosztu czasu dodawania z O (N) do O (sqrt (N)) nie powoduje znaczącego wzrostu wymaganej liczby tranzystorów lub złożoności trasowania (każdy etap musi tylko pozwolić, aby jeden przewód wślizgnął się z dołu , i muszą być dodatkowe etapy scalania sqrt (N). Koszt czasu można zmniejszyć do O (lgN) kosztem tranzystorów O (lgN), ale w wielu przypadkach pomocne może być przetworzenie czegoś w rodzaju 64- dodawanie bitów, np. osiem 8-bitowych dodań (z wykorzystaniem przekazywania sqrtN) połączonych z trzema warstwami logiki scalania, zamiast 64 bitowych 1-bitowych
dodań
Tak, sumatory są dość proste. Naprawdę imponujące są nowoczesne procesory x86 z całkowicie potokowym 3-cyklowym opóźnieniem 64-bitowego mnożnika liczb całkowitych . (np. imul rax, rcxma opóźnienie 3c i przepustowość 1 na 1c w przypadku rodziny Intel Sandybridge i AMD Ryzen). Nawet 64-bitowe pełne mnożenie (wytwarzanie 128-bitowego wyniku w rdx: rax) ma takie samo opóźnienie i przepustowość, ale jest implementowane jako 2 uops (które działają równolegle na różnych portach). (Zobacz agner.org/optimize, aby zapoznać się z tabelami instrukcji i doskonałym przewodnikiem po mikroarchiwach).
Peter Cordes
[add-with-carry] jest na innym poziomie złożoności (poziom języka programowania, a nie poziom asemblera / kodu maszynowego . Zależy od języka. Kompilator AC ukierunkowany na 16-bitowy procesor musi emitować dla ciebie add / adc podczas kompilacji dodanie dwóch uint32_twartości. Jest to nadal aktualne dla int64_t na 32-bitowych obiektach docelowych. AVR to 8-bitowy mikrokontroler RISC, więc 32-bitowe liczby całkowite wymagają 4 instrukcji: godbolt.org/g/wre0fM
Peter Cordes
Tak, @PeterCordes, o to mi chodziło, trochę wyjaśniłem swoje zdanie.
AnoE