Dlaczego bramy odwracalne nie są używane?

25

Czytałem książkę „Osobliwość jest bliska” napisaną przez Kurzweila, który wspomniał o odwracalnych bramach, takich jak na przykład brama Fredkina . Zaletą korzystania z takich bram jest to, że moglibyśmy pozbyć się odpadów termicznych związanych z obliczeniami, w których bity po prostu znikają w cieple, a obliczenia nie będą wymagały żadnego wkładu energii. Te założenia sprawiają, że bramy te brzmią jak cudowne rozwiązanie. Powstaje więc pytanie, jakie przeszkody techniczne wciąż uniemożliwiają ich wykorzystanie na dużą skalę.

Myślę też, że to wstyd, że nigdy nie słyszałem o tych bramach w trakcie studiów licencjackich i magisterskich z elektrotechniki na jednym z najlepszych niemieckich uniwersytetów ...

Mehdi
źródło
5
Zauważ, że obliczenia kwantowe dotyczą w dużej mierze odwracalnych bramek (to część tego, co oznacza „jednostkowy”).
David Richerby,
1
@DavidRicherby Nie wszystkie obliczenia kwantowe są odwracalne; ostatecznie pojawia się dekoherencja.
Alice,
Zwróć uwagę, że każdy praktyczny komputer korzystający z odwracalnych bramek nadal będzie generował ciepło, ponieważ musisz wykonać korekcję błędów, aby utrzymać komputer na dobrej drodze. Korekta błędów z natury wymaga nieodwracalnych operacji (lub ciągłej dostawy zerowych bitów; ta sama różnica).
Craig Gidney

Odpowiedzi:

18

W żadnym wypadku nie jestem ekspertem w tym temacie, ale od niechcenia czytam Wikipedię:

opiera się na ruchu sferycznych kulek bilardowych w pozbawionym tarcia otoczeniu wykonanym ze zderzaków, o które kule odbijają się idealnie

... to brzmi bardzo realistycznie.

Nikt jeszcze nie wymyślił, jak zrobić takie bramy, są one jedynie przedmiotem zainteresowania teoretycznego. To może wyjaśniać, dlaczego nigdy o nich nie słyszałeś, ponieważ inżynieria zwykle zajmuje się praktyką.

Założeniem obliczeń odwracalnych jest to, że gdy trochę znika, generowana jest pewna ilość ciepła. Dzięki zastosowaniu odwracalnych bram, żadne bity nigdy się nie pojawiają ani nie znikają, więc przypuszczalnie obliczenia mogłyby być znacznie wydajniejsze w przypadku odwracalnych bram.

kTln260C1095GHz16mW1/10000

Nasze współczesne komputery nie są ograniczone wytwarzaniem ciepła związanego z znikaniem bitów. Ogranicza je wrodzona nieefektywność w poruszaniu elektronami po małych śladach miedzi.

Tom van der Zanden
źródło
5
-1. Niektórzy ludzie wykonali odwracalne bramki i zbudowali z nich cały procesor. Zdjęcie tego odwracalnego procesora logicznego znajduje się na stronie cise.ufl.edu/research/revcomp .
David Cary
2
@DavidCary, ale nie są one (lub nieistotnie) bardziej wydajne niż komputery wykonane z nieodwracalnych bram.
user253751
3
@immibis Znacząco nieprawdziwe; nie podlegają tym samym prawom, co komputery wykonane z nieodwracalnych bram, a zatem są znacznie bardziej wydajne.
Alice,
3
@DavidCary Pokaż mi trochę danych na temat wydajności procesora, z którym się łączysz. Widzę tylko obraz procesora ze słowem „adiabatyczny”, ale nie ma informacji o tym, o ile wydajniejszy niż tradycyjne komputery.
Tom van der Zanden,
1
@TomvanderZanden Pomiar wydajności jest nieco bezużyteczny, jeśli nie określisz, jaki rodzaj wydajności. Układy RISC są bardziej wydajne niż układy CISC pod względem wielkości układu, ale nie pod względem liczby instrukcji potrzebnych do określenia danego algorytmu. Każdy obwód zwrotny jest natychmiast bardziej wydajny niż tradycyjny obwód, ponieważ nie podlega zasadzie Landauera ; to już ogromna wygrana.
Alice,
15

