硬件算法之细胞自动机

1 细胞自动机简介

        细胞自动机是基于网格状单元和简单规则的离散计算模型，由冯诺依曼等人在20世纪40年代提出。细胞自动机被广泛应用于可计算性理论、属性、物理学、复杂适应性系统、数理生物学、微观结构建模等领域，可以对生命现象、晶体生长、湍流等复杂自然现象进行模拟。

2 细胞自动机举例

        细胞自动机由具有有限个状态的细胞构成，经过离散时间后每个细胞的状态发生变化。某时刻t上细胞的状态和邻居细胞的内部状态决定着下一时刻t+1上各个细胞的变化。邻居有两种，一种是考虑上下左右细胞状态的冯诺依曼型邻居，另一种是考虑全部八个周边细胞状态的摩尔型邻居。以冯诺依曼型邻居为例，如下图：

        若每个单元可能的状态数为K，全部5个单元总共有K^5种状态。因此，基于冯诺依曼型邻居的细胞自动机存在（K^(K^5)）个规则。一种广为人知的细胞自动机是生命游戏，它采用冯诺依曼型邻居（K=2），并由下述规则定义：

• 诞生：如果死亡细胞的周围有3个生存细胞，则该细胞在下一轮转为生存状态；
• 维持：生存细胞的周围如果有2或3个生存细胞，则该细胞在下一轮维持生存状态；
• 死亡：上述之外的情况下细胞在下一轮死亡。

        生命游戏具有类似生物繁殖的复杂性和多样性。

        细胞自动机的仿真大多基于有限个细胞进行。一般会采用有限的四边形结构来实现，但边界部分会出现问题。可以将边界全部定义为常数，但缺点是需要增加规则。还有一种方法是采用环面结构。用环面法将四边形的上下左右各自相连，相当于一个用四边形填充的无限大的平面，这样就可以模拟无数个四边形。下图是一个在3×3的网格上放置PE并以环面连接的细胞自动机模拟电路。例如仿真生命游戏时，PE保存着各个细胞的状态，每个时钟周期按上述规则执行，在下一时钟周期更新状态。

        这种从输入/输出到运算全部可以并行的细胞自动机模拟电路非常适合在FPGA上实现，其性能可以轻易超过冯诺依曼型架构。特别是细胞规则的运算层数越深，越能体现流水线的高吞吐量处理能力。近些年，除了传统的电路或器件，还有从材料角度实现更加物理化的细胞自动机的尝试。这些实现方法和FPGA相结合，非常有希望代替传统的冯诺依曼型架构。

        告辞。