This code will deadlock for blocking send/receive. One solution is to send/receive to the thread under you, and then send/receive to the thread above you. In this way, thread 0 will receive first since it has nothing to send, and the receives will cascade upwards, and then cascade back downwards, for the second round of message passing since thread N-1 has nothing to send and thus will receive first. However, this ends up making all communications sequential.
A far better solution is for even rows to send first while odd rows receive first so we can communicate in parallel.
This comment was marked helpful 0 times.
FooManchu
What might an optimal message passing algorithm be in a two or three dimensional system?
A naive solution, an extension of that above, can run in time linear with the maximum dimension, by sending towards one corner, receiving those, sending towards the opposite corner and then receiving those.
This comment was marked helpful 0 times.
danielk2
Just to add an example of deadlock situation: If every processors send a row to the neighboring processor (blocking send), then every processors would have to wait for the blocking send to return. However, since every processors are doing blocking sending and wait, no thread can perform blocking receive. Thus, the program deadlocks as every processors are waiting for their blocking send to return.
This comment was marked helpful 1 times.
Mayank
@FooManchu: For 2D case i wonder if a red-black pattern as in the solver example work? All red cells will send and all black ones will receive. This way all the blocking sends of the red cells will be acknowledged by the receive call of black ones and then the roles can be reversed where all black cells send and all red ones receive.
One thing we might have to take care is that if the sequence of send call from red cells is: send(right) send(left) send(top) send(bottom)
Then the receive calls from black cells should be in the following order: receive(left) receive(right) receive(bottom) receive(top)
If the order of receive is first right followed by left, then it will result in a deadlock.
This comment was marked helpful 0 times.
kailuo
@Mayank I think your proposed solution is increasing the total amount of communications by a huge amount, and the overhead of such communications will offset any benefits gained.
This code will deadlock for blocking send/receive. One solution is to send/receive to the thread under you, and then send/receive to the thread above you. In this way, thread 0 will receive first since it has nothing to send, and the receives will cascade upwards, and then cascade back downwards, for the second round of message passing since thread N-1 has nothing to send and thus will receive first. However, this ends up making all communications sequential.
A far better solution is for even rows to send first while odd rows receive first so we can communicate in parallel.
This comment was marked helpful 0 times.
What might an optimal message passing algorithm be in a two or three dimensional system?
A naive solution, an extension of that above, can run in time linear with the maximum dimension, by sending towards one corner, receiving those, sending towards the opposite corner and then receiving those.
This comment was marked helpful 0 times.
Just to add an example of deadlock situation: If every processors send a row to the neighboring processor (blocking send), then every processors would have to wait for the blocking send to return. However, since every processors are doing blocking sending and wait, no thread can perform blocking receive. Thus, the program deadlocks as every processors are waiting for their blocking send to return.
This comment was marked helpful 1 times.
@FooManchu: For 2D case i wonder if a red-black pattern as in the solver example work? All red cells will send and all black ones will receive. This way all the blocking sends of the red cells will be acknowledged by the receive call of black ones and then the roles can be reversed where all black cells send and all red ones receive. One thing we might have to take care is that if the sequence of send call from red cells is:
send(right)send(left)send(top)send(bottom)Then the receive calls from black cells should be in the following order:
receive(left)receive(right)receive(bottom)receive(top)If the order of receive is first right followed by left, then it will result in a deadlock.
This comment was marked helpful 0 times.
@Mayank I think your proposed solution is increasing the total amount of communications by a huge amount, and the overhead of such communications will offset any benefits gained.
This comment was marked helpful 0 times.