DocumentCode :
297248
Title :
A merging network scheme that builds large sorting networks
Author :
Law, K. L Eddie ; Leon-Garcia, Alberto
Author_Institution :
Dept. of Electr. & Comput. Eng., Toronto Univ., Ont., Canada
fYear :
1994
fDate :
28 Nov- 2 Dec 1994
Firstpage :
105
Abstract :
We present a new scheme for building large sorting networks. The scheme is recursive in the sense of indicating how to build a large sorting network from modules of smaller sorting and merging networks. The scheme involves a regular wiring pattern between modules. When the scheme is applied to 2×2 comparison elements, we obtain a new sorting network with a wiring pattern that has fewer cross-over points than Batcher´s (1968) networks. When the scheme is applied to modules of a given size, for example 32×32 single-chip sorters, then we obtain a multi-chip implementation of larger sorting networks. Thus the scheme presented allows us to circumvent technology limitations that currently limit the size of sorters that are implementable
Keywords :
VLSI; multichip modules; multistage interconnection networks; network routing; packet switching; switching networks; wiring; Batcher networks; large sorting networks; merging network scheme; modules; multi-chip implementation; packet switching; recursive scheme; regular wiring pattern; single-chip sorters; Buildings; Corporate acquisitions; Delay; Distributed control; Hardware; Merging; Routing; Sorting; Switches; Wiring;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Global Telecommunications Conference, 1994. GLOBECOM '94. Communications: The Global Bridge., IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
0-7803-1820-X
Type :
conf
DOI :
10.1109/GLOCOM.1994.513317
Filename :
513317
Link To Document :
بازگشت