Block assignment here is a better split in terms of the communication overhead needed to go across processors. However, the "solution" that both splits find should be the same given the same starting point. Even though this scenario has better (or at least easier) parallelism to carry out compared to the first algorithm proposed by professor, the solutions they found should be very different. Although I don't know which one will converge better in this case, but parallelism is not our first concern here, the quality of the solution arguably is.
top
@Jing I am a little confused about your comment. How will these two solutions give different answers? I thought that both solutions given in class were performing the same operations, just in a different order. So it should be true that both will converge to the same answer, just that this implementation has better parallelism.
dsaksena
@Jing blocked assignment vs the interleaved assignment will give us the same answer, the difference is I have lesser message passing (orchestration) which is computationally expensive.
The initial method and the red black dot method will give different answers but it is an accepted approximation as kayvon informed us in his class.
vrazdan
While later on we realize that the interleaved assignment does lead to more communication overhead, most likely slowing down performance, I would think that there is better cache performance from the interleaving assignment rather than blocking, merely because the memory being computed on concurrently are all closer to each other. Is there a way to know just how much worse the added communication overhead is compared to the potentially better caching?
mangocourage
@vrazdan I fail to see how the blocked assignment would have much worse cache performance than the interleaving assignment. If anything it seems that the interleaved assignment works on data that is further apart
Sherry
@vrazdan I suppose the cache performance of interleaving assignment would be very bad because of false sharing. Every update of P1 could lead to an invalid cache line in P2. I am not quiet sure about this, if someone can help prove or disprove this?
yuel1
@Sherry as it turns out from the later cache lectures, you are indeed correct.
Block assignment here is a better split in terms of the communication overhead needed to go across processors. However, the "solution" that both splits find should be the same given the same starting point. Even though this scenario has better (or at least easier) parallelism to carry out compared to the first algorithm proposed by professor, the solutions they found should be very different. Although I don't know which one will converge better in this case, but parallelism is not our first concern here, the quality of the solution arguably is.
@Jing I am a little confused about your comment. How will these two solutions give different answers? I thought that both solutions given in class were performing the same operations, just in a different order. So it should be true that both will converge to the same answer, just that this implementation has better parallelism.
@Jing blocked assignment vs the interleaved assignment will give us the same answer, the difference is I have lesser message passing (orchestration) which is computationally expensive.
The initial method and the red black dot method will give different answers but it is an accepted approximation as kayvon informed us in his class.
While later on we realize that the interleaved assignment does lead to more communication overhead, most likely slowing down performance, I would think that there is better cache performance from the interleaving assignment rather than blocking, merely because the memory being computed on concurrently are all closer to each other. Is there a way to know just how much worse the added communication overhead is compared to the potentially better caching?
@vrazdan I fail to see how the blocked assignment would have much worse cache performance than the interleaving assignment. If anything it seems that the interleaved assignment works on data that is further apart
@vrazdan I suppose the cache performance of interleaving assignment would be very bad because of false sharing. Every update of P1 could lead to an invalid cache line in P2. I am not quiet sure about this, if someone can help prove or disprove this?
@Sherry as it turns out from the later cache lectures, you are indeed correct.