EDA开源仿真工具verilator入门3：多线程优化相关模块和方法总结和介绍
多线程模式
在多线程模式里，直到V3Order之前，Verilator Pipeline的前端（front end）是串行的模式。V3Order会建立一个细粒度语句级的依赖图(dependency graph)，其通过单个的函数eval()来控制代码执行顺序。在串行模式下，通过依赖图将所有语句转化为一个完整的串行序。并行模式下，同一个依赖图是一个partitioner（V3Partition）的开始点。
Partitioner的目标是将细粒度的图转换为粗粒度的图，并且尽可能维护并行性。通常，partitioner可以将一个有成千上万个nodes的输入graph转换为一个有几十个nodes的粗粒度可执行graph，同时利用CPU的多核性维护足够多的并行性。粗粒度下，有较少的nodes，运行时同步耗时是可以接受的。
Partitioning算法
Partitioner 会为多处理器分割和规划并行程序，首先声明几个术语：
Par Factor
可用并行数或者"par-factor"是一个DAG执行所有顶点的总花费。这个总花费可以通过这个图的最长关键路径（longest critical path）来分割，关键路径的概念可以参看AOE网络。这使得你能够根据图结构进行并行化得到的速度提升（多核CPU下忽略异步和通信的耗时）。
Macro Task
Partitioner 粗粒度化（coarsens）图的时候，它会把所有的顶点结合到一起。每一个细颗粒（fine-grained）的顶点代表一个原子任务。在粗粒度图中，结合到一起的顶点为宏观任务（macro-tasks，Sarkar提出的概念）。每一个宏观任务执行期间在一个CPU核上运行，且不需要同其他任务同步(同步只发生在任务开始和结束的时候)。
Edge Contraction
Partitioner 主要依靠边收缩（edge contraction）来粗粒度化图，其开始于每个原子任务的一个宏观任务并且不断以迭代的方式合并通过边相连的宏观任务。
局部关键路径（Local Critical Path）
图中的每个顶点有个“局部”关键路径，即图的起点到该顶点的关键路径+该顶点的cost+该顶点终点到图的终点的关键路径。
Sarkar执行了一种折中的方案：在macro-tasks中粗粒度化图可以降低同步的消耗，但是会增长图的关键路径，从而降低par-factor。
在算法中采用的方案是选择关键路径增长最少的macro-tasks对来合并。每一次合并会产生新的顶点，新的顶点将会有一些局部关键路径，选择生成最短局部关键路径点合并，重复此方法直到par-factor达到某个门限，其并不能保证能生成最佳partition（Vivek Sarkar证明其是NP难问题）。
估计逻辑代价（Estimating Logic Costs）
为了计算任意一条通过图的给定路径的代价，Verilator会估计每个任务的执行代价，每一个宏任务都有一个执行代价，为其所有任务代价的总和。假定通信开销和同步开销均为0，那么一条路径的代价就是其所有任务代价的总和。
Verilator的代价估计由InstrCountVisitor类来分配，InstrCountVisitor类为多线程执行中最不牢靠的一环。很容易出现bug，而且其只是时间运行代价的一个宽松估计，更好的估计会带来多线程性能的提升，这是verilator目前需要改进的一方面。
运行时规划宏观任务（Scheduling Macro-Tasks at Runtime）
粗粒度化图以后，必须在运行时规划宏观任务，Sarkar给出了两种选择:第一种方法是通过一个运行时graph follower，在运行时动态地规划任务，Sarkar称此为"macro-dataflow model."。Verilator不支持此操作，早期基于此方法的实验表现很差。
另一种选择是静态地分配宏观任务给线程，每一个线程按照静态序执行其宏观任务。verilator采用这种静态的方法，唯一动态的可能是每一个宏任务在开始之前可能阻塞（block），会一直等待直到其在其他线程的先决条件完成。
如果先决条件满足，多线程同步的代价得很低的，但不能满足的话，有可能出现碎片化（CPU Fragmentation），这是此方法的主要消耗来源。``--prof-exec`` 开关和``verilator_gantt`` 脚本可以对这种碎片化的时间进行可视化。
定位变量到最佳空间位置
在规划完所有代码以后，尝试定位变量在内存中的位置，以便使得同一个宏任务需要获取的变量在内存中位置接近。这种方法提供了 "spatial locality"，即当我们拉取一个64-byte的cache行数据来获取2byte变量值的时候，我们希望另外62bytes也是我们想很快获取的数据，从而可以达到一个最佳的cache表现。
此方法对性能有很关键的影响，其应该允许Verilator扩展至非常大的模型。这里不依赖于工作集适合任何CPU cache，反之我们本质上使得数据从内存“流入（streaming）”caches。注意这里并不是字面上的streaming，地址会单调增加。但是，只要每个宏观任务的数据集适合一个核的局部caches，就应该有相似性能特征。
为了实现空间定位,对于每一个变量都打上其对应宏观任务集合的标签，这个集合被称为这个变量的footprint。一个给定模型里的变量都有一个footprint，可以对这些变量的footprint进行排序从而最小化它们之间的距离（两个footprint之间宏观任务的差别数目），最后将所有变量存入按照footprint排序的结构中。
字面上看，footprint排序是一个traveling salesman problem（TSP）问题，代码中使用了一种近似TSP算法来接近最佳排序。
这是一种比较旧的优化方法，以前的仿真器用类似的技术去优化单线程和多线程，但是这里Verilator在串行模式下并不优化变量的空间位置分布，这是一个可以提升的领域。
进一步提升多线程性能（可做事情列表）
波形规划（Wave Scheduling）
允许verilator模型和testbench并行运行，目前的情况当执行eval(),Verilator其他的工作线程都会处于空闲状态，因此这方面的改变也许可以带来性能提升。
高效的动态规划（Efficient Dynamic Scheduling）
如果扩展到更多的线程，那么可以进一步考虑一个完全的动态规划器（scheduler）。对于大型系统（cores>16）贡献一整个core给规划也许是有意义的，这样规划器的数据结构将与L1 cache相匹配，因此遍历主备好的优先排序序列的花费将不是过高的。
运行时重新打包的动态规划（Static Scheduling with Runtime Repack）
在运行时采集宏任务的执行次数，将宏任务重新打包到线程里。比如，每10000次循环重新打包一次。比起静态估计宏任务运行次数，是有潜在优势的。对于CPU核表现不均衡的情况，其可以做出快速反应。
时钟域平衡（Clock Domain Balancing）
目前Verilator没有针对宏任务坐时钟域的平衡，对于多域的模型，将会导致性能的降低，这是实践中一个非常重要的有待提高的问题。
其他形式的多任务平衡（Other Forms of MTask Balancing）
运行时系统开销的最大源头是空闲CPU，发生这种情况是由于多任务预测运行时间和实际运行时间的差异，对于含有类似重复逻辑（源代码中通常在一起并且打包在一起）的同类多任务这种差异会放大。
如果Verilator可以避免这些，而是取出类似逻辑并分发给不同的任务，这样就能增加任务的多样性从而降低代价估计的方差。
一种方法是，在源头随机制作各种 "tie breaker"比较运行时间，并且可以打乱的话，努力保持输入节点不在一起。
配置文件引导的优化（Profile-guided optimization）通过调整多任务规划可以使其性能更好，但这并不会引导打包进多任务。
性能回归（Performance Regression）
增加性能回归的功能可以有效地帮助我们优化性能，特别是如果可以设计一个回归来测试各种设计风格的话。
每个类分配一个实例（Per-Instance Classes）
同样的module对应多个示例，用不同的方式进行分割，那么对于实例的变量排序必然是次优解，因此对于每一个module的实例设置一个独特的类来做优化和排序是有可能提升性能的。
执行流（Verilated Flow）
Verilator的评测循环在大多数情况下只允许一个函数进行评测，在第一个评测中，代码段调用初始化模块，评估函数会等待所有的信号稳定，而在其他评测中，代码段检测输入信号的改变，例如时钟信号的改变，那么它会调用相应的串行函数（combo function）,当这些完成之后，会继续检测combo loops或者内部生成时钟带来的改变，如果发现存在变化则必须这重新评估模型。如果追踪（tracing）允许的话，可以用一个回调检测设计中所有变量的变化，并写下来所有变化的追踪，为了加速，评测过程记录下变量变化的bit mask，如果记录准确清晰的话，可以忽略检测信号改变的流程。