JPH0351340B2 - - Google Patents

Description

[Detailed description of the invention]

(Technical Field) The present invention relates to a switching network that interconnects processors or resources such as memory modules and the like in a parallel processing system using a large number of processors. (Technical background) oG.H. Barnes and SF Lundstrom,
``Design and Validation of a Connection
“Network for Many−Processor Systems”
IEEE Computer, Vol.14, No.12, pp.31-41,
Dec. 1981. For example, as described in the above paper, multi-stage networks such as buses, cross-point networks, and Banyan networks have traditionally been used as switching networks in the technical fields mentioned above. was. Among these, a multi-stage network is, for example, a 2-input 2-input network.
The basic element is an output shuffle circuit, and by arranging 2 ^n-1 of these in one stage and connecting n stages in series, a network with 2 ⁿ inputs and 2 ⁿ outputs is realized. Since a plurality of data transfer paths can be formed simultaneously from the output side to the output side, the number of required switch circuits is small compared to the data transfer capacity, which has the advantage of being economical. However, there are drawbacks such as the fact that the transfer paths to be implemented at the same time cannot be freely selected at all, and it is not possible to implement broadcast transfer in which the same data is sent to a plurality of output terminals at the same time. (Object of the Invention) The object of the present invention is to solve the above-mentioned drawbacks of the prior art, and to
The object of the present invention is to provide a large-scale multi-stage switching network that can realize broadcast transfer within a group. (Structure of the Invention) The present invention includes a plurality of data input terminals of four or more,
The same number of data output terminals and switches that direct data input from any data input terminal to any data output terminal correspond to each data input terminal, and receive data input from there, and A packet header is detected and decoded from among the packets, and if the packet header instructs transfer to one output terminal, a connection request is issued to the second priority interrupt encoder corresponding to that output terminal. , when instructing transfer to multiple output terminals, issue a group transfer request to their first priority interrupt encoder, and after receiving a permission response, respond to those output terminals. a first priority interrupt code that receives group transfer requests from all decoders and grants permission to one of them at a time; The data output terminal corresponds to the decoder and each data output terminal, receives connection requests from each decoder, accepts one of them at a time, and transmits data corresponding to the decoder issuing the accepted connection request. The basic component is a router module consisting of a second priority interrupt encoder that generates a control signal for opening a switch that directs data from an input terminal to its corresponding output terminal. It is a switching network characterized by being configured with multi-stage connections.
Hereinafter, it will be explained in detail using examples. (Example) In the following description, unless otherwise specified, lowercase letters attached to numbers represent numbers 1 to 4. FIG. 1 is a block diagram of a 64-input, 64-output network according to an embodiment of the present invention. ₁ in the same figure 1
...1 ₆₄ is an input terminal, 2 ₁ ...2 ₆₄ is an output terminal, 3 ₁ ...
₃₁₆ , ₄₁ ... ₄₁₆ , and ₆₁ ... ₆₁₆ are router modules with four inputs and four outputs. Also, the signal line connecting the router module 3 _i (i=1 to 16) and the router module 4 _j (j=1 to 16) is 5 _ij , and the signal line connecting the router module 4 _i (i=1 to 16) and the router module 4 The signal line connecting the modules 6 _j (j=1 to 16) is expressed as 7 _ij . The input and output of each router are for data (8 lines), for boundary tags (1 line), and for control (2 lines).
Consisting of 11 signal lines, the data line is used for data packets to be transferred, the boundary line is used to express the boundaries of data packets, and the control line is used for data synchronization. The data packet has a variable length of 8 bits×x words (x is any natural number), and the first word is used as a packet header to represent the destination of the packet. FIG. 2 shows the format of the packet header. There are two types of packet header formats, representing one-to-one transfer mode and group transfer mode, respectively. In one-to-one transfer mode, the upper 6 bits of the address field represent the destination output terminal number of the packet, and in the group transfer mode, the upper 4 bits of the address field represent the destination group number, and the next 3 bits represent the destination group number. The size part represents the size of the group. Furthermore, the size of the group is
Since it is expressed in the form of ^2N , in the case of a 64-input 64-output network, N is selected between 2 and 6, so 3 bits is sufficient for representation. FIG. 3 is a block diagram showing in detail the inside of one of the router modules used in FIG. ₁ , for example 31, where 11a is an input terminal and 12b is
FIFO register, 13c is a 4-input switch bank, 14d is an output terminal, 15 is a control combiner, 16
is a control unit, and ₁₆₁ is an external program input terminal. FIG. 4 is a diagram showing the external connections of the FIFO register in _{FIG .} D0
~D7 and a signal line of BT for boundary dug are connected, and control signal lines of C0 and C1 are connected to input side control terminals SI (shift in) and IR (input ready), respectively. In addition, the data signal lines from D0 to D7 on the data output terminal side, the boundary tag signal line, and the signal line from the output side control terminal OR (output ready) are routed through the 4-input switch bank 13c. It is connected to the data, boundary tag, and control (CO) signal lines of the output terminal 14d, respectively. The signal lines output from the remaining output control terminal SO (shift out) are connected to the remaining control signal line C1 of the output terminal 14d via the control coupler 15. In the case of one-to-one transfer mode, one input terminal 11
One output terminal 14d is connected to a, but in the group transfer mode, two or four output terminals 14 are connected to one input terminal 11a.
d may also be connected. FIG. 5 is a block diagram showing in detail one of the four-input switch banks 13c in FIG. 3, for example ₁₃₁ , where ₂₁₁ ... ₂₁₁₀ are input terminals;
22 ₁ ...22 ₁₀ is a 4-input selector, 23 ₁ ...23 ₁₀
is an AND gate, and ₂₄₁ is one of the control inputs 24e connected to the control section 16 in FIG.
One of the control inputs 24 ₁ , 24 _1-1 has a selection code for selecting one of the four inputs, and the remaining 2
4 An enable signal is sent to _1-2 to enable the selection code. FIG. 6 is a circuit diagram of the control coupler 15 in FIG. 3, and 24e is a control input from the control section 16;
25 is an input terminal from the control line C1 of the output terminals 14d, 26f is an output terminal to be connected to SO of the FIFO 12b, 27g is a 2-line to 4-line decoder, 28 ₁ ... 28 ₃₂ are AND gates, 29 ₁ ... 29 ₁₆
is an OR gate, and 30h is a 4-input AND gate. The control input 24e specifies the input terminal 11a connected to the output terminal 14e in FIG.
Selecting the input terminal 11a by the selection code,
When the enable signal becomes H level, a path from the control line C1 of the output terminal 14d to the output terminal 26f is opened. A plurality of control inputs 24e are connected to the same input terminal 11a
If you specify a plurality of corresponding control lines C1
A path from C to AND gate 30h is opened, and C
The logical product of the signals flowing to 1 is output from the output terminal 26f.
It is sent to the SO terminal of the FIFO register 12b. In this way, data transfer from one FIFO register 12b to multiple external FIFO registers, such as a FIFO register included in a next-stage router or a FIFO register connected to an output terminal of a switching network, can be synchronized. It becomes possible. FIG. 7 is a detailed block diagram of the control unit 16 in FIG. 3, where 31k is a decoder, 32m is an input terminal from the FIFO register 12b in FIG. 3, and 33 is a priority interrupt encoder (hereinafter abbreviated as PIE). , 34n
is a 2-level priority interrupt encoder (hereinafter abbreviated as 2L-PIE), and 24e is a 4-input switch bank 13c.
₁₆₁ is an external program input terminal. Also, FIG. 8 shows the decoder 31 in FIG.
It is a detailed connection diagram between k and PIE33, and 2L-PIE34n. Here, the decoder 31k detects and decodes the header of the data packet. Then, according to the operation mode determined by the contents of this header and the external program code input from the external program input terminal, signals are sent to the PIE 33 and 2L-PIE 34n. In the case of group transfers, deadlock may occur, so to avoid this, PIE33 is used to transfer only one router module at a time.
Only perform one group transfer. That is, when the decoder 31k detects a packet header in group transfer mode, it first issues a group transfer request (hereinafter abbreviated as GRQ) to the PIE 33, and
After obtaining a permission response (hereinafter referred to as RP),
Enter the specified connection operation. and until the transfer is finished
Continue to send GRQ and stop sending GRQ when transfer is complete. On the other hand, PIE33 selects one of the maximum four GRQ input INs and sends a permission signal to the transfer request source.
Give ACK, 2L-PIE34n output terminal 14d
Select the input terminal 11a to be connected to. During the connection, there are two types of connection requests, RQ0 and RQ1, sent from the decoder 31k, each of which is 2L-PIE3.
4n L0 and L1 are connected, but RQ0 is accepted with priority. FIG. 9 is a detailed block diagram of the decoder 31k in FIG. 7, where 41 is an 8-bit latch, 42 is a timing generator, 43 is a valid bit selector,
44 is a control signal generator, 45 is two signal lines connected to PIE33, 46p is a signal line connected to four 2L-PIEs, 47 is a reset terminal, 32m is an input terminal, ₁₆₁ is an external program input terminal. be. Here, the timing generator 42 has an input terminal 32m.
Signals are input from BT and CO, and timing signals indicating the start and end of a data packet are generated and sent to latch 41 and control signal generator 44.
However, when starting up the system, the timing signal generator 42 is reset through the reset terminal 47 and is assumed to be in an initial state, and the first data input from this state is regarded as a packet header.
When the boundary tag BT becomes H, it is assumed that the packet is at the end and returns to the initial state. A packet header is input to latch 41 by this timing signal. The valid bit selector 43 inputs the output of the latch 41 and the external program code S input from the external program input terminal ₁₆₁ , determines the operating mode of the router, and selects the valid address bits (up to 2 bits) in the packet header. ) is extracted and sent to the control signal generator 44 along with the operating mode code. By using this information, the control signal generator 4
4 generates control signals for PIE33 and 2L-PIE34n. Next, the operation of the router module in two data transfer modes will be explained. _Among the bits in the address field of the packet header having _the format shown in FIG. ).

