Grid layouts of switching and sorting networks
AssigneeLucent Technologies Inc.
InventorsShanmugavelayut Muthukrishnan, Suleyman Cenk Sahinalp, Michael S. Paterson
Life of this patent
Estimating the term…
Abstract
A systematic method for creating layouts for various sorting and switching networks on VLSI chips is proposed. These sorting and switching networks include butterfly switching networks, benes networks, odd-even sorting networks, and bitonic sorting networks. The present invention utilizes the existing VLSI grid-model to create various layouts. A rectangular layout is proposed which introduces the use of an additional row to create an area-efficient layout for various switching networks. A diamond layout is proposed which further improves rectangular layout by reducing the number of columns required. A suitable combination of diamond and rectangular layouts is also proposed.
Claims11
A method for determining a layout of a sorting network on a grid model with rows and columns, said method comprising the steps of:
- determining a required number of said rows for said sorting network;
- determining a required number of said columns for said sorting network;
- adding an additional horizontal row to said required number of rows;
- and
- designing a layout for said sorting network between said columns and said rows.
A method of determining a layout of a sorting or switching network having N inputs and N outputs on a grid model of rows and columns, said method comprising the steps of:
- (1) selecting N/L butterflies of size L, where L is a number of inputs and a number of outputs of said butterfly and wherein N/L is a number of butterflies comprising said network, each of said inputs comprising a one-input/two-output selector and each of said outputs comprising a two-input/one-output selector, whereby each butterfly comprises 2L rows;
- (2) for each butterfly, mapping grid point (2i+1, 0) to grid point (2i+1, L+1) via a straight connection, where i is an integer between 0 and L−1;
- (3) for each butterfly, mapping grid point (2i, 0) to grid point (i′+2, L+1) using jogs, wherein i′ is the number obtained by inverting the two most significant bits of i when i is represented as a binary number;
- and
- (4) combining said N/L butterflies to form said network.
Dependencies are inferred from the claim text.