一种多线程程序内存系统模拟器Trace驱动仿真方法

伴随大数据计算时代的到来,片上多核处理器为提高多线程程序服务器吞吐率发挥巨大作用,同时其内存系统的访问延迟越来越影响系统性能.目前,路径驱动(trace-driven)仿真方法比执行驱动(execution-driven)运行速度快,被内存系统研究者广泛采用.但是路径驱动在仿真并发线程时,会同时导致宏观和微观的访存错位.而实际多线程程序运行过程中,不会发生这种访存错位行为.通过理论分析和计算,访存错位引起路径驱动的仿真结果存在明显偏差.针对上述问题,提出了一种方法来避免路径驱动仿真发生宏观和微观访存错位,精确回放采集阶段的多线程程序行为.实验数据显示,在避免宏观访存trace错位后,多线程程序的多个仿真指标出现最高10.22％的变化;对于部分访存密集型的多线程程序,避免微观访存trace错位可以使算数平均IPC出现大于50％的变化.为研究交互线程的内存系统行为提供一种更加准确的路径驱动方法.     

一种基于目录的软件事务性内存实现算法

软件事务性内存(STM)提供同步手段,让多线程程序高效并发执行.STM算法中一般包含记录所访问的共享数据、缓冲投机修改的数据以及处理事务冲突.STM中的主要开销在于维护共享数据访问记录和一致性验证.维护共享数据访问记录主要目的是便于进行验证.冲突检测(conflict detection)判断两个事务能否同时提交,而验证(validation)确保每个线程看到的数据状态是一致的.给出了关于STM一个简单模型,证明在STM中对共享数据的修改是线性的.提出的LDSTM算法通过在目录中维护版本信息,可以在读取各个共享对象时快速确定事务的内存视图是否处于一致状态,可以极大减少冲突检测和验证的开销.该算法可以实现早期发现写一写冲突,减少无效计算.在单线程情况下该算法开销很小.实验数据表明,LDSTM简单高效,冲突检测和验证开销减少明显.     

基于Adaboost模型的并发程序数据竞争语句级检测

针对并发程序数据竞争检测时准确率低和开销大的问题,基于Adaboost模型设计并发程序数据竞争语句级检测方法。对多线程并发程序进行插桩操作,记录指令的相关内存信息,并对提取出的指令集做语句级转化处理,利用语句对相关属性特征构建并发程序Adaboost数据竞争检测模型,实现多线程程序数据竞争检测工具ADR。实验结果表明,相比于Eraser、Djit+和Thread Sanitizer工具,ADR能够在降低时间及内存开销的同时,有效提高分类准确率,验证了所提方法的有效性。     

基于数据特征的内核恶意软件检测

内核恶意软件对操作系统的安全造成了严重威胁.现有的内核恶意软件检测方法主要从代码角度出发,无法检测代码复用、代码混淆攻击,且少量检测数据篡改攻击的方法因不变量特征有限导致检测能力受限.针对这些问题,提出了一种基于数据特征的内核恶意软件检测方法,通过分析内核运行过程中内核数据对象的访问过程,构建了内核数据对象访问模型;然后,基于该模型讨论了构建数据特征的过程,采用动态监控和静态分析相结合的方法识别内核数据对象,利用EPT监控内存访问操作构建数据特征;最后讨论了基于数据特征的内核恶意软件检测算法.在此基础上,实现了内核恶意软件检测原型系统MDS-DCB,并通过实验评测MDS-DCB的有效性和性能.实验结果表明：MDS-DCB能够有效检测内核恶意软件,且性能开销在可接受的范围内.     

动态容忍和检测非对称数据竞争

非对称数据竞争是数据竞争中一种常见的类型.当一个线程在临界区内访问某个共享变量,另外一个线程在临界区外或不同的临界区内同时也访问这个共享变量时,就触发了非对称数据竞争.多线程程序中的非对称数据竞争往往是有害的.为了解决非对称数据竞争引入的问题,提出了ARace.它使用共享变量保护和写缓冲区来动态容忍和检测非对称数据竞争.其中,共享变量保护用于保护临界区内只读和先读后写的共享变量,防止这些变量在临界区外被修改;写缓冲区用于缓存临界区内对共享变量的写操作.ARace不仅可以容忍临界区内和临界区外之间的非对称数据竞争,还可以对并发临界区之间的非对称数据竞争进行检测.ARace既不依赖程序源代码和编译器的支持,也不依赖额外硬件的支持.此外,还提出了一种通过动态二进制插桩技术实现ARace的方法.实验结果表明,ARace在保证容忍和检测非对称数据竞争的同时,并未引入很大的性能开销和内存开销.     

