TACLeBench中内核程序循环级推测并行性分析

线程级推测（TLS）技术可挖掘程序并行执行潜能,提高多核资源利用率,但目前TACLeBench的内核基准仍未在TLS并行化中得到有效分析。针对该问题设计了循环级推测执行的剖析方案和剖析工具。选取7个代表性的TACLeBench内核基准程序,首先对程序进行初始化分析,选取程序热点片段插入循环标识;其次对这些片段进行交叉编译,记录程序推测线程与内存地址相关数据,剖析其循环级最大潜在并行性;最后综合探讨程序运行时的特征（线程粒度、可并行化覆盖率、依赖特征）以及源码对加速比的影响。实验结果表明：1）该类程序适合采用TLS加速,与串行执行结果相比,循环结构的推测执行下的大部分程序的加速比在2以上,其中最高加速比达到20.79;2）利用TLS加速TACLeBench内核程序时,多数应用可有效利用4核到16核的计算资源。     

基于自适应线程束的GPU并行粒子群优化算法

基于统一计算设备架构（CUDA）对图形处理器（GPU）下的并行粒子群优化（PSO）算法作改进研究。根据CUDA的硬件体系结构特点,可知Block是串行执行的,线程束（Warp）才是流多处理器（SM）调度和执行的基本单位。为了充分利用Block中线程的并行性,提出基于自适应线程束的GPU并行PSO算法：将粒子的维度和线程相对应;利用GPU的Warp级并行,根据维度的不同自适应地将每个粒子与一个或多个Warp相对应;自适应地将一个或多个粒子与每个Block相对应。与已有的粗粒度并行方法（将每个粒子和线程相对应）以及细粒度并行方法（将每个粒子和Block相对应）进行了对比分析,实验结果表明,所提出的并行方法相对前两种并行方法,CPU加速比最多提高了40。     

一种基于Inter-warp异构性的缓存管理与内存调度机制

在GPU中,一个warp内的所有线程在锁步中执行相同的指令。某些线程的内存请求可以得到快速处理,而其余请求会经历较长时间。在最慢的请求完成之前,warp不能执行下一条指令,导致内存发散。对GPU中warp间的异构性进行了研究,实现并优化了一种基于inter warp异构性的缓存管理机制和内存调度策略,以减少内存发散和缓存排队延迟的负面影响。根据缓存命中率将warp分类,以驱动后面的3个组件：（1）基于warp类型的缓存旁路技术组件,使低缓存利用率的warp进入旁路,不访问L2缓存;（2）基于warp类型的缓存插入/提升策略组件,防止来自高缓存利用率warp的数据被过早清除;（3）基于warp类型的内存控制器组件,优先处理从高缓存利用率的warp接收到的请求,并优先处理来自相同warp的请求。基于warp间异构性的缓存管理和内存调度机制在8种不同的GPGPU应用中,与基准GPU相比,平均加速18.0％。     

嵌入式应用中的循环级线程推测并行性分析

如何有效利用多核提供的丰富晶体管资源对串行程序的执行进行加速是当前研究中的热点问题。线程级推测（thread-level speculation,TLS）技术旨在充分利用多核资源,最大化地开发出串行代码中存在的潜在并行性。目前TLS技术已经在多种串行应用的并行化工作中得到有效利用,但嵌入式应用程序仍未在推测并行化方面进行有效的分析。因此,选取了八个具有代表性的嵌入式应用,对其在循环级推测并行化中的性能提升潜力和运行时特征（数据依赖、线程粒度和并行覆盖率）进行探讨。实验结果表明,利用线程级推测并行化嵌入式应用的加速效果优于指令级并行技术,实验中的最大加速比达到了13.29;在嵌入式应用领域,该技术可以有效地利用4到8核的计算资源。     

基于数据流的测试用例自动生成研究

目前的数据流测试技术存在缺乏具体的数据驱动方法,测试用例的生成过程没有与测试需求结合起来等问题。基于此,文中提出一种自动生成测试用例的模型（TRGA）,利用控制流图（CFG）计算生成测试用例所需的变量的定义使用对,使用数据类型结构图（DTG）来作为创建测试对象的数据驱动,利用遗传算法的搜索能力来生成数据,并提出了一种新的适应度计算方法。实验结果表明,该模型能够在减少搜索时间,降低生成测试用例规模的同时达到较高的测试覆盖率。     

针对能耗热点的SPM静态分配管理策略

