Calcolo reversibile - Reversible computing

Il calcolo reversibile è qualsiasi modello di calcolo in cui il processo computazionale è in una certa misura reversibile nel tempo . In un modello di calcolo che utilizza transizioni deterministiche da uno stato all'altro della macchina astratta, una condizione necessaria per la reversibilità è che la relazione della mappatura dagli stati ai loro successori deve essere uno a uno . Il calcolo reversibile è una forma di calcolo non convenzionale .

A causa della unitarietà della meccanica quantistica , circuiti quantistici sono reversibili, purché non " collasso " del quantum dichiara operano su.

Reversibilità

Esistono due tipi principali di reversibilità strettamente correlati che sono di particolare interesse a questo scopo: reversibilità fisica e reversibilità logica .

Un processo si dice fisicamente reversibile se non determina un aumento dell'entropia fisica ; è isoentropico . Esiste uno stile di progettazione del circuito che mostra idealmente questa proprietà che viene definita logica di recupero della carica , circuiti adiabatici o calcolo adiabatico (vedi Processo adiabatico ). Sebbene in pratica nessun processo fisico non stazionario possa essere esattamente fisicamente reversibile o isoentropico, non c'è limite noto alla vicinanza con cui possiamo avvicinarci alla reversibilità perfetta, in sistemi sufficientemente ben isolati dalle interazioni con ambienti esterni sconosciuti, quando le leggi della fisica che descrivono l'evoluzione del sistema sono noti con precisione.

Una motivazione per lo studio delle tecnologie volte all'implementazione del calcolo reversibile è che offrono quello che si prevede essere l'unico modo potenziale per migliorare l' efficienza energetica computazionale dei computer oltre il limite fondamentale di von Neumann-Landauer di kT ln(2) energia dissipata per funzionamento irreversibile del bit . Sebbene il limite di Landauer fosse milioni di volte inferiore al consumo energetico dei computer negli anni 2000 e migliaia di volte inferiore negli anni 2010, i sostenitori del calcolo reversibile sostengono che ciò può essere attribuito in gran parte alle spese generali architettoniche che amplificano efficacemente l'impatto del limite di Landauer in pratica progetti di circuiti, in modo che potrebbe rivelarsi difficile per la tecnologia pratica progredire molto oltre gli attuali livelli di efficienza energetica se non vengono utilizzati i principi di calcolo reversibili.

Relazione con la termodinamica

Come è stato sostenuto per la prima volta da Rolf Landauer mentre lavorava in IBM , affinché un processo computazionale sia fisicamente reversibile, deve anche essere logicamente reversibile . Il principio di Landauer è l'osservazione rigorosamente valida che la cancellazione ignara di n bit di informazione nota deve sempre incorrere in un costo di nkT ln(2) in entropia termodinamica . Un processo computazionale discreto e deterministico si dice logicamente reversibile se la funzione di transizione che mappa i vecchi stati computazionali in quelli nuovi è una funzione biunivoca ; cioè gli stati logici di output determinano in modo univoco gli stati logici di input dell'operazione di calcolo.

Per i processi computazionali non deterministici (nel senso di probabilistici o casuali), la relazione tra vecchi e nuovi stati non è una funzione a valore singolo e il requisito necessario per ottenere la reversibilità fisica diventa una condizione leggermente più debole, ovvero che la dimensione di un dato insieme di possibili stati computazionali iniziali non diminuisce, in media, man mano che il calcolo procede in avanti.

Reversibilità fisica

Il principio di Landauer (e in effetti, la stessa seconda legge della termodinamica ) può anche essere inteso come una conseguenza logica diretta della sottostante reversibilità della fisica , come si riflette nella formulazione hamiltoniana generale della meccanica e nell'operatore unitario di evoluzione temporale di meccanica quantistica più specificamente.

L'implementazione del calcolo reversibile equivale quindi ad apprendere come caratterizzare e controllare la dinamica fisica dei meccanismi per eseguire operazioni computazionali desiderate in modo così preciso da poter accumulare una quantità totale trascurabile di incertezza riguardo allo stato fisico completo del meccanismo, per ogni operazione logica che viene eseguito. In altre parole, bisognerebbe tracciare con precisione lo stato dell'energia attiva coinvolta nello svolgimento delle operazioni di calcolo all'interno della macchina, e progettare la macchina in modo tale che la maggior parte di questa energia venga recuperata in una forma organizzata che possa essere riutilizzati per operazioni successive, piuttosto che essere lasciati dissipare sotto forma di calore.

Sebbene il raggiungimento di questo obiettivo rappresenti una sfida significativa per la progettazione, la produzione e la caratterizzazione di nuovi meccanismi fisici ultra precisi per l' elaborazione , al momento non vi è alcuna ragione fondamentale per pensare che questo obiettivo non possa essere raggiunto, consentendoci un giorno di costruire computer che generano molto meno di 1 bit di entropia fisica (e dissipano in calore molto meno di kT ln 2 energia) per ogni operazione logica utile che svolgono internamente.

