Message transfer system and method for parallel computer with message transfers being scheduled by skew and roll functions to avoid bottlenecks
First Claim
1. A computer system comprising a plurality of processing elements interconnected by a communications network, the communications network having a series of network addresses each associated with one of said processing elements,A. the communications network transferring messages transmitted by the processing elements in accordance with an address portion associated with each message, each address portion identifying a network address, the communications network transferring each message to one of said processing elements whose network address is identified by the message'"'"'s address portion;
- B. said processing elements during a message transfer operation, generating a series of messages and transmitting them over the communications network, each of said processing elements;
i. transmitting a first message whose address portion contains a network address which is a mathematical function of a skew parameter value and the processing element'"'"'s network address, andii. after transmitting the first message, transmitting successive messages having address portions containing successive network addresses following the first message'"'"'s network address in the series,such that successive messages are associated with respective address portions which enable the communications network to transfer the messages to processing elements which have successive network addresses.
5 Assignments
0 Petitions
Accused Products
Abstract
A computer system comprises a plurality of processing elements interconnected by a communications network. The communications network has a series of network addresses each identifying a location in the network, each processing element has an associated network address in the series. The communications network transfers messages transmitted by the processing elements in accordance with a respective address portion associated with each message, thereby to transfer the messages among the processing elements. Each processing element includes a message generator and a message transmitter. The message generator generates, during a message transfer operation, a series of messages for transmission over the communications network to others of the processing elements in the system, each message having an address portion whose contents enable the communications network to transfer the message from the processing element generating the message to a processing element to receive the message. The message generator generates the messages such that address portions of the successive messages in the series are transferred to processing elements having successive network addresses. The message transmitter iteratively transmits the series of messages generated by the message generator, the message transmitters of the processing elements which have successive network addresses selecting, as initial messages to be transmitted, messages having address portions to be transmitted to processing elements which have succeeding network addresses, thereby to effect a skewing of the messages transferred over the communications network.
114 Citations
21 Claims
-
1. A computer system comprising a plurality of processing elements interconnected by a communications network, the communications network having a series of network addresses each associated with one of said processing elements,
A. the communications network transferring messages transmitted by the processing elements in accordance with an address portion associated with each message, each address portion identifying a network address, the communications network transferring each message to one of said processing elements whose network address is identified by the message'"'"'s address portion; B. said processing elements during a message transfer operation, generating a series of messages and transmitting them over the communications network, each of said processing elements; i. transmitting a first message whose address portion contains a network address which is a mathematical function of a skew parameter value and the processing element'"'"'s network address, and ii. after transmitting the first message, transmitting successive messages having address portions containing successive network addresses following the first message'"'"'s network address in the series, such that successive messages are associated with respective address portions which enable the communications network to transfer the messages to processing elements which have successive network addresses. - View Dependent Claims (2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
5. A computer system as defined in clam 4 in which the mathematical function is St =St-1 +W (mod M), where St is related to the network address for the address portion associated with a message to be transmitted by the processing element, St-1 is related to the network address for the address portion associated with a message previously transmitted by the processing element, "W" represents the roll parameter value and "M" corresponds to the number of messages to be transmitted by the processing element during the message transfer operation, and "mod" refers to a modulo function.
-
17. A method for use in connection with a computer system comprising a plurality of processing elements interconnected by a communications network, the communications network having a series of network addresses each associated with one of said processing elements, the communications network transferring messages transmitted by the processing elements in accordance with an address portion associated with each message, each address portion identifying a network address, the communications network transferring each message to one of said processing elements whose network address is identified by the message'"'"'s address portion;
- at least some of said processing elements during a message transfer operation generating a series of messages and transmitting them over the communications network, the method of controlling at least some of said processing elements to generate messages for transmission during a message transfer operation comprising the steps wherein each of said at least some of said processing elements;
A. transmits a first message whose address portion contains a network address which is a mathematical function of a skew parameter value and the processing element'"'"'s network address, and B. after transmitting the first message, transmits successive messages having address portions containing successive network addresses following the first message'"'"'s network address in the series, such that successive messages are associated with respective address portions which enable the communications network to transfer the messages to processing elements which have successive network addresses. - View Dependent Claims (18, 19, 20, 21)
- at least some of said processing elements during a message transfer operation generating a series of messages and transmitting them over the communications network, the method of controlling at least some of said processing elements to generate messages for transmission during a message transfer operation comprising the steps wherein each of said at least some of said processing elements;
Specification