综合考虑程序的指令块、数据块、全局变量对程序执行能耗的影响,使用带权重扩展控制流图（WECFG）将应用程序划分成各类逻辑节点,通过SPM平均访问能耗值计算出逻辑节点平均能耗,以及各逻辑节点的能耗密度。以能耗热点为依据构造SPM分配的整数线性规划算法（ILP）,转化成以能耗密度为优先权的0-1背包算法。仿真结果表明,使用该分配策略的SPM空间分配,比不使用SPM时的能耗量平均减少34.8%左右。     

面向国产异构平台的OpenMP Offload共享内存访存优化

国产异构处理器DCU(deep computing unit)上的本地数据共享（local data share,LDS）是一种低延迟、高带宽的显式寻址内存。国产异构系统的OpenMP未提供LDS访问的编程接口,导致未有效地利用LDS硬件实现数据的高效访存。针对此问题,研究了面向DCU平台的OpenMP Offload执行模式和LDS的分配方法,以及特定于LDS访存的指令结构,实现了LDS访存的手动支持。另外针对于OpenMP Offload的不同执行模式,在此优化方法的基础上实现了LDS访存的自动化,形成了一套面向国产异构平台的高效访存策略。实验采用polybench标准测试集进行测试,利用手动和自动优化方法在单线程模式下平均加速比可达2.60,利用手动优化方法在多线程non-SPMD模式下平均加速比达1.38,利用自动优化方法在多线程SPMD模式下平均加速比达1.11。实验结果表明LDS访存的自动和手动支持有助于提高OpenMP异构程序运行速度。     

基于负载瞬时IPC性能的同时多线程处理器取指策略

同时多线程处理器在每时钟周期从多个线程读取指令执行,极大地提高了指令吞吐率.文中简单介绍了SMT技术,讨论了常用的取指策略,比较了各策略在提高性能方面的优劣.给出特定负载下理论上的最优取指策略,在此基础上提出一种基于负载瞬时IPC性能的动态取指策略IPCBFP.实验表明,该策略可以有效地提高负载的性能,平均加速比对于两线程负载可以达到17%,对于四线程负载可以达到8%.该策略还具有平均占用指令队列项少,指令队列冲突率低的特点,而且,对降低SMT的Cache失效率和TLB失效率方面也有一定的作用.     

面向异构多核系统的多任务流并行编程模型设计

目前的多任务流并行编程模型难以探测到异构多核系统中存的慢任务和落后任务,存在调用开销高、计算开销高和编程加速比低的问题。为此,设计了新的面向异构多核系统的多任务流并行编程模型。通过寄存器重定向、指令迁移、分离发射和线程切换4个部分组建多任务流并行编程模型,并设计了任务探测算法,探测异构多核系统中存在的慢任务和落后任务,提高了异构多核系统在多任务并行处理过程中的编程灵活性。测试结果表明,该模型的调用开销和计算开销均较低,且编程加速比高。     

面向CPU/MIC异构架构的K-Means向量化算法

在大数据背景下,以K-Means为代表的聚类分析对于数据分析和挖掘十分重要。海量高维数据的处理给K-Means算法带来了性能方面的强烈需求。最新提出的众核体系结构MIC（many integrated core）能够为算法加速提供众核间线程级和核内指令级并行,使其成为K-Means算法加速的很好选择。在分析K-Means基本算法特点的基础上,分析了K-Means算法的瓶颈,提出了可利用数据并行的K-Means向量化算法,优化了向量化算法的数据布局方案。最后,基于CPU/MIC的异构架构实现了向量化K-Means算法,并且探索了MIC在非传统HPC（high performance computing）应用领域的优化策略。测试结果表明,K-Means向量化算法具有良好的计算性能和扩展性。     

面向持续集成测试优化的强化学习奖励机制

持续集成环境下的测试存在测试用例集变化大、测试时间有限和快速反馈等需求,传统的测试优化方法难以适用.强化学习是机器学习的一个重要分支,其本质是解决序贯决策问题,可以用于持续集成测试优化.但现有的基于强化学习的方法中,奖励函数计算只包括测试用例在当前集成周期的执行信息.从奖励函数设计和奖励策略两个方面开展研究.在奖励函数设计方面,采用测试用例的完整历史执行信息替代当前执行信息,综合考虑测试用例历史失效总次数和历史失效分布信息,提出了两种奖励函数.在奖励策略方面,提出对当前执行序列的测试用例整体奖励和仅对失效测试用例的部分奖励两种策略.在3个工业级被测程序进行实验研究,结果表明：（1）与现有方法相比,所提出的基于完整历史执行信息奖励函数的强化学习方法可以大幅度提高持续集成测试序列的检错能力;（2）测试用例历史失效分布有助于发现潜在失效的测试用例,对强化学习奖励函数的设计更加重要;（3）整体奖励与部分奖励两种奖励策略受到被测程序的多种因素影响,需要根据实际情况具体选择;（4）包含历史信息的奖励函数会增加时间消耗,但并不影响测试效率.     

