面向STM的松弛存储一致性算法

软件事务性内存(STM)提供同步手段,让多线程程序高效并发执行。如果两个事务访问了同一个共享数据且至少一个事务进行了修改操作,则称发生了冲突。检测冲突后,一般选择一个事务终止。当前的STM实现都基于严格的线性一致性(Linearizability)语义模型,实现简单。但是,基于该语义会导致很多本来可以完成提交的事务失败,降低了系统效率。把因果一致性模型应用于STM,可以在保证程序准确性条件下取得较好的实际性能。实验数据表明,该算法简单高效,明显减少了冲突数目。     

集群上软件事务内存的层次化冲突检测

大多数事务内存研究都在多核处理器上进行,只有少数研究针对集群计算环境。现有的集群事务内存性能较差,因为事务内存的运行需要进行大量的远程内存访问,而集群的内存分布性使得远程内存访问的性能较差。事务内存运行中的冲突检测是进行远程内存访问最多的操作。我们提出了一种层次化的冲突检测方法,将其分为两个步骤进行,这种层次化的策略可以使集群上的软件事务内存获得高性能。     

基于弱隔离性的事务内存冲突分析

事务内存是一种扩展性好、易于编程的并行编程模型,其核心技术在于事务冲突的检测和处理.已有研究工作主要关注于冲突检测机制,但缺少对如何减少事务冲突的深入研究.分析表明,冲突概率的增长会严重降低事务内存系统的性能,并且随着处理器核数目的增长,这一问题会变得更加严重.研究发现,事务系统中弱隔离性模型的使用可以系统性地减少事务执行中的冲突,从而提升程序执行效率.基于该研究,提出了弱隔离性冲突检测方法(weak isolation conflict detection,WICD),并在SESC事件驱动模拟器上对WICD进行实现和评估,结果表明,与传统的严格隔离性模型相比,弱隔离性模型下最高可以减少35.7%的事务冲突,提升系统性能最大为31.0%.基于WICD的方法,通过对部分冲突进行立即检测,进而提出了一种改进的弱隔离性冲突检测方法(enhanced WICD,EWICD).实验表明,EWICD对于事务冲突的减少比率和WICD近似,最高达到33.8%,对系统性能的提升优于WICD,最大达到36.8%.     

新型内存硬件环境中的事务管理系统综述

大数据爆发的时代产生了各种新的业务类型,业务数据驱动着事务管理系统创新性的迭代发展.由于传统持久化介质的制约,传统的事务管理系统无法高效执行事务.并且,解决事务冲突的额外开销仍然会限制事务管理系统的吞吐.新型硬件的商业化应用为事务管理系统注入了更多的可能性,在学术界和工业界均得到了广泛关注.硬件事务内存可以为事务管理系统提供硬件级别的事务冲突检测.而且,相对于固态硬盘,非易失性内存的字节寻址和持久化特性可以显著降低事务延迟并提升事务管理系统的性能.但是,现有的事务管理系统技术无法充分地利用硬件本身带来的性能提升,因此需要重构事务架构来解决这个问题.首先对新型硬件环境下的事务管理系统进行总结分析;之后总结了当前基于新型硬件事务管理系统的技术路线,明确了硬件事务内存和非易失性存储硬件下的事务管理系统的优势和不足;最后指明了新型硬件环境中事务管理系统未来可能的发展方向以及新的挑战.     

基于页着色的多核处理器共享Cache动态分区

随着多核/众核成为处理器结构发展的主流,并行任务间共享地使用Cache而导致的冲突越来越成为性能提升的瓶颈.利用页着色可以实现对Cache的分区管理,减少共享Cache导致的冲突.页着色的原理是利用内存与Cache之间的组相联映射关系,通过控制分配固定区域的内存而达到分配固定区域Cache的目的,这一方面限制了任务能够请求的物理内存范围,另一方面调整程序使用的Cache空间需要做大量的内存拷贝,带来了不可忽视的开销.为了克服页着色的缺点,文中通过动态内存分配的方式,只对动态分配的页进行着色,在不修改内核和程序源码的前提下实现了动态Cache分区.文中提出的动态内存分配策略(CachePM)会根据运行时环境为任务分配内存,避免不同任务间共享Cache的冲突和同一任务内出现Cache的访问热点,通过合理划分程序运行时动态分配的内存达到Cache分区的目的.当任务的运行环境改变时,CachePM自适应地改变已经分配的堆中数据在物理内存中的布局,以实现Cache分区的动态调节.为进一步降低动态页着色的开销,作者采用了减少和延迟内存拷贝的策略.实验表明,该方法能够有效实现动态Cache分区,从而提高并行运行的任务的性能;同时由于动态内存分配策略避免了同一任务内出现Cache访问热点,单独运行的任务的性能也较在libc下运行有所提升.     

