1
Download Computacion Reversible
Document related concepts
Transcript
COMPUTACIÓN REVERSIBLE Y
TERMODINÁMICA DE LA COMPUTACIÓN
Vicente Moret Bonillo
Senior Member, IEEE
Basado en el texto
“Feynman Lectures on Computation”
PUERTAS Y LÓGICA COMBINATORIA
2
ALGUNAS OPERACIONES SENCILLAS
Sumas
Transferencias
Control de decisiones
SISTEMA DE CÓMPUTO BINARIO
DÍGITOS “0” Y “1”
OPERACIÓN “Suma”
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS Y LÓGICA COMBINATORIA
3
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS Y LÓGICA COMBINATORIA
4
REGLAS BÁSICAS DE LA SUMA BINARIA
0
+
0
=
0
0
+
1
=
1
1
+
0
=
1
1
+
1
=
1
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
+
1
Acarre
o
PUERTAS Y LÓGICA COMBINATORIA
5
TABLA BOOLEANA PARA LA SUMA BINARIA
A
B
S
C
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS Y LÓGICA COMBINATORIA
6
UN “MEDIO SUMADOR” COMO UNA CAJA NEGRA
CON DOS ENTRADAS (A y B) Y DOS SALIDAS (S y C)
∑
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS Y LÓGICA COMBINATORIA
7
Tabla de verdad de AND
A
B
0
0
A and
B
0
0
1
0
La puerta AND
A
B
1
0
0
1
1
1
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
A and
B
PUERTAS Y LÓGICA COMBINATORIA
8
A and B es 1 si, y sólo si, A=1 y B=1
El BIT de acarreo y el operador AND son “lo mismo”
El BIT de acarreo (C) del semisumador se puede
obtener directamente introduciendo las señales A y B
como entradas de una puerta AND
Siguiendo el mismo razonamiento… ¿Cómo podemos
obtener el BIT suma del sumador (S) utilizando otra
operación lógica?
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS Y LÓGICA COMBINATORIA
9
Tabla de verdad de XOR
A
B
0
0
A xor
B
0
0
1
1
La puerta XOR
A
B
1
0
1
1
1
0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
A xor
B
PUERTAS Y LÓGICA COMBINATORIA
10
Tabla de verdad de
OR
A
B
A or B
0
0
La puerta OR
0
A
0
1
1
1
0
1
1
1
1
A or B
B
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS Y LÓGICA COMBINATORIA
11
A xor B es 1, si A=1, o B=1, pero no A=B=1
A xor B equivale al BIT suma del semisumador
AND-XOR-OR son ejemplos de “Funciones de
Conmutación”
Las funciones de conmutación tienen como
entrada algunas variables binarias y calculan
alguna función binaria
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS Y LÓGICA COMBINATORIA
12
A
La Identidad
A
A
A
0
0
1
1
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS Y LÓGICA COMBINATORIA
13
A
La puerta NOT
B
A
B
0
1
1
0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS Y LÓGICA COMBINATORIA
14
La operación IDENTIDAD, en un sistema
abstracto, puede considerarse como un simple
“cable”
En sistemas reales, la IDENTIDAD es un
“retardo”
A or B es lo mismo que ¬ {(¬ A) and (¬ B)}
El conjunto {AND, OR, NOT} es un conjunto
completo, por medio de cuyos elementos
puede, en principio, construirse “todas las
posibles” funciones lógicas
Existen
operadores que por sí solos forman un
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
conjunto completo
PUERTAS REVERSIBLES
15
La operación FANOUT y la operación
EXCHANGE
FANOUT
EXCHANGE
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
16
FANOUT divide una entrada (cable) en dos o
más
EXCHANGE simplemente intercambia un par
de conexiones
Estas dos operaciones “obvias” van a ser
necesarias para discutir sobre la
REVERSIBILIDAD
Supondremos, además, que disponemos de
suficientes CEROS y UNOS durante todo el
tiempo
que deseemos
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
17
Las operaciones AND, ¬ AND, OR, XOR son
IRREVERSIBLES: A partir de la salida no se
puede reconstruir la entrada
Con operaciones irreversibles perdemos
información de forma irreversible
Una operación REVERSIBLE es la que tiene la
suficiente información en la salida para que
podamos deducir la entrada
La reversibilidad es imprescindible para estudiar
la Termodinámica de la Computación, ya que nos
permite realizar cálculos de Energía Libre, y
conocer la Eficiencia Física de la Computación
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
18
Bennet y Fredkin fueron los primeros que,
independientemente, estudiaron la posibilidad
de construir “ordenadores reversibles”
Para ello se requieren “puertas lógicas
reversibles”:
NOT…………………………………….. (N)
CONTROLLED NOT………………………
(CN)
CONTROLLED CONTROLLED NOT………
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
(CCN)
COMPUTACIÓN
PUERTAS REVERSIBLES
19
N es un NOT convencional, que es claramente
reversible
CN es un dispositivo con dos entradas y dos
salidas
A
A*
B
B*
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
20
En la puerta CN la estrella (en adelante X), es
un NOT controlado por la entrada al cable O
Si la entrada al cable O es “UNO”, la entrada
al cable X se invierte
Si la entrada O es “CERO” la puerta N no
funciona y la señal X pasa sin modificarse
La entrada en la línea O activa una puerta N
en la línea inferior
La salida O es siempre la misma que la
entrada
OREVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
COMPUTACIÓN
PUERTAS REVERSIBLES
21
Tabla booleana de la puerta CN
A
B
A*
B*
0
0
0
0
0
1
0
1
1
0
1
1
1
1
1
0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
22
Se puede interpretar B* como la salida de una
puerta XOR con entradas A y B: B* = XOR
(A,B)
CN es reversible sin más que repetir la
A
operación
A
B
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
B
PUERTAS REVERSIBLES
23
Reversibilidad de CN
La salida B* es la salida que tendríamos a partir de una puerta XOR
alimentada con A y B
El dispositivo no es el mismo puesto que la puerta CN produce
realmente dos salidas
Esta puerta es perfectamente reversible ya que, una vez conocida la
salida, siempre podemos reproducir la entrada
A
0
0
1
1
B
0
1
0
1
A*
0
0
1
1
B*
0
1
1
0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
A**
0
0
1
1
B**
0
1
0
1
PUERTAS REVERSIBLES
24
Las puertas N y CN no bastan para “hacerlo
todo”
Necesitamos algo más: la puerta CCN
A
A*
B
B*
C
C*
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
25
En CCN
Hay 2 líneas de control, A y B / A* = A , B* = B
La línea C sólo es activada cuando A = 1 y B = 1
En este último caso: C* = ¬ C
Si mantenemos A = B = 1 : CCN = N
Si sólo mantenemos A = 1 : CCN = CN, con A y B
inputs
La puerta CCN forma por sí sola un conjunto
completo
de operadores
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
26
Tabla booleana de la puerta CCN
A
B
C
A*
B*
C*
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
0
1
1
0
1
1
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
27
Reversibilidad de CCN
A
B
C
A*
B*
C*
A**
B**
C**
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
1
1
0
1
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
28
La puerta CCN es por sí misma un conjunto completo
de operadores
AND se construye fijando C = 0 y alimentando la
puerta con A y B según:
A
B
C
A*
B*
C*
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
1
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
29
Con CCN, NAND se construye fijando C = 1 y
alimentando la puerta con A y B:
A
B
C
A*
B*
C*
0
0
1
0
0
1
0
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
30
XOR se construye fijando A ó B = 1 :
A
B
C
A*
B*
C*
1
0
0
1
0
0
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
1
1
0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
31
Un Sumador Completo de números de 1-bit
A
Suma
B
C
Acarre
o
OBJETIVO : Sumar A , B y C para obtener la Suma y el Acarreo
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
32
La operación anterior no es reversible
No es posible reconstruir las tres entradas a
partir de la Suma y el Acarreo
Queremos un Sumador Reversible
Necesitamos más información en la salida
Para resolver el problema necesitamos…
2 líneas extra que salgan de la puerta
1 línea extra en la entrada, con un valor fijo (e.g.
0)
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
33
PROCEDIMIENTO
Utilizar N, CN, CCN (o sólo CCN)
Construir AND, OR, XOR, con los que se puede
construir un sumador
Utilizar la redundancia de las salidas extra
Organizar el sistema de forma que las dos líneas
extra, aparte de las salidas de Suma y Acarreo,
sean precisamente A y B
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
34
El Sumador Completo Reversible
A
X
B
Y
C
SUMA
0
ACARRE
O
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
35
La puerta de FREDKIN
Puerta reversible
El número de “1” y de “0” no cambia nunca
Introduce un elemento que realiza un intercambio
controlado
A
A* = A
B
B*
C
C*
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
36
Funcionamiento de la puerta de Fredkin
Si A = 0 → B y C no cambian : B* = B , C* = C
Si A = 1 → B* = C : C* = B
Con este dispositivo el número de CEROS y de
UNOS no varía
CONSTRUIR LA TABLA BOOLEANA DE LA
PUERTA DE FREDKIN
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
PUERTAS REVERSIBLES
37
EJERCICIOS
Diseñar un semisumador, o sumador simple,
utilizando puertas AND , OR y NOT
Diseñar un sumador completo de números de 1bit
Construir un OR reversible a partir de la puerta
CCN
Diseñar un sumador completo reversible de
números de 1-bit
Demostrar que la puerta de Fredkin se puede
utilizar para
realizar
todas las
operaciones lógicas
COMPUTACIÓN
REVERSIBLE
Y TERMODINÁMICA
DE LA
COMPUTACIÓN
en lugar de la puerta CCN
PUERTAS REVERSIBLES
38
Análisis:
La puerta N acepta 1 entrada y devuelve 1 salida
La puerta CN acepta 2 entradas y devuelve 2 salidas
La puerta CCN acepta 3 entradas y devuelve 3 salidas
La puerta de Fredkin acepta 3 entradas y devuelve 3
salidas
Las cuatro puertas son reversibles
¿Para construir una puerta reversible es imprescindible
que el número de entradas coincida con el número de
salidas?
¿Por qué podemos decir –y por qué esto es
importante-que una computación reversible se
efectúa con coste cero de energía?
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
39
LA FÍSICA DE LA
INFORMACIÓN
¿Cuál es la energía MÍNIMA necesaria para
realizar una computación?
Enfoque desde la definición física del contenido
de información de un mensaje
Shannon pretendía resolver el problema de la
transmisión de mensajes a través de cables
reales
Interferencias con el mundo físico
Posibilidad de abordar el problema de la
computación desde la física.
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
40
LA FÍSICA DE LA
INFORMACIÓN
Un modelo sencillo de mensaje enviado
Supóngase
un número no determinado de
cajas pegadas entre si
En cada caja hay una partícula
Cada partícula puede estar
A
la derecha de la caja
A la izquierda de la caja
Si
una partícula está a la derecha es un bit 1
Si una partícula está a la izquierda es un bit 0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
41
LA FÍSICA DE LA
INFORMACIÓN
UN MENSAJE “ATÓMICO” BÁSICO
Cuando la fila de cajas pasa por delante de mi,
mirando dónde está cada partícula puedo obtener
el correspondiente bit
1
1
0
0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
1
0
42
LA FÍSICA DE LA
INFORMACIÓN
El modelo físico apropiado para estudiar este
sistema es la Física de los Gases, o Teoría
Cinética de los gases
Sea un gas con N partículas
El gas ocupa un volumen V1
Cada partícula del gas es “libre”
No hay fuerzas de atracción o de repulsión
entre las partículas del gas
La última restricción es cierta a presiones
bajas
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
43
LA FÍSICA DE LA
INFORMACIÓN
Compresión isotérmica del gas
Baño térmico a una temperatura fija T
La temperatura del sistema permanece
constante
V1 → V2
V1
V2
Baño a Temperatura Constante
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
44
LA FÍSICA DE LA
INFORMACIÓN
¿Cuánto trabajo se necesita para comprimir el
gas?
∂W = F∂x
Si _ < p > _ es _ la _ presión _ del _ gas
y _ < A > _ es _ el _ área _ del _ dispositivo _ de _ compresión
y _ dado _ que _ < F = p × A >
y _ que _ ∂V = A∂x → ∂W = p∂V
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
45
LA FÍSICA DE LA
INFORMACIÓN
Aplicando ahora la Teoría de los Gases
p × V = NkT
N = n º _ de _ partículas _ del _ gas
k = cte _ de _ Boltzmann
T = cte
Integrando :
V2
V2
NkT
W=∫
dV = NkT ln
V
V1
V1
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
46
LA FÍSICA DE LA
INFORMACIÓN
ANÁLISIS
W es negativo → Convención : El trabajo
realizado para comprimir un gas es negativo
Generalmente, cuando un gas es comprimido, el
gas se calienta
En nuestro la Energía Cinética no ha variado
El baño térmico ha absorbido el incremento de
energía de las partículas del gas → Compresión
Isotérmica
Proceso cuasi-estático → Realizado muy
lentamente
COMPUTACIÓN
REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
47
LA FÍSICA DE LA
INFORMACIÓN
Termodinámica del proceso : Cambio de
Estado
V1 → V2
U = ∑i Ui
Energía total < U > :
Los cambios de estado se definen a partir de :
F = Energía Libre
S = Entropía
F = U − TS
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
48
LA FÍSICA DE LA
INFORMACIÓN
F nos permite tratar diferencias entre estados
cuando entre ellos no hay diferencias
mecánicas
A temperatura
∂F =constante
∂U − T∂S :
∂U = 0 → ∂F = −T∂S
δF es la energía trasvasada
al baño térmico
V1
V2
∂F = −W = NkT ln
V2
→ ∆S = Nk ln
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
V1
49
LA FÍSICA DE LA
INFORMACIÓN
SEGUNDA LEY DE LA TERMODINÁMICA
Para Procesos Reversibles
∂F ∂Q
∂S = −
≈
T
T
Para Procesos Irreversibles
∂F ∂Q
∂S ≥ −
≈
T
T
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
50
LA FÍSICA DE LA
INFORMACIÓN
ABSTRACCIÓN
El gas sólo tiene una partícula
N = 1
T , p , V , F , S … aparentemente no están
definidas
Tienen sentido si estudiamos el fenómeno
durante un tiempo suficientemente amplio, y
V1
promediando
Si : V 2 =
→ ∆F = kT ln(2) : ∆S = − k ln(2)
2
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
51
LA FÍSICA DE LA
INFORMACIÓN
SITUACIÓN GRÁFICA
V1
V2 = V1/2
El estado físico parece no haber cambiado
La energía cinética es la misma
Sin embargo F y S han cambiado
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
52
LA FÍSICA DE LA
INFORMACIÓN
EXPLICACIÓN
El conocimiento sobre las posibles posiciones de
la partícula de gas ha cambiado
En nuestro ejemplo, después de la compresión,
hay menos lugares en los que podemos buscar < y
encontrar > a la partícula de gas
Naturaleza estadística de la termodinámica
T , p , … son magnitudes estadísticas
S es una magnitud de naturaleza estadística,
pero…
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
53
LA FÍSICA DE LA
INFORMACIÓN
Naturaleza estadística de la entropía < S >
T , p , … son magnitudes estadísticas de carácter
macroscópico , que se obtienen a partir del promedio
de una suma de valores individuales , es decir , son el
promedio de una suma de propiedades microscópicas
S es una magnitud de naturaleza estadística , pero
está directamente relacionada con la probabilidad de
que el gas esté en la configuración en la que se
encuentra
< Configuración > es una ordenación concreta , o un
conjunto de ordenamientos , posiciones y momentos ,
para cada una de las N partículas constituyentes
Configuración es un punto o región concreta del <
Espacio de Fases >
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
54
LA FÍSICA DE LA
INFORMACIÓN
ENTROPÍA Y PROBABILIDAD
Si la probabilidad de una determinada
configuración es ω → S ≈ k ln ω
Cuanto mayor es ω mayor es la entropía del
sistema
Como todas las probabilidades, las ω se suman
Podemos calcular la probabilidad de encontrar al
gas en un rango de configuraciones
Cuanto menos sepamos de la configuración de
un gas, en más estados puede estar, mayor es ω,
y mayor es S
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
55
LA FÍSICA DE LA
INFORMACIÓN
LA ENTROPÍA EN LA COMPRESIÓN
ISOTERMA
El momento de las partículas del gas no ha
cambiado
δU = 0
Cada partícula tiene acceso a menos posiciones
espaciales
El gas tiene ahora una configuración con menor ω y,
por lo tanto, su entropía ha disminuido
ω de la Termodinámica, la
Pero, por la segunda∂Ley
∂S ≈ k
≥0
ω
entropía total nunca disminuye
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
56
LA FÍSICA DE LA
INFORMACIÓN
EXPLICACIÓN
El sistema no está aislado
Hemos evacuado el calor al baño térmico
El flujo de calor que llega al baño térmico
incrementa su entropía
CUANTA MENOS INFORMACIÓN TENEMOS
SOBRE UN ESTADO MAYOR ES SU
ENTROPÍA
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
57
LA FÍSICA DE LA
INFORMACIÓN
ANÁLISIS DE CONSISTENCIA
La naturaleza estadística de S nos permite
definirla para un sistema de una única partícula
Si comprimimos el volumen en un factor 2 →
Dividimos por la mitad el número de posiciones
espaciales de la partícula
Lo anterior equivale a decir que dividimos a la
mitad el número de configuraciones que la
partícula puede ocupar
∂S = k ln 2
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
58
LA FÍSICA DE LA
INFORMACIÓN
¿Dónde encaja esta física en el tema de la
información?
Mensaje típico
Sobre algunos de los bits no tenemos conocimiento
previo
Sobre otros sí tenemos conocimiento previo
La información de un mensaje es proporcional a
la energía libre necesaria para reiniciar toda la
COMPUTACIÓN
REVERSIBLE Y TERMODINÁMICA DE LA
cinta
a cero
COMPUTACIÓN
59
LA FÍSICA DE LA
INFORMACIÓN
Reiniciar a cero es comprimir cada celda de la
cinta para asegurarnos de que su partícula
constituyente está en la posición < 0 >
Problemas
Simetría no natural entre < 0 > y < 1 >
Si una partícula está en la parte < 0 > , para
reiniciar no hay que hacer nada → ∆F = 0
Si una partícula está en la parte < 1 > , para
reiniciar hay que hacer un trabajo → ∆F = 0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
60
LA FÍSICA DE LA
INFORMACIÓN
¿ No sería lo mismo reiniciar la cinta a < 1 > ?
¿ No deberíamos obtener la misma respuesta
sólo en el caso de tener el mismo número de
< 0 > que de < 1 > ?
Sutileza…
Sólo si no conocemos en qué parte de cada caja
se encuentra la partícula gastamos energía libre
Ésta es la única circunstancia en la que el
espacio de fases se divide por la mitad y la
entropía aumenta
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
61
LA FÍSICA DE LA
INFORMACIÓN
Si sabemos de antemano la posición de la
partícula no gastamos energía al reiniciar
Esto ocurre independientemente de la
posición inicial de la partícula
LA INFORMACIÓN DE UN MENSAJE ESTÁ
CONTENIDA EN LOS BITS SORPRESA
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
62
LA FÍSICA DE LA
INFORMACIÓN
∆ F< 1 > → < 0 > = ∆ F < 0 > → < 0 > = 0 : si
conocemos de antemano la posición de la
partícula
Este argumento se utiliza frecuentemente en
Computación Reversible
CONTEXTO
Naturaleza abstracta e ideal del sistema
considerado
Interés exclusivo en la energía contenida en el
mensaje
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
La energía del mensaje
está definida por las
COMPUTACIÓN
posiciones de las partículas en las cajas de la
63
LA FÍSICA DE LA
INFORMACIÓN
COSTE CERO…
INCONVENIENTE
El proceso < giro > tiene que realizarse a
velocidad prácticamente nula : infinitamente
despacio
Proceso cuasi-estático
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
64
LA FÍSICA DE LA
INFORMACIÓN
UNA REINICIACIÓN MÁS REALISTA…
También en el límite infinitesimal de velocidad
∆ F = 0 porque cualquier trabajo que efectuemos
sobre un extremo se recupera por el otro
Sólo cuando no sabemos dónde está la partícula
hay que realizar una compresión
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
65
LA FÍSICA DE LA
INFORMACIÓN
LA COMPRESIÓN REQUIERE ENERGÍA
LIBRE
AL COMPRIMIR DISMINUIMOS NUESTRA
IGNORANCIA SOBRE LA POSICIÓN DE LA
PARTÍCULA
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
66
LA FÍSICA DE LA
INFORMACIÓN
LA APROXIMACIÓN DE BENNETT
Propone utilizar la información del mensaje de la
cinta como combustible
Relacionó la información de la cinta con su poder
calorífico; i.e. con la cantidad de energía que
podemos obtener de ella
Temperatura T
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
67
LA FÍSICA DE LA
INFORMACIÓN
Motor en contacto con un baño térmico
Por un extremo entra la cinta
Por el otro extremo sale la cinta
Al principio la cinta está en blanco, i.e. todas sus
partículas está en el estado < 0 >
Este sistema puede usarse para proporcionar
trabajo útil y mover el motor
Necesitamos un pistón.
Cuando llega cada celda el pistón se desplaza
hasta la mitad de la celda
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
68
LA FÍSICA DE LA
INFORMACIÓN
El baño térmico calienta la celda
La partícula choca contra el pistón
empujándolo isotérmicamente hacia fuera
De esta forma se genera trabajo en el motor
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
69
LA FÍSICA DE LA
INFORMACIÓN
Proceso inverso al de compresión del gas
Sobre el pistón se realiza trabajo que podemos
usar
Para una
cinta
F = nkT
ln 2de < n > bits…
T = Temperatura _ del _ baño _ térmico
La cinta que sale ha sido aleatorizada
Después de que el pistón ha sido empujado, la
partícula que lo empujó puede estar en cualquier
lugar dela celda
Para
saber dónde está hay que hacer una medida
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
70
LA FÍSICA DE LA
INFORMACIÓN
GENERALIZACIÓN…
Un pistón maniobrable nos permite extraer
trabajo de cintas que tienen algún < 1 >
Si < 1 > → cambiar pistón a la otra parte de la
celda, llevándolo hasta el borde de la mitad < 1 >
Trabajo útil = kT ln2
La cinta sale de la máquina con un contenido
aleatorio
Sabemos qué bit está entrando en la máquina
Sólo así podemos tener al pistón preparado
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
71
LA FÍSICA DE LA
INFORMACIÓN
Si el pistón está en la posición < 0 > y
encuentra un < 1 > hay que hacer trabajo para
llevar a la partícula a la posición < 0 >
Luego, cuando la partícula se expande, nos
devuelve el trabajo realizado previamente :
∆ Fneto = 0
Una cinta aleatoria tiene poder calorífico nulo
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
72
LA FÍSICA DE LA
INFORMACIÓN
Feynman
Parte de una cinta aleatoria
Realiza trabajo sobre la cinta
Termina con una cinta totalmente reiniciada : < 0
>
Bennett
Parte de una cinta reiniciada : < 0 >
Obtiene trabajo de la cinta
Termina con una cinta aleatoria
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
73
LA FÍSICA DE LA
INFORMACIÓN
Definición de Bennett del concepto de
Información
Sea una cinta con N bits : Se define Información
< I > de acuerdo con la expresión…
Poder calorífico de la cinta = (N – I) kT ln2
Si la cinta da una carga de combustible
completa de (kT ln2)/bit → contiene
información nula
En este caso la cinta contiene un “mensaje”
completamente predecible
Las aproximaciones de Feynman y Bennett
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
son, desde el punto deCOMPUTACIÓN
vista físico, totalmente
simétricas
74
EL DEMONIO DE MAXWELL Y LA
TERMODINÁMICA DE LA
MEDIDA
El estudio del demonio de Maxwell llevó a
físicos como Bennett y Landauer a establecer
conclusiones sobre la computación reversible
El Demonio de Maxwell
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
75
EL DEMONIO DE MAXWELL Y LA
TERMODINÁMICA DE LA
MEDIDA
Descripción…
Demonio sentado sobre una caja dividida en 2 partes
Cada parte contiene gas cuyas partículas tienen una
distribución aleatoria de posiciones y de velocidades
En el tabique de separación hay una puerta
El demonio observa cada parte de la caja y elige :
derecha → rápidas , izquierda → lentas
Cuando ve una partícula rápida que se dirige hacia la
puerta desde la dirección adecuada, la abre
confinando a la partícula, y la cierra inmediatamente
Cuando ve una partícula lenta que se dirige hacia la
puerta desde la dirección adecuada, la abre
confinando a la partícula, y la cierra inmediatamente
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
76
EL DEMONIO DE MAXWELL Y LA
TERMODINÁMICA DE LA
MEDIDA
RESULTADO
Transcurrido un tiempo suficiente, el demonio de
Maxwell habrá separado las partículas rápidas de
las lentas : i.e. las partículas calientes de las
partículas frías
Habrá creado una diferencia de temperatura entre
las dos partes de la caja
La entropía del sistema habrá disminuido
¿ Se ha violado el segundo principio de la
Termodinámica ?
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
77
EL DEMONIO DE MAXWELL Y LA
TERMODINÁMICA DE LA
MEDIDA
ANÁLISIS…
En algún momento del proceso debe generarse
entropía
Esta entropía puede surgir como resultado de la
medida del demonio sobre la posición de las
partículas
Una forma de detectar partículas es iluminarlas, pero
esto implica la dispersión de al menos un fotón,
proceso que consume energía
Antes de mirar una partícula concreta, el demonio no
puede saber si se mueve en un sentido o en el otro
Cuando la observa, su incertidumbre < entropía > se
reduce a la mitad → Debe generarse entropía en el
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
entorno
COMPUTACIÓN
78
EL DEMONIO DE MAXWELL Y LA
TERMODINÁMICA DE LA
MEDIDA
Argumentación de Bennett
El demonio de Maxwell puede realizar sus medidas
con coste energético nulo
Para ello debe seguir ciertas reglas para grabar y
para borrar cualquier información que obtenga
Antes de medir :
El demonio está en un estado estándar S → Situación de
Incertidumbre
Después de medir :
L → Moviéndose a la izquierda
R→ Moviéndose a la derecha
S se sobre-escribe con L o con R según proceda
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
79
EL DEMONIO DE MAXWELL Y LA
TERMODINÁMICA DE LA
MEDIDA
Bennett demuestra que…
El proceso global de medida < incluyendo la sobreescritura de S > se realiza sin coste energético
El coste energético se produce cuando se borran L o
R para reiniciar al demonio al estado estándar S y
prepararlo para la siguiente medida
Fue un gran avance en el estudio de la
computación reversible el descubrimiento de que
en un proceso computacional la entropía no se
genera en la realización de la medida, sino al
borrar la información
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
80
COMPUTADORES
REVERSIBLES
Definimos COMPUTADOR REVERSIBLE
como aquél que da como salida el resultado
real de una computación y además la entrada
original
Se puede demostrar que esta computación se
puede realizar con un coste nulo de energía
El único coste en que se incurre aparece en la
reiniciación de la máquina para volver a
empezar
Esta reiniciación no depende de la
complejidad del cálculo. Sólo depende del
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
número de bits de la respuesta
COMPUTACIÓN
81
COMPUTADORES
REVERSIBLES
Se pueden tener N componentes funcionando
en una máquina, pero si la respuesta que se
obtiene es de sólo 1 bit, la energía que se
necesita para que todo funcione es : kT ln2
La computación reversible no necesita el
establecimiento de requisitos mínimos de
energía
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
LA COMPUTACIÓN < COPIA >
82
Utilizamos la computación COPIA como forma
de introducir los conceptos que subyacen en
la disipación de energía
Sean un conjunto de datos y su copia
Consideremos ambos como dos mensajes en
cinta idénticos
Podemos conocer el mensaje original o no
conocerlo
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
LA COMPUTACIÓN < COPIA >
83
PRIMER CASO
Si conocemos el mensaje original no gastamos
energía libre en borrar la cinta
Tampoco necesitamos energía libre para copiarla
SEGUNDO CASO
Si no conocemos el mensaje original gastamos
energía libre al borrar la cinta
No gastamos energía libre en borrar la copia
No hay más información en el conjunto {datos
, copia} que en el conjunto {datos}
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
LA COMPUTACIÓN < COPIA >
84
PROCESO GENERAL DE COPIA
Objeto original o < modelo >
El modelo puede contener un < 0 > o un < 1 >
El modelo es un dispositivo físico biestable : i.e.
un pozo de potencial
Copiadora
La copiadora puede tener un < 0 > o un < 1 >
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
LA COMPUTACIÓN < COPIA >
85
Estado inicial del modelo
Estado inicial de la copiadora
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
LA COMPUTACIÓN < COPIA >
86
Copiar → Hacer que el punto pase de un valle al
otro
Tenemos que poder manipular la curva de
potencial
Tenemos que conseguir que el valle de la
derecha sea energéticamente más favorable para
el punto
Parámetros ajustables y restricciones
Altura de Barrera
Profundidades relativas entre valles
Fuerza de interacción entre copiadora y modelo o
fuerza deREVERSIBLE
inclinación
COMPUTACIÓN
Y TERMODINÁMICA DE LA
COMPUTACIÓN
En todo momento habrá un único mínimo accesible al
t
LA COMPUTACIÓN < COPIA >
87
Proceso…
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
LA COMPUTACIÓN < COPIA >
88
Análisis ( 1 )…
Inicialmente el modelo está lejos de la copiadora
Incluso a distancia ejerce una ligera fuerza
inclinadora sobre la copiadora
Esta fuerza aumenta la profundidad del valle de
la copiadora que corresponde al valle ocupado en
el modelo
El potencial de la copiadora se ve ligeramente
modificado
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
LA COMPUTACIÓN < COPIA >
89
Análisis ( 2 )…
Acercamos suavemente el modelo a la copiadora
La fuerza de inclinación aumenta
El punto se desliza suavemente por la curva de
potencial
Ocupa el nuevo valle que es energéticamente
más favorable
Restauramos la barrera de potencial
Retiramos suavemente el modelo
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
LA COMPUTACIÓN < COPIA >
90
CONCLUSIÓN…
El proceso podría hacerse rápidamente
En este caso consumiría energía
Si el proceso es suficientemente lento el coste
energético es nulo
En este caso la disipación de energía es
despreciable
Para conseguir coste cero la computación
copia debe realizarse de forma cuasi-estática
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
91
UNA IMPLEMENTACIÓN
FÍSICA
Dispositivo físico bi-estable
2 agujas de brújula
2 dipolos magnéticos que pueden girar sobre sus ejes
Modelo físico y copiadora están hechas de este
dispositivo bi-estable
Cada elemento del par de agujas está ligado al
otro
Ambos elementos apuntan a la misma dirección
Podemos analizar el sistema en términos de una
sola variable
Esta variable es el ángulo Φ que las agujas
forman con la horizontal
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
92
UNA IMPLEMENTACIÓN
FÍSICA
Configuración angular permitida…
Φ
Φ
Configuración angular prohibida…
Φ1
Φ2
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
93
UNA IMPLEMENTACIÓN
FÍSICA
Estados estables y estados inestables
S
N
S
N
N
N
S
S
Energía potencial de un estado con ángulo Φ :
EΦ ≈ sen2Φ
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
94
UNA IMPLEMENTACIÓN
FÍSICA
Energía potencial en función de Φ
Sen2 Φ
1
0
Π/2
Π
3Π/2
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
1
95
UNA IMPLEMENTACIÓN
FÍSICA
Los mínimos están en…
Φ=0
Φ=Π
Los mínimos corresponden a los estados
estables
Los máximos corresponden a…
Φ = Π/2
Φ = 3Π/2
El sistema es bi-estable
Si las agujas están en uno de los dos mínimos se
necesitará energía para pasarlo al otro
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
96
UNA IMPLEMENTACIÓN
FÍSICA
Para modificar la barrera introducimos un
campo magnético vertical B que añade a la
energía potencial el término : -B sen Φ
Al aumentar B la barrera de potencial entre los
estados < 0 > y < Π > disminuye
B
B
Φ
B
Φ
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
Φ
97
UNA IMPLEMENTACIÓN
FÍSICA
Como antes, la fuerza de inclinación surge
como consecuencia de acercar el modelo a la
copiadora
Esta fuerza en el modelo está causada por el
campo magnético del bit dato
La fuerza es perpendicular a B, y en dirección
de las agujas en el modelo
Si < b > es la fuerza de inclinación, contribuye
a la energía potencial en : -b cos Φ
Esta situación rompe la simetría en : Π/2 y
3Π/2
y representa una inclinación
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
98
UNA IMPLEMENTACIÓN
FÍSICA
EL PROCESO DE COPIA
Copiadora en estado estándar
Φ=0
(→→)
Suavemente
Desplazamos la copiadora de una región B débil a
una de gran B hasta que se elimina la barrera, o
Empezamos a aumentar el campo B
En este momento el dipolo es vertical
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
99
UNA IMPLEMENTACIÓN
FÍSICA
Estado inicial inestable de la copiadora…
Acercamos el modelo a la copiadora < ya
ligeramente perturbada, pero no lo bastante >
Según se va acercando, el campo hace que
las agujas de la copiadora giren
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
100
UNA IMPLEMENTACIÓN
FÍSICA
Lo anterior ocurre si el nuevo estado es apropiado
Si el estado estándar y el estado del modelo
coinciden, las agujas volverán a su posición
original
A continuación alejamos el modelo
La copia liberada del campo B recupera la barrera
La copia finaliza
Este método de copia funciona si no sabemos en
qué estado se encuentra el modelo
Se puede comprobar que si el proceso se realiza
cuasi-estáticamente no cuesta ni energía, ni
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
corriente,
ni nada
COMPUTACIÓN
101
COSTE ENERGÉTICO DE LA
COMPUTACIÓN FRENTE A
VELOCIDAD
Sea un computador reversible
Cuando un proceso se realiza de forma
reversible e infinitamente despacio → La
energía libre es cero
Restricción…
Estamos ejecutando un proceso a velocidad < r >
En un instante dado es < r > veces más probable
realizar un paso computacional hacia delante que
hacia atrás
Fpaso = kT ln r
En cada paso computacional :
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
102
COSTE ENERGÉTICO DE LA
COMPUTACIÓN FRENTE A
VELOCIDAD
Niveles de energía : La transición general
A
AVANC
E
E1
E2
El computador puede hacer una computación
o deshacerla < avance , retroceso >
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
103
COSTE ENERGÉTICO DE LA
COMPUTACIÓN FRENTE A
VELOCIDAD
E1 ≠ E2
La energía disminuye en la dirección de la
computación
A = Energía de Activación = Energía que se le
debe suministrar al sistema para que
evolucione
Fluctuaciones térmicas…
Siempre que su energía sea mayor que A harán
que el computador se mueva aleatoriamente
entre estados
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
104
COSTE ENERGÉTICO DE LA
COMPUTACIÓN FRENTE A
VELOCIDAD
La probabilidad < ω > de que un sistema pase
a un estado Ei es la probabilidad de que
adquiera suficiente energía para pasar A y
caer en Ei
FE1→E2 = A – E1
FE2→E1 = A – E2
Mecánica Estadística…
La probabilidad de una transición entre dos
∂Edifieren en una cantidad
estados cuyas energías
C exp(− )
kT
positiva δE es :
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
105
COSTE ENERGÉTICO DE LA
COMPUTACIÓN FRENTE A
VELOCIDAD
< C > es un factor que depende de las fluctuaciones
térmicas
Para calcular las tasas de transición entre estados
necesitamos otro factor < X > que depende de
propiedades moleculares, pero que no depende de la
_
_
exp[
(
1) / kT ]
Tasa
de
avance
=
CX
−
A
−
E
energía
Tasa _ de _ retroceso = CX exp[−( A − E 2)kT ]
Tasa _ de _ avance
= exp[( E1 − E 2) / kT ]
Tasa _ de _ retroceso
Fpaso = kT ln r = E1 − E 2
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
106
ACCESIBILIDAD DE
ESTADOS
PROBLEMA :
Investigar cómo se conduce un computador en
una dirección determinada
RESTRICCIONES…
Los estados computacionales no difieren en su
energía
Los estados computacionales difieren en su
disponibilidad
El computador va a elegir a qué estado se dirige
basándose en el número de estados equivalentes
que son accesibles
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
107
ACCESIBILIDAD DE
ESTADOS
El computador así diseñado funciona por
DIFUSIÓN
< ni > es el número
estadosnaccesibles
Tasa _ dede
_ avance
2
r=
Tasa _ de _ retroceso
=
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
n1
108
ACCESIBILIDAD DE
ESTADOS
Recordando…
S ≈ k ln ω
y:
kT ln r = kT (ln n 2 − ln n1) = ( S 2 − S 1)T = T∆S
La pérdida de energía por paso es igual a la
entropía generada en ese paso multiplicada
por la temperatura
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
MINIMIZANDO ENERGÍA
109
Problema…
¿ Podemos, en una situación real, minimizar la
energía consumida en cada paso de computación
?
Contexto…
En un computador reversible las probabilidades
de avance y de retroceso son iguales
No tenemos pérdida de energía
El proceso tiene que efectuarse cuasiestáticamente
COMPUTACIÓN
REVERSIBLE
Y TERMODINÁMICA
DE LA
Se requiere
un tiempo
infinito
COMPUTACIÓN
MINIMIZANDO ENERGÍA
110
Aproximación…
Para mantener al sistema moviéndose hay que
facilitar de alguna manera el proceso, por
ejemplo:
Bajando algo las energías de pasos sucesivos
Haciendo los pasos sucesivos más accesibles
Tasa de avance : f
Tasa de retroceso : b
f = b + ε
ε es muy pequeño
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
MINIMIZANDO ENERGÍA
111
Energía / paso = kT ln r = kT ln( f / b)
Pero : f / b = 1 + ε / b
Energía / paso = kT ln(1 + ε / b)
Como _ ε _ es _ pequeño : ln(1 + ε / b) ≈ ε / b
Energía / paso = kT ln(1 + ε / b) ≈ kT
Pero : ε / b =
ε
b
f
f −b
:
−1 =
b
b
f −b
Entonces : Energía / paso = kT
⇔ε →0
b
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
MINIMIZANDO ENERGÍA
112
Una expresión aproximadamente igual a la
anterior es:
f −b
Energía / paso = kT
( f + b) / 2
Análisis…
Sea :
f −b
f −b
f − b 2 f − 2b
=
→
=
b
( f + b) / 2
b
f +b
Entonces : ( f − b) × ( f + b) = f 2 − b 2 = 2 fb − 2b 2
f = b + ε : ε → 0 : f 2 − b 2 = 2( f 2 − b 2 ) ⇔ f = b
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
MINIMIZANDO ENERGÍA
113
En la expresión : Energía / paso = kT
f −b
( f + b) / 2
ε
La diferencia con la expresión original es del orden
de
El numerador es la velocidad a la que se realiza la
computación
El denominador es la tasa media de transición :
2
Una medida del grado en que el ordenador oscila entre
avances y retrocesos
La expresión del denominador es , muy aproximadamente
,
el máximo desplazamiento posible
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
MINIMIZANDO ENERGÍA
114
En términos de Energía perdida en cada
paso…
υdesplazamiento
Energía _ perdida / paso = kT
υ max
Si queremos resaltar aspectos temporales de
esta computación…
Energía _ perdida / paso = kT
Tiempo _ mínimo _ empleado / paso
Tiempo _ realmente _ empleado / paso
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR GENERAL
REVERSIBLE
115
Una computación reversible tiene que
almacenar mucha información…
Parte de esta información es el resultado de la
computación
El resto es la información extra que necesitamos
para conseguir la reversibilidad
A
A
B
XOR (A , B) = suma
C=0
AND (A , B) = acarreo
Un sumador de 2 bits construido con puertas reversibles
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR GENERAL
REVERSIBLE
116
Restricciones de la computación reversible…
En un computador convencional, cuando se
realiza un paso hacia delante, no puede haber
ninguna ambigüedad
Con una máquina reversible tampoco puede
haber ninguna ambigüedad en los pasos < hacia
atrás >
Esta última característica es lo que hace que la
computación reversible sea radical y
esencialmente diferente de la computación
irreversible convencional
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
BENNET Y LA COMPUTACIÓN
REVERSIBLE GENERAL
117
Hipótesis de trabajo y diseño del computador:
Sistema de unidades lógicas reversibles unidas
entre sí
Introducimos un dato de entrada
Introducimos un conjunto de ceros “estándar” (o
de unos, que podemos negar con un NOT
reversible)
La unidad lógica hará su trabajo con el siguiente
resultado:
Respuesta deseada
BITS sobrantes
con
la historiaDEdel
COMPUTACIÓN
REVERSIBLE Y
TERMODINÁMICA
LA proceso
COMPUTACIÓN
BENNET Y LA COMPUTACIÓN
REVERSIBLE GENERAL
118
El computador reversible general (unidades lógicas <
M >)
DATOS
0
1
1
0
1
0
1
1
1
0
0
1
RESPUESTA
UNIDADES LÓGICAS
CEROS
ESTÁNDAR
0
0
0
0
0
1
0
0
0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
1
1
BASURA
0
BENNET Y LA COMPUTACIÓN
REVERSIBLE GENERAL
119
Se empieza con una cinta en blanco o
preestablecida
Se termina con mucho desorden
Vuelve a aparecer la entropía de la información
La aleatorización de ceros es el “combustible” que
mueve la máquina de Bennet
¿ Por qué, y cómo, el mantenimiento de esta
información puede hacer < desde un punto de
vista práctico > que la computación sea reversible
?
Solución: Añadir más cintas al sistema e
COMPUTACIÓN REVERSIBLE
Y TERMODINÁMICA
DE LAmáquina
introducir
los resultados
en
otra
COMPUTACIÓN
-1
reversible < M >
BENNET Y LA COMPUTACIÓN
REVERSIBLE GENERAL
120
EL COMPUTADOR REVERSIBLE SIN PÉRDIDA DE
ENTROPÍA
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
BENNET Y LA COMPUTACIÓN
REVERSIBLE GENERAL
121
< M > es reversible
< M-1 > también es reversible
< M-1 > es la inversa de < M >
FANOUT es en realidad un proceso de copia
Realmente siempre habrá algo de entropía al
tener que “conducir” un poco el proceso
La computación reversible realmente ahorra
trabajo
Habrá pérdida de energía cuando reiniciemos
el sistema para realizar otros cálculos
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
122
Fredkin , Toffoly y otros proponen el “uso de bolas
de billar” para computar
Simulan el movimiento de los bits a través de puertas
lógicas
El lanzamiento de las bolas es la entrada
La distribución resultante es la salida
Las bolas se mueven diagonalmente a través de una
malla plana
Las bolas obedecen las leyes ideales de la mecánica
clásica…
Fricción cero
Choques perfectamente elásticos
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
123
La computación básica en la colisión de dos
bolas
A
W
X
Y
B
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
Z
EL COMPUTADOR DE LA BOLA
DE BILLAR
124
A=0
A=1
B=0
B=1
W=1
W=0
X=1
X=0
Y=1
Y=0
Z=1
Z=0
→
→
→
→
→
→
→
→
→
→
→
→
No hay bola en la posición A
Hay bola en A y la lanzamos
No hay bola en la posición B
Hay bola en B y la lanzamos
La bola sale por W
La bola no sale por W
La bola sale por X
La bola no sale por X
La bola sale por Y
La bola no sale por Y
La bola sale por Z
La bola no sale por Z
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
125
Hay cuatro salidas posibles
2 salidas si falta una bola
2 salidas si hay choques
Ejemplo…
No hay bola en A
Si hay bola en B → sale por X
X=1⇔A=0yB=1
No hay bola en B
Si hay bola en A → sale por Y
Y=1⇔A=1yB=0
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
126
Si están las dos bolas A y B…
W=1
Z = 1
En términos lógicos:
X = B AND ¬ A
Y = A AND ¬ B
W , Z = A AND B
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
127
Estructura lógica de la computación básica en
la colisión
A
AΛB
B Λ¬ A
¬BΛ
A
B
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
AΛB
EL COMPUTADOR DE LA BOLA
DE BILLAR
128
FANOUT con bolas de billar
A = 1 → Señal de control en la entrada “on”
Salidas
( W = 1) Λ ( Z = 1) → Ramificación en B
B → BW Λ BZ
Si B = 0 → ( W = 0 ) Λ ( Z = 0 )
PROBLEMA :
Configurar el dispositivo de las dos bolas de billar
para obtener una puerta reversible CN
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
129
La puerta de colisión…
Proceso integrado “doble FANOUT”
2 bolas incidentes colisionan con bolas en reposo
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
130
La puerta de redirección…
CUATRO PUERTAS DE REDIRECCIÓN
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
131
Un dispositivo de cruce…
En un dispositivo de cruce las bolas son
indistinguibles
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
132
Un dispositivo interruptor...
A
B Λ¬ A
BΛA
B
A
Cruce desplazado
Independientemente de B, la salida (↓→) es siempre
A
Es un bit “sobrante” de control de la puerta
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
133
La puerta de Fredkin…
A
A* = A
B
B*
C
C*
Construir la puerta de Fredkin con puertas de
bolas de billar (… si sois capaces)
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
EL COMPUTADOR DE LA BOLA
DE BILLAR
134
Con puertas de bola de billar…
Podemos construir puertas CN
Podemos construir puertas CCN
Podemos construir puertas de intercambio
controlado
Si podemos construir puertas de intercambio
controlado, como la de Fredkin, podemos
construir cualquier tipo de computadora
Pero… ¿ qué va a pasar cuando podamos
construir computadoras tan pequeñas que
sólo incluyan unos pocos átomos ?
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
COMPUTACIÓN CUÁNTICA
135
¿ Qué podemos esperar de una computadora
que funcione de acuerdo con las leyes de la
mecánica cuántica ?
¿ Cuál va a ser el papel del principio de
incertidumbre de Heisenberg ?
¿ Cuál debería ser el tamaño mínimo de una
computadora ?
No podemos construir una computadora más
pequeña que un átomo : Necesitamos algo
sobre lo que escribir
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
COMPUTACIÓN CUÁNTICA
136
Comenzaremos con un solo átomo < un
núcleo también valdría >
Ambos son sistemas de espín naturales
Tienen atributos físicos medibles a los que
podemos asignar números
Cada número diferente representa un estado
La mecánica cuántica no impone más
restricciones sobre el tamaño que las que
imponen…
La mecánica estadística
La mecánica clásica
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
COMPUTACIÓN CUÁNTICA
137
Sea un sistema cuántico ideal
El sistema puede estar en uno cualquiera de
dos estados
Arriba ( ↑ ) :
Estado excitado
Abajo
(↓) :
Estado no excitado
Espín ( ↑ ) ≡ Bit ( 1 )
Espín ( ↓ ) ≡ Bit ( 0 )
Construimos nuestro dispositivo de
computación a partir de estos átomos,
uniéndolos unos a otros de una forma
concreta
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
COMPUTACIÓN CUÁNTICA
138
Sea una parte < o todo > el sistema…
Un conjunto de átomos cada uno de los cuales está
en uno cualquiera de los dos estados posibles
Esto representa un número : La Entrada
Dejamos que el sistema evolucione durante un
tiempo : t
La evolución se efectúa de acuerdo con las leyes
de la mecánica cuántica…
El sistema interacciona consigo mismo
Los átomos cambian de estado
Los < 1 >REVERSIBLE
y los < 0Y TERMODINÁMICA
> se cambian
COMPUTACIÓN
DE LA
COMPUTACIÓN
COMPUTACIÓN CUÁNTICA
139
En un momento determinado tenemos un
conjunto de átomos en ciertos estados : La
Salida
La computación cuántica es un paradigma de
computación distinto al de la computación
clásica
Se basa en el uso de qbits en lugar de bits
Da lugar a nuevas puertas lógicas que hacen
posibles nuevos algoritmos
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
COMPUTACIÓN CUÁNTICA
140
Una misma tarea puede tener diferente
complejidad en computación clásica y en
computación cuántica
Algunos problemas intratables pasan a ser
tratables
Un computador clásico equivale a una
máquina de Turing
Un computador cuántico equivale a una
máquina de Turing indeterminista
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
COMPUTACIÓN CUÁNTICA
141
Feynman profetiza que sobre 2050 o antes la
computación cuántica será una realidad
Tendremos computadoras que ni siquiera
podremos ver
En el Max Plank Institute, un grupo de Óptica
Cuántica < dirigido por un joven científico
español > está realizando importantes
esfuerzos, y obteniendo resultados
espectaculares en este campo…
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
COMPUTACIÓN CUÁNTICA
142
…Campo del que fue pionero Richard Phillips
Feynman, nacido el 11 de mayo de 1918 y
fallecido el 15 de febrero de 1988
El día siguiente a su muerte, todo el Instituto
Tecnológico de California < CALTECH >
apareció literalmente empapelado con
pancartas en las que se podía leer…
¡¡¡ WE LOVE YOU DICK !!!
COMPUTACIÓN REVERSIBLE Y TERMODINÁMICA DE LA
COMPUTACIÓN
