Layout of large multistage interconnection networks technical field

• US 5,153,843 A
• Filed: 04/01/1988
• Issued: 10/06/1992
• Est. Priority Date: 04/01/1988
• Status: Expired due to Fees

• Current Assignee: Loral Corporation (Newell Brands Inc.)
• Original Assignee: Loral Corporation (Newell Brands Inc.)
• Inventors: Batcher, Kenneth E.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/176,515
• Time in Patent Office: 1,649 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/124
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A technique for laying out large multistage interconnection networks. The invention provides for the division of a network into sub-networks which may be maintained on printed circuit boards and then provides for the addition of switching circuitry at the inputs or outputs of such boards such that pin locations on the boards may be swapped with each other to allow for a parallel interconnection of corresponding pins between the boards. Such parallel interconnection eliminates the existence of rat'"'"'s nests in the wiring harness.

Claims

1. A method for laying out multistage networks, comprising:

cutting the network between stages thereof to divide the network into subnetworks of a few types;

grouping the sub-networks onto boards;

providing logic control means at inputs and outputs of sub-network stages for reversing the input and outputs thereof, wherein said control means comprises a first control bus for reversing inputs of all elements in a sub-network stage, a second control bus for reversing outputs of all elements in a sub-network stage, and digital switches selectively actuated by the application thereto of a logic 0 to 1.

wiring said first and second buses to logic 0 and 1 values; and

wherein each said board is designated by a unique binary index, each board having pins designated by binary indices, each pin of each board being uniquely connected to a pin of another board by a line having a unique binary index.

2. The method according to claim 1 wherein said network is an m-stage, N-line network, stage i has a key bit position p, stage i+1,..., m are regular and have key bit positions not equal to p, which includes the step of complementing bit position p in all line indices in line sets i, i+1,..., m such that any element in stage i with standard outputs gets reversed outputs, any element in stage i with reversed outputs gets standard outputs, and no effects are caused in the later stages except for the permutation of line indices.

3. The method according to claim 2 wherein stages 1, 2,..., i-1 are regular and have key bit positions not equal to p, including the step of complementing bit position p in all line indices in line-sets 0, 1,..., i-1 such that every element in stage i with standard inputs gets reversed inputs, every element in stage i with reversed inputs gets standard inputs, and no effects are caused in the earlier stages except for permutation of line indices.