¿Por qué no se utilizan puertas reversibles?

25

Estaba leyendo el libro "La singularidad está cerca", escrito por Kurzweil, y mencionó las puertas reversibles como, por ejemplo, la puerta de Fredkin . La ventaja de usar tales compuertas es que podríamos deshacernos del desperdicio térmico relacionado con la computación donde los bits simplemente desaparecen en calor, y la computación no necesitará ningún aporte de energía. Esos supuestos hacen que estas puertas suenen como una solución milagrosa. Entonces, la pregunta es qué obstáculos técnicos siguen impidiendo su uso a gran escala.

También creo que es una lástima que nunca haya oído hablar de esas puertas en mi licenciatura en ingeniería eléctrica y estudios de maestría en una de las mejores universidades alemanas ...

Mehdi
fuente
55
Tenga en cuenta que el cálculo cuántico tiene mucho que ver con puertas reversibles (eso es parte de lo que significa "unitario").
David Richerby
1
@DavidRicherby No todos los cálculos cuánticos son reversibles; finalmente se produce decoherencia.
Alice
Tenga en cuenta que cualquier computadora práctica que use puertas reversibles seguirá generando calor, ya que debe realizar una corrección de errores para mantener la computadora en el camino correcto. La corrección de errores inherentemente requiere operaciones irreversibles (o un suministro continuo de bits cero; la misma diferencia).
Craig Gidney

Respuestas:

18

De ninguna manera soy un experto en este tema, pero solo de leer casualmente Wikipedia:

se basa en el movimiento de las bolas esféricas de billar en un ambiente libre de fricción hecho de amortiguadores contra los cuales las bolas rebotan perfectamente

... esto suena muy realista.

Nadie ha descubierto realmente cómo hacer tales puertas todavía, son meramente de interés teórico. Eso podría explicar por qué nunca has oído hablar de ellos, ya que la ingeniería generalmente trata con la práctica.

La premisa de la computación reversible es que cuando desaparece un poco, se genera cierta cantidad de calor. Al usar puertas reversibles, nunca aparecen ni desaparecen bits, por lo que supuestamente el cálculo podría ser mucho más eficiente con puertas reversibles.

El límite teórico que afirma Reversible Computing es que borrar 1 bit de información genera al menos energía en calor. Para una computadora que funciona a un tostado con transistores cada uno haciendo que los bits desaparezcan a una velocidad de , que corresponde a de generación de calor. Eso solo representa una pequeña proporción ( ) del uso de energía de una computadora.60kTln260C 5109 165GHz 1 / 10,00016mW1/10000

Nuestras computadoras actuales no están limitadas por la generación de calor asociada con la desaparición de bits. Están limitados por la ineficiencia inherente en el movimiento de electrones en pequeñas trazas de cobre.

Tom van der Zanden
fuente
55
-1. Algunas personas hicieron puertas reversibles y construyeron una CPU completa a partir de ellas. Hay una fotografía de esa CPU de lógica reversible en cise.ufl.edu/research/revcomp .
David Cary
2
@DavidCary pero no son (o despreciablemente) más eficientes que las computadoras hechas de puertas no reversibles.
user253751
3
@immibis Marcado como falso; no están sujetos a las mismas leyes que las computadoras hechas con puertas no reversibles y, por lo tanto, drásticamente más eficientes.
Alice
3
@DavidCary Por favor, muéstrame algunos datos sobre qué tan eficiente es la CPU a la que te vinculaste. Todo lo que veo es una imagen de una CPU con la palabra "adiabático", pero no hay información sobre cuánto más eficiente que las computadoras tradicionales.
Tom van der Zanden
1
@TomvanderZanden Medir la eficiencia es un poco inútil si no especifica qué tipo de eficiencia. Los chips RISC son más eficientes que los CISC, en términos de tamaño de chip, pero no en términos de cuántas instrucciones se necesitan para especificar un algoritmo dado. Cualquier circuito reversible es inmediatamente más eficiente que un circuito tradicional porque no está sujeto al principio de Landauer ; eso ya es una gran victoria.
Alice
15

El problema con las compuertas reversibles prácticas (compuertas que pueden (y han sido) fabricadas en silicio) es que los ahorros de energía reales son linealmente proporcionales a la lentitud con la que se ejecutan.

