软件事务内存的动态竞争管理策略

软件事务内存是为了简化并行程序设计而出现的一种新的程序设计技术.为了降低软件事务内存系统中事务冲突的发生频率以提升系统整体性能,提出了一种新的基于动态控制和队列调度的竞争管理策略.定义了竞争强度的概念和系统总体框架,并在此基础上给出了利用运行时反馈信息动态调节竞争强度的方法.同时给出了事务序列化的设计方法与实现中应注意的问题,通过将冲突概率大的事务序列化以达到避免相同冲突再次发生的目的.结合常用的基准数据结构,对模型和算法进行了实验,最后结果表明了算法的正确性和有效性.     

STM多事务竞争冲突下竞争管理策略的研究

事务存储系统是一种高层次抽象并行编程模型,目的为方便开发并行程序。事务存储系统中的竞争管理模块用于解决事务之间的冲突。传统的事务竞争管理策略只负责仲裁两个冲突事务之间的冲突．提出将多个事务及事务冲突关联转换成一张无向图,基于全局事务冲突情景,利用图顶点着色技术求解无向图中最大独立集。最大独立集中事务相互不冲突,CM仲裁处理并发执行,实现系统并发最大化。     

事务存储中的一种自适应冲突检测算法

事务存储被认为是极具前景的多核处理器并行编程的手段,但存在开销过大的问题。采用Bloom Filter对事务间访问共享变量进行冲突检测,能够有效地降低开销,但其存在误判会导致不必要的事务作废,因此要尽可能减少。简要介绍了Bloom Filter和事务存储,提出了一种事务存储的自适应冲突检测算法ACDA,根据事务读写集合大小自适应地调整Bloom Filter的位串大小,在较低开销的情况下,保持误判率不增加。分析了软件事务存储中实现ACDA的特点,初步实现ACDA,与主流软件事务存储实现RSTM相比,在事务存储测试程序STAMP中,开销可接受的前提下,减少因误判而作废的事务最高达93%。给出了对ACDA哈希函数进一步优化的思路。     

采用向量时钟的软件事务存储算法

在多核处理器上,事务存储是一种有望取代锁的同步手段。软件事务存储不需要增加额外硬件支持,就可以充分利用当前商业多核处理器的多线程能力。提出一种软件事务存储实现算法VectorSTM,该算法不需要使用原子操作。VectorSTM采用分布的向量时钟来跟踪各线程事务执行情况,能够提供更高的并发度。对事务存储基准程序STAMP的测试表明,VectorSTM在性能或者语义上比软件事务存储算法TL2和RingSTM有优势。     

事务存储研究

为了研究多核处理器系统上的并行编程问题,开展了对事务存储模型的研究.阐述了事务存储,介绍了事务存储系统的实现方法,利用4种事务存储系统详细阐述了事务存储的实现;重点讨论了6种影响事务存储发展的关键技术,即实现方式、数据结构组织、并发控制,冲突检测、争用管理等;提出了事务存储将向着软硬件结合、提升性能、提高正确性和满足多核应用需求的方向发展.     

基于事务存储的事务级线程切换

针对目前TM系统将现有操作系统优化以提供良好的事务支持,研究基于LogTM系统的事务级线程切换,通过分析现有结构和修改操作系统的相关模块信息,为事务级线程切换提供支持,使事务化线程能够在操作系统调度下高效运行。     

面向多核的基于RSTM系统的冲突管理策略

程序并行化是充分发挥多核处理器性能的有效手段。现有编程模型受锁、管道等同步方式的约束,并行度很难提高。针对上述问题,提出一种面向多核的基于Rochester软件事务存储(RSTM)系统的冲突管理策略,在现有编程语言中提供接口,通过事务方式提高程序并行度,以优先级方式解决2个事务发生冲突时的裁决问题,减少不必要的一致性验证,减小系统开销。     

事务存储并行程序编程接口研究

事务存储并行程序编程接口按照实现方式和实现层次的不同,分为三种形式:库函数接口、语言扩展和编译器指导命令。本文以RSTM、英特尔C/C++软件事务存储编译器原型和OpenTM为例,讨论了三种事务存储编程接口的特点,对OpenTM编程接口进行了扩展和完善,并对未来编程接口的发展进行了展望。     

基于OpenMP的事务存储同步语义研究

多核处理器环境下必须解决多核处理器的并行编程问题,才能够充分发挥多核处理器的性能.事务存储(Transactional Memory)机制提供了一种在多核环境下程序并行执行和同步的方法.已有的工作已将事务存储扩展到了OpenMP,为程序员提供满足事务原子性、一致性和隔离性的共享存储访问.但当前事务存储的语义并不完善,事务间不能交换中间结果,不能实现锁的部分语义.提出并实现了一种基于开放嵌套的事务存储的同步语义,从而解决了事务间不能交换中间结果的问题,增强了扩展事务存储后OpenMP的并行编程能力.     

基于键值存储的事务控制策略

