Dlaczego bramy odwracalne nie są używane?

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

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.

$kT\ln 2$$60\,{}^\circ\mathrm{C}$$10^9$$5\,\mathrm{GHz}$$16\,\mathrm{mW}$$1/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.

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łą.

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 .

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.

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.

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