A parallel algorithm for embedding large pyramids into smaller hypercubes with load balancing

Taipei, Taiwan December 18-December 20

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/ISPAN.1997.645097

1997 International Symposium on Paral ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	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 Y.W. Chen Articles by K.L. Chung

	ASCII Text	x
	Y.W. Chen, K.L. Chung, "A parallel algorithm for embedding large pyramids into smaller hypercubes with load balancing," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 215, 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), 1997.

	BibTex	x
	@article{ 10.1109/ISPAN.1997.645097, author = {Y.W. Chen and K.L. Chung}, title = {A parallel algorithm for embedding large pyramids into smaller hypercubes with load balancing}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {1997}, issn = {1087-4089}, pages = {215}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1997.645097}, 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 - A parallel algorithm for embedding large pyramids into smaller hypercubes with load balancing SN - 1087-4089 SP EP A1 - Y.W. Chen, A1 - K.L. Chung, PY - 1997 KW - parallel algorithms; parallel algorithm; large pyramids; small hypercubes; load balancing; k-dimensional hypercube; dilation; congestion VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Y.W. Chen, Dept. of Inf. Manage., Nat. Taiwan Univ. of Sci. & Technol., Taipei, Taiwan

K.L. Chung, Dept. of Inf. Manage., Nat. Taiwan Univ. of Sci. & Technol., Taipei, Taiwan

Consider a pyramid with n levels and a k-dimensional hypercube, 0/spl les/k/spl les/2n-2. The paper presents a parallel algorithm for embedding large pyramids into smaller hypercubes with load balancing. With dilation 4, congestion at most 2/sup n-k/2/+4, and load [2/sup 2n-k//3] when k is even, our algorithm embeds the pyramid into the hypercube, otherwise, with the same dilation and load, it has congestion 2/sup n-(k+1)///sup 2+1/+6 when k is odd. The algorithm can be performed in O(k)-bit time.

Index Terms:

parallel algorithms; parallel algorithm; large pyramids; small hypercubes; load balancing; k-dimensional hypercube; dilation; congestion

Citation:

Y.W. Chen, K.L. Chung, "A parallel algorithm for embedding large pyramids into smaller hypercubes with load balancing," ispan, pp.215, 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), 1997

Peer Review Notice | Give Us Feedback

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