Simulating a Mesh with Separable Buses by a Mesh with Partitioned Buses

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Susumu Matsumae Articles by Nobuki Tokura

1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99)

Fremantle, Australia

June 23-June 25

ISBN: 0-7695-0231-8

	ASCII Text	x
	Susumu Matsumae, Nobuki Tokura, "Simulating a Mesh with Separable Buses by a Mesh with Partitioned Buses," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 198, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999.

	BibTex	x
	@article{ 10.1109/ISPAN.1999.778939, author = {Susumu Matsumae and Nobuki Tokura}, title = {Simulating a Mesh with Separable Buses by a Mesh with Partitioned Buses}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {1999}, issn = {1087-4089}, pages = {198}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778939}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - Simulating a Mesh with Separable Buses by a Mesh with Partitioned Buses SN - 1087-4089 SP EP A1 - Susumu Matsumae, A1 - Nobuki Tokura, PY - 1999 KW - two-dimensional mesh-connected computer KW - broadcasting KW - mesh with separable buses KW - mesh with partitioned buses KW - simulation algorithm KW - propagation delay VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Susumu Matsumae, Osaka University

Nobuki Tokura, Osaka University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778939

We propose an algorithm that simulates a mesh with separable buses (MSB) by a mesh with partitioned buses (MPB). The MSB and the MPB are the two-dimensional mesh-connected computers which have additional broadcasting buses along every row and column. The broadcasting buses of the MSB can be dynamically sectioned into smaller bus segments of various lengths by the program control, while those of the MPB are statically partitioned in advance by a fixed length. Our algorithm takes Theta(n^{1/3}) steps to simulate the MSB of size n \times n on the MPB of size n \times n, and this time cost is shown to be optimal in the worst case. Furthermore, we discuss the advantage of the MPB, considering the influence of propagation delays of the broadcasting buses.

Index Terms:

two-dimensional mesh-connected computer, broadcasting, mesh with separable buses, mesh with partitioned buses, simulation algorithm, propagation delay

Citation:

Susumu Matsumae, Nobuki Tokura, "Simulating a Mesh with Separable Buses by a Mesh with Partitioned Buses," ispan, pp.198, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.