next up previous contents index
Next: 3.8 Parallel Computing Works? Up: 3 A Methodology for Previous: 3.6 Compound Complex Systems

3.7 Mapping Complex Systems


Equation 3.1 first stated our approach to computation as a map between different complex systems. We can quantify this by defining a partial order on complex systems written


Equation 3.17 states that a complex system A can be mapped to complex system B, that is, that B has a more general architecture than A. This was already seen in Figure 3.8 and is given in more detail in Figure 3.12, where we have represented complex systems in a two-dimensional space labelled by their spatial and temporal properties. In this notation, we require:


Figure 3.12: An Illustration of Problem or Computer Architecture Represented in a Two-dimensional Space. The spatial structure only gives a few examples.

The requirement that a particular problem parallelize is that


which is shown in Figure 3.13. We have drawn our space labelled by complex system properties so that the partial ordering of Figures 3.8 and 3.12 ``flows'' towards the origin. Roughly, complex systems get more specialized as one either moves upwards or to the right. We view the three key complex systems, , , and , as points in the space represented in Figures 3.12 and 3.13. Then Figure 3.13 shows that the computer complex system lies below and to the left of those representing and .

Let us consider an example. Suppose (the computer) is a hypercube of dimension with a MIMD temporal structure.  Synchronous, loosely synchronous, or asynchronous problems can be mapped onto this computer as long as the problem's spatial structure is contained in the hypercube topology. Thus, we will successfully map a two-dimensional mesh.  But what about a mesh or irregular lattice? The mesh only has nine (spatial) components and insufficient parallelism to exploit the 64-node computer. The large irregular mesh can be efficiently mapped onto the hypercube as shown in Chapter 12. However, one could support this with a more general computer architecture where hardware or software routing essentially gives the general node-to-node communication shown in the bottom left corner of Figure 3.12. The hypercube work at Caltech and elsewhere always used this strategy in mapping complex spatial topologies; the crystal-router mechanism in CrOS or Express was a powerful and efficient software strategy. Some of the early work using transputers  found difficulties with some spatial structures  since the language Occam  only directly supported process-to-process communication over the physical hardware channels. However, later general Occam subroutine libraries (communication ``harnesses'') callable from FORTRAN or C allowed the general point-to-point (process-to-process) communication model for transputer systems.

Figure: Easy and Hard Mappings of Complex Systems or . We show complex systems for problems and computers in a space labelled by spatial and temporal complex system (computer architectures). Figure 3.12 illustrates possible ordering of these structures.

next up previous contents index
Next: 3.8 Parallel Computing Works? Up: 3 A Methodology for Previous: 3.6 Compound Complex Systems

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