Reverzibilní výpočetní technika - Reversible computing

Reverzibilní výpočet je jakýkoli model výpočtu, kde je výpočetní proces do určité míry časově reverzibilní . V modelu výpočtu, který používá deterministické přechod z jednoho stavu do abstraktního stroje ke druhému, je nezbytnou podmínkou pro reverzibility je, že vztah k mapování ze států svým nástupcům musí být jedna ku jedné . Reverzibilní výpočetní technika je formou nekonvenčních výpočetních prostředků .

Vzhledem k unitarity z kvantové mechaniky , kvantové obvody jsou vratné, pokud tomu tak není „ kolaps “, jejíž kvantových stavů , které fungují dál.

Reverzibilita

Pro tento účel jsou zvláště zajímavé dva hlavní, úzce související typy reverzibility: fyzická reverzibilita a logická reverzibilita .

Říká se, že proces je fyzicky reverzibilní, pokud nevede ke zvýšení fyzické entropie ; je to isentropické . Existuje styl návrhu obvodu, který v ideálním případě ukazuje tuto vlastnost, která se označuje jako logika obnovy náboje , adiabatické obvody nebo adiabatické výpočty (viz adiabatický proces ). Ačkoli v praxi nemůže být žádný nestacionární fyzikální proces přesně fyzicky reverzibilní nebo isentropický, neexistuje žádná známá hranice, s jakou bychom se mohli přiblížit k dokonalé reverzibilitě, v systémech, které jsou dostatečně dobře izolovány od interakcí s neznámým vnějším prostředím, kdy fyzikální zákony přesně popisující evoluci systému.

Motivace pro studium technologií zaměřených na provádění reverzibilní computing je, že nabízejí to, co se předpokládá, že jedinou možnou cestou ke zlepšení výpočetní energetickou účinnost počítačů mimo základní von Neumann-Landauer limitu z kT ln (2) energie rozptýlena per nevratný bitový provoz . Ačkoli Landauerův limit byl milionkrát nižší než spotřeba energie počítačů v roce 2000 a tisíckrát méně v letech 2010, zastánci reverzibilních počítačů tvrdí, že to lze do značné míry přičíst architektonickým režijním nákladům, které efektivně zvyšují dopad Landauerova limitu v praxi návrhů obvodů, takže pro praktické technologie může být obtížné pokročit velmi daleko za současné úrovně energetické účinnosti, pokud nejsou použity reverzibilní výpočetní principy.

Vztah k termodynamice

Jak poprvé argumentoval Rolf Landauer při práci v IBM , aby byl výpočetní proces fyzicky reverzibilní, musí být také logicky reverzibilní . Landauerovým principem je důsledně platné pozorování, že nezapomenutelné vymazání n bitů známé informace musí vždy způsobit náklady na nkT ln (2) v termodynamické entropii . Diskrétní, deterministický výpočetní proces je logicky reverzibilní, pokud přechodová funkce, která mapuje staré výpočetní stavy na nové, je funkcí one-to-one ; tj. výstupní logické stavy jednoznačně určují vstupní logické stavy výpočetní operace.

U výpočetních procesů, které jsou nedeterministické (ve smyslu pravděpodobnosti nebo náhody), není vztah mezi starým a novým stavem funkcí s jednou hodnotou a požadavek potřebný k získání fyzické reverzibility se stává o něco slabší podmínkou, konkrétně že velikost daného souboru možných počátečních stavů výpočtu v průměru neklesá, jak výpočet postupuje vpřed.

Fyzická reverzibilita

Landauer princip (a opravdu, druhý termodynamický zákon sám) může být také zřejmé, že je přímým logickým důsledkem podkladové reverzibility fyziky , jak se odráží v obecném Hamiltonova formulaci mechaniky , a v jednotné operátor časově evolution of konkrétně kvantová mechanika .

Implementace reverzibilních výpočtů tedy znamená naučit se charakterizovat a řídit fyzickou dynamiku mechanismů k provádění požadovaných výpočetních operací tak přesně, že můžeme akumulovat zanedbatelné celkové množství nejistoty ohledně úplného fyzického stavu mechanismu pro každou logickou operaci které se provádí. Jinými slovy, potřebovali bychom přesně sledovat stav aktivní energie, která se podílí na provádění výpočetních operací uvnitř stroje, a navrhnout stroj tak, aby se většina této energie získala zpět v organizované formě, která může být znovu použity pro následné operace, místo aby se mohly rozptýlit do formy tepla.

Přestože dosažení tohoto cíle představuje významnou výzvu pro návrh, výrobu a charakterizaci ultrapřesných nových fyzických mechanismů pro výpočetní techniku , v současné době neexistuje žádný zásadní důvod domnívat se, že tohoto cíle nelze nakonec dosáhnout, což nám umožňuje jednoho dne postavit počítače, které generují mnohem méně než 1 bit fyzickou entropii (a rozptylují mnohem méně než kT ln 2 energie na teplo) pro každou užitečnou logickou operaci, kterou provádějí interně.

