Top-down方法学由Intel提出，是一种软件性能分析技术。在众多软件性能分析技术中，Top-down使用了最多的硬件信息，与处理器微架构设计关系最为密切。目前，Top-down方法学已经成为服务器、桌面机领域进行软件性能分析的标准方法之一。
Top-down方法学
从PMC说起
性能监视计数器（Performance Monitor Counter，PMC）是软件工程师获取处理器运行情况最重要的手段。
在处理器设计阶段，会在CPU内部埋设众多性能监视信号。这些信号负责监视处理器中各种各样的事件，比如Cache缺失、TLB缺失、分支预测错误、各种指令的发射（issue）和退休（retire）等等。通常情况下，一种事件的性能监视信号只有1比特的电平信号（不需要握手）。当监控的事件发生时，信号置1（或置0）；监控事件结束之后，信号置0（或置1）。
性能监视计数器的软件接口通常会被称为性能监视单元（Performance Monitor Unit，PMU）。处理器中各个地方的性能监视信号都要汇集到PMU上。图1提供了一个典型的PMC框图。
图1 PMC示意图
在PMU中会提供几个性能计数器。每个性能计数器都提供可读写的配置寄存器和可读的值寄存器。配置寄存器可以为PMC选择需要计数的监控信号，以及计数的模式和过滤器。比如，对于提供了SMT功能的处理器，可以配置为统计两个线程的事件或者只统计其中一个线程的事件。
对于一个PMU来说，能够同时监控的事件是很少的。x86处理器的PMU一般提供8个PMC，其中4个是固定的PMC，其对应的监控信号是不能配置的。另外4个PMC监控的信号是可以配置的。
在多核处理器SoC中不只存在一个PMU。实际上，每个处理器核心Core都有自己独立的PMU，而且有时核外的存储系统和外设也会提供自己的PMU。PMU中也不只有计数器一种性能统计工具。
Top-down方法学的动机
通过PMC，软件工程师可以获得处理器中各种事件（指令数量、分支预测错误、Cache缺失等）发生的数量。基于这些事件，软件工程师可以窥探处理器的行为。
首先，软件工程师可以通过PMC获得程序执行的时钟周期。在X86中，时钟周期是固定PMC之一。
接着，软件工程师可以通过PMC获得各种类型指令（访存、分支、整形计算、浮点计算、向量计算等）的执行次数。不同于软件的静态分析，这里可以获得真正执行时的指令混合（Instruction Mix）情况。可以初步反映程序热点所在。另一方面，通过PMC可以进一步获得微指令（micro-op）的指令混合情况，这更加接近处理器的真实负载比例。更近一步，通过PMC可以获得投机执行的指令（无法退休的指令）的占比。
然后，软件工程师可以通过PMC获得各种可能使得流水线stall的事件的次数。流水线stall表示处理器无法给执行单元提供指令。会引起流水线stall的典型事件包括：Cache缺失、TLB缺失、分支预测错误、发射端口不足、乱序资源不足等。对于顺序执行以及单发射的处理器中，可以通过累加上述事件以及他们引入的stall的周期的乘积，就可以估计流水线stall的总数。
为了提高性能，现代处理器充分利用超标量、乱序执行和投机执行。这就造成了孤立的统计指标无法反映程序整体性能瓶颈的问题。具体表现为：
- 超标量误差。在顺序执行以及单发射的处理器中，一种stall事件就会引起整个流水线的stall。但是在超标量处理器中，由于处理器可以同时发射或处理多条指令，一条指令遇到stall并不意味着整个流水线stall。这就使得单纯统计可能引起stall的时间的数量并不能正确反映流水线stall的情况。
- 可能引起流水线stall的事件会出现重叠。比如处理器的前端和后端可能在同时出现stall行为，此时两个事件引起的stall效果重叠在一起。类似的还有寄存器依赖关系和访存依赖关系引起的stall会重叠等。
- 预定义的事件集合遗漏流水线stall。通过累加stall事件和stall周期的乘积获得流水线stall的周期数，需要预定义stall事件的集合。这种预定义的事件集合可能会遗漏掉一些少见或者没有预期的stall，引入了误差。
- 投机执行。投机执行的指令并不是真正需要执行的指令。即便流水线没有发生stall，但是执行投机指令仍然是对于处理器性能的浪费。
以上这些误差都会影响通过PMC对于软件性能瓶颈的定位，使得定位出现偏差。综上，Top-down方法学最为重要的动机就是为现代处理器提供一个直接的、准确的性能分析方法。
Top-down方法学
论文“A Top-Down Method for Performance Analysis and Counters Architecture”中对于Top-down方法学的描述如下：
Top-down方法学的目的是正确而高效的确认性能瓶颈。Top-down方法学指导软件工程师关注到真正重要的问题。
Top-down方法学首先在高层次分类CPU的执行时间。从这里可以获得需要进一步分析的领域。然后，用户可以进入到值得关注的领域，并且忽略其他领域。按照层次结构重复这一个过程，直到确定特定的性能问题，或者将潜在问题确定在很小的范围内。
个人理解，Top-down方法学的关键词是“饼图”和“层次化”。Top-down首先在微架构中寻找一个可以量化的观测点，并且确定一种分类单位（时钟周期、Slot或带宽等）。然后对选定的单位进行分类，得到各分类的占比，形成“饼图”（如图2所示）。比如时钟周期是空闲还是被使用。对于得到的一个分类，既可以继续细化分类，也可以重新选择观察点和单位，再进行分类。从而形成层次化架构（或者决策树）。 
图2 Topdown结果示例
下面的图是icelake架构的Top-down决策树。 
图3 Icelake微架构的topdown决策树
在Intel的决策树中，第一层（L1）和第二层（L2）的分类比较宏观，可以认为是架构层面的指标。L1和L2的度量采用相同的度量指标和相同的观察点获得。所以，不考虑误差的情况下，L1各指标之和应当等于1；L2各指标之和应当等于1；属于同一分类下的L2指标之和不应大于这个分类的L1指标。L1和L2可以拉通分析。图2中就将L1和L2的度量画在了同一个饼图中。
第三层（L3）开始，度量指标具有明显的微架构特征。L3度量指标不使用统一的度量指标和观察点。同属于一个L2分类的L3指标会使用相同的度量和观察点；属于不同L2分类的L3指标不使用不同的度量和观察点；L3指标也不遵循其L2分类的度量和观察点。L3的度量不能拉通分析，只能在某个L2分类下进行分析。L3之后各层也是这样的。
Top-down方法学的第一层
处理器流水线一般被分为前端（frontend）和后端（blackend）两部分。前端部分指令顺序流动，后端部分指令并发和乱序。在Top-down方法学的第一层，将观察点设置在流水线中前端和后端的分割点。图4展示了skylake的微架构框图。途中用虚线标识了顺序部分（Inorder）和乱序部分（OOO）的分界位置，即从Allocate/rename/retire（一般指RAT和ROB）到Schedular（一般指RS），在这个分界位置之前，指令流都是顺序的；在这个位置之后，指令流会出现并发和乱序。
说明：对于采用CISC指令集的Intel处理器，其译码单元会将一条x86指令译码为一串微指令（micro-op），指令单元通过执行这一串微指令实现x86指令的行为。为了描述方便，在后续描述中不强制区分指令和微指令。
图4. Skylake微架构示意图
但是Top-down的观察点并没有直接放置在虚线的位置上，而是放在了图4中数字4的位置，即从译码单元到寄存器重命名单元（RAT）的位置，这个位置也被称为dispatch。这是因为RAT和ROB的逻辑会受到乱序引擎的影响，如图所示，在Allocation/rename/retire部分的左侧有三个箭头，分别来自Load buffer、Store buffer和Reorder buffer。这三个资源是乱序执行引擎需要维护和依赖的重要资源。由于这三种资源的不足导致流水线stall应该被看作是由于乱序引擎引起的。
Top-down方法学将第一层的观察点设置在了dispatch的位置。在这个位置之前，指令按照程序执行顺序在流水线上流动；在这个位置之后，指令的流动受到乱序执行引擎的影响，比如乱序缓存资源不足、寄存器依赖关系未满足、地址依赖关系未解除等。
对于超标量处理器，在dispatch位置可以并行发送多条指令。如果使用周期作为分类单位会引起超标量误差。Top-down方法学在这里选择slot作为分类单元。slot表示的是一个周期传递的一条指令，slot总量是dispatch宽度和执行周期的乘积。
slot的分类如图5所示。根据slot是否被指令占用可以分为两类。对于被指令占用的slot，可以进一步按照指令是否投机执行进行区分为retiring和bad-speculation。没有指令占用的slot，可以进一步按照造成空闲的原因，区分为frontend-bound和backend-bound。如果后端不能接收前端提供的指令，那么将空闲slot归类为backend-bound；如果前端不能提供指令，那么将空闲slot归类为frontend-bound。
图5. Topdown决策树第一层
由于前面提到的乱序和投机等问题，一个slot可能具备同时属于多个分类的可能。比如说，当流水线stall的时候，前端由于L1指令缓存缺失而无法给后端提供指令，后端因为L1数据缓存缺失而无法接受前端的指令。此时，需要根据经验给出倾向性的判断，从而保证一个单位只能归类到一种类型。Intel认为当前端和后端stall同时出现时，认为是后端stall，因为在现有处理器中优化后端stall更加重要。这种“强制性”的分类是根据大量的软件分析以及对于微架构演进方向的展望做出的，在绝大多数情况下都是可以信任的。
Top-down对于PMC设计的影响
Top-down分析方式是一种软件设计方法，但是需要硬件PMC进行配合，提供基本数据。由于Top-down方法学是从软件角度出发的，Top-down对于PMC的需求，从硬件角度并不容易满足，常常需要变通和组合。
例如，Top-down方法需要测试流水线dispatch的slot中哪些是被有效指令使用的，哪些是被投机指令使用的。但是在硬件上，从dispatch的流水级是无法知道dispatch的指令是否能够正常退休，而是需要到退休的流水级才能确定。考虑到测试时间都远远大于处理器的流水级深度，这里采用的变通方法是直接以退休的指令数表示正常退休的指令占用的退休的slot，忽略流水级不对齐引入的误差。
又比如，某个度量指标需要区分投机指令和有效指令，但是在实际RTL中测量的时候无法区分。考虑到这个度量指标与投机与否是独立的，这里采用的变通方式是将PMC测量的结果按照投机指令的比特进行缩放：metric = #retired\_uop / (#retired\_uop + #speculate\_uop) * PMC\_value。
Top-down方法学对于硬件的PMC设计也不是毫无启发。比如分析执行单元的利用率，可以将时钟周期为分类单元，按照周期中issue的指令数量进行分类，分为issue 0个、1个、2个或n个指令给执行单元。分析存储单元的带宽，可以将带宽作为分类单元，按照带宽的使用原因来分类，分为Load、Store、Refill以及Evict使用的。按照Top-down的思路设置的硬件PMC，其分析数据能够同时反映出测试程序的特性以及硬件对于测试程序的响应，分析出的结论更加精准。
Top-down工具pmu-tools
Intel Top-down工具称为pmu-tools。pmu-tool只用于Linux操作系统（因为需要调用Linux系统的Perf工具）。pmu-tool以python3开发，不需要额外的安装步骤。下载代码后可以直接执行。Intel的性能分析工具集Vtune也集成了Top-down工具。
图6. pmutool软件栈
调用Perf
top-down工具利用perf获取物理机的底层信息。Perf是linux平台的性能测试工具，功能非常强大。其中最为常用的功能包括：
- perf record报告程序各函数执行的时间占比，从而定位程序热点。
- perf stat获取程序执行阶段的硬件PMC的数值。
top-down工具就是利用perf stat来获取PMC统计数值的。工具会根据目标CPU生成需要监控的PMC列表，然后利用perf stat获取这些PMC的数值。
top-down使用的PMC数量非常多，但是硬件提供的PMC接口却很少。同一时刻，硬件只能对4个PMC进行计数。为此，perf stat将执行时间进行分段，轮询监控PMC。首先监控PMC列表开始的4个PMC，一段时间后切换到后面4个PMC。这种方法称为复用（multiplex）。
程序运行结束后，在根据监控PMC的时间和总的执行时间，对于统计到的PMC计数进行缩放：final\_count = raw\_count * time\_enabled/time\_running。
toplev默认采用复用的方法，因此，利用top-down工具进行分析时，程序执行时间不能太短，否则会出现无法统计到所有PMC的情况。
如果测试程序确实很短，也可以采用多次测量的方法。将被测试程序运行多次，每一次只测量几个PMC。这种方法称为非复用（no-multiplex），通过命令行选项使能。
度量指标
pmu-tool中定义了top-down方法学需要测量和分析的度量指标（metrics）。这些度量指标对硬件性能计数器结果进行计算，得到更加形象和有针对性的指标。比如度量Metric\_L1MPKI表示每千条指令中，L1缓存缺失的次数。计算公式如下：
Metric_L1MPKI = 1000 * MEM_LOAD_RETIRED.L1_MISS / INST_RETIRED.ANY
公式中，MEM\_LOAD\_RETIRED.L1\_MISS和INST\_RETIRED.ANY都是硬件PMC，分别表示发生L1缓存缺失的非投机的load指令数，以及所有非投机的退休指令数。
pmu-tool中使用的度量（metrics）可以分为决策树和微架构度量两部分。决策树部分用来定位性能瓶颈，比如Frontend-Bound、Backend-Bound、Retiring和Bad-Speculation。
为了方便表征指标的含义，Intel为每一个度量指标提供了阈值。当统计到的度量指标大于阈值时，pmu-tool会高亮这一指标进行提示。在决策树部分，工程师可以根据pmu-tool的提示，逐层完成定位分析。在完成决策树定位之后，可以通过微架构度量进一步分析性能瓶颈产生的原因。微架构度量部分的metric相互之间没有约束关系，软件工程师需要根据这些metric含义自行判断数值是否需要采纳，以寻找性能缺陷。
Metric数据库
pmu-tool中的metric定义一共有三个版本，代码中称为V1.0，V2.0和V4.5。新增加的处理器选择那个版本并不是完全取决于处理器发布的时间顺序，而是取决于处理器架构的延续脉络。每一个版本中又包含了针对不同微架构的定义。随着微架构的发展，针对不同微架构的metric定义会增加新的度量，或调整度量的公式。
V1.0属于极简版，应用于Silvermont和Knights Landing微架构。V1.0只提供了3级决策树（10个度量指标）和6个通用度量指标。
- "slm"代表Silvermont和Airmont微架构，属于凌动系列小核处理器。
- "knl"代表Knights Landing，第二代PHI计算卡中的处理器架构，其中使用了72个Silvermont核心。
V2.0属于精简版，应用于Elkhart Lake和GraceMont微架构。V2.0提供了4级决策树（总共38个度量指标）和45个通用度量指标。
- "ehl"代表Elkhart Lake微架构，也称为Tremont，也属于凌动系列的架构。
- 在V2.0版中，"adl"代表Gracemont和Enhanced Gracemont微架构，分别作为Alder Lake/Raptor Lake能效核心（小核）微架构。Gracemont是Tremont的后继架构。
V4.5是目前主要的版本，应用于以下微架构：
Core系列：从第二代酷睿开始的所有架构。目前支持到Raptor Lake。
- "snb"代表Sandy Bridge微架构，用于第二代酷睿处理器。
- "ivb"代表Ivy Bridge微架构，用于第三代酷睿处理器。
- "hsw"代表Haswell微架构，用于第四代酷睿处理器。
- "bdw"代表Broadwell微架构，用于第五代酷睿处理器。
- "skl"代表Skylake、KabyLake、CoffeeLake、Whisky Lake、Amber Lake和Comet Lake微架构，用于第六、七、八、九代酷睿处理器。
- "icl"代表Ice Lake和Rocket Lake微架构，用于第十、十一代酷睿处理器。
- "tgl"代表Tiger Lake微架构，用于第十一代酷睿处理器。Tiger Lake和Ice Lake共享相同的top-down设计。
- 在V4.5中，"adl"代表Golden Cove和Raptor Cove微架构，分别作为Alder Lake/Raptor Lake性能核心（大核）微架构。用于第十二、十三代酷睿处理器。
Xeon系列：
- "jkt"代表Sandy Bridge微架构，用于Xeon E3-1200系列，Xeon E5-2400/1400系列，Xeon E5-4600/2600/1600系列，Xeon E7-8800/4800/2800系列。
- "ivt"代表Ivy Bridge微架构，用于Xeon E5-2400/1400 v2系列，Xeon E5-4600/2600/1600 v2系列，E7-8800/4800/2800 v2系列。
- "hsx"代表Haswell微架构，用于Xeon E3-1200 v3系列，Xeon E5-2600/1600 v3系列。
- "bdx"代表Broadwell微架构，用于Xeon D-1500系列和Xeon E5 v4系列。
- "skx"代表Skylake微架构，用于Xeon可扩展处理器和Xeon E3-1500m v5系列。
- "clx"代表Cascade Lake和Copper Lake微架构，用于第2代Xeon可扩展处理器。
- "icx"代表Ice Lake微架构，用于第3代Xeon可扩展处理器。
- "spr"代表Sapphire Rapids微架构，用于第4代Xeon可扩展处理器。
V4.5提供了4级决策树（总共109个度量指标）和118个通用度量指标。与V2.0的决策树相比，V4.5的决策树在第3、4级有非常明显的区别。此外，V4.5也存在Core微架构和Xeon微架构两条演进路线。相对于对应的Core微架构版本，Xeon路线主要加强了uncore部分的决策。
工具使用
工具源代码中的toplev就是工具的可执行文件。执行toplev --help就可以获得工具命令行的帮助信息。toplev的基本格式是 toplev [options] command
其中，command指定了需要测试程序的命令。由于toplev需要获得PMC，所以通常需要sudo权限。
不提供任何选项时，pmu-tool的的输出如下图：
图7 pmutool输出示例
pmu-tool的输出信息包括如下部分：
- 硬件信息（处理器型号、微架构代号、频率），例如”# 4.5-full-perf on Intel(R) Xeon(R) Gold 5220 CPU @ 2.20GHz [clx/skylake]”
需要关注的度量。不提供任何参数时，工具只提供第一层决策树的度量指标，并且只输出值得关注的度量指标（工具认为不重要的度量指标不会打印）。
- 每个度量指标的信息包括：处理器核心编号（比如S1-C0和S1-C0-T1），度量分组（FE或BE），度量名称，度量单元（Slots），数值。
- 每个度量指标还会提供测量这个指标占用的执行时间，比如[33.2%]标识测量这个指标占用了1/3的执行时间。
- 如果度量指标超过预设的阈值，会通过箭头标识出来，比如backend\\_bound就被用箭头标示了。
- 针对进一步分析提示：比如”Run toplev --describe Backend\\_Bound^ to get more information on bottleneck”
pmu-tool的常用选项包括：
- -v：输出所有测量的指标。
- -m：除了测量决策树，还提供微架构度量指标。
- -l1/-l2/-l3/-l4/--all：指定测量决策树到哪一个层次。l4表示测量L1到L4的全部度量指标；all表示测量整个决策树。
- -x, -o <file>：将测量结果按照CSV格式输出到指定文件，CSV分隔符为逗号。
- --core <core>：指定测量的CPU。通常与taskset命令一起适用，将测试任务绑定在某一个处理器上。
- --no-desc：输出不打印度量的描述，可以优化屏幕显示。
- --no-multiplex：进行执行多次测量。适用于执行时间很短的负载。
提供上述选项时，工具的输出如下图：
图8 pmutool输出示例
此时，测试结果保存在matmul\\\_fma.csv文件中： 
图9 pmutool输出csv文件
参考资料
- Ahmad Yasin, A Top-Down Method for Performance Analysis and Counters Architecture
- Ahmad Yasin, Top-down Microarchitecture Analysis through Linux perf and toplev tools
- Ahmad Yasin, Performance Analysis in Out-of-Order Cores
