I was wondering during class if there are many situations where it is worth redoing substantial work to avoid communication costs. In this example, workers might consider computing the values for an extra row on both of their borders on the even iterations. Then they would have to communicate four rows after every odd iteration instead of two rows every iteration. This might be beneficial if latency for communication was very high.
kayvonf
Yes, there are certainly situations where duplicating some work to reduce communication costs is a good implementation strategy. I recommend you come back to this comment after Assignment 2.
BigFish
@kayvonf How is this related to Assignment 2? My strategy in Assignment 2 is to divide pixel into regions and test what circles those regions intersect with, which is the idea of a bloom filter to eliminate most circles that make no contributions to pixels in the region. And then I parallel on pixels to check if those circles are actually making contribution to the pixels in that region. I reduced the amount of computation by applying the bloom filter. Is there other good strategies more related to reducing communication costs?
paluri
@BigFish, I suspect @kayvonf was referring to the prefix sum usage, where you do some task A marking say 1s and 0s in an array, then you use prefix sum to get the indices of each "1" case, and then repeat task A again, this time, on a "1" being able to immediately access the index. Even though you are doing the task A twice, it is still a super efficient way (the most efficient?) to access the indices and compress the "1" cases.
kayvonf
@paluri, @BigFish. Actually I was referring to extra circle-in-tile testing work (as compared to a sequential implementation) done by parallel implementations that produced no data structure out in memory, and instead processed each output screen tile completely independently in a single kernel. The lack of communication (or memory traffic) was good... but it comes at the cost of performing extra work.
I was wondering during class if there are many situations where it is worth redoing substantial work to avoid communication costs. In this example, workers might consider computing the values for an extra row on both of their borders on the even iterations. Then they would have to communicate four rows after every odd iteration instead of two rows every iteration. This might be beneficial if latency for communication was very high.
Yes, there are certainly situations where duplicating some work to reduce communication costs is a good implementation strategy. I recommend you come back to this comment after Assignment 2.
@kayvonf How is this related to Assignment 2? My strategy in Assignment 2 is to divide pixel into regions and test what circles those regions intersect with, which is the idea of a bloom filter to eliminate most circles that make no contributions to pixels in the region. And then I parallel on pixels to check if those circles are actually making contribution to the pixels in that region. I reduced the amount of computation by applying the bloom filter. Is there other good strategies more related to reducing communication costs?
@BigFish, I suspect @kayvonf was referring to the prefix sum usage, where you do some task A marking say 1s and 0s in an array, then you use prefix sum to get the indices of each "1" case, and then repeat task A again, this time, on a "1" being able to immediately access the index. Even though you are doing the task A twice, it is still a super efficient way (the most efficient?) to access the indices and compress the "1" cases.
@paluri, @BigFish. Actually I was referring to extra circle-in-tile testing work (as compared to a sequential implementation) done by parallel implementations that produced no data structure out in memory, and instead processed each output screen tile completely independently in a single kernel. The lack of communication (or memory traffic) was good... but it comes at the cost of performing extra work.