Efficient Simulation Algorithms among Processor Arrays with Broadcasting Buses
進 松前 · OUKA (Osaka University Knowledge Archive) (Osaka University) · 2000
The mesh architecture has been studied as one of promising models for parallel computation.Its structure is natural for solving problems in matrix computations and image processing, and is suitable for VLSI implementation.However, since each processor can communicate with only adjacent processors in a single time step, in many cases the time complexity of an algorithm on the mesh is lower-bounded by its large diameter.This is a crucial drawback for a parallel computational model, and as a result, the mesh has been enhanced by the addition of various types of broadcasting capability.In this dissertation, we study in inter-model simulations among several of these enhanced mesh models.Here, we consider the step-by-step simulations; we say that a mesh M can be simulated in T steps on a mesh M' if there exists an algorithm on M' that computes the result of an arbitrary step of M in T steps.From a theoretical point of view, a simulation result between two models is useful to relate the time-complexity classes of computational problems of each models.Also, it may provide a lower-bound or upperbound for a problem on one model if the problem is well studied on the other model.From a practical point of view, a simulation algorithm provides the simulated model as a higher level programming platform for the simulating model.