US5247694A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for generating communications arrangements for routing data in a massively parallel processing system
Assignee: Thinking Machines Corp
•
Filing: 1990-06-14
•
Granted: 1993-09-21
•
Expires: 2010-06-14
Abstract
Abstract A system for generating communication pattern information for facilitating communication among processing nodes interconnected over communications links in a predetermined pattern to form a massively parallel processor. The system includes a mapping element and a communication pattern information generating element. The mapping element maps problem vertices from a problem graph onto processing nodes of a massively-parallel processor in relation to a communication cost function representing delays associated with communicating among processing nodes to which the respective problem vertices have been mapped. The communication pattern information generating element generates communication pattern information in connection with problem vertices mapped onto processing nodes, for use in directing message transfers among processing nodes to facilitate transfers of messages among the processing nodes over the communications links as defined by the problem graph.
Inventors
- 👤 E. Denning Dahl
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 20:35
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17337; G06F15/17343
Claims Analysis
Total Claims: 82
Claim 1
Independent Claim
181 words
A system to facilitate the fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent the pattern of communication of data between problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected in a fixed pattern by a plurality of communications links for transferring data among the processing nodes, the system comprising: A. a mapping element for establishing a fixed mapping of said problem vertices onto said processing nodes in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped over the communications links as defined by the edges of the problem graph; and B. a communication pattern information generating element for generating communication pattern information in connection with the fixed mapping as determined by the mapping element, for use in directing message transfers among processing nodes to facilitate transfers of messages among the processing nodes over the communications links as defined by the edges of the problem graph.
Claim 2
Independent Claim
181 words
A system to facilitate the fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent the pattern of communication of data between problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected in a fixed pattern by a plurality of communications links for transferring data among the processing nodes, the system comprising: A. a mapping element for establishing a fixed mapping of said problem vertices onto said processing nodes in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped over the communications links as defined by the edges of the problem graph; and B. a communication pattern information generating element for generating communication pattern information in connection with the fixed mapping as determined by the mapping element, for use in directing message transfers among processing nodes to facilitate transfers of messages among the processing nodes over the communications links as defined by the edges of the problem graph.
Claim 3
Dependent Claim
181 words
A system as defined in claim 1 in which said mapping element comprises: A. an initial mapping generator for generating an initial current fixed mapping in which said problem vertices are selectively assigned to said processing nodes; B. a prospective perturbation generator for generating prospective perturbations in response to the current fixed mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex to another of said processing nodes; C. a perturbation selector for selecting prospective perturbations generated by said prospective perturbation generator in response to a change in the communication cost function related thereto; D. a perturbation mapping generator for generating an updated fixed mapping in response to prospective perturbations generated by said prospective perturbation generator as selected by said perturbation selector; and E. a control element for controlling operations by said prospective perturbation generator, the perturbation selector, and the perturbation mapping generator in a plurality of iterations, said prospective perturbation generator and said perturbation selector using the updated fixed mapping generated by said perturbation mapping generator during one iteration as the current fixed mapping during a subsequent iteration.
Claim 4
Dependent Claim
39 words
A system as defined in claim 2 in which each prospective perturbation comprises a prospective reassignment of a problem vertex from one of said processing nodes to another of said processing nodes connected directly thereto by a communications link.
Claim 5
Dependent Claim
52 words
A system as defined in claim 2 in which: A. said control element initially generates a maximum occupancy value, B. said initial mapping generator assigns ghost vertices to said processing nodes, such that the number of problem vertices and ghost vertices assigned to a processing node corresponds to said maximum occupancy value.
Claim 6
Dependent Claim
76 words
A system as defined in claim 2 in which said perturbation selector includes a plurality of rendezvous nodes each associated with predetermined ones of said processing nodes, each rendezvous node selecting a prospective perturbation generated by said prospective perturbation generator for problem vertices assigned to its associated processing nodes, each rendezvous node determining a change in the communication cost function related thereto related to the prospective perturbation and selectively enabling the prospective perturbation in response thereto.
Claim 7
Dependent Claim
150 words
A system as defined in claim 5 in which each prospective perturbation identifies a prospective reassignment of a problem vertex from one processing node over one communications link to an adjacent communications link and in which: A. said control element initially generates a maximum occupancy value, B. said initial mapping generator assigns ghost vertices to said processing nodes, such that the number of problem vertices and ghost vertices assigned to a processing node corresponds to said maximum occupancy value; C. said prospective perturbation generator also generates a prospective perturbed mapping in relation to said ghost vertices; and D. each rendezvous node is associated with two processing nodes that are interconnected by a communications link, each rendezvous node selecting the same number of prospective perturbations from its associated processing nodes to maintain the number of problem vertices and ghost vertices assigned to each processing node corresponding to the maximum occupancy value.
Claim 8
Dependent Claim
23 words
A system as defined in claim 6 in which each rendezvous node selects one prospective perturbation from each of its associated processing nodes.
Claim 9
Dependent Claim
65 words
A system as defined in claim 6 in which each rendezvous node includes: A. a prospective perturbation selector for selecting a pair of prospective perturbations, the pair comprising a prospective perturbation from each of its associated processing nodes; B. a communication cost change element for determining a communication cost change value in response to the pair of prospective perturbations selected by the prospective perturbation selector.
Claim 10
Dependent Claim
51 words
A system as defined in claim 8 in which said control element generates a threshold value, and said rendezvous node further includes a comparator for comparing said communication cost change value generated by the communication cost change element to said threshold value and for enabling the prospective perturbations in response thereto.
Claim 11
Dependent Claim
20 words
A system as defined in claim 9 in which the control element generates a new threshold value for each iteration.
Claim 12
Dependent Claim
251 words
A system as defined in claim 1 in which said mapping element comprises: A. a massively-parallel processor including a plurality of processing nodes interconnected by communications links in a predetermined pattern; B. a mapping element control portion comprising: i. an initial mapping generator for generating an initial current fixed mapping in which said problem vertices are selectively assigned to said processing nodes, said initial mapping generator generating problem vertex tokens representing said problem vertices and enabling each problem vertex token to be loaded into its assigned processing node; ii. a prospective perturbation generator for enabling said processing nodes to generate prospective perturbations in response to the current fixed mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex token to another of said processing nodes; iii. a perturbation selector for enabling said processing nodes to select prospective perturbations generated during processing in response to said prospective perturbation generator, in further response to a change in the communication cost function related thereto; iv. a perturbation mapping generator for generating an updated fixed mapping in response to prospective perturbations generated by said prospective perturbation generator as selected by said perturbation selector; and v. an iteration control element for controlling processing in response to the prospective perturbation generator, the perturbation selector and the perturbation mapping generator in a plurality of iterations, said prospective perturbation generator and said perturbation selector using the updated fixed mapping generated by said perturbation mapping generator during one iteration as the current fixed mapping during a subsequent iteration.
Claim 13
Dependent Claim
93 words
A system as defined in claim 11 in which, during processing in response to said perturbation selector, a plurality of processing nodes are enabled to operate as rendezvous nodes, each rendezvous node being associated with predetermined ones of said processing nodes, rendezvous node selecting a prospective perturbation generated during processing in response to the prospective perturbation generator for problem vertices assigned to its associated processing nodes, each rendezvous node determining a change in the communication cost function related thereto related to the prospective perturbation and selectively enabling the prospective perturbation in response thereto.
Claim 14
Dependent Claim
167 words
A system as defined in claim 12 in which each prospective perturbation identifies a prospective reassignment of a problem vertex from one processing node over one communications link to an adjacent communications link and in which: A. said mapping element control portion initially generates a maximum occupancy value, B. said initial mapping generator further generates ghost vertex tokens and enables them to be loaded into said processing nodes, such that the number of problem vertex tokens and ghost vertex tokens loaded into a processing node corresponds to said maximum occupancy value; C. said prospective perturbation generator also enables said processing nodes to generate a prospective perturbed mapping in relation to said ghost vertices; and D. each rendezvous node is associated with two processing nodes that are interconnected by a communications link, each rendezvous node selecting the same number of prospective perturbations from its associated processing nodes to maintain the number of problem vertices and ghost vertices assigned to each processing node corresponding to the maximum occupancy value.
Claim 15
Dependent Claim
23 words
A system as defined in claim 13 in which each rendezvous node selects one prospective perturbation from each of its associated processing nodes.
Claim 16
Dependent Claim
85 words
A system as defined in claim 13 in which the rendezvous nodes operate in response to: A. a prospective perturbation enabling portion for enabling the processing nodes selected to be rendezvous nodes to select a pair of prospective perturbations, the pair comprising a prospective perturbation from each of its associated processing nodes; B. a communication cost change enabling portion for enabling the processing nodes selected to be rendezvous nodes to determine a communication cost change value in response to the pair of selected prospective perturbations.
Claim 17
Dependent Claim
68 words
A system as defined in claim 15 in which said mapping element control portion generates a threshold value, and said rendezvous nodes further operate in response to a comparator enabling portion for enabling the processing nodes selected to be rendezvous nodes to compare the communication cost change value generated by the communication cost change element to the threshold value and for enabling the prospective perturbations in response thereto.
Claim 18
Dependent Claim
22 words
A system as defined in claim 16 in which the mapping element control portion generates a new threshold value for each iteration.
Claim 19
Dependent Claim
83 words
A system as defined in claim 1 in which the communication pattern information generating element comprises: A. a message/communications link correspondence element for generating correspondences to facilitate the transfer of a message over a selected communications link at each processing node; and B. a communication pattern control element for controlling said message/communications link correspondence element in a series of communications link iterations, during each iteration enabling the generation of correspondences for one of a plurality of communications links for a message transfer cycle.
Claim 20
Dependent Claim
108 words
A system as defined in claim 18 in which said message/communications link correspondence element includes, for each processing node; A. a message list including a plurality of entries each associated with a message available for transfer by the processing node during the message transfer cycle; B. a priority establishment element for generating a priority value associated with each entry in said message list; and C. a communications link assignment element for using the priority values generated by said priority establishment element to associate entries in said message list with communications links connected to said processing node and for generating said communication pattern information in response to the associations.
Claim 21
Dependent Claim
71 words
A system as defined in claim 19 in which, at each processing node, each message can be transmitted over selected ones of the communications links connected thereto, said priority establishment element generates a priority value for each entry and communications link in relation to (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link.
Claim 22
Dependent Claim
70 words
A system as defined in claim 20 in which the priority value generated by the priority establishment element corresponds to the sum of (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link, the communication link assignment element generating communication pattern information for associations of entries and communications links with low priority values.
Claim 23
Dependent Claim
49 words
A system as defined in claim 18 in which said communication pattern control element further controls said message/communications link correspondence element in a series of message transfer cycle iterations, each including a plurality of communications link iterations, thereby enabling generation of correspondences for a plurality of message transfer cycles.
Claim 24
Dependent Claim
120 words
A system as defined in claim 22 in which said message/communications link correspondence element includes, for each processing node: A. a message list including a plurality of entries each associated with a message available for transfer by the processing node during the message transfer cycle, including messages determined to be transferred during a previous message transfer cycle; B. a priority establishment element for generating a priority value associated with each entry in said message list; and C. a communications link assignment element for using the priority values generated by said priority establishment element to associate entries in said message list with communications links connected to said processing node and for generating said communication pattern information in response to the associations.
Claim 25
Dependent Claim
71 words
A system as defined in claim 23 in which, at each processing node, each message can be transmitted over selected ones of the communications links connected thereto, said priority establishment element generates a priority value for each entry and communications link in relation to (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link.
Claim 26
Dependent Claim
70 words
A system as defined in claim 24 in which the priority value generated by the priority establishment element corresponds to the sum of (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link, the communications link assignment element generating communication pattern information for associations of entries and communications links with low priority values.
Claim 27
Dependent Claim
123 words
A system as defined in claim 1 in which the communication pattern information generating element comprises: A. a massively-parallel processor including a plurality of processing nodes interconnected by communications links in a predetermined pattern; B. a communication pattern control portion comprising: i. a message/communications link correspondence element for enabling said processing nodes to generate correspondences to facilitate the transfer of a message over a selected communications link at each processing node; and ii. a communication pattern control element for enabling said processing nodes to control said processing in response to said message/communications link correspondence element in a series of communications link iterations, during each iteration enabling the generation of correspondences for one of a plurality of communications links for a message transfer cycle.
Claim 28
Dependent Claim
125 words
A system as defined in claim 26 in which said message/communications link correspondence element includes: A. a message list generating portion for enabling said processing nodes to generate a message list including a plurality of entries each associated with a message available for transfer by the processing node during the message transfer cycle; B. a priority establishment element for enabling said processing nodes to generate a priority value associated with each entry in said message list; and C. a communications link assignment element enabling said processing nodes to use the priority values generated by said priority establishment element to associate entries in said message list with communications links connected to said processing node and to generate said communication pattern information in response to the associations.
Claim 29
Dependent Claim
76 words
A system as defined in claim 27 in which, at each processing node, each message can be transmitted over selected ones of the communications links connected thereto, said priority establishment element enabling said processing nodes to generate a priority value for each entry and communications link in relation to (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link.
Claim 30
Dependent Claim
80 words
A system as defined in claim 28 in which the priority value generated in response to processing controlled by the priority establishment element corresponds to the sum of (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link, the communications link assignment element enabling said processing node to generate communication pattern information for associations of entries and communications links with low priority values.
Claim 31
Dependent Claim
59 words
A system as defined in claim 26 in which processing in response to said communication pattern control element further controls enables said processing nodes to process said message/communications link correspondence element in a series of message transfer cycle iterations, each including a plurality of communications link iterations, thereby enabling generation of correspondences for a plurality of message transfer cycles.
Claim 32
Dependent Claim
136 words
A system as defined in claim 30 in which said message/communications link correspondence element includes: A. a message list generating portion for enabling said processing nodes to generate a message list including a plurality of entries each including a message token associated with a message available for transfer by the processing node during the message transfer cycle, including message tokens associated with messages determined to be transferred during a previous message transfer cycle; B. a priority establishment element for generating a priority value associated with each entry in said message list; and C. a communications link assignment element for using the priority values generated by said priority establishment element to associate entries in said message list with communications links connected to said processing node and for generating said communication pattern information in response to the associations.
Claim 33
Dependent Claim
76 words
A system as defined in claim 31 in which, at each processing node, each message can be transmitted over selected ones of the communications links connected thereto, said priority establishment element enabling said processing nodes to generate a priority value for each entry and communications link in relation to (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link.
Claim 34
Dependent Claim
80 words
A system as defined in claim 32 in which the priority value generated in response to processing controlled by the priority establishment element corresponds to the sum of (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link, the communications link assignment element enabling said processing node to generate communication pattern information for associations of entries and communications links with low priority values.
Claim 35
Dependent Claim
47 words
A system as defined in claim 31 in which the message/communications link correspondence element further includes a message token transfer element for enabling the processing nodes to transfer of message tokens over the communications links associated therewith after associations have been generated for a message transfer cycle.
Claim 36
Dependent Claim
45 words
A system as defined in claim 34 in which each message token has a destination pointer, said message token transfer element enabling the processing nodes to adjust the values of the pointers in relation to the communications link over which it transfers the message token.
Claim 37
Independent Claim
260 words
A system to facilitate the fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent a data communication pattern among the problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected by a plurality of communications links for transferring data among the processing nodes, the mapping being in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped, the system comprising: A. an initial mapping generator for generating an initial current fixed mapping in which said problem vertices are selectively assigned to said processing nodes; B. a prospective perturbation generator for generating prospective perturbations in response to the current mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex to another of said processing nodes; C. a perturbation selector for selecting prospective perturbations generated by said prospective perturbation generator in response to a change in the communication cost function related thereto; D. a perturbation mapping generator for generating an updated fixed mapping in response to prospective perturbations generated by said prospective perturbation generator as selected by said perturbation selector; and E. a control element for controlling operations by said prospective perturbation generator, the perturbation selector and the perturbation mapping generator in a plurality of iterations, said prospective perturbation generator and said perturbation selector using the updated fixed mapping generated by said perturbation mapping generator during one iteration as the current fixed mapping during a subsequent iteration.
Claim 38
Independent Claim
260 words
A system to facilitate the fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent a data communication pattern among the problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected by a plurality of communications links for transferring data among the processing nodes, the mapping being in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped, the system comprising: A. an initial mapping generator for generating an initial current fixed mapping in which said problem vertices are selectively assigned to said processing nodes; B. a prospective perturbation generator for generating prospective perturbations in response to the current mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex to another of said processing nodes; C. a perturbation selector for selecting prospective perturbations generated by said prospective perturbation generator in response to a change in the communication cost function related thereto; D. a perturbation mapping generator for generating an updated fixed mapping in response to prospective perturbations generated by said prospective perturbation generator as selected by said perturbation selector; and E. a control element for controlling operations by said prospective perturbation generator, the perturbation selector and the perturbation mapping generator in a plurality of iterations, said prospective perturbation generator and said perturbation selector using the updated fixed mapping generated by said perturbation mapping generator during one iteration as the current fixed mapping during a subsequent iteration.
Claim 39
Dependent Claim
39 words
A system as defined in claim 36 in which each prospective perturbation comprises a prospective reassignment of a problem vertex from one of said processing nodes to another of said processing nodes connected directly thereto by a communications link.
Claim 40
Dependent Claim
52 words
A system as defined in claim 36 in which: A. said control element initially generates a maximum occupancy value, B. said initial mapping generator assigns ghost vertices to said processing nodes, such that the number of problem vertices and ghost vertices assigned to a processing node corresponds to said maximum occupancy value.
Claim 41
Dependent Claim
76 words
A system as defined in claim 36 in which said perturbation selector includes a plurality of rendezvous nodes each associated with predetermined ones of said processing nodes, each rendezvous node selecting a prospective perturbation generated by said prospective perturbation generator for problem vertices assigned to its associated processing nodes, each rendezvous node determining a change in the communication cost function related thereto related to the prospective perturbation and selectively enabling the prospective perturbation in response thereto.
Claim 42
Dependent Claim
150 words
A system as defined in claim 39 in which each prospective perturbation identifies a prospective reassignment of a problem vertex from one processing node over one communications link to an adjacent communications link and in which: A. said control element initially generates a maximum occupancy value, B. said initial mapping generator assigns ghost vertices to said processing nodes, such that the number of problem vertices and ghost vertices assigned to a processing node corresponds to said maximum occupancy value; C. said prospective perturbation generator also generates a prospective perturbed mapping in relation to said ghost vertices; and D. each rendezvous node is associated with two processing nodes that are interconnected by a communications link, each rendezvous node selecting the same number of prospective perturbations from its associated processing nodes to maintain the number of problem vertices and ghost vertices assigned to each processing node corresponding to the maximum occupancy value.
Claim 43
Dependent Claim
23 words
A system as defined in claim 40 in which each rendezvous node selects one prospective perturbation from each of its associated processing nodes.
Claim 44
Dependent Claim
65 words
A system as defined in claim 40 in which each rendezvous node includes: A. a prospective perturbation selector for selecting a pair of prospective perturbations, the pair comprising a prospective perturbation from each of its associated processing nodes; B. a communication cost change element for determining a communication cost change value in response to the pair of prospective perturbations selected by the prospective perturbation selector.
Claim 45
Dependent Claim
51 words
A system as defined in claim 42 in which said control element generates a threshold value, and said rendezvous node further includes a comparator for comparing said communication cost change value generated by the communication cost change element to said threshold value and for enabling the prospective perturbations in response thereto.
Claim 46
Dependent Claim
20 words
A system as defined in claim 43 in which the control element generates a new threshold value for each iteration.
Claim 47
Independent Claim
370 words
A system to facilitate the fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent the pattern of communication of data between problem vertices in connection with processing of a problem, onto a problem massively parallel processor comprising a plurality of problem processing nodes interconnected by a plurality of problem communications links for transferring data among the problem processing nodes, the mapping being in relation to a communication cost function representing time to transfer data among the problem processing nodes to which the respective problem vertices have been mapped, the system comprising: A. mapping massively-parallel processor including a plurality of mapping processing nodes interconnected by mapping communications links; B. a mapping element control portion comprising: i. an initial mapping generator for generating an initial current fixed mapping in which said problem vertices are selectively assigned to said problem processing nodes, said initial mapping generator generating problem vertex tokens representing said problem vertices and enabling each problem vertex token to be loaded into its assigned mapping processing node; ii. a prospective perturbation generator for enabling said mapping processing nodes to generate prospective perturbations in response to the current mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex to another of said problem processing nodes; iii. a perturbation selector for enabling said mapping processing nodes to select prospective perturbations generated during processing in response to said prospective perturbation generator, in further response to a change in the communication cost function related thereto; and iv. a perturbation mapping generator for enabling said mapping processing nodes to generate an updated fixed mapping in response to prospective perturbations generated by said mapping processing nodes during processing in response to said prospective perturbation generator and said perturbation selector v. an iteration control element for controlling processing by said mapping processing nodes in response to the prospective perturbation generator, the perturbation selector and the perturbation mapping generator in a plurality of iterations, said mapping processing nodes, during processing in response to said prospective perturbation generator and said perturbation selector during in one iteration using as the current fixed mapping, the updated fixed mapping generated during processing in response to the perturbation mapping generator during a previous iteration.
Claim 48
Independent Claim
370 words
A system to facilitate the fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent the pattern of communication of data between problem vertices in connection with processing of a problem, onto a problem massively parallel processor comprising a plurality of problem processing nodes interconnected by a plurality of problem communications links for transferring data among the problem processing nodes, the mapping being in relation to a communication cost function representing time to transfer data among the problem processing nodes to which the respective problem vertices have been mapped, the system comprising: A. mapping massively-parallel processor including a plurality of mapping processing nodes interconnected by mapping communications links; B. a mapping element control portion comprising: i. an initial mapping generator for generating an initial current fixed mapping in which said problem vertices are selectively assigned to said problem processing nodes, said initial mapping generator generating problem vertex tokens representing said problem vertices and enabling each problem vertex token to be loaded into its assigned mapping processing node; ii. a prospective perturbation generator for enabling said mapping processing nodes to generate prospective perturbations in response to the current mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex to another of said problem processing nodes; iii. a perturbation selector for enabling said mapping processing nodes to select prospective perturbations generated during processing in response to said prospective perturbation generator, in further response to a change in the communication cost function related thereto; and iv. a perturbation mapping generator for enabling said mapping processing nodes to generate an updated fixed mapping in response to prospective perturbations generated by said mapping processing nodes during processing in response to said prospective perturbation generator and said perturbation selector v. an iteration control element for controlling processing by said mapping processing nodes in response to the prospective perturbation generator, the perturbation selector and the perturbation mapping generator in a plurality of iterations, said mapping processing nodes, during processing in response to said prospective perturbation generator and said perturbation selector during in one iteration using as the current fixed mapping, the updated fixed mapping generated during processing in response to the perturbation mapping generator during a previous iteration.
Claim 49
Dependent Claim
96 words
A system as defined in claim 45 in which, during processing in response to said perturbation selector, a plurality of mapping processing nodes are enabled to operate as rendezvous nodes, each rendezvous node being associated with predetermined ones of said mapping processing nodes, said rendezvous nodes selecting a prospective perturbation generated during processing in response to the prospective perturbation generator for problem vertices assigned to its associated processing nodes, each rendezvous node determining a change in the communication cost function related thereto related to the prospective perturbation and selectively enabling the prospective perturbation in response thereto.
Claim 50
Dependent Claim
177 words
A system as defined in claim 46 in which each prospective perturbation identifies a prospective reassignment of a problem vertex from one processing node over one communications link to an adjacent communications link and in which: A. said mapping element control portion includes a maximum occupancy value generator that generates a maximum occupancy value. B. said initial mapping generator further generates ghost vertex tokens and enables them to be loaded into said mapping processing nodes, such that the number of problem vertex tokens and ghost vertex tokens loaded into a processing node corresponds to said maximum occupancy value; C. said prospective perturbation generator also enables said mapping processing nodes to generate a prospective perturbed mapping in relation to said ghost vertex tokens; and D. each rendezvous node is associated with two mapping processing nodes that are interconnected by a communications link, each rendezvous node selecting the same number of prospective perturbations from its associated processing nodes to maintain the number of problem vertices and ghost vertices assigned to each processing node corresponding to the maximum occupancy value.
Claim 51
Dependent Claim
24 words
A system as defined in claim 47 in which each rendezvous node selects one prospective perturbation from each of its associated mapping processing nodes.
Claim 52
Dependent Claim
90 words
A system as defined in claim 47 in which the rendezvous nodes operate in response to: A. a prospective perturbation enabling portion for enabling the mapping processing nodes which are selected to be rendezvous nodes to select a pair of prospective perturbations, the pair comprising a prospective perturbation from each of its associated mapping processing nodes; B. a communication cost change enabling portion for enabling the mapping processing nodes selected to be rendezvous nodes to determine a communication cost change value in response to the pair of selected prospective perturbations.
Claim 53
Dependent Claim
77 words
A system as defined in claim 49 in which said mapping element control portion includes a threshold value generating portion that generates a threshold value, and said rendezvous nodes further operate in response to a comparator enabling portion for enabling the processing nodes which are selected to be rendezvous nodes to compare the communication cost change value generated by the communication cost change element to the threshold value and for enabling the prospective perturbations in response thereto.
Claim 54
Dependent Claim
22 words
A system as defined in claim 50 in which the threshold value generating portion generates a new threshold value for each iteration.
Claim 55
Independent Claim
126 words
A system for generating communication pattern information to direct message transfers in a predetermined pattern among processing nodes interconnected over communications links to form a massively parallel processor, to in turn facilitate communication among problem vertices mapped onto the processing nodes in a fixed pattern as defined by a problem graph, the system comprising: A. a message/communications link correspondence element for generating for each processing node fixed correspondences to facilitate the transfer of a message over a selected communications link at each processing node; and B. a communication pattern control element for controlling said message/communications link correspondence element in a series of communications link iterations, during each iteration enabling the generation of correspondences for one of a plurality of communications links for a message transfer cycle.
Claim 56
Independent Claim
126 words
A system for generating communication pattern information to direct message transfers in a predetermined pattern among processing nodes interconnected over communications links to form a massively parallel processor, to in turn facilitate communication among problem vertices mapped onto the processing nodes in a fixed pattern as defined by a problem graph, the system comprising: A. a message/communications link correspondence element for generating for each processing node fixed correspondences to facilitate the transfer of a message over a selected communications link at each processing node; and B. a communication pattern control element for controlling said message/communications link correspondence element in a series of communications link iterations, during each iteration enabling the generation of correspondences for one of a plurality of communications links for a message transfer cycle.
Claim 57
Dependent Claim
108 words
A system as defined in claim 52 in which said message/communications link correspondence element includes, for each processing node: A. a message list including a plurality of entries each associated with a message available for transfer by the processing node during the message transfer cycle; B. a priority establishment element for generating a priority value associated with each entry in said message list; and C. a communications link assignment element for using the priority values generated by said priority establishment element to associate entries in said message list with communications links connected to said processing node and for generating said communication pattern information in response to the associations.
Claim 58
Dependent Claim
71 words
A system as defined in claim 53 in which, at each processing node, each message can be transmitted over selected ones of the communications links connected thereto, said priority establishment element generates a priority value for each entry and communications link in relation to (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link.
Claim 59
Dependent Claim
70 words
A system as defined in claim 54 in which the priority value generated by the priority establishment element corresponds to the sum of (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link, the communications link assignment element generating communication pattern information for associations of entries and communications links with low priority values.
Claim 60
Dependent Claim
49 words
A system as defined in claim 52 in which said communication pattern control element further controls said message/communications link correspondence element in a series of message transfer cycle iterations, each including a plurality of communications link iterations, thereby enabling generation of correspondences for a plurality of message transfer cycles.
Claim 61
Dependent Claim
120 words
A system as defined in claim 56 in which said message/communications link correspondence element includes, for each processing node: A. a message list including a plurality of entries each associated with a message available for transfer by the processing node during the message transfer cycle, including messages determined to be transferred during a previous message transfer cycle; B. a priority establishment element for generating a priority value associated with each entry in said message list; and C. a communications link assignment element for using the priority values generated by said priority establishment element to associate entries in said message list with communications links connected to said processing node and for generating said communication pattern information in response to the associations.
Claim 62
Dependent Claim
71 words
A system as defined in claim 57 in which, at each processing node, each message can be transmitted over selected ones of the communications links connected thereto, said priority establishment element generates a priority value for each entry and communications link in relation to (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link.
Claim 63
Dependent Claim
70 words
A system as defined in claim 58 in which the priority value generated by the priority establishment element corresponds to the sum of (i) the number of communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link, the communications link assignment element generating communication pattern information for associations of entries and communications links with low priority values.
Claim 64
Independent Claim
176 words
A system for generating communication pattern information to direct message transfers in a predetermined pattern among problem processing nodes interconnected over problem communications links to form a problem massively parallel processor, to in turn facilitate communication among problem vertices mapped onto the processing nodes in a fixed pattern as defined by a problem graph, the system comprising: A. a mapping massively-parallel processor including a plurality of mapping processing nodes interconnected by mapping communications links in a predetermined pattern; B. a communication pattern control portion comprising: i. a message/communications link correspondence element for enabling said mapping processing nodes to generate for each processing node fixed correspondences to facilitate the transfer of a message over a selected communications link at each problem processing node; and ii. a communication pattern control element for enabling said mapping processing nodes to control said processing in response to said message/communications link correspondence element in a series of communications link iterations, during each iteration enabling the generation of correspondences for one of a plurality of problem communications links for a message transfer cycle.
Claim 65
Independent Claim
176 words
A system for generating communication pattern information to direct message transfers in a predetermined pattern among problem processing nodes interconnected over problem communications links to form a problem massively parallel processor, to in turn facilitate communication among problem vertices mapped onto the processing nodes in a fixed pattern as defined by a problem graph, the system comprising: A. a mapping massively-parallel processor including a plurality of mapping processing nodes interconnected by mapping communications links in a predetermined pattern; B. a communication pattern control portion comprising: i. a message/communications link correspondence element for enabling said mapping processing nodes to generate for each processing node fixed correspondences to facilitate the transfer of a message over a selected communications link at each problem processing node; and ii. a communication pattern control element for enabling said mapping processing nodes to control said processing in response to said message/communications link correspondence element in a series of communications link iterations, during each iteration enabling the generation of correspondences for one of a plurality of problem communications links for a message transfer cycle.
Claim 66
Dependent Claim
131 words
A system as defined in claim 60 in which said message/communications link correspondence element includes: A. a message list generating portion for enabling said mapping processing nodes to generate a message list including a plurality of entries each associated with a message available for transfer by the problem processing node during the message transfer cycle; B. a priority establishment element for enabling said mapping processing nodes to generate a priority value associated with each entry in said message list; and C. a communications link assignment element enabling said mapping processing nodes to use the priority values generated by said priority establishment element to associate entries in said message list with communications links connected to said respective problem processing nodes and to generate said communication pattern information in response to the associations.
Claim 67
Dependent Claim
81 words
A system as defined in claim 61 in which, at each problem processing node, each message can be transmitted over selected ones of the problem communications links connected thereto, said priority establishment element enabling said mapping processing nodes to generate a priority value for each entry and communications link in relation to (i) the number of problem communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the problem communications link.
Claim 68
Dependent Claim
83 words
A system as defined in claim 62 in which the priority value generated in response to processing controlled by the priority establishment element corresponds to the sum of (i) the number of problem communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the communications link, the communications link assignment element enabling said mapping processing nodes to generate communication pattern information for associations of entries and problem communications links with low priority values.
Claim 69
Dependent Claim
59 words
A system as defined in claim 60 in which processing in response to said communication pattern control element further enables said mapping processing nodes to process said message/communications link correspondence element in a series of message transfer cycle iterations, each including a plurality of communications link iterations, thereby enabling generation of correspondences for a plurality of message transfer cycles.
Claim 70
Dependent Claim
151 words
A system as defined in claim 64 in which said message/communications link correspondence element includes: A. a message list generating portion for enabling said mapping processing nodes to generate a message list including a plurality of entries each including a message token associated with a message available for transfer by the problem processing node during the message transfer cycle, including message tokens associated with messages determined to be transferred during a previous message transfer cycle; B. a priority establishment element for enabling said mapping processing nodes to generate a priority value associated with each entry in said message list; and C. a communications link assignment element for enabling said mapping processing nodes to use the priority values generated by said priority establishment element to associate entries in said message list with communications links connected to said mapping processing node and for generating said communication pattern information in response to the associations.
Claim 71
Dependent Claim
82 words
A system as defined in claim 65 in which, at each problem processing node, each message can be transmitted over selected ones of the problem communications links connected thereto, said priority establishment element enabling said mapping processing nodes to generate a priority value for each entry and problem communications link in relation to (i) the number of problem communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the problem communications link.
Claim 72
Dependent Claim
84 words
A system as defined in claim 66 in which the priority value generated in response to processing controlled by the priority establishment element corresponds to the sum of (i) the number of problem communications links the entry's message can be transmitted over and (ii) the number of messages that can be transmitted through the problem communications link, the communications link assignment element enabling said mapping processing node to generate communication pattern information for associations of entries and problem communications links with low priority values.
Claim 73
Dependent Claim
49 words
A system as defined in claim 65 in which the message/communications link correspondence element further includes a message token transfer element for enabling the mapping processing nodes to transfer of message tokens over the mapping communications links associated therewith after associations have been generated for a message transfer cycle.
Claim 74
Dependent Claim
47 words
A system as defined in claim 68 in which each message token has a destination pointer, said message token transfer element enabling the mapping processing nodes to adjust the values of the pointers in relation to the mapping communications link over which it transfers the message token.
Claim 75
Independent Claim
167 words
A method of establishing a fixed mapping a problem graph comprising a plurality of problem vertices interconnected by edges which represent the pattern of communication of data between problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected in a fixed pattern by a plurality of communications links for transferring data among the processing nodes, the method comprising the steps of: A. establishing a fixed mapping of said problem vertices onto said processing nodes in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped over the communications links as defined by the edges of the problem graph; and B. generating communication pattern information in connection with the established fixed mapping for use in directing message transfers among processing nodes to facilitate transfers of messages among the processing nodes over the communications links as defined by the edges of the problem graph.
Claim 76
Independent Claim
167 words
A method of establishing a fixed mapping a problem graph comprising a plurality of problem vertices interconnected by edges which represent the pattern of communication of data between problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected in a fixed pattern by a plurality of communications links for transferring data among the processing nodes, the method comprising the steps of: A. establishing a fixed mapping of said problem vertices onto said processing nodes in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped over the communications links as defined by the edges of the problem graph; and B. generating communication pattern information in connection with the established fixed mapping for use in directing message transfers among processing nodes to facilitate transfers of messages among the processing nodes over the communications links as defined by the edges of the problem graph.
Claim 77
Independent Claim
199 words
A method of establishing a fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent a data communication pattern among the problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected by a plurality of communications links for transferring data among the processing nodes, the fixed mapping being in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped, the method comprising the steps of: A. generating an initial current fixed mapping in which said problem vertices are selectively assigned to said processing nodes; and B. iteratively: (i) generating prospective perturbations in response to the current fixed mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex to another of said processing nodes; and (ii) selecting prospective perturbations in response to a change in the communication cost function related thereto, the ones of the prospective perturbations selected during an iteration effecting an actual reassignment of problem vertices to provide a new current fixed mapping for use as the current fixed mapping in a subsequent iteration.
Claim 78
Independent Claim
199 words
A method of establishing a fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent a data communication pattern among the problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected by a plurality of communications links for transferring data among the processing nodes, the fixed mapping being in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped, the method comprising the steps of: A. generating an initial current fixed mapping in which said problem vertices are selectively assigned to said processing nodes; and B. iteratively: (i) generating prospective perturbations in response to the current fixed mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex to another of said processing nodes; and (ii) selecting prospective perturbations in response to a change in the communication cost function related thereto, the ones of the prospective perturbations selected during an iteration effecting an actual reassignment of problem vertices to provide a new current fixed mapping for use as the current fixed mapping in a subsequent iteration.
Claim 79
Dependent Claim
327 words
For use in connection with a computer to facilitate the fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent the pattern of communication of data between problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected by a plurality of communications links for transferring data among the processing nodes, the mapping being in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped, a mapping element control element for controlling said computer comprising: A. an initial mapping generator element for enabling said computer to generate an initial current fixed mapping in which said problem vertices are selectively assigned to said processing nodes; B. a prospective perturbation generator element for enabling said computer to generate prospective perturbations in response to the current mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex to another of said processing nodes; C. a perturbation selector element for enabling said computer to select prospective perturbations generated during processing in response to said prospective perturbation generator, in further response to a change in the communication cost function related thereto; D. a perturbation mapping generator element for enabling said computer to generate an updated fixed mapping in response to prospective perturbations generated and selected by said computer during processing in response to said prospective perturbation generator element and said perturbation selector element; and E. an iteration control element for controlling processing by said computer in response to the prospective perturbation generator element, the perturbation selector element and the perturbation mapping generator element in a plurality of iterations, the computer, during processing in response to said prospective perturbation generator element and said perturbation selector element, using as the current fixed mapping, the updated fixed mapping generated during processing in response to said perturbation mapping generator element during a previous iteration.
Claim 80
Dependent Claim
327 words
For use in connection with a computer to facilitate the fixed mapping of a problem graph comprising a plurality of problem vertices interconnected by edges which represent the pattern of communication of data between problem vertices in connection with processing of a problem, onto a massively parallel processor comprising a plurality of processing nodes interconnected by a plurality of communications links for transferring data among the processing nodes, the mapping being in relation to a communication cost function representing time to transfer data among the processing nodes to which the respective problem vertices have been mapped, a mapping element control element for controlling said computer comprising: A. an initial mapping generator element for enabling said computer to generate an initial current fixed mapping in which said problem vertices are selectively assigned to said processing nodes; B. a prospective perturbation generator element for enabling said computer to generate prospective perturbations in response to the current mapping, each prospective perturbation comprising a prospective reassignment of a problem vertex to another of said processing nodes; C. a perturbation selector element for enabling said computer to select prospective perturbations generated during processing in response to said prospective perturbation generator, in further response to a change in the communication cost function related thereto; D. a perturbation mapping generator element for enabling said computer to generate an updated fixed mapping in response to prospective perturbations generated and selected by said computer during processing in response to said prospective perturbation generator element and said perturbation selector element; and E. an iteration control element for controlling processing by said computer in response to the prospective perturbation generator element, the perturbation selector element and the perturbation mapping generator element in a plurality of iterations, the computer, during processing in response to said prospective perturbation generator element and said perturbation selector element, using as the current fixed mapping, the updated fixed mapping generated during processing in response to said perturbation mapping generator element during a previous iteration.
Claim 81
Dependent Claim
140 words
For use in connection with a computer to generate communication pattern information to direct message transfers in a predetermined pattern among processing nodes interconnected over communications links to form a massively parallel processor, to in turn facilitate communication among problem vertices mapped onto the processing nodes in a fixed pattern as defined by a problem graph, a communication pattern control element comprising: A. message/communications link correspondence element for enabling said computer to generate fixed correspondences to facilitate the transfer of a message over a selected communications link at each processing node; and B. a communication pattern control element for controlling processing by said computer in connection with said message/communications link correspondence element in a series of communications link iterations, during each iteration enabling the generation of correspondences for one of a plurality of communications links for a message transfer cycle.
Claim 82
Dependent Claim
140 words
For use in connection with a computer to generate communication pattern information to direct message transfers in a predetermined pattern among processing nodes interconnected over communications links to form a massively parallel processor, to in turn facilitate communication among problem vertices mapped onto the processing nodes in a fixed pattern as defined by a problem graph, a communication pattern control element comprising: A. message/communications link correspondence element for enabling said computer to generate fixed correspondences to facilitate the transfer of a message over a selected communications link at each processing node; and B. a communication pattern control element for controlling processing by said computer in connection with said message/communications link correspondence element in a series of communications link iterations, during each iteration enabling the generation of correspondences for one of a plurality of communications links for a message transfer cycle.
References Cited (Backward Citations)
US4247892A
Cited
US4380046A
Cited
US4435758A
Cited
US4621339A
Cited
US4972314A
Cited
US4730322A
Cited
US4814980A
Cited
US4933933A
Cited
US4922413A
Cited
US4920487A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-09-20 | 1997-03-22 | 1997-09-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-09-20 | 2001-03-22 | 2001-09-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-09-20 | 2005-03-22 | 2005-09-21 | $7700.00 | Window Closed / Lapsed |