1. Derivation of Sun-Ni's Law

Let [math]\displaystyle{ \textstyle W^{*} }[/math] be the scaled workload under a memory space constraint. The memory bounded speedup can be defined as:

Sequential Time to Solve W*/Parallel Time to Solve W* 

Suppose [math]\displaystyle{ \textstyle f }[/math] is the portion of the workload that can be parallelized and [math]\displaystyle{ \textstyle(1-f) }[/math] is the sequential portion of the workload.

Let [math]\displaystyle{ \textstyle y = g(x) }[/math] be the function that reflects the parallel workload increase factor as the memory capacity increases m times.

Let: [math]\displaystyle{ \textstyle W = g(M) }[/math] and: [math]\displaystyle{ \textstyle W^{*} = g(m\cdot M) }[/math] where [math]\displaystyle{ \textstyle M }[/math] is the memory capacity of one node.

Thus, [math]\displaystyle{ W^{*} = g(m\cdot g^{-1}(W)) }[/math]

The memory bounded speedup is then:

[math]\displaystyle{ \frac{(1-f)W + f\cdot g(m\cdot g^{-1}(W))}{(1-f)W + \frac{f\cdot g(m\cdot g^{-1}(W))}{m}} }[/math]

For any power function [math]\displaystyle{ \textstyle g(x) = ax^{b} }[/math] and for any rational numbers a and b, we have:

[math]\displaystyle{ g(mx) = a(mx)^{b} = m^{b}\cdot ax^{b} = m^{b}g(x) = \bar{g}(m)g(x) }[/math]

where [math]\displaystyle{ \textstyle \bar{g}(m) }[/math] is the power function with the coefficient as 1.

Thus by taking the highest degree term to determine the complexity of the algorithm, we can rewrite memory bounded speedup as:

[math]\displaystyle{ \frac{(1-f)W + f\cdot \bar{g}(m)W}{(1-f)W + \frac{f\cdot \bar{g}(m)W}{m}} = \frac{(1-f) + f\cdot \bar{g}(m)}{(1-f) + \frac{f\cdot \bar{g}(m)}{m}} }[/math]

In this equation, [math]\displaystyle{ \textstyle \bar{g}(m) }[/math] represents the influence of memory change on the change in problem size.

Suppose [math]\displaystyle{ \textstyle \bar{g}(m) =1 }[/math], Then the memory-bounded speedup model reduces to Amdahl's law, since problem size is fixed or independent of resource increase.

Suppose [math]\displaystyle{ \textstyle \bar{g}(m)=m }[/math], Then the memory-bounded speedup model reduces to Gustafson's law, which means when memory capacity increases m times and the workload also increases m times all the data needed is local to every node in the system.

Often, for simplicity and for matching the notation of Amdahl's Law and Gustafson's Law, the letter G is used to represent the memory bound function [math]\displaystyle{ \textstyle \bar{g}(m) }[/math], and n replaces m. Using this notation we get:

[math]\displaystyle{ Speedup_\text{memory-bounded} = \frac{(1-f) + f\cdot G(n)}{(1-f) + \frac{f\cdot G(n)}{n}} }[/math]

2. Examples

Suppose one would like to determine the memory-bounded speedup of matrix multiplication. The memory requirement of matrix multiplication is roughly [math]\displaystyle{ \textstyle x = 3N^{2} }[/math] where N is the dimension of the two N X N source matrices. And the computation requirement is [math]\displaystyle{ 2N^{3} }[/math]

Thus we have:

[math]\displaystyle{ g(x) = 2(x/3)^{3/2} = \frac{2}{3^{3/2}}x^{3/2} }[/math] and [math]\displaystyle{ \bar{g}(x) = x^{3/2} }[/math]

Thus the memory-bounded speedup is for matrix multiplication is:

[math]\displaystyle{ \frac{(1-f) + f\cdot \bar{g}(m)}{(1-f) + \frac{f\cdot \bar{g}(m)}{m}} = \frac{(1-f) + f\cdot m^{3/2}}{(1-f) + f\cdot m^{1/2}} }[/math]

The following is another matrix multiplication example which illustrates the rapid increase in parallel execution time.^[1] The execution time of a N X N matrix for a uniprocessor is:[math]\displaystyle{ O(n^{3}) }[/math]. While the memory usage is: [math]\displaystyle{ O(n^{2}) }[/math]

Suppose a 10000-by-10000 matrix takes 800 MB of memory and can be factorized in 1 hour on a uniprocessor. Now for the scaled workload suppose is possible to factorize a 320,000-by-320,000 matrix in 32 hours. The time increase is quite large, but the increase in problem size may be more valuable for someones whose premier goal is accuracy. For example, an astrophysicist may be more interested in simulating an N-body problem with as the number of particles as large as possible.^[1] This example shows for computation intensive applications, memory capacity does not need to proportionally scale up with computing power.

3. Applications/Effects of Sun-Ni's Law

The memory-bounded speedup model is the first work to reveal that memory is the performance constraint for high-end computing and presents a quantitative mathematical formulation for the trade-off between memory and computing. It is based on the memory-bounded function,W=G(n), where W is the work and thus also the computation for most applications. M is the memory requirement in terms of capacity, and G is the reuse rate. W=G(M) gives a very simple, but effective, description of the relation between computation and memory requirement. From an architecture viewpoint, the memory-bounded model suggests the size, as well as speed, of the cache(s) should match the CPU performance. Today, modern microprocessors such as the Pentium Pro, Alpha 21164, Strong Arm SA110, and Longson-3A use 80% or more of their transistors for the on-chip cache rather than computing components. From an algorithm design viewpoint, we should reduce the number of memory accesses. That is, reuse the data when it is possible. The function G() gives the reuse rate. Today, the term memory bound functions has become a general term which refers to functions which involve extensive memory access.^[2] Memory complexity analysis has become a discipline of computer algorithm analysis.