Dnes má tento obor za sebou značný soubor akademické literatury. Fyzici , elektrotechnici a počítačoví vědci navrhli a analyzovali širokou škálu konceptů reverzibilních zařízení, logických bran , elektronických obvodů , architektur procesorů, programovacích jazyků a aplikačních algoritmů .

Tato oblast výzkumu čeká na podrobný vývoj vysoce kvalitní, nákladově efektivní, téměř reverzibilní technologie logických zařízení, která zahrnuje vysoce energeticky účinné taktovací a synchronizační mechanismy, nebo se jim vyhýbá prostřednictvím asynchronního návrhu. Tento druh solidního inženýrského pokroku bude zapotřebí, než velká část teoretického výzkumu reverzibilních počítačů najde praktické uplatnění při umožnění skutečné počítačové technologii obejít různé blízké překážky její energetické účinnosti, včetně vazby von Neumann – Landauer. To lze obejít pouze použitím logicky reverzibilních počítačů, kvůli druhému zákonu termodynamiky .

Logická reverzibilita

Chcete-li implementovat reverzibilní výpočet, odhadnout jeho náklady a posoudit jeho limity, může být formalizován z hlediska obvodů na úrovni brány. Zjednodušený model takových obvodů je takový, ve kterém jsou spotřebovány vstupy (všimněte si však, že skutečné logické brány implementované např. V CMOS to nedělají). V tomto modelovacím rámci je invertorová (NE) brána vratná, protože ji lze vrátit zpět . Exkluzivní nebo (XOR) brána je nevratná, protože jeho dva vstupy nelze jednoznačně rekonstruován z jejího jediného výstupu. Reverzibilní verzi brány XOR - kontrolovanou bránu NOT (CNOT) - však lze definovat zachováním jednoho ze vstupů. Tři vstupy varianta Cne brány se nazývá brána Toffoli . Zachovává dva ze svých vstupů a, b a nahrazuje třetí c o . S , to dává funkci AND a tím dává funkci NOT. Toffoli gate je tedy univerzální a může implementovat jakoukoli reverzibilní booleovskou funkci (vzhledem k dostatečnému počtu pomocných bitů inicializovaných nulou). Obecněji řečeno, vratné brány, které spotřebovávají jejich vstup, nemají více vstupů než výstupů. Reverzibilní obvod spojuje vratné brány bez větráků a smyček. Proto takové obvody obsahují stejný počet vstupních a výstupních vodičů, z nichž každý prochází celým obvodem. Podobně v Turingův stroj výpočetních modelů, reverzibilní Turingův stroj je ten, jehož funkce přechodu nezvratné, tak, že každý automat obsahuje nejvýše jednu předchůdce.

Yves Lecerf navrhl v dokumentu z roku 1963 reverzibilní Turingův stroj, který si však zjevně nebyl vědom Landauerova principu, dále se tomuto tématu nevěnoval a většinu zbytku své kariéry věnoval etnolingvistice. V roce 1973 Charles H. Bennett ve společnosti IBM Research ukázal, že univerzální Turingův stroj by mohl být logicky i termodynamicky reverzibilní, a proto by v zásadě mohl provádět libovolně velký počet výpočetních kroků na jednotku rozptýlené fyzické energie, pokud bude dostatečně provozován pomalu. Termodynamicky reverzibilní počítače mohly provádět užitečné výpočty s užitečnou rychlostí, přičemž na logický krok rozptýli podstatně méně než kT energie. V roce 1982 Edward Fredkin a Tommaso Toffoli navrhli počítač s kulečníkovými koulemi , mechanismus využívající klasické tvrdé sféry k provádění reverzibilních výpočtů konečnou rychlostí s nulovým rozptylem, ale vyžadující dokonalé počáteční zarovnání trajektorií koulí, a Bennettova recenze porovnávala tyto „Brownian“ a „balistická“ paradigmata pro reverzibilní výpočet. Kromě motivace energeticky efektivního výpočtu nabízely vratné logické brány praktické vylepšení transformací bitové manipulace v kryptografii a počítačové grafice. Od 80. let 20. století přitahují reverzibilní obvody zájem jako součásti kvantových algoritmů a v poslední době o fotonické a nano-výpočetní technologie, kde některá spínací zařízení nenabízejí žádný zisk signálu .

K dispozici jsou průzkumy reverzibilních obvodů, jejich konstrukce a optimalizace a také nedávné výzkumné výzvy.

Viz také

Reference

Další čtení

externí odkazy