A bitonic sorting network with simpler flip interconnections

	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 Jae-Dong Lee Articles by K.E. Batcher

1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96)

Beijing, CHINA

June 12-June 14

ISBN: 0-8186-7460-1

	ASCII Text	x
	Jae-Dong Lee, K.E. Batcher, "A bitonic sorting network with simpler flip interconnections," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 104, 1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96), 1996.

	BibTex	x
	@article{ 10.1109/ISPAN.1996.508968, author = {Jae-Dong Lee and K.E. Batcher}, title = {A bitonic sorting network with simpler flip interconnections}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {1996}, issn = {1087-4089}, pages = {104}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1996.508968}, 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 bitonic sorting network with simpler flip interconnections SN - 1087-4089 SP EP A1 - Jae-Dong Lee, A1 - K.E. Batcher, PY - 1996 KW - sorting; multiprocessor interconnection networks; parallel architectures; parallel algorithms; flip interconnections; bitonic sorting network; inter-level wiring; parity technique; Construct-BSMF; N/2 even-parity keys; interconnection scheme; perfect-shuffle interconnection VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Jae-Dong Lee, Dept. of Math. & Comput. Sci., Kent State Univ., OH, USA

K.E. Batcher, Dept. of Math. & Comput. Sci., Kent State Univ., OH, USA

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

This paper presents the new scheme of interconnecting levels in a bitonic sorting network with simpler inter-level wiring. A parity technique which leads to the algorithm Construct-BSMF is introduced. Wiring simplification through the network is achieved wiring the N/2 even-parity keys straight through the network. N/2 odd-parity keys use flip interconnections. As a result, our interconnection scheme simplifies the inter-level wiring through the network and outperforms the perfect-shuffle interconnection scheme both in terms of cost and delay.

Index Terms:

sorting; multiprocessor interconnection networks; parallel architectures; parallel algorithms; flip interconnections; bitonic sorting network; inter-level wiring; parity technique; Construct-BSMF; N/2 even-parity keys; interconnection scheme; perfect-shuffle interconnection

Citation:

Jae-Dong Lee, K.E. Batcher, "A bitonic sorting network with simpler flip interconnections," ispan, pp.104, 1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96), 1996

Peer Review Notice | Give Us Feedback

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