【table】

[Table] Here, the x mark indicates that it is not related to address bits. Then the valid bits selected according to these tables
According to the information b ₀ b ₁ , a path connecting the appropriate input terminal 11a and the appropriate output terminal 14d is opened. At this time, the output terminal number to be selected, the subscript d, is the input terminal number, and the effective bit is independent of the subscript a.
b ₀ b ₁ only as specified in Table 3.

[Table] Here, the ampersand & indicates that multiple specified output terminals are connected simultaneously from the same input terminal. Assuming that a data packet is now input to the input terminal 11a of the router, the decoder 31k decodes the header of this packet. And header is 1
When pair-to-one transfer is instructed, the valid bit selector 43 selects the valid bit b ₀ b _{1 according to Table 1, and the control signal generator 44 determines the output terminal number according to Table 3, and selects the valid bit b 0 b 1} according to Table 1. Turn on the output of RQ1 to 2L-PIE34n corresponding to . This 2L-PIE3
When 4n becomes vacant, the connection request RQ1 is accepted, a path from the input terminal 11a to the output terminal 14d is opened, and data transfer begins. Also, the decoder 3
1k monitors the boundary tag BT of the input data and
When becomes H level, it is regarded as the end of the packet, and RQ1 is turned OFF to return to the initial state. Next, if the header indicates group transfer, the valid bit selector 43 selects the valid bit b ₀ b ₁ according to Table 2, and the control signal generator 44 selects the output terminal number according to Table 3. seek. When there is only one output terminal to be connected, that is, in the case of the classification shown in Table 3, the output of RQ0 to the 2L-PIE 34n corresponding to that output terminal is turned ON. And this 2L
- When the PIE34n becomes free or the one-to-one transfer it is handling is completed, the RQ0 is accepted,
Data transfer begins. Data transfer ends 1:1
Same as for transfer. When there are a plurality of output terminals to be connected, that is, in the case of the classifications shown in Table 3, GRQ for PIE 33 is first turned ON and a response from PIE 33 is waited. reply
When RP turns on, turn on the output of RQ0 to 2L-PIE34n, which corresponds to all output terminals to be connected. The subsequent operation is the third one mentioned above.
This is the same as for table classification. As explained above, by using a switching network that operates in this way, variable-length data packets can be sent to specified output terminals in one-to-one transfer mode, and ^{variable-length} data packets can be sent to specified output terminals in group transfer mode. Can be transferred to groups of any size. In addition, the above-mentioned PIE33 and FIFO register 12
Since hardware such as b can be easily realized using ordinary digital circuit technology, the third
It is also possible to realize the router itself in the figure with a single-chip VLSI, making it possible to achieve overall downsizing and economy. (Effects of the Invention) According to the present invention, a large-scale switching network can be constructed by using one type of router module as a basic component and combining them.
Since variable-length data packets can be transferred one-to-one and in groups, it can be applied to switching networks of large-scale parallel processing systems where broadcast communications often occur. In addition, the hardware has high modularity,
It is suitable for VLSI, and can be made smaller and more economical. In the above-described embodiment, a 4-input, 4-output router with a data word length of 8 bits was used as the basic component, but the same function can be realized by using, for example, a 2-input, 2-output router, or an 8-input, 8-output router. Furthermore, for example, if only the data word length is set to 12 bits,
A switching network of up to 1024 inputs and 1024 outputs can be configured. Also, the FIFO in the router
The capacity of the register was set to 16 words, but the basic functionality remains unchanged even if this capacity is increased or decreased. However, if this capacity becomes smaller than the data packet length,
It is reasonable to choose the same length as the average length of data packets, since this increases the probability of network blockage and reduces traffic capacity.

