Switching system for transferring broadcast packet held in broadcast buffer received from input port to output ports according to the state of each output port

• US 5,825,773 A
• Filed: 03/18/1992
• Issued: 10/20/1998
• Est. Priority Date: 03/20/1991
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd., Hitachi Vlsi Engineering Corporation (Hitachi, Ltd.)
• Original Assignee: Hitachi, Ltd., Hitachi Vlsi Engineering Corporation (Hitachi, Ltd.)
• Inventors: Shutoh, Shin'ichi, Hamanaka, Naoki, Higuchi, Tatsuo, Takeuchi, Shigeo, Chiba, Hiroyuki, Ogata, Yasuhiro, Nakagoshi, Junji, Toba, Taturu
• Primary Examiner(s): Meky, Moustafa M.
• Application Number:
  US07/853,242
• Time in Patent Office: 2,407 Days
• Field of Search: 395/200, 395/250, 395/500, 395/575, 395/275, 395/200.18, 379/9, 379/14, 379/220, 379/221, 370/231, 370/398, 370/416, 370/422, 370/471, 370/474, 370/476
• US Class Current: 370/398
• CPC Class Codes: G06F 15/17393 having multistage networks, e.g. broadcasting scattering, gathering, hot spot contention, combining/decombining
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based

Abstract

In a method of transferring packets in a network for a parallel processor system handling a one-to-one transfer packet to be transferred from a processor to another processor and a broadcast packet to be transferred from a processor to a plurality of other processors, a transfer request of a broadcast packet is preferentially selected and a check is made to detect whether or not a plurality of processors specified as receivers are in a state in which the packet can be received. The broadcast packet is transferred to the processors found to be in the state in which the packet can be received. The packet transfer is delayed for the other processors in a state in which the packet cannot be received. Namely, only when the state of the processors is changed to the state in which the packet can be received, the broadcast packet is transferred thereto.

Claims

1. A method of transferring a broadcast packet in a switch circuit having a plurality of input ports and a plurality of output ports, comprising the steps of:

(a) checking states of said plurality of output ports;

(b) transferring said broadcast packet to at least one of said plurality of output ports detected in the step (a) as being in a receive state in which a packet can be received, in response to input of the broadcast packet to one of the plurality of input ports, said transferring of said broadcast packet to said at least one of said plurality of output ports in said receive state being performed independently from transferring of said broadcast packet to other output ports not in said receive state in which a packet can not be received when said other output ports not in said receive state changes to said receive state;

(c) transferring said broadcast packet to each of said other output ports not in said receive state, as said each of said other output ports not in said receive state changes to said receive state, said transferring of said broadcast packet to said each of said other output ports having changed from not in said receive state to said receive state being performed independently from transferring of said broadcast packet to said each of said other output ports which have not changed to said receive state; and

responsive to input of a one-to-one transfer packet to be transferred to one of said plurality of output ports after the input of the broadcast packet and during transfer of the broadcast packet to said output ports wherein the broadcast packet remains to be transferred to at least one of the plurality of output ports which remains in a state in which a packet cannot be received, transferring said one-to-one transfer packet to one of said plurality of output ports, designated by said one-to-one transfer packet without waiting for transfer of the broadcast packet to the at least one output port by the step (c), when the broadcast packet has already been transferred to the one output port designated by said one-to-one transfer packet.

2. A method of transferring a broadcast packet in a switch circuit having a plurality of input ports and a plurality of output ports, comprising the steps of:

(a) checking states of said plurality of output ports;

(b) transferring said broadcast packet to at least one of said plurality of output ports detected in the step (a) as being in a receive state in which a packet can be received, in response to input of the broadcast packet to one of the plurality of input ports, said transferring of said broadcast packet to said at least one of said plurality of output ports in said receive state being performed independently from transferring of said broadcast packet to other output ports not in said receive state in which a packet can not be received when said other output ports not in said receive state changes to said receive state;

