Broadcast-Bus Elimination without Any Loss of Time Efficiency in Iterative (Cellular or Systolic) Arrays

Hiroshi UMEO; Thomas WORSCH; Roland VOLLMAR

Broadcast-Bus Elimination without Any Loss of Time Efficiency in Iterative (Cellular or Systolic) Arrays

Hiroshi UMEO, Thomas WORSCH, Roland VOLLMAR

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on transactions Vol.E72-E No.5 pp.647-655

Publication Date: 1989/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Computer Systems

Authors

Hiroshi UMEO
Thomas WORSCH
Roland VOLLMAR

Keyword

Cite this

Copy

Hiroshi UMEO, Thomas WORSCH, Roland VOLLMAR, "Broadcast-Bus Elimination without Any Loss of Time Efficiency in Iterative (Cellular or Systolic) Arrays" in IEICE TRANSACTIONS on transactions, vol. E72-E, no. 5, pp. 647-655, May 1989, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e72-e_5_647/_p

Copy

@ARTICLE{e72-e_5_647,
author={Hiroshi UMEO, Thomas WORSCH, Roland VOLLMAR, },
journal={IEICE TRANSACTIONS on transactions},
title={Broadcast-Bus Elimination without Any Loss of Time Efficiency in Iterative (Cellular or Systolic) Arrays},
year={1989},
volume={E72-E},
number={5},
pages={647-655},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Broadcast-Bus Elimination without Any Loss of Time Efficiency in Iterative (Cellular or Systolic) Arrays
T2 - IEICE TRANSACTIONS on transactions
SP - 647
EP - 655
AU - Hiroshi UMEO
AU - Thomas WORSCH
AU - Roland VOLLMAR
PY - 1989
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E72-E
IS - 5
JA - IEICE TRANSACTIONS on transactions
Y1 - May 1989
AB - 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.
ER -