一种多粒度锁的事务并发控制算法

研究了一种基于多粒度锁的并发控制算法,包括其多粒度锁锁、锁表数据结构及锁操作的算法步骤。算法可以降低冲突发生的概率和事务的夭折数,减少事务重启,有利于满足事务截止期的要求,提高事务的并发度。在验证算法有效性时,通过测试类对内存数据库记录的插入速度、索引查找的速度、记录的删除速度三方面的性能进行了测试,结果表明,事务并发控制优化算法对内存数据库性能的提升是有效可行的。     

一种高效直方图生成算法在GPU上的实现

直方图生成算法(Histogram Generation)是一种顺序的非规则数据依赖的循环运算,已在许多领域被广泛应用。但是,由于非规则的内存访问,使得多线程对共享内存访问会产生很多存储体冲突(Bank Conflict),从而阻碍并行效率。如何在并行处理器平台,特别是当前最先进的图像处理单元(Graphic Processing Unit,GPU)实现高效的直方图生成算法是很有研究价值的。为了减少直方图生成过程中的存储体冲突,通过内存填充技术,将多线程的共享内存访问均匀地分散到各个存储体,可以大幅减少直方图生成算法在GPU上的内存访问延时。同时,通过提出有效可靠的近似最优配置搜索模型,可以指导用户配置GPU执行参数,以获得更高的性能。经实验验证,在实际应用中,改良后的算法比原有算法性能提高了42%～88%。     

事务存储系统中PGHB冲突检测算法研究

事务存储系统是一种全新的多核体系结构,为并行编程提供了一个简洁高效的编程环境。基于Signature的冲突检测算法是事务存储系统中很有前景的一种冲突检测方法,其误判率直接影响系统性能。GHB算法是一种优秀的冲突检测算法,具有较低的误判率,但硬件实现开销较大。本文对GHB冲突检测算法进行进一步改进,提出了一种PGHB算法。与GHB算法相比,PGHB算法在硬件开销和误判率两者之间取得了更好的折衷。     

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

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

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

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

Non-preemptive and SRP-based fully-preemptive scheduling of real-time Software Transactional Memory

Recent embedded processor architectures containing multiple heterogeneous cores and non-coherent caches renewed attention to the use of Software Transactional Memory (STM) as a building block for developing parallel applications. STM promises to ease concurrent and parallel software development, but relies on the possibility of abort conflicting transactions to maintain data consistency, which in turns affects the execution time of tasks carrying transactions. Because of this fact the timing behaviour of the task set may not be predictable, thus it is crucial to limit the execution time overheads resulting from aborts. In this paper we formalise a FIFO-based algorithm to order the sequence of commits of concurrent transactions. Then, we propose and evaluate two non-preemptive and one SRP-based fully-preemptive scheduling strategies, in order to avoid transaction starvation.     

Boosting performance of transactional memory through O-GEHL predictors

Time-based Software Transactional Memory (STM) exploits a global clock to validate transactional data and guarantee consistency of transactions. While this method is simple to implement it results in contentions over the clock if transactions commit simultaneously. The alternative method is thread local clock (TLC) which exploits local variables to maintain consistency of transactions. However, TLC may increase false aborts and degrade performance of STMs. In this paper, we analyze global clock and TLC in the context of STM systems, highlighting both the implementation trade-offs and the performance implications of the two techniques. We demonstrate that neither global clock nor TLC is optimum across applications. To counter this challenge, we introduce two optimization techniques: The first optimization technique is Adaptive Clock (AC) which dynamically selects one of the two validation techniques based on probability of conflicts. AC is a speculative approach and relies on software O-GEHL predictors to speculate future conflicts. The second optimization technique is AC+ which reduces timing overhead of O-GEHL predictors by implementing the predictors in hardware. In addition, we exploit information theory to eliminate unnecessary computational resources and reduce storage requirements of the O-GEHL predictors. Our evaluation with TL2 and Stamp benchmark suite reveals that AC is effective and improves execution time of transactional applications up to 65%.     

基于ARM的双界面IC卡读写器的设计与实现

为满足智能卡在银行、保险、医疗等管理系统的应用需求,设计了一款基于ARM的支持双界面智能卡的读写系统。采用具有ARM Cortex M3内核的STM32F103RBT6和近场通信收发器STRFNFCA等芯片进行相关的硬件设计。软件设计完成了对非接触式卡和接触式卡的底层驱动及应用层通信模块、LCD显示等操作;根据PBOC 2.0标准对智能卡进行金融交易包括圈存、消费、查余额等;同时,读卡器集成了Crypto 1加密算法来兼容市场上的Mifare系列卡。测试结果表明,读写系统性能稳定、功耗低、实用性强、可靠性高。     

