Sun-Ni定理

在理论计算机科学中，Sun-Ni’s Law是一种内存有界加速模型，它指出随着计算能力的增加，问题的相应增加 大小受系统内存容量的限制。 一般来说，随着系统计算能力的增长，系统上运行的问题也会增加。 类似于 Amdahl 定律，它表明问题大小随着系统规模的增长而保持不变，以及 Gustafson 定律，它提出问题规模应该扩大但受固定时间限制，Sun-Ni 的定律指出问题的大小应该按比例缩放，但受系统内存容量的限制。 Sun-Ni 定律最初是由孙贤和和 Lionel Ni 在 1990 年 IEEE 超级计算会议论文集上提出的。

随着 CPU 速度和内存数据访问延迟之间的差距越来越大，应用程序执行时间通常取决于系统的内存速度。 正如Sun和Ni所预测的那样，数据访问已经成为高端计算的首要性能瓶颈。 从这一事实可以看出 Sun-Ni 定律背后的直觉，随着系统资源的增加，应用程序经常受到内存速度和带宽的瓶颈，因此应用程序可以通过利用系统中的所有内存容量来实现更大的加速。 Sun-Ni 定律可以应用于内存层次系统的不同层，从 L1 高速缓存到主内存。 通过其内存有界函数W=G(M)，它揭示了算法和系统架构设计中计算和内存之间的权衡。

Sun–Ni、Gustafson 和 Amdahl 这三个加速模型都提供了一个指标来分析并行计算的加速。 阿姆达尔定律侧重于减少给定的固定大小问题的时间。 阿姆达尔定律指出，问题（算法）的顺序部分限制了随着系统资源的增加可以实现的总加速。 古斯塔夫森定律表明，构建大型并行系统是有益的，因为如果按比例扩大问题规模以保持固定的执行时间，加速比可以随系统规模线性增长。 然而，由于内存访问延迟通常成为影响应用程序执行时间的主要因素，因此应用程序可能无法扩展以满足时间限制。 Sun-Ni 定律不是按时间来限制问题的大小，而是按系统的内存容量来限制问题，换句话说，是基于内存的界限。 Sun-Ni定律是Amdahl定律和Gustafson定律的推广。 当内存有界函数G(M)=1时，它解析为Amdahl定律，当内存有界函数G(M)=m时，处理器的数量，它解析为Gustafson定律。

令 W ∗ 为内存空间限制下的缩放工作负载。 内存有界加速可以定义为：

求解 W* 的顺序时间/求解 W* 的并行时间

假设 f  是可以并行化的工作负载部分，而 ( 1 − f ) 是工作负载的顺序部分。

令 y = g ( x )  为反映内存容量增加 m 倍时并行工作负载增加因子的函数。

内存有界加速是：

对于任意幂函数 g ( x ) = a x b 和任意有理数 a 和 b

其中 g ¯ ( m ) 是系数为 1 的幂函数。

因此，通过采用最高阶项来确定算法的复杂性

表示记忆变化对问题大小变化的影响。

内存有界加速模型简化为阿姆达尔定律，因为问题大小是固定的。