Pourquoi les portes réversibles ne sont-elles pas utilisées?

25

Je lisais le livre "La singularité est proche" écrit par Kurzweil et il a mentionné les portes réversibles comme par exemple la porte Fredkin . L'avantage d'utiliser de telles portes est que nous pourrions nous débarrasser des déchets thermiques liés au calcul où les bits disparaissent simplement dans la chaleur, et le calcul ne nécessitera aucun apport d'énergie. Ces hypothèses font que ces portes sonnent comme une solution miracle. La question est donc de savoir quels obstacles techniques empêchent encore leur utilisation à grande échelle.

Je pense aussi que c'est dommage que je n'ai jamais entendu parler de ces portes dans mon baccalauréat en génie électrique et mes études de maîtrise dans une université allemande de premier plan ...

Mehdi
la source
5
Notez que le calcul quantique concerne beaucoup les portes réversibles (cela fait partie de ce que signifie "unitaire").
David Richerby
1
@DavidRicherby Tous les calculs quantiques ne sont pas réversibles; finalement la décohérence se produit.
Alice
Notez que tout ordinateur pratique utilisant des portes réversibles va toujours générer de la chaleur, car vous devez effectuer une correction d'erreur pour garder l'ordinateur sur la bonne voie. La correction d'erreurs nécessite par nature des opérations irréversibles (ou une alimentation continue de bits nuls; même différence).
Craig Gidney

Réponses:

18

Je ne suis en aucun cas un expert sur ce sujet, mais juste en lisant négligemment Wikipedia:

il repose sur le mouvement des boules de billard sphériques dans un environnement sans frottement fait de tampons contre lesquels les boules rebondissent parfaitement

... cela semble très réaliste.

Personne n'a encore compris comment fabriquer de telles portes, elles n'ont qu'un intérêt théorique. Cela pourrait expliquer pourquoi vous n'en avez jamais entendu parler, car l'ingénierie traite généralement de la pratique.

Le principe du calcul réversible est que lorsqu'un peu disparaît, une certaine quantité de chaleur est générée. En utilisant des portes réversibles, aucun bit n'apparaît ou ne disparaît jamais, donc le calcul pourrait être beaucoup plus efficace avec des portes réversibles.

La limite théorique que l'informatique réversible prétend contourner est que l'effacement d'un bit d'information génère au moins énergie en chaleur. Pour un ordinateur fonctionnant à un 60 grillékTln2 avec 10 9 transistors faisant chacun disparaître les bits au rythme de 560C109 , ce qui correspond à 165GHz de génération de chaleur. Cela ne représente qu'une infime proportion ( 1 / 10 000 ) de la consommation d'énergie d'un ordinateur.16mW1/10000

Nos ordinateurs actuels ne sont pas limités par la génération de chaleur associée à la disparition des bits. Ils sont limités par l'inefficacité inhérente au déplacement des électrons sur de minuscules traces de cuivre.

Tom van der Zanden
la source
5
-1. Certaines personnes ont fabriqué des portes réversibles et en ont construit un processeur entier. Il y a une photo de ce CPU à logique réversible sur cise.ufl.edu/research/revcomp .
David Cary
2
@DavidCary, mais ils ne sont pas (ou négligeables) plus efficaces que les ordinateurs fabriqués à partir de portes non réversibles.
user253751
3
@immibis Manifestement faux; ils ne sont pas soumis aux mêmes lois que les ordinateurs fabriqués à partir de portes non réversibles, et donc considérablement plus efficaces.
Alice
3
@DavidCary S'il vous plaît, montrez-moi quelques données sur l'efficacité du processeur auquel vous vous êtes connecté. Tout ce que je vois, c'est une image d'un processeur avec le mot "adiabatique" dessus, mais aucune information sur combien il est plus efficace que les ordinateurs traditionnels.
Tom van der Zanden
1
@TomvanderZanden Mesurer l'efficacité est un peu inutile si vous ne spécifiez pas quel type d'efficacité. Les puces RISC sont plus efficaces que les puces CISC, en termes de taille de puce, mais pas en termes de nombre d'instructions nécessaires pour spécifier un algorithme donné. Tout circuit réversible est immédiatement plus efficace qu'un circuit traditionnel car il n'est pas soumis au principe de Landauer ; c'est déjà une énorme victoire.
Alice
15

Le problème avec des portes réversibles pratiques (portes qui peuvent (et ont été) fabriqué en silicium) est que les économies d'énergie réelles sont linéairement proportionnel à la façon dont lentement vous les exécutez.

