Next: 3.4 The Temporal Properties Up: 3 A Methodology for Previous: The Process of

# Examples of Complex Systems and TheirSpace-Time Structure

In the previous section, we showed how the process of computation could be viewed as mappings between complex systems. As the book progresses, we will quantify this by providing examples that cover a range of problem architectures. In the next three sections, we will set up the general framework and define terms which will be made clearer later on as we see the explicit problems with their different architectures. The concept of complex systems may have very general applicability to a wide range of fields but here we will focus solely on their application to computation. Thus, our discussion of their properties will only cover what we have found useful for the task at hand. These properties are surely more generally applicable, and one can expect that other ideas will be needed in a general discussion. Section 3.3 gives examples and a basic definition of a complex system and its associated space-time structure. Section 3.4 defines temporal properties and, finally, Section 3.5 spatial structures.

We wish to understand the interesting characteristics or structure of a complex system. We first introduce the concept of space-time into a general complex system. As shown in Figure 3.7, we consider a general complex system as a space, or data domain, that evolves deterministically or probabilistically with time. Often, the space-time associated with a given complex system is identical with physical space-time but sometimes it is not. Let us give some examples.

Figure 3.7: (a) Synchronous, Loosely Synchronous (Static), and (b) Asynchronous (Dynamic) Complex Systems with their Space-Time Structure

• For a computer considered as a complex system, the space is the collection of processing nodes, communication channels and peripherals as illustrated in Figures 1.1 and 1.2. Time is the physical time, but it is usually quantized, with for instance a unit of seconds for a node.

• An earthquake  can be considered as a physical complex system () which is first mapped, by the theoretical geophysicist who is modelling it, into displacements measured by the amplitudes of waves as a function of space and time. Here again, the complex system () space-time is mapped into physical space-time. One might Fourier-Transform this picture to obtain a third complex system () whose space is now labelled by wave numbers.

• One might record this earthquake on a collection of N strip recorders. Now the resultant complex system () is a collection of N sheets of paper. The space of consists of the set of sheets and has N discrete members. The time associated with is the extension along the ``long'' (say x) direction of each sheet. This complex system is specified by the recording on the other (y) direction as a function of the time defined above. This example illustrates how mappings between complex systems can mix space and time. This is further illustrated by the next example, which completes the sequence of complex systems related to earthquakes.

• Suppose one writes a Fortran program to simulate such an earthquake and runs it on a conventional single processor workstation. This von Neumann model of computation has mapped the original complex system into one () with perhaps one or at best a few elements in its spatial domain corresponding to the independent functional units on the workstation. has mapped the original space-time into a totally temporal complex system. This could be viewed either as an example of the richness of mappings allowed between complex systems or as an illustration of the artificial nature of the sequential computing! Simulation of an earthquake on a parallel computer more faithfully links the space-time of the problem () with that of the simulation ().

• The seismic  simulation, mentioned above, could involve solution of the wave equation

Consider instead the solution of the elliptic partial differential equation

for the electrostatic potential in the presence of a charge density . A simple, albeit usually non-optimal approach to solving Equation 3.4, is a Jacobi iteration, which in the special case of two dimensions and involves the iterative procedure

where we assume that integer values of the indices x and y label the two-dimensional grid on which Laplace's  equation is to be solved. The complex system defined by Equation 3.5 has spatial domain defined by the grid and a temporal dimension defined by the iteration index n. Indeed, the Jacobi iteration is mathematically related to solving the parabolic partial differential equation

where one relates the discretized time t to the iteration index n. This equivalence between Equations 3.5 and 3.6 is qualitatively preserved when one compares the solution of Equations 3.3 and 3.5. As long as one views iteration as a temporal structure,  Equations 3.3 and 3.4 can be formulated numerically with isomorphic complex systems . This implies that parallelization issues, both hardware and software, are essentially identical for both equations.

The above example illustrates the most important form of parallelism-namely, data parallelism. This is produced by parallel execution of a computational (temporal) algorithm on each member of a space or data domain. Data parallelism is essentially synonymous with either massive parallelism or massive data parallelism. Spatial domains are usually very large, with from to members today; thus exploiting this data parallelism does lead to massive parallelism.

• As a final example, consider a particular simple formulation of the solution of linear equations, with a dense (few zero elements) matrix A.

Parallelization of this is covered fully in [Fox:88a] and Chapter 8 of this book. Gaussian elimination  (LU decomposition)  for solving Equation 3.7 involves successive steps where in the simplest formulation without pivoting,  at step k one ``eliminates'' a single variable where the index . At each step k, one modifies both and

and , are formed from ,

where one ensures (if no pivoting is employed) that when j>k. Consider the above procedure as a complex system. The spatial domain is formed by the matrix A with a two-dimensional array of values . The time domain is labelled by the index k and so is a discrete space with n (number of rows or columns of A) members. The space is also discrete with members.

Next: 3.4 The Temporal Properties Up: 3 A Methodology for Previous: The Process of

Guy Robinson
Wed Mar 1 10:19:35 EST 1995