Sorting networks having reduced-area layouts

Details Sorting networks having reduced-area layouts Sorting networks having reduced-area layouts

1997-07-08

2000-07-11

Hsu, Alpus H.

Multiplex communications

Pathfinding or routing

Through a circuit switch

370411, 34082579, H04L 1250, H04Q 1100, H04Q 1900

Patent

active

060883537

ABSTRACT:
Improved layouts for sorting networks having O[N log.sup.2 N] comparison circuits, a method therefor, and improved switches incorporating such layouts, are disclosed. An improved layout reduces grid-area requirements for Batcher's bitonic sorting network to an area of 4N.sup.2 grid units. The improved layout results from (i) slanting a substantial portion of each link between comparison circuits 45.degree. with respect to a conventional layout of the network, (ii) incorporating "flip-links," and (iii) not restricting all comparison circuits having the same network depth to placement in a single grid column.

REFERENCES:
patent: 5130976 (1992-07-01), Hickey et al.
patent: 5216420 (1993-06-01), Munter
patent: 5272767 (1993-12-01), Asmuth et al.
patent: 5392279 (1995-02-01), Taniguchi
patent: 5636210 (1997-06-01), Agrawal
patent: 5875190 (1999-02-01), Law
C.D. Thompson, "The VLSI Complexity of Sorting," IEEE Trans. Computers, vol. C32, No. 12, pp. 1171-1184, Dec. 1983.
D.S. Wise, "Compact Layouts of Banyan/FFT Networks,"VLSI Systems and Computations, H.T. Kung et al., (ed.), pp. 186-195 (Computer Science Press, 1981).

Affiliated with

Also associated with

Rating

Sorting networks having reduced-area layouts does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sorting networks having reduced-area layouts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sorting networks having reduced-area layouts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-549293