足球比分直播

基于共享资源声明的并发访问控制分析与实现.pdf

返回
基于共享资源声明的并发访问控制分析与实现.pdf_第1页
第1页 / 共59页
基于共享资源声明的并发访问控制分析与实现.pdf_第2页
第2页 / 共59页
基于共享资源声明的并发访问控制分析与实现.pdf_第3页
第3页 / 共59页
基于共享资源声明的并发访问控制分析与实现.pdf_第4页
第4页 / 共59页
基于共享资源声明的并发访问控制分析与实现.pdf_第5页
第5页 / 共59页
点击查看更多>>
资源描述:
中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文,是本人在导师指导卜.进行研究工作所取得的成果。除已特另JJn以标注和致谢的地方外,论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名星丝至堑 签字日期 忉l。。6。l。中国科学技术大学学位论文授权使用声明作为申请学位的条件之一,学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权,即学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅,可以将学位论文编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。b公开 口保密年作者签名主丝g臣签字日期竺i 2堡I导师签名 驰艺签字口期 丝墨第l章绪论第1章绪论近年来随着超线程、多核体系结构等多线程技术的发展和广泛应用,计算机底层系统已经提供了越来越高效的并行运行平台。但是,当前并行编程仍然是件困难的事情。如何提高程序的并发度,保证共享数据的‘致性,减轻程序员编程的负担,降低编译器运行的开销等,都成为制约并行编程的重大问题。为了平衡编程难度和编译器分析负担,我所在的课题组正在尝试探索一种新的面向共享内存的并行编程语言,提出一种语言级的高级抽象一共享资源使用声明。程序员只需给出共享资源的使用声明,不用关心这些数据的同步控制,编译器分析这些信息,并自动的插入具体的访问控制代码。由程序员提供的共享资源使用声明,到具体的访问控制首先需要研究不同类型共享数据的特,并分析各种类型数据在并行执行时的访问规律;另外需要研究不同的访问控制方式与共享数据使用之间的联系;最终运用多种程序分析方法,让编译器可以自动给卜H不同情况卜.具体的同步访问控制方法。本章首先介绍现今并行语言的发展和主要的访问控制技术,并比较各种技术的优点和不足,最后给出本文的研究内容。1.1问题描述已有的pthreadtll线程库扩展了并行编程的需要,程序员在使用pthread库写并行程序时,需要通过锁来管理对共享变量的访问控制,从而造成编程困难,容易出现死锁等问题。现今最流行的并行编程实践是用MPI[2】表达粗粒度的算法并行性,伴以在每个MPI任务内用OpenMPl 3J描述辅助的细粒度并行。MPI通过同时执行多个借助MPI库进行消息传递的程序实例来并行,并行粒度足程序;而OpenMP则要求程序员使用预编译指令和库函数调用对程序及数据进行标,来显示控制共享内存下的并行与同步。这类编程技术给程序员提供了最大的控制程序并行性的自己空间,却限制了编泽优化在编程语言中所起的作用【4】。正在研究的高产能并行编程语言IBM’S X1015,61、Cray’S Chapel[7】和Sun’SFortress[8】都引入了原子区,这种语言构造使得基于共享内存的并行编程不必使用显示的低级同步。原子区的引入确实简化了对共享资源访问控制的编程一J,但是目前支持原子区的软硬件技术尚不令人满意。第1章绪论为了解决以上问题,我所在的课题组正在研发一种新的面向共亨资源的并行编程语言,程序员使用这种语言编写程序时不需要显式地管理对共享变量的加锁与解锁,而只需要给出对共享数据及其使用约束的描述;编译器将根据程序中的粗粒度并行结构以及共享数据描述信息来分析识别共享数据及其并发访问控制维持区间,然后总结共享数据的不同使用特征,没计不同的并发访问控制实现策略,自动地在程序中安插共享数据的并发访问控制代码。然而从程序员提供的共享资源使用声明生成对共享资源的有效访问控制代码,需要程序分析理论和技术的支持。本文致力于研究各种类型数据的并发访问控制规律,利用共享数据使用声明信息分析得到共享数据在程序运行时具体的访问控制点,并给出自动添加访问控制代码的方法。1.2相关工作传统的并行编程主要采用锁进行同步,这种方法不但给程序员带来很大的负担,也容易产生诸如锁顺序混乱,死锁等错误。近年来出现了一些新的方式来处理共享数据的同步访问,其中最热门的是存语言中引入形如atomic{S的原子区,其中S为语句块。atomic{S的抽象语义解释为S是原子执行的,要求满足以下几点a原子性语句块S要么不做要么仝做,b隔离性语句块S执行的中间状态对其他线程是不可见的,c’致性事务执行之前和执行之后数据都必须处于一致性状态。当前原子区的实现存在有悲观和乐观两种方式也称为保守和开放方式。保守的观点认为数据竞争是严重的,在对数据进行访问时需要先获得访问的权限,然后才能做相应的操作。而乐观方式认为数据竞争不严重,可以先投机地执行代码块S,在执行结束前进行冲突检测决定是提交还是回滚。采用保守方式的原子区实现是由编译器将原子区变成基于锁的代码Il卜191,编译器通过全程序分析来识别共享资源并为之分配锁,确定在程序中加锁和解锁的位置,由于存在指针间接访问共享资源、共享资源被传入到原了区内调用的函数等情况,编译器只能采取保守的分析,导致生成的代码并发度不高。采用保守方式设计实现原子区的研究T作有Bill McCioskey的AutolockerI博J、Michael Emmi的Lock Allocationl22】、Sigmund Cherem的Inferring locks for atomic sectionsI 19J、Michael Hicks的Lock Inference for Atomic Sectionst刀l等。其中,Autolocker定义了一种程序语言,程序员需要给m共享变量的定义和保护该变量的锁,同时需要显式的指定原子块。然后编译器运用指针分析和类型推理的方法去分析原子块中共享数据的访问点,最终由编译器在这些位置添加锁。这种做法程序员只需给出2第1章绪.沦用于保护共亨数据的锁,而不用去管理锁的使用,减轻了程序员的负担。它采用了两阶段锁的方式去保护整个原子区,当原子区结束后才释放所有的锁,这样的方式不利于处理类似树这样的结构。Sigmund Cherem提供了更简单的语法,程序员只需要指定原子区的开始和结束点,剩下的事就全由编译器完成。他为了分析原子区中的共享数据建立了一套程序分析的框架,通过分析得到数据的各种使用方式,例如变量、偏移地址和引用等,并为这些方式定义了不同的锁,最终通过他们提供的锁库来运行程序。这种方法大大减轻了程序员的负担,但是编译器的代价太大。采用开放方式设计实现原子区的研究工作以事务内存【1 o】技术为主。事务内存借鉴了数据库中事务的概念,但又有很多区别。粗略的说,事务内存是一种编程抽象或编程泛型,通过内存事务来保汪共享数据的一致性。一个内存事务是一组含内存操作的操作序列,要么全做即成功提交、要么全不做失败终止。目前事务内存有硬件事务内存HTM,Herlihy和Moss[TM最早在硬件上实现了事务内存系统。软件事务内存STM,Shavit和Touitou[251通过软件的方法实现了事务内存系统。目前主要的研究是在软件事务内存上,Dave Dice的TL2126】实现了一种基于版本锁的软件事务内存。它将每个内存映射到一个锁,并且锁中包含锁标记和锁版本,标记表示是否被锁,版本用来记录该锁对应的地址值最近被修改的时间戳。根据版本的比较可以让事务在执行时就对读写的内存地址直接检查是否已被修改,避免了做剩下无用的操作,从而提高了STM的执行效率。事务内存的方法虽然在程序的正确性上大大提高,但是事务内存技术尚未成熟【1叫61,现有的事务内存系统的运行开销普遍较高,囚事务中止而引起的不确定性会是程序的调试复杂化;因不了解应用程序的数据访问特征而采取的保守冲突检测导致产生假冲突,此外还有诸如系统调用和I/O操作能否出现在事务中、事务嵌套[15,16]等问题。此外一些特殊的原子区也可以用无锁编程实现,低级代码上无锁编程的目标是在不使用锁的前提下安全的管理共享资源的访问,主要的方法是处理器提供的CAS或LL/SC指令,无锁代码虽然效率高但是很难编写和维护120,21]。1.3研究内容在充分调研国内外相关工作的基础下,本课题组致力于设计并实现一种基于共享数据使用声明的并行编程语言。这种语言的特点在于提供一种简单有效的并行编程方式,通过在语言级卜给卜H共享数据使用声明信息,然后编译器通过程序分析【27l获得共享变量的维持信息,最后依据维持信息由编译器自动给并行程序3第l章绪论添加共享数据的访问控制代码。基于以上整个项月的研究模块,本文主要研究和完成以的工作1.参与SPC语言的没计,研究通过共享数据声明来捕述共享数据的使用,从而给编译器提供简单、有效的静态分析信息。第一阶段我们对语言进行简化,集中研究共享数据在并行程序中的使用情况,并将SPC翻译剑采用锁方式的访问控制上。2.研究动态数据的维持特性,通过在源语言级给出数据结构的形状信息,从而使编译器能够分析动态数据的共享性质和维持性质。形状图在程序中的推导可以用来表示动态数据的形态和数据与指针之间的关系,然后根据图形的表示分析哪些动态数据是共享,哪些数据需要维持,最终给出这些动态共享数据的维持区间信息,并通过指针访问路径来进行保护。3.根据项目组其他同学分析整型共享数据得到的维持开始于结束点信息,研究在不同程序结构中加锁与解锁的规律,从而给出自动加锁操作的方法。设计一种能够表示整型共享数据在各种程序结构下加锁和解锁操作的访问控制信息,和计算这种访问控制信息的方法,为后面的访问控制提供依据。4.在一种编译平台下实现源到源的程序变换,将SPC语言翻译到带有访问控制代码和并行结构的C程序,并提供翻译后程序的运行库。运行库中的线程管理和锁操作主要足基于pthread库的实现。对于自动添加锁操作的位置则是依据前面设计的维持信息中存储的访问控制点。1.4论文组织本文的其余部分是这样组织的第2章介绍本项目组共同研究的一种基于共享资源声明的并行语言SPC。首先介绍该语言的特点,然后介绍为实现用该语言编写的程序能够编译运行采用的主要方法步骤,并简要介绍本文承担的主要工作。第3章详细介绍一种基于形状图推导的动念数据的访问控制分析方法,利用形状图对动态单元和指针的抽象,分析程序中动态数据的共享性和维持性。第4章介绍整型共享数据在不同程序结构中加锁和解锁的分析,给出一种对应的方法用于计算这种访问控制信息。第5章介绍在SUIF编译框架下实现一种源到源的程序变换,以及为变换后程序实现程序的运行库。第6章对全文进行总结4第2章SPC语言总述第2章SPC语言总述我所在的课题组已设计出一种新的面向共享资源的并行编程语言Sharedvariable usage declarations based Parallel C.style language,简称sPc,程序员使用这种语言编写程序时不需要显式管理共享资源的访问控制代码,而只需要给出共享数据及其使用的描述,编译器将根据程序员提供的共享数据描述信息来分析识别共享数据及其访问控制点,然后根据共享数据的使用特征,给出相应的并发访问控制实现策略,自动地在程序中安捅共享数据的并发访问控制代码。本章首先介绍课题组设计的并行编程语言SPC的语法,语义和主要特性。然后介绍对SPC这种并行程序语言设汁的具体实现思路和总体实现框架,并简单介绍本文在整个设汁和实现中完成的工作。2.1 SPC语言简介SPC语言是本项目当前设计的基于共享资源需求描述的并行编程语言。它的控制流结构、表达式以及类型整型、指针型、结构体类型等源自C语言,增加了共享变量的使用声明last、shared等,另外引入粗粒度的并行机制如cobegincoend并行语句。图2.1给出了SPC的详细语法定义。与已有的共享资源访问的同步方式/应用编程接口相比,我们课题组设计的共享变量维持声明有以下特色1语言抽象层次更高程序员只需声明对共享变量的维持需求,而不需要采用具体的同步技术来对共享变量的访问控制直接编程。2易于分析利用程序员给出的共享变量维持声明信息,编译器能较容易地获得对共享变量的维持信息。3访问控制策略灵活利用共享变量的维持信息,编译器可以结合底层结构特征,采用不同策略灵活生成共享变量访问控制代码。SPC与具有锁和原子块特点的浯言相比,为其享数据的同步提供更高层语言的抽象描述。程序员在编写并行程序时,不需要自己管理锁,也不需要考虑原子块的问题,只要给出芡享变量的维持声明。例如,为了表达某个线程在一段代码段范围内对某个共享变量一直保持访问权限,可以使用关键字last在被维持范围的最后一条语句上修饰该共享变量。编译器根据程序员提供的这螳信息,分析如何对共享变量的进行访问控制,并根据具体的情况选择最优的访问控制方式和访问控制粒度。5第2章SPC语言总述ProgramStruct Declaration ListStuct DeclarationField Definition listlField DefinitionVariable Declaration ListVaria ble DeclarationIdentifier ListFuncition DefinitionStatement Block ListStatement Block Statement ListStatementAtomic StatementJExpressionBoolean ExpressionLvalue Expression ListL·value ExpressionConstantArithmetic Binary OperatorRelational Bi nary O peratorBoolean Binary 0peratorInteger ConstantIndentifierp,07u”‘ 2掌tructdec list £,·ucth·· 矗elddctfist矗eldd盯 vardrc list ;uⅡ,deC“ tdhst pm.d吖blocklist block slmthst shut 5lIIIIIIlnto,,‘善打H£ IIlIlbexp llIh,alhst ll,al c, 黼£shoprbopbbopinlconstst l’“.tthcl i.st tflrdeclisttrtdof Istr·“·tdechst s≠,‘“c·tdecstruct id{fie.1dd,伊讧t}fiehhle.f Iflelddefltst.1Ieldd盯int idI struct·idr l,ardcclist oaIrlccint tdhst;I struct}idzd tdhst,idvoid main1 blockblock{blot Mist blockf”rzrwecli.t.stmtlist}f I,{lmt,l抽Z一£竹“atoln,_tmtreturn;jfbt一_∥一z,nzifhr,jMint else Mrnlwhile阮rtJ,s lmlidmaliocsturct州;freei,班blockcobegln blocklist eoendh’alexp;skip lvallist£t alnFpC ortatf珂,exp n£,巾凹p【6P.rpbrxpexp rbop exp6P.rp bbop bexplast id I胁alliat.1ast fdjlast idid I州---F last idfd last f rZ l,f]c÷i“l last idid I州.÷last idf”£‘rttfIl·I/I X-l I_II·&矗l I I l;l}一【o-9][o-g].f_A-z.-}lo一9_A-Za-z],图2.1 SPC语法定义以下的各小节将分别介绍SPC中共享数据的描述,并行结构的定义,以及共享数据维持的含义。2.1.1共享数据描述SPC程序中的数据区被分成可以被多个线程访问的共享数据区以及每个线程的私有数据区。不论是共享数据区还是线程私有数据区,都可以进一步分静态数据区和动态数据区,前者存放静态分配的数据,后者存放通过malloc动态分配的数据。·在函数外声明的变量均认为是共享的,称为全局共享变量。6第2章SPC语言总述·由malloc所分配的共享存储空间称为动态共亨变量,而那些在程序中声明的共享变量称为静态共享变量。·如果一个指针类型的变量是共享的,则不仅该变量对应的存储单元是共享的,而且其指向的单元也是共享的。·如果一个结构体类型的变量是共享的,则它所有的域都是共享的。不存在一个结构体的一部分域是共享的,而剩余的域是非共享的情况。·如果指针变量P声明为全局共享变量或者是指向共享变量的局部变量或形参,则当执行Pmalloc时,malloc将在共享数据区中分配存储空间。·如果指针变量P声明为不指向共享变量的局部变量或形参,则当执行Pmalloc时,malloc将在线程私有数据区中分配存储空间。2.1.2并行结构并行语句eobegin block list coend表示组成block list的各个程序块将产生一个线程体,采用fork-join的方式并行执行。其中,执行并行语句中每个程序块的执行体称为是执行并行语句的线程的子线程。执行并行语句的线程等待各子线程执行结束后,才继续执行eobegin block list eoend之后的语句。编译器需要为cobegin block list eoend中的各个程序块分配创建子线程、以各程序块作为各子线程的执行任务来启动子线程的执行、等待子线程的执行结束、销毁子线程等。2.1.3维持特性一个线程T存执行某段代码期间维持某共享变晕S,是指该线程在此期间要访问S,并且禁止其他线程在此期间访问S。在线程T维持共享变量S期间,只要出现线程T对共享变量S的值的修改,则称线程T写维持S,否则称为T读维持S。对于整型的共享变量S,在一个线程T写维持S期间,禁止其他线程对S读和写。对于指针类型的变量S,则在一个线程T读维持或写维持S期间,禁止其他线程对S读写,进一步地,还不允许其他线程释放S所指向的变量因为若S所指向的变量被其他线程释放,本质上就是S被其他线程修改,即修改成了悬空指针。仅上述自动维持尚不足以囊括各种需求,因此给程序员提供一种描述维持需求的手段。last可以出现在左值表达式中,带last的变量出现在某线程的一个原.了代码7第2章SPC语言总述段中表示,从上次读写该变量到执行该原子代码段期间,该变量被维持。在自动维持和last维持还不足以表达维持需求时,可以借助skip lvall,,lval行语句,其中Ival,包含有last修饰符。skip语句本质上是不执行任何操作,但是把它当作读lvalt.,lval。的一个语句,以便通过其中的last来调整对lvall,...,lval。的维持。共享变量的最简单的维持区间是一个包含该共享变量的原子代码段的执行区间,即从这个原子代码段之前的程序点到其之后的那个程序点所执行的代码。更长的维持区间则是南上面的自动维持和last维持等引起的。2.1.4 SPC程序实例//second blockintbuffer;//shared {void main{ int flag,count;//buf.fer initialize flagI;count0;whileflag{cobegin ifbuffer0{||黾rst block last bufferbuffer·1{ countO;int flag; }else{flag1countcount1whileflag{ ifbuffer1 OO{ ifcount1 ooo{flagO flag2 0}else{ Iast bufferbufferl; coendreturn;图2.2 SPC程序实例图2.2是一个用SPC语言编写的生产者消费者的并行程序实例,程序中包含一个全局共享变量buffer用来表示当前剩余产品的数量。该程序中有两个并行块,每个并行块将创建一个线程,并以fork-join的形式并行执行。其中一个专门用于生产,另一专门负责消费,两个线程可能回同时对共享变量bu疏r进行操作。因此每个并行块中在使用buffer时都需要给出相应的last使用声明,以便编译器可以根据这个声明分析访问控制信息。2.2 SPC实现框架为了能够使SPC语言编写的程序能够真正的运行,使其更具有实际应用价值。本阶段我们的考虑通过一个扩展性较高的编译平台将SPC叶1的语法结构先8第2章SPC语言总述翻译到编译框架的中间表示结构中,然后再中间表示层进行各种程序分析得到所需要的访问控制信息,最后再通过一种源到源的程序变换方法,将SPC程序翻译成具有并行执行能力的C语言程序。如图2.3,整个项目的总体实现方案包含前端解析、CFG生成、维持区间分析、访问控制分析和优化、程序变换和运行库支持等儿大部分。2.2.1整体框架图2.3 SPC语言实现总体方案图1其中前端解析是指将SPC程序翻译成带有扩展结构的SUIF编译、F台中间表示;CFG生成是在编译,F台中生成程序的控制流表示结构,为后一阶段的程序分析和变换提供支持。2维持分析是在中间表示层利用各种程序分析技术对SPC源程序中的共享数据进行分析,得到共享数据在程序巾需要维持的范用,即维持区间信息。3访问控制分析是根据维持分析得到的共享数据维持区间信息,分析程序的不同情况,决定采用哪种具体访问控制方式,然后给出这种控制方式下自动插入访问控制代码的方法。4程序变换的作用是在中间表示层对SPC源程序进行包括类型、结构、插入代码等源到源的变换【3 71,将SPC程序翻译成GCC可以编译运行的以PThread库为基础的C代码并行程序;5运行库的作用是为变换后的程序定义程序运行时需要调用的程序代码,主要包括内存分配,线程管理和同步控制等实现。9
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播