Verdvana

空持千百偈 不如吃茶去

硬件算法之细胞自动机

31 Jul 2019 » Verilog HDL, FPGA, Hardware Algorithm

1 细胞自动机简介

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


2 细胞自动机举例

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

1

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

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

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

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

2

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


        告辞。