没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记279(3)(2011)63-72www.elsevier.com/locate/entcs一种生成式Zala′nSzugyi1MarkTook2NorbertP ataki3埃奥特维奥斯·洛兰德大学编程语言与语言学系匈牙利布达佩斯摘要当今,编程中最重要的挑战之一是多核处理器的有效使用。许多新的编程语言和库都支持多核编程。Cilk++是C++最著名的语言扩展之一,为多核编程提供了新的关键字。C++标准模板库是一个高效的泛型库,但它不支持并行性。 它针对顺序领域进行了优化,因此在多核环境中使用时可能会成为效率瓶颈。在本文中,我们认为Cilk++的C++标准模板库的多核实现。 我们还考虑了容器、算法和函子的实现。我们的实现利用C++的生成技术我们还测量了实现的加速关键词:多核编程,C++,STL,泛型编程1介绍最近的趋势,增加核心数量的处理器,导致了新的兴趣,est在设计的方法和机制,有效的并行编程的共享存储器的计算机体系结构。这些方法主要基于传统的并行计算方法通常,低级方法仅为程序员提供控制权管理(创建,销毁),同步和数据共享的原语,这些原语通常在互斥(互斥)访问的关键区域中完成。例如,POSIX线程库可以用于此目的。以这种方式对并行复杂应用程序进行编程当然很困难;调优1电子邮件地址:lupin@ludens.elte.hu2电子邮件地址:tmark@inf.elte.hu3电子邮件:patakino@elte.hu1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2011.11.03864Z. SzuBoggyietal. /《理论与计算科学》选编279(3)(2011)63由于内存围栏(用于实现互斥)对核心缓存中复制的数据事实上,内存围栏是通信密集型(如流)并行应用程序的性能下降的关键来源之一避免内存围栏不仅意味着避免锁,还意味着避免内存中的任何类型的原子虽然存在用于异步对称通信的若干评估的无栅栏解决方案,但是这些结果不能容易地扩展到异步非对称通信,这对于支持任意流网络是必要的提高并发管理对象的抽象层次是减轻程序员工作负担、提高程序效率的重要途径例如,线程可以抽象为更高级别的实体,这些实体可以根据特定的策略在用户空间中进行池化和调度,以最大限度地减少缓存溢出或最大限度地提高内核的负载平衡。同步原语也可以被抽象出来,并与代码中语义上有意义的点相关联,比如函数调用和返回、循环等。这种抽象大大简化了应用程序的手工编码。然而,它仍然太低级,无法有效地自动化par-encode的优化:这里最重要的弱点是缺乏关于代码意图的信息生成式方法侧重于从更高级别的规范中合成实现,而不是转换它们。通过这种方法,程序员的目标被规范捕获。此外,代码生成技术也得到了很好的发展(staging,部分评估,自动编程,生成式编程)[7]。[17][18][19程序员需要通过使用适当的构造来明确定义并行行为,这些构造明确地约束了控制权、只读数据、累积操作的关联性、对共享数据结构的并发访问之间的相互作用Cilk++是C++编程语言的一组扩展,支持MIT Cilk风格的多核编程。它提供了一种快速,简单和可靠的方法来提高多核处理器上程序的性能[12]。C++标准模板库(STL)是通过泛型编程方法开发的[5]。通过这种方式,容器被定义为类模板,许多算法可以实现为函数模板。此外,算法以独立于容器的方式实现,因此可以将它们用于不同的容器[19]。C++ STL被广泛使用,因为它是一个非常方便的标准C++库,其中包含有用的容器(如列表,向量,地图等), 很多算法(如排序、查找、计数等)以及其他实用程序。STL被设计为可扩展的。我们可以添加可以与现有算法一起工作的新容器。 另一方面,我们可以扩展一组新的算法,可以与现有的容器一起工作。迭代器弥合了容器和算法之间的差距[15]。用这种方法解决了表达式问题[24]STL还包括适配器Z. SzuBoggyietal. /《理论与计算科学》选编279(3)(2011)6365转换库的标准元素以实现不同功能的类型[4]。STL算法的基于OpenMP的多核实现已经可用[18]。类似的实现对于广泛使用的Cilk++平台是必要的[22]。将并行性扩展到容器将是有价值的在本文中,我们认为C++ STL的多核实现。我们研究了如何在生成技术的帮助下为Cilk++平台有效地开发一组容器和算法。我们测量应用程序的加速比。本文的组织结构如下。第二节简要介绍了Cilk++平台。我们在第3节中介绍了如何在Cilk++的帮助下实现STL第四节介绍了典型STL算法的新实现。在第5节中,我们提出了仿函数特征的概念,并展示了重载泛型函数在此特性上的优势。最后,本文在第6节中进行了总结。2联系我们Cilk++语言可用于在多核机器上高效地执行我们的应用程序在这种语言中,应用程序在Cilk++运行时中运行,Cilk ++运行时使用计算工作者管理并行执行。这些工作线程运行在不同的操作系统线程上,每个CPU核心有一个工作线程Cilk++语言是C++,具有一些额外的语言特性。当关键字cilkspawn位于函数调用之前时,将创建并行工作。从C++函数(或方法)调用中派生派生器的语义仅在于父函数可以继续与子函数并行执行,而不是像C++中那样等待子函数完成Cilk++中的调度程序运行时系统负责在多核计算机的各个处理器核上调度产生的函数函数在执行cilksync语句之前,不能安全地使用其子函数返回的值。的cilksync语句是一个局部“屏障”,而不是全局屏障,例如,在消息传递编程中。除了cilksync语句提供的显式同步之外,每个Cilk函数在返回之前都会隐式同步,从而确保其所有子函数在它之前终止。循环可以通过简单地将关键字for替换为关键字cilk forkeyword来进行parallelize,这允许循环的所有迭代并行操作Cilk++是一个C++扩展,因此C++ STL可以用作容器和算法的通用框架。另一方面,STL并不适合多核环境。这样,STL可能是一个效率瓶颈,因为它不支持多核编程。此外,Cilk++不包含通用容器和算法库。66Z. SzuBoggyietal. /《理论与计算科学》选编279(3)(2011)633容器我们重新实现了STL的向量容器,以提高其效率。向量上有几种操作,可以通过并行来改进,例如创建一个大向量并使用给定值填充其元素,复制向量或增长其内部缓冲器。其中一些操作是由构造函数或vector的复制构造函数完成的。Cilk++提供了高级构造来支持并行性,例如cilk,但是它们不能在构造函数内部工作。(It目前尚未实施)。因此,我们需要通过较低级别的构造来处理并行性:cilk spawn和cilksync。第一个线程启动一个新线程并在其上执行一个函数,第二个线程等待派生线程被终止。使用较低级别的结构时,程序员必须手动处理在我们的解决方案中,我们将主任务拆分到与CPU中的内核数量由于内核的数量是编译时的信息,模板元程序[1]在编译器编译源代码期间进行拆分过程通过这种方式,我们可以节省确定核心数量和拆分进程的运行时开销。下面的例子展示了模板元程序如何将编译过程拆分为线程的框架。template intn,intcorenum>struct Do_aux{voidit(int size){constint s=size/ corenum;cilk_spawn process(n *s,(n + 1)*s); Do_aux n-1,corenum>::it(size);}};template intcorenum>struct Do_aux0,corenum>{voidit(int size){constint s=size/ corenum;process(0,s);}};template intcorenum>structDo{voidit(int size){if(size> MIN_GROWSIZE){Do_aux corenum-1,corenum>::it(size);cilk_sync;}其他return(0);}};结构体Do启动进程,结构体Do aux是它的实用类。结构体Do有一个模板参数,用于存储CPU中的核心数量要创建的线程数取决于它。计算过程从调用Do的静态成员函数调用它开始。参数大小是指Z. SzuBoggyietal. /《理论与计算科学》选编279(3)(2011)6367大小我们的解决方案STD::vector1000000.0000.00110000000.0010.004100000000.0190.0331000000000.1820.365表1按运行时间的向量。如果向量只有很少的元素,则不值得并行计算,因此调用过程的顺序版本。否则,将实例化实用程序结构Do aux,并调用其静态成员函数来执行进程P2P。该技术是基于模板的递归实例化。 结构Do aux有两个模板参数。第一个是关于子区间的循环变量的种类来处理,第二个是核的数目。结构Do aux将间隔划分为与CPU中的核心数量一样多的子间隔,并调用处理函数到最后一个子间隔。之后,它用当前循环变量减一和核数实例化自己,并调用静态成员函数it。 当循环变量的值为零,则选择结构体Do aux的专用版本,并停止递归。这个特殊的结构除了调用进程函数到第一个子区间之外什么也不做。在编译器编译代码的过程中,这个拆分过程是由一个模板元程序完成的。因此,编译器生成的目标代码将与从下面的源代码生成的目标代码相同。(Let我们假设CPU中有四个核心。结构执行{voidit(int size){if(size> MIN_GROWSIZE){const int s= size/ 4;cilk_spawn进程(3 * s,4 * s);cilk_spawn进程(2 * s,3 * s);cilk_spawn进程(s,2 * s);进程(0,s);cilk_sync}其他return(0);}};核的数量和常数MIN GROWSIZE由分析程序确定。这个程序在我们的库在计算机中编译之前运行。我们比较了我们的解决方案的运行时间与STL的向量。我们在四核2.4GHz CPU上进行了此测试,并使用不同大小的向量。表1显示了以秒为单位的结果我们的解决方案比STL中的矢量实现快两倍68Z. SzuBoggyietal. /《理论与计算科学》选编279(3)(2011)634算法除了容器之外,算法是STL的另一个广泛使用的部分,并且算法也以顺序的方式实现。因此,我们重新实现了算法,以运行并行计算,并利用多核领域。在这一节中,我们介绍的方法,我们应用到重新实现这些算法在并行环境中。我们可以把算法分成不同的组。这些组是非修改序列操作,修改序列操作,堆,排序等.举几个例子:• count:返回一个范围内与指定值相等的元素数。• countif:返回满足条件的范围内的n个元素。• find:返回一个迭代器,指向一个范围内的第一个元素,如果没有找到,则返回最后一个元素• fill:为指定范围内的所有元素设置值• sort:对范围内的元素进行排序。为了利用并行性,算法的输入范围必须由随机访问迭代器定义。否则,将工作线程的范围分割成更小的范围可能比并行化获得的速度慢得多为了克服这个问题,我们用迭代器标签s重载了算法,就像在STL中实现的函数advance一样[14]。当定义范围的迭代器是随机访问迭代器时,选择算法的并行版本,否则选择顺序版本鉴于大多数算法通过迭代器遍历数据结构,这种迭代可以改为Cilk++提出的cilk 在某些情况下,对共享资源的访问发生在算法内部,这导致了竞争条件的发展,这种方式的原子性保险是我们的责任。我们通过引入reducer来解决这个问题,以确保给定的变量修改是原子的。下面的例子显示了我们的实现方法,通过cilk重新实现al-taxm:template classIterator, classT>类型类型计数iterator_traits Iterator>::difference_typecount(Iteratorfirst,Iteratorlast,constT value,random_access_iterator_tag){cilk::reducer_opadd<类型迭代器Iterator>::difference_type>c;cilk_for(Iterator i=first; i!= last;++i){ if(*i==value){++C;}}return c. getValue();Z. SzuBoggyietal. /《理论与计算科学》选编279(3)(2011)6369大小我们的解决方案STD::vector1000000.0000.00110000000.0020.006100000000.0220.0421000000000.1930.289表2算法平均运行时间}重新实现算法的另一种方法是使用cilkspawn和cilksync届在本例中,我们应用了第3章中描述的模板元程序框架。表2显示了算法的平均运行时间。我们通过输入范围的不同大小来测试是在四核2.4GHz CPU上完成的在GCC编译器中有一个STL算法的实验性并行实现[18]。该实现基于OpenMP技术。这种解决方案只是比我们测试计算机中的串行版本的算法稍快一点。5函子Reducer可以用来有效地计算大量数据块上的关联操作[9]。从概念上讲,reducer是一个变量,可以被并行运行的多个线程安全地使用。运行时系统确保每个worker都可以访问变量的私有副本,从而在不需要锁的情况下消除了竞争的可能性。当线程同步时,reducer副本被合并(或“减少”)到单个变量中。运行时系统仅在需要时创建副本,从而最小化开销。我们主张一种新的特征类型,称为函子特征。 的协助下如果一个函子类型实现了一个关联操作,则可以描述该类型。算法,如累加,可以在此信息上过载,并执行算法的更有效版本,并利用关联性[10]。Functor traits类型类似于STL的迭代器traits类型。Traits由typedef组成。在STL中,可以找到重载迭代器能力的泛型算法。例如,当使用随机访问迭代器时,advance可以在常数时间运行,否则在线性时间运行首先,我们写两个伪类型来描述一个函子类型是否是关联的:struct关联{};structnon_associative{};默认的仿函数traits是一个模板类,并描述了一般的70Z. SzuBoggyietal. /《理论与计算科学》选编279(3)(2011)63functors不是关联的:模板类Fun> struct函子特征{typedef非结合结合性;};库中的典型关联函子设置为关联:模板类T>structfunctor_traits + T>>{typedef结合结合性;};模板类T>structfunctor_traits乘以T>>{typedef结合结合性;};此外,非标准函子可以定义为关联函子。现在,我们可以编写算法。我们区分了三种不同的情况,第一种是函子不是结合的,第二种是函子是结合的,但迭代器不是随机访问的,第三种是函子是结合的,迭代器是随机访问的:template class InputIterator,class T,classFun>T accumulate(InputIteratorfirst,InputIteratorlast,Tinit,有趣的binary_op){返回累积(首先,last,init,binary_op,typingiterator_traits InputIterator>::iterator_category,typeratorfunctor_traits Fun>::associativity());}在这里,我们提出了一个一般的幺半群类型。它将被专门的算法:template class T,class Fun>structMonoid:cilk::monoid_base T>{Monoid(constTt):init(t){ }void identity(T* p)const{new(p)init;}void reduce(T*a,T* b)const{*a= Fun()(*a,*b);}私人:Tinit;};现在,我们可以编写高级版本的算法,用于关联操作,迭代器是随机访问迭代器。其他两种情况调用算法的通常行为。template class InputIterator,class T,classFun>T accumulate(InputIteratorfirst,Z. SzuBoggyietal. /《理论与计算科学》选编279(3)(2011)6371InputIteratorlast,Tinit,有趣的binary_op,random_access_iterator_tag关联性){ cilk::reducerMonoid T,Fun>> reducerImp(init);cilk_for(; first!=last;++first){transformer()= transformer();}return results();}关于reducer的实现细节可以在[9]中找到。6结论和今后的工作多核编程是一种有趣的新编程方式。Cilk++是一种广泛使用的语言,它是C++的扩展。 在这个平台上,STL 它本身不准备用于多核编程,并且在该平台中没有其他容器/算法库可用。这样,STL可能成为Cilk++应用程序的效率瓶颈。在本文中,我们主张为Cilk++平台的C++标准模板库的多核版本。我们重新实现了容器,以及基于泛型编程范式的算法。我们已经制定了一个更先进的框架函子生成技术的基础上。我们测量了应用程序的加速比。我们已经实现了一组算法和容器。在本文中,我们没有处理关联容器,但是,它们也是并行化的理想容器。我们未来的主要工作之一是加强这些容器。确认该项 目由 欧盟支 持, 并由欧 洲社会 基金 会(欧 洲社 会基金 会) 共同资 助 。TA′MOP4.2.1./ B-09/1/KMR-2010-0003)。引用[1] Abrahams,D.,Gurtovich,A.:“C++ Template Metaprogramming: Concepts, Tools, and Techniques[2] Aldinucci,M.,Danelutto,M.,Meneghin,M.,Kilpatrick,P.,Torquati,M.:FastFlow在多核上的高效流应用:生物序列比对测试平台,Proc. of Intl.并行计算(PARCO)2009。[3] Aldinucci , M. , Ruggieri , S. , Torquati, M. : Porting Decision Tree Algorithms to Multicore usingFastFlow,in Proc. of European Conference in Machine Learning and Knowledge Discovery in Databases(ECML PKDD),LNCS6321,pp.7比23[4] Alexandrescu,A.:“Modern C++ Design”, Addison-Wesley[5] Austern,M. H.:“Generic Programming and the STL: Using and Extending the C++ Standard TemplateLibrary,” Addison-Wesley[6] Bishof,H.,Gorlatsch,S.:使用C++模板和骨架的通用并行编程,Proc. of Domain-Specific ProgramGeneration(国际研讨会),2003年,修订论文,LNCS3016, pp. 107比12672Z. SzuBoggyietal. /《理论与计算科学》选编279(3)(2011)63[7] 恰 尔 内 茨 基 ·K. Eisenecker , U. W. : “Generative Programming: Methods, Tools and Applications”,Addison-Wesley[8] 达古姆湖梅农,R.:OpenMP:一个用于共享内存编程的行业标准API,46比55[9] 弗里戈,M.,Halpern,P.,莱瑟森角E、Lewin-Berlin,S.:Reducers and other cilk++ hyperobjects,在Proc. 2009年,Symposium on Parallel Algorithms and Architectures(SPAA)出版。79比90[10] Gottschling,P.,Lumsdaine,A.:集成语义和编译:使用c++概念开发健壮和高效的可重用库,在第七届生成编程和组件工程国际会议上,GPCE 2008,pp。67比76[11] 哈里森,N.,Meiners,J.H.:The dynamics of changing dynamic memory allocation in a largescale C++ application,In Companion To the 21st ACM SIGPLAN Conference on Object-OrientedProgramming Systems ,Languages ,and Applications (Portland ,Oregon , USA ,October 22 -26,2006).(OOPSLA,2006),pp. 866-873。[12] 莱瑟森角E.:Cilk++ Concurrency Platform,2009年第46届年度设计自动化会议论文集,pp. 522-527[13] Matsuda,M.,Sato,M.,Ishikawa,Y.:使用C++ STL适配器的并行数组类实现,在面向对象并行环境中的科学计算,LNCS1343,pp。113- 120[14] Meyers,S.:“有效的STL - 50种改进标准模板库使用的具体方法”,Addison-Wesley(2001)。[15] Pataki,N., Szugyi,Z., 你好,G.:C ++标准模板库在一个更安全的方式,在程序. WGT 2010(WGT2010),pp. 46比55[16] Pataki , N. ,Szugyi , Z. ,你 好 , G. :MeasuringtheOverheadofC++StandardTemplateLibrarySafeVariants , “Electronic Notes in Theoretical Computer Science”264(5),pp. 71比83[17] Reinders,J.:“Intel Threading Building Blocks”, O’Reilly[18] Singler,J.,Sanders,P.,Putze,F.:多核标准模板库,第13届国际欧标会议论文集,LNCS4641,pp.682-694。[19] Stroustrup,B.:“The C++ Programming Language”, Special Edition, Addison-Wesley,[20] Szugyi,Z., Pataki,N.: Sophisti cat dMeth odsinC++,InPr oc. 计算机科学与工程国 际 科 学 会 议(CSE 2010),第10 页。93比100[21] Szugyi,Z., Sin kovics,A'., Pataki,N., P或kola′b,Z.:C++MetastringLibraryand itsAppli cations,InProc. of Generative and Transformational Techniques in Software Engineering 2009,LNCS 6491,pp.467-486.[22] Szugyi,Z., Toréok,M., Pataki,N. :在P roc中,要创建一个多核C++标准模板库。 of生成技术研讨会(WGT 2011),第100页。38比48[23] Szugyi , Z. ,Torok, M. ,Pataki , N. , Kozsik , T. :MulticoreC++StandardTemplateLibrarywithC++0x , in AIP Conf.Proc.Vol.1389 , Numerical Analysis and AppliedMathematics ICNAAM2011 : International Conference on Numerical Analysis and AppliedMathematics,pp. 857-860[24] Torgersen,M.:The Expression Problem Revisited-123-143
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- Spring 应用开发手册
- Dreamweaver制作ASP动态网页与access数据库连接教程
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功