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
3
)
.
Overhead
h(s,n)=O(nlogn + s
2
n
)
w(s) approx.h(s,n)
O(s
3
) = O(n logn)
O(s
3
) = O(s
2
n
) =>O(s) = O(
n
) =>O(s
3
) = O(n
n
)
Isoefficiency
f
E
(n) = O(n
n
)
Matrix size
s = O(
n
)
Matrix size
s
must grow with at least
n
!
Author:
Wolfgang Schreiner
Last modification: November 8, 1996