Parallel program execution time with message consolidation
First Claim
1. A method of determining which messages in a program for a distributed memory parallel processor system can be merged without causing deadlock of the system when the program is run, comprising the steps of:
- (a) determining regions in the code allocated to each processor, where new regions begin at the receive statements of entering messages;
(b) identifying two consecutive outgoing messages to a second processor and sent from a first processor, where outgoing messages will be consecutive when considering only messages going to the second processor;
(c) checking if the two consecutive messages are crossed, with crossed messages having a first receive statement whose message is sent first from the first processor, said first receiving statement being located after the receive statement which is to receive the outgoing message from the second consecutive outgoing message; and
(d) determining for non-crossed messages whether there is a chain that originates between the two receive statements and terminates between the two send statements for the consecutive messages being considered for merging and not merging the messages if such a path is found, thereby avoiding deadlock.
1 Assignment
0 Petitions
Accused Products
Abstract
In distributed memory multiprocessors, communication between processing elements (PEs) can have a significant impact on the overall computation time. In addition, contention for the communication links can often make PEs wait even longer for a message than would normally be required. Because of this, it is important to minimize the effects of inter-processor communication time. The present invention reduces the execution time of a parallel program by merging messages (also called message combining, or message consolidation) after the program has already been partitioned and scheduled onto the PEs. The data from two (or more) messages are combined and sent in a single communication by locating sections of the system where a merge will affect the overall execution time, and determining before the merge takes place whether it will positively or negatively affect the system.
-
Citations
7 Claims
-
1. A method of determining which messages in a program for a distributed memory parallel processor system can be merged without causing deadlock of the system when the program is run, comprising the steps of:
-
(a) determining regions in the code allocated to each processor, where new regions begin at the receive statements of entering messages; (b) identifying two consecutive outgoing messages to a second processor and sent from a first processor, where outgoing messages will be consecutive when considering only messages going to the second processor; (c) checking if the two consecutive messages are crossed, with crossed messages having a first receive statement whose message is sent first from the first processor, said first receiving statement being located after the receive statement which is to receive the outgoing message from the second consecutive outgoing message; and (d) determining for non-crossed messages whether there is a chain that originates between the two receive statements and terminates between the two send statements for the consecutive messages being considered for merging and not merging the messages if such a path is found, thereby avoiding deadlock.
-
-
2. A method carried out on a computer of merging two or more messages of a program for a distributed memory parallel processor system, so that the messages can be sent as one message to reduce the overall computation time and bus loading of the system while running the program, after the program that has been scheduled, comprising the steps of:
-
(a) determining regions in the program code allocated to each processor, where new regions begin at the receive statements of entering messages; (b) estimating start time of each region based on whether it takes longer for the execution of the previous region to be completed than for the message to arrive which defines the beginning of the region, or if it takes longer for the message to arrive which defines the beginning of the region than the time the previous region takes to complete its execution; (c) identifying two consecutive outgoing messages from a first processor to a second processor, where outgoing messages will be consecutive when considering only messages going to the second processor; (d) checking if the two consecutive messages are crossed, with crossed messages having a first receive statement whose message is sent first from the first processor, the first receive statement being located after the receive statement which is to receive the outgoing message from the second consecutive outgoing message; and (e) determining for non-crossed messages whether there is a chain that originates between the two receive statements and terminates between the two send statements for the consecutive messages being considered for merging and not merging the messages if such a path is found, thereby avoiding deadlock. - View Dependent Claims (3, 4, 5, 6, 7)
-
Specification