Problem z praktycznymi bramami odwracalnymi (bramami, które mogą (i zostały) wykonane z krzemu) jest to, że rzeczywiste oszczędności energii są liniowo proporcjonalne do tego, jak wolno je uruchamiasz.

Wiem, że grupa badawcza Toma Knighta w MIT wyprodukowała pod koniec lat 90. mały procesor adiabatyczny. Opracowana przez nich praktyczna rodzina logiki nazywa się logiką odzyskiwania ładunków dwupoziomowych i można ją zaimplementować przy użyciu standardowych technik wytwarzania (CMOS). Wierzę, że prace kontynuował Michael P Frank z Florida State University. Przykładem pracy w grupie Toma Knighta jest następująca praca magisterska (która ma dość przyzwoitą część na temat powiązanych prac do początku lat 90.). Vieri, CJ: Pendulum: A Reversible Computer Architecture , Master's Thesis, MIT EECS dept, 1995.

Obwody odwracalne muszą być adiabatyczne (nie może być wymiany ciepła między obwodem a jego otoczeniem), co oznacza, że ​​muszą one znajdować się w równowadze przez cały czas. W przypadku każdego procesu, który musi coś zmienić, można jedynie przybliżyć równowagę, dokonując zmiany tak wolno, jak to możliwe.

Jeśli dobrze pamiętam moją termodynamikę, możesz dowolnie zmniejszyć energię obliczeń odwracalnych, ale minimalne działanie (czas energii) musi być małą stałą.

Wędrująca logika
źródło
2
Nie pamiętasz poprawnie termodynamiki; Zasada Landauera nie musi być wspierana przez obwód odwracalny (ponieważ nie kasuje bitów), a zatem potrzebna energia może teoretycznie wynosić zero (i żadne ciepło nie zostanie uwolnione). Obwody odwracalne również nie muszą być adiabatyczne; wykonano praktyczne odwracalne bramki, które nie są wolniejsze niż nieodwracalne układy scalone (biorąc pod uwagę, że odwracalne układy scalone są zwykle większe, a zatem mają prędkość lekkiego wzrostu opóźnienia).
Alice,
„prędkość wzrostu opóźnienia światła”: Czy masz na myśli odwracalne układy optyczne ? Większość układów jest elektroniczna.
zylstra
6

Największa przeszkoda uniemożliwiająca ich wykorzystanie na dużą skalę jest taka sama jak w przypadku obwodów asynchronicznych i praktycznie każdej innej niestandardowej konstrukcji obwodu: prawo Moore'a.

Prawo Moore'a stało się czymś w rodzaju samospełniającej się przepowiedni; zgodnie z harmonogramem wydawania Tick Tock producenci chipów traktują przestrzeganie prawa Moore'a jako wyzwanie. Ze względu na potrzebę przestrzegania prawa Moore'a, coraz bardziej biegłe w zmniejszaniu wielkości żetonów poprzez ulepszanie litografii (i często poprzez stosowanie kodów, takich jak multipatterning).

Co to wszystko ma wspólnego z odwracalnymi bramami? Gdy odlewnie starają się wypuszczać nowsze i mniejsze rozmiary tranzystorów, firmy, które chcą wydrukować nowe układy scalone, widzą łatwą drogę do zwiększenia prędkości po prostu dodając więcej pamięci podręcznej i przerabiając swoje konwencjonalne konstrukcje, aby lepiej wykorzystać tę pamięć podręczną.

Zabójcą lepszych nie są technologiczne problemy; to wystarczająco dobry sukces .

