用于在高性能计算应用中检测异常调用堆栈树的可视分析框架 (A Visual Analytics Framework for th...

在高性能计算(HPC)应用中，诸如延迟之类的异常行为会对运行程序产生很大的负面影响。 因此，检测HPC集群中的异常执行是非常重要的。这些异常执行通常是从跟踪事件(trace event)中识别的，也是HPC节点中函数入口、出口和消息传递的序列。下图1(b)显示了HPC节点中计算函数的一次执行（图1(a)）内的跟踪事件的示例。它表示在执行compute函数期间调用堆栈的历史（使用绿色等颜色表示的函数即其调用的子函数）。目前，领域科学家一般基于函数随时间变化的执行时长等信息来检测异常执行。但是，这种方法并不能完全识别和诊断真正的异常。例如，图1中compute函数的延迟可能是由其子函数引起的，而这种延迟可能是由与之通信的其他HPC结点造成的。因此，在没有上下文函数执行结构的情况下对异常函数进行检测是不够的。

图1 (a) compute函数的跟踪事件示例；(b)从追踪事件中重新构建的调用堆栈；(c)用顶点带权重的有向树来表示调用堆栈。

为了解决这个问题，2018年VAST的一篇文章[1]中，作者使用调用堆栈树(CSTree)的表示来模拟运行时行为。如图1(c)所示，在该树中，节点表示在调用堆栈中调用的函数，有向边表示从父函数到子函数的调用。节点权重是执行时间。从同一函数的多次执行可以生成调用堆栈森林。因此，异常行为检测可以被归结为在调用栈森林中找到异常树结构的问题。其输出将是森林中结构最不寻常的调用堆栈树。文章所提出的检测异常调用堆栈树的可视分析方法如图2所示，主要包括四个部分。首先根据运行时信息生成调用堆栈森林，再将每个调用堆栈树转换为一种根据所提出的stack2vec方法学习得到的嵌入向量。这些向量被用作异常检测的输入。文章使用一个主动学习策略循环地标记、检测和验证候选异常。

图2 该工作所提出方法的步骤。

图3 Weisfeiler-Lehman graph kernel 算法提取调用堆栈树的子结构信息。

方法的第一步是构建调用堆栈树，这个如前所述。之后，为了在异常树检测中度量不同CSTree之间的结构相似性，其使用Weisfeiler-lehman 算法通过一个顶点重新标记过程来提取树中的子结构特征。如图3所示，该算法是一个迭代过程，在每次迭代中执行两个操作：增强(augmentation)和压缩(compression)。在标签增强中，在每个节点的标签附加上其子节点的标签，在标签压缩中，为增强后的节点分配新标签。然后，如图3表格的中间栏所示，可以在算法迭代期间识别出A到J的子树。

图4 调用堆栈树的bag-of-subtree向量表示。

根据得到的子结构特征，作者提出了stack2vec，用于构造调用树的向量表达。他们使用了文档分析的类比来进行树的表达。如图4所示，树中的子树对应文档中的单词，与文档中的单词频率类似，每个子树的执行持续时间被视为其频率。之后，原则上这种bag-of-subtree向量可以直接用作异常检测的输入向量。但是这种树的表达可能非常稀疏，并且子树的语料库可能很大。为了解决这一问题，作者采用了类似的文档神经嵌入方法。stack2vec使用与doc2vec相同的框架来嵌入调用堆栈树。doc2vec是一种浅但宽的神经网络，一共有三层，如图5所示。隐藏层的输出可用作调用堆栈树的嵌入向量，也即是异常检测的输入。

图5 doc2vec神经网络训练模型。

图6 (a)调用堆栈树嵌入向量的MDS投影；(b)异常调用堆栈树的候选。

图6(a)的可视化展示了调用堆栈森林中所有树的MDS投影。通过诸如one class SVM的异常检测方法，可以学习决策边界来分离正常树和异常树。对于在决策边界外标记为红色的候选异常树，有必要验证它们是否为真正的异常。该可视化提供了散点图中的候选列表，如图6(b)所示，允许用户进一步探索。用户可以在检查后将它们标记为正常树或异常树。通过这种主动学习策略，可以从用户提供的标签中改进决策边界。此外，为了进行详细的检查和验证，作者还提供了两个额外的可视化，分别关注调用堆栈树的结构信息和时间信息。

图7 调用堆栈树结构可视化。(a)和(b)分别对应正常和异常调用堆栈树。

如图7所示，第一个可视化是CSTree结构可视化。树顶点的区域大小和颜色分别映射了顶点的权重和函数名称。图7(a)显示了一个正常的CSTree，它是HPC节点15中compute函数的第361次执行。为了便于比较，图7(b)还显示了一个节点非常大的异常树结构（第40次执行），其表示该函数执行时间非常长。为了帮助理解异常检测过程，该工作还计算了树中最异常的子结构特征。例如，图右侧两个视图显示了分别以forward_comm_pair和MPI_send为根的子树，它们是该树中最异常的两个子结构。

图8 时间线可视化。(a)和(b)分别对应正常和异常调用堆栈树。

图7的可视化中没有显示函数调用的顺序和消息发送信息。基于此，该工作的第二个可视化即是时间线可视化。如图8所示，x轴是时间，y轴表示调用堆栈方向。对于上下文信息，使用了垂直箭头线的方式来表示此次执行与其通信的节点之间的调用。图8(a)是一个正常的调用堆栈树。为了便于比较，图8(b)展示了第二棵树的时间线可视化。可以观察到发送和响应消息之间存在一些显著的延迟，这可能是由与其通信的节点的延迟引起的（例如节点0）。对应地可以看到，左边调用堆栈树的节点尺寸之所以比较大也主要是由消息延迟引起的。

图9 分析案例。

总的来讲这个工作将高性能计算应用中运行时异常行为的检测看作是在调用堆栈森林中找出异常树结构的问题。通过使用机器学习的方法，将调用堆栈树转化为向量的表达，之后可以用于分类和对异常的检测。图9给出了一个完整的案例，通过在各个视图中探索，用户可以根据自己的经验知识，改进检测结果，定位异常行为并对其上下文进行分析。未来这个工作也可以和运行代码相结合，以实现一个完整的执行调度和代码设计优化的分析框架。

Reference

[1] Cong Xie, Wei Xu, and Klaus Mueller. A Visual Analytics Framework for the Detection of Anomalous Call Stack Trees in High Performance Computing Applications. IEEE Transactions on Visualization and Computer Graphics (VAST’18), 25(1):215-224, 2019.