移动计算环境中实时嵌套事务并发控制协议的研究

提出了移动计算环境中多版本乐观并发控制协议(MultiversionOptimisticConcurrencyControl,MVOCC)处理移动实时嵌套事务.协议消除了只读事务和更新事务之间冲突,通过动态调整事务串行次序,避免不必要的事务重启动.只读事务在移动主机处理,只读事务的响应时间大大改善.事务有效性检查分两级局部有效性检查和全局有效性检查.局部有效性检查在移动主机进行.通过局部有效性检查的事务提交到服务器进行全局有效性检查.如此早地检测数据冲突,节省了处理和通信资源.通过模拟仿真,对协议进行了性能测试,并与OCC-TI-WAIT50和HP2PL协议进行了比较.实验结果表明该协议要优于其它协议.协议不但能有效地降低事务的重启动率和延误截止时间率,而且改善只读事物的响应时间.     

Detecting intrusion transactions in databases using data item dependencies and anomaly analysis

Abstract: The purpose of the intrusion detection system (IDS) database is to detect transactions that access data without permission. This paper proposes a novel approach to identifying malicious transactions. The approach concentrates on two aspects of database transactions: (1) dependencies among data items and (2) variations of each individual data item which can be considered as time‐series data. The advantages are threefold. First, dependency rules among data items are extended to detect transactions that read or write data without permission. Second, a novel behaviour similarity criterion is introduced to reduce the false positive rate of the detection. Third, time‐series anomaly analysis is conducted to pinpoint intrusion transactions that update data items with unexpected pattern. As a result, the proposed approach is able to track normal transactions and detect malicious ones more effectively than existing approaches.     

基于状态转移矩阵的变化检测方法

土地利用变化检测一直是遥感影像变化检测研究的重点。在分析已有变化检测方法的基础上提出了一种基于状态转移矩阵（State Transition Matrix,STM）的变化检测方法。以像斑为分析单位,通过样本像斑的选择与更新对变化检测区域进行分析,利用辅助数据生成的地物变化状态转移矩阵对变化检测结果进行修正。实验证明了该方法的有效性。     

基于STM32的生猪生长参数自动检测系统

随着科学的发展与时代的进步,传统的农业已经向着智能化、自动化、信息化的方向发展。本文主要说明设计制造一个基于STM32单片机的生猪生长参数自动检测系统。TFT LCD触摸液晶屏显示与发出指令,射频模块识别每一头生猪,HC-SR04超声波测量生猪的高度,MLX90614红外测温模块测量生猪的体温,HX711重量传感器测量体重并且STM32采集AD数据返回体重值。通过这一系列的模块测量以及STM32对其数据采集,最后可完成这套自动检测系统的设计,实现生猪检测自动化、智能化。     

基于依赖图的硬件事务存储技术研究

事务存储技术能够简化并行程序中对共享资源的访问控制,是当前的研究热点之一.目前,多数基于硬件的事务存储系统采用基于冲突检测与处理的并发控制协议,当检测到两事务发生冲突时就中止二者之一.但是对事务间"冲突"更深入的分析表明,某些"冲突"并不一定会导致事务的回退,这种冲突称为"弱冲突".基于依赖图的硬件事务存储技术能够避免弱冲突引发的多余事务回退.模拟实验表明,基于依赖图的事务存储系统与基于冲突处理的事务存储系统相比具有明显的性能优势.     

基于交易不可信度的比特币非法交易检测

比特币非法交易检测根据交易特征构建检测模型鉴别非法交易,在反金融犯罪领域得到广泛应用。现有的比特币非法交易检测方法假定交易的属性包含交易是否非法的信息,并从交易属性中挖掘能够代表交易非法性的特征,难以准确判断非法交易,导致检测精度和召回率降低。设计基于交易不可信度的比特币非法交易检测方法。根据非法交易之间具有关联的特性,定义交易不可信度。通过构建交易不可信度度量模型,将量化结果作为直接反映交易非法性的特征融入到已有的分类模型中,提高模型的检测性能。在此基础上,采用迭代训练集的方式扩增非法交易样本,解决非法交易样本不足以及标注困难的问题。在Elliptic数据集上的实验结果表明,与本地特征和聚合特征相比,加入不可信度特征的逻辑回归、随机森林、多层感知机和图卷积网络分类模型的F1值平均提高8.5%。