介绍基于键值存储的优点以及发展趋势,提出键值存储模型中支持事务的方法。新型的键值存储数据库应该具备传统数据库的事务能力,新型数据库实现事务控制,需要与传统关系型数据库不同的策略,本文描述使用写前日志WAL（Write-ahead Log）和并发版本系统CVS（Concurrent Versions System）的事务控制,满足ACID特性。     

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

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

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

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

事务存储系统

多核处理器性能的发挥依靠程序的并行,共享存储并行编程模型为大多数多核处理器所采用,而有效同步多个线程对共享变量的访问是其关键、也是难题.借鉴数据库中事务的思想,人们提出事务存储(transactional memory),旨在提供一种编程简单,对程序正确性推理容易的同步手段.简介了事务存储的起源,诠释了事务存储系统的概念.论述了事务存储的编程接口和执行模型.讨论了事务存储系统所涉及的主要内容,对各种方法和策略进行了比较.对事务存储中有待解决的问题进行了探讨.最后介绍了几个开源的事务存储研究平台.     

一种硬件事务存储系统模拟环境的研究与实现

针对事务存储技术研究中的模拟实验问题,实现了一种专门用于硬件事务存储系统的模拟环境,该模拟环境采用执行驱动模拟方式,支持全系统模拟,利用系统结构模拟器Simics和多核扩展包GEMS实现多核处理器相关部件的功能和性能模拟,在此基础上扩展实现硬件事务存储系统各部件的建模和模拟,以模块化的方法支持多种事务存储系统的模拟实验和性能评价.论文在分析事务存储和系统结构模拟技术的基础上,讨论了事务存储系统模拟环境的设计思路和方案,给出了该模拟环境的组成结构,并通过一种目标事务存储系统结构和一组测试程序对模拟环境进行了实验测试.     

基于事务性执行的投机并行多线程软件模拟

基于事务性执行的投机并行多线程是一种适合未来多核微处理器架构的新型并行程序设计和编译技术.但在此基础上的并行程序执行过程更为复杂,程序执行过程的模拟成为关键问题之一.本文提出利用二进制代码级动态插桩技术对投机并行多线程程序进行功能性模拟,设计并实现了完整的软件平台,可精确地模拟和监控并行程序的线程级投机执行过程,检测访存冲突,从而实现投机并行多线程的语义.该软件平台同时可以作为进一步研究投机多线程并行程序真实执行过程的基础,并有效支持投机并行多线程编译器的设计和分析.     

Store Atomicity for Transactional Memory

We extend the notion of Store Atomicity [Arvind and Jan-Willem Maessen. Memory model = instruction reordering + store atomicity. In ISCA '06: Proceedings of the 33rd annual International Symposium on Computer Architecture, 2006] to a system with atomic transactional memory. This gives a fine-grained graph-based framework for defining and reasoning about transactional memory consistency. The memory model is defined in terms of thread-local Instruction Reordering axioms and Store Atomicity, which describes inter-thread communication via memory. A memory model with Store Atomicity is serializable: there is a unique global interleaving of all operations which respects the reordering rules and serializes all the operations in a transaction together. We extend Store Atomicity to capture this ordering requirement by requiring dependencies which cross a transaction boundary to point in to the initiating instruction or out from the committing instruction. We sketch a weaker definition of transactional serialization which accounts for the ability to interleave transactional operations which touch disjoint memory. We give a procedure for enumerating the behaviors of a transactional program—noting that a safe enumeration procedure permits only one transaction to read from memory at a time. We show that more realistic models of transactional execution require speculative execution. We define the conditions under which speculation must be rolled back, and give criteria to identify which instructions must be rolled back in these cases.     

嵌入式软件虚拟内存管理平台的研究和实现

虚拟内存管理在通用操作系统中是非常重要和有效的，但由于嵌入式设备资源的有限性以及嵌入式应用实时性和可移植性的要求，必须提出一种适用于嵌入式软件系统的虚拟内存管理机制。分析了嵌入式系统虚拟内存管理应具有的功能特点，提出了一种具有处理器无关标准编程接口的嵌入式虚拟内存管理平台的实现方法。     

HybridTCache:一种基于专用事务Cache的软硬件协同事务内存系统

文中提出一种高效的软硬件协同事务内存系统HybridTCache.在通常情况下,事务完全由硬件执行,当事务大小超出了硬件限制时,操作系统将协同硬件执行.HybridTCache提出了一种新的专用事务Cache,称为TCache,缓存事务执行过程中的临时数据,由操作系统协同管理TCache溢出.文中给出了基于GEMS模拟器的HybridTCache原型系统.系统的评测显示HybridTCache比传统系统在性能、可扩展性、设计复杂度方面有较好的改进.     

事务工作流WfSaga及其建模工具

以扩展事务模型Saga和Flexible为基础,引入可替换事务和平凡事务等事务种类,借用传统事务恢复机制"保存点"的思想,提出了支持分布式工作流应用的可靠事务工作流模型WfSaga,以Java图形操作为基础,设计了图形化建模工具并用基于XML的过程定义语言对模型进行了描述,最后对模型的正确性验证进行了讨论.