基于数据对象规模的Rank级内存分配方法

利用主存的多bank/rank/channel结构挖掘访存并行性和局部性,是提高系统性能的重要手段.相关研究工作通过sub-rank技术增加可并行工作的存储资源,或在并行程序之间对bank划分,以隔离访存冲突.但上述方法没有考虑在bank/rank资源共存的情况下,单个程序内部数据对象间的冲突问题.通过观察数据在主存中的分布,发现程序的数据倾向聚簇于单个rank中,并提出了一种基于数据对象规模的rank级内存分配方法(data object scale aware rank-level memory allocation,DSRA).DSRA将冲突开销较大的数据对象分散到不同的rank,利用增长的bank/rank资源提高访存性能.DSRA工作在操作系统层,基于编译器和操作系统提供的信息来分析数据对象间的冲突开销,既不用修改源码,也不依赖特殊的底层硬件.基于2款真实处理器对来自NAS Benchmark和SPEC CPU2000中的存储敏感型基准测试程序进行评测.结果表明,在不影响cache失效率的情况下,DSRA通过减少主存访问周期数,可以降低程序的执行时间.与已有的优化技术相比,性能平均提高6.8%,最高性能提升幅度为16%.     

面向流式处理系统的对象管理方法

在车联网的应用实践中,人们将分析车辆数据的任务运行在流式计算系统中。在运行分析中发现,这些任务具有运行周期长,处理延迟低,任务有状态等需求和特点,并且计算过程中需要在内存中保存大量计算参数和中间状态等数据对象,其中大量的数据对象并不活跃,任由其占用内存造成了系统资源的浪费。针对该问题开展研究,给出了流式任务的数据对象管理方法,优化了内存的使用。为流式数据对象建立生命周期模型,采用应用驱动、数据驱动的模型参数确定方法为流式数据对象设置合适的过期参数,设计车联网测试用例,验证该生命周期管理方法的有效性。实验结果表明,该方法在用户可接受的处理延迟范围内,能够有效地减少流式系统中不活跃对象的数目,达到了优化内存,降低资源开销的目的。     

基于线程调度顺序控制的多线程程序测试

随着多核技术越来越普及,多线程程序的编程也越来越流行。但是多线程程序的正确性问题已经严重影响软件可靠性,且现有的测试技术不能很好地满足多线程程序的需求。本文重点研究多线程程序中最常见的一种bug,即数据竞争,提出一种基于线程调度顺序控制的测试方法。该方法混合静态方法和动态方法,能够有效地找到多线程程序中存在的数据竞争,且能够区分出哪些数据竞争是有害的,需要程序员优先修复。实验结果显示,对于数据竞争的触发概率,本文的方法使其平均从0.53%提高到79.2%,且本文所引入的运行时开销平均只有80%,与相关方法所引入370%的开销相比更优。     

基于对象的C程序边界安全检测改进技术

C语言对内存操作不进行边界安全检测,这使C程序具有高执行效率,但也产生各种安全问题,例如数组越界、指针访问越界、C库函数的非法操作等。基于对象的运行时验证技术能实时监测程序的运行行为,自动找出程序中存在的漏洞。在原有基于对象技术的基础上,改进多维数组和结构体变量的地址范围记录方式,用2次地址查询操作检测指针访问,用平衡二叉树优化存储结构。实验结果表明,改进的方法优于传统的基于对象技术。     

多线程程序时序分析的隐Markov模型

针对多线程程序数据竞争分析与检测困难的问题,提出一种基于隐Markov 模型的多线程程序时序分析方法.用随机变量不确定性刻画不同线程之间时序上的交互关系,分析数据竞争条件下程序不确定结果的概率分布情况;建立多线程程序时序分析的隐Markov 模型,使用Baum-Welch 和前向算法仿真上下文对程序实际运行状态的影响.实验结果表明,该模型能够快速有效反映多线程执行时序,用于指导多线程程序时序竞争检测过程.     

