Deterministic routing method for minimal switch circuits
AssigneeIntel Corporation
InventorsJay J. Sturges, Richard P. Vireday
Life of this patent
Estimating the term…
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.
Claims13
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.
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.
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).
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.
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.
Dependencies are inferred from the claim text.