Sé que el grupo de investigación de Tom Knight en el MIT fabricó un pequeño procesador adiabático a fines de la década de 1990. La familia lógica práctica que desarrollaron se llama lógica de recuperación de carga de nivel dividido y puede implementarse utilizando técnicas de fabricación estándar (CMOS). Creo que el trabajo ha sido continuado por Michael P Frank en la Florida State University. Un ejemplo del trabajo en el grupo de Tom Knight es la siguiente tesis de maestría (que tiene una sección bastante decente sobre trabajos relacionados a principios de la década de 1990). Vieri, CJ: Pendulum: A Reversible Computer Architecture , Master's Thesis, MIT EECS dept, 1995.

Los circuitos reversibles deben ser adiabáticos (no puede haber intercambios de calor entre el circuito y su entorno), lo que significa que deben estar en equilibrio en todo momento. Para cualquier proceso que necesite cambiar algo, solo puede aproximarse al equilibrio haciendo que el cambio suceda lo más lentamente posible.

Si recuerdo correctamente mi termodinámica, puede hacer que la energía de un cálculo reversible sea arbitrariamente pequeña, pero la acción mínima (energía por tiempo) debe ser una constante pequeña.

Lógica Errante
fuente
2
No recuerdas la termodinámica correctamente; El principio de Landauer no necesita ser respaldado por un circuito reversible (ya que no borra bits), y por lo tanto, la energía necesaria puede ser teóricamente cero (y no se liberaría calor). Los circuitos reversibles tampoco necesitan ser adiabáticos; Se han realizado puertas reversibles prácticas que no son más lentas que las virutas no reversibles (teniendo en cuenta que las virutas reversibles son generalmente más grandes y, por lo tanto, tienen una velocidad de aumento de la latencia de la luz).
Alice
"un aumento de la velocidad de latencia de la luz": ¿Se refiere a chips ópticos reversibles ? La mayoría de los chips son electrónicos.
zylstra
6

El obstáculo más grande que impide su uso a gran escala es el mismo que para los circuitos asíncronos y prácticamente cualquier otro diseño de circuito no estándar: la ley de Moore.

La ley de Moore se ha convertido en una especie de profecía autocumplida; Como se ve en el Programa de lanzamiento de Tick Tock , los fabricantes de chips ven el cumplimiento de la ley de Moore como un desafío. Debido a la necesidad de cumplir con la ley de Moore, nos hemos vuelto más y más hábiles para disminuir el tamaño de los chips al avanzar la litografía (y a menudo usando trampas, como el multipatterning).

¿Qué tiene que ver todo esto con las puertas reversibles? A medida que las fundiciones compiten por lanzar transistores de tamaños más nuevos y más pequeños, las compañías que desean imprimir nuevos chips ven un camino fácil hacia el aumento de la velocidad simplemente agregando más caché y reelaborando sus diseños convencionales para usar mejor ese caché.

El asesino de lo mejor no son los problemas tecnológicos; Es el éxito de lo suficientemente bueno .

