基于三值光計算機的細胞自動機計算系統

李 梅

(西安工業大學 計算機科學與工程學院，陜西 西安 710021)

0 引 言

三值光計算機[1-3]，經過幾次大的理論突破，現已發展成為能夠并行處理百位量級三值邏輯運算的實驗系統[4-8]。文中在此實驗系統上實現大規模二維三值細胞自動機的演化計算，把細胞自動機的天然并行性和三值光計算機的數據位巨并行性結合起來，極大地簡化了運算過程的時間復雜性；同時，發揮三值光計算機的運算器可重構性[9]，極大地擴充了細胞自動機演化規律的靈活性和多樣性，為細胞自動機的應用創造了更好的條件。

1 三值光計算機的相關特點

三值光計算機是一種光電混合并行數字計算機，通過控制液晶改變光的偏振性完成運算，一次運算可以處理整屏數據，因此三值光計算機擁有巨大的數據位數。同時，依據降值設計理論和方法[9]設計的三值光學邏輯處理器可以規范地為各種二元三值邏輯運算構建專門的運算器單元，具有邏輯運算器的重構性。

2 細胞自動機

細胞自動機是一種具有時間、空間和狀態離散性的動力學系統[10-11]，可表示為CA=(Ld,S,N,f)。其中，L為細胞空間，d為細胞空間維數；S為細胞的有限狀態集；N表示鄰域細胞的組合，可以采用(S1,S2,…,S|N|)表示，|N|是此組合鄰域細胞的個數；f表示將(S1,S2,…,S|N|)映射到S的一個狀態轉換函數。

目前實現細胞自動機有兩種方法，用VLSI實現[12]和軟件模擬[13]。用VLSI實現，雖然運算速度快、結構簡單，但細胞單元之間的局部狀態轉換規則一旦確定就很難改變。用軟件模擬需要逐個計算每個細胞的演化函數，屬于串行過程，當規模巨大時效率急劇降低。……