JPS63301645A - Self-routing channel - Google Patents

Abstract

PURPOSE:To obtain an LSI and a high speed-action by wiring a signal line to connect between elements in respective channel steps and even a signal line to connect between the channel steps in a shortest distance and erasing a confounding between wirings. CONSTITUTION:Out of the elements of respective channel steps l1-lm, a pair of input line and output line are connected to the elements of a prescribed number, however, only one output line is respectively connected to the remained elements. Between the mutual elements, they are not turned from a first element to an n-th element but cascade connected in a single direction and the output line of the channel step lm of a terminal step is outputted to an outgoing line by obtaining a logical OR per two stripes separated with a (n) stripe only. Thus, an element which is a minimum unit can be arranged in a lattice shape and even with a signal line to connect between the elements in the respective channel steps and a signal line to connect between the channel steps, a wiring can be executed in a shortest distance. Since there is no confounding between the wirings, this constitution is optimum to an arrangement and a wiring in an LSI and a high speed-action can be attained without the limit of a wiring length.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a self-routing communication path, and more particularly, to an ink connection network used for communication between processors of a computer, a communication path used for high-speed packet switching, etc. The present invention relates to a hardware-based, distributed-controlled, self-routing channel suitable for.

[Conventional technology]

Conventionally, in centralized control communication paths used in digital exchanges, etc., routing control is concentrated in one place and processed by software, so the larger the communication path, the more complex the routing control becomes. As a result, speeding up of processing has been limited. In this way 1. In the control system of the phono-Neumann computer, which performs switching control and other controls using stored programs, the control speed rapidly decreases as the amount of processing increases.

In order to eliminate such phono-Neumann-type bottlenecks and realize high-speed control and large-capacity communication paths, self-routing communication paths based on distributed control using hardware have been actively researched in recent years. (For example, "Self-routing channel configuration" written by Fukaya and Imai, 8-174 of the General Conference of the Institute of Electronics, Information and Telecommunications Engineers (published in 1986))
reference).

FIG. 2 is a block diagram showing an example of a conventional self-routing communication path.

