Introduction to Roofline Model
Roofline model本质用来一个描述程序或者应用的性能状态并进一步给出大体优化方向。
Latnecy
延迟是从发出一个请求，到收到结果之间的时间间隔。它是对单个操作从头到尾耗时的度量。延迟是这个操作客观固有的物理时间，该时间无法消除，它取决于这个操作本身和所需硬件性能。
Latency Hiding and Latency-Bound
延迟是操作固有的耗时，当发起方没有别的事可做时，延迟就表现为空闲等待；而隐藏延迟就是让发起方在这段时间里去做其它独立任务，从而把空闲“隐藏”起来。而当一个或者多个任务的延迟无法被充分隐藏，性能因此受限于延迟，那么这个任务就是Latency-Bound。可是，如何界定延迟是否被充分隐藏了呢？那就要用到下面的Little's Law
Little’s Law
Little’s Law的公式很简单
充分利用带宽所需的in flight求数 = 延迟 × 带宽
Little’s Law本质上是说要维持某个吞吐率，你必须同时保持”延迟这么长时间内积累下来的量”处于正在处理的状态。
假设一条汽车生产流水线：
- 延迟 = 一辆车从进入流水线到开出来，要 10 小时。
- 带宽（吞吐率） = 流水线每小时能开出 1 辆车。
每辆车都要花 10 小时，但工厂却能每小时产出1辆，这怎么可能？因为流水线上同时有很多辆车在不同工位上被加工。虽然每辆单独看都要10小时，但它们是重叠进行的，所以从出口看，车是一辆接一辆稳定地出来的。问题来了：要让这条流水线达到”每小时 1 辆”的产出，流水线上必须同时有多少辆车在被加工？
如果每小时进1辆，在10小时的窗口里，线上就有10辆车同时在被加工。这样才能保证每个小时能出1辆车，所以
在线的车数 = 延迟 × 吞吐率 = 10 小时 × 1 辆/小时 = 10 辆
这就完美解释了latency-bound，如果一个程序的延迟是100ns，并且只能维持1个请求在处理，那么根据同样的算式反推，实际吞吐率只有：
1 / 100 ns = 0.01/ns
如果带宽明明是1/ns，那么该程序只用到了1%的带宽，其余99%全空着。这就是latency-bound：不是带宽不够，而是你提供不出足够多的in flight请求去占满它，于是被延迟这个”每趟往返时间”死死拴住。
Bandwidth-Bound
那么如果能够提供足够多甚至更多的in flight请求呢，还用上面的例子
实际吞吐 = in-flight请求数 / 延迟 = 100 / 100 ns = 1/ns
也就是说，如果in-flight够多，达到了延迟 × 带宽的时候，程序就从latency-bound 跨入了 bandwidth-bound。
bandwidth-bound 的程序一般长什么样：它们一般情况下in flight请求管够，延迟被完全隐藏了。这一步就已经排除了 latency-bound。同时，有大量的数据传输，但是计算量没有那么大，也就是说数据供应速度跟不上它的计算能力。于是限制整个程序的，就是内存带宽：它能多快地把这些数据流进流出。
Arithmetic Intensity
这就引出了另外一个问题，如何知道一个程序是bandwidth-bound还是compute-bound呢？有个非常实用的量，叫算术强度（arithmetic intensity）：
算术强度 = 计算操作数 / 数据传输量（每搬运一字节做多少次计算）
-
算术强度低（搬得多、算得少）→ 计算单元容易挨饿 → 大概率 bandwidth-bound。
-
算术强度高（每个数据被反复利用、算很多次）→ 数据一旦搬进来就”物尽其用” → 瓶颈转向计算能力，可能变成 compute-bound。
矩阵乘法是个好对比：它每搬进一个数据能参与非常多次乘加运算，算术强度高，所以（在优化得当时）往往是 compute-bound 而非 bandwidth-bound。
把三种情况放一起
latency-bound: 独立工作不够，延迟没藏住。应该加并行。
bandwidth-bound： 延迟藏住了，但数据搬运速率到顶了。应该减少搬运量、提高复用。
compute-bound： 数据供应绰绰有余，但计算本身太重，算不过来。应该加计算能力或减少计算量。
三者的分界，本质上就取决于两个比值：程序能维持多少in flight请求（决定 latency 还是 bandwidth），以及每字节数据配多少计算（即算术强度，决定 bandwidth 还是 compute）。
Roofline Model
Roofline Model是理解的这三种瓶颈画进同一张图里的工具。Roofline Model 用一张图告诉你：给定某个算术强度的程序，硬件最多能跑多快，以及此刻限制它的到底是带宽还是计算能力。
上图两个轴，横轴：算术强度（每字节数据做多少次计算，FLOP/Byte）—就是你上一个问题里刚掌握的那个量。纵轴：可达到的性能（每秒多少次计算，FLOP/s）—即程序实际能跑多快。
性能上限 = 算术强度 × 带宽
图上那个转折点（ridge point）正是两种瓶颈的分界。屋檐和平顶相交的那个拐角，叫 ridge point（脊点）。它的横坐标算出来正好是：
脊点算术强度 = 峰值计算能力 / 带宽
这个点意义重大，因为它就是之前问题里说的”从 bandwidth-bound 跨入 compute-bound 的临界值”，现在它在图上有了确切位置：
-
程序的算术强度落在脊点左边 → 它撞到的是斜的屋檐（带宽线）→ bandwidth-bound。
-
程序的算术强度落在脊点右边 → 它撞到的是平的屋顶（计算线）→ compute-bound。
把这张图想象成横轴是算术强度、纵轴是性能，头顶罩着那个”斜屋檐 + 平顶”的屋顶。我们按区域来看。
位置一：脊点左侧、贴着斜屋檐的点。
这是已经优化到位的 bandwidth-bound 程序。它把内存带宽完全喂饱了，延迟也藏好了，在当前算术强度下已经跑到了物理极限。它没有”向上”的空间了。它唯一的出路是”向右”——提高算术强度，让自己沿着斜屋檐往上爬、越过脊点。典型代表是优化良好的向量加法、SAXPY 这类操作。
位置二：脊点右侧、贴着平顶的点。
这是compute-bound 程序，也就是我们刚讨论的理想归宿（前提是算法最优）。它顶到了硬件的计算峰值，向上和向右都没有空间了。典型代表是优化良好的稠密矩阵乘法。如果它用的是最优算法，那这里就是终点；如果算法有冗余，出路是换算法（这会让点的横坐标和纵坐标一起改变）。
位置三：远低于斜屋檐的点（脊点左侧下方）。
这是没优化好的、潜在 bandwidth-bound 程序。它的算术强度不高，本该受带宽限制，但它连带宽都没喂饱——大概率是延迟没藏住（latency-bound，in-flight请求太少）、并行度不够、或者访存模式差导致缓存和预取失效。它离屋檐的垂直距离，就是被浪费掉的性能。它的当务之急是向上：增加in-flight的独立请求来隐藏延迟、改善数据布局让硬件能预取。先爬到屋檐上，再谈向右。
位置四：远低于平顶的点（脊点右侧下方）。
这是没优化好的、潜在 compute-bound 程序。它的算术强度足够高，本该顶到计算峰值，但实际性能却远低于平顶。这通常意味着计算单元没被充分利用——比如没有用上向量化（SIMD）、指令级并行不足、线程没占满、或者有大量分支和依赖打断了计算流水线。它的出路也是向上：通过向量化、更好的指令调度、提高占用率等手段，把浪费的计算能力榨出来，爬到平顶。
把四个位置连成一张地图, 如果用一句话概括每个区域：
贴着屋顶的点（位置一、二）说的是”我已经用满了当前瓶颈，要突破得改变策略”——左侧改算术强度，右侧改算法或硬件。
低于屋顶的点（位置三、四）说的是”我还在浪费当前瓶颈的潜力，先别谈突破，把浪费补齐”——不管在哪一侧，方向都是先向上。
Roofline本质上是在说：优化的理想轨迹，是把点从图的低处、从脊点左侧，一路先向上补齐浪费、再向右提高算术强度，最终推到脊点右侧、贴住平顶。 到那时，限制的因素只剩下硬件计算能力这个最硬的物理墙——只要算法本身已经无冗余，这就是这块硬件上能达到的极限，也就是名副其实的优化终点。
Reference:
- Samuel Williams, Andrew Waterman, and David Patterson. “Roofline: an insightful visual performance model for multicore architectures.” Communications of the ACM 52, no. 4 (2009): 65-76.