(c) transferring said broadcast packet to each of said other output ports not in said receive state, as said each of said other output ports not in said receive state changes to said receive state, said transferring of said broadcast packet to said each of said other output ports having changed from not in said receive state to said receive state being performed independently from transferring of said broadcast packet to said each of said other output ports which have not changed to said receive state; and

responsive to input of a one-to-one transfer packet to be transferred to one of said plurality of output ports after the input of the broadcast packet and during transfer of the broadcast packet to said output ports wherein the broadcast packet remains to be transferred to at least one of the plurality of output ports which remains in a state in which a packet cannot be received, transferring said one-to-one transfer packet to one of said plurality of output ports, designated by said one-to-one transfer packet after said broadcast packet has been transferred to said designated one output port, when said broadcast packet remains to be transferred to said designated one output port by said step (c).

3. A switch circuit having a plurality of input ports and a plurality of output ports, comprising:

(1) a broadcast buffer, connected and provided in common to said input ports, for receiving and holding at least one broadcast packet inputted from one of said input ports; and

(2) a first transfer controller connected to said output ports and said broadcast buffer, for controlling transfer of said broadcast packet held in said broadcast buffer to each of said output ports, based on a state of said each output port, said transfer of said broadcast packet held in said broadcast buffer to said each output port is performed when permitted according to the state of said each output port, and said transfer is performed independently of a state of output ports other than said each output port.

4. A switch circuit according to claim 3, wherein

said first transfer controller comprises means for transferring said broadcast packet to one or more of the plurality of output ports, which are in a state in which a packet can be received, and for transferring said broadcast packet to each of other one or more of the plurality of output ports in a state in which a packet cannot be received, after said each other output port has changed to a state in which a packet can be received.

5. A switch circuit according to claim 3, wherein said broadcast buffer comprises a plurality of buffers connected and provided in common to said input ports, each buffer being provided in correspondence to one of said output ports and each buffer receiving and holding said at least one broadcast packet inputted from said one input port, and

said first transfer control comprises a plurality of controllers each provided in correspondence to one of said buffers, each controller transfers the broadcast packet held in one of said buffers corresponding to said each controller to one of said output ports corresponding to said corresponding one buffer, after confirming that a state of said corresponding output port is in a state in which a packet can be received.

6. A switch circuit according to claim 3, wherein said broadcast buffer comprises a common buffer provided in common for said plurality of said output ports and for receiving and holding said broadcast packet inputted through said one input port, and

said first transfer controller comprises means for transferring said broadcast packet held in said common buffer to the plurality of output ports in sequence so that said broadcast packet is transferred to one of said output ports after said broadcast packet has been transferred to another of said output ports.

7. A switch circuit having a plurality of input ports and a plurality of output ports, comprising:

(1) a broadcast buffer, connected and provided in common to said input ports, for receiving and holding at least one broadcast Packet inputted from one of said input ports;

(2) a first transfer controller connected to said output ports and said broadcast buffer, for controlling transfer of said broadcast packet held in said broadcast buffer to each of said output ports, based on a state of said each output port, said transfer of said broadcast packet held in said broadcast buffer to said each output port is performed when permitted according to the state of said each output port, and said transfer is performed independently of a state of output ports other than said each output port; and

(3) second transfer controller connected to said plurality of input ports and said plurality of output ports, for transferring a one-to-one transfer packet inputted from one of said input ports to one of said plurality of output ports determined by said one-to-one transfer packet, said second transfer controller comprising means for transferring said one-to-one transfer packet to said determined output port after said broadcast packet has been transferred to said determined output port by said first transfer controller, in case the one-to-one transfer packet has been inputted when said broadcast packet remains to be transferred to the determined output port by said first transfer controller.

8. A switch apparatus for transferring a broadcast packet, and having a plurality of input ports and a plurality of output ports, comprising:

(1) a broadcast buffer connected and provided in common to said plurality of input ports for holding a broadcast packet inputted from one of said input ports;

