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

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

基于全局同步逻辑时间的访存依赖约减方法

并发执行的并行多线程程序执行过程中,不同的访存顺序会得到不同的执行结果.由于再次执行时,难以重现首次执行时的错误,导致并行程序的调试非常困难.确定性重放是解决该问题的一种方法,目的是通过记录并行程序执行过程中的不确定性事件,然后利用记录的事件重现出程序的原始执行.然而,已有的确定性重放方法会产生大量的记录日志,如何减小记录日志是确定性重放领域的研究热点,在实际应用中也是非常具有挑战性的问题.为了减小记录日志的开销,文中提出了一种基于逻辑时间的访存依赖约减方法,并在支持松弛存储一致性模型的处理器上提出具体的实现技术,该方法利用了访存依赖对应的逻辑时间之间的序关系进行约减.通过模拟评估所提出方法的性能和可扩展性.其中,在8核模拟平台上,通过Splash2测试程序进行评估,结果显示所提出的记录方法平均日志开销为0.11Bytes/Kilo-Instruction,与目前最好的访存依赖约减方法Timetraveler相比提高了75%;通过4核、8核和16核平台的评估结果,表明所提出约减方法具有较好的可扩展性.     

多核处理器并行程序的确定性重放研究

多核处理器并行程序的确定性重放是实现并行程序调试的有效手段,对并行编程有重要意义。但由于多核架构下存在共享访存不同步问题,并行程序确定性重放的研究依然面临多方面的挑战,给并行程序的调试带来很大困难,严重影响了多核架构下并行程序的普及和发展。分析了多核处理器造成并行程序确定性重放难以实现的关键因素,总结了确定性重放的评价指标,综述了近年来学术界对并行程序确定性重放的研究。根据总结的评价指标,从纯软件方式和硬件支持方式对目前的确定性重放方法进行了分析与对比,并在此基础上对多核架构下并行程序的确定性重放未来的研究趋势和应用前景进行了展望。     

计算机访存冲突的对策与实现

计算机系统中，多个内存用户访存之间，内存用户访存与内存刷新之间相互冲突是一个很重要的技术问题。本文以Ｃｌａｓｓｉｃ－７８３５计算机为例，论述了计算机访存冲突的产生机理，阐明了解决此问题的技术途径，并对该机内存扩容中出现的问题提出了具体解决方法。     

基于逐步细化快照序列的多核并行程序调试

多核并行程序的调试是一个公认的困难问题,困难主要来自于程序执行的不确定性.可重现调试(replay debug)提供了消除程序中不确定性的能力,但是现有的可重现调试解决方案都无法应用于商用的软硬件平台中,且进行调试所带来的性能损失会随着并发度的增加而超线性地增长.提出了一种基于运行快照的新型并行程序调试方法SDT(snapshot debug tool).该方法以离线的断点设置、运行快照捕捉和运行快照细化为基础,提出了一套可以指导用户由粗到细发现错误的调试过程,并在通用的软硬件平台上进行了实现.实验结果显示,在8线程的并发条件下,使用SDT调试所带来的时间性能损耗平均为5188%;同时当线程数增长4倍时,使用SDT所带来的额外时间消耗最多增长1倍,具有很好的可扩展性.记录快照的数据量是影响SDT性能的重要挑战,实验证明通过使用增量式的快照记录方式可以有效地降低需要记录的数据量,减少记录快照花费的时间,提高SDT的整体性能.     

面向实时流处理的多核多线程处理器访存队列

针对多核多线程处理器中乱序访存影响计算实时性的问题,在对典型访存队列进行研究的基础上提出了一种新的访存队列构建模型及其硬件结构.该模型采用窗口优化算法控制最差情况下的访存延迟,保证访存的实时性,同时又利用优化的乱序调度策略减少访存延迟.实验证明,该访存队列可控制最大访存延迟,与顺序访存相比,存储器具备更高的带宽,与传统的乱序访存相比较,可以充分满足计算的实时性需求,而存储器有效带宽基本不受影响,解决了多核多线程处理器承担实时流计算的基础难题.     

多核系统共享内存资源分配和管理研究

