Deterministic routing method for minimal switch circuits

• US 5,371,495 A
• Filed: 01/24/1992
• Issued: 12/06/1994
• Est. Priority Date: 01/24/1992
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Sturges, Jay J., Vireday, Richard P.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US07/824,940
• Time in Patent Office: 1,047 Days
• Field of Search: 370/56, 370/94.1, 340/825.03, 340/825.79, 340/825.83, 340/825.85, 340/825.86, 340/825.89, 340/825.9, 340/825.91, 307/112, 307/113, 307/115
• US Class Current: 340/2.29
• CPC Class Codes: H04Q 3/523 Details
• CPC Class Codes: H04Q 3/685 Circuit arrangements therefor

Abstract

A deterministic routing method for switch matrices. The routed matrix receives N input signals and produces M output signals on M output columns. The method of the present invention has three steps. First, each of the M output columns in the switch matrix is searched for each of N separate input signals. Secondly, each of the N inputs is assigned to its located column. If all of the N inputs cannot be assigned to one of the M columns, the set of inputs is shifted and the steps are repeated until all of the N inputs are routed.

Claims

1. A method for routing a set of N inputs taken M output groupings at a time through a switch matrix having R number of input rows of switches and M output columns of switches, said method comprising the steps of:

(a) ordering said set of N inputs into a first order;

(b) selecting one of said N inputs;

(c) locating one of said M output columns coupled to said one of said N inputs;

(d) assigning said one of said M output columns to said one of said N inputs; and

(e) iteratively repeating steps (b), (c), and (d) for the remaining said N inputs until all of said N inputs has been assigned to a unique one of said M output columns, wherein if all of said N inputs cannot be assigned one of said M output columns, then shifting said set of N inputs to produce a second order of said set of N inputs and then repeating steps (b), (c), (d) and (e) using said set of N inputs in the second order until all of said N inputs have been routed.

2. The method defined in claim 1 wherein each said set of N inputs positioned in the first order is shifted one position.

4. The method defined in claim 1 wherein the said set of N inputs positioned in said first order is shifted a predetermined number of positions.

5. The method defined in claim 1 wherein said set of N inputs positioned in said first order is shifted to the left.

3. A method for routing a set of N inputs taken M outputs at a time in a switch matrix having R inputs rows of switches and M output columns of switches, said method comprising the steps of:

(a) ordering said set of N inputs to have an order;

(b) selecting one of said N inputs;

(c) locating one of said M output columns coupled to said one of said N inputs;

(d) assigning said one of said M output columns to said one of said N inputs; and

(e) iteratively repeating steps (b), (c), and (d) for each of the remaining said N inputs until all of said N inputs is assigned to a unique one of said M output columns wherein if all of said N inputs cannot be assigned to one of said M output columns, then shifting the order of said set of N inputs according to a number of cycles of said N inputs that occur throughout said matrix and then repeating steps (b), (c), (d) and (e) until all of said N inputs have been routed.

6. The method defined in claim 3 wherein after said order of N inputs have been cycle-shifted a first predetermined number of times, said set of N inputs is only further shifted by a second predetermined number in order to route said set of N input signals.

7. A method for routing N inputs taken M outputs at a time through a switch matrix having R number of input rows of switches and M output columns of switches, said method comprising the steps of:

(a) ordering said set of N inputs, said step of ordering producing an ordered set of said set of N inputs;

(b) searching each of said M output columns for one of said N inputs;

(c) assigning one of said M output columns to said one of said N inputs;

(d) marking said one of said M output columns as taken; and

(e) repeating steps (a) through (e) for the next of said N inputs in said ordered set and all non-taken ones of M output columns until all of said N inputs in said set have been assigned, wherein if all of said N inputs in said set cannot be assigned to a separate one of said M outputs columns, said method further includes the step of shifting said N inputs in said ordered set in a cyclical manner and then repeating steps (a) through (e).

9. The method defined in claim 7 wherein the order of said N inputs is shifted a predetermined number of positions.

10. The method defined in claim 7 wherein said order is shifted to the left.

11. The method defined in claim 7 wherein said order is logical left rotated one position.

8. A method for routing N inputs taken M outputs at a time through a switch matrix having R number of input rows of switches and M output columns of switches, said method comprising the steps of:

(a) ordering said set of N inputs, said step of ordering producing an ordered set of said set of N inputs;

(b) searching each of said M output columns for one of said N inputs;

(c) assigning one of said M output columns to said one of said N inputs;

(d) marking said one of said M output columns as taken; and

(e) repeating steps (a) through (e) for the next of said N inputs in said ordered set and all non-taken ones of M output columns until all of said N inputs in said set have been assigned, wherein if all of said N inputs in said set cannot be assigned to a separate one of said M output columns said method further includes the step of shifting said N inputs in said ordered set and then repeating steps (a) through (e), wherein the order of said N inputs is shifted according to the number of cycles of said N inputs occur throughout said matrix.

12. The method defined in claim 8 wherein after said order of N inputs have been cycle-shifted a first predetermined number of times, said set of N inputs is only further shifted by a second predetermined number in order to route said set of N input signals.

13. A method for routing a set of N inputs taken to M outputs in a switch matrix having R input rows of switches and M output columns of switches, said method comprising the steps of:

(a) ordering said set of N inputs into an order;

(b) selecting one of said N inputs;

(c) locating one of said M output columns coupled to said one of said N inputs;

(d) assigning said one of said M output columns to said one of said N inputs;

(e) repeating steps (b), (c), and (d) for successive ones of said N inputs until each of said N inputs is assigned to a unique one of said M output columns; and

(f) if step (e) fails, such that each of said N inputs is not assigned to a unique one of said M output columns then;

discarding all previous assignments,

shifting the order of the N inputs a number of positions, and

repeating steps (b) through (f) until each of N inputs has a unique output assigned to it.