Does anyone know why compare parallel program speedup to parallel algorithm running on one core can make result look good?
afzhang
@amaliujia: It's because it's not fair to compare a parallel program running on one core to a parallel program running on multiple cores. A more reasonable comparison would be the best/most optimized sequential algorithm running on one core vs. a parallel program on many cores. A parallel program might have overhead costs that the most optimized sequential algorithm avoids.
VP7
yes, afzhang is right. For example, in order to avoid serialization/ dependency on shared data we might add the overhead of replicating data. The cost for this will be quite high for a parallelized algorithm running on single core. But it get amortized when you have multiple cores. (I know this example is oversimplified, neglecting the factors like cache coherence, but it still explains the crux of the idea).
Kapteyn
To add, just think about the amount of work that has to be done in the data parallel sort version. For each particle we determine which cell it belongs to, that's P work. Then we sort the array by cell values, that' O(PlogP) work. Then have to find out where the cell values start and end in the array, which is another P work and finally we do the subtraction of cell ends minus cell starts for each cell to get their counts and write that to the final cell counts array, which is another P work.
So doing the parallel algorithm on one core would take 3P + PlogP work which is silly because we can do accomplish the same task with a simple sequential algorithm that just goes over each particle, finds the cell it belongs to and increments the count for that cell which only requires P work.
We incurred extra work in the data parallel version to avoid serialization caused by locks which slowed our parallel implementation down. The extra work is only a worthwhile tradeoff under the assumption that we have multiple cores that can do much of the work at the same time.
Does anyone know why compare parallel program speedup to parallel algorithm running on one core can make result look good?
@amaliujia: It's because it's not fair to compare a parallel program running on one core to a parallel program running on multiple cores. A more reasonable comparison would be the best/most optimized sequential algorithm running on one core vs. a parallel program on many cores. A parallel program might have overhead costs that the most optimized sequential algorithm avoids.
yes, afzhang is right. For example, in order to avoid serialization/ dependency on shared data we might add the overhead of replicating data. The cost for this will be quite high for a parallelized algorithm running on single core. But it get amortized when you have multiple cores. (I know this example is oversimplified, neglecting the factors like cache coherence, but it still explains the crux of the idea).
To add, just think about the amount of work that has to be done in the data parallel sort version. For each particle we determine which cell it belongs to, that's P work. Then we sort the array by cell values, that' O(PlogP) work. Then have to find out where the cell values start and end in the array, which is another P work and finally we do the subtraction of cell ends minus cell starts for each cell to get their counts and write that to the final cell counts array, which is another P work.
So doing the parallel algorithm on one core would take 3P + PlogP work which is silly because we can do accomplish the same task with a simple sequential algorithm that just goes over each particle, finds the cell it belongs to and increments the count for that cell which only requires P work.
We incurred extra work in the data parallel version to avoid serialization caused by locks which slowed our parallel implementation down. The extra work is only a worthwhile tradeoff under the assumption that we have multiple cores that can do much of the work at the same time.