| n the design of parallel algorithms, it is always assumed that the abstract network can have as many processors as needed in order to achieve the optimum performance. However, existing networks not only may contain much fewer processors but also have totally different communication links. Therefore, the problem of simulating the abstractly designed algorithms by the physical parallel architectures is a very important task.;Simulation is described by a many-to-one mapping of the processors in guest network into the processors in host network. Each processor in host network simulates the operations of at least one processor in guest network.;Among all parallel machines,the mesh and torus are two major architecture which have been used for parallel computation, image processing, computer vision, numerical analysis, and graph algorithm problems. We examine here techniques for simulation, or embedding, of these two machines.;There are two common measurements concerning the quality of a particular embedding. The first is the load factor, i.e. the maximum number of guest processors that each host processor host. We want to achieve an embedding with load factor as close to the optimum load factor as possible, (i.e. the ceiling of the number of processors in guest network divided by the number of processors in host network), thus the workload of each processor in host network is divided evenly and idle time is minimized. The second is dilation which is a measurement of how much the guest network's edges are stretched. Apparently, with smaller dilation, the communication time can be reduced.;We first develop the techniques for embedding 2-dimensional networks, namely, grouping, shuffling, circular arrangement & shifting, and bending. Then, the techniques are generalized for multi-dimensional embedding. In general, we can have an embedding with optimum load factor and optimum, or near optimum, dilation.;In addition, we can embed any d-dimensional mesh or torus into its optimal hyper-cube with dilation at most... |
