# 可逆计算 reversible computing
Date: 2021-01-17


> 本周在学习Trie数据结构的时候，看到了他的发明者 Edward Fredkin，他也在研究reversible computing

弗雷德金（Fredkin）对计算，硬件和软件一直很感兴趣。 在1960年代初期，他在BBN编写了第一台PDP-1汇编程序。 他是`trie数据结构`，`Fredkin gate`和`Billiard-Ball`计算机模型的可逆计算的发明者。 他的主要贡献包括他在`可逆计算`和`元胞自动机`方面的工作。 他还研究领域还包括计算机视觉，人工智能研究和计算机象棋。

<!--more-->

#### **研究可逆运算原因：**

可逆计算的研究的动机是能量的消耗, 据不完全统计全世界目前有  
\-30亿台个人电脑  
\-3000万台服务器  
能源消耗大约占到世界总能源消耗的2.5%

#### **关于能量的消耗：**

1960 来自德国就职IBM的物理学家 Rolf Landauer提出, 不可逆计算Irrversibility, 擦除一个bit的信息需要的最小能量，也就是能量消耗最小值。

`Landauer's principle`\-朗道尔原理是一种物理原理，它与计算能耗的理论下限有关。  
"信息的任何逻辑上不可逆的操纵，例如位的擦除或两个计算路径的合并，都必须伴随着信息处理设备或其环境的非信息承载自由度的相应熵增加。"

![](https://garlicspace.com/wp-content/uploads/2021/01/irrversibility-5-300x101.png)

#### 不可逆运算：

Irrversibility 我们目前大多数的运算不可逆的， 如下图

![](https://garlicspace.com/wp-content/uploads/2021/01/irrversibility-300x272.png)

逆向的话会有多种可能, 2+2, 1+3, 5+(-1), 这种设备是不可逆运算的设备， 看下我们现有的GATE

![](https://garlicspace.com/wp-content/uploads/2021/01/gate-300x175.png)

可以看到除了NOT 其他运算都是不可逆的。 

如果是不可逆运算的计算机最终会达到耗能下限， 由于热量增加很难提升通用的运算性能，  而可逆计算能达到单位性能消耗更小， 如下图：

![](https://garlicspace.com/wp-content/uploads/2021/01/irrversibility-3-300x166.png)

#### 为什么要可逆计算:

可逆运算Reversible computation可以打破 最小能量消耗的限制， 从而突破由于发热给给性能带来的瓶颈，也就是到达热力学墙，每单位进行开销能够进行的位运算次数无法再提高了。 

![](https://garlicspace.com/wp-content/uploads/2021/01/door-300x191.png)

from  https://www.researchgate.net/figure/Cost-efficiency-of-reversible-computing-vs-irreversible-computing-over-the-next\_fig4\_267820141

#### 可逆计算实现思路:

![](https://garlicspace.com/wp-content/uploads/2021/01/irrversibility-4-300x202.png)

能够通过输出反推出输入， 比如x = 2, y = 2 <=> x+y = 4, x-y = 2

但是可逆计算需要计算机所有层次都支持，才可以构造一台可逆计算的机器, 从物理硬件实现，到计算机架构， 到机器码， 高级语言，甚至算法。 

关于可逆计算可以参见这个视频：

\[embed\]https://www.youtube.com/watch?v=rVmZTGeIwnc\[/embed\]