Patent EP0365745A2 successfully refreshed from Google Patents.
EP0365745A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A method for detecting and avoiding erroneous decombining in combining networks for parallel computing systems
Assignee: International Business Machines Corp
•
Filing: 1989-06-21
•
Granted: —
•
Expires: 2009-06-21
Abstract
Abstract A method to detect and avoid erroneous message decombining in the switching nodes of message combining multistage interconnection networks used to connect the multiple processors to the multiple memory modules of the shared memories used in parallel computing systems. The method assigns a unique ID to each switch and tags each combined message with it. This ID is also tagged to the reply messages. During decombining the message's ID is matched with the switch's ID, if they do not match the message is not decombined. According to a further feature of the invention, it is possible to provide sufficient information in the ID field to allow a routing error to be detected.
Inventors
- 👤 Bharat Deep Rathi
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-26 16:47
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17393
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
210 words
A method for performing message combining/decombining in multistage interconnection networks (MINs) which comprises: 1) assigning a unique identification (ID) number to every switch in the network; 2) analyzing every message to be transmitted to the system through each switch from a first source to determine if it can be combined with another message from another source; and if so, performing a combining operation, and 3) appending the unique ID number of the switch performing the combining operation tc the message header, 4) passing the modified message to the next point in the network, and repeating steps 1-3 until the message reaches its destination in memory; 5) placing a response message on the reverse path of said interconnection network back to a requesting processor and appending any switch IDs to the response message which were contained in the forward message; 6) analyzing said response message at each switch through which said message is routed to determine if the message needs to be decombined at that switch; 7) said analyzing step including comparing the switch's ID field with the decombining ID field included in the header; if any, and 8) if the ID'S match, decombining the message and forwarding the separate messages to the next switch node or to the requesting processors.
Claim 2
Independent Claim
210 words
A method for performing message combining/decombining in multistage interconnection networks (MINs) which comprises: 1) assigning a unique identification (ID) number to every switch in the network; 2) analyzing every message to be transmitted to the system through each switch from a first source to determine if it can be combined with another message from another source; and if so, performing a combining operation, and 3) appending the unique ID number of the switch performing the combining operation tc the message header, 4) passing the modified message to the next point in the network, and repeating steps 1-3 until the message reaches its destination in memory; 5) placing a response message on the reverse path of said interconnection network back to a requesting processor and appending any switch IDs to the response message which were contained in the forward message; 6) analyzing said response message at each switch through which said message is routed to determine if the message needs to be decombined at that switch; 7) said analyzing step including comparing the switch's ID field with the decombining ID field included in the header; if any, and 8) if the ID'S match, decombining the message and forwarding the separate messages to the next switch node or to the requesting processors.
Claim 3
Dependent Claim
40 words
A method for performing message combining/decombining in a multistage interconnection network as set forth in claim 1 including returning the message without decombining, when the ID fields do not match, to a single preceding stage (or processor) in the MIN.
Claim 4
Dependent Claim
89 words
A method operable in a message combining/decombining multistage interconnection network system as set forth in claim 1, including setting the switch ID field in the message header to an initial no-combination configuration (NOC) when a message is presented to the MIN, and resetting said NOC field to a particular switch's ID only if a combination operation takes place; and bypassing the decombination function at any switch which a message traverses in the reverse direction if the ID field which would be associated with that switch is set to NOC.
Claim 5
Dependent Claim
62 words
A method operable in a message combining/decombining multistage interconnection network as set forth in claim 3 wherein the step of inserting a unique switch ID field in a combined message level includes first concatenating the unique switch ID field with a unique ID field identifying the level of the switch in the MIN, and inserting the concatenated ID in the message header.
Claim 6
Dependent Claim
68 words
A method operable in a message combining/decombining multistage interconnection network as set forth in claim 3, including generating and inserting an error detection code field generated for the unique switch ID field in the message header, together with the ID field, and utilizing the error detection code field to verify the ID carried by a message traversing the MIN in the reverse direction before performing any decombination operation.
Claim 7
Dependent Claim
227 words
In a combining/decombining multistage interconnection network (MIN) for communicating between the processors of a multiprocessor computer system and a memory system comprising a plurality of separate memory modules, wherein said MIN comprises a plurality of individual switch elements organized into a plurality of multi-switch levels, a switch in any level being connected only to switches in adjacent levels, each said switch including means for determining if two messages can be combined and, if so, effecting a combining operation and storing all internal data necessary to effect subsequent decombining when the combined message is returned to that switch, the improvement which comprises a method operable in the MIN switch architecture of each switch comprising: 1) appending a unique ID to the combined message's header, when it is "combined", uniquely and unambiguously identifying the switch which effected the combining operation; 2) checking the IDs of any "combined" message returned to the switch to see if the ID of this message and the switch ID match and, if so; 3) decombining the message and routing the individual decombined messages in accordance with data stored in the switch and if not; 4) inhibiting any decombining operation and routing the message to the next switch node in the network or to a requesting processor and; 5) setting an error/field in the message if an ID transmission and/or a routing error is detected.
Claim 8
Dependent Claim
227 words
In a combining/decombining multistage interconnection network (MIN) for communicating between the processors of a multiprocessor computer system and a memory system comprising a plurality of separate memory modules, wherein said MIN comprises a plurality of individual switch elements organized into a plurality of multi-switch levels, a switch in any level being connected only to switches in adjacent levels, each said switch including means for determining if two messages can be combined and, if so, effecting a combining operation and storing all internal data necessary to effect subsequent decombining when the combined message is returned to that switch, the improvement which comprises a method operable in the MIN switch architecture of each switch comprising: 1) appending a unique ID to the combined message's header, when it is "combined", uniquely and unambiguously identifying the switch which effected the combining operation; 2) checking the IDs of any "combined" message returned to the switch to see if the ID of this message and the switch ID match and, if so; 3) decombining the message and routing the individual decombined messages in accordance with data stored in the switch and if not; 4) inhibiting any decombining operation and routing the message to the next switch node in the network or to a requesting processor and; 5) setting an error/field in the message if an ID transmission and/or a routing error is detected.
Claim 9
Dependent Claim
75 words
A method operable in a MIN switch architecture as set forth in claim 6 further including appending a unique level ID to the message header when a combined message is formed together with the unique switch ID and comparing both the switch ID and the level ID when a "combined" message is received on the return path of the MIN and flagging a routing error if the level IDs match but the switch IDs don't.
Claim 10
Dependent Claim
57 words
A method operable in a MIN switch architecture as set forth in claim 7 including initially setting a unique "no-combined" field (NOC) in all message ID fields and retaining the NOC configuration until a combining operation occurs and bypassing any decombination procedure when any message having its ID field set to NOC is returned to any switch.
Claim 11
Independent Claim
241 words
A method for performing message combining/decombining in multistage interconnection networks (MINs) which comprises: 1) assigning a unique identification (ID) number to every switch in the network; 2) analyzing every message to be transmitted to the system through each switch from a first source to determine if it can be combined with another message from another source; and if so, performing a combining operation, and 3) appending the unique ID number of the switch performing the combining operation to the message header, 4) passing the so combined message to the next point in the network, and repeating steps 1-3 until the message reaches its destination in memory; 5) placing a response message from memory on the reverse path of the MIN and appending all header information from the outgoing message to the response message; 6) comparing the response message's ID with the ID of the receiving switch; 7) if IDs match in step 6, decombining the messages and 8) routing the decombined messages to the processors via internal information stored in the switch; 9) if the IDs compared in step do 6 do not match, checking to see if a message is routed incorrectly, or there is an error in the ID based on an error detection code appended to the ID and; 10) if any error is detected, appending an error signal to the non-decombined message's "error" field before it is sent out to the next swtich level or requesting processor.
Claim 12
Independent Claim
241 words
A method for performing message combining/decombining in multistage interconnection networks (MINs) which comprises: 1) assigning a unique identification (ID) number to every switch in the network; 2) analyzing every message to be transmitted to the system through each switch from a first source to determine if it can be combined with another message from another source; and if so, performing a combining operation, and 3) appending the unique ID number of the switch performing the combining operation to the message header, 4) passing the so combined message to the next point in the network, and repeating steps 1-3 until the message reaches its destination in memory; 5) placing a response message from memory on the reverse path of the MIN and appending all header information from the outgoing message to the response message; 6) comparing the response message's ID with the ID of the receiving switch; 7) if IDs match in step 6, decombining the messages and 8) routing the decombined messages to the processors via internal information stored in the switch; 9) if the IDs compared in step do 6 do not match, checking to see if a message is routed incorrectly, or there is an error in the ID based on an error detection code appended to the ID and; 10) if any error is detected, appending an error signal to the non-decombined message's "error" field before it is sent out to the next swtich level or requesting processor.
Claim 13
Dependent Claim
89 words
A method operable in a message combining/decombining multistage interconnection network system as set forth in claim 9, including setting the switch ID field in the message header to an initial no-combination configuration (NOC) when a message is presented to the MIN, and resetting said NOC field to a particular switch's ID only if a combination operation takes place; and bypassing the decombination function at any switch which a message traverses in the reverse direction if the ID field which would be associated with that switch is set to NOC.
Claim 14
Dependent Claim
61 words
A method operable in a message combining/decombining multistage interconnection network as set forth in claim 10 wherein the step of inserting a unique ID field in a combined message level includes first concatenating a unique switch ID field with a unique ID field identifying the level of the switch in the MIN, and inserting the concatenated ID in the message header.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.