一种采用Lock-Free同步机制的数据结构的研究

随着多核芯片在嵌入式实时系统中的广泛应用,采用传统锁机制对共享数据的访问会引起死锁、优先级翻转以及CPU饥饿现象,进而会影响系统整体性能的发挥,严重时还会导致不可估量的损失发生.为此,针对Skiplist的共享数据结构提出了一种Lock-Free的同步机制方法,对该方法的线性一致性进行了证明,并将其应用于混合关键任务的共享优先级调度队列中.经过实验,该方法在吞吐量、核利用率以及平均响应时间方面优于传统的基于锁机制的方法,有效地提升了多核运行的效率.

一种基于无锁队列的运行时多线程并行验证方法

运行时验证是一种动态的软件验证技术,主要包括使用形式化规约描述待验证性质、自动生成对应监控器以及监控器的插桩.然而现有的面向C语言程序的运行时验证技术存在一些局限性,主要体现在多监控器的情况下,现有的运行时验证工具只能使用串行的方式处理,这大大降低了验证效率.因此,本文在分析了形式化规约的基础上,提出了一种基于无锁队列的运行时多线程并行验证方法.方法在现有工具MOVEC上实现并在测试集mibench上插桩运行,并与相关工具ACC、AC++和串行机制下的MOVEC进行了对比实验.实验结果表明,本文所实现的基于无锁队列的运行时多线程并行算法可以在有多个监控器的情况下有效地对C语言程序进行并行的运行时验证,且并行验证算法的性能比串行验证算法提升了约83%.

水电站进水口闸门未正常闭门分析及处理

针对水电站进水口事故闸门动水落门时未在要求时间内正常闭门的问题,通过对比分析不同工况下落门过程曲线,结合现场观察,推断是在电站出现故障引起闸门动水落门过程中,由于闸门、油缸启闭机振动相对较大,液压启闭机有杆腔高压球阀自由转动而关闭所导致。为此加设了液压启闭机有杆腔高压球阀锁定装置,确保球阀不会自由转动;并建议高压球阀应选择全开位置带有锁定装置的型号;优化油管的空间结构和管道支撑结构布置,减小管道振动;对大尺寸的混流式水轮发电机组应进行过渡过程工况的动水落门试验。

船用楔形齿桨轴离合器设计与仿真分析

针对船用楔形齿桨轴离合器的参数设计问题,开展了船用楔形齿桨轴离合器设计研究。理论分析了船用楔形齿桨轴离合器自锁所需的临界摩擦因数随楔形齿压力角和楔形角变化的规律,并进行了仿真验证;建立了船用楔形齿桨轴离合器的多体动力学模型,研究了存在对齿误差时的接合过程。结果表明,船用楔形齿桨轴离合器降低了对齿过程的精度需求,在接合对齿过程存在0.4°以内的误差时可以在自身导向作用下完成接合。推导的自锁临界摩擦因数公式可以用来指导船用楔形齿桨轴离合器设计。

磁控管自由振荡带宽对其注入锁定带宽的影响研究

自由振荡磁控管的输出信号通常具有一定的带宽,而非理想的单频信号;文章研究了磁控管自由振荡输出带宽对其注入锁定的影响。从统计上认为自由振荡磁控管的输出频率服从正态分布,结合注入锁定理论,计算了磁控管在不同注入频率下的输出频谱。理论分析表明:当考虑自由振荡磁控管输出频谱具有一定带宽时,峰值频率牵引带宽将大于理想单频假设下的锁定带宽;随着自由振荡带宽的增加,峰值频率牵引带宽增加,锁定带宽减小。磁控管注入锁定实验结果表明:自由振荡带宽(3 dB)分别为0.375、1.049 MHz时,其锁定带宽分别为8.4、7.9 MHz,峰值频率牵引带宽分别为10.2、13.9 MHz,验证了理论的正确性。本研究发展了磁控管注入锁定理论。

一种正交分解大数据处理系统设计方法及实现

MapReduce等计算框架的出现开启了大数据处理新纪元,以Hadoop,Spark为代表的大数据处理系统具有大吞吐率、跨平台、高可扩展的优势,并得到广泛应用.然而,为避免与具体的操作系统、硬件平台绑定,这些系统的设计与优化集中在计算模型、调度算法等方面,无法充分利用底层平台的优势.提出了一种基于正交分解的大数据处理系统设计与优化方法,将系统分解为松耦合的多个功能正交的模块,使存储、处理功能分离出来,交给能够利用底层平台操作系统甚至硬件资源的存储、执行引擎,原大数据系统退化为调度平台;进而,提出基于锁无关机制的存储底层优化策略和基于指令超级优化的执行引擎底层优化策略.以此为指导,以Hadoop作为兼容和改进的对象,实现了原型大数据处理系统Arion.Arion既能保持Hadoop的跨平台、高可扩展的优势,又能消除任务执行的瓶颈,其本地化的设计与优化手段对非Hadoop平台同样有效.通过在原型系统上的实验证明,Arion能够提升大数据处理任务的执行效率,最高达7.7%.