对于共享内存资源的多核系统来说,分配和管理有限的内存资源是一个非常重要且具有挑战性的问题.随着处理器核数的快速增长,不同线程间的访存请求对系统中共享内存的竞争也愈发激烈,由此导致的对系统性能和系统公平性的影响也更加显著.为了缓解这一问题,除了增加可用共享资源外,公平高效地管理和利用共享内存资源至关重要.在各类共享资源中,对系统性能影响最大的是共享Cache和DRAM.文中将这两级共享内存资源的分配和管理研究归结为三个重要方面,包括共享缓存分区、访存请求调度以及地址映射优化,并从优化系统吞吐率和公平性方面分析总结了一系列共享缓存分区策略,从缓解多线程对DRAM的竞争和相互干扰方面分析概括了一系列访存调度算法和地址映射策略.最后对共享内存资源未来的研究和发展做了总结和展望.     

基于SPM的多核SoC访存结构设计与优化

针对“一个RISC主处理器核＋几个专用协处理器核”结构的计算密集型SoC,设计一种以执行命令方式完成大块数据传输的高效访存结构。通过增加组传输和流水传输模式,对该结构进行优化。实验结果表明,该访存结构设计及优化方案的数据传输效率高、实现开销小,并且对同类SoC系统,该设计具有良好的适用性。     

基于指令流访存模式预测的缓存替换策略

传统的缓存替换策略主要基于经验主义,近年来研究者们使用预测技术推测访存行为,提高缓存替换的准确性,预测技术的应用是当前缓存替换策略研究的热点.由于访存行为自身的复杂性,直接在缓存系统中预测访存行为是困难的,要面对很大的不确定性.当前已有的研究为了解决该问题,使用越来越复杂的预测算法来分析访存行为之间的关联.然而这种方式并未真正减小不确定性,同时现有的缓存替换策略很难避免乱序执行和缓存预取对访存行为分析过程的干扰.为了解决以上问题,提出了一种新的预测缓存访问序列的方法IFAPP(instruction flow access pattern prediction),根据分支预测技术推测程序指令流,定位指令流中的访存指令,进而对其中访存指令的行为逐一进行预测.通过访存序列计算每个替换候选项的重用距离,将重用距离最远的候选项踢出.该方法可以避免乱序执行和缓存预取的干扰,预测对象是行为简单的独立访存指令,减少预测过程中所面对的不确定性.实验结果表明,该算法在一级数据缓存上比LRU算法平均减少3.2%的缓存缺失.相比经典的基于缓存预测的BRRIP和BIP算法,该算法在一级数据缓存上分别减少12.3%和14.4%的缓存缺失.     

面向监听一致性协议的并发内存竞争记录算法

内存竞争记录是解决多核程序执行不确定性的关键技术,然而现有点到点的内存竞争记录机制带来的硬件开销大,难以应用到实际的片上多核处理器系统中.以降低点到点内存竞争记录方式的硬件开销为出发点,为采用监听一致性协议的片上多核处理器(chip multiprocessor, CMP)系统设计了基于并发记录策略的点到点内存竞争记录算法.该记录算法将两两线程间点到点的内存竞争关系扩展到所有线程,采用分布式记录方法为每个线程记录一个由内存竞争关系的一方构成的内存竞争日志;重演时采用简化的生产者消费者模型,确保了确定性重演的实现,有效降低了硬件消耗和带宽开销.在8核处理器系统中的仿真结果表明,该并发式点到点内存竞争记录算法为每个处理器核添加硬件资源约171B,每千条内存操作指令记录日志大小约2.3B,记录和重演阶段均添加不到1.5%的带宽开销.     

基于硬件签名的循环式内存竞争记录算法

多核程序的执行存在不确定性,内存竞争记录是实现多核程序确定性重演的关键技术.针对现有内存竞争记录机制记录日志较大、重演速度受限等问题,提出了一种新型的循环式点到点内存竞争记录算法.该算法用当前发生序表示内存冲突,用硬件签名实现冲突检测,无需修改原有的cache结构;引入冲突方向检测机制,约减连续同向的当前发生序,记录循环发生序到内存竞争日志.该算法中,内存竞争日志中所记录的任意两线程间的内存竞争呈循环状,大大减少了冗余,并用增量计数器优化循环发生序,更大程度上减小了内存竞争日志.仿真结果表明该算法能够在引入较少硬件资源的前提下有效地减小内存竞争日志.同时,内存竞争日志也具有较好的可扩展性.     