Oggi, il campo ha alle spalle un corposo corpo di letteratura accademica. Un'ampia varietà di concetti di dispositivi reversibili, porte logiche , circuiti elettronici , architetture di processori, linguaggi di programmazione e algoritmi applicativi è stata progettata e analizzata da fisici , ingegneri elettrici e informatici .

Questo campo di ricerca attende lo sviluppo dettagliato di una tecnologia di dispositivi logici di alta qualità, economica e quasi reversibile, che includa meccanismi di clock e sincronizzazione altamente efficienti dal punto di vista energetico , o ne eviti la necessità grazie alla progettazione asincrona. Questo tipo di solido progresso ingegneristico sarà necessario prima che il vasto corpo di ricerche teoriche sul calcolo reversibile possa trovare applicazione pratica nel consentire alla tecnologia informatica reale di aggirare le varie barriere a breve termine alla sua efficienza energetica, incluso il legame von Neumann-Landauer. Questo può essere aggirato solo con l'uso del calcolo logicamente reversibile, a causa della seconda legge della termodinamica .

Reversibilità logica

Per implementare il calcolo reversibile, stimarne il costo e giudicarne i limiti, può essere formalizzato in termini di circuiti a livello di porta. Un modello semplificato di tali circuiti è quello in cui vengono consumati gli ingressi (tuttavia, si noti che le porte logiche reali implementate ad esempio in CMOS non lo fanno). In questo quadro di modellazione, un gate inverter (NOT) è reversibile perché può essere annullato . La porta esclusiva o (XOR) è irreversibile perché i suoi due ingressi non possono essere ricostruiti in modo univoco dalla sua singola uscita. Tuttavia, una versione reversibile della porta XOR, la porta NOT controllata (CNOT), può essere definita preservando uno degli ingressi. La variante a tre ingressi della porta CNOT è denominata porta Toffoli . Conserva due dei suoi input a, b e sostituisce il terzo c con . Con , questo dà la funzione AND e con questo dà la funzione NOT. Pertanto, la porta di Toffoli è universale e può implementare qualsiasi funzione booleana reversibile (dato un numero sufficiente di bit ausiliari inizializzati a zero). Più in generale, le porte reversibili che consumano il loro input non hanno più input che output. Un circuito reversibile collega le porte reversibili senza fanout e loop. Pertanto, tali circuiti contengono un numero uguale di cavi di ingresso e di uscita, ciascuno dei quali attraversa un intero circuito. Allo stesso modo, nel modello di calcolo della macchina di Turing , una macchina di Turing reversibile è una la cui funzione di transizione è invertibile, in modo che ogni stato della macchina abbia al massimo un predecessore.

Yves Lecerf propose una macchina di Turing reversibile in un articolo del 1963, ma apparentemente ignaro del principio di Landauer, non approfondì ulteriormente l'argomento, dedicando la maggior parte del resto della sua carriera all'etnolinguistica. Nel 1973 Charles H. Bennett , presso IBM Research, dimostrò che una macchina di Turing universale poteva essere resa sia logicamente che termodinamicamente reversibile, e quindi in grado, in linea di principio, di eseguire un numero arbitrariamente grande di passi di calcolo per unità di energia fisica dissipata, se operata sufficientemente lentamente. I computer termodinamicamente reversibili potrebbero eseguire calcoli utili a velocità utile, dissipando notevolmente meno di kT di energia per passo logico. Nel 1982 Edward Fredkin e Tommaso Toffoli proposero il Billiard ball computer , un meccanismo che utilizzava le classiche sfere rigide per eseguire calcoli reversibili a velocità finita con dissipazione nulla, ma che richiedeva un perfetto allineamento iniziale delle traiettorie delle palle, e la recensione di Bennett ha confrontato queste "Browniane" e Paradigmi "balistici" per il calcolo reversibile. A parte la motivazione del calcolo efficiente dal punto di vista energetico, le porte logiche reversibili hanno offerto miglioramenti pratici delle trasformazioni di manipolazione dei bit nella crittografia e nella computer grafica. Dagli anni '80, i circuiti reversibili hanno attirato l'interesse come componenti di algoritmi quantistici e, più recentemente, nelle tecnologie fotoniche e di nanoinformatica in cui alcuni dispositivi di commutazione non offrono alcun guadagno di segnale .

Sono disponibili indagini sui circuiti reversibili, sulla loro costruzione e ottimizzazione, nonché sulle recenti sfide della ricerca.

Guarda anche

Riferimenti

Ulteriori letture

link esterno