The Global Cellular Automata (GCA) Model is a generalization of the Cellular Automata (CA) Model. The GCA model consists of a collection of cells which change their states depending on the states of their neighbors, like in the classical CA model. In generalization of the CA model, the neighbors are no longer fixed and local, they are variable and global. In the basic GCA model, a cell is structured into a data part and a pointer part. The pointer part consists of several pointers that hold addresses to global neighbors. The data rule defines the new data state, and the pointer rule define the new pointer states. The cell's state is synchronously or asynchronously updated using the new data and new pointer states. Thereby the global neighbors can be changed from generation to generation. Similar to the CA model, only the own cell's state is modified. Thereby write conflicts cannot occur, all cells can work in parallel which makes it a massively parallel model. The GCA model is related to the CROW (concurrent read owners write) model, a specific PRAM (parallel random access machine) model. Therefore many of the well-studied PRAM algorithms can be transformed into GCA algorithms. Moreover, the GCA model allows to describe a large number of data parallel applications in a suitable way. The GCA model can easily be implemented in software, efficiently interpreted on standard parallel architectures, and synthesized / configured into special hardware target architectures. This article reviews the model, applications, and hardware architectures.
翻译:Global Cellulal Automata 模型(GCA) 是 Cellulal Automata (CA) 模型的概括性。 GSA 模型包括一系列细胞,这些细胞根据邻国的状态而改变其状态,如古典 CA 模型。 在CA 模型的一般化中, 邻居不再固定和本地, 它们是可变的和全球性的。 在基本的 GCA 模型中, 单元格结构是一个数据部分和一个指针部分。 指针部分由几个持有全球邻国地址的指针组成。 数据规则定义了新的数据状态, 和指针规则定义了新的指针状态。 单元格的状态是同步或不同步地更新, 取决于其邻国的状态, 如古典CA 模式, 和新指针的状态。 因此, 全球邻国邻居可以从一代到下一代, 只有自己的单元格状态才被修改。 这样, 所有单元格都可以同时工作, 使得它成为一个巨大的平行模式。 GCA 模型与 CROW (当前阅读者写入) 模型, 一个特殊的 PRAM 特殊的配置, 和 版本的硬件结构, 可以将一个大型的硬件结构转换成一个大的系统。