Cellular automata-based systems with fault-tolerance
Tóm tắt
One of the new computing paradigms which could overcome some of the problems of existing computing architectures may be cellular computing. In the investigated scenario, cellular automata-based systems are intended for yet-unknown methods of fabrication and as such, they need to address the problem of fault-tolerance in a way which is not tightly connected to used technology. Our goal is to reach not too complicated solutions, which may not be possible with existing elaborate fault-tolerant systems. This paper presents a possible solution for increasing fault-tolerance in cellular automata in a form of static module redundancy. Further, a set of experiments evaluating this approach is described, using triple and quintuple module redundancy in the automata with the presence of defects. The results indicate that the concept works for low intensity of defects for our selected benchmarks, however, the ability to cope with defects can not be intuitively deduced beforehand, as shown by the varying outcomes. One of the problems—the majority task—is then explored further, investigating the cellular automaton’s ability to cope not only with defects but also with transient errors.
Tài liệu tham khảo
Andre D, Bennett III FH, Koza JR (1996) Discovery by genetic programming of a cellular automata rule that is better than any known rule for the majority classification problem. In: Proceedings of the first annual conference on genetic programming, GECCO ’96. MIT Press, Cambridge, pp 3–11
Beckett P, Jennings A (2002) Towards nanocomputer architecture. In: Proceedings of the seventh Asia-Pacific conference on computer systems architecture, CRPIT ’02. Australian Computer Society, Inc., Darlinghurst, pp 141–150
Bersini H, Detour V (1994) Asynchrony induces stability in cellular automata based models. In: Brooks RA, Maes P (eds) Artificial life IV. MIT Press, Cambridge, pp 382–387
Byl J (1989) Self-reproduction in small cellular automata. Physica D 34(1–2):295–299
Durbeck L, Macias N (2001) The cell matrix: an architecture for nanocomputing. Nanotechnology 12(3):217–230
Dysart T, Kogge P (2008) System reliabilities when using triple modular redundancy in quantum-dot cellular automata. In: IEEE international symposium on defect and fault tolerance of VLSI systems, 2008. DFTVS ’08, pp 72–80. doi:10.1109/DFT.2008.25
Gardner M (1970) The fantastic combinations of john conway’s new solitaire game ’life’. Sci Am 223:120–123
Garzon M (1995) Models of massive parallelism: analysis of cellular automata and neural networks. Springer, London
Gasc P, Kurdyumov G, Levin L (1978) One-dimensional homogeneous media dissolving finite islands. Probl Inf Transm 14(3):92–96
Lala, PK (eds) (2001) Self-checking and fault-tolerant digital design. Morgan Kaufmann Publishers Inc, San Francisco
Li W (1992) Phenomenology of nonlocal cellular automata. J Stat Phys 68:829–882. doi:10.1007/BF01048877
Macias N, Durbeck L (2004) Adaptive methods for growing electronic circuits on an imperfect synthetic matrix. Biosystems 73(3):173–204. doi:10.1016/j.biosystems.2003.12.003
Mange D, Sipper M, Stauffer A, Tempesti G (2000) Towards robust integrated circuits: the embryonics approach. Proc IEEE 88(4):516–541
Mitchell M (1998) An introduction to genetic algorithms. MIT Press, Cambridge
Peper F, Lee J, Abo F, Isokawa T, Adachi S, Matsui N, Mashiko S (2004) Fault-tolerance in nanocomputers: a cellular array approach. IEEE Trans Nanotechnol 3(1):187–201. doi:10.1109/TNANO.2004.824034
Sekanina L, Komenda T (2011) Global control in polymorphic celular automata. J Cell Autom 6(4):301–321
Sipper M (1997) Evolution of parallel cellular machines: the cellular programming approach. Lecture Notes in Computer Science, vol 1194. Springer, Berlin
Sipper M (1999) The emergence of cellular computing. Computer 32(7):18–26. doi:10.1109/2.774914
Stepney S, Braunstein SL, Clark JA, Tyrrell A, Adamatzky A, Smith RE, Addis T, Johnson C, Timmis J, Welch P, Milner R, Partridge D (2005) Journeys in non-classical computation I: a grand challenge for computing research. Int J Parallel Emergent Distrib Syst 20(1):5–19
Toffoli T, Margolus N (1987) Cellular automata machines: a new environment for modeling. MIT Press, Cambridge
Wolfram S (1994) Cellular automata and complexity: collected papers. Addison-Wesley, Reading
Wolfram S (2002) A new kind of science. Wolfram Media Inc, Champaign
Zaloudek L (2011) Permanent errors may contribute to emergent behavior in one-dimensional cellular automata. In: Third world congress on nature and biologically inspired computing (NaBIC, 2011), pp 57–62. doi:10.1109/NaBIC.2011.6089417
Zaloudek L, Sekanina L (2011) Increasing fault-tolerance in cellular automata-based systems. In: 10th International conference unconventional computation, UC 2011, Turku, Finland. Lecture Notes in Computer Science, vol. 6714. Springer, Berlin, pp 533–537
Zaloudek L, Sekanina L, Simek V (2010) Accelerating cellular automata evolution on graphics processing units. Int J Adv Soft 3(1):294–303