Grid layouts of switching and sorting networks

Details Grid layouts of switching and sorting networks Grid layouts of switching and sorting networks

1998-06-15

2001-02-06

Olms, Douglas W. (Department: 2732)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S389000, C370S394000, C370S397000

Reexamination Certificate

active

06185220

ABSTRACT:

This patent application contains an appendix (Appendix A) consisting of 18 pages, titled Improved Grid Layouts of Switching and Sorting Networks. Appendix A is an unpublished article written by the inventors of the present invention. The article comprises the results of the various experiments conducted by the inventors according to the principles of the current invention. The article also comprises various experimental techniques used by the inventors to conduct these experiments.
The enclosed article, attached as an Appendix A, is an expression of the embodiments included in this patent application. However, the information and the language of the article should not be construed as limiting the scope of the claims.
FIELD OF THE INVENTION
This invention generally relates to switching and sorting networks: including butterfly, benes network, odd-even sorter, and bitonic sorter. In particular, the invention relates to the layout of these switching and sorting networks on Very Large Scale Integrated (VLSI) chips.
BACKGROUND OF THE INVENTION
Sorting and switching networks are widely used as interconnection networks in telecommunications, parallel computing, and distributed computing.
There is a renewed interest in these networks in Asynchronous Transfer Mode (ATM) technology. ATM switches are commonly used in telecommunication networks to switch voice, data, and video. ATM switches deploy various sorting and switching networks to receive incoming packets and sort them according to destination.
In a typical ATM switch, these sorting and switching networks are systematically laid on a VLSI chip. However, the layouts of these sorting networks on VLSI chips have always been a problem. The sorting networks have connections which are angled in three dimensional space; wherein VLSI chips use a two dimensional grid-model comprising only horizontal rows and vertical columns. In this grid-model, various sorters and other network nodes are mapped to a subset of grid points, and the connections between the nodes are selected using the edge-disjoint wiring along grid rows and grid columns.
Therefore, there exists a need for an improved systematic method for laying out these sorting networks on VLSI chips. The goal is to produce an area-efficient layout. The production cost of a VLSI chip grows with the total area of its layout, and it is desirable to produce a layout of sorting networks on VLSI chips as compactly as possible.
SUMMARY OF THE INVENTION
The present invention provides a systematic method for creating layouts for various sorting and switching networks. These sorting and switching networks include butterfly switching networks, benes networks, odd-even sorting networks, and bitonic sorting networks.
The present invention utilizes the prior-art grid-model of VLSI chips. This grid-model comprises horizontal rows and vertical columns.
Two different layout schemes, termed rectangular and diamond, are proposed. The rectangular layout involves use of existing rows in an economical manner as well as use of one additional row. The diamond layout utilizes the columns efficiently and produces a layout comprising successive levels. The present invention also provides a layout comprising a suitable combination of the rectangular and diamond layouts.
In the preferred embodiment, a suitable rectangular layout for a single butterfly is proposed. In the alternative embodiments, suitable layouts for complete butterfly switching networks, odd-even sorting networks, and bitonic sorting networks are proposed.


REFERENCES:
patent: 4905224 (1990-02-01), Lobjinski et al.
patent: 5216420 (1993-06-01), Manter
patent: 6018523 (2000-01-01), Even
patent: 6021131 (2000-02-01), Even
“Improved Grid Layouts of Switching and Sorting Networks”, S. Muthukrishnan, M. Paterson, and S. Sahinalp, 18 pages, unpublished.

Affiliated with

Also associated with

Rating

Grid layouts of switching and sorting networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Grid layouts of switching and sorting networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Grid layouts of switching and sorting networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2581316