Parallel Computing 27 (2001) 539±553
www.elsevier.com/locate/parco
Cellular automata: From a theoretical parallel computational model to its application to complex systems S. Bandini a,*, G. Mauri a, R. Serra b a
Department of Computer Science, Systems and Communication (DISCo), University of Milano-Bicocca, Via Bicocca degli Arcimboldi, 8-20134 Milan, Italy b Centro Ricerche Ambientali Montecatini, Via Ciro Menotti, 48-48023 Marina di Ravenna, Italy Received 12 October 2000
Abstract This introductory paper gives a short survey of cellular automata (CAs), from dierent points of view. It starts with the main de®nitions and theoretical results about CAs as an abstract model of computation or as discrete dynamical systems. Then, the main applications of CAs in dierent ®elds (biology, physics, etc.) as a model of complex systems are illustrated. Finally, implementations of the CA model on parallel computing platforms are surveyed. Ó 2001 Elsevier Science B.V. All rights reserved. Keywords: Cellular automata; Applications; Complex systems
1. Introduction and basic de®nitions This issue of Parallel Computing collects the best papers presented at the conference on ``Cellular Automata for Research and Industry'', held in Trieste (Italy) in September 1998. The selection includes papers containing the theoretical research results about cellular automata (CAs), as well as more application-oriented contributions that illustrate a growing scenario of interests in the ®eld of CAs.
*
Corresponding author. Present address: Dip. Informatica-Sistemistica e Comunicazione, Univ. Degli Studi di Milano-Bicocca, 20126 Milano, Italy. Tel.: +39-02-64487835; fax: +39-02-64487839. E-mail addresses:
[email protected] (S. Bandini),
[email protected] (G. Mauri),
[email protected] (R. Serra). 0167-8191/01/$ - see front matter Ó 2001 Elsevier Science B.V. All rights reserved. PII: S 0 1 6 7 - 8 1 9 1 ( 0 0 ) 0 0 0 7 6 - 4
540
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
This introductory paper aims at giving a short overview of the dierent aspects of CAs. In Section 1, the main theoretical results about CAs are presented. Section 2 illustrates the main applications of CAs in dierent ®elds. Finally, Section 3 concerns implementations of the CA model on parallel computing platforms. For a more detailed presentation of CAs, see [30,36,73]. The theory of CAs as models of self-reproducing systems was conceived and ®rstly developed by John Von Neumann during the 1950s, and was exposed in [72] In the same years, other researchers like Thatcher [68], Code [24] and Burks [16±18] contributed to completing and improving the model. Following these seminal papers, the interest in CAs grew in dierent directions, and they were studied from dierent perspectives. Informally, a CA is a set of identical elements, called cells, each one of which occupies a node of a regular, discrete, in®nite spatial network. Each cell can assume a state from a ®nite set, and the automaton evolves in discrete time steps, changing the states of all its cells according to a local rule, homogeneously applied at every step. The new state of a cell depends on the previous states of a set of cells, which can include the cell itself, and constitutes its neighborhood. More formally, we can give the following de®nition, assuming Zd as the underlying spatial network of the automaton. De®nition 1.1. A d-dimensional cellular automaton (or d-CA) is a structure A
Zd ; S; N ; d where: (a) Zd is the (discrete) lattice of d-tuples of integer numbers. (b) S is a ®nite set of states. (c) N f
nj
x1j ; . . . ; xdj =j 2 f1; . . . ; ngg is a ®nite ordered subset of Zd called the neighborhood of A. (d) d : S n1 ! S is the local transition function or local rule of A. It is useful to have a special state, called quiescent and denoted by 0, such that d
0; . . . ; 0 0. Let x 2 Zd be a cell, and s 2 S its state at time t. Then at time t 1, x will assume the state S 0 d
x n1 ; . . . ; x nn . Hence, the elements of N give the vector of displacements along each one of the d possible directions that allow reaching the cells that in¯uence the state change of the cell at hand. Two important neighborhoods are as follows: (a) Von Neumann neighborhood: ) ( d X nVN
nj
x1j ; . . . ; xdj =xkj 2 f 1; 0; 1g for k 1; . . . ; d and jxkj j 6 1 : k1
In this case, a cell x is connected to all the cells at a distance 1 along exactly one of the d coordinates, and with itself (distance 0): see Fig. 1(a). (b) Moore neighborhood: nM f
nj
x1j ; . . . ; xdj =xkj 2 f 1; 0; 1g for k 1; . . . ; dg In this case, a cell x is connected to cells at distance at most 1 in each direction (i.e., diagonal connections are allowed: see Fig. 1(b) for the 2D case).
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
541
Fig. 1. von Neumann (a) and Moore (b) neighborhoods for the cell x.
It appears clear from the above de®nition that the main characteristics of CAs are discreteness and locality. From the repeated synchronous application of the simple local evolution rules, a global behavior emerges which can be very complex. Let us now formalize the notion of evolution or behavior of CAs, starting with the de®nition of con®guration. De®nition 1.2. A configuration or instantaneous description or global state of a cellular automaton A
Zd ; S; n; d is a map C : Zd ! S that associates a state with every cell. We will denote by C
A, or simply C, the set of con®gurations of A. The synchronous application of the local rule to every cell allows transforming a con®guration into a new one. De®nition 1.3. The global function of a cellular automaton A
Zd ; S; n; d is a map FA : C ! C de®ned by FA
c
x d
x n1 ; . . . ; x nn for every x 2 Zd . De®nition 1.4. The behavior or evolution of a cellular automaton A from a given initial con®guration c0 2 C is a sequence of con®gurations fct gt P 0 , such that for t 2 n; ct1 FA
ct . The sequence fct gt P 0 is often designated as the orbit of c0 when CAs are considered as dynamical systems, or as a computation on c0 when they are seen as computation models.
2. Dynamical behavior of CAs Despite their apparently simple de®nition, based on local rules, CAs can show very complex dynamical behaviors, even in the case of the so-called elementary
542
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
CAs, i.e. 1D cellular automata with two neighbors and two states. To de®ne a precise criterium which captures the notion of complexity, concepts like chaos or non-ergodicity, taken from the theory of dynamical systems, have been used [46,47,50]. An important work on CAs as dynamical systems was done by Wolfram [73], with the interpretation of the 1D cellular automata dynamics in the framework of statistical physics. Wolfram proposes a classi®cation of 1D CAs in four complexity classes, according to the asymptotic pattern generated by the synchronous dynamics starting from random initial con®gurations: 1. Any initial con®guration converges to a ®xed homogeneous state (i.e., all the cells are in the same state). 2. The limits of initial con®gurations are cycles, with separated simple stable or periodic structures. 3. ``Chaotic'' or fractal patterns, with arbitrary periods, appear. 4. Breaking symmetry con®gurations (as gliders) and long-lived localized patterns appear. This classi®cation is empirical and dicult to apply. For example, it has been shown that the membership of a given CA even in the simpler class (1) is undecidable. However, this classi®cation is the basis for more rigorous classi®cation attempts. An attempt in the formalization of Wolfram's classi®cation scheme has been done by Culik and Yu (28) who split CA into three classes of increasing complexity. Unfortunately, membership in each of these classes is shown to be undecidable. A complete and eective classi®cation of elementary cellular automata was given by Braga [15]. The dynamical properties of CAs are essentially related to the properties of the global functions, such as surjectivity, injectivity and bijectivity. Another important property, in particular when CAs are considered as models of physical systems, is reversibility. Before considering these properties, let us de®ne some classes of con®gurations of particular interest: (a) Finite con®gurations: For every con®guration c 2 C we de®ne its support as the set of cells whose state is not the quiescent one supp
c fx 2 Zd : c
x 6 0g: We say c is ®nite if jsupp
cj < 1, and will denote by cfin the set of ®nite con®gurations. Since we are interested in using CAs to represent and manipulate ®nite data, these con®gurations are essential in the computation or language recognition areas. Since d
0; . . . ; 0 0, the global function maps ®nite con®gurations into ®nite con®gurations: FA : Cfin ! Cfin :
1
(b) Periodic con®gurations: A periodic con®guration is a con®guration c for which there exists x 2 Zd such that c
x Z c
x for every x 2 Zd . (c) Garden of Eden: Since the global function is not in general surjective, there are con®gurations that cannot be obtained during the evolution of the CA, but can only be taken as initial con®gurations, or given as ``input''. They are called Garden of
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
543
Eden con®gurations, and originated the systematic study of global functions [29,52,53]. The principal result is as follows [52,53]. Theorem 2.1. A cellular automaton with a quiescent state is surjective iff its restriction to finite configurations is injective. Another important problem is to characterize the set of global functions F, which come from local functions. This problem was solved by Hedlund [39] and Richardson [56]. Theorem 2.2. An application F : C ! C that commutes with the shift r, i.e. satisfies F r r F , is continuous with respect to the product topology on Zd iff it is the global function of a CA. Let us recall that r is de®ned by r
c
x c
x 1; this means that every cell x is mapped by r in the state assumed by the cell x 1 in the current con®guration, where 1 is the vector of all ones. We also have: Theorem 2.3. A cellular automaton is bijective iff it is reversible iff it is injective. Let us now introduce another important concept, the phase space of the cellular automaton A, that is a graph whose nodes are the con®gurations, and in which there is an arc from c to c0 i c0 FA
c. The orbit generated by a given initial con®guration c will correspond to a path in this graph. Some of these orbits, after an initial subpath without cycles, called transient, enter a cycle, called period of c. Periodic orbits of some classes of CAs, like additive or linear automata, have been completely characterized. An important role, in order to ®nd signi®cant classi®cations, is played by topologies or metrics de®ned on the phase space, and by related notions of topological chaos. Various notions of topological chaos for iterated discrete time dynamical systems, with applications to cellular automata dynamics, are introduced and compared in [21]. The study of the dynamics of CAs has played an important role in the development of concepts and conjectures in the ®eld of complex systems, in particular those concerning the notion of the ``edge of chaos'' [41±43] and ``self-organized criticality'' [4,5]. Langton [43] observed that, by de®ning a suitable order parameter on a set of CA rules, it was possible to observe a transition between an interval of values of the order parameter where the automata displayed ordered behaviors (Wolfram's classes 1 or 2), and an interval corresponding to chaotic behaviors (class 3). The transition region, corresponding to class 4 behavior, was a sort of boundary between ordered and chaotic regimes, and was called the ``edge of chaos''. Packard [54] observed that a population of CA rules, which evolved under selective pressure trying to perform a
544
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
computational task, tended to reach the boundary region, which seemed favored with respect to other regions. Mitchell et al. [51] investigating a dierent case, obtained very dierent results, where the evolution towards the boundary region is not observed. Kauman [42] provided heuristic arguments, as well as examples from other dynamical systems, in favor of the notion that complex adaptive systems tend to evolve under fairly general conditions towards the ``edge of chaos'' which separates the ordered and the chaotic regions. Self-organized criticality [4,5] is a theory of the evolution of dynamical systems, which emphasizes the role of the so-called critical states, which are ubiquitous in nature and which are characterized by the presence of perturbations of every size, following a power-law distribution. This theory aims at a great generality and has generated an animated debate on complex systems' theoretical research. It is worth recalling here that the basic example upon which the whole theory was built, namely the celebrated sandpile, has been modeled by Bak and co-workers with a simple CA rule. It should also be recalled that the work by Mitchell, Crutch®eld and co-workers on emergent computation, who developed CAs to be able to perform various computational tasks and a theoretical framework to analyze them, called computational mechanics (see e.g. [27]); an interesting example concerning density classi®cation can be found in this volume (see the paper by Jimenez Morales et al.). These examples show how the availability of CA models has allowed the birth and the development of deep concepts for the investigation of the theoretical bases of complex systems behavior. 3. Computing capabilities of CAs Cellular automata can be considered as an abstract model of computation, which transforms a given ®nite con®guration, representing the input data, in an output con®guration. The computational capabilities of CAs have been extensively studied since the beginning, for example by Thatcher [68], Codd [24], Banks [11] and Burks [18]. They proved that there exist CAs that have the capabilities of an universal Turing machine, hence could be used as general-purpose computers. The notion of universality was de®ned both in a direct way and by simulation of Turing machines. In the above-quoted papers, 2D cellular automata were considered, and the main eort was to ®nd the simpler (i.e., with less states) universal automaton. In particular, starting from a universal automaton with von Neumann neighborhood and 29 states, shown by von Neumann, Codd reduced the number of states to 8 and Banks to 4. If we consider the Moore neighborhood, only two states suce to obtain universality. This was shown by Conway [13,26]. Its universal automaton has been presented as a solitaire computer game, the well-known ``Game of Life''. It is natural to ask whether universality may be obtained even with 1D automata. A positive answer was given by Smith [62], who proved the following theorem.
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
545
Theorem 3.1. Given a Turing machine with n internal states and m alphabetic symbols, there exists a 1D cellular automaton with six neighbors and max
n; m 1 states which simulates it.
4. Applications of CAs The primitive concept of CAs dates back to the late 1940s, but during their following existence, CAs models and applications have been created, developed, and used in many dierent ®elds. In spite of the large amount of work made throughout these dierent ®elds, in this section the focus will be on applications, letting to the solid literature on CA the task of satisfying other interests of the readers about this topic. 1 In general, it is possible to distinguish two main approaches in the creation of CA models: forward and backward [73]. The forward (theoretical) approach concerns the study of transition rules of a given cellular space in order to establish its intrinsic properties (dynamical behavior, patterns growth, and so on [74]. The backward (practical) approach regards the design of transition rule sets of a designed cellular space in order to match the ``right'' behavior of the CA system of a given complex system (physical, biological, social, urban, and so on). Many actual applications of CA directly derive from the theoretical results (as in the case of the dialectics between physics and engineering sciences, for example). In several cases, sets of backward rules show a successful behavior matching on the behavior of a given system, and the theoretical properties of such rules have to be investigated. Looking around in the world of applications of CA, it is possible to hazard the observation of a mirroring situation between the CA world and the world of the hard/soft sciences: where formal models can be de®ned, a synergic cycle among theoretical and application aspects rises. The example of physics is an evident case of this cycle. Moreover, in many cases of scienti®c discovery, the cycle is very complex, and the exact role of theoretical and application/experimental contribution is fuzzy. In the case of not-hard sciences (e.g. urbanistics, sociology, and so on), the question is controversial, but the lack of formal models due to the intrinsic very complex nature of phenomena often does not allow the above-mentioned cycle to be evident. The application of CA to physical systems has been the ®rst successful case. In particular, the case of the so-called HPP (from the name of the authors) lattice gas model [38] signed an important milestone in the evolution of CA models. As well described in [23], the HPP dynamics was initially planned as a theoretical model to study the fundamental statistical properties of a gas of interacting particles. Simplifying, since it is well known that the ¯ows of a real system of particle (like a ¯uid or a gas), a fully discrete and simpli®ed molecular dynamics could simulate a ¯uiddynamic phenomenon at an appropriated observation scale. This principle is the 1
ftp://alife.santafe.edu/pub/topics/cas/ca-faq.bib
546
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
basis of many applications of ¯uid-dynamic CA models to simulate real physical phenomena. It should also be stressed that the so-called lattice Boltzmann automata [64] have been successful in simulating ¯uid dynamics, by resorting to a state space which is continuous. This departure from the original CA paradigm improves however their simulation capabilities, and it has been taken also in the so-called macroscopic cellular automata [33]. A case of industrial application of a CA (HPP) is the simulation of water percolation processes occurring in a porous medium: ground and toasted coee [20]. This work has been developed within the cellular automata for percolation processes (CAPPs) transfer technology project, supported by European Union [8]. Within this project, also the applications of CA to the simulation of visco-elastic properties in rubber compounds [10] and of reaction±diusion phenomena in polluted soil [9] have been developed in collaboration with three companies. They gave the real experimental data of the investigated phenomena in order to verify the goodness of the models and of the simulations results. All the three applications of the CAPP projects have been developed on parallel platforms (CRAY 3TE and Origin 2000) at CINECA (Bologna), showing good performances [8]. In the framework of projects supported by UE another interesting industrial application must be mentioned: the CABOTO, and its successor COLOMBO projects dedicated to the modeling of the problem of bioremediation of contaminated soils. They regard a CA-based model which describes the interaction among physical, chemical and biological phenomena which take place during in situ bioremediation, and which can be used to forecast the results of interventions in the ®eld, starting from laboratory and pilot plant data [31,59]. Biology is one of the ®rst disciplines involved in the application of CA. The main purpose of von Neumann when he created the core de®nition of CAs [17] was the development of a formal computational model for the description and the simulation of self-reproduction in a biological sense. Today it is possible to roughly divide the research and the application of CA in biology into two main branches. The ®rst falls in the general topic of Arti®cial Life (Alife) models [44,45], and the second regards models and systems that have been developed for studying dynamical properties of biological phenomena. The boundaries of these two sets are fuzzy. This fact depends on the discipline where researchers belong to, on the speci®c biological phenomena to be studied using computational supports, and of the possible interactions occurring in interdisciplinary environments (i.e., computer scientists involved in some biological research). For instance, the creation of a CA-based system for the simulation of the cellular interaction in the immune system [22] has been possible thanks to the positive collaboration between an immunologist and a theoretical physicist at the Watson Research Center of IBM (USA). A nested CA-based model has been developed from this original devoted to the immune system and adopted also for the simulation of the calcium ions diusion in living cells [7]. Models and simulations of vegetal growth is a very interesting case of application of CA. In [3] a CA model for the simulation of emergent spatial structure in vege-
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
547
tation successions is presented. It allows the examination of the response of the boreal treeline of northern Quebec to various environmental forcing factors, such as climate amelioration in the post-glacial period. Moreover, a CA-based model and the related parallel simulation concerning growth patterns of botanical colonies is presented in [40] This simulation shows graceful features visualizing the structural dynamics of the growing colonies. Other interesting applications can be found in [6,25,37]. The importance of the dynamics of gene expression in a cell is becoming increasingly clear for the study, e.g. of cell dierentiation, switching among dierent metabolic regimes and tumor growth. A simpli®ed model of random boolean networks, proposed by Kauman [41], which can be regarded as a CA-like model, has provided valuable theoretical insights into the generic behavior of these networks. A generalization of this model, designed to describe the bacterial degradation of organic compounds by bacterial consortia, has been proposed [57,59], which allows for the presence of exogenous chemicals and for continuous activation values. By adopting a simpli®ed version of this model as the rule for cell dynamics, it has also been possible to develop a CA model which describes the growth of a population of cells in a tissue, simulating the development of tumors in in vitro cell cultures [60]. Another topic that is becoming a challenging application ®eld for CA regards the simulation of population dynamics. Research contributions (e.g. [14,61]) de®ned the basis of this approach, and constituted a side important milestone also in the application of CA to the simulation of the dynamics of populations organization. For instance, change within an organization is a complex phenomenon that involves the interaction of many individuals and can be studied by CA in the area of Arti®cial Societies [34]. This interaction among independent entities makes CA useful in modeling the diusion of change processes in populations. Other disciplines that are introducing CA-based models and applications are those involved in geography and economic geography. Cellular geography has been introduced by W. Tobler [69] more than 20 years ago, and today is a central issue in the application of models and computer-based simulation systems [12]. In economic geography several models concerning competition and coordination dynamics in the formation of social clusters have been successfully applied on several cases [35,48]. Trac control is another application area that involves CA models and systems. An overview of the main results in this area can be found in [63]. The main applications in this area regard both urban and extra-urban trac, and the CA approach allows the knowledge of the trac state to be explicitly represented in the model in order to simulate crucial situations (i.e., trac jams). Also Arti®cial Vision has been approached by CA models [49]. The most meaningful application area is edge detection of images in automotive [1]. Another suggestive application ®eld of CA concerns graphics applications. Examples of this novel CA topic are etherogeneous. Virtual clay modeling [2] and the texture generation by CA [66] have been performed. In the late example, arti®cial evolution of RD textures, maze formation and zebra formation examples have been simulated. In [65] parallel particle systems are applied to the cases of ¯ames, ¯ames in the wind, trickle of water (steps and slope), collision and scatter, aggregation of particles.
548
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
5. Parallel implementation of CAs Although CAs have been conceived at a time when the computing tools which were available to the majority of researchers were pen and pencil, they seem to be ``born for computers'', as the use of discrete time and discrete state space perfectly ®ts the features of digital computers. Actually, CA and computers were born at about the same time, and one might speculate upon the fact that the inventor of the CAs approach, John von Neumann, has been also deeply involved in the development of digital computers, so the relationship might not be due to chance. Unknown at the time of their conception, there is another feature of CA which makes them well suited also for simulation on parallel computers, which do not conform to the von Neumann architecture, namely locality of interactions. Moreover, the regular topologies that are used in CA allow the use of straightforward parallelization methods. It is trivial to observe that some global information is also needed for simulating a CA, for example the parameters of the transition function that must be uniform over the entire grid. While in classical, textbook cases these parameters are ®xed once and for all, there may be cases where they may change in time, and must do so in a globally coherent way. There is of course some fuzziness concerning the de®nition of a CA; while the classical ``basic case'' is that of a fully homogeneous automaton with a discrete state space, the requirements related to the application of a CA approach to real problems have led many researchers to ``enlarge the paradigm''. Among the most important extensions, let us recall the introduction of inhomogeneous automata, where different cells may be ruled by dierent transition functions, and of continuous state spaces (for a discussion see [32,33,75]. Inhomogeneous automata are necessary to deal with systems with physical boundaries, whose behavior diers from that of the bulk cells; continuous state spaces are necessary, e.g. in lattice Boltzmann or in macroscopic CA, in order to deal with a coarser graining of physical systems than that which is typical of lattice gases. For the sake of de®niteness, let us consider the case of macroscopic CAs [33], where the state variables refer to macroscopic quantities like, for example, concentrations of chemicals in a given ¯uid phase. In this case, the transition function of every cell might require the knowledge of phenomenological parameters, e.g. partition coecients of a given chemical among dierent phases, which may depend upon physical parameters like the temperature. If the system is not held at ®xed temperature, this parameter may change in time, and there is a need to make available the corresponding information to each cell. It is possible, in principle, to introduce (local) heat transport mechanisms into the model, but this may be inconvenient, or computationally heavy, so a macroscopic description might require global variables which are determined from ``outside'' the system itself. And it is of course necessary to provide each cell which the necessary information. Moreover, there may be cases where a CA model is coupled with a parameter estimation algorithm, like e.g. genetic algorithms [31]. The whole procedure which
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
549
tailors the model to the case at hand involves multiple simulations, with dierent parameter values, and the use of an optimization algorithm to ®nd the set of parameter values which provides the best match with a set of experimental values. Also in this case, it is necessary to provide each cell with the information concerning the present parameter values. A dierent case, which does not strictly require global variables, but which requires an information ¯ow among distant parts of the system, can show up when one models phenomena with dierent time constants, where fast and slow processes coexist and interact. A frequently useful approximation is the adiabatic one, where the slow variables are kept constant until the fast ones reach their stationary values. An example is provided by the simulation of ¯uid transport in porous media by macroscopic CA [71]. If one wants to model the dicult case of unsaturated media, where the water phase does not ®ll entirely the pore space, then he has to determine at each time step the pressure ®eld of the water phase, which is a fast relaxing variable. In fact after the pressure ®eld has reached convergence, mass ¯ow simply follows the pressure gradient. It turns out that reaching convergence may require dierent times in dierent portions of the system, and the computation of mass ¯ow has to wait for the convergence of the slowest part. This implies of course the need for information ¯ow among distant parts of the system. So, it may be necessary, or convenient, to introduce macroscopic global variables in CAs for the description of real-world problems, and/or to handle information ¯ows among distant cells. This may of course pose a limitation upon the eciency of parallel implementations. Nonetheless, very high speed-ups have been obtained even with macroscopic CAs on MIMD parallel computers [58]. Classical CA can be eciently run on special purpose hardware, on SIMD machines and on MIMD machines. Among the former, let us recall the cellular automata machine (CAM) series, which has now reached the CAM-8 release, and which has been designed by Tooli and co-workers at MIT for the purpose of ecient CA simulation [70]. CAM machines have played an important role in the diusion of the CA approach, by providing high computing speeds at limited cost since the 1980s. CAs have also become a frequent benchmark for SIMD machines. Let it suce to recall the simulation of CA on the DAP and on the Connection Machine CM-2 [55]; see [67] for a review. There is an obvious match between the architecture of a CA, with its cells, synchronous updating and local connections, and the architecture of a SIMD machine, with its locally connected simple processors. MIMD architectures present, with respect to both the special purpose hardware and SIMD architectures, the advantage of a higher ¯exibility and a wider application spectrum. While they may appear at ®rst sight more to be complicated than what is needed to simulate CA, several examples have been provided in the literature of very good speed-ups achieved also with MIMDs. Actually, someone said that parallelization of CA is embarassingly easy, but of course we need not be embarassed. On the contrary, the ease of parallelization represents an advantage, rather than a limitation of the approach. Ecient parallelization on MIMDs may also bene®t from a clever parallelization scheme. There are indeed several cases, in the simulation of a physical system, where
550
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
only a limited portion of the cells change their state variables at each time step (this may happen, for example, when there is an advancing front of some physical quantity which is spatially limited to a small region of the whole space, like e.g. in modeling lava ¯ows [32]. In these cases, straightforward parallelization strategies, which assign to each processor a given portion of the whole space, would lead to most processors staying idle for most of the time. It is more convenient to resort to less trivial mapping of CA cells to processing elements, as it is done, e.g. in the Camel environment [19]. There are of course several software environments which are available for CAs. For a review, see e.g. [75]. Recently, within the framework of the Esprit project Colombo, a software environment for CA simulation on parallel architectures, based upon the MPI standard, has been developed and tested on several machines, including the Computing Surface and PC clusters [71]. While the environment has been devised in particular for the simulation of the remediation of contaminated sites, its kernel, called Camelot, can be used as a general-purpose CA simulator on parallel architectures. In conclusion, it is also worth stressing that the relationship between CA and parallel computation is not only technological, but also conceptual. CA represents a way of describing the world which naturally ®ts parallel computers, while the latter provide precious hints to useful enlargements of the classical CA model. References [1] G. Adorni, S. Cagnoni, M. Mordonini, Uniform and non-uniform cellular automata: Some issues and case studies in computer vision, in: S. Bandini, R. Serra, F. Suggi Liverani (Eds.), Cellular Automata: Research Towards Industry, Springer, London, 1998. [2] H. Arata, Y. Takai, N.K. Takai, T. Yamamoto, Free-form shape modeling by 3D cellular automata, in: Proceedings of Shape Modeling International'99, 1999. [3] D.E. Atkinson, M.C. Sawada, K. Gajewski, Emergent spatial structure in vegetation succession, in: Proceedings of the Annual Meeting of the Canadian Association of Geographer, Ottawa, 1998. [4] P. Bak, C. Tang, K. Wiesenfeld, Self-organized criticality, Phys. Rev. A 38 (1988) 364±374. [5] P. Bak, How nature works: The Science of Self-organized Criticality, Copernicus Books, 1996. [6] H. Baltzer, W.P. Braun, W. Kohler, Cellular automata models for vegetation dynamics, Ecol. Modeling 107 (1998) 113±125. [7] S. Bandini, G. Mauri, Multilayered automata networks, Theoret. Comput. Sci. 217 (1999) 99±113. [8] S. Bandini, G. Erbacci, G. Mauri, Implementing cellular automata based models on parallel architectures: The CAPP project, in: V. Malyshkin (Ed.), Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 1662, Springer, Berlin, 1999. [9] S. Bandini, G. Mauri, G. Pavesi, C. Simone, Parallel simulation of reaction±diusion phenomena in percolation processes: A model based on cellular automata, in: Future Generation Computer Systems, Elsevier, Amsterdam, 2000a. [10] S. Bandini, M. Magagnini, Parallel processing simulation of dynamic properties of ®lled rubber compounds based on cellular automata, Parallel Computing 27 (2001), this issue. [11] E.R. Banks, Information processing and transmission in cellular automata, MIT Project, MAC Report No. TR-81, 1971. [12] M. Batty, H. Couclelis, M. Eichen (Eds.), Urban Systems as Cellular Automata (special issue), Planning Design 24 (2) (1997). [13] E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways, vol. 2, Academic Press, 1985 (Chapter 25).
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
551
[14] N. Boccara, Automata networks models of interacting populations, in: E. Goles, S. Martinez (Eds.), Cellular Automata, Dynamical Systems and Neural Networks, Kluwer Academic Publishers, The Netherlands, 1994. [15] G. Braga, G. Cattaneo, P. Flocchini, C. Vogliotti, Pattern growth in elementary cellular automata, Theoret. Comput. Sci. 145 (1995) 1±26. [16] E. Burks, Theory of Self-Reproduction, University of Illinois Press, Champaign, IL, 1966. [17] A.W. Burks, Von Neumann's self-reproducing automata, in: A.W. Burks (Ed.), Essays on Cellular Automata, University of Illinois Press, Champaign, IL, 1970, pp. 3±74. [18] E. Burks, Essays on Cellular Automata, University of Illinois Press, Champaign, IL, 1972. [19] M. Cannataro, S. Di Gregorio, R. Rongo, W. Spataro, G. Spezzano, D. Talia, A parallel cellular automata environment on multicomputers for computational science, Parallel Comput. 21 (1995) 803±824. [20] R. Cappuccio, G. Cattaneo, G. Erbacci, U. Jocher, A parallel implementation of a cellular automata based model for coee percolation, Parallel Computing 27 (2001), this issue. [21] G. Cattaneo, E. Formenti, L. Margara, Topological de®nitions of deterministic chaos, in: J. Mazoyer (Ed.), Cellular Automata, Kluwer Academic Publishers, Dordrecht, 1999. [22] F. Celada, P. Seiden, A computer model of cellular interactions in the immune system, Immunol. Today 13 (1992) 56±62. [23] B. Chopard, Cellular Automata Modeling of Physical Systems, Cambridge University Press, Cambridge, UK, 1998. [24] E.F. Codd, Cellular Automata, Academic Press, New York, 1968. [25] R.L. Colasanti, J.P. Grime, Resource dynamics and vegetation processes, a deterministic model using two-dimensional cellular automata, Functional Ecol. 7 (1993) 169±176. [26] J.H. Conway, Unpublished, quoted in [13]. [27] J.P. Crutch®eld, M. Mitchell, The evolution of emergent computation, Proc. Natl. Acad. Sci., USA 92 (1995) 10742±10746. [28] K. Culik II, S. Yu, Undecidability of CA classi®cation schemes, Complex Systems 2 (1988) 177±190. [29] K. Culik II, J. Pachl, S. Yu, On the limit sets of cellular automata, SIAM J. Comput. 18 (1989) 831± 842. [30] M. Delorme, J. Mazoyer (Eds.), Cellular Automata, Kluwer Academic Publishers, Dordrecht, 1999. [31] S. Di Gregorio, R. Serra, M. Villani, A cellular automata model of soil bioremediation, Complex Systems 11 (1) (1997) 31±54. [32] S. Di Gregorio, R. Serra, An empirical method for modelling and simulating some complex phenomena by cellular automata, Future Generation Comput. Systems 16 (1999) 259±271. [33] S. Di Gregorio, R. Serra, M. Villani, Applying cellular automata to complex environmental problems: The simulation of the bioremediation of contaminated soils, Theoret. Comput. Sci. 217 (1999) 131±156. [34] J.M. Epstein, R. Axtell, Growing Arti®cial Societies: Social Science from the bottom up, Brooking Institution Press, Washington, DC, 1996. [35] A. Ginsberg, E. Larsen, A. Lomi, Where do industrial districts come from? A cellular automata model of competition, cooperation and the dynamics of industrial clusters, in: S. Bandini, R. Serra, F. Suggi Liverani (Eds.), Cellular Automata: Research Towards Industry, Springer, London, 1998. [36] E. Goles, S. Martinez, Neural and Automata Networks: Dynamical Behavior and Applications, Kluwer Academic Publishers, Boston, 1990. [37] D.G. Green, Modeling plants in landscape, in: T.H. Michalewicz (Ed.), Plants to Ecosystem, CASIRO, Lollingwood Ans, 1997. [38] J. Hardy, Y. Pomeau, O. de Pazzis, Molecular dynamics of a classic lattice gas: Transport properties and time correlation functions, Phys. Rev. A 13 (1976) 1949±1960. [39] G.A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. System Theory 3 (1969) 320±375. [40] T.L. Kunii, Y. Takai, Cellular self-reproducing automata as a parallel processing model for botanical colony growth pattern simulation, in: New Advances in Computer Graphics, Springer, Berlin, 1989. [41] S.A. Kauman, The Origins of Order, Oxford University Press, Oxford, 1993.
552
S. Bandini et al. / Parallel Computing 27 (2001) 539±553
[42] S.A. Kauman, At Home in the Universe, Oxford University Press, Oxford, 1995. [43] C.G. Langton, Computation at the edge of chaos: Phase transitions and emergent computation, Physica D 42 (1990) 12±37. [44] C.G. Langton, Arti®cial Life, Addison-Wesley, New York, 1989. [45] C.G. Langton, C. Taylor, J.D. Farmer, S. Rasmussen (Eds.), Arti®cial Life II, Addison-Wesley, New York, 1992. [46] D.A. Lind, Applications of ergodic theory and so®c systems to cellular automata, Physica D 10 (1984) 36±44. [47] K. Lindgren, M. Nordhal, Complexity measures and cellular automata, Complex Systems 2 (4) (1988) 409±440. [48] A. Lomi, E.R. Larsen, Interacting locally and evolving globally: A computational approach to the dynamics of organizational populations, Acad. Manage. J. (39) (1996). [49] R.A. Marques Pereira, Early vision with cellular automata ®elds, in: M.S. Garrido, R. Vilela Mendes (Eds.), Complexity in Physics and Technology, World Scienti®c, Singapore, 1992. [50] J. Milnor, On the entropy geometry of cellular automata, Complex Systems 2 (3) (1988) 257±385. [51] M. Mitchell, P.T. Hraber, J.P. Crutch®eld, Revisiting the edge of chaos: Evolving cellular automata to perform computation, Complex Systems 7 (1993) 89±130. [52] E.F. Moore, Machine models of self-reproduction, Proc. Symp. Appl. Math. 14 (1962) 17±33. [53] J. Myhill, The converse of Moore's garden-of-eden theorem, Proc. AMS 14 (1963) 685±686. [54] N.H. Packard, Adaptation toward the edge of chaos, in: J.A. Scott Kelso, et al. (Ed.), Dynamic Patterns in Complex Systems, World Scienti®c, Singapore, 1988. [55] M. Resnick, Turtles, Termites and Trac Jams, MIT Press, Cambridge, MA, 1994. [56] D. Richardson, Tessellations with local transformations, J. Comput. System Sci. 5 (1972) 373±388. [57] R. Serra, M. Villani, Modelling bacterial degradation of organic compounds with genetic networks, J. Theoret. Biol. 189 (1) (1997) 107±119. [58] R. Serra, S. Di Gregorio, M. Villani, M. Andretta, Bioremediation simulation models, in: R. Serra (Ed.), Biotechnology for Soil Remediation, Cipa Editore, Milano, 1998. [59] R. Serra, M. Villani, A. Salvemini, Continuous genetic networks, Parallel Computing 27 (2001), this issue. [60] R. Serra, M. Villani, A. Colacci, A cellular automata model for the simulation of in vitro carcinogenesis tests, in: T. Worsch, S. Bandini (Eds.), Proceedings of ACRI 2000, Springer, London, 2000. [61] K. Satoh, Computer experiment on the complex behavior of a two-dimensional cellular automaton as a phenomenological model for an ecosystem, J. Phys. Soc. Jpn. (58) (1989). [62] A.R. Smith, Simple computation-universal cellular spaces, J. ACM 18 (3) (1971) 339±353. [63] M. Schreckenberg, D.E. Wolf (Eds.), Trac and Granular Flow'97, World Scienti®c, Singapore, 1998. [64] S. Succi, R. Benzi, F. Higuera, The lattice Boltzmann equation: A new tool for computational ¯uid dynamics, Physica D 47 (1991) 219±230. [65] Y. Takai, K. Ecchu, N.K. Takai, A cellular automaton model of particle motions and its applications, The Visual Comput. 11 (5) (1995). [66] Y. Takai, N.K. Takai, K.J. Nakamori, Exploration of the reaction±diusion textures, in: Proceedings of the International Conference on Modelling and Simulation, 1998. [67] D. Talia, Parallel cellular automata for high performance computational simulation, in: Proceedings of HPC'98, SCS Press, San Diego, 1998. [68] J. Thatcher, Universality in the von Neumann cellular model, Technical Report 03105-30-T, University of Michigan, 1964. [69] W. Tobler, Mathematical map models, in: Proc. Int. Symposium on Computer Aided Cartography, Reston, American Congress on Surveying and Mapping, 1975, pp. 66±73. [70] T. Tooli, N. Margolus, Cellular Automata Machines, MIT Press, Cambridge, MA, 1987. [71] M. Villani, M. Mazzanti, M. Padovani, M. Andretta, R. Serra, S. Di Gregorio, R. Rongo, W. Spataro, A new dynamical model of biodegradation, in: T. Worsch, S. Bandini (Eds.), Theoretical and Practical Issues on Cellular Automata, Springer, London, 2000.
S. Bandini et al. / Parallel Computing 27 (2001) 539±553 [72] [73] [74] [75]
553
J. von Neumann, Theory of Self-reproducing Automata, University of Illinois Press, Urbana, 1966. S. Wolfram, Theory and Applications of Cellular Automata, World Scienti®c, Singapore, 1986. S. Wolfram, Cellular Automata and Complexity, Addison-Wesley, Reading, MA, 1994. T. Worsch, Programming environments for cellular automata, in: S. Bandini, G. Mauri (Eds.), Proceedings of ACRI'96, Springer, London, 1996.