Alicia
fuente
1
Esperemos que algún día lo suficientemente bueno ya no sea lo suficientemente bueno.
Mehdi
@Mehdi No todos deseamos. Pero no estaría tan seguro; La energía es actualmente barata y hay caminos para continuar el ciclo actual durante al menos otros 5 años (posiblemente 10, si encontramos una manera de hacer que ciertas tecnologías funcionen . Después de eso, alguna nueva tecnología tendrá que reemplazar la litografía, pero Esto no significa que tenga que ser poco convencional. La litografía 3D podría proporcionar chips mucho más densos al construir en el mismo campo, pero en diferentes direcciones. Eso podría obtener ganancias hasta 2050.
Alice
3

Los dispositivos informáticos útiles requieren retroalimentación, lo que hace posible que un elemento del circuito realice un número esencialmente ilimitado de cálculos secuenciales. Los circuitos de retroalimentación utilizables deben contener secciones cuya cantidad total de entradas (contando tanto las que se retroalimentan de las salidas como las que no) excede la cantidad de salidas que se retroalimentan a la entrada (la única forma en que la cantidad de entradas no t excedería el número de salidas realimentadas si los circuitos no respondieran de ninguna manera a los estímulos externos). Dado que las funciones lógicas perfectamente reversibles no pueden tener más entradas que salidas, no es posible construir a partir de ellas ninguna de las estructuras de retroalimentación necesarias para realizar tareas informáticas no triviales repetidamente. Tenga en cuenta que con la tecnología CMOS utilizada en las computadoras actuales, se requiere retroalimentación para garantizar que los resultados informados por los cálculos en diferentes partes de un circuito estén disponibles simultáneamente para otras partes, ya que si no fueran el tiempo relativo con el que llegarían las señales constituir "información" que no podría transmitirse perfectamente aguas abajo; otras tecnologías podrían permitir que muchas puertas propaguen señales exactamente a la misma velocidad mientras retienen la reversibilidad, pero no conozco ninguna tecnología práctica para eso.

Tenga en cuenta que desde una perspectiva CS, es trivial hacer que un proceso informático sea reversible si uno tiene un medio de almacenamiento inicialmente vacío cuyo tamaño es esencialmente proporcional al número de pasos multiplicado por la cantidad de estado que podría cambiar en cada paso. Este reclamo no contradice el reclamo del párrafo anterior, ya que el almacenamiento proporcional al número de pasos requerirá circuitería proporcional al número de pasos, lo que implicará circuitería proporcional a la cantidad que se requeriría si se eliminaran todos los comentarios.

Si a uno se le permite tener salidas que se ignoran si, dadas las condiciones de entrada adecuadas, nunca subirán, entonces podría ser posible diseñar un sistema que, en teoría, se beneficiaría de la lógica reversible. Por ejemplo, si uno tuviera un algoritmo que funcionara en un fragmento de RAM de 256 palabras y quisiera usar una "CPU de lógica reversible" que realizara 1,000,000 de operaciones por segundo y cada operación actualizara un registro, el contador del programa o uno palabra de RAM, uno podría usar una "CPU reversible" que:

  • ejecutó un montón de instrucciones y, en cada una, envió lo que se sobrescribió a un búfer LIFO
  • después de ejecutar un montón de instrucciones, copie la RAM en un búfer de "reenvío" inicialmente en blanco
  • usando los valores en el LIFO, ejecute todos los cálculos en reversa
  • sobrescribe el contenido de la RAM principal con el búfer de reenvío, que se borraría en el proceso.

La receta anterior podría repetirse cualquier número de veces para ejecutar el algoritmo durante un número arbitrario de pasos; solo el último paso de la receta no sería reversible. La cantidad de energía gastada por paso algorítmico en operaciones no reversibles sería inversamente proporcional al tamaño del LIFO y, por lo tanto, podría reducirse arbitrariamente si se construyera para construir un LIFO lo suficientemente grande.

Sin embargo, para que esa capacidad se traduzca en cualquier tipo de ahorro de energía, sería necesario contar con un LIFO que almacenara la energía cuando se ingresara la información y la devolvería útilmente cuando se leyera. Además, el LIFO tendría que ser lo suficientemente grande como para contener los datos del estado durante pasos suficientes para que el costo de energía de usarlo fuera menor que la cantidad de energía que ahorró útilmente. Dado que la cantidad de energía perdida en el almacenamiento y la recuperación de N bytes de cualquier FIFO práctico es poco probable que sea O (1), no está claro que el aumento de N reduzca significativamente el consumo de energía.

Super gato
fuente
1
@LoganMayfield: Creo que ignora el requisito de que la longitud de la cinta requerida sea proporcional al número de pasos que se deben realizar de forma reversible. Si arrojo un cartucho a mi Atari 2600 y lo enciendo por un tiempo, funcionará aproximadamente 100 mil millones de ciclos por día. Dado que el sistema (incluidos todos los cartuchos excepto los más grandes) tendría menos de 100,000 transistores, eso es más de un millón de ciclos por día por transistor. Si uno quisiera diseñar una máquina equivalente que pudiera funcionar durante un día de forma totalmente reversible, incluso con la capacidad de hacer un LIFO reversible con un transistor por bit ...
supercat
1
... sería necesario aumentar el número de transistores más de un millón de veces. Si uno solo necesitara ejecutar algunos miles de ciclos a la vez de manera reversible, capture los resultados, rebobine los ciclos y luego reemplace el estado inicial anterior con los resultados capturados, eso podría ser casi viable, pero sería monstruosamente complejo. Con cualquier cosa que se parezca a la tecnología actual, cualquier reducción en las pérdidas "teóricamente inevitables" que se obtendría mediante el uso de la informática reversible se vería afectada por un aumento en la pérdida de potencia por causas que eran evitables solo en teoría.
supercat
1
Solo me preocupaba la afirmación de su respuesta original que decía "la tecnología reversible no puede calcular las mismas cosas que la tecnología irreversible". No quise decir que sea práctico.
Logan Mayfield
1
@LoganMayfield: La pregunta inicial era "¿por qué no se usan estas cosas?". Sugeriría que casi todos los dispositivos informáticos prácticos utilizan la retroalimentación de tal manera que una cantidad fija de hardware podrá realizar un número ilimitado de cálculos si se le da un tiempo ilimitado. Eso es algo que la lógica reversible simplemente no puede hacer . Esa es una diferencia cualitativa importante entre la computación reversible y no reversible. Puede ser que incluso un ordenador que sólo puede ejecutar un número limitado de operaciones antes de "rebobinado" aún podría ser útil, así que ...
supercat
1
... He editado la publicación para decir qué se requeriría para usar tal cosa para hacer un trabajo significativo. Sin embargo, creo que el problema práctico fundamental se deriva de lo que dije originalmente: las computadoras obtienen la mayor parte de su inversión de su capacidad de reutilizar elementos de circuito un número arbitrario de veces para realizar diferentes cálculos, y la incapacidad de lógica reversible para manejar que lo pondrá en grave desventaja desde el principio.
supercat
2

La informática reversible aplicada práctica es un área activa de investigación y es probable que se vuelva más prominente en el futuro. Se puede ver que la mayor parte de la computación cuántica intenta crear compuertas qubit reversibles y es muy difícil experimentalmente hacer coincidir las propiedades teóricas del formalismo QM, pero se está logrando un progreso constante.

Otro punto básico es que cada vez que se reduce la disipación de energía en un chip, esencialmente se está moviendo el sistema de compuerta a "más reversible", y la disipación de chip de baja energía ha sido una alta prioridad durante mucho tiempo en la informática móvil (que representa una especie de cambio de paradigma en toda la industria). Durante décadas, el rendimiento del chip (similar a la ley de Moore) se produjo estando algo "relajado" o incluso "descuidado" con la disipación de energía, pero eso alcanzó un punto de rendimientos decrecientes hace unos años. Intel, el principal fabricante mundial de chips, está tratando de convertirse en chips de menor potencia para competir con Arm, que tiene una ventaja después de nunca construir nada más.

Hay algunas investigaciones recientes posiblemente innovadoras que utilizan tecnología superconductora (junio de 2014), y hay otros proyectos de investigación activos en esta área.

Ver, por ejemplo , Puerta lógica reversible utilizando dispositivos superconductores adiabáticos / Takeuchi, Yamanashi, Yoshikawa, Nature:

La computación reversible se ha estudiado desde que Rolf Landauer presentó el argumento que se conoce como el principio de Landauer. Este principio establece que no existe una mínima disipación de energía para las operaciones lógicas en la computación reversible, porque no se acompaña de reducciones en la entropía de la información. Sin embargo, hasta ahora, no se han demostrado puertas lógicas reversibles prácticas. Uno de los problemas es que las puertas lógicas reversibles deben construirse mediante el uso de dispositivos lógicos extremadamente eficientes energéticamente. Otra dificultad es que las puertas lógicas reversibles deben ser tanto lógicamente como físicamente reversibles. Aquí proponemos la primera puerta lógica reversible práctica que utiliza dispositivos superconductores adiabáticos y demostramos experimentalmente la reversibilidad lógica y física de la puerta. Además, estimamos la disipación de energía de la puerta, y discuta la disipación de energía mínima requerida para las operaciones lógicas reversibles. Se espera que los resultados de este estudio permitan que la computación reversible pase de la etapa teórica al uso práctico.

vzn
fuente
1

Las puertas de Fredkin son realistas y muchas han sido implementadas. Hay placas FPGA completas que usan estrictamente puertas lógicas reversibles que se implementan usando las puertas Fredkin y Toffoli como LU.

Existen varios problemas que afectan su uso generalizado en la arquitectura de computadoras. Hay varias ventajas "anunciadas" para las puertas fredkin que no necesariamente funcionan como se espera en los circuitos reales. El ahorro de energía de las puertas lógicas reversibles se debe principalmente al hecho de que no requieren que se cree entropía cuando se realiza una operación. Como dijo Tom van der Zanden, esta es la razón principal por la que la lógica reversible puede ser mucho más eficiente. Por qué este no es el caso en circuitos reales:

  1. Actualmente, la tecnología de transistores es más lo que limita la velocidad de la computadora y el consumo de energía, y desafortunadamente, se requieren más transistores para hacer una compuerta fredkin en lugar de las compuertas nand o nor tradicionales. Esto significa que las puertas fredkin desperdician más energía a través de la fuga del transistor y requieren más espacio en el silicio (lo que significa más costoso). Esto solo es suficiente para justificar el uso de nand / ni sobre puertas fredkin
  2. Dado que la forma principal de pérdida de potencia proviene de los transistores y no de la creación de entropía debido al cálculo real, aún debe ejecutar la energía y las líneas de tierra a las puertas de fredkin para compensar esta pérdida de potencia. Estos buses grandes son buses de abanico, que también ocupan mucho espacio en el silicio. Dado que hay más transistores en una puerta fredkin, esto conduce a más fan-in y, por lo tanto, más espacio desperdiciado en silicio.
  3. Aunque tenemos puertas reversibles de Fredkin, estas están construidas a partir de dispositivos no reversibles (transistores). Esto significa que algunas de las ganancias de energía no se realizan con la tecnología de compuerta actual (fuera de los circuitos cuánticos).
  4. El tamaño y la velocidad están relacionados con el silicio, cuanto más cerca están las cosas, generalmente más rápido puedes hacerlas. Dado que las puertas fredkin usan más transistores y tienen más conexiones para la alimentación, etc., tienden a ser significativamente más lentas.
  5. Las ventajas de consumo de energía y de velocidad solo se obtienen cuando los bits se reutilizan con éxito. La mayoría de los algoritmos que tenemos son terriblemente no conservadores. Puede ver esto investigando la implementación de un sumador completo o un registro de desplazamiento utilizando puertas fredkin. Dado que la lógica reversible no permite la entrada y salida del ventilador lógico, esto lleva a muchos cálculos de bits que no terminan siendo utilizados para lograr una operación útil. Algo como agregar dos números de 8 bits producirá 9 bits o información útil (resultado de 8 bits, 1 bit de acarreo), pero requerirá un bus de entrada de muchas constantes 1 y 0 y producirá muchos bits de salida de datos basura. Como tiene un bus más ancho, esto conduce a un circuito aún más extendido en silicio.
  6. Además, los bits de basura deben ser arrojados por el procesador y, por lo tanto, conducirían a una pérdida de energía de todos modos porque nunca se usan

Resumen: las puertas de Fredkin producen muchos cálculos de desperdicio al implementar algoritmos reales. cálculo de residuos = energía desperdiciada. Debido a esto, el tamaño del bus aumenta, lo que extiende las cosas y las ralentiza. Además, la implementación física de las puertas fredkin es la mayor preocupación para la tecnología actual. La implementación actual extiende más las cosas al requerir más potencia y líneas de tierra para compensar las pérdidas en el circuito (que es una preocupación mucho mayor por la pérdida de energía) y utiliza mucho más espacio en el silicio (que es una preocupación mucho mayor por la velocidad )

Me doy cuenta de que este es un hilo viejo, pero muchas de las respuestas se centran en el hecho de que los transistores son ineficientes. Mi objetivo es mostrar que nuestros algoritmos también son ineficientes y no manejan bien la informática reversible. Soy un ingeniero informático que disfruta investigando computación cuántica y reversible

Ryan
fuente