If I understand the solution correctly, then even and odd number of threads alternate between sending and receiving there is concurrency between threads that are sending.
makingthingsfast
Yes, that is true. As the example in class showed (where each person in each row said hi to the person ahead of him/her in the next row), if every thread is sending a message to the thread "ahead," each thread has to wait for that other thread to communicate back indicating that it has received the message. This delay is not efficient. Thus, the division into every other thread doing one action is beneficial.
TanXiaoFengSheng
Is it ok for even threads do sendDown(), sendUp(), recvDown(),recvUp; while odd threads do recvUp(), recvDown(), sendUp(), sendDown()? looks no deadlock to me. But I do remember that Kayvon said there was a way that might cause deadlock but I forgot exactly what it was.
msfernan
@TanXiaoFengSheng
Kayvon said that there would be no deadlock with this method. Deadlock would occur if all threads were waiting on each other to complete the send and receive. i.e. all threads waiting to receive or all threads waiting to send such as in the example on lecture 7, slide 9
I think the point of having both the even and odd numbered threads alternate between a send and a receive instead of having the all the even row numbered threads send first while the odd row numbered threads receive first and then alternating based on the row is that we want to parallelize the send and receive. We want to be able to send and receive at the same time. Otherwise we would end up writing a correct program but a sequential one.
PandaX
@msfernan But how is the proposed apporach sequential? It looks a parallel process to me.
Can someone clarify this point?
PandaX
If we let even row perform this:
sendDown();
sendUp();
Odd row perform this
recvUp();
recvDown();
It will also work. CMIIW
jrgallag
@PandaX, I believe you're correct. That program would still be perfectly parallel, the only difference between that and the solution in the slide is the order of data sent.
The sequential implementation that was discussed in lecture would be doing something like this:
if (tid != 0)
sendDown();
if (tid != get_num_threads() - 1) {
recvUp();
sendUp();
}
if (tid != 0)
recvDown();
In this case, after the sendDown call all threads would be block except the one with id 0, which could receive the data, allowing the next to receive, and so on. So this implementation would not deadlock, but would be entirely sequential.
If I understand the solution correctly, then even and odd number of threads alternate between sending and receiving there is concurrency between threads that are sending.
Yes, that is true. As the example in class showed (where each person in each row said hi to the person ahead of him/her in the next row), if every thread is sending a message to the thread "ahead," each thread has to wait for that other thread to communicate back indicating that it has received the message. This delay is not efficient. Thus, the division into every other thread doing one action is beneficial.
Is it ok for even threads do sendDown(), sendUp(), recvDown(),recvUp; while odd threads do recvUp(), recvDown(), sendUp(), sendDown()? looks no deadlock to me. But I do remember that Kayvon said there was a way that might cause deadlock but I forgot exactly what it was.
@TanXiaoFengSheng
Kayvon said that there would be no deadlock with this method. Deadlock would occur if all threads were waiting on each other to complete the send and receive. i.e. all threads waiting to receive or all threads waiting to send such as in the example on lecture 7, slide 9
I think the point of having both the even and odd numbered threads alternate between a send and a receive instead of having the all the even row numbered threads send first while the odd row numbered threads receive first and then alternating based on the row is that we want to parallelize the send and receive. We want to be able to send and receive at the same time. Otherwise we would end up writing a correct program but a sequential one.
@msfernan But how is the proposed apporach sequential? It looks a parallel process to me.
Can someone clarify this point?
If we let even row perform this:
Odd row perform this
It will also work. CMIIW
@PandaX, I believe you're correct. That program would still be perfectly parallel, the only difference between that and the solution in the slide is the order of data sent.
The sequential implementation that was discussed in lecture would be doing something like this:
In this case, after the
sendDowncall all threads would be block except the one with id 0, which could receive the data, allowing the next to receive, and so on. So this implementation would not deadlock, but would be entirely sequential.