1-1hit |
Hiroshi UMEO Thomas WORSCH Roland VOLLMAR
Mesh-connected computers (MCC's for short) are an important class of physically realizable parallel processors, since many scientific problems can be naturally mapped on them and because their regular structures and simple nearest-neighbour interconnections are particularly suitable for VLSI implementations. In former days iterative arrays and cellular automata were studied and recently special attention has been paid to the study of systolic arrays as a model of parallel computation on VLSI implemented MCC's. These abstract computational models constitute a family of MCC's. In this paper we study the effects of broadcasting bus systems augmented with a mesh-connected computer. First we develop a direct proof technique for the elimination of broadcasting buses. Then, as an application of the technique, we will show that a rich variety of broadcasting bus systems on one- and two-dimensional arrays can be eliminated without any loss of time efficiency. No-time-loss elimination of broadcasting buses on one-dimensional arrays has been shown by a different technique by Ibarra et al., but without our technique, it would be more difficult, but not impossible, to get the same results that we presented newly in this paper.