Efficient single-hop interconnection network employing merged shared directional multichannels
First Claim
1. A method for interconnecting m1 groups of m2 first Source Stations (SSs) each said first SS having at least a1 groups of a2 outputs for transmitting message signals to n2 groups of n1 first Destination Stations (DSs) each said first DS having at least b2 groups of b1 inputs for receiving said message signals, such that each said first SS is uniquely connected to every said first DS by a single-hop directional connection whereby up to k3 concurrent non-interfering message signal transmissions can be scheduled from said m2 *m1 =m3 first SSs to said n2 *n1 =n3 first DSs, wherein k3 =k1 *k2, ni >
- ki and mi >
ki, and wherein ki, mi, ni, ai and bi are positive non-zero integers for i=1, 2 or 3, said method comprising the steps of;
(a) composing said interconnection of said first SSs and said first DSs by performing the steps of(a.1) abutting a first plurality of first Shared Directional Multichannels (SDMs) to a second plurality of second SDMs, each said first SDM having a first plurality of coupling stages each having one or more couplers, said each first SDM having capacity for scheduled uniform message signal traffic of up to k1 concurrent signals from m1 second SSs, each said second SS having at least a1 outputs for transmitting said signals to n1 second DSs, each said second DS having at least b1 inputs for receiving said signals, each said second SDM having a second plurality of coupling stages each having one or more couplers, said each second SDM having capacity for scheduled uniform message signal traffic of up to k2 concurrent signals from m2 third SSs, each said third SS having at least a2 outputs for transmitting said signals to n2 third DSs, each said third DS having at least b2 inputs for receiving said signals, wherein said first plurality of first SDMs is at least (n2 *b2) in number and said second plurality of second SDMs is at least (m1 *a1) in number,(a.2) assigning a second SDM index to every said second SDM in said second plurality according to the concatenation (s1, t1) of an index s1 ≦
m1 for one said first SS group and an index t1 ≦
a1 for one said first SS output group, where s1 and t1 are positive non-zero integers and said second SDM index is the concatenation (s1,t1),(a.3) assigning a second output index to every output of each said second SDM having said second SDM index (s1, t1) according to the concatenation (d2, r2) of an index d2 <
n2 for one said third DS and an index r2 <
b2 for one said third DS input, where d2 and r2 are positive non-zero integers and said second output index is the concatenation (s1, t1, d2, r2),(a.4) assigning a first SDM index to every said first SDM in said first plurality according to the concatenation (d2, r2) of an index d2 ≦
n2 for one said first DS group and an index r2 ≦
b2 for one said first DS input group, where d2 and r2 are positive non-zero integers and said first SDM index is the concatenation (d2,r2),(a.5) assigning a first input index to every input of each first SDM having said first SDM index (d2, r2) according to the concatenation (s1, t1) of an index s1 ≦
m1 for one said second SS and an index t1 ≦
a1 for one said second SS output, where s1 and t1 are positive non-zero integers and said first input index is the concatenation (s1, t1, d2, d2), and(a.6) connecting each said output from said second plurality of second SDMs having a second output index (s1,t1,d2,r2) to all said inputs of said first plurality of first SDMs having said first input index (s1, t1, d2, r2).
1 Assignment
0 Petitions
Accused Products
Abstract
A system for the scheduled transmission of signals from source stations to destination stations in a passive, static, Single-Hop Interconnection (SHI) employing a plurality of Shared Directional Multichannels (SDMs) in a power-efficient and cost-effective manner. The system provides a practical implementation of any SHI built from a plurality of smaller SDMs whose salient feature is a significant degree of parallelism at low hardware cost while retaining the simplicity and reliability of a passive interconnection. The system is a scheme for wiring a SHI to retain the useful features of a SDM design for connecting (m) Source Stations each having (a) outputs to (n) Destination Stations each having one input such that, for m=n, the power split losses are reduced to a provably optimal value of (2n/a) and component count reduced to anlog2 (n/a), which is optimal for the optimal power split constraint. A SHI for any number of source and destination stations with any input and output count can be optimally constructed by the method of this invention. The passive efficient SHI of this invention outperforms the conventional passive bus-oriented SHI in channel concurrency with fewer components.
-
Citations
36 Claims
-
1. A method for interconnecting m1 groups of m2 first Source Stations (SSs) each said first SS having at least a1 groups of a2 outputs for transmitting message signals to n2 groups of n1 first Destination Stations (DSs) each said first DS having at least b2 groups of b1 inputs for receiving said message signals, such that each said first SS is uniquely connected to every said first DS by a single-hop directional connection whereby up to k3 concurrent non-interfering message signal transmissions can be scheduled from said m2 *m1 =m3 first SSs to said n2 *n1 =n3 first DSs, wherein k3 =k1 *k2, ni >
- ki and mi >
ki, and wherein ki, mi, ni, ai and bi are positive non-zero integers for i=1, 2 or 3, said method comprising the steps of;(a) composing said interconnection of said first SSs and said first DSs by performing the steps of (a.1) abutting a first plurality of first Shared Directional Multichannels (SDMs) to a second plurality of second SDMs, each said first SDM having a first plurality of coupling stages each having one or more couplers, said each first SDM having capacity for scheduled uniform message signal traffic of up to k1 concurrent signals from m1 second SSs, each said second SS having at least a1 outputs for transmitting said signals to n1 second DSs, each said second DS having at least b1 inputs for receiving said signals, each said second SDM having a second plurality of coupling stages each having one or more couplers, said each second SDM having capacity for scheduled uniform message signal traffic of up to k2 concurrent signals from m2 third SSs, each said third SS having at least a2 outputs for transmitting said signals to n2 third DSs, each said third DS having at least b2 inputs for receiving said signals, wherein said first plurality of first SDMs is at least (n2 *b2) in number and said second plurality of second SDMs is at least (m1 *a1) in number, (a.2) assigning a second SDM index to every said second SDM in said second plurality according to the concatenation (s1, t1) of an index s1 ≦
m1 for one said first SS group and an index t1 ≦
a1 for one said first SS output group, where s1 and t1 are positive non-zero integers and said second SDM index is the concatenation (s1,t1),(a.3) assigning a second output index to every output of each said second SDM having said second SDM index (s1, t1) according to the concatenation (d2, r2) of an index d2 <
n2 for one said third DS and an index r2 <
b2 for one said third DS input, where d2 and r2 are positive non-zero integers and said second output index is the concatenation (s1, t1, d2, r2),(a.4) assigning a first SDM index to every said first SDM in said first plurality according to the concatenation (d2, r2) of an index d2 ≦
n2 for one said first DS group and an index r2 ≦
b2 for one said first DS input group, where d2 and r2 are positive non-zero integers and said first SDM index is the concatenation (d2,r2),(a.5) assigning a first input index to every input of each first SDM having said first SDM index (d2, r2) according to the concatenation (s1, t1) of an index s1 ≦
m1 for one said second SS and an index t1 ≦
a1 for one said second SS output, where s1 and t1 are positive non-zero integers and said first input index is the concatenation (s1, t1, d2, d2), and(a.6) connecting each said output from said second plurality of second SDMs having a second output index (s1,t1,d2,r2) to all said inputs of said first plurality of first SDMs having said first input index (s1, t1, d2, r2). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
- ki and mi >
-
12. A method for reducing the power spreading loss in a passive interconnection of m1 groups of m2 first SSs, each said first SS having at least a1 groups of a2 outputs for transmitting up to k3 concurrent non-interfering message signals to n2 groups of n1 first DSs, each said first DS having at least b2 groups of b1 inputs for receiving said message signals, said passive interconnection having a first plurality of first SDMs and a second plurality of second SDMs, each said first SDM having c1 coupling stages and a uniform scheduled concurrent non-interfering message signal capacity of k1, each said second SDM having c2 coupling stages and a uniform scheduled concurrent non-interfering message signal capacity of k2, each said coupling stage having one or more couplers, where k3 =k1 *k2 and k1, k2, c1 and c2 are all positive non-zero integers, said method comprising the steps of:
-
(a) replacing said (c1 +c2) coupling stages with c3 ≦
(c1 +c2) new coupling stages, each said new coupling stage having a plurality of substantially balanced couplers; and(b) connecting the inputs and outputs of said new coupling stages such that each said first SS is connected to every said first DS in accordance with the connections made by said passive interconnection, thereby compacting said passive interconnection of said first SSs and said first DSs to reduce power spreading loss and component count. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
18. A shared directional multichannel system for scheduled uniformed message signal traffic of up to (k) concurrent non-interfering message signal transmissions, wherein k, m, n, a, b and c are positive non-zero integers, c= loga n , and m≧
- k≧
(c choose (a-1))=c!/(a-1)!/(c-a+1)!, said system comprising;a first plurality of source stations (SSs), each said SS including a second plurality (a) of transmitter outputs, wherein said first plurality is less than or equal to (m); a third plurality (n) of destination stations (DSs), each said DS including a fourth plurality (b) of receiver inputs; and interconnection means for passively coupling signals from each said SS to every said DS such that the power received at each said receiver input is greater than a/n2 times the power transmitted from said transmitter outputs connected to said each receiver input. - View Dependent Claims (19, 20, 21)
- k≧
-
22. A method for reducing the power spreading loss in a passive interconnection of m1 groups of m2 first SSs, each said first SS having at least a1 groups of a2 outputs for transmitting up to k3 concurrent non-interfering message signals to n2 groups of n1 first DSs, each said first DS having at least b2 groups of b1 inputs for receiving said message signals, said passive interconnection having a first plurality of first SDMs and a second plurality of second SDMs, each said first SDM having c1 coupling stages and a uniform scheduled concurrent non-interfering message signal capacity of k1, each said second SDM having c2 coupling stages and a uniform scheduled concurrent non-interfering message signal capacity of k2, each said coupling stage having one or more couplers, where k3 =k1 *k2 and k1, k2, c1 and c2 are all positive non-zero integers, said method comprising the steps of:
-
(a) evaluating the coupler fan-in and fan-out within each of said (c1 +c2) coupling stages to determine where said coupler fan-in and fan-out must be changed to make said coupler fan-in substantially equal to said coupler fan-out in said each coupling stage; (b) responsive to the results of said evaluating step, performing at least one of the following (b.1), (b.2) or (b.3) replacing steps of; (b.1) replacing one or more said coupling stages with one or more first new coupling stages, said first new coupling stages each having a plurality of first new couplers specified in accordance with the steps of (b.1.1) increasing the out-degree of each said coupler in a first said coupling stage by a first factor, (b.1.2) decreasing the out-degree of each said coupler in a second said coupling stage by said first factor, and (b.1.3) increasing the number of said couplers in said second coupling stage, where said second coupling stage is disposed on the output side of said first coupling stage, (b.2) replacing one or more said coupling stages with one or more second new coupling stages, said second new coupling stages each having a plurality of second new couplers specified in accordance with the steps of (b.2.1) decreasing the in-degree of each said coupler in a third said coupling stage by a second factor (b.2.2) increasing the in-degree of each said coupler in a fourth said coupling stage by said second factor, and (b.2.3) increasing the number of said couplers in said third coupling stage, where said third coupling stage is disposed on the input side of said fourth coupling stage, and (b.3) replacing a pair of two adjacent said coupling stages with a single coupling stage having a plurality of couplers with in-degree and out-degree specified in accordance with the coupler in-degree for one said adjacent coupling stage and the coupler out-degree for the other said adjacent coupling stage, where each said coupler in said one adjacent coupling stage is connected to no more than one said coupler in said other adjacent coupling stage; and (c) repeating said evaluating step (a) and said replacing step (b) successively until said coupler in-degree and out-degree are substantially balanced in each remaining said coupling stage.
-
-
23. A method for reducing the power spreading loss in a passive interconnection for transmitting a plurality of concurrent non-interfering message signals from a set of Source Stations (SSs) to a set of Destination Stations (DSs), said passive interconnection having a first plurality of coupling stages each having one or more couplers, each said coupler having one or more inputs and one or more outputs, wherein said coupler inputs of the ith said coupling stage are connected passively to said coupler outputs of the (i-1)th said coupling stage and said coupler outputs of said ith coupling stage are connected passively to said coupler inputs of the (i+1)th said coupling stage, where i<
- j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;
(a) replacing said first plurality of coupling stages with a second plurality of new coupling stages, said second plurality being less than or equal to said first plurality, each said new coupling stage having a plurality of substantially balanced couplers; and (b) connecting said inputs and said outputs of each said new coupling stage such that said set of SSs is interconnected with said set of DSs in accordance with said passive interconnection, thereby compacting said passive interconnection of said set of SSs and said set of DSs to reduce power spreading loss and component count. - View Dependent Claims (24, 25, 26, 27, 28)
- j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;
-
29. A method for reducing the power spreading loss in a passive interconnection for transmitting a plurality of concurrent non-interfering message signals from a set of Source Stations (SSs) to a set of Destination Stations (DSs), said passive interconnection having a first plurality of coupling stages each having one or more couplers, each said coupler having one or more inputs and one or more outputs, wherein said coupler inputs of the ith said coupling stage are connected passively to said coupler
outputs of the (i-1)th said coupling stage and said coupler outputs of said ith coupling stage are connected passively to said coupler inputs of the (i+1)th said coupling stage, where i< - j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;
(a) evaluating the coupler fan-in and fan-out within each of said first plurality of coupling stages to determine where said coupler fan-in and fan-out must be changed to make said coupler fan-in substantially equal to said coupler fan-out in said each coupling stage; (b) responsive to the results of said evaluating step, performing at least one of the following (b.1), (b.2) or (b.3) replacing steps of; (b.1) replacing one or more said coupling stages with one or more first new coupling stages, said first new coupling stages each having a plurality of first new couplers specified in accordance with the steps of (b.1.1) increasing the out-degree of each said coupler in said ith coupling stage by a first factor, (b.1.2) decreasing the out-degree of each said coupler in said jth coupling stage by said first factor, and (b.1.3) increasing the number of said couplers in said jth coupling stage, (b.2) replacing one or more said coupling stages with one or more second new coupling stages, said second new coupling stages each having a plurality of second new couplers specified in accordance with the steps of (b.2.1) decreasing the in-degree of each said coupler in said ith coupling stage by a second factor (b.2.2) increasing the in-degree of each said coupler in said jth coupling stage by said second factor, and (b.2.3) increasing the number of said couplers in said ith coupling stage, and (b.3) replacing a pair of two adjacent said coupling stages with a single coupling stage having a plurality of couplers with in-degree and out-degree specified in accordance with the coupler in-degree for one said adjacent coupling stage and the coupler out-degree for the other said adjacent coupling stage, where each said coupler in said one adjacent coupling stage is connected to no more than one said coupler in said other adjacent coupling stage; and (c) repeating said evaluating step (a) and said replacing step (b) successively until said coupler in-degree and out-degree are substantially balanced in each remaining said coupling stage.
- j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;
-
30. A method for reducing the number of switching elements in a switched interconnection for transmitting a plurality of non-interfering message signals from a set of Source Stations (SSs) to a set of Destination Stations (DSs), said switched interconnection having a first plurality of switching stages each having one or more switches, each said switch having one or more inputs and one or more outputs, wherein the inputs of the ith said switching stage are connected passively to the outputs of (i-1)th said switching stage and the outputs of said ith switching stage are connected passively to the inputs of the (i+1)th said switching stage, where i<
- j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;
(a) replacing said first plurality of switching stages with a second plurality of new switching stages, said second plurality being less than or equal to said first plurality, each said new switching stage having a plurality of substantially balanced switches; and (b) connecting said inputs and said outputs of each said new switching stage such that said set of SSs is interconnected with said set of DSs in accordance with said passive interconnection, thereby compacting said passive interconnection of said set of SSs and said set of DSs to reduce component count. - View Dependent Claims (31, 32, 33, 34, 35)
- j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;
-
36. A method for reducing the number of switching elements in a switched interconnection for transmitting a plurality of non-interfering message signals from a set of Source Stations (SSs) to a set of Destination Stations (DSs), said switched interconnection having a first plurality of switching stages each having one or more switches, each said switch having one or more inputs and one or more outputs, wherein the inputs of the ith said switching stage are connected passively to the outputs of (i-1)th said switching stage and the outputs of said ith switching stage are connected passively to the inputs of the (i+1)th said switching stage, where i<
- j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;
(a) evaluating the switch fan-in and fan-out within each said switching stage to determine which of said switch fan-in and fan-out must be increased to make said switch fan-in substantially equal to said switch fan-out for said each switching stage; (b) responsive to the results of said evaluating step, performing at least one of the following (b.1), (b.2) or (b.3) replacing steps of; (b.1) replacing one or more said switching stages with one or more first new switching stages, said first new switching stages each having a plurality of switches specified in accordance with the steps of (b.1.1) increasing the out-degree of each said switch in said ith switching stage by a first factor, (b.1.2) decreasing the out-degree of each said switch in said jth switching stage by said first factor, and (b.1.3) increasing the number of said switches in said jth switching stage, (b.2) replacing one or more said switching stages with one or more second new switching stages, said second new switching stages each having a plurality of switches specified in accordance with the steps of (b.2.1) decreasing the in-degree of each said switch in said ith switching stage by a second factor, (b.2.2) increasing the in-degree of each said switch in said jth switching stage by said second factor, and (b.2.3) increasing the number of said switches in said ith switching stage, and (b.3) replacing a pair of two adjacent said switching stages with a single switching stage having a plurality of switches with in-degree and out-degree specified in accordance with the switch in-degree for one said adjacent switching stage and the switch out-degree for the other said adjacent switching stage, where each said switch in said one adjacent switching stage is connected to no more than one said switch in said other adjacent switching stage; and (c) repeating said evaluating step (a) and said replacing step (b) successively until said switch in-degree and out-degree are substantially balanced in each remaining said switching stage.
- j are non-zero positive integers less than or equal to said first plurality, said method comprising the steps of;
Specification