神威·太湖之光上排列熵算法异构并行加速

为增加检测突变信号的时效性，提高各种故障检测系统的效率，提出在“神威·太湖之光”上基于两级并行模式改进的排列熵(PE)算法。在节点间采用MPI(信息传递接口)并行编程模型，通过对等模式轮询调度方式解决多文件负载不均衡问题；在核组内采用Athread(加速线程库)并行编程模型，通过相空间构建重构矩阵，实现从核级数据划分；采用双缓冲技术实现从核计算与访存的重叠，减少主从通信时间；利用DMA通信和重组传输数据的方法，减少主从通信次数。使用15个LDK UER204滚动轴承全寿命周期实验数据进行测试，结果表明，单核组性能较主核版本最高可获得11.86倍加速，128核组最高实现123.73倍的性能提升。     

全球涡分辨率并行海洋模式POP在神威蓝光上的移植和应用

基于中国自行研制的超大规模并行计算机神威蓝光平台,对海洋环流模式POP进行移植和进一步优化,并进行模式和机器的并行测试。测试结果表明:0.1度分辨率在5 000核以内达到了线性加速比,随着使用线程数目的增多,虽然加速比依然增加,但是加速效率在降低,当线程数目达到24 000的时候加速比出现降低,加速效率只有12.6%;0.05度分辨率可在12 000核以内达到了线性加速比,同样随着线程数目的增多加速在增多但加速效率在降低,当线程数目达到32 000的时候加速比出现降低,加速效率只有25.7%。经过优化后的海洋环流模式POP在神威蓝光并行计算机系统上具有良好的兼容性,并行效率较高,而且具有很强的可扩展性,可用来开展超大规模的并行计算。对测试结果的进一步分析发现,发展并行性良好的线性方程组求解方案、快速高效的计算网络协议等问题是未来发展高分辨率模式中需解决的问题。     

汇编级软硬结合的控制流检测方法

控制流检测技术是防止由于瞬时故障造成程序错误运行的有效手段之一,在ARGOS卫星上测试过的基于汇编语言的软件控制流检测算法CFCSS具有较高的错误检测能力和较低的冗余指令开销,实用性较强,但此算法存在检测混淆和检测出错现象.为此,首先阐述了CFCSS算法中存在的检测混淆和检测出错现象;接下来根据汇编语言特点,修改了基础基本块的选择方法和多调整签名值赋值语句的插入位置,提出了改进的ICFCSS控制流检测算法;为了在ICFCSS算法基础上进一步提高错误检测能力、降低故障延迟时间和冗余指令开销,提出了软硬结合的ICFCSSHS控制流检测方法,此方法在编译程序时只增加了和签名有关的信息,在程序运行时通过译码阶段判指令类型来触发相应的硬件完成控制流检测.实验表明,此方法的冗余代码空间开销比CFCSS算法减少了21.5%,平均未检测出错误率仅为1.5%,具有一定的使用价值.     

JUTA: 一个Java自动化单元测试工具

描述了一个Java自动化的单元测试工具JUTA.JUTA首先调用工具Soot解析单个Java方法的源码,并将源码解析成一个控制流图.在此基础上,采用符号执行的方法分析控制流图上的路径.工具能够自动地产生满足覆盖率标准的程序的测试用例.这种方法产生的所有测试用例都是可执行的,并且一般来说具有较小的测试用例数.如果用户能够合理地给出描述程序错误的断言,框架JUTA能够自动地检查源码中部分特定类型的错误.实验结果表明工具对Java单元代码的动态测试和静态测试均能在可接受的时间内给出有效的结果.     

多核计算机上并行生成类测试用例

