计算机系统模拟器研究综述

计算机系统模拟器已经成为计算机系统结构领域研究中不可或缺的工具,真实计算机系统的不断发展对模拟器的性能要求也越来越高,模拟器的性能提升也促进了真实计算机结构和性能上的进步.为了提升性能,模拟器的发展经历了从串行单线程模拟到多处理单元并行模拟的发展趋势.串行模拟器和并行模拟器分别针对各自的模拟目标和模拟过程提出了各种优化方案,串行模拟器研究者提出了交织码、二进制翻译、FPGA加速、模拟分离等加速技术,而并行模拟器在串行模拟器基础上针对自己特有的支撑架构以及负载均衡、同步机制和通信机制等问题提出了各种解决方案.

非默认规则线技术下基于多策略的时延驱动层分配算法

层分配作为超大规模集成电路物理设计中的关键环节,在决定布线方案的时延起到非常重要作用.为了优化集成电路的时延性能,现有的层分配工作通常注重优化互连时延和通孔数量,但要么未考虑到对线网中时序关键段的分配问题,要么对线网段的时序关键性的表示不够合理,最终使得算法的时延优化不够理想.为此,本文提出一种非默认规则线技术下基于多策略的时延驱动层分配算法,主要包含4种关键策略:(1)提出轨道数感知的层选择策略,增强层分配器为线网段选择合适布线层的能力;(2)提出多指标驱动的初始线网排序策略,综合考虑线长、信号接收器数和可布线轨道资源等多个指标为线网确定层分配优先级,从而获得高质量的初始层分配结果;(3)提出线网段调整策略,通过重绕线网,将时序关键段调整至上层布线层,优化线网时延;(4)提出线网段时延优化策略,对存在溢出线网进行拆线重绕,从而可同时优化时延和溢出数.实验结果表明,本文提出的算法相比于现有的层分配算法能够在时延和通孔数两个指标上均取得最佳,并且保证不产生溢出.

污点分析技术的原理和实践应用

信息流分析可以有效保证计算机系统中信息的保密性和完整性,污点分析作为其实践,被广泛用于软件系统的安全保障技术领域.对近些年来面向解决应用程序安全问题的污点分析技术进行综述:首先,总结了污点分析的基本原理以及在应用中的通用技术,即,使用动态和静态的方法解决污点传播;随后,分析该技术在移动终端、互联网平台上的应用过程中遇到的问题和解决方案,包括解决Android应用隐私泄露与检测Web系统安全漏洞的污点分析技术;最后,展望该技术的研究前景和发展趋势.

带权图的均衡k划分

带权图的均衡k划分是把一个图的顶点集分成k个不相交的子集,使得任意2个子集中顶点的权值之和的差异达到极小,并且连接不同子集的边权之和也达到极小.这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域,它已被证明是NP完全问题.首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法.该算法在保证子集均衡的条件下,采用最大化同一子集内部边权之和的策略来构造每一个顶点子集;构建子集S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中,直到子集S的顶点权值之和满足要求.此外,采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化.实验结果表明,当k分别取值为2,4,8时所提算法分别在86%,81%,68%的基准图上求得的平均解优于当前最新算法求得的平均解;解的最大改进幅度可达60%以上.

低熵云计算系统

当前的云计算系统,不论是虚拟化云还是分区云,难以同时满足用户体验和系统效率需求,产业界和学术界都开始研究下一代云计算系统以应对这个难题.本文指出,这个难题的一个重要原因是计算系统熵(无序、干扰和不确定性)居高不下,并归纳了云计算系统中存在的4类无序现象.本文提出了低熵云计算系统的学术概念,刻画了其主要特点,比较了低熵云计算系统与虚拟化云和分区云在用户体验、开发效率、运行效率、资源适配方面的区别,并讨论了低熵云的新概念和新技术:(1)不同于图灵可计算性和算法可计算性的实用可计算性概念,形式化地刻画了云计算行业的"用户体验差的功能是不存在的功能"的实践经验;(2)刻画云计算系统能够实现实用可计算性的充分必要条件,即DIP猜想;(3)支持DIP猜想,即能够区分、隔离、优先化计算任务相空间,从而降低干扰,有潜力同时满足用户体验和系统效率需求的标签化von Neumann体系结构;(4)适配深度学习负载与神经网络处理器的云计算协同设计技术.

