Fig. 1 The concept of SDT logical replay
图1 SDT逻辑重现概念示意图
王博弘 刘 轶 张国振 钱德沛
(北京航空航天大学中德软件技术联合研究所 北京 100191)
(turtlemax2009@gmail.com)
摘要多核并行程序的调试是一个公认的困难问题，困难主要来自于程序执行的不确定性.可重现调试(replay debug)提供了消除程序中不确定性的能力，但是现有的可重现调试解决方案都无法应用于商用的软硬件平台中，且进行调试所带来的性能损失会随着并发度的增加而超线性地增长.提出了一种基于运行快照的新型并行程序调试方法SDT(snapshot debug tool).该方法以离线的断点设置、运行快照捕捉和运行快照细化为基础，提出了一套可以指导用户由粗到细发现错误的调试过程，并在通用的软硬件平台上进行了实现.实验结果显示，在8线程的并发条件下，使用SDT调试所带来的时间性能损耗平均为51.88%；同时当线程数增长4倍时，使用SDT所带来的额外时间消耗最多增长1倍，具有很好的可扩展性.记录快照的数据量是影响SDT性能的重要挑战,实验证明通过使用增量式的快照记录方式可以有效地降低需要记录的数据量,减少记录快照花费的时间,提高SDT的整体性能.
关键词可重现调试；运行快照；确定性；多核并行程序调试；多线程
随着现代处理器技术的发展，在单个芯片上集成多个处理器核[1]，形成多核处理器，已经成为芯片工业发展的主要趋势.在这种架构下，能够对多核处理器资源进行充分利用的多核并行程序也得到了越来越多的应用.然而面对多核架构，并行程序的开发和部署面临着诸多的困难.在这些困难之中，最为严峻的就是多核并行程序的调试问题.为了表示的方便和简洁，在第1～3节和第5节中，并行程序即指代多核架构下的并行程序，而非多节点架构下如基于MPI实现的广义并行程序.
在调试并行程序时，存在2个严重的问题：
1) 调试的基础存在问题.并行程序的运行存在着不确定性.不确定性往往会导致程序中的错误变得无法追查：在某种特定的系统条件和运行顺序下错误会出现，但是当软件开发人员尝试对错误进行调试和分析时错误又会消失.
2) 调试的方法存在问题.用户所熟悉的传统调试方法无法应用于并行程序的调试.例如在多线程的环境下，用户所设置的断点无法实现和串行程序调试一样的控制效果，并且很难从整体上采用由粗到细的方式发现错误.
可重现调试(replay debug)是一种针对并行程序调试，可以消除并行程序运行中不确定性的调试辅助技术，其对确定性的保证还被应用于并行安全性和可靠性检查[2]、性能预测[3]等多个领域.可重现调试在近年来已经成为了学术界和工业界关注的重点.ISCA，HPCA，MICRO，ASPLOS，SOSP，OSDI，PLDI，PPOPPT等关于体系结构、操作系统、并行计算、分布式计算、编程语言方面的顶级会议每年都会出现大量的关于可重现调试的论文.同时，IBM，Intel，Microsoft，VMware等在工业界具有影响力的公司都在确定性重现方面投入了大量的人力，他们相信可重现调试会给用户带来更好的可编程性.
部分现有的可重现调试研究成果，如LReplay[4]，RelaxReplay[5]，Pacifier[6]，已经将可重现调试的代价降低到了较小的程度，但是它们都是硬件辅助的解决方案，需要在处理器体系结构方面进行改动.而纯软件的实现方法往往要依托于高度定制的操作系统和运行时环境，如CoreDet[7]和Kendo[8].并且无论是软件还是硬件的解决方案，其实现可重现的代价往往会随着并发度的增加而超线性地增长.综上，现有的可重现调试方法普遍存在3个缺陷：
1) 无法应用于商用的软件和硬件平台；
2) 随着并行度增加的可扩展性较差；
3) 关注于调试基础，即确定性的保证，而忽略了对并行调试方法性的支持.
基于上述的缺陷和问题，本文提出了一种新型的基于运行快照的可重现调试方案SDT(snapshot debug tool).SDT的核心思路为把物理的可重现转为逻辑上的可重现，以牺牲部分调试上的灵活性为代价，得到一种可以在目前商用平台上进行应用的可重现调试方法.同时，SDT在保证确定性的前提下，还额外兼顾了对调试方法的支持，提供了一种基于运行快照逐渐细化的错误发现方法，更为符合用户的调试习惯，并且可以在调试的过程中与用户建立紧密的互动，具有很好的实用性.我们在PARSEC和SPLASH-2测试集上的运行结果表明，使用SDT调试所带来的时间性能损耗平均为51.88%，处于可接受的范围内.同时当多核并行程序的并发度增长4倍时，使用SDT所带来的额外时间代价最多增长1倍，具有很好的可扩展性.
可重现调试技术所应用的具体领域有很多.根据硬件体系结构和软件体系结构的不同，可以主要分为3类：
1) 单核处理器可重现调试;
2) 多核处理器消息传递可重现调试;
3) 多核处理器共享存储可重现调试.
目前，单核处理器可重现调试和多核处理器消息传递可重现调试的实现方法已经比较成熟，并且开始进入工业化实用阶段,ReVirt[3]和ReTrace[4]是其中比较具有代表性的成果;但是多处理器共享存储的可重现调试，目前仍然存在一些技术上的困难,这一技术困难主要集中在存储器竞争上.
针对多核处理器共享存储条件下的可重现调试问题，现有的研究方法主要可以分为2类：确定性重现和确定性并行.
确定性重现技术的实质为实现一个重现系统.确定性重现系统包含2个阶段：首次执行阶段和重现执行阶段.1)在首次执行阶段，并行程序在执行的过程中，将所有的不确定因素记录到日志文件中；2)在重现执行阶段，系统根据首次执行阶段记录的日志文件重新执行程序，以保证重现执行和首次执行有着相同的过程.目前主流的确定性重现方法普遍都需要对硬件进行更改：RelaxReplay[5]以及Pacifier[6]都以cache一致性消息的扩展为基础，通过硬件的改动，实现了对共享内存的所有冲突访问进行快速的识别和记录.而LReplay[4]的思路则是在处理器片间距离较小的情况下，引入全局时钟.通过全局时钟的辅助，绝大多数的指令执行序都可以被推导确定，LReplay只需要记录少部分无法推导的执行序即可.
与确定性重现记录的思想不同，确定性并行的根本思路为直接消除并行程序运行中所产生的不确定性，从而保证并行程序在相同的输入下，总是能产生相同的程序执行流程和相同的结果.确定性并行技术能够完全复现bug，实现对并行程序调试困境的突破，并且能同时对程序测试、容错等方面提供有力支持.CoreDet[7]是一个典型的使用串并行转化思路的确定性并行方法，使用内存持有表(memory ownership table, MOT)来判定并行读和串行写的边界.如果一个线程对非自己所有的内存块执行了写操作，或者对非自己所有的非共享或者blank的内存块执行了读操作，则需要转入串行写状态.Kendo[8]则只关注存储器竞争中的同步部分，首先提出了基于软件方法来实现确定性同步事件的解决方案.Kendo使用确定的逻辑时间(determine logical time, DLT)，计算每个同步操作的确定性交互，同时保证负载平衡.
综上所述，面对存储器竞争这一可重现调试实现过程中的关键问题，现有的研究从确定性并行和确定性重现2方面出发，给出了很多可行的解决方法.但是现有的方案普遍具有3点缺陷：
1) 泛用性问题.为了解决数据竞争的确定性问题，现有的高效率解决方案都采用了硬件辅助的实现方式，从而无法在商用的硬件平台上使用.而对于一些采用纯软件技术实现可重现调试方法，则往往需要依赖于定制的操作系统，或者高度定制的编译和运行时系统，同样具有泛用性差的问题.
2) 可扩展性差.目前针对可重现调试的技术方案，在方案的测试中，大多数只使用了2～4个线程，只有少数方案测试了8线程条件下的效果，并且在现有的测试结果中，可重现调试的实现代价一般随着线程数的增加会产生超线性的增长.
3) 忽略了调试方法问题.现有的可重现调试技术，其关注点都在于如何保证程序执行的确定性，使得程序中的错误能够重现.但是在错误重现的基础上，却并没有提出指导用户发现错误的具体调试方法，没有实现真正的实用性.
鉴于相关工作的研究现状，我们希望提出的新型可重现调试方法应当能够保证方法的泛用性，保证并行度增加时调试代价的可接受，同时提供给用户一个实用的调试方法指导.本文所提出的SDT就是一种能够同时满足泛用性、调试代价的可扩展性以及能够提供实用调试方法的可重现调试解决方案.在第2节中，我们将详细说明SDT的设计初衷和所采用的具体方法.
SDT在设计时同时考虑到了编写并行程序的用户在调试多核并行程序时所遇到的调试基础问题和调试方法问题.为了表示的方便，在第2～5节中所提到的用户即指代编写多核并行程序并对多核并行程序进行调试的程序编写者.
调试基础方面，需要保证的关键点是多核并行程序运行和调试时的确定性.SDT利用了运行快照序列，通过运行快照序列的捕捉和重现，保证了并行程序调试时的确定性.
调试方法方面，用户所熟悉的调试方式是由粗到细，逐步定位错误的发生位置，并最终发现需要修改的程序代码.SDT采用对运行快照序列进行逐步细化的方式，提供了由粗到细的调试方法支持.
在2.1节和2.2节中，我们将对SDT所使用的两大核心方法：运行快照序列和快照序列的逐步细化进行详细的介绍.
传统的可重现调试技术方案，无论采用确定性重现或是确定性并行的方法，所注重的都是并行程序执行过程的重现.而在SDT的设计中，我们认为，用户在调试过程中真正关注的是在调试过程固定时所能观察到的固定的运行结果.例如在调试存在写突的多线程程序时，用户所关注的并不是线程中所有指令的执行先后顺序，而是写冲突是否会导致某些可以被观察到并影响程序正确执行的运行结果.
因此，SDT并不记录程序的执行过程，转而记录程序的执行结果.在SDT中，我们所记录的运行结果为运行快照序列，通过对运行快照的记录和重现来实现并行程序调试中的可重现.传统可重现调试方法实现的是基于运行过程的物理重现，而SDT中所实现的则是基于观察结果的逻辑重现.
如图1所示，用户所编写并需要进行调试的并行程序的每一次运行，都将产生一个运行快照序列.一个运行快照序列由按照捕捉顺序排列的多个运行快照组成，每个运行快照中包含了并行程序运行至某个快照捕捉点时并行程序的全部断面信息，包括捕捉时刻的并行程序所使用的全部内存以及处理器上下文数据.运行快照的捕捉点由用户在程序运行前根据程序的具体逻辑设置.参照传统串行程序的调试，为了表述的清晰和简明，并突出捕捉点在运行前设置的特性，在本节以及第3，4节中我们称运行快照的捕捉点为离线断点.
Fig. 1 The concept of SDT logical replay
图1 SDT逻辑重现概念示意图
考虑2种调试场景：场景1是用户使用了SDT进行调试，在程序运行结束后顺序观察了运行快照序列中的每一个运行快照.在完成了所有的观察后得到了观察结果A.场景2是用户使用传统的可重现调试方式完成对并行程序的物理重现，在重现的过程中，对参照场景1中离线断点的位置，顺序观察每个位置上的程序运行断面，得到观察结果B.
可以发现，在SDT中每个运行快照都保存了完整的断面信息的情况下，从观察结果A和观察结果B中用户所能得到的信息量是相同的.因此，SDT中从观察角度出发的逻辑重现与传统可重现调试方法从运行角度出发的物理重现，实现了相同的调试效果.
综上，SDT所使用的基于运行快照的调试方法已经十分清晰：在程序运行前由用户在源程序中标记离线断点；运行过程中到达每个离线断点时，暂停并行程序的所有线程，保存当前程序的运行断面为运行快照；运行结束后，用户顺序观察所有的运行快照，等价于并行程序进行了逻辑重现，可以实现和传统物理重现相同的调试效果.
但必须指出的是，为了实现程序调试的确定性，SDT提供给用户使用的断点设置方式为离线断点，即断点必须在程序运行前设置，一旦设置后就不可更改，这实际为调试过程的灵活性带来了一定的牺牲.为了解决这一问题，SDT还额外添加了离线断点属性和快照捕捉配置检查机制.
通过SetBreakpoint给出了SDT所提供的离线断点设置接口.Level，Class，Id，Attrs等均为用户设定的与离线断点相关的属性.而Multiple_mark则用来决定该离线断点是否会被触发多次.这样设计的原因为在并行程序中，一段程序代码往往会被多个线程共用，同时执行，在这种情况下用户可以通过Multiple_mark的设置来保证只有最先达到的线程会触发断点，从而触发快照保存.
SetBreakpoint(Level,Class,Id,Multiple_mark,Attrs)；
Level：快照保存的层次；
Class：快照保存的类别；
Id：快照保存的独立编号；
Multiple_mark：该快照是否会被保存多次；
Attrs:为〈key,value〉二元组的集合，用于自定义快照过滤策略.
通过上述的离线断点属性和快照捕捉配置检查机制，虽然用户仍然必须在程序运行前设置所有的离线断点，但是可以通过更改快照捕捉配置，使得同一并行程序的多次运行产生不同的运行快照序列，以增强SDT调试方法的灵活性.同时快照捕捉配置检查也为之后快照序列的逐步细化提供了快照捕捉的技术基础.
Fig. 2 Process of refined replay execution
图2 细粒度重现过程示意图
在完成了快照序列的捕捉和分析后，用户应当可以在一定粒度上确定程序中错误的发生位置.如图2所示，被调试程序P的执行共生成了S0,S1,S2,S3这4个快照，它们实际将P的执行划分成(begin,S0),(S0,S1),(S1,S2),(S2,S3),(S3,end)共5个区间，其中begin指代P执行的起点，end指代P执行的终点.假设在完成了快照的查看和分析后，用户确定程序中的错误一定发生在区间(S1,S2)中，但是仍无法明确具体的错误代码段，则此时可以应用SDT快照的细粒度重现，完成错误的逐步细化过程.
在执行细粒度重现前，首先需要用户提供起点快照和终点快照，并修改快照捕捉配置.在图2中，由于用户已经确定错误发生在(S1,S2)区间内，则设定S1为起点快照，S2为终点快照.之后SDT会将起点快照还原为一个可执行的进程，进程的状态就是被调试进程在触发起点快照对应的离线断点时的状态.由于快照中已经保存了足够多的信息，包括全部的内存页和处理器上下文，这一还原过程将不具有技术上的困难.被还原的进程将继续正常执行，并且由于快照的捕捉配置已经被修改，还原进程在执行的过程中将能够触发不同的离线断点，从而捕捉到与之前不同的运行快照.这些在细粒度重现过程中新增的运行快照被称为细粒度快照.图2中的S1.0，S1.1和S1.2为新生成的细粒度快照.
在被还原进程执行到达终点快照后，SDT仍将保存新版本的终点快照(图2中的S2.new为新版本快照).随后，SDT会在新版本和原版的终点快照之间执行一致性检查，一致性检查的目的为判定此次的细粒度重现执行是否重现了用户之前通过分析终点快照而发现并粗略定位范围的错误.
由于选定起点快照和终点快照的是编写程序的用户，用户应当在终点快照中发现了某些标志性的变量信息，这些信息代表了错误的出现.因此，SDT在进行上述的一致性检查时采用的是用户判定一致性策略，即由用户指定关键的变量，若用户指定的变量在原版终点快照和新版终点快照中的取值完全相同，则此次执行通过一致性检查，否则此次执行无法通过一致性检查.
如果细粒度重现所产生的新版本终点快照未通过一致性检查，则需要使用相同的起点快照和终点快照，再次重复，直到通过一致性检查为止.在这里我们默认了一个假设，即在重现区间大大缩小(从程序的整体执行缩小到了2个运行快照之间的执行路径)，一致性判定也相对较弱(只判定用户指定的关键变量，而不需要保证原版和新版本终点快照之间完全一致)的情况下，在多次重试的基础上终点快照是可以重现原版快照中的错误的.在当前SDT的设计中还必须保留这一假设，但是在SDT的改进计划中，将会在细粒度重现中加入执行路径搜索机制，以消除这一假设对SDT调试有效性的影响.
在细粒度重现执行成功且通过了一致性检查后，用户便可以继续执行SDT调试过程中的逻辑重现及分析，继续分析程序中的错误，如果仍无法定位则可以继续在细粒度快照中选择新的起点快照和终点快照，继续下一级别的细粒度重现.虽然加入了快照保存的配置检查机制，但是本质上用户在SDT中使用的仍是离线断点，当重现的粒度不断变细时仍然可能出现断点无法覆盖的情况.为了解决这一问题，SDT提供了粗粒度的定时快照保存机制，当现有的离线断点不足以产生出足够细粒度的快照时，可以定时触发出一些新的快照保存点.
SDT系统在实现中可以分解为3个核心的功能部分：快照的捕捉、快照展示和分析、快照的恢复和细粒度重现.
快照捕捉部分在整体上可以分为3个子功能模块：1)提供给用户并行程序调用的SDT程序库；2)负责快照捕捉配置注册和快照收集的SDT辅助服务进程；3)负责快照过滤、捕捉以及传输转移的SDT内核模块.由SDT添加的系统调用如下：
1)GetSnapShot(intpid,char*buffer)，SDT辅助服务进程向SDT内核模块注册下一个运行快照的转存地址；
2)RigisterSnapshot(intpid,char*optionBuffer)，SDT辅助服务进程向SDT内核模块注册快照捕捉配置；
3)TriggerSnapshot(intpid,char*attrBuffer)，SDT程序库向SDT内核模块触发一个离线断点.
SDT程序库和SDT辅助服务进程都会通过系统调用与SDT内核模块进行交互.SDT内核模块共定义了如表1所示的3个系统调用，用以完成SDT用户空间模块和SDT内核空间模块之间的交互.
Table1SoftwareandHardwareInformationofEvaluation
表1测试软硬件环境清单
3.1.1 快照捕捉触发
在触发快照捕捉时，必须对正在执行被调试进程线程的处理器核进行控制，使被调试进程的所有子线程都暂停；否则在快照捕捉的过程中仍会有线程处于执行状态，捕捉到的运行快照将不具有调试和分析的意义.
在控制所有其他线程暂停时，快照捕捉偏差仍是一个需要尽量规避的现象.快照捕捉偏差的概念如图3所示.为了表示的方便，我们称当前正在触发快照保存的进程为P，在P的某一个子线程触发了快照的捕捉后，正在执行该线程的处理器核称为触发核，正在执行P的其他子线程的处理器核称为响应核.以触发核接收到快照捕捉信号的时间点为理想快照捕捉点，最后一个响应核暂停P的子线程执行的时间点为实际快照捕捉点，则两者之间的时间差为快照的捕捉偏差.为了保证快照的有效性，需要尽量缩短快照捕捉偏差.
Fig. 3 Illustration of snapshot capture deviation
图3 快照捕捉偏差说明图
在SDT的实现中，我们摒弃了通过操作系统控制线程暂停的实现方法，而是直接使用了更为底层的IPIs(inter process interrupts)，即跨处理器中断.IPIs是现代多核处理器架构普遍支持的一种中断功能，在Intel的所有商业化多核产品中都有很好的支持.在实现中，触发核接收到快照触发的信号时会立刻向其他所有的处理器核发送IPIs，触发其他所有的处理器核进入SDT系统定义的中断向量.对于其他所有的处理器核，进入中断后首先会判断当前执行的线程是否为P的子线程，如果不是，则继续执行原有程序，否则当前处理器核为响应核.对于响应核，需要立刻暂停当前执行的线程，循环等待触发核发出快照捕捉结束的信号.
3.1.2 快照捕捉执行
在完成了对所有处理器核的识别和控制后，SDT的捕捉过程将进入执行状态.如图4所示，core0为当前的触发核，core1和core2为当前的响应核.
Fig. 4 Illustration of snapshot capture process
图4 快照捕捉执行说明图
在进入捕捉执行状态后，触发核首先执行快照捕捉配置检查.当前离线断点的属性会由用户程序所包含的SDT程序库通过TriggerSnapshot系统调用，在快照捕捉触发时传递给响应核.而当前使用的快照捕捉配置则会在用户程序开始运行前，由SDT辅助服务进程通过RegisterSnapshot传递给SDT内核模块.快照配置检查的具体过程可参见4.1节.
如果当前离线断点通过了快照配置检查，则会同时进入快照捕捉的执行和快照数据传输阶段.响应核会读取当前捕捉的进程P所持有的所有信息，包括所有的处理器上下文以及持有的内存页.同时，在SDT内核模块和SDT辅助服务进程之间，会通过消息队列和GetSnapshot相结合的方式，让触发核可以直接将快照数据转存到用户空间，以减少额外的内存读写操作.
在触发核完成了全部的快照捕捉以及快照数据传输的工作后，会与其他所有的响应核再进行一次同步，随后同时恢复进程P的各个子进程的执行.所有的响应核在快照捕捉的过程中都会处于同步等待的状态，这样的处理虽然在一定程度上会影响系统的整体性能，但是能够有效地避免快照的捕捉对用户并行程序执行产生的影响.
3.1.3 快照增量处理与保存
SDT所保存的运行快照中，包含了用户并行程序所使用的全部内存页.而在2个被触发的离线断点之间，用户并行程序所能修改的内存一般而言是十分有限的.基于这一考虑，SDT在实现中添加了快照的增量保存模式，以减少最终向硬盘写入快照的数据量.
SDT中快照的增量处理由SDT辅助服务进程完成，在接收到一个新的运行快照时，会生成针对此快照的增量片段，如算法1所示，以当前时刻快照内存页数据PageListold和新接受的快照Snapnew为输入，新生成的增量片段newPatch为输出，完成增量快照的计算和维护.上述的快照增量计算均在SDT辅助服务进程中进行.
算法1. 创建增量块.
输入:快照PageListold，Snapnew；
输出:增量块newPatch.
①PageListnew←SplitMemoryPage(Snapnew)；
②Sort(PageListnew,PageListnew.size,AddrComp)；
③oldPage←PageListold.begin()；
④ for eachnewPageinPageListnew
⑤ whileoldPage.addr<newPage.addr&oldPage.hasNext()
⑥oldPage←oldPage.next()；
⑦ end while
⑧ ifoldPage.addr==newPage.addr
⑨pagePatch←getPagePatch(newPage,oldPage)；
⑩newPatch.insertModifiedPage(pagePatch)；
else
newPatch.insertAddedPage(newPage)；
end if
end for
addIncPatch(newPatch)；
PageListold←PageListold；
returnnewPatch.
目前SDT所使用的只是一个较为粗糙的增量快照维护方式.在后续的计划中，SDT中的快照增量存储将更改为页面监视模式.我们会在操作系统内核空间中额外添加页面变更监听模块，使用陷阱来监控所有针对目标进程内存页的写入操作，从而在触发核进行快照捕捉时，可以只捕捉较少数量的内存页.目前基于页面监视模式的快照保存方式已经具有了较为成熟的技术方案[9-10].
在快照展示及分析模块中，我们需要把SDT已经捕捉到的快照数据展示给用户.考虑到用户的使用习惯问题，我们在实现上选择将SDT与GDB相结合.
SDT采用了将运行快照转化为EIF Core数据格式的方式.ELF是一种可以灵活表示二进制程序数据的数据格式[11].在Linux系统中，当程序运行崩溃时，可以生成EIF Core文件，而GDB支持对EIF Core的调试功能，SDT也就利用了这一点，使得SDT中的运行快照可以被主流调试工具解析，在符合用户使用习惯的条件下进行分析和查看.
在灵活调试能力的实现上，由于SDT对于运行快照的查看已经与GDB整合，对程序中变量和当前执行路径的修改均可以通过GDB中的已有命令完成.SDT将采用在GDB外层进行包装的方式，截取所有用户对运行快照进行的修改，并将修改应用于运行快照上.修改后的运行快照可以通过快照的恢复和细粒度重现模块恢复为可运行的进程.
快照的恢复和细粒度重现模块提供了SDT调试方法中细粒度定位错误的能力.在该模块中需要实现2个核心功能：
1) 将SDT中的运行快照转化为可运行的进程.这一功能场景与容错领域的检查点和恢复(checkpoint & replay)十分类似[12]，因此在实现上，我们也采用了和现有checkpoint & replay工具相结合的方式.CRIU(checkpoint
restart in userspace)是一个支持检查点恢复功能的开源软件[13]，SDT在实现上选择了与CRIU的整合.SDT在实现时，将运行快照转化为CRIU需求的数据格式，并由CRIU完成从快照恢复至可运行进程的功能.
2) 细粒度重现的一致性检查.我们使用用户判定一致性的检查策略，由用户指定在运行快照中可以表示错误出现的关键变量.只要关键变量一致就可以认为此次细粒度重现通过了一致性检查.
在后续的改进计划中，我们将添加细粒度执行的执行路径控制功能.这一方法目前已经在可重现调试中得到了成功的应用[14].
在本节中，我们将在一些典型的科学计算程序集中应用SDT，对SDT的实际性能进行测试.测试的详细软硬件环境如表2所示.我们在该系统中安装部署了SDT的所有组件.
我们选择了PARSEC[15]和SPLASH-2[14]测试集中的7个并行计算应用：4个PARSEC测试程序包括blackscholes，fluidanimate，bodytrack和swaption；3个SPLASH-2中的测试程序包括FFT，LU，FMM.
选用上述7个测试程序的原因为：这些测试程序基本覆盖了PARSEC和SPLASH-2中的所有不同的计算特性.例如fluidanimate中包含大量的同步操作，且整体内存占用量较大，可以达到400 MB;而blackscholes则是典型的计算密集型应用，对内存的占用量最小，仅有4 MB.实验中用到的软硬件环境详细信息如表1所示.
Table2OriginalDataofSDTEfficiencyTest
表2SDT效率测试原始数据
Notes: ET:Execution Time;ETS:Execution Time with SDT;TS:Total Snapshot Size;TIS:Total Incremental Snapsot Size.
在应用SDT进行测试时，由于SDT调试过程的第1步是由用户设定离线断点，所以此时必须对所有的benchmark应用程序进行一定的改造.
考虑到用户在分析调试数据时所能投入的精力有限，我们选择为每个Benchmark程序添加了10个可以通过快照捕捉配置检查的离线断点和10个不会通过快照捕捉检查的无效离线断点.在断点的设置时，我们所秉承的准则是尽量使各有效断点均匀分布在Benchmark程序的整体执行过程中.我们将以blackscholes程序为例，说明我们普遍采用的断点设置策略.blackscholes的具体修改如图5所示:
Fig. 5 Modification of blackscholes’s source code
图5 blackscholes源程序修改说明
在4.2节和4.3节中，我们将主要从时间和空间效率两方面对SDT进行测试.时间效率为使用SDT前后Benchmark程序运行时间的差异，空间效率为SDT所产生的运行快照所占用的总存储空间.各个应用程序在使用SDT时所消耗的时间和空间资源的原始数据如表2所示.其中ET表示不使用SDT时程序执行所花费的时间，ETS则表示在使用SDT情况下程序执行所花费的时间，TS表示采用完全保存快照的方法需要保存的数据量，TIS表示采用增量式的快照保存方法需要保存的数据量.
在时间效率的测试中，我们使用未添加SDT调试功能的Benchmark的多次执行时间的平均值作为基准，测试出了添加SDT并捕捉了10个运行快照后所造成的性能损失.
图6中显示，在添加SDT并保存了10个运行快照后，相比于基准时间，多个测试程序在2线程、4线程、8线程下的平均性能损失为19.80%，33.62%，51.88%；最坏情况下的性能损失为76.21%；总体性能损失增长率低于并发度增长率.
Fig. 6 Comparison of total execution time
图6 总执行时间对比示意图
设测试程序在未添加SDT调试库时的平均运行时间为T0，添加后的平均运行时间为T1，则可以认为SDT触发离线断点并捕捉快照所占用的总时间为T1-T0.在下面的分析中，我们使用此种方法，得到了SDT在2线程、4线程、8线程下捕捉快照所占用的总时间.图7中给出了各个Benchmark程序以2线程时的快照为基准，在4线程、8线程条件下的快照捕捉时间增长率.如果SDT的快照捕捉代价线性增长，则增长率的数据应符合最右边的LINER数据项.
Fig. 7 Comparison of snapshot capture time
图7 快照捕捉时间对比示意图
实际的数据结果显示，各个Benchmark程序的平均快照捕捉时间增长率在4线程、8线程的情况下分别为12.57%和41.85%，远远低于线性增长情况下的300%.即使在最差的情况下，8线程下的增长率也小于100%，这表示SDT调试方法所带来的性能损失远小于随线程数增长，具有较好的可扩展性.SDT具有上述扩展性的根本原因为SDT所捕捉的快照数据量随线程数的增长是低于线性的.在一般情况下，多线程程序在并发度增加时，所需额外占据的内存空间仅为新增线程的运行栈，只占进程全部内存占用中的一小部分.需要额外说明的是，图7中的LINER并不是真实Benchmark程序的测试结果，而是给出了一个在捕捉时间代价完全随着线程数线性增长时的假想对比示例.通过与LINER图例的对比可以看出，我们选择的7个测试程序的平均捕捉时间增长率是远低于线性的.
在测试空间效率时，我们的重点在于测试SDT所使用的增量快照保存机制的效果.
图8给出了各个应用在各个线程条件下，采用增量保存方式和采用全量保存方式的对比.结果显示，在平均情况下，2线程、4线程、8线程情况下，增量存储相比于全量存储只会占据15.50%,14.47%,14.12%的空间.同时应当注意到，除去bodytrack和swaption外的大多数的Benchmark程序，其增量存储都会占用小于12%的空间.
Fig. 8 Comparison of snapshot incremental effect
图8 增量快照保存对比图
增量存储中的数据可以分为2部分:1)所有增量开始作用的初始快照;2)多个增量片段.如果认为10个快照所占有的内存数据量是近似相同的，则除去初始快照外，所有的增量片段数据量之和小于总数据量的2%，即小于一个运行快照平均大小的20%.这一数据表明增量快照存储在大多数的计算密集型科学计算应用中将起到非常好的效果.
我们还对各个快照之间内存页面的差异情况进行了进一步的分析，统计出了运行快照所持有的内存页面之间的增加和修改的关系.
设多个运行快照中，每个快照与上一个连续的运行快照相比，发生变更或增加的内存页的数目的综述为ChangeSum；而10个运行快照中包含的内存页面总数为Allsum.则图9中计算的即是ChangeSum在Allsum中所占的比例.结果显示，2线程、4线程、8线程情况下的平均内存页面添加修改比例分别为49.95%,66.79%,66.45%.这一结果表示，如果按照计划实现了基于内存页面监控的增量快照保存机制，SDT的快照保存效率在理论上还有30%以上的提升空间.
Fig. 9 Comparison of memory page change rate
图9 内存页面变化示意图
在多核处理器得到越来越广泛应用的今天，学术界和工业界公认并行程序的调试存在困难，可重现调试技术可以解决调试过程中的不确定性问题，但是普遍具有泛用性差和可扩展性差的特点，且缺乏对用户在调试方法上的指导，无法被广大的并行程序编写者所使用.
本文基于上述的问题，提出了一种基于运行快照序列的并行程序重现调试方法SDT.SDT牺牲了部分调试上的灵活性，但是保证了并行程序调试的确定性，并具有很好的可用性和可扩展性.SDT同时给出了一套完整的由粗到细发现并行程序中问题的调试方法指导，可以有效地指导用户进行调试，具有很强的实用性.
测试结果显示，SDT在8线程的情况下平均对并行程序执行时间的影响为51.88%，同时快照保存的时间消耗随线程数增加的增长率远远小于线性的增长率，具有很好的可扩展性.
我们未来计划在SDT中添加基于内存页面监控的增量快照生成，以及细粒度重现时的执行路径搜索控制.以上2种较为成熟的技术预计能有效地提升SDT的快照捕捉效率并减少细粒度重现时的重试次数.
参考文献
[1]Asanovi K, Bodik R, Demmel J, et al. A view of the parallel computing landscape[J]. Communications of the ACM, 2009, 52(10): 56-67
[2]Nightingale E B, Peek D, Chen P M, et al. Parallelizing security checks on commodity hardware[C]
Proc of the 13th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2008: 308-318
[3]Zhai Jidong, Chen Wenguang, Zheng Weimin. Phantom: Predicting performance of parallel applications on large-scale parallel machines using a single node[C]Proc of the 15th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2010: 305-314
[4]Chen Yunji, Hu Weiwu, Chen Tianshi, et al. LReplay: A pending period based deterministic replay scheme[C]Proc of the 37th Annual Int Symp on Computer Architecture. New York: ACM, 2010: 187-197
[5]Honarmand N, Torrellas J. RelaxReplay: Record and replay for relaxed-consistency multiprocessors[C]Proc of the 19th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2014: 223-238
[6]Qian Xuehai, Sahelices B, Qian Depei. Pacifier: Record and replay for relaxed-consistency multiprocessors with distributed directory protocol[C]Proc of the 41st Annual Int Symp on Computer Architecture. Piscataway, NJ: IEEE, 2014: 433-444
[7]Bergan T, Anderson O, Devietti J, et al. CoreDet: A compiler and runtime system for deterministic multithreaded execution[C]Proc of the 15th Edition of ASPLOS on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2010: 53-64
[8]Olszewski M, Ansel J, Amarasinghe S. Kendo: Efficient deterministic multithreading in software[J]. ACM SIGPLAN Notices, 2009, 44(3): 97-108
[9]Vasavada M, Mueller F, Hargrove P H, et al. Comparing different approaches for incremental checkpointing: The showdown[C]Proc of the 13th Annual Linux Symp. Ottawa, Canada: Linux Symposium, 2011: 69-79
[10]Gioiosa R, Sancho J C, Song Jiang, et al. Transparent, incremental checkpointing at kernel level: A foundation for fault tolerance for parallel computers[C]Proc of the 2005 ACMIEEE Conf on Supercomputing. Piscataway, NJ: IEEE, 2005: 9-23
[11]TIS Committee. Tool interface standards (TIS): Executable and linkable format (ELF)[EBOL]. 1995[2015-07-11]. http:flint.cs.yale.educs422docELF_Format.pdf
[12]Nicolae B, Cappello F. AI-Ckpt: Leveraging memory access patterns for adaptive asynchronous incremental checkpointing[C]Proc of the 22nd Int Symp on High-performance Parallel and Distributed Computing. New York: ACM, 2013: 155-166
[13]Emelyanov P. CRIU: Checkpointrestore in userspace[CP]. 2012[2015-07-11]. http:criu.orgMain_Page
[14]Woo S, Ohara M, Torrie E, et al. The SPLASH-2 programs: Characterization and methodological considera-tions[C]Proc of the 22nd Int Symp on Computer Architecture. Piscataway, NJ: IEEE, 1995: 24-36
[15]Bienia C, Kumar S, Singh J P, et al. The PARSEC benchmark suite: Characterization and architectural implications[C]Proc of the 17th Int Conf on Parallel Architectures and Compilation Techniques. New York: ACM, 2008: 72-81
Wang Bohong, Liu Yi, Zhang Guozhen, and Qian Depei
(Sino-GermanJointSoftwareInstitute,BeihangUniversity,Beijing100191)
AbstractDebugging multi-core parallel program is a well-known difficult problem. The key problem is that parallel problem may introduce many non-deterministic factors. Replay debugging is a promising method to eliminate non-deterministic. However, the state-of-art replay debugging solutions are not suitable for commercial software and hardware architecture. With the growth of concurrent degree, current replay debug method may also have unaccepted overhead. We propose a practical and novel replay debugging scheme name SDT (snapshot debug tool). The key innovation of SDT is using offline breakpoint and abstracting replay execution, instead of performing typical and physical replay execution. SDT can apply on commercial operate system and hardware, while also providing a gradually refined debugging method. According to the experimental results, using SDT will introduce 51.88% extra execution time in average when using 8 threads. When the thread count increases from 1x to 4x, the overhead of SDT debugging will only increase from 1x to 2x, which shows that SDT has strong scalability. It’s a great challenge for SDT to record a large amount of data. The incremental snapshot capture used in our experiments has been proved that it can be effective to reduce the time and data which need to be record so that to improve the SDT performance.
Keywordsreplay debug; program snapshot; deterministic; multi-core parallel program debug; multithread
This work was supported by the National High Technology Research and Development Program of China (863 Program) (2012AA01A302).
基金项目：国家“八六三”高技术研究发展计划基金项目(2012AA01A302)
修回日期：2016
0602
收稿日期：20151209；
中图法分类号TP311; TP302; TP306
WangBohong, born in 1991. Master. His main research interests include high performance computing, parallel computing and parallel program debugging.
LiuYi, born in 1968. Professor and PhD supervisor. Senior member of CCF. His main research interests include computer architecture, high performance computing and computer network (yi.liu@jsi.buaa.edu.cn).
ZhangGuozhen, born in 1987. PhD candidate. His main research interests include high performance computing and parallel program debugging (gzzhang@buaa.edu.cn).
QianDepei, born in 1952. Professor and PhD supervisor, Fellow member of CCF. His main research interests include high performance computer and many-core architecture (depeiq@buaa.edu.cn).