(2) a switch circuit connected to said plurality of said input ports, the plurality of output ports and said broadcast buffer, for connecting one of an output of said broadcast buffer and said input ports to each of said output ports;

(3) a switch controller for controlling a switching operation performed by said switch circuit; and

(4) a broadcast controller connected to said switch controller, for sending an instruction to said switch controller as to whether said broadcast packet in said broadcast buffer is to be transferred to each of said output ports or not, based on a state of each output port independent of a state of each output port other than said each output port.

9. A switch apparatus for transferring a broadcast packet, and having a plurality of input ports and a plurality of output ports, comprising:

(1) a broadcast buffer connected and provided in common to said plurality of input Ports for holding a broadcast packet inputted from one of said input ports;

(2) a switch circuit connected to said plurality of said input ports, the plurality of output ports and said broadcast buffer, for connecting one of an output of said broadcast buffer and said input ports to each of said output ports;

(3) a switch controller for controlling a switching operation performed by said switch circuit; and

(4) a broadcast controller connected to said switch controller, for sending an instruction to said switch controller as to whether said broadcast packet in said broadcast buffer is to be transferred to each of said output ports or not, based on a state of each output port independent of a state of each output port other than said each output port;

wherein said switch controller comprises;

first means connected to said plurality of said input ports and responsive to a one-to-one transfer packet inputted from one of said input ports, for sending an instruction to said switch circuit so as to transfer said one-to-one transfer packet to one of said output ports determined by said one-to-one transfer packet; and

second means, responsive to an instruction sent from said broadcast controller to transfer said broadcast packet to said determined output port for controlling said first means so as to transfer said one-to-one transfer packet after said broadcast packet has been transferred to said specified output port.

10. A switch apparatus for transferring a broadcast packet, and having a plurality of input ports and a plurality of output ports, comprising:

(1) a broadcast buffer connected and provided in common to said plurality of input ports for holding a broadcast packet inputted from one of said input ports;

(2) a switch circuit connected to said plurality of said input ports, the plurality of output ports and said broadcast buffer, for connecting one of an output of said broadcast buffer and said input ports to each of said output ports;

(3) a switch controller for controlling a switching operation performed by said switch circuit; and

(4) a broadcast controller connected to said switch controller, for sending an instruction to said switch controller as to whether said broadcast packet in said broadcast buffer is to be transferred to each of said output ports or not, based on a state of each output port independent of a state of each output port other than said each output port;

wherein said switch controller comprises a plurality of selectors each provided for a pair of one of said output ports and one of said input ports, each selector selecting one of a one-to-one transfer packet inputted from one of said input ports and a broadcast packet outputted from said broadcast buffer.

11. A switch apparatus for transferring a broadcast packet, and having a plurality of input ports and a plurality of output ports, comprising:

(1) a broadcast buffer connected and provided in common to said Plurality of input ports for holding a broadcast packet inputted from one of said input ports;

(2) a switch circuit connected to said plurality of said input ports, the plurality of output ports and said broadcast buffer, for connecting one of an output of said broadcast buffer and said input ports to each of said output ports;

(3) a switch controller for controlling a switching operation performed by said switch circuit; and

(4) a broadcast controller connected to said switch controller, for sending an instruction to said switch controller as to whether said broadcast packet in said broadcast buffer is to be transferred to each of said output ports or not, based on a state of each output port independent of a state of each output port other than said each output port;

wherein said switch controller comprises;

a plurality of selector controllers each provided in correspondence to one of said selectors, and

said broadcast controller comprises means for selectively sending an instruction to one or more of said selector controllers to transfer a broadcast packet held in said broadcast buffer to one or more of the output ports which are in a state in which a packet can be received,

wherein each selector controller comprises;

means for sending an instruction to transfer a one-to-one transfer packet to one of said selector controllers corresponding to a specified output port of said output ports determined by said one-to-one transfer packet in response to said one-to-one transfer packet inputted from one of said input ports corresponding to said each selector controller, and