通过类的数据流分析计算出实例变量的“定义-使用”对信息以及成员函数的前置和后置条件,利用类的继承多态性对被测试类进行预处理。在JPF中设置搜索环境,将测试用例生成问题简化成模型检测中寻找反例的问题,提出一种在多核计算机上实现的线程级并行生成类测试用例的方法。实验结果表明,该方法可以减少测试生成所需的状态数和运行时间,算法可使用的处理核心越多、测试生成所需的时间越少。     

多核多线程结构线程调度策略研究

片上多核多线程（CMT）结构兼具了片上多处理（CMP）和同时多线程（sMT）结构的优势，支持片上所有处于执行状态的线程每周期并行执行，导致核内与核间硬件资源共享和争用问题。该文在阐述CMT结构的资源共享特征并简要介绍SMT线程调度发展状况的基础上，主要围绕以减少资源争用为目标的线程调度策略和资源划分机制等热点，分析其研究现状，论述已有策略在处理这些问题上的优缺点，并探讨了可能的研究发展方向。     

面向多线程多道程序的加权共享Cache划分

并行应用在共享Cache结构的多核处理器执行时,会因为对共享Cache的冲突访问而产生性能下降和执行时间不确定的现象.共享Cache划分技术可以把共享Cache互斥地分配给多个进程使用,是解决该问题的有效方法.由于线程间的数据共享,线程数目不同的应用对共享Cache的利用率不同,但传统的以失效率最低为目标的共享Cache划分算法(例如UCP)没有区分应用线程数目的不同.文中设计了一种面向多线程多道程序的加权共享Cache划分框架(Weighted Cache Partitioning,WCP),包括面向应用的失效率监控器和加权Cache划分算法.失效率监控器以进程为单位动态监控在不同的Cache容量下应用的失效率;而加权Cache划分算法扩展了传统的失效率最优的Cache划分算法,根据应用线程数目的不同在进行Cache划分时给应用赋予不同的权值,以使具有更多线程的应用获得更多的共享Cache,从而提高系统的整体性能.实验结果表明:加权Cache划分算法虽然失效率有所增高,但却改进了IPC吞吐率、加权加速比和公平性.在由科学和工程计算应用组成的多道程序测试用例中,WCP-1的IPC吞吐率比以失效率最低为目标函数的共享Cache划分算法最高高出10.8%,平均高出5.5%.     

面向DSWP并行的OpenMP任务调度机制的扩展与实现

多核处理器能够提升多线程程序的性能,但早已存在的诸多单线程程序无法从中获益,程序员也习惯于编写单线程程序.自动并行化技术是将单线程程序移植到多核上的重要手段,但是当循环中存在无法确定的数据依赖或复杂的控制流时,传统的自动并行化技术无法取得良好效果.Ottoni等人针对传统自动并行失败的循环提出了Decoupled Software Pipelining(DSWP)算法用以实现指令级的细粒度并行,但其需要对处理器体系结构的深入了解以及对核间通信队列和专用指令的硬件支持,并行性能和应用广泛性受到限制.基于OpenMP应用编程接口实现的DSWP并行不依赖于硬件上对核间通信队列和专用指令的支持,且不受平台的限制,但现有的OpenMP任务调度机制无法满足DSWP并行中对任务调度的需求.对现有的OpenMP任务调度机制进行扩展,增加了任务与线程绑定的属性,保证了基于OpenMP的DSWP并行程序的正确执行.在GCC的OpenMP运行库libgomp中扩展了任务绑定属性子句的功能,扩展后的GCC作为OpenMP DSWP程序的基础编译器,为自动并行提供支持.通过对基准测试集NPB3.3.1的测试表明,传统自动并行失败的循环,经OpenMP DSWP自动并行后在双核处理器上平均加速比达到1.23以上;使用添加了OpenMP DSWP算法的Open64编译器生成的并行程序,与仅使用传统自动并行方法的Intel 编译器和Open64编译器所得程序相比,平均加速比分别高出22％和26％.     

常用函数调用频度的统计与分析

本文给出了数学库中各标准子程序的调用频度及统计方法；讨论了函数计算对整机性能的影响。研究结果表明：加速常用函数计算，可显著提高超级计算机的实用性能。Ｒ、ＳＱＲＴ、ＳＩＮ／ＣＯＳ计算的２￣ｘ，Ｉｏｇ２￣ｘ、Ｓｉｇｎ（ｘ＿ｌ，ｘ＿２）某函数计算的辅助性指令，直接用硬件实现；设置固定函数库装入最常用函数标子，可显著提高整机的综合计算速度，在参考文献［３］中的模拟分析也验证了这一结论。