【摘 要】
:
随着多核处理器的普及和编程语言的发展,并发程序在近年来得到了迅速的普及。由于并发程序中的线程访问共享资源的顺序并不确定,导致并发缺陷难触发、难复现、难检测,给并发程序的质量保障带来了重大挑战。本文关注实现并发程序动态分析的基础技术。并发程序的动态分析技术具有代价相对较低、正确性(soundness)容易保证等优点,是目前最有效的并发程序质量保障手段之一,也是工业实践中应用最广泛的一类技术。为实现并
论文部分内容阅读
随着多核处理器的普及和编程语言的发展,并发程序在近年来得到了迅速的普及。由于并发程序中的线程访问共享资源的顺序并不确定,导致并发缺陷难触发、难复现、难检测,给并发程序的质量保障带来了重大挑战。本文关注实现并发程序动态分析的基础技术。并发程序的动态分析技术具有代价相对较低、正确性(soundness)容易保证等优点,是目前最有效的并发程序质量保障手段之一,也是工业实践中应用最广泛的一类技术。为实现并发程序的动态分析,就必须在运行时观测并发程序的行为。不同于串行程序,并发程序执行包含线程间的共享资源依赖关系,这导致应用于串行程序的动态分析技术无法直接在并发程序中应用。这些依赖关系必须在运行时予以捕获或记录,才能实现对并发程序执行轨迹的分析和调控。本文关注并发程序共享内存访问的数据依赖(共享内存访问依赖,简称访存依赖)相关的研究问题。由于共享内存是并发程序中最常见的共享资源也是实现其他类型共享资源的基础,因此实现访存依赖的高效观测和有效使用是实现并发程序动态分析的基本问题之一。也因并发程序执行中共享内存访问数量众多,使用朴素方法获取访存依赖将导致数千倍的运行时开销和海量的事件日志。如何设计、实现并发程序动态分析技术和与之适应的访存依赖的获取技术是十分具有挑战性的难题。本文完成了对访存依赖相关的研究框架、获取技术和基于访存依赖的动态分析三方面的研究工作:1.针对目前对访存依赖研究缺乏系统性的现状,本文首先提出了访存依赖的理论框架与技术框架。理论框架帮助我们系统性地理解访存依赖获取这一问题,其中包括系统模型和访存依赖的形式化定义、访存依赖获取的问题空间。理论框架还提出了并发程序共享内存访问的局部性理论,刻画了现实程序访问共享内存的特征,为后续深入研究奠定了基础;技术框架帮助我们在统一的视角下研究来自体系结构、计算机系统、程序设计语言和软件工程四个研究领域的相关工作。技术框架包含三个要素:访存依赖获取技术的四个评价指标、获取访存依赖的两类技术、访存依赖在并发程序动态分析中的两类应用。在技术框架下实现了对现有访存依赖相关技术所作出的权衡的全面综述,为进一步研究奠定了基础。2.在理论框架和技术框架的共同指导下,提出了利用线程和空间-线程局部性的高效访存依赖获取技术。基于乐观锁的高效访存依赖获取技术RWTrace在不引入额外同步/原子操作的前提下,能实现O(1)时间对读操作的线程局部性检测,从而实现高效的访存依赖在线追踪,相比于朴素的互斥锁在访存密集型的程序上实现多达数百倍的性能提升;基于二分组(bisectional coordination)协议的高效访存依赖约减技术在运行时动态维护地址空间的区间划分,使得区间中的变量具有空间-线程局部性并被视作一个整体处理从而实现访存依赖约减,相比于高度优化的RWTrace,在仅付出0-54.7%运行时开销的前提下实现多达97%的依赖减少。3.基于在访存依赖获取问题研究中的经验,提出基于访存依赖的动态分析技术:基于缓存的高效执行重放技术CARE,其通过数值预测缓存实现近似的检测线程局部性检测,通过启发式算法离线合成访存依赖,实现高效、简洁的运行时记录;基于二分组协议的高效数据竞争检测和假共享检测算法,通过避免对整个变量组进行不必要的检测,能大幅减少检测开销和元数据维护的数量;基于依赖反转技术的应用程序崩溃一致性自动检测技术C3和移动应用的并发测试技术AATT,在知名开源软件中找到了前所未知的缺陷。最后,基于二十多年来的研究都未能找到只进行wait-free修改实现准确访存依赖追踪的事实,本文提出没有免费(只进行wait-free的修改)午餐(在多项式时间内获得满足顺序一致性的访存依赖)的猜想。在复杂性探讨中,我们给出顺序一致性判定(VSC)问题的一个新证明,并据此证明了“没有免费午餐”猜想的特殊情形。
其他文献
肿瘤细胞对化疗药物产生耐药性(Drug resistance)是造成化疗失败的主要原因。虽然肿瘤细胞耐药的机制十分复杂,但研究显示一些关键酶在这一过程中发挥重要作用,其中谷胱甘肽S-转移酶P1(Glutathione S-transferases P1,GSTP1)是最受研究人员关注的耐药相关酶之一。GSTP1在很多耐药肿瘤细胞中高表达,且GSTP1的高表达与癌症病人的不良预后密切相关。因此,在肿
研究背景食管癌是最常见的消化道恶性肿瘤之一,是由食管鳞状上皮或腺上皮的异常增生所形成的恶性病变,其发病率和死亡率因地区而异,我国是食管癌发病率最高的地区之一。根据组织学类型,食管癌可以分为鳞癌和腺癌,在我国食管鳞癌(Esophageal squamous cell carcinoma,ESCC)占到 90%以上。尽管随着一系列诊治新技术应用于临床,在一定程度上改善了食管鳞癌患者的治疗效果,但食管鳞
本论文从作用于身体之上的政治与话语权力入手,研究库切南非主题小说中所剖析的种族化、性别化的身体政治。由于注重心理探索以及形式革新,库切的南非小说,或被批评家们认为是注重探索人物内心世界而忽视社会现实的现代主义小说,或被认为致力于阐释历史之虚构性与话语性,不愿触及南非殖民主义和种族隔离制度的社会本质,因而倍受诟病。本论文提出,库切对身体所承受的各种苦难表现出深切关怀,其小说也因此具备现实观照意义。库
“主题式”语言课程是“内容依托型”教学模式连续体中的一种形式,课程以一个个“主题”展开,学习者以目的语为工具,学习与“主题”相关的“内容”,用目的语来完成各项学习任务,在此过程中其语言能力得到训练和提高。对“内容依托型”教学模式和“主题式”语言课程的研究已经成为二语教学研究热点之一。很多研究者发现“主题式”语言课程能够促进语言学习。但是,现有研究对语言能力的评估多从学习结果入手,通过实验组和对照组
本文研究的主题是C.I.刘易斯的认识论。刘易斯的认识论是以“概念实用主义”为其主要思想核心的,本文也正是从刘易斯的这一“概念”为着眼点,力图通过揭示出其认识论的深层含义,挖掘出刘易斯在实用主义理论中有关经验、知识及语言问题的深刻见解;从而展现出刘易斯在传统与现代哲学之间所做的突出贡献。并在此基础上,对刘易斯认识论的理论不足之处作个系统的评价。全文的布局分为导言、正论与评价三个部分。导言中,首先介绍
背景和目的胆管癌是指发生于胆管上皮细胞的恶性肿瘤,近年来发病率有上升趋势。即使采用以手术治疗为主并辅以放、化疗等综合方案,总体预后较差,因此探索针对胆管癌的抗肿瘤药物,以加强手术及放化疗效果,为改善患者预后提供新的思路。丙酮酸脱氢酶激酶(Pyruvate dehydrogenase kinase,PDHK)是线粒体丙酮酸脱氢酶复合体(Pyruvate dehydrogenase Complex,P
口腔鳞状细胞癌(OSCC)是头颈部最常见的恶性上皮肿瘤,主要发病机制是机体免疫功能异常致使肿瘤免疫逃逸,其中树突状细胞(DC)功能异常是OSCC免疫逃逸的主要机制。DC来源于骨髓中的造血干细胞,其分化可分为三个阶段为:前体DC(pre-DC),未成熟DC及成熟DC。DC是体内最强大的专职抗原递呈细胞,能够激发或抑制抗原特异性的T细胞反应,即未成熟DC处于耐受状态,抑制T细胞反应,而成熟DC能够诱导
周汝登是晚明浙江地区的心学家。他因与许孚远关于良知心体的争辩而为学界所知。学界据此或认为周汝登思想是“自然主义”的,或认为是属于禅宗,或认为是杂糅儒佛。其实这并不符合周汝登思想的实际。因此,全面梳理有关周汝登的文献,并依此把握其思想倾向和理论特质就很有必要。周汝登在哲学上的首要贡献,是他以“无”去消解理念世界的实体性,从而扭转了“天”对“人”的统治。他强调“造化在我,何天非人”,突出了人的主体地位
以维基百科为代表的网络百科是Web 2.0环境下知识生产、知识组织和知识分享的一种新兴形式。它突破了传统的组织模式,以激励制取代了合约制,充分利用了社会大众的集体智慧。正是在充分依靠社会大众的基础上,网络百科取得了巨大成功。在被称为“e时代”的今天,网络百科已经成为普通大众获取知识的一个重要途径。与此同时,网络百科在科学、教育和商业等多个领域也得到了广泛应用。毋庸置疑,网络百科已经取得了巨大的成功
Ⅲ族氮化物半导体材料由于其大的禁带宽度、高电子饱和速度、耐高温、耐击穿和抗辐射等优异的物理化学特性,在高温、高频、大功率电子器件领域有着比Si基MOSFET、AlGaAs/GaAs HEMT更广阔的应用前景。尽管GaN基电子器件具备上述多种优势,该器件工作的可靠性问题一直是阻碍其商业化应用的瓶颈。为提高GaN基高电子迁移率晶体管(HEMT)的可靠性,需对GaN基异质结光学特性、变温应变情况、高场条