Reversibel databehandling - Reversible computing

Reversibel databehandling er enhver beregningsmodell der beregningsprosessen til en viss grad er tids reversibel . I en beregningsmodell som bruker deterministiske overganger fra en tilstand av den abstrakte maskinen til en annen, er en nødvendig betingelse for reversibilitet at forholdet mellom kartleggingen fra stater til deres etterfølgere må være en-til-en . Reversibel databehandling er en form for ukonvensjonell databehandling .

På grunn av kvantemekanikkens enhetlighet er kvantekretser reversible, så lenge de ikke " kollapser " kvantetilstandene de opererer på.

Reversibilitet

Det er to store, nært beslektede typer reversibilitet som er av spesiell interesse for dette formålet: fysisk reversibilitet og logisk reversibilitet .

En prosess sies å være fysisk reversibel hvis den ikke resulterer i økning i fysisk entropi ; det er isentropisk . Det er en stil med kretsdesign som ideelt viser denne egenskapen som kalles ladningsgjenopprettingslogikk , adiabatiske kretser eller adiabatisk databehandling (se Adiabatisk prosess ). Selv om ingen ikke -stasjonær fysisk prosess i praksis kan være nøyaktig fysisk reversibel eller isentropisk, er det ingen kjent grense for hvor nært vi kan nærme oss perfekt reversibilitet, i systemer som er tilstrekkelig godt isolert fra interaksjoner med ukjente ytre miljøer, når fysikkens lover som beskriver systemets utvikling er nøyaktig kjent.

En motivasjon for å studere teknologier rettet mot implementering av reversibel databehandling er at de tilbyr det som er spådd å være den eneste potensielle måten å forbedre datamaskiners energieffektivitet på datamaskiner utover den grunnleggende von Neumann - Landauer -grensen på kT ln (2) energi spredt pr. irreversibel bitoperasjon . Selv om Landauer -grensen var millioner ganger lavere enn energiforbruket til datamaskiner på 2000 -tallet og tusenvis av ganger mindre på 2010 -tallet, hevder talsmennene for reversibel databehandling at dette i stor grad kan tilskrives arkitektoniske omkostninger som effektivt forstørrer virkningen av Landauers grense i praktisk kretsdesign, slik at det kan vise seg vanskelig for praktisk teknologi å gå veldig langt utover dagens energieffektivitetsnivå hvis reversible databehandlingsprinsipper ikke brukes.

Forhold til termodynamikk

Som først ble hevdet av Rolf Landauer mens han jobbet i IBM , for at en beregningsprosess skal være fysisk reversibel, må den også være logisk reversibel . Landauers prinsipp er den strengt gyldige observasjonen om at uvitende sletting av n biter av kjent informasjon alltid må medføre en kostnad på nkT ln (2) i termodynamisk entropi . En diskret, deterministisk beregningsprosess sies å være logisk reversibel hvis overgangsfunksjonen som kartlegger gamle beregningstilstander til nye er en en-til-en-funksjon ; dvs. de logiske utgangstilstandene bestemmer de logiske inngangstilstandene til beregningsoperasjonen unikt.

For beregningsprosesser som er ubestemmelige (i den forstand at de er sannsynlige eller tilfeldige), er forholdet mellom gamle og nye tilstander ikke en enkeltverdiert funksjon , og kravet som trengs for å oppnå fysisk reversibilitet blir en litt svakere betingelse, nemlig at størrelsen av et gitt ensemble av mulige innledende beregningstilstander reduseres ikke i gjennomsnitt etter hvert som beregningen går videre.

Fysisk reversibilitet

Landauers prinsipp (og faktisk den andre loven i termodynamikken i seg selv) kan også forstås som en direkte logisk konsekvens av fysikkens underliggende reversibilitet , slik det gjenspeiles i den generelle hamiltonske formuleringen av mekanikk , og i enhetens tids-evolusjon operatør av kvantemekanikk mer spesifikt.

Implementeringen av reversibel databehandling innebærer dermed å lære å karakterisere og kontrollere den fysiske dynamikken til mekanismer for å utføre ønskede beregningsoperasjoner så presist at vi kan akkumulere en ubetydelig total mengde usikkerhet om mekanismens komplette fysiske tilstand, for hver logiske operasjon som utføres. Med andre ord må vi nøyaktig spore tilstanden til den aktive energien som er involvert i å utføre beregningsoperasjoner i maskinen, og designe maskinen på en slik måte at størstedelen av denne energien gjenvinnes i en organisert form som kan gjenbrukes for påfølgende operasjoner, i stedet for å få lov til å spre seg i form av varme.