BDSim:面向大数据应用的组件化高可配并行模拟框架

大规模并行模拟是研究大数据体系结构的重要方法,对大数据应用及众核体系结构的发展有着不可替代的推动作用.然而,目前的模拟技术不能满足大数据体系结构研究的需求,主要体现在模拟速度慢、配置过程复杂以及可扩展性差等方面.为了解决此问题,评估面向大数据应用的高通量众核体系结构的性能与功耗,该文提出了面向大数据应用的并行模拟框架——BDSim.该框架基于组件化思想,将功能组件与框架服务单元组成并行功能单元,并可根据负载情况,自由配置组件与框架服务单元之间的映射关系.为了提高组件之间的通信和同步效率,该文提出了一种非阻塞无锁通信优化方法,和一种CMB保守同步算法的优化算法——NMTRT-CMB同步算法.模拟不同并发规模的基于2D-Mesh网络的众核系统的实验结果表明,与基于锁的并行通信方法相比,框架采用的非阻塞无锁通信优化方法可以提高并行模拟速度约10%,该算法与CMB同步算法相比,NMTRT-CMB同步算法可以减少空消息数量达90%以上.

一种基于超步执行的并行模拟平台研究与实现

计算机系统的并行化趋势使得传统的串行模拟器正面临严峻的挑战,一方面由于执行速度和内存的限制无法模拟目标大规模并行系统;另一方面,无法充分利用已有并行系统的资源。因此,串行模拟器已经成为宿主机和目标系统之间的瓶颈。Hypersim是基于SMP集群平台的新型并行模拟器,运行于其上的主从式操作系统原型hyperOS为应用程序提供了运行环境,实验表明,该模拟平台可以正确地模拟一种新型的HPP高性能计算机体系结构。为了高效并行,hypersim中采用细粒度负载分配及高效的同步和通信机制,提出并采用超步执行技术来加速模拟器执行,结果显示hypersim在多进程情况下有一定的加速,在单进程多线程情况下有较好的加速比。

一种多核环境中无锁的多进程负载均衡会话保持方案

负载均衡是云计算的基本问题之一,多核环境中多进程负载均衡会话保持问题得到广泛关注并发展成为研究热点。针对该问题,面向Linux内核,基于Hash化管理内核网络数据包传递的思想,该文提出并实现了一种无锁的多进程负载均衡会话保持方案。该方案避免了锁的使用,而且不需要对原有单进程负载均衡程序进行结构上的修改,能够快速地将现有单进程负载均衡程序转变为多进程架构。理论分析和实验表明,相较于传统的共享内存式锁机制会话保持解决方案,该方案性能更好、适用性更强,提高了多核环境中负载均衡系统的效率。

并行计算机系统中的计数算法研究

计数算法是计算机程序设计中的基础算法。然而,传统计数算法在新兴的多核并行计算机系统中存在计数效率低下以及计数不准确的问题。文中首先对这些问题进行深入量化分析,之后提出了一种适用于并行计算机系统的确定性高速计数算法。该算法采用对计数器数据先进行快照再进行统计计数的方法,有效避免了计数算法中读者线程与写者线程之间的相互干扰,保证了计数数据的准确性;同时,通过采用无锁链表队列存储计数数据快照,实现了并发读取情况下的无阻塞计数统计,保证了计数算法的效率。实验论证和性能分析结果表明:在新一代的多核并行计算机中,本计数算法计数效率高且计数准确,综合性能优于现有算法。

基于无锁数据结构的FIFO队列算法

现代商用多核处理器缺少硬件支持的处理核间通信机制,多个处理核间必须通过加锁保护的共享内存传递数据。为此,设计一种基于软件的无锁队列作为核间通信机制,通过无锁数据结构提高软件队列的性能。当数据到达速率较低时,队列自适应地减小队列长度,从而占用较小的内存空间,进而更好地利用处理器高速缓存;当数据到达速率较高时,队列自适应地增加队列长度,以避免数据丢失。实验结果表明,在数据到达速率变化较大的实际应用场景中,该队列较FastForward、MCRingBuffer和B-Queue队列具有更高的数据处理性能。

GBLHT:一种GPU加速的批量插入线性哈希表

为改善线性哈希表这一有效索引结构的插入性能,在分析现有方法的基础上,结合CUDA并行编程模型,设计并实现了一种基于GPU的批量插入线性哈希表GBLHT;借助原子函数atomicAdd,GBLHT可以充分利用GPU强大的并行吞吐量来实现大规模记录的无锁批量插入;通过实验对比传统串行插入方法、CPU批量插入方法以及GBLHT的插入性能,发现在不同参数设置条件下,GBLHT的插入性能比传统串行方式提升了7～14倍,与4线程的CPU批量插入方法相比则提升了3～6倍.

基于硬件CAS原语的高效多字无锁同步算法

