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 equationwhere 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 andand , 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.

Wed Mar 1 10:19:35 EST 1995