[Brief explanation of drawings]

Fig. 1 is a block diagram of an embodiment of the present invention, Fig. 2 is a diagram showing the format of a packet header, Fig. 3 is a detailed block diagram of the router module, and Fig. 4 is a diagram showing the format of a packet header.
3 is a diagram showing the external connection of the FIFO register 12b in FIG. 3, FIG. 5 is a detailed block diagram of the 4-input switch bank 13c in FIG. 3, and FIG. 6 is a circuit diagram of the control coupler 15 in FIG. 3. 7th
The figure shows a detailed block diagram of the control unit 16 in FIG. 3, and FIG. 8 shows the decoder 31k and PIE in FIG.
33 and 2L-PIE 34n, and FIG. 9 is a detailed block diagram of the decoder 31k in FIG. 1 ₁ to 1 ₆₄ ... Input terminals, 2 ₁ to 2 ₆₄ ... Output terminals, 13 ₁ to 13 ₄ ... 4-input switch bank,
31 ₁ to 31 ₄ ... decoder, 33 ... priority interrupt encoder, 34 ₁ to 34 ₄ ... two-level priority interrupt encoder.

Claims (1)

[Claims] 1 (a) a plurality of data input terminals of 4 or more, (b) the same number of data output terminals as the data input terminals, and (c) any data input from any data input terminal. (d) A switch corresponding to each data input terminal, which receives data input therefrom, detects and decodes a packet header from the data, and converts the packet header into one packet. If transfer to an output terminal is specified, the second
issues a connection request to the priority interrupt encoder of
When instructing transfer to multiple output terminals, a group transfer request is issued to the first priority interrupt encoder, and after a permission response is obtained, the group transfer request corresponding to those output terminals is issued. (e) a first said priority decoder that issues a connection request to a second priority interrupt encoder; (f) a decoder corresponding to each data output terminal, receiving connection requests from each decoder, accepting one of them at a time, and issuing the accepted connection request; a second generating a control signal for opening a switch that directs data from a data input terminal corresponding to the device to its corresponding output terminal;
(g) These router modules are connected in multiple stages, and all arbitrary input terminals of the switching network are connected to all arbitrary output terminals. This switching network is characterized by connecting these routers and modules in accordance with the above. 2. The decoder issues connection requests for one-to-one transfer and group transfer separately, and when the second priority interrupt encoder accepts these connection requests, it preferentially accepts the connection request for group transfer. A switching network according to claim 1. 3 The packet header has two formats, one containing information on the number of the data output terminal, and the other containing information on the group number and group size of the data output terminal. The switching network described in Scope 1.