共享内存体系结构下,为解决锁同步导致的并发性能瓶颈,本文提出了一种基于硬件CAS(比较交换)原语的无锁同步算法.该算法利用底层处理器提供的比较交换指令,实现了在多核多线程环境下对共享变量的非阻塞同步操作,通过采用全局标记值的方式,避免了传统设计中由于使用内存字标记导致的性能开销,同时确保数据在并发访问中的一致性.实验结果表明,本文算法可以高效地支持任意多字的CAS同步,提高了对共享数据的并发访问性能,具有较好的可扩展性.

长北区块无土相防水锁低伤害钻井液技术

针对长北区块生产井持续生产致使地层压力衰减、压差增大,导致钻井液对储层伤害加剧的问题,在分析长北区块储层伤害机理的基础上,研制了解水锁剂G311,优选了润滑剂G316,并对其加量进行了优化,形成了适用于长北区块压力衰减储层的无土相防水锁低伤害钻井液。该钻井液与无土相低伤害钻井液相比,钻井液滤液表面张力降低率达77.8%,线性膨胀率达22.6%,岩心伤害率低于15.0%,具有解除水锁、抑制水敏及储层保护效果显著等优点。无土相防水锁低伤害钻井液在长北区块2口气井进行了现场试验,钻井过程中没有发生井下故障,起下钻顺畅,井眼始终处于良好净化状态。其中,CX-5井平均机械钻速提高12.1%,裸眼完井并直接气举投产,产气量达70×10^4m^3/d,高于预期产气量。研究结果表明,无土相防水锁低伤害钻井液能够满足长北区块压力衰减地层长水平段水平井钻井安全及储层保护要求。

快速时代回收:一种针对无锁编程的快速垃圾回收算法

在多核、众核时代,并行编程模型如软件事务内存、无锁编程等成为研究热点.无锁编程技术使得多个线程无需加锁即可并发访问同一个数据结构成为可能,该技术已被证明能够有效地提升程序的性能.实现无锁算法的一个关键的技术是垃圾回收.时代回收算法是一种高效、易用的垃圾回收算法,但其回收速度受制于最慢的线程,在极端情况下该算法完全停滞,难以在实际情况下使用.本文针对时代回收算法的不足,在其基础上提出了快速时代回收算法,新算法的回收速度与最快线程保持一致,在测试中回收成功率为100%,实验证明快速时代回收算法一种适用于无锁编程的快速实用的垃圾回收算法.

非阻塞同步在嵌入式操作系统中的实现

提出了把非阻塞同步机制应用于嵌入式操作系统的新设想,同时通过修改嵌入式操作系统内核源码的方法对其进行了实现。针对内核中共享资源的不同特点,综合使用了锁自由和等待自由两种不同性质的非阻塞同步策略,同时改进了锁自由的同步算法,并对原有的等待自由同步算法进行简化,使新内核具有较小的同步开销和较好的实时性能。

网络数据包高性能并行处理技术研究

针对当前多核处理器在对高速网络数据包处理时性能低,不能完全发挥多核优势的问题,分析对高速网络数据包处理的瓶颈所在,提出一种网络数据包并行处理模型。该模型利用多队列网卡,结合并行网络协议栈、多核多线程及无锁编程技术在网络数据包的整个收发路径上进行完全并行化处理。实验结果表明,该模型方法能够充分发挥多核处理器优势,大幅提升网络数据包处理效率。

基于Transpose规则的无锁自组织链表算法

自组织链表可以依据访问序列动态调整链表结构,提高链表性能。在分析并研究现有自组织链表算法的基础上,结合Transpose规则,提出无锁自组织链表算法。线程可标记被访问的结点并尝试与标记结点前驱相交换,也可直接物理删除已被标记的结点,同时其他线程发现该标记结点时会辅助该线程完成相应操作,从而保证链表的非阻塞特性。实验结果表明,该算法性能与Harris-Michael链表算法相当,并且其无锁实现方式比粗粒度锁算法更具优势。

改进型锁无关双端队列的设计与实现

高性能实时系统对系统性能、确定性和容错性有着更高的要求。非阻塞同步在任务同步方面满足要求,实现方法之一就是设计锁无关数据结构。介绍了设计锁无关数据结构算法的关键技术,通过对已有算法不足的分析提出了一种改进型的锁无关双端队列算法,介绍了对该算法的实验分析和实际应用。实验结果表明,该算法提高了访问双端队列的执行速度,并避免了多任务间同步引发的死锁、优先级逆转、低容错性等缺点。

线弹性问题的locking-free双参数元(英文)

文中运用双参数法提出了一个4参数的四边形非协调有限元,讨论了该单元对纯位移边界条件下的均匀介质线弹性方程的逼近问题.证明了在材料几乎不可压时单元对弹性问题的一致最优收敛性,数值试验验证了理论分析结果.并通过构造后处理算子,得到了超收敛结果.所有的分析结果都可以推广到三维情形.