论文部分内容阅读
新的摩尔定律指出在基本不变的主频下,单个芯片上的处理器核的数目每一代(约两年)增加一倍,程序性能的提高必须依靠并行,并行算法和并行编程是今后几十年计算机科学和软件界必须突破的科学问题和关键技术。在共享存储体系结构上,并行编程中各并行任务间通信都要通过共享变量,同步是保证正确的共享变量访问必不可少的手段。然而传统的用于线程间同步的锁机制编程困难,不具备可组合性。学术界借鉴数据库中事务的思想,提出了事务存储(Transactional Memory,TM)机制,其研究目标是提供简单高效的并行程序同步机制,近年来事务存储研究成为了体系结构和编译领域的研究热点。本文就如何构建一个实用的软件事务存储并行编程环境,从事务存储执行安全和具体语言环境中的事务语义、满足安全和语义要求的软件事务存储实现与优化、事务存储并行编程接口及事务存储程序性能调优和事务存储应用几方面,对事务存储系统展开深入研究。完成的主要工作和取得的创新性成果如下:(1)提出了事务存储串行性与事务互斥语义目前在共享存储模型的语言中,事务存储作为一种同步手段,缺乏满足安全属性条件的执行模型,对此提出了事务存储串行性(Transactional Memory Serializability,TMS)与事务互斥语义,二者描述了程序员进行事务存储程序设计的平台必须满足的要求和可能的优化空间。TMS针对事务之间并发执行提出约束,消除事务并发执行中可能的异常情况,使并发事务获得顺序执行的效果。通过证明,TMS是一种安全属性。在TMS的基础上,事务互斥语义要求存在访问冲突的事务之间保持发生序(happen-before)关系,与现有同步操作语义一致,有效解决了弱隔离性下事务代码与非事务代码之间的数据竞争问题。(2)提出了无原子操作向量时钟软件事务存储算法VectorSTM针对现有的软件事务存储实现难以同时兼顾语义与性能的问题,提出一种实用向量时钟的软件事务存储算法VectorSTM,该算法采用Bloom Filter检测冲突,不需要任何原子操作,能够有效降低软件事务存储中冲突检测和原子操作的开销,同时高效的实现了TMS与事务互斥语义。对事务存储基准程序STAMP的测试结果表明,VectorSTM性能接近高度优化的TL2,优于RingSTM,并且能提供比TL2和RingSTM更强的语义。(3)提出了基于异或函数的自适应事务冲突检测算法AdapSig针对现有软件事务存储使用的Bloom Filter误判率过高的问题,提出了一种软件实现的基于异或函数的自适应冲突检查算法AdapSig,能够根据事务执行时读写集合的大小,动态改变Bloom Filter位向量长度,达到降低误判率,提高性能的目的。在VectorSTM中,与优化前的使用位选函数、定长位串的Bloom Filter冲突检测算法相比,AdapSig算法对STAMP测试集性能有所提高,8个线程时性能平均提高3.32%,最好达到15%。(4)构建了集成优化技术的软件事务存储并行编程环境针对目前科学计算语言Fortran缺乏事务存储支持的情况,首次构造了一个OpenTM-Fortran软件事务存储并行编程环境,集成了VectorSTM与Adapsig,为程序员提供对事务程序调优的剖视信息。研究了利用事务存储对不规则循环进行前瞻并行,实验表明该方法能够有效的开发多核处理器的存储级并行和并行计算能力。