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
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.
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.