Go backward to Block-Oriented Algorithm Go up to Top Go forward to References

Analysis of Algorithm

n² matrix, p processors.

• Row-Column-oriented algorithm
  • Computation: n²/p*n/p = n³/p².
  • Communication: 2(lambda + beta n²/p)
  • p iterations.
• Block-oriented algorithm
  • Computation: n²/p*n/p = n³/p².
  • Communication: 4(lambda + beta n²/p)
  • sqrt(p)-1 iterations.
• Comparison

  2p (lambda + beta n²/p) > 4 (sqrt(p)-1) (lambda + beta n²/p)
  lambda p + beta n² > 4 lambda (sqrt(p)-1) + 4 beta (sqrt(p)-1) n²/p

  1. p > 4 (sqrt p-1) -> p > 4
  2. 1 > 4 (sqrt p-1)/p -> p > 4

For larger processor numbers, communication dominates computation!