Go backward to The Isoefficiency Concept Go up to Top Go forward to More Performance Parameters

Scalability of Matrix Multiplication

• n processors, s xs matrix.
• Workload w(s) = O(s³).
• Overhead h(s,n)=O(nlogn + s² sqrt(n))
• w(s) approx.h(s,n)
  1. O(s³) = O(n logn)
  2. O(s³) = O(s² sqrt(n)) =>O(s) = O(sqrt(n)) =>O(s³) = O(n sqrt(n))
• Isoefficiency f_E(n) = O(nsqrt(n))
• Matrix size s = O(sqrt(n))

Matrix size s must grow with at least sqrt(n)!