means for controlling a corresponding selector so as to select a broadcast packet held in said broadcast buffer or a one-to-one transfer packet inputted from an input port corresponding to other selector controller in response to a transfer instruction of said broadcast packet sent from said broadcast controller or a transfer instruction of said one-to-one transfer packet sent from said other selector controller.

12. A switch circuit having a plurality of input ports and a plurality of output ports, comprising:

(1) means for holding a broadcast packet inputted from one of said input ports and a one-to-one transfer packet inputted from one of said input ports;

(2) a first control circuit, connected to said holding means, for controlling as to whether said broadcast packet in said holding means is to be selectively transferred to each of said output ports or not, based on a state of said each output port independent of a state of each output port other than said each output port; and

(3) a second control circuit, which operates in parallel with said first control circuit, for controlling as to whether said one-to-one transfer packet in said holding means is to be transferred to one of said output ports designated by said one-to-one transfer packet or not, based on a state of said designated output port independently of a state of each output port other than said designated output port.

13. A switch circuit according to claim 12, further comprising different transfer paths for transferring said broadcast packet and said one-to-one transfer packet from said holding means to each of said output ports.

14. A switch circuit according to claim 12, wherein said second control circuit comprises means for transferring said one-to-one transfer packet after said broadcast packet has been transferred to said determined port, when said broadcast packet present in said holding means remains to be transferred to said determined output port.

15. A parallel processor system comprising:

(A) a plurality of mutually connected switch circuits each of which comprises;

(1) a plurality of input ports and a plurality of output ports,

(2) a broadcast buffer connected and provided in common to said input ports, for receiving and holding a broadcast packet inputted from said one of input ports, and

(3) means connected to said plurality of said output ports and to said broadcast buffer for selectively transferring said broadcast packet held in said broadcast buffer to each of said output ports, based on a state of said each output port independent of a state of each output port other than said each output port; and

(B) a plurality of processors each connected to one of said input ports and to one of said output ports of said switch circuits.

16. A parallel processor system according to claim 15, wherein

said transferring means transfers said broadcast packet to one or more of the plurality of output ports which are in a state in which a packet can be received and for transferring said broadcast packet to each of one or more of the plurality of output ports in a state in which a packet cannot be received, after said each other output port has changed to a state in which a packet can be received.

17. A parallel processor system according to claim 15, wherein said switch circuits are connected to each other so as to constitute a multistage switch circuit network.

18. A parallel processor system according to claim 15;

wherein said switch circuits comprise crossbar switches aligned in a row direction and crossbar switches aligned in a column direction, each of said crossbar switches aligned in a row direction connected to said crossbar switches aligned in a column direction.

19. A parallel processor system according to claim 18, further comprising a plurality of exchangers, wherein each output port of each of said crossbar switches aligned in the column direction and each input port of one of said crossbar switches aligned in the row direction circuits are connected via one of said exchangers, and each of said processors is connected to one of said input ports and to one of said output ports of said switch circuits via one of said exchangers.

20. A method for transferring a broadcast packet in a switch circuit having a plurality of input ports and a plurality of output ports, comprising the steps of:

(a) inputting a broadcast packet from one of said plurality of input ports;

(b) storing each of a plurality of broadcast packets into one of a plurality of buffers each provided in correspondence to one of said output ports, each of said plurality of broadcast packets being same as said inputted broadcast packet;

(c) checking states of said plurality of output ports to determine whether each output port is ready to receive a packet; and

(d) controlling transfer of said plurality of broadcast packets stored in said plurality of buffers to said plurality of output ports, so that each of said plurality of broadcast packets is transferred to one of said output ports corresponding to said each buffer, depending upon a state of said corresponding output port checked by the step (c) independently of a state of each output port other than said corresponding output port.