Je sais que le groupe de recherche de Tom Knight au MIT a fabriqué un petit processeur adiabatique à la fin des années 1990. La famille logique pratique qu'ils ont développée est appelée logique de récupération de charge à deux niveaux et peut être implémentée à l'aide de techniques de fabrication standard (CMOS). Je crois que le travail a été poursuivi par Michael P Frank à la Florida State University. Un exemple du travail dans le groupe de Tom Knight est la thèse de maîtrise suivante (qui a une section assez décente sur les travaux connexes jusqu'au début des années 1990.) Vieri, CJ: Pendulum: A Reversible Computer Architecture , Master Thesis, MIT EECS dept, 1995.

Les circuits réversibles doivent être adiabatiques (il ne peut y avoir d'échanges de chaleur entre le circuit et son environnement), ce qui signifie qu'ils doivent être en équilibre à tout moment. Pour tout processus qui doit changer quelque chose, vous ne pouvez qu'approcher l'équilibre en faisant en sorte que le changement se produise aussi lentement que possible.

Si je me souviens bien de ma thermodynamique, vous pouvez rendre l' énergie d'un calcul réversible arbitrairement petite, mais l' action minimale (énergie fois le temps) doit être une petite constante.

Logique errante
la source
2
Vous ne vous souvenez pas correctement de la thermodynamique; Le principe de Landauer n'a pas besoin d'être soutenu par un circuit réversible (car il n'efface pas les bits), et donc l'énergie nécessaire peut théoriquement être nulle (et aucune chaleur ne serait libérée). Les circuits réversibles n'ont pas non plus besoin d'être adiabatiques; des portes réversibles pratiques ont été réalisées qui ne sont pas plus lentes que les puces non réversibles (en tenant compte du fait que les puces réversibles sont généralement plus grandes, et ont donc une vitesse d'augmentation de la latence lumineuse).
Alice
"une vitesse d'augmentation de la latence lumineuse": parlez-vous de puces optiques réversibles ? La plupart des puces sont électroniques.
zylstra
6

Le plus grand obstacle empêchant leur utilisation à grande échelle est le même que pour les circuits asynchrones et à peu près tout autre circuit non standard: la loi de Moore.

La loi de Moore est devenue quelque chose d'une prophétie auto-réalisatrice; comme le montre le calendrier de sortie de Tick Tock , les fabricants de puces considèrent la mise en œuvre de la loi de Moore comme un défi. En raison de la nécessité de respecter la loi de Moore, nous sommes devenus de plus en plus aptes à réduire la taille des puces en faisant avancer la lithographie (et souvent en utilisant des tricheurs, comme le multi-modèle).

Qu'est-ce que tout cela a à voir avec les portes réversibles? Alors que les fonderies se précipitent pour libérer des transistors plus récents et plus petits, les entreprises qui souhaitent imprimer de nouvelles puces voient un moyen facile d'augmenter la vitesse en ajoutant simplement plus de cache et en retravaillant leurs conceptions conventionnelles pour mieux utiliser ce cache.

Le tueur de mieux n'est pas un problème technologique; c'est le succès de bien assez .

Alice
la source
1
Si tout va bien un jour assez bon ne sera plus assez bon.
Mehdi
@Mehdi Ne souhaitons-nous pas tous. Mais je n'en serais pas si sûr; l'énergie est actuellement bon marché et il existe des voies pour continuer le cycle actuel pendant au moins 5 ans (peut-être 10, si nous trouvons un moyen de faire fonctionner certaines technologies . Après cela, une nouvelle technologie devra remplacer la lithographie, mais cela ne signifie pas qu'elle doit être non conventionnelle. La lithographie 3D pourrait fournir des puces beaucoup plus denses en construisant au même pas, mais dans des directions différentes. Cela pourrait nous faire gagner jusqu'en 2050.
Alice
3

Les dispositifs informatiques utiles nécessitent une rétroaction, ce qui permet à un élément de circuit d'effectuer un nombre essentiellement illimité de calculs séquentiels. Les circuits de rétroaction utilisables doivent contenir des sections dont le nombre total d'entrées (en comptant à la fois celles qui sont renvoyées par les sorties et celles qui ne le sont pas) dépasse le nombre de sorties qui sont renvoyées à l'entrée (la seule façon dont le nombre d'entrées ne t dépasser le nombre de sorties de rétroaction serait si les circuits ne répondaient en aucune façon à des stimuli extérieurs). Étant donné que les fonctions logiques parfaitement réversibles ne peuvent pas avoir plus d'entrées que de sorties, il n'est pas possible de construire à partir d'elles les structures de rétroaction requises pour effectuer à plusieurs reprises des tâches informatiques non triviales.. Notez qu'avec la technologie CMOS utilisée dans les ordinateurs d'aujourd'hui, une rétroaction est nécessaire pour garantir que les résultats rapportés par les calculs dans différentes parties d'un circuit sont mis à la disposition simultanément d'autres parties, car s'ils n'étaient pas le timing relatif avec lequel les signaux arrivent, constituent des "informations" qui ne peuvent être parfaitement transmises en aval; d'autres technologies pourraient permettre à de nombreuses portes de propager des signaux exactement au même rythme tout en conservant la réversibilité, mais je ne connais aucune technologie pratique pour cela.

Notez que d'un point de vue CS, il est trivial de rendre un processus informatique réversible si l'on a un support de stockage initialement vide dont la taille est essentiellement proportionnelle au nombre d'étapes multiplié par la quantité d'état qui pourrait changer à chaque étape. Cette affirmation ne contredit pas l'affirmation du paragraphe précédent, car un stockage proportionnel au nombre d'étapes nécessitera des circuits proportionnels au nombre d'étapes, ce qui impliquera des circuits proportionnels à la quantité qui serait nécessaire si tous les retours étaient éliminés.

Si l'on est autorisé à avoir des sorties qui sont ignorées si, dans des conditions d'entrée appropriées, elles n'atteindront jamais le niveau haut, il pourrait être possible de concevoir un système qui, en théorie, bénéficierait d'une logique réversible. Par exemple, si l'on avait un algorithme qui fonctionnait sur un bloc de 256 mots de RAM et que l'on voulait utiliser un "processeur logique réversible" qui effectuait 1 000 000 d'opérations par seconde et chaque opération mettait à jour un registre, le compteur de programme ou un mot de RAM, on pourrait utiliser un "CPU réversible" qui:

  • a exécuté un tas d'instructions et, sur chacune, envoyer tout ce qui a été écrasé dans un tampon LIFO
  • après l'exécution d'un tas d'instructions, copiez la mémoire RAM dans un tampon de "transfert" initialement vierge
  • en utilisant les valeurs du LIFO, exécutez tous les calculs en sens inverse
  • écraser le contenu de la RAM principale avec le tampon de transfert, qui serait effacé au cours du processus.

La recette ci-dessus peut être répétée un certain nombre de fois pour exécuter l'algorithme pour un nombre arbitraire d'étapes; seule la dernière étape de la recette ne serait pas réversible. La quantité d'énergie dépensée par étape algorithmique dans des opérations non réversibles serait inversement proportionnelle à la taille du LIFO, et pourrait donc être rendue arbitrairement petite si l'on construisait pour construire un LIFO suffisamment grand.

Cependant, pour que cette capacité se traduise par toutes sortes d'économies d'énergie, il serait nécessaire d'avoir un LIFO qui stockerait l'énergie lorsque les informations seraient entrées et rendrait utilement cette énergie lors de la lecture. En outre, le LIFO devrait être suffisamment grand pour contenir les données d'état pour suffisamment d'étapes pour que le coût énergétique de son utilisation soit inférieur à la quantité d'énergie qu'il a utilement économisée. Étant donné que la quantité d'énergie perdue dans le stockage et la récupération de N octets à partir de n'importe quel FIFO pratique est peu susceptible d'être O (1), il n'est pas clair que l'augmentation de N réduira significativement la consommation d'énergie.

supercat
la source
1
@LoganMayfield: Je pense que vous ignorez l'exigence selon laquelle la longueur de bande requise est proportionnelle au nombre d'étapes à effectuer de manière réversible. Si je jette une cartouche dans mon Atari 2600 et que je l'allume pendant un certain temps, elle exécutera environ 100 milliards de cycles par jour. Étant donné que le système (y compris toutes les cartouches sauf les plus grandes) aurait moins de 100 000 transistors, cela représente plus d'un million de cycles par jour et par transistor. Si l'on voulait concevoir une machine équivalente qui pourrait fonctionner pendant une journée de manière entièrement réversible, même avec la possibilité de fabriquer un LIFO réversible avec un transistor par bit ...
supercat
1
... il faudrait multiplier par plus d'un million le nombre de transistors. Si l'on n'avait besoin d'exécuter que quelques milliers de cycles à la fois de manière réversible, de capturer les résultats, de rembobiner les cycles, puis de remplacer l'état initial précédent par les résultats capturés, cela pourrait presque être réalisable, mais serait monstrueusement complexe. Avec tout ce qui ressemble à la technologie d'aujourd'hui, toute réduction des pertes "théoriquement inévitables" que l'on obtiendrait en utilisant l'informatique réversible serait submergée par une augmentation de la puissance perdue pour des causes qui n'étaient évitables qu'en théorie.
supercat
1
Je ne m'inquiétais que de la déclaration que vous avez faite dans votre réponse initiale, qui disait: "la technologie réversible ne peut pas calculer les mêmes choses que la technologie irréversible". Je ne voulais pas laisser entendre que c'est pratique.
Logan Mayfield du
1
@LoganMayfield: La question initiale était "pourquoi ces choses ne sont-elles pas utilisées". Je dirais que presque tous les appareils informatiques pratiques utilisent la rétroaction de manière à ce qu'une quantité fixe de matériel puisse effectuer un nombre illimité de calculs si on leur donne un temps illimité. C'est quelque chose qu'une logique réversible ne peut tout simplement pas faire . C'est une différence qualitative majeure entre l'informatique réversible et non réversible. Il se peut que même un ordinateur qui ne peut exécuter qu'un nombre limité d'opérations avant le "rembobinage" puisse encore être utile, alors ...
supercat
1
... J'ai édité le post pour dire ce qui serait nécessaire pour utiliser une telle chose pour faire un travail significatif. Je pense que le problème pratique fondamental découle cependant de ce que j'ai dit à l'origine: les ordinateurs tirent le meilleur parti de leur capacité à réutiliser des éléments de circuit un nombre arbitraire de fois pour effectuer différents calculs, et l'incapacité de une logique réversible à gérer qui le mettra dans une position désavantageuse dès le départ.
supercat
2

L'informatique réversible appliquée pratique est un domaine de recherche actif et devrait devenir plus important à l'avenir. La plupart de l'informatique quantique peut être considérée comme tentant de créer des portes de qubit réversibles et il est très difficile expérimentalement de faire correspondre les propriétés théoriques du formalisme QM, mais des progrès constants sont en cours.

Un autre point fondamental est que chaque fois que la dissipation d'énergie est diminuée sur une puce, cela déplace essentiellement le système de porte vers "plus réversible", et la dissipation de puce à faible énergie est depuis longtemps une priorité élevée dans l'informatique mobile (représentant une sorte de changement de paradigme à l'échelle de l'industrie). Pendant des décennies, les gains de performances des puces (similaires à la loi de Moore) ont été obtenus en étant quelque peu "détendus" ou même "bâclés" avec la dissipation d'énergie, mais qui ont atteint un point de rendement décroissant il y a quelques années. Le premier fabricant mondial de puces Intel tente de se tourner vers des puces de faible puissance pour rivaliser avec Arm qui a un avantage après avoir jamais rien construit d'autre.

Il y a peut-être des recherches récentes potentiellement révolutionnaires utilisant la technologie supraconductrice (juin 2014), et il existe d'autres projets de recherche actifs dans ce domaine.

Voir par exemple la porte logique réversible utilisant des dispositifs supraconducteurs adiabatiques / Takeuchi, Yamanashi, Yoshikawa, Nature:

L'informatique réversible a été étudiée depuis que Rolf Landauer a avancé l'argument qui est devenu le principe de Landauer. Ce principe stipule qu'il n'y a pas de dissipation d'énergie minimale pour les opérations logiques en informatique réversible, car elle ne s'accompagne pas de réductions d'entropie d'information. Cependant, jusqu'à présent, aucune porte logique réversible pratique n'a été démontrée. L'un des problèmes est que les portes logiques réversibles doivent être construites en utilisant des dispositifs logiques extrêmement économes en énergie. Une autre difficulté est que les portes logiques réversibles doivent être à la fois logiquement et physiquement réversibles. Nous proposons ici la première porte logique réversible pratique utilisant des dispositifs supraconducteurs adiabatiques et démontrons expérimentalement la réversibilité logique et physique de la porte. De plus, nous estimons la dissipation d'énergie de la porte, et discuter de la dissipation d'énergie minimale requise pour les opérations logiques réversibles. Les résultats de cette étude devraient permettre à l'informatique réversible de passer du stade théorique à l'utilisation pratique.

vzn
la source
1

Les portes Fredkin sont réalistes et beaucoup ont été mises en œuvre. Il existe des cartes FPGA entières utilisant strictement des portes logiques réversibles qui sont implémentées en utilisant la porte Fredkin et Toffoli comme LU.

Il existe plusieurs problèmes affectant leur utilisation répandue dans l'architecture informatique. Il existe plusieurs avantages "annoncés" aux portes en fredkin qui ne fonctionnent pas nécessairement comme prévu dans les circuits réels. Les économies d'énergie des portes logiques réversibles sont principalement dues au fait qu'elles ne nécessitent pas de création d'entropie lorsqu'une opération est effectuée. Comme l'a déclaré Tom van der Zanden, c'est la principale raison pour laquelle la logique réversible peut être beaucoup plus efficace. Pourquoi ce n'est pas le cas dans les circuits réels:

  1. Actuellement, la technologie des transistors limite davantage la vitesse et la consommation d'énergie des ordinateurs, et malheureusement, davantage de transistors sont nécessaires pour fabriquer une porte en fredkin, contrairement aux grilles nand ou nor traditionnelles. Cela signifie que les portes fredkin gaspillent plus d'énergie par les fuites de transistor et nécessitent plus d'espace sur le silicium (ce qui signifie plus cher). Cela suffit à lui seul pour justifier l'utilisation de portes nand / nor over fredkin
  2. Étant donné que la principale forme de perte de puissance provient des transistors et non de la création d'entropie en raison du calcul réel, vous devez toujours exécuter des lignes d'alimentation et de masse aux portes fredkin pour compenser cette perte de puissance. Ces gros bus sont des bus en éventail, qui occupent également beaucoup d'espace sur le silicium. Puisqu'il y a plus de transistors dans une porte en fredkin, cela conduit à plus de fan-in, et donc plus d'espace gaspillé sur le silicium.
  3. Bien que nous ayons des portes réversibles en fredkin, celles-ci sont construites à partir de dispositifs non réversibles (transistors). Cela signifie que certains des gains d'énergie ne sont pas réalisés avec la technologie de porte actuelle (en dehors des circuits quantiques).
  4. La taille et la vitesse sont liées au silicium, plus les choses sont rapprochées, généralement plus vous pouvez les fabriquer rapidement. Étant donné que les portes fredkin utilisent plus de transistors et ont plus de connexions pour l'alimentation, etc., elles ont tendance à être beaucoup plus lentes.
  5. Les avantages de consommation d'énergie et de vitesse ne sont réalisés que lorsque les bits sont réutilisés avec succès. La plupart des algorithmes que nous avons sont horriblement non conservateurs. Vous pouvez le voir en recherchant une implémentation d'un additionneur complet ou d'un registre à décalage à l'aide de portes fredkin. Étant donné que la logique réversible ne permet pas les entrées et sorties logiques, cela conduit à beaucoup de calculs de bits qui ne finissent pas par être utilisés pour réaliser une opération utile. Quelque chose comme l'ajout de deux nombres de 8 bits produira 9 bits ou des informations utiles (résultat 8 bits, 1 bit de retenue), mais nécessitera un bus d'entrée de nombreuses constantes 1 et 0 et produira de nombreux bits de sortie de données indésirables. Puisque vous avez un bus plus large, cela conduit à un circuit encore plus étendu sur le silicium.
  6. De plus, les bits indésirables doivent être vidés par le processeur et entraîneraient de toute façon une perte d'énergie car ils ne sont jamais utilisés

Résumé: Les portes Fredkin produisent beaucoup de calculs de déchets lors de l'implémentation d'algorithmes réels. calcul des déchets = énergie gaspillée. Pour cette raison, la taille des bus augmente, ce qui répartit et ralentit les choses. En outre, la mise en œuvre physique des portes en fredkin est la plus grande préoccupation pour la technologie actuelle. La mise en œuvre actuelle répartit davantage les choses en exigeant plus de lignes électriques et de mise à la terre pour compenser les pertes dans le circuit (ce qui est beaucoup plus préoccupant pour les pertes d'énergie) et utilise beaucoup plus de biens immobiliers sur silicium (ce qui est beaucoup plus préoccupant pour la vitesse )

Je me rends compte que c'est un vieux fil, mais beaucoup de réponses se concentrent sur le fait que les transistors sont inefficaces. Mon objectif est de montrer que nos algorithmes sont également inefficaces et ne gèrent pas bien l'informatique réversible. Je suis un ingénieur en informatique qui aime faire des recherches sur l'informatique réversible et quantique

Ryan
la source