I'm confused as to the difference between having the even threads send and odd threads receive, in regards to which send and which receive we are talking about. What's the difference between the outer send and receive vs inner send and receive that would result in a parallel vs sequential communication?
This program is wrong if the send and receive here is synchronized, in which all the threads will busy in sending their message and never running other instructions.
On the contrary, if we let odd threads receive first and even threads send first, look here, there will not be dead lock.
In class we talked about fixing this code when the sends and receives are synchronous. One suggested solution was if the even threads do 2 sends to the odd threads then do 2 receives. So for example, for thread i, (i is even), i sends to i+1 and then i-1, and then i receives from i+1 and i-1. However, Prof. Kayvon said that may not quite work due to some sort of cascade effect. Could someone please explain why this strategy may not work?
@eknight7 The cascade effects probably consists of two things: if the send and receive are synchronous, then they are blocking calls. Then no work would actually be parallelized because of blocking.
Also this might result in deadlock, when every thread is "holding" send, and "wanting" receive.
The program is problematic mainly because send() is only returned when the sender receives the acknowledgment from the receiver (the ACK message). But the receiver of this message is not able to receive anything before it sends out its own messages.
This results in deadlock!
I agree with @PandaX, the code above result in deadlock since each sender is also waiting to receive a message before it sends.
This was shown in class when we tried to send a message to the row in front of us and we ourselves had to wait for acknowledgement before receiving a message coming from the back.