What's the motivation behind this parallelization scheme? What other partitioning/parallelization schemes would also perform well?
bob_sacamano
I believe that this approximate approach is used, because, this is an iterative algorithm that continues to execute until the convergence condition is met. The idea is that since every element is dependent on the values propagated by its neighbours in each iteration and the number of iterations are likely to be large, the error due to approximation will eventually be smoothed out. The PageRank algorithm is parallelized using this similar approximation approach. Since the nodes in the web graph will have large number of dependencies, the parallelization idea is to only consider the scores from in-edges and propagate the new score to adjacent nodes only in the next iteration.
LazyKiller
If we choose the partition of red-black coloring. We are not only changing the implementation but also changing the algorithm itself. Although Prof.Mowry said it is okay because this method's only doing blur. I still wonder that change will increase the iteration number? Or if the partition is equivalent to change an algorithm?
What's the motivation behind this parallelization scheme? What other partitioning/parallelization schemes would also perform well?
I believe that this approximate approach is used, because, this is an iterative algorithm that continues to execute until the convergence condition is met. The idea is that since every element is dependent on the values propagated by its neighbours in each iteration and the number of iterations are likely to be large, the error due to approximation will eventually be smoothed out. The PageRank algorithm is parallelized using this similar approximation approach. Since the nodes in the web graph will have large number of dependencies, the parallelization idea is to only consider the scores from in-edges and propagate the new score to adjacent nodes only in the next iteration.
If we choose the partition of red-black coloring. We are not only changing the implementation but also changing the algorithm itself. Although Prof.Mowry said it is okay because this method's only doing blur. I still wonder that change will increase the iteration number? Or if the partition is equivalent to change an algorithm?