Sun–Ni law

Within theoretical computer science, the Sun–Ni law (or Sun and Ni's law, also known as memory-bounded speedup) is a memory-bounded speedup model which states that as computing power increases the corresponding increase in problem size is constrained by the system’s memory capacity. In general, as a system grows in computational power, the problems run on the system increase in size. Analogous to Amdahl's law, which says that the problem size remains constant as system sizes grow, and Gustafson's law, which proposes that the problem size should scale but be bound by a fixed amount of time, the Sun–Ni law states the problem size should scale but be bound by the memory capacity of the system. Sun–Ni law ^[1][2] was initially proposed by Xian-He Sun and Lionel Ni at the Proceedings of IEEE Supercomputing Conference 1990.

With the increasing disparity between CPU speed and memory data access latency, application execution time often depends on the memory speed of the system.^[3] As predicted by Sun and Ni, data access has become the premier performance bottleneck for high-end computing. From this one can see the intuition behind the law; as system resources increase, applications are often bottlenecked by memory speed and bandwidth, thus an application can achieve a larger speedup by utilizing all the memory capacity in the system. The law can be applied to different layers of a memory hierarchy system, from L1 cache to main memory. Through its memory-bounded function, W=G(M), it reveals the trade-off between computing and memory in algorithm and system architecture design.

All three speedup models, Sun–Ni, Gustafson, and Amdahl, provide a metric to analyze speedup for parallel computing. Amdahl’s law focuses on the time reduction for a given fixed-size problem. Amdahl’s law states that the sequential portion of the problem (algorithm) limits the total speedup that can be achieved as system resources increase. Gustafson’s law suggests that it is beneficial to build a large-scale parallel system as the speedup can grow linearly with the system size if the problem size is scaled up to maintain a fixed execution time.^[4] Yet as memory access latency often becomes the dominant factor in an application’s execution time,^[5] applications may not scale up to meet the time bound constraint.^[1][2] The Sun–Ni law, instead of constraining the problem size by time, constrains the problem by the memory capacity of the system, or in other words bounds based on memory. The law is a generalization of Amdahl's Law and Gustafson's Law. When the memory-bounded function G(M)=1, it resolves to Amdahl's law; when the memory-bounded function G(M)=m, the number of processors, it resolves to Gustafson's law.

Derivation

Let ${\displaystyle \textstyle W^{*}}$  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 ${\displaystyle \textstyle f}$  is the portion of the workload that can be parallelized and ${\displaystyle \textstyle (1-f)}$  is the sequential portion of the workload.

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

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

Thus, ${\displaystyle W^{*}=g(m\cdot g^{-1}(W))}$ 

The memory bounded speedup is then:

${\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}}}}}$ 

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

${\displaystyle g(mx)=a(mx)^{b}=m^{b}\cdot ax^{b}=m^{b}g(x)={\bar {g}}(m)g(x)}$ 

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

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

${\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}}}}}$ 

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

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

Suppose ${\displaystyle \textstyle {\bar {g}}(m)=m}$ , 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 ${\displaystyle \textstyle {\bar {g}}(m)}$ , and n replaces m. Using this notation one gets:

${\displaystyle Speedup_{\text{memory-bounded}}={\frac {(1-f)+f\cdot G(n)}{(1-f)+{\frac {f\cdot G(n)}{n}}}}}$ 

Examples

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

Thus we have:

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

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

${\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}}}}$ 

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

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.^[6] This example shows for computation intensive applications, memory capacity does not need to proportionally scale up with computing power.

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.^[7] Memory complexity analysis has become a discipline of computer algorithm analysis.

References

1. [1] Another View on Parallel Speedup, Xian-He Sun and Lionel Ni, Proceedings of IEEE Supercomputing Conference '90.
2. [2] Scalable Problems and Memory-Bounded Speedup, X.H. Sun, and L. Ni, Journal of Parallel and Distributed Computing, Vol. 19, p. 27–37, Sept. 1993.
3. [3] Hitting the Memory Wall:Implications of the Obvious, Wm.A. Wulf and Sally A. McKee, ACM SIGARCH Computer Architecture News Vol. 23 p. 20–24 March 1995.
4. [4] Reevaluating Amdahl's Law in the Multicore Era, Xian-He Sun and Yong Chen, Journal of Parallel and Distributed Computing, Vol. 70 p. 183–188, February 2010.
5. [5] Scaling the Bandwidth Wall:Challenges in and Avenues for CMP Scaling, Brian M. Rogers, Anil Krishna, Gorden B. Bell, Ken Vu, Xiaowei Jiang, and Yan Solihin, ACM SIGARCH Computer Architecture News, Vol. 37 p. 371–382, June 2009
6. David Culler; Jaswinder Pal Singh; Anoop Gupta. Parallel Computer Architecture a Hardware/Software Approach. pp. 206–207.
7. U.Meyer, P.Sanders, and J.F. Sibeyn (Eds.), Algorithms for Memory Hierarchies, Vol. 2625 of LNCS Springer, 2003.