21. A method for transferring a broadcast packet in a switch circuit having a plurality of input ports and a plurality of output ports, comprising the steps of:

(a) inputting a broadcast packet from one of said plurality of input ports;

(b) storing said inputted broadcast packet into a buffer;

(c) checking states of said plurality of output ports determine whether to each output port is ready to receive a packet; and

(d) controlling transfer of said broadcast packet stored in said buffer to said plurality of output ports, depending upon states of said output ports checked by the step (c), so that said broadcast packet is transferred to one of said output ports which is in a state in which a packet can be received and said broadcast packet is transferred to another one of said output ports which is in a state in which a packet can be received after completion of transfer of said broadcast packet to said one output port independently of output ports which are in a state in which a packet can not be received.

22. A method of transferring a broadcast packet in a switch circuit having a plurality of input ports, a broadcast buffer provided in common to said input ports, and a plurality of output ports, said method comprising the steps of:

(a) storing said broadcast packet in said broadcast buffer;

(b) checking states of said plurality of output ports;

(c) transferring said broadcast packet from said broadcast buffer to at least one of said plurality of output ports detected in the step (a) as being in a receive state in which a packet can be received, in response to input of the broadcast packet to one of the plurality of input ports, said transferring of said broadcast packet to said at least one of said plurality of output ports in said receive state being performed independently from transferring of said broadcast packet to other output ports not in said receive state in which a packet can not be received when said other output ports not in said receive state changes to said receive state;

(d) transferring said broadcast packet from said broadcast buffer to each of said other output ports not in said receive state, as said each of said other output ports not in said receive state changes to said receive state, said transferring of said broadcast packet to said each of said other output ports having changed from not in said receive state to said receive state being performed independently from transferring of said broadcast packet to said each of said other output ports which have not changed to said receive state; and

(e) responsive to input of a one-to-one transfer packet to be transferred to one of said plurality of output ports after the input of the broadcast packet and during transfer of the broadcast packet to said output ports wherein the broadcast packet remains to be transferred to at least one of the plurality of output ports which remains in a state in which a packet cannot be received, transferring said one-to-one transfer packet to one of said plurality of output ports, designated by said one-to-one transfer packet without waiting for transfer of the broadcast packet to the at least one output port by the step (c), when the broadcast packet has already been transferred to the one output port designated by said one-to-one transfer packet.

23. A method of transferring a broadcast packet in a switch circuit having a plurality of input ports, a broadcast buffer provided in common to said input ports, a broadcast buffer provided in common to said input ports, and a plurality of output ports, said method comprising the steps of:

(a) storing said broadcast packet in said broadcast buffer;

(b) checking states of said plurality of output ports;

(c) transferring said broadcast packet from said broadcast buffer to at least one of said plurality of output ports detected in the step (a) as being in a receive state in which a packet can be received, in response to input of the broadcast packet to one of the plurality of input ports, said transferring of said broadcast packet to said at least one of said plurality of output ports in said receive state being performed independently from transferring of said broadcast packet to other output ports not in said receive state in which a packet can not be received when said other output ports not in said receive state changes to said receive state;

(d) transferring said broadcast packet from said broadcast buffer to each of said other output ports not in said receive state, as said each of said other output ports not in said receive state changes to said receive state, said transferring of said broadcast packet to said each of said other output ports having changed from not in said receive state to said receive state being performed independently from transferring of said broadcast packet to said each of said other output ports which have not changed to said receive state; and

(e) responsive to input of a one-to-one transfer packet to be transferred to one of said plurality of output ports after the input of the broadcast packet and during transfer of the broadcast packet to said output ports wherein the broadcast packet remains to be transferred to at least one of the plurality of output ports which remains in a state in which a packet cannot be received, transferring said one-to-one transfer packet to one of said plurality of output ports, designated by said one-to-one transfer packet after said broadcast packet has been transferred to said designated one output port, when said broadcast packet remains to be transferred to said designated one output port by said step (c).