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 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. 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. Yet as memory access latency often becomes the dominant factor in an application’s execution time, applications may not scale up to meet the time bound constraint. 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 W ∗ {\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 f {\displaystyle \textstyle f} is the portion of the workload that can be parallelized and ( 1 − f ) {\displaystyle \textstyle (1-f)} is the sequential portion of the workload. Let y = g ( x ) {\displaystyle \textstyle y=g(x)} be the function that reflects the parallel workload increase factor as the memory capacity increases m times. Let: W = g ( M ) {\displaystyle \textstyle W=g(M)} and: W ∗ = g ( m ⋅ M ) {\displaystyle \textstyle W^{*}=g(m\cdot M)} where M {\displaystyle \textstyle M} is the memory capacity of one node. Thus, W ∗ = g ( m ⋅ g − 1 ( W ) ) {\displaystyle W^{*}=g(m\cdot g^{-1}(W))}
The memory bounded speedup is then:
( 1 − f ) W + f ⋅ g ( m ⋅ g − 1 ( W ) ) ( 1 − f ) W + f ⋅ g ( m ⋅ g − 1 ( W ) ) m {\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 g ( x ) = a x b {\displaystyle \textstyle g(x)=ax^{b}} and for any rational numbers a and b, we have:
… excerpt ends here. Continue reading the full article.
