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