Data race avoidance and replay scheme for developing and debugging parallel programs on distributed shared memory systems

Distributed shared memory (DSM) allows parallel programs to run on distributed computers by simulating a global virtual shared memory, but data racing bugs may easily occur when the threads of a multi-threaded process concurrently access the physically distributed memory. Earlier tools to help programmers locate data racing bugs in non-DSM parallel programs are not easily applied to DSM systems. This study presents the data race avoidance and replay scheme (DRARS) to assist debugging parallel programs on DSM or multi-core systems. DRARS is a novel tool which controls the consistency protocol of the target program, automatically preventing a large class of data racing bugs when the parallel program is subsequently run, obviating much of the need for manual debugging. For data racing bugs that cannot be avoided automatically, DRARS performs a deterministic replay-type function on DSM systems, faithfully reproducing the behavior of the parallel program during run time. Because one class of data racing bugs has already been eliminated, the remaining manual debugging task is greatly simplified. Unlike previous debugging methods, DRARS does not require that the parallel program be written in a specific style or programming language. Moreover, DRARS can be implemented in most consistency protocols. In this paper, DRARS is realized and verified in real experiments using the eager release consistency protocol on a DSM system with various applications.     

Flexible resource monitoring of Java programs

Monitoring resource consumptions is fundamental in software engineering, e.g., in validation of quality requirements, performance engineering, or adaptive software systems. However, resource monitoring does not come for free as it typically leads to overhead in the observed program. Minimizing this overhead and increasing the reliability of the monitored data is a major goal in realizing resource monitoring tools. Typically, this is achieved by limiting capabilities, e.g., supported resources, granularity of the monitoring focus, or runtime access to results. Thus, in practice often several approaches must be combined to obtain relevant information.We describe SPASS-meter, a novel resource monitoring approach for Java and Android Apps, which combines these conflicting capabilities with low overhead. SPASS-meter supports a large set of resources, flexible configuration of the monitoring scope even for user-defined semantic units (components), runtime analysis and online access to monitoring results in a platform-independent way. We discuss the concepts of SPASS-meter, its architecture, realization and validation, the latter in terms of case studies and an overhead analysis based on performance experiments with SPASS-meter, OpenCore and Kieker. SPASS-meter provides a detailed view of the runtime resource consumption at reasonable overhead of less than 3% processing power and 0.5% memory consumption in our experiments.     

对象存储系统中一种高效的分层对象布局算法

在对象存储系统中,如何有效地在对象存储设备上分布对象是其面临的重大挑战.需要一个能够常数时间内定位对象,同时能公平地分布对象以及自适应存储规模变化的对象布局算法.目前大部分布局算法只能适应单层模式,少数的多层模式对设备配置有严格的要求,而且无法在常数时间内定位对象,自适应性较差.提出了一种新的分层对象布局算法,首先使用最大最小聚类算法将设备集合进行分类,支持灵活的设备配置.然后使用提出的EFAH Hashing算法在集群间和集群内分布对象.理论和实验证明,新的分层对象布局算法可以在常数时间内定位对象,从而减轻元数据服务器的计算量.同时可以在设备之间较公平地分布对象,达到I/O负载均衡的目的.而且在设备集合变化时,迁移较少的对象数以满足对象再次分布的公平性.     

目标导向的多线程程序UAF漏洞预测方法

Use-After-Free （UAF）漏洞是多线程程序的常见并发缺陷.预测性UAF漏洞检测方法因兼顾误报率和漏报率而备受关注.然而,已有的预测性UAF检测方法未结合待检测目标作针对性优化,当程序规模大或行为复杂时会导致检测效率低下.为解决上述问题,本文提出一种目标导向的多线程程序UAF漏洞检测方法.首先,由程序运行轨迹挖掘程序的Petri网模型;之后,针对每一个潜在可构成UAF漏洞的内存Free/Use操作对,以触发该漏洞为目标导向,在程序的Petri网模型中添加保持操作间因果约束和数据一致性的行为控制结构,在此基础上设计一种基于Petri网反向展开的UAF漏洞检测方法.该方法每次只针对一个潜在的UAF漏洞有针对性地验证其真实性,从而保证检测的效率.与此同时,为减少待检测的潜在UAF漏洞数量,提出一种新型向量时钟进行Free操作与Use操作间的因果关系自动识别,据此对潜在的UAF漏洞进行筛选.结合多个程序实例对所提方法进行了实验评估.实验结果表明,所提方法在检测的效率和准确性方面较主流方法有所提高.     