Alice
źródło
1
Mam nadzieję, że jeden dzień wystarczająco dobry nie będzie już wystarczająco dobry.
Mehdi,
@Mehdi Nie wszyscy sobie życzymy. Ale nie byłbym taki pewien; energia jest obecnie tania i istnieją ścieżki do kontynuowania obecnego cyklu przez co najmniej kolejne 5 lat (ewentualnie 10, jeśli znajdziemy sposób na uruchomienie pewnych technologii . Po tym, niektóre nowe technologie będą musiały zastąpić litografię, ale to nie znaczy, że musi być niekonwencjonalny. Litografia 3D może zapewnić znacznie gęstsze układy scalone, budując na tym samym boisku, ale w różnych kierunkach. To może nam przynieść zysk do 2050 r.
Alice
3

Przydatne urządzenia komputerowe wymagają sprzężenia zwrotnego, dzięki czemu jeden element obwodu może wykonywać praktycznie nieograniczoną liczbę kolejnych obliczeń. Użyteczne obwody sprzężenia zwrotnego muszą zawierać sekcje, których całkowita liczba wejść (licząc zarówno te, które są sprzężone zwrotnie z wyjściami, jak i te, które nie są), przekracza liczbę wyjść, które są sprzężone zwrotnie z wejściami (jedyny sposób, w jaki liczba wejść nie byłaby „ t przekroczyłoby liczbę sprzężeń zwrotnych, gdyby obwody nie reagowały w żaden sposób na bodźce zewnętrzne). Ponieważ funkcje doskonale odwracalnej logiki nie mogą mieć więcej danych wejściowych niż danych wyjściowych, nie można z nich zbudować żadnej struktury sprzężenia zwrotnego wymaganej do wielokrotnego wykonywania wszelkich nietrywialnych zadań obliczeniowych. Zauważ, że dzięki technologii CMOS stosowanej w dzisiejszych komputerach wymagane jest sprzężenie zwrotne, aby zapewnić, że wyniki raportowane przez obliczenia w różnych częściach obwodu są udostępniane jednocześnie innym częściom, ponieważ gdyby nie były względnym taktowaniem, z którym przychodzą sygnały, stanowią „informacje”, których nie można idealnie przekazać na dalszym etapie; inne technologie mogą pozwolić, aby wiele bramek propagowało sygnały dokładnie z tą samą prędkością, zachowując odwracalność, ale nie znam na to żadnej praktycznej technologii.

Zauważ, że z punktu widzenia CS, trywialne jest uczynienie procesu obliczeniowego odwracalnym, jeśli ma się początkowo pusty nośnik pamięci, którego rozmiar jest zasadniczo proporcjonalny do liczby kroków pomnożonej przez liczbę stanów, które mogą się zmieniać w każdym kroku. Twierdzenie to nie jest sprzeczne z twierdzeniem z poprzedniego akapitu, ponieważ przechowywanie proporcjonalne do liczby kroków będzie wymagało zespołu obwodów proporcjonalnych do liczby kroków, co będzie oznaczało zespół obwodów proporcjonalny do ilości, która byłaby wymagana, gdyby wszystkie sprzężenia zwrotne zostały wyeliminowane.

Jeśli ktoś może mieć wyjścia, które są ignorowane, jeśli przy odpowiednich warunkach wejściowych nigdy nie osiągną wysokiego poziomu, możliwe byłoby zaprojektowanie systemu, który teoretycznie skorzystałby na odwracalnej logice. Na przykład, jeśli ktoś miał algorytm działający na 256-słowowej części pamięci RAM i chciałby zastosować „odwracalny procesor logiczny”, który wykonywał 1 000 000 operacji na sekundę, a każda operacja aktualizowała rejestr, licznik programu lub jeden słowo RAM, można użyć „odwracalnego procesora”, który:

  • uruchomiłem kilka instrukcji i na każdym wysłałem wszystko, co zostało zastąpione do bufora LIFO
  • po wykonaniu szeregu instrukcji skopiuj pamięć RAM do początkowo pustego bufora „przesyłania”
  • używając wartości w LIFO, uruchom wszystkie obliczenia w odwrotnej kolejności
  • nadpisuje zawartość głównej pamięci RAM buforem przesyłania, który zostałby w ten sposób usunięty.

Powyższy przepis można powtórzyć dowolną liczbę razy, aby uruchomić algorytm dla dowolnej liczby kroków; tylko ostatni krok przepisu nie byłby odwracalny. Ilość energii wydatkowanej na krok algorytmu w nieodwracalnych operacjach byłaby odwrotnie proporcjonalna do wielkości LIFO, a zatem mogłaby być dowolnie mała, gdyby budować, aby zbudować wystarczająco dużą LIFO.

Aby ta zdolność mogła przełożyć się na jakąkolwiek oszczędność energii, konieczne byłoby jednak posiadanie LIFO, który magazynowałby energię po wprowadzeniu informacji i pożytecznie zwrócił tę energię po odczytaniu. Co więcej, LIFO musiałby być wystarczająco duży, aby pomieścić dane stanu dla wystarczającej liczby kroków, aby każdy koszt energii jego użycia był mniejszy niż ilość energii, którą użytecznie zaoszczędził. Biorąc pod uwagę, że ilość energii utraconej podczas przechowywania i pobierania N bajtów z jakiegokolwiek praktycznego FIFO prawdopodobnie nie będzie równa O (1), nie jest jasne, czy zwiększenie N znacząco zmniejszy zużycie energii.

supercat
źródło
1
@LoganMayfield: Myślę, że ignorujesz wymaganie, aby wymagana długość taśmy była proporcjonalna do liczby kroków, które należy wykonać w sposób odwracalny. Jeśli wrzucę nabój do mojego Atari 2600 i włączy go na jakiś czas, będzie on działał około 100 miliardów cykli dziennie. Ponieważ system (w tym wszystkie oprócz największych wkładów) miałby mniej niż 100 000 tranzystorów, to ponad milion cykli dziennie na tranzystor. Gdyby ktoś chciał zaprojektować równoważną maszynę, która mogłaby działać przez cały dzień w pełni odwracalnie, nawet z możliwością stworzenia odwracalnego LIFO z jednym tranzystorem na bit ...
supercat
1
... konieczne byłoby zwiększenie liczby tranzystorów ponad milion razy. Gdyby trzeba było wykonać kilka tysięcy cykli jednocześnie, przechwytywanie wyników, przewijanie cykli, a następnie zastępowanie poprzedniego stanu początkowego przechwyconymi wynikami, co może być prawie wykonalne, ale byłoby monstrualnie złożone. Gdyby cokolwiek przypominało dzisiejszą technologię, jakiekolwiek zmniejszenie strat „teoretycznie nieuniknionych”, które można uzyskać za pomocą obliczeń odwracalnych, byłoby zatłoczone przez wzrost mocy utraconej z przyczyn, których można było uniknąć tylko teoretycznie.
supercat
1
Martwiłem się tylko stwierdzeniem, które udzieliła pierwotna odpowiedź, które brzmiało: „technologia odwracalna nie może obliczyć tych samych rzeczy, co technologia nieodwracalna”. Nie chciałem sugerować, że to praktyczne.
Logan Mayfield,
1
@LoganMayfield: Początkowe pytanie brzmiało „dlaczego nie używa się tych rzeczy”. Sugerowałbym, że prawie wszystkie praktyczne urządzenia obliczeniowe wykorzystują sprzężenie zwrotne w taki sposób, aby stała ilość sprzętu była w stanie wykonać nieograniczoną liczbę obliczeń, jeśli otrzyma nieograniczony czas. Jest to coś, czego odwracalna logika po prostu nie może zrobić . Jest to główna jakościowa różnica między obliczeniami odwracalnymi i nieodwracalnymi. Możliwe, że nawet komputer, który może wykonać tylko ograniczoną liczbę operacji przed „przewinięciem”, może być nadal przydatny, więc ...
supercat
1
... Zredagowałem post, aby powiedzieć, co byłoby wymagane, aby użyć czegoś takiego do jakiejkolwiek znaczącej pracy. Myślę jednak, że podstawowy problem praktyczny wynika z tego, co pierwotnie powiedziałem: komputery czerpią większość korzyści z ich zdolności do ponownego użycia elementów obwodu dowolną liczbę razy do wykonywania różnych obliczeń oraz niemożności odwracalna logika do obsługi, która sprawi, że będzie to w bardzo niekorzystnej sytuacji od samego początku.
supercat
2

Praktyczne stosowane odwracalne obliczenia są aktywnym obszarem badań i prawdopodobnie staną się bardziej widoczne w przyszłości. Większość obliczeń kwantowych może być próbą stworzenia odwracalnych bram kubitowych i bardzo trudno eksperymentalnie dopasować teoretyczne właściwości formalizmu QM, ale poczyniono stały postęp.

Inną podstawową kwestią jest to, że za każdym razem, gdy rozpraszanie energii jest zmniejszane na chipie, zasadniczo przesuwa on system bramkowy do „bardziej odwracalnego”, a rozpraszanie chipów o niższej energii było od dawna priorytetem w przetwarzaniu mobilnym (reprezentując rodzaj zmiana paradygmatu w branży). Przez dziesięciolecia wzrost wydajności chipów (podobny do prawa Moore'a) był nieco „zrelaksowany”, a nawet „niechlujny” z rozpraszaniem energii, ale kilka lat temu osiągnął poziom malejących zwrotów. Wiodący światowy producent układów Intel, stara się przestawić na układy o niższej mocy, aby konkurować z Arm, który ma tę przewagę, że nigdy niczego nie buduje.

Niedawno przeprowadzono pewne przełomowe badania z wykorzystaniem technologii nadprzewodzącej (czerwiec 2014 r.), A także inne aktywne projekty badawcze w tym obszarze.

Patrz np. Odwracalna bramka logiczna wykorzystująca adiabatyczne urządzenia nadprzewodzące / Takeuchi, Yamanashi, Yoshikawa, Nature:

Odwrotne obliczenia zostały zbadane, odkąd Rolf Landauer wysunął argument, który stał się znany jako zasada Landauera. Zasada ta stwierdza, że ​​nie ma minimalnego rozproszenia energii dla operacji logicznych w obliczeniach odwracalnych, ponieważ nie towarzyszy temu zmniejszenie entropii informacji. Jednak do tej pory nie wykazano praktycznych odwracalnych bramek logicznych. Jednym z problemów jest to, że odwracalne bramki logiczne muszą być budowane przy użyciu wyjątkowo energooszczędnych urządzeń logicznych. Inną trudnością jest to, że odwracalne bramki logiczne muszą być logicznie i fizycznie odwracalne. W tym miejscu proponujemy pierwszą praktyczną odwracalną bramkę logiczną z wykorzystaniem adiabatycznych urządzeń nadprzewodzących i eksperymentalnie wykazujemy logiczną i fizyczną odwracalność bramki. Dodatkowo szacujemy rozpraszanie energii przez bramę, i omówienie minimalnego rozpraszania energii wymaganego do operacji logiki odwracalnej. Oczekuje się, że wyniki tego badania umożliwią przejście obliczeń odwracalnych z etapu teoretycznego na praktyczne zastosowanie.

vzn
źródło
1

Bramy Fredkina są realistyczne i wiele z nich zostało zaimplementowanych. Istnieją całe płyty FPGA ściśle wykorzystujące odwracalne bramki logiczne, które są implementowane za pomocą Fredkin i Toffoli jako ich jednostek logicznych.

Istnieje kilka problemów wpływających na ich powszechne użycie w architekturze komputerowej. Istnieje kilka „reklamowanych” zalet bram Fredkina, które niekoniecznie działają zgodnie z oczekiwaniami w rzeczywistych obwodach. Oszczędność energii odwracalnych bramek logicznych wynika głównie z faktu, że nie wymagają one tworzenia entropii podczas wykonywania operacji. Jak stwierdził Tom van der Zanden, jest to główny powód, dla którego odwracalna logika może być znacznie wydajniejsza. Dlaczego tak nie jest w rzeczywistych obwodach:

  1. Obecnie technologia tranzystorowa bardziej ogranicza prędkość komputera i zużycie energii, a niestety potrzeba więcej tranzystorów, aby stworzyć bramę Fredkina w przeciwieństwie do tradycyjnych bram NAND lub NOR. Oznacza to, że fredkinowskie bramy marnują więcej energii przez upływ prądu tranzystora i wymagają więcej miejsca na krzemie (co oznacza droższe). Już to wystarczy, aby uzasadnić użycie nand / nor nad bramami Fredkin
  2. Ponieważ podstawowa forma utraty mocy pochodzi z tranzystorów, a nie tworzenia entropii z uwagi na faktyczne obliczenia, nadal musisz uruchomić zasilanie i linie uziemienia do bram Freddy'ego, aby zrekompensować tę utratę mocy. Te duże autobusy to autobusy wachlarzowe, które również zajmują dużo miejsca na krzemie. Ponieważ w bramie Freddina znajduje się więcej tranzystorów, prowadzi to do większej liczby wtyków, a tym samym do więcej zmarnowanej przestrzeni na krzemie.
  3. Chociaż mamy odwracalne bramki Freddina, są one zbudowane z nieodwracalnych urządzeń (tranzystorów). Oznacza to, że niektóre zyski energii nie są realizowane przy użyciu technologii bramek prądowych (poza obwodami kwantowymi).
  4. Rozmiar i prędkość są powiązane z krzemem, im bliżej siebie jest, tym szybciej można je wykonać. Ponieważ bramki Fredkina używają więcej tranzystorów i mają więcej połączeń dla zasilania itp., Są one zwykle znacznie wolniejsze.
  5. Zalety zużycia energii i prędkości są realizowane tylko wtedy, gdy bity są ponownie wykorzystywane. Większość naszych algorytmów jest strasznie niekonserwatywna. Możesz to zobaczyć, badając implementację pełnego sumatora lub rejestru przesuwnego za pomocą fredkina. Ponieważ odwracalna logika nie pozwala na logiczne włączanie i wyłączanie, prowadzi to do wielu obliczeń bitów, które nie są ostatecznie wykorzystywane do uzyskania użytecznej operacji. Coś takiego jak dodanie dwóch liczb 8-bitowych spowoduje wygenerowanie 9-bitowych lub przydatnych informacji (wynik 8-bitowy, 1 bit przenoszący), ale będzie wymagało szyny wejściowej zawierającej wiele stałych 1 i 0 i wytworzy wiele niepotrzebnych bitów wyjściowych danych. Ponieważ masz szerszą szynę, prowadzi to do jeszcze większego rozproszenia obwodu na krzemie.
  6. Ponadto śmieci muszą zostać zrzucone przez procesor, a zatem i tak doprowadziłoby to do strat energii, ponieważ nigdy nie są używane

Podsumowanie: Bramki Fredkina powodują wiele obliczeń odpadów podczas implementacji prawdziwych algorytmów. obliczanie odpadów = zmarnowana energia. Z tego powodu zwiększają się rozmiary autobusów, co rozkłada i spowalnia. Ponadto fizyczna implementacja bram Fredrika stanowi większy problem dla obecnej technologii. Obecna implementacja bardziej rozprzestrzenia się, wymagając większej mocy i linii uziemienia, aby zrekompensować straty w obwodzie (co jest znacznie większym problemem w przypadku strat energii) i wykorzystuje znacznie więcej nieruchomości na krzemie (co jest znacznie większym problemem dla prędkości )

Zdaję sobie sprawę, że to stary wątek, ale wiele odpowiedzi skupia się na tym, że tranzystory są nieefektywne. Moim celem jest pokazanie, że nasze algorytmy są również nieefektywne i nie radzą sobie dobrze z odwracalnym przetwarzaniem. Jestem inżynierem komputerowym, który lubi badać obliczenia odwracalne i kwantowe

Ryan
źródło