矩阵形状无关的并行编译优化

矩阵计算是科学计算中的重要应用,传统编译优化虽然能够大大提升规则矩阵乘法的性能,但对于不规则的矩阵乘法,即使加入编译优化也仅能获得领域专家1%的性能.提出基于模式的矩阵乘法编译优化,通过对矩阵乘法计算模式制定对应的优化策略,使形状规则和形状不规则的矩阵乘法都能取得良好的性能.在优化策略中引入数据布局重组优化是缩小不规则与规则矩阵乘法性能差距的关键,通过数据布局重组能够实现对不规则矩阵中数据元素的连续访问,从而提高数据的局部性.实验表明,基于模式的编译优化方法能够使规则和不规则矩阵乘法运算性能分别比商用编译器(icc)提高34%和43倍,且该方法具有良好的可扩展性.

基于静态调度的多线程程序分析方法

静态多线程程序分析是一种在编译时刻分析多线程程序的执行行为和特征的有效方法。本文通过分析多线程程序实际执行的特点,提出了一种基于静态调度的多线程分析方法。该方法通过模拟多线程程序的动态执行方式,从而在不运行程序的情况下也能较准确地获得多线程的行为特征。实验表明,该分析方法可以有效地提高多线程程序中同步关系的识别和匹配精度,为分析和检测多线程性能瓶颈以及程序错误等信息奠定了基础。

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

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

基于软硬件协同设计的解释器指令分派方法

为了降低指令分派造成的运行开销以提高解释器的性能,提出了一种采用软硬件协同设计的解释器指令分派方法。其核心思想是在软件层面通过对指令分派表进行优化以消除了代价较高的地址常量加载操作,在硬件层面通过扩展处理器的访存指令进一步实现基于硬件支持的访存加速。软硬件协同设计可以最大限度地降低由指令分派引入的运行时开销,从而提升解释执行的效率。试验结果表明,该方法能够显著提升解释器的性能。对于SPECjvm98和Da Capo测试集,解释器总体性能提升了11.5%,且单项性能的最大提升幅度高达15.4%。该方法通用性强,实现代价低,适用于现代主流处理器平台上高性能解释器的设计和优化。

编译队列监视下的Size-Speed动态编译调度算法

针对动态编译影响虚拟机启动性能和响应速度的问题,研究了动态编译系统的优化技术,提出了编译队列监视下的Size-Speed动态编译调度算法。该Size-Speed调度算法以程序中方法的运行速度和方法本身的大小为参数计算调度的优先级,使得调度既能适应程序的动态行为,又能提高动态编译的吞吐量。此外,在调度的同时进行编译队列监视,通过跟踪编译队列中方法的活跃度,及时删除队列中不再活跃的方法,进一步降低了动态编译的开销。实验结果表明,该算法能够显著提升系统的启动性能和响应速度。在DaCapo的测试中,虚拟机总体性能提升了12.4%,单项性能的最大提升幅度高达54.3%。该算法通用性强,实现代价低,适用于绝大多数动态编译系统。

基于NUMA架构的解释器访存优化设计与实现

为了提高非一致内存访问(NUMA)架构虚拟机解释器的访存性能,研究了解释器在NUMA架构下的访存优化技术,提出了一种NUMA架构下的解释器访存优化方案,而且设计并实现了解释器的静态指令分派优化方法和动态指令分派优化方法。根据这一方案虚拟机启动时首先获取NUMA节点信息,并在每个NUMA节点中自动生成解释器所需的全部数据结构;解释器在运行时,通过静态或动态的指令分派技术来实现其执行线程在NUMA节点上访存的局部化。试验结果表明,上述方法能够显著提升解释器在NUMA系统中的性能。在DaCapo测试集上的总体性能提升了8%,最高性能提升幅度高达23%,而且算法实现代价低,适用于绝大多数的NUMA服务器系统。