基于Petri网展开的多线程程序数据竞争检测与重演

数据竞争是多线程程序的常见漏洞之一,传统的数据竞争分析方法在查全率和准确率方面难以两全,而且所生成检测报告难以定位漏洞的根源.鉴于Petri网在并发系统建模和分析方面具有行为描述精确、分析工具丰富的优点,提出一种基于Petri网展开的新型数据竞争检测方法.首先,对程序的某一运行轨迹进行分析和挖掘,构建程序的一个Petri网模型,它由单一轨迹挖掘得到,却可隐含程序的多个不同运行轨迹,由此可在保证效率的同时降低传统动态分析方法的漏报率;其次,提出基于Petri网展开的潜在数据竞争检测方法,相比静态分析方法在有效性上有较大提升,而且能明确给出数据竞争的产生路径;最后,对上一阶段检测到的潜在数据竞争,给出基于CalFuzzer平台的潜在死锁重演调度方法,可剔除误报,保证数据竞争检测结果的真实性.开发相应的原型系统,结合公开的程序实例验证了所提方法的有效性.     

Local Painting and Deformation of Meshes on the GPU

We present a novel method to adaptively apply modifications to scene data stored in GPU memory. Such modifications may include interactive painting and sculpting operations in an authoring tool, or deformations resulting from collisions between scene objects detected by a physics engine. We only allocate GPU memory for the faces affected by these modifications to store fine‐scale colour or displacement values. This requires dynamic GPU memory management in order to assign and adaptively apply edits to individual faces at runtime. We present such a memory management technique based on a scan‐operation that is efficiently parallelizable. Since our approach runs entirely on the GPU, we avoid costly CPU–GPU memory transfer and eliminate typical bandwidth limitations. This minimizes runtime overhead to under a millisecond and makes our method ideally suited to many real‐time applications such as video games and interactive authoring tools. In addition, our algorithm significantly reduces storage requirements and allows for much higher resolution content compared to traditional global texturing approaches. Our technique can be applied to various mesh representations, including Catmull–Clark subdivision surfaces, as well as standard triangle and quad meshes. In this paper, we demonstrate several scenarios for these mesh types where our algorithm enables adaptive mesh refinement, local surface deformations and interactive on‐mesh painting and sculpting.     

基于硬件辅助的用户态并行程序记录方法

程序调试工作的首要基础是错误可重现,然而并行程序执行过程存在天然的不确定性,尤其在多核处理器上,如何重现并行程序的错误是一个巨大的挑战.现有的方法或记录整个系统的状态或需要细粒度插桩,存在可用性差与运行时开销大等问题.本文首次提出一种基于硬件辅助的面向用户态并行程序的轻量级记录与重放方法,该方法通过软件协助来记录信号、系统调用与操作系统调度相关的序关系;利用硬件记录访存冲突,同时在记录过程中采用基于目录的方法来压缩日志存储.通过在16核模拟平台上评估,本文提出的方法不仅方便了用户态并行程序调试,同时减少了81%的存储日志开销.     

支持多核并行程序确定性重放的高效访存冲突记录方法

多核系统中并行程序执行过程的不确定性给程序调试带来了很大的困难.准确记录初始执行中冲突访存的次序是并行程序确定性重放的基础.提出了通过建立精确happens-before关系记录访存冲突的方法.此方法利用简洁高效的地址冲突检测机制确定冲突访存操作在执行中所处happens-before序关系的位置,可以抑制部分记录信息的产生,从而有效减少记录信息.与其他方式方法相比,可以进一步压缩17%的记录条数.采用逻辑向量时钟描述冲突访存操作间的happens-before关系,与采用标量时钟相比,可以避免happens-before关系的误识,降低重放执行时并行度的损失.