In FIG. 2, 21. ...21. ...2m is a communication line, I N,, I N, ... I
Nn is the incoming line, OUT,, OUT,, --...0UTn
is the outgoing line, I' 1yLIIJi*z...L L+
xp Li+z... are the output lines of each stage, L(
, -021,...L(m-J+□,... are all input lines of each stage.

The i-th (1≦im) stage has n input lines (
L(, -x), t-L(, -x), n) and n output lines (Liti~L, , n) are connected. In addition, in each stage i, there are a total of n elements (2i 1
, 2 i 2° . . . 2 inches), each having one pair of input lines and one pair of output lines connected to each other. Further, each element is connected in a circular manner in a single direction.

That is, element 2i1→2i2→・・・・・・2
They are connected sequentially like in→2i1.

Note that each of the elements 2i1 to 2in has a built-in flip-flop and a gate, and has a switching connection function.

Next, the operation shown in FIG. 2 will be explained in detail.

First, each incoming line (IN,,IN,...IN
n) contains header information (■()) indicating the difference between the outgoing line position (0) where communication information should be output and its incoming line position (I).
Communication information including the information is input. Note that the header information is expressed by a linear equation.

H=(O-I) mod n... (1) Here, the symbol mod indicates a modulo function. That is, .

The operation of the first stage communication path stage 21 is as follows.

Each element (211 to 2 inches) is the header information input from the input line, from the highest (or lowest) to ((
i-1) Based on the partial bit string Si consisting of t bits from the t+1)th bit to the (it)th bit, the communication information input from the input line is transmitted between elements connected in a unidirectional manner in a cyclic manner. S,・2kit(or,S,・2(
After moving by i−+)t), the output line (Li
s1 to L1-n).

This operation is the same for the first to m-th communication path stages, and movement between elements and movement between communication path stages are all performed synchronously.

As a result, the communication information input from the incoming line is transmitted through a self-routing communication path consisting of the first to mth communication path stages based on the header information indicating the difference between the outgoing line position and the incoming line position. The output position is moved by , and the signal is output to the target outgoing line (OUT□, ○UT2゜...0UTn).

Using such a conventional self-routing channel, each element (211 to 2 inches) is required to perform a connection that outputs communication information input from an incoming line to all outgoing lines, that is, a broadcast type connection operation. moves the communication information input from the input line by (2t-1)2k-'' between elements, and also moves the communication information input from the input line by (2x-1)2k-Lt (however, 0≦
The above communication information may be branched and output for each movement (x≦x).

[Problem that the invention seeks to solve]

As mentioned above, conventional self-routing channels.

This is a non-blocking communication path in which communication information input to any incoming line is output to any outgoing line without colliding with each other within one communication path. Also, the number of elements is small as nQog□n for the number of input/output lines n.
It also has the advantage of easy routing control. However, when attempting to realize this self-routing communication path using LSI, the signal line from the lowest element to the highest element in each communication path stage becomes larger as the switch size increases, and the wiring length increases. There is a problem in that the operating speed of the communication path is limited.

The purpose of the present invention is to solve such conventional problems and to
To provide a self-routing communication path that can be arranged and wired appropriately for I, is not limited by signal wiring length, and can operate at high speed.

[Means for solving problems]

In order to achieve the above object, the self-routing communication path of the present invention has n (= 2k, k is a natural number) incoming lines and 0
Based on header information consisting of routing control information indicating the difference between the outgoing line position where the communication information input from the incoming line is to be output and the incoming line position, the communication information is transferred to the target line. m output to the outgoing line (=k / t
) (k p t is a natural number) In a self-routing channel equipped with (k p t is a natural number) stages, ■Each i-th (1≦i≦m) channel stage is as follows: Xi=
2 n -n 2-('-1' (or = n +2
('-1)' -1) input lines and y1=2n-n2"
(or = n12"-1) output lines, and has y elements, and X elements are each connected to a pair of input and output lines. , only one output line is connected to each of the remaining (yi-xi) elements, and the lines between the 1st to yth,
The elements are cascaded in a single direction up to ((i-1
)t+1) bit to (it) bit, the communication information inputted from the input line is converted into Si·2k-it (or Sl·2(i- +) t) "After moving between the above elements, output to the next stage of the communication line, ■The output line of the m-th communication line is the logical OR of the two lines with only 0 wires, The feature is that it is output to the outgoing line.

Further, the self-routing communication path of the present invention is a self-routing system equipped with m communication path stages for outputting communication information to a target outgoing line or for outputting communication information input from an incoming line to all outgoing lines. In the communication path, when the broadcast control information has a logical value of 10', each element transmits the communication information input from the input line to S based on the partial bit string SL.
After being moved between elements by i・2 k-1t, it is output to the next communication path stage, and when the broadcast control information has a logical value of '1', the communication information input from the input line is transferred to (2'-1).
)・2k-it is moved between elements, and the communication information is branched and outputted to the next communication path stage every time (2x-1)・2k-1t is moved.

[For production]

In the present invention, a pair of input lines and output lines are connected to a predetermined number of elements of each channel stage.
Only one output line is connected to each of the remaining elements, and the elements are cascaded in a single direction without going around from the first to the nth element, and the output line of the final channel stage The lines are outputted to the outgoing line by performing the logical sum of two lines separated by n lines.

This makes it possible to arrange the elements, which are the smallest units, in a grid pattern, and also to wire the signal lines that connect between elements in each channel membrane and the signal lines that connect between channels of channels with the shortest possible distance. Moreover, since there is no interlacing between wires, it is optimal for placement and wiring in LSI, and high-speed operation is possible without being limited by wire length.

In addition, in the second embodiment, the self-routing communication path is capable of outputting communication information input from an incoming line to all outgoing lines, and the header information includes broadcast control information. When is '0', each element is moved by the same distance as in the first embodiment, and the broadcast control information is '1'.
', regardless of the bit string S, (2t-1)
It is moved between elements by 2k-it, sequentially branched into two, and connected to all output lines at the last speech path stage. This enables broadcast-type connections.

〔Example〕

FIG. 1 is a block diagram of a self-routing channel showing a first embodiment of the present invention.

In FIG. 1, 11, yi. ...li,...
...1m is the communication path, IN, IN,...IN
n is the incoming line, OUT□, 0UT2. ...0UT
n is the outgoing line.

For the first stage (1≦1≦m), x1=2 n
−n 2””−1)t (or x, = n+ 2
(i-t) t-1) human force line (L(i-1>l~L
(t-z)+xi) and yi=2n-n2it (or yyo=n+21t-1) output lines (L,...~Li
+yi) is connected.

Also, y1 elements (111, 1yi1...
・1 i
i) and the output line (Li, 1 to LiyX□) are connected, and the remaining (y knee
1) to 1iyi) each have one output line (Li+
Xi+1 to Li+/E) are connected. Also the first
yi-th element 1 from the th element lil
iy are cascaded in a single direction.

Furthermore, the output lines of the final m-th stage are connected between two output lines separated by n lines (for example, L, , □, Il).

50. ...L, 1-4 and LIltym*In addition, yl
a=2n-1) is a logical sum circuit (21,...2(n-
1), 2n), and its output line is the output line (OUT
□, OUT, ...0UTn).

Next, the operation will be explained in detail.

First, as in the conventional example shown in Fig. 2, each incoming line (IN□, I
N, ...INn) is input with communication information including header information (H) indicating the difference between the outgoing line position (0) to which the communication information should be output and its incoming line position (I). . Note that the header information is expressed by the following formula.

H= (0-I)mOd n ・ ・ ・ ・ ・
- (2) Here, the symbol mod indicates a modulo function. The operation of the first stage communication path stage 11 is as follows.

Each element (111 to lix) is from the highest (or lowest) of the header information input from the input line,
Communication information input from the input line is cascaded in a single direction based on a partial bit string Si consisting of t bits from the ((i −1)t + 1))th bit to the (it)th bit. After moving Si・211 t (or Si・2(1-z)t) between the elements reached at the end, the output lines (List to Li .

yi).

As a result of the above, when there is a relationship of 0≧■ between the incoming line position (I) and the outgoing line position (0), the position of the m-th stage output line and the target outgoing line position match, but 0 ■When
The output position of the m-th stage where communication information is output is a position n away from the target output line position. For this reason,
The output lines of the final m-th stage are two output lines separated by n lines. For example, LIll, 1, , n+, ""
” ' ”L@an-8 and L□ym) (Here, ym
= 2n-1) is a logical sum circuit (21°...2 (n-1
), 2n), and their output lines are output lines (O
UT□, OUT, ...0UTn).

Note that the OR circuits (21, . . . 2n) do not cause their output signals to be fed back to the input lines of each channel, so they do not become a factor that limits the operating speed of one channel. Due to the repeatability of the wiring, phase matching of signals can be easily performed by matching the wiring lengths to the OR circuits (21, . . . 2n).

Next, a second embodiment of the present invention will be described using FIG.

In the second example, x1=2 n −n 2−
('-t) t, y, =2 n n 2
-Lt, and instructs to output the communication information input from the incoming line to all outgoing lines, along with routing control information indicating the difference between the outgoing line position where the communication information input from the incoming line should be output and its incoming line position. Each element operates as follows based on header information consisting of broadcast control information.

Each element (21,...2n) has a logical value (when the broadcast control information is Ol, the ((i-1)t+1)th bit to (it) from the most significant bit in the header information.
Based on the partial bit string Si consisting of t bits of the bit-th bit, the communication information input from the input line is
・After moving between the elements by 2k-11,
When the broadcast control information has a logical value of '1', the communication information input from the input line is transmitted between the elements by (2t-1)·2k-11. While moving, (2”-1)・2 k-
Every time it moves by 1t (0≦x≦t), the communication information is branched and output to the next communication path stage. The other operations are the same as those in the first embodiment, so their explanation will be omitted.

〔Effect of the invention〕

As explained above, according to the present invention, even if communication information input to any incoming line is sent out to any outgoing line, communication information does not collide with each other within the communication path, that is, non-blocking communication is possible. In addition, the number of elements may be as small as nQog2n for the number of input/output lines n.

Furthermore, routing control is simple. In addition, it is possible to arrange elements, which are the smallest units, in a grid pattern.
It is most suitable for placement and wiring in LSI because it can be wired with the shortest distance between the signal lines connecting elements in each communication path membrane and the signal lines connecting between the communication path sections, and there is no confounding between the wirings. It is possible to realize a self-routing channel that is not limited by wiring length and can operate at high speed. Furthermore, one-on-one
In addition to this type of connection, broadcast type connections are also possible.

[Brief explanation of drawings]

FIG. 1 is a configuration diagram of a self-routing communication path showing an embodiment of the present invention, and FIG. 2 is a configuration diagram of a conventional self-routing communication path. 111,...1yi. ...1ixi, 1iyi: element, 11. ...11. ...1m: communication road,
IN,, IN2. ...-INn: Incoming line, OU
T,,○UT2.・---○UTn: Outgoing line, 21゜2
2,...2 (n-1), 2n: OR circuit, L(□-0)1, ~L(i-1)l X□Input line to two-channel stage 1j, Li+, ""'Li+Xi+
Li+yi: Output line from communication line stage 11.

Claims (2)

[Claims] (1) Accommodates n (=2^k, k is a natural number) incoming lines and n outgoing lines, and identifies the outgoing line position where communication information input from the incoming line should be output and the incoming line position. m (=k/t) (k, t
[1] In a self-routing channel equipped with (a natural number) stages, each i-th (1≦i≦m) channel stage is x_i=2n−n2＾−＾(＾i＾−＾ 1^)
^t (or = n+2^(^i^-^1^)^t-1)
It accommodates input lines of books and output lines of y_i=2n-n2^-^i^t (or = n+2^i^t-1), and
It has __i elements, among which x_i
A pair of input and output lines is connected to each element, and only one output line is connected to each of the remaining (y_i-X_i) elements. cascade-connected in a single direction until Based on the partial bit string S_i,
The communication information input from the input line is S_i・2^
k^-^i^t (or S_i・2^(^i^-^1
After moving the line by ^)^t) between the elements, it is output to the next stage of the communication line, and [2] The output line of the m-th communication line is the logical sum of two lines separated by n lines. A self-routing communication path is characterized in that the communication path is output to an outgoing line. (2) Accommodates n (=2^k, k is a natural number) incoming lines and n outgoing lines, and identifies the outgoing line position where communication information input from the incoming line should be output and the incoming line position. outputting the communication information to a target outgoing line based on header information consisting of routing control information indicating the difference and broadcasting control information instructing to output the communication information to all outgoing lines;
Alternatively, in a self-routing channel equipped with m (=k/t) (k, t are natural numbers) communication channel stages that output communication information input from the incoming line to all outgoing lines, [1] Each i-th (1≦i≦m)-th communication path is x_i=2n
-n2^-^(^i^-^1^)^t input lines and y_
It accommodates i=2n-n2^-^i^t output lines and has y_i elements, of which x_
One pair of input line and output line is connected to each of the i elements, only one output line is connected to each of the remaining (y_i-x_i) elements, and the distance between the first to y_i elements is When the broadcast control information has a logical value of '0', each element is connected in cascade in a single direction up to {(i-1)t
Based on the partial bit string S_i consisting of t bits from the +1}th bit to the (it)th bit, the communication information input from the input line is transferred between the elements by S_i 2^k^-^i^t. After moving it, it is output to the next communication path stage, and when the broadcast control information has a logical value of '1',
The communication information input from the input line is (2^t-1
)・2^k^-^i^t between the elements, and (2^x-1)・2^k^-^i^t(
However, each time the communication information moves by 0≦x≦t), the communication information is branched and output to the next communication path stage, and [2] The output line of the m-th communication path stage is two logic lines separated by n lines. Take peace,
A self-routing call path characterized by outputting to an outgoing line.