Selv om det å nå dette målet utgjør en betydelig utfordring for design, produksjon og karakterisering av ultra-presise nye fysiske mekanismer for databehandling , er det foreløpig ingen grunnleggende grunn til å tro at dette målet til slutt ikke kan oppnås, slik at vi en dag kan bygge datamaskiner som generere mye mindre enn 1 bits fysiske entropi (og spre mye mindre enn kT ln 2 energi til varme) for hver nyttig logisk operasjon som de utfører internt.

I dag har feltet en betydelig mengde akademisk litteratur bak seg. Et bredt utvalg av reversible enhets begreper, logiske porter , elektroniske kretser , prosessorarkitekturer, programmeringsspråk , og programalgoritmer er blitt utviklet og analysert ved hjelp av fysikere , elektriske ingeniører og dataforskere .

Dette forskningsfeltet venter på detaljert utvikling av en kostnadseffektiv, nesten reversibel logisk enhetsteknologi av høy kvalitet, en som inkluderer svært energieffektive klokke- og synkroniseringsmekanismer , eller unngår behovet for disse gjennom asynkron design. Denne formen for solid ingeniørfremdrift vil være nødvendig før den store mengden teoretisk forskning om reversibel databehandling kan finne praktisk anvendelse for å gjøre det mulig for ekte datateknologi å omgå de forskjellige kortsiktige hindringene for energieffektivitet, inkludert von Neumann-Landauer-bindingen. Dette kan bare omgås ved bruk av logisk reversibel databehandling, på grunn av termodynamikkens andre lov .

Logisk reversibilitet

For å implementere reversibel beregning, estimere kostnadene og dømme grensene, kan den formaliseres når det gjelder kretser på gate-nivå. En forenklet modell av slike kretser er en der innganger forbrukes (vær imidlertid oppmerksom på at virkelige logiske porter som implementert f.eks. I CMOS ikke gjør dette). I dette modellrammeverket er en inverter (NOT) gate reversibel fordi den kan angres . Den eksklusive eller (XOR) porten er irreversibel fordi dens to innganger ikke entydig kan rekonstrueres fra sin enkeltutgang. Imidlertid kan en reversibel versjon av XOR -porten - den kontrollerte NOT -porten (CNOT) - defineres ved å beholde en av inngangene. Treinngangsvarianten av CNOT-porten kalles Toffoli-porten . Den beholder to av inngangene a, b og erstatter den tredje c med . Med , dette gir AND -funksjonen, og med dette gir NOT -funksjonen. Dermed er Toffoli-porten universell og kan implementere enhver reversibel boolsk funksjon (gitt nok null-initialiserte tilleggsbiter). Mer generelt har reversible porter som bruker sine innspill ikke flere innganger enn utganger. En reversibel krets forbinder reversible porter uten ventilatorer og sløyfer. Derfor inneholder slike kretser like mange inngangs- og utgangskabler, som hver går gjennom en hel krets. På samme måte, i Turing -maskinens modell for beregning, er en reversibel Turing -maskin en hvis overgangsfunksjon er inverterbar, slik at hver maskintilstand har høyst en forgjenger.

Yves Lecerf foreslo en reversibel Turing -maskin i et papir fra 1963, men tilsynelatende uvitende om Landauers prinsipp, forfulgte ikke emnet videre, og viet det meste av resten av karrieren til etnolingvistikk. I 1973 viste Charles H. Bennett , ved IBM Research, at en universell Turing -maskin kunne gjøres både logisk og termodynamisk reversibel, og derfor i prinsippet i stand til å utføre et vilkårlig stort antall beregningstrinn per enhet fysisk energi spredt, hvis den drives tilstrekkelig sakte. Termodynamisk reversible datamaskiner kan utføre nyttige beregninger med nyttig hastighet, mens de forsvinner betydelig mindre enn kT energi per logisk trinn. I 1982 Edward Fredkin og Tommaso Toffoli foreslått billiard ball datamaskin , en mekanisme ved hjelp av klassiske harde kuler for å gjøre reversible beregninger med begrensede hastighet med null spredning, men krever perfekt første justering av ballene baner, og Bennetts vurdering sammenlignet disse 'Brownsk' og "ballistiske" paradigmer for reversibel beregning. Bortsett fra motivasjonen for energieffektiv beregning, tilbød reversible logiske porter praktiske forbedringer av bitmanipuleringstransformasjoner i kryptografi og datagrafikk. Siden 1980-tallet har reversible kretser tiltrukket interesse som komponenter i kvantealgoritmer , og mer nylig i fotoniske og nano-databehandlingsteknologier der noen koblingsenheter ikke gir noen signalforsterkning .

Undersøkelser av reversible kretser, deres konstruksjon og optimalisering, samt de siste forskningsutfordringene, er tilgjengelige.

Se også

Referanser

Videre lesning

Eksterne linker