多核处理器机群Memory层次化并行计算模型研究

多核处理器机群点对点通信同时具有memory纵向层次化特征和横向层次化的新特征.纵向层次化特征揭示了对不同大小和步长的消息进行点对点通信时消息通信中间件对其性能的影响;横向层次化的新特征由intra-CMPi、nter-CMP和inter-node消息通信性能的显著差异引起,目前缺少有效的分析模型.文中提出一种新的memory层次化并行计算模型,对多核处理器机群memory横向、纵向层次化特征进行了统一的抽象.在对多核处理器机群点对点通信和集合通信的开销进行模型分析和实际测试中,新模型的精确性优于现有的未引入memory横向层次化特征的模型.     

面向多兴趣区域图像处理应用的高效无冲突并行访问存储模型

针对不规则数据访问模式图像处理应用提出了一种通用的高效无冲突并行访问存储模型.在主存储器与处理器之间构建了一种多体存储结构,并将大部分的不规则数据访问模式归类为对图像中多个局部矩形兴趣区域内的任意位置固定大小矩形数据块的无冲突并行访问.为了提高访问效率,只将兴趣区域内的数据缓存在多体存储器中,且不同兴趣区域的重叠数据可以重用.多体存储器的寻址机制是基于提出的地址映射表结构进行动态寻址,而不是采用传统的固定寻址函数,既保证了对任意数据读写操作的编址一致性,又提高了数据重用性.每处理一个新兴趣区域就对地址映射表内容进行一次更新,提出的双表结构与数据块动态调度机制保证了更新过程与计算过程的并行执行.基于提出的存储模型构建了硬件体系结构,并在FPGA上实现,测试结果表明,与直接访问主存储器相比在访存速度上提高了几倍到上百倍.     

面向神威高性能多核处理器的并行编译优化方法

在神威高性能多核服务器上,自动并行化编译系统为识别和申明程序中的并行性,产生的OpenMP程序没有经过充分的优化,其采用简单的fork-join模型,存在大量的并行循环嵌套,导致运行效率低。为提升自动并行化编译系统产生的OpenMP程序的运行效率,提出一种并行域重构优化技术。并行域重构技术通过合并程序中的并行域和扩展嵌套循环中的并行域范围,减少OpenMP程序的并行域数目,降低线程组频繁创建和合并等控制开销,将简单fork-join模型的OpenMP程序转换为性能更为高效的单程序多数据模型的OpenMP程序。实验结果表明,在新一代神威高性能多核服务器SW1621平台上,并行域重构技术在NPB3.3-OMP测试集和SPEC OMP2012测试集上的运行效率分别提高了10.77%和7.94%的,可有效提升自动并行化编译系统OpenMP程序的执行效率。     

X10并行程序中静态数据竞争检测

在多线程程序中,当2个以上线程在没有顺序约束的条件下访问同一个存储单元时,且其中至少有一个为写访问,则可能会发生数据竞争。为此,提出一种针对X10并行程序的静态数据竞争检测算法,包括源访存对计算、可达访存对计算、时钟同步访存对计算和逃逸访存对计算4个阶段。通过在WALA框架中分析构建程序的调用图,计算源访存对集合,检测出内存访存中可能发生数据竞争的无序对。实验结果表明,该算法可以在不显著增加X10并行程序总体运行时间的情况下,达到比较理想的数据竞争检测效果。     

Program Development Tools for Clusters of Shared Memory Multiprocessors

Applications are increasingly being executed on computational systems that have hierarchical parallelism. There are several programming paradigms which may be used to adapt a program for execution in such an environment. In this paper, we outline some of the challenges in porting codes to such systems, and describe a programming environment that we are creating to support the migration of sequential and MPI code to a cluster of shared memory parallel systems, where the target program may include MPI, OpenMP or both. As part of this effort, we are evaluating several experimental approaches to aiding in this complex application development task.