天津大学并行计算（共7篇）
三维低速NS方程的并行计算
本文在求解低速NS方程的串行程序基础上,针对分布式存贮网络异构的`并行编程环境建立了隐式并行计算软件,并行计算的方法采用区域分解法.并行软件对高速列车进行了气动特性计算,并对并行效率和并行可靠性进行了研究,结果表明:并行计算结果与串行计算吻合良好,并行改造后的软件可以应用于工程实际问题.
作 者：王开春 李树民 朱国林 作者单位：中国空气动力研究与发展中心,四川,绵阳,621000刊 名：空气动力学学报 ISTIC EI PKU英文刊名：ACTA AERODYNAMICA SINICA年，卷(期)：20(z1)分类号：V211.3关键词：低速NS方程 并行计算
近年来多核处理器的快速发展,使得当前软件技术面临着极大挑战。无论CPU在主频率上还是处理器核数上都在飞速发展。硬件技术在不断发展的同时,要求软件技术也须同时进步。常用的并行计算技术有调用系统函数启动多线程以及利用多种并行编程语言开发并行程序,常用的并行编程模型有MPI、PVM、Open MP、TBB、Cilk++等。利用这些并行技术可以充分利用多核资源,适应目前快速发展的社会需求。并行技术不仅要提高并行效率,也要在一定程度上减轻软件开发人员负担,如近年来的TBB、Cilk++并行模型就在一定程度上减少了开发难度,提高了开发效率,使得并行软件开发人员把更多精力专注于如何提高算法本身效率,而非把时间和精力放在如何去并行一个算法。
1 并行架构[1,2]
常用的并行架构分为SMP(对称多处理器结构)、NUMA(非统一内存存取)、MPP(巨型并行处理)、CLUSTERS(集群)。
SMP系统中每个计算机中有多个对称CPU处理核,无主次或从属关系,它们共享内存空间和I/O设备,每个CPU访问内存中的任何地址所需时间是相同的,因此SMP也被称为一致存储器访问结构(UMA:Uniform Memory Access)。由操作系统调度算法将任务进行分解并分配在不同的CPU处理核上运行。SMP服务器的主要特征是共享,系统中所有资源都是共享的。
NUMA即非一致访问分布共享存储技术,它是由若干通过高速专用网络连接起来的独立节点构成的系统,各个节点可以是单个的CPU或是SMP系统。在NUMA中,Cache的一致性有多种解决方案,需要操作系统和特殊软件的支持。
MPP提供了另外一种进行系统扩展的方式,它由多个SMP服务器通过一定的节点互联网络进行连接,协同工作,完成相同的任务。其基本特征是由多个SMP服务器节点通过互联网络连接而成,每个节点只访问自己的本地资源(内存、存储等),是一种完全无共享(Share Nothing)结构,因而扩展能力最好,理论上其扩展无限制。在MPP系统中,每个SMP节点也可以运行自己的操作系统、数据库等。但和NUMA不同的是,它不存在异地内存访问的问题。
集群系统由独立的计算机组成,由控制管理工具统一管理,搭建集群的目的是共享和高效地利用资源,提供海量数据运算功能,提供负载均衡功能及出现故障时具有保障数据容错功能。
2 并行编程模型
并行编程可以调用系统函数启动多线程,也可以利用并行编程模型,如常用的并行模型有MPI、PVM、Open MP、TBB及Cilk++等。
2.1 MPI简介[3,4]
MPI(Message Passing Interface)是基于消息传递的并行编程模型。消息传递指的是并行执行的各个进程具有自己独立的堆栈和代码段,作为互不相关的多个程序独立执行,进程之间的通信通过显式地调用通信函数来完成。
(1)MPI程序基本函数
(1)MPI_Init用来初始化MPI执行环境,建立多个MPI进程之间的联系,为后续通信做准备。而MPI_Finalize则是结束MPI执行环境。这两个函数之间定义MPI程序的并行区域。
(2)MPI_Comm_rank来标识各个MPI进程。
(3)MPI_Comm_size用来标识进程组中有多少个进程,返回整形的错误值,同时有两个函数参数,MPI_Comm类型的通信域,标识参与计算的MPI进程组,如MPI_COMM_WORLD;整数指标,返回相应进程组中的进程数。
(2)MPI性能分析与优化举例
MPI消息传递开销由两部分组成:一部分是通信固有的延迟;另一部分是消息传递开销,与消息的数据量和网络带宽有关。时间消耗可以用下面的式子表示:
其中,TTotal、Tcomm、Tserial分别表示程序总用时、通信用时和串行部分用时。而通信用时一般可作如下分解:
其中,n为点对点通信次数,m为群集通信次数,ts为通信固定延迟,Bi为第i次通信的容量,ω为网络带宽,Ti为负载不平衡造成的时间消耗,TCi为群集通信耗时。
(3)解决负载均衡问题
在并行计算中,若各个处理器上的执行时间不同,因同步会使先完成的处理器等待未完成的处理器,此时应该考虑负载均衡问题,使得资源得到合理利用。负载均衡分为:静态负载均衡及动态负载均衡。静态负载均衡适用于计算前可以准确估算总的负载,且这些负载容易平均划分给各个进程的情况。对于事先不知道负载总数,或者总负载不易平均划分的情况,需要动态负载均衡策略来解决。
2.2 PVM简介[5]
PVM是一个在网络上的虚拟并行机系统的软件包,它允许将网络上基于UNIX操作系统的并行机和单处理机的集合当成一台单一的并行虚拟机来使用。PVM支持用户采用消息传递方式编写并行程序。PVM支持用户采用消息传递方式编写并行程序,计算以任务为单位,一个任务就是一个UNIX进程,每个任务都有一个taskid来标识(不同于进程号)。
PVM支持在虚拟机中自动加载任务运行,任务间可以相互通讯以及同步,在PVM系统中,一个任务被加载到哪个结点上去运行,PVM就允许用户指定任务被加载的结点,这样就方便了用户编写并行程序。
2.3 Open MP简介[3,6]
Open MP是一种面向共享内存及分布式共享内存的多处理器多线程并行编程语言,它也是一种能够用于显示指导多线程、共享内存并行的应用程序编程接口。Open MP的编程模型以线程为基础,通过编译指导语句来显示地指导并行化,为编程人员提供了并行化的完整控制。Open MP的执行模型采用Fork-Join形式,Fork-Join执行模式在开始执行的时候,只有一个主线程存在。主线程在运行过程,当遇到需要进行并行计算的时候,派生出子线程来执行并行任务。在并行执行的时候,主线程和派生线程共同工作。在并行代码结束执行后,派生线程退出或者挂起,不再工作,控制流程回到单独的主线程中。
图1是共享内存多线程应用程序的Fork-Join模型。主线程在运行时遇到并行编译指导语句,根据环境变量派生出4个子线程,4个子线程与主线程同时运行。在运行的过程中,某一个派生线程遇到了另外一个编译指导语句时,也派生出另外一组子线程。新的线程组共同完成一项任务,但对于原有的线程来说,新线程组的工作类似于一块串行程序,对原来的线程不会产生影响。新线程组在通过一个隐含的同步屏障后,汇合成原有的线程。最后,原有的线程组汇合成主线程,执行完最后的程序代码并退出。
(1)编译指导语句
编译指导语句的含义是在编译器编译程序的时候,会识别特定的注释,而这些特定的注释就包含着Open MP程序的一些语义。如在C/C++程序中,用#pragma omp parallel来标识一段并行程序块。在一个无法识别Open MP语义的普通编译器中,会将这些特定的注释当作是普通的注释而被忽略。因此,如果仅仅使用编译指导语句中,编写完成的Open MP程序就能够同时被普通编译器与支持Open MP的编译器处理。这样就可以用一份代码来编写串行或者并行程序,或者在把串行程序改编成并行程序的时候保持串行源代码部分不变,极大方便了编写人员。常用的编译指导语句以#pragma omp开始,具有如下形式:
#pragma omp
其中,directive部分就包含了具体的编译指导语句,包括parallel,for,parallel for,section,single,critical,flush,ordered和atomic,这些编译指导语句用来分配任务或者用来同步。
(2)运行时库函数
Open MP运行时函数库用以设置和获取执行环境相关的信息,它们也包含一系列用以同步的API,如omp_get_thread_num()就是一个运行时函数库中的函数,用来返回当前线程的标识号。Open MP程序同时结合了两种并行编程方式。通过编译指导语句,可以将串行的程序逐步改造成一个并行程序,同时也可以将串行程序和并行程序保持在一个源代码档中,减少了维护的负担。Open MP也提供了运行时库函数来支持运行时对并行环境的改变和优化,给编程人员足够的灵活性来控制运行时的程序运行状况。
2.4 Intel TBB(Threading Building Block)简介[7,8]
Intel TBB是一个用来支撑可扩展编程的库,TBB的工作层次要高于裸线程,它为C++程序提供了丰富而完备的方法来表达并行语义。TBB指定的是任务而不是线程,一般线程软件包都要求创建、汇合及管理线程。TBB运用自己的调度算法把任务分配到各个线程,高效合理地利用处理器资源。TBB的目标是通过线程来提升性能,将密集的计算任务并行化,提供更高层次和更简单的解决方案,TBB依赖泛型编程。TBB中还支持算法模板,如基于递归区间的面向循环算法,根据需求来递归地划分问题,从而获得并行任务的正确层次。相比静态划分问题,递归划分问题的方式更占优势。线程构建模块的函数都定义在空间tbb中,TBB提供parallel_for与parallel_reduce泛型并行算法,可以负载均衡地对固定数目的独立循环迭代体进行并行执行。
参考以下示例:
将这个循环并行化的第一步就是将循环体转换为小空间上进行操作的形式。这种形式是标准模板库(STL)风格的函数对象,称为体对象(body object),每个operator将处理一个小空间。
其中,方法operator()的迭代空间参数。blocked_range
2.5 Cilk++简介[9]
Cilk++语言扩展了C++语言来编写并行应用程序,有效地利用多处理器。Cilk++语言特别适合但不限于分而治之算法,把任务分解成子问题(任务),可以独立地加以解决。递归函数通常用于分而治之算法。这些任务会在不同循环迭代。Cilk++关键字识别函数调用和循环,可以并行运行。Cilk++语言比较适合“二分法”算法,将问题分解成若干独立子问题,再将这些执行结果合并起来。任务既可以在不同的函数里实现,也可以在一个迭代的循环中完成。Cilk++的关键词能有效地标识可并行执行的函数调用和循环,Cilk++的运行环境能有效地将这些任务调度到空闲的处理器上运行。
(1)使用Cilk++并行化程序的步骤
定位出程序中可并行部分;使用Cilk++关键词;编译程序;执行程序;通过使用reducer、锁及重写代码解决由于竞争条件而产生的冲突问题。
(2)Cilk++三个关键词:cilk_spawn、cilk_sync和cilk_for
(1)cilk_spawn关键词修改函数调用语句,可使该函数与调用函数并行执行。Func函数是能与当前strand并行执行的函数,一个strand是一串行指令序列。包含cilk_spawn的程序段可以和之后的func部分并行执行。Var是一个类型为func返回类型的变量,它接收函数调用的返回值,被称为接收者。对于返回值为空的函数,则必须省略接收者。args是被衍生的函数的参数。
(2)cilk_sync语句表示当前函数不能继续和派生的子任务并行运行,在所有子任务运行完之后,当前函数才能继续执行,cilk_sync只同步由该函数衍生的子任务,其它函数的子任务不受影响。
(3)cilk_for循环用于取代for循环,它允许循环迭代并行执行。cilk_for的语法规则基本如下:
Cilk++运行环境将一个cilk_for循环转换成基于循环迭代的递归往复,使用了有效的二分法策略,cilk_for的串行化就是将cilk_for换成for,但cilk_for循环有比C/C++的for循环更多的限制。因为循环体要并行执行,循环控制标量和非本地变量均不能被修改,否则将导致数据竞争,Reducer可以用来防止竞争。
3 云计算、分布式计算及网格计算
3.1 云计算与并行计算[10]
云计算是分布式处理、并行处理和网格计算的进一步发展,是一种新兴的共享基础架构的技术,它可以将巨大的系统池连接在一起以提供各种IT服务。连接设备、实时数据流、SOA的采用以及搜索、开放协作、社会网络和移动商务等都是推动云计算技术发展的推动因素。
云计算与并行计算相比,在应用广泛性方面,并行计算是为满足某科学领域的专业需求,要求开发者具备较强的技术水平,不具备较强的广泛性,但云计算可以运用在较多领域,而且具有好的效果。在性能方面,并行计算主要追求较高的加速比,而云计算则单机的计算能力要求较低,此系统通过将分散的结点统一,根据相应调度算法合理调度,从而获得巨大的计算能力,而且还能根据客户的需求变化进行调整。
3.2 分布式计算[11]
分布式计算是一种把需要进行大量计算的工程数据分割成小块,由多台计算机分别计算,在上传运算结果后,将结果统一合并得出数据结论的计算方法。目前常见的分布式计算形式通常使用世界各地上千万计算机的闲置计算能力,通过互联网进行数据传输,进行数据交互。
3.3 网格计算[11]
网格计算是分布式计算中一种类型,是针对复杂科学计算产生的一种新型计算模式,此系统将具有很强的数据处理能力,它是随着互联网而迅速发展起来的。这种计算模式是利用互联网把分散在不同地理位置的计算机组织成一个虚拟的超级计算机,其中每一台参与计算的计算机就是一个节点,而整个计算是由成千上万个节点组成的网格,所以这种计算方式叫网格计算。网格计算背后的思想是解决平衡和重新分配现有IT资源所需要的压力。
网格计算具有两个优势:一个是数据处理能力超强;另一个是能充分利用网上的闲置处理能力。
4 结束语
介绍了常见并行架构,分为SMP(多处理系统)、NUMA(非统一内存存取)、MPP(巨型并行处理)、CLUSTERS(集群),介绍了常用并行编程模型,有MPI、PVM、Open MP、TBB及Cilk++等,对以上各个模型进行了分析比较。
最后,介绍了云计算、分布式计算、网格计算与并行计算之间的联系及以后的发展方向。
参考文献
[1]庞征斌.基于SMP的CC-NUMA类大规模系统中Cache一致性协议研究与实现[D].国防科学技术大学,2007.
[2]王睿伯.面向NUMA结构的软件事务内存关键技术研究[D].国防科学技术大学,2007.
[3]李晓明.多核程序设计[M].清华大学出版社,2007.
[4]张武生,薛巍,李建江,等.MPI并行程序设计实例教程[M].清华大学出版社.
[5]纪珊珊.基于PVM的并行计算在PC机群上的实现[D].大连理工大学,2000.
[6]Shameem Akhter,Jason Roberts.多核程序设计技术——通过软件多线程提升性能[M].电子工业出版社,2007.
[7]James Reinders.Intel Threading Building Blocks[M].北京:机械工业出版社,2009.
[8]王磊,曹菡.基于TBB和Cilk++的并行蚁群算法在路径寻优中的应用[J].计算机应用,30(10):2781-2784.
[9]Intelcilk++sdk programmer’s guide[EB/OL].http://www.owlnet.rice.edu/～comp422/resources/Intel_Cilk++_Program-mers_Guide.pdf.
[10]刘鹏.云计算[M].北京:电子工业出版社,2010.
关键词：并行计算；系列课程：教学团队
近几年来，高性能并行计算机的发展取得了长足的进展，每秒数十万亿次乃至数百万亿次计算能力的高端并行机已相继研制成功。同时，廉价的PC机群、多CPU(多核)的桌面系统和个人高性能计算机的出现与发展，更是使得今日的并行计算机，已经“飞入寻常百姓家”了。价廉的桌面式并行系统中，有多个处理器可供使用，迫使人们必须学习并行计算，才能有效地利用手边的丰富资源。这就为并行计算的教学的发展和推广带来了新机遇，也对并行计算系列课程的建设与推广提出了新要求。在此条件下，为了适应高性能并行计算迅速发展的需要，充分发挥计算学科在现代科学和技术发展中的作用，在高校中普遍开设高性能并行计算类的课程就显得尤为重要。与之相应的，配合该学科发展的课程建设也是刻不容缓。
20多年来，中国科学技术大学在并行计算相关的教学和科研中积累了许多经验，取得了一些成绩，逐渐形成了并行计算系列课程的教学团队。教师是教学过程中最为重要的因素，教学团队的建设决定了课程建设的效果。本文主要介绍我们在教学团队建设过程中的一些经验和体会，希望可以有助于并行计算课程的推广，并为其他课程教学团队建设提供有益的思路。
一、教学团队的基本情况
1并行计算系统课程特色
并行计算系列课程包括并行计算、并行计算机体系结构、并行算法和并行程序设计等课程，力图适应培养面向21世纪的宽口径、通才、适应性强的高等人才的培养需要，定位于全国计算机专业的专业基础课，面向全国普通高校中计算机专业，兼顾全国高校中面向计算型的非计算机专业。系列课程将“并行计算机”、“并行算法”和“并行编程”融为一体，将“课堂讲授”与“上机实践”融为一体，将“基础理论”与“学科前沿”融为一体，将“基础教学”与“培养学生创新能力”融为一体，努力沟通“计算机科学”、“计算科学”和“计算型应用科学”。
2团队的结构及特色
在并行计算系列课程长期建设过程中，逐步形成了相对稳定的老中青相结合的教学团队。教学团队的带头人为中国科学院院士、首届高等学校教学名师奖获得者陈国良教授。他长期致力于本团队课程建设，坚持在本校教学第一线为本科生和研究生授课，指导和培养年轻教师的教学工作。教学团队成员中包括多名教授、副教授、讲师，年轻教师基本具有博士学位。
团队成员具有良好的知识结构，坚持教学科研相结合，专业蕴含了并行算法、并行计算机体系结构和并行程序设计等领域。每门课程都配备至少两位教师，以便轮流执教。通过在职培养和短期出国进修，进一步拓宽团队成员的知识面，优化知识结构。
二、教学团队的作用
1教学团队带动了系列课程的教材建设
课程建设的核心是教材建设，中国科学技术大学历来就非常重视教材建设工作。20世纪90年代中期以来，教学团队酝酿和筹划并行计算课程的配套系列教材建设工作，根据并行计算的课程体系，规划了并行计算课程的系列教材——并行计算系列从书：
《并行计算——结构·算法·编程》教材，是以并行计算为主题，探讨了并行计算的硬件平台(并行计算机)、并行计算的理论基础(并行算法)和并行计算的软件支撑(并行程序设计)，强调了融并行计算机结构、并行算法设计和并行编程为一体，涉及的内容比较广泛。该教材为“九五”国家规划教材(1996)、面向21世纪课程教材(1999)、高等教育出版社“高等教育百门精品课程教材建设计划”精品项目(2002)，2000年获中国高校科学技术一等奖，2006年入选“十一五”国家规划教材。
《并行算法的设计与分析(修订版)》教材，是以并行计算模型为主线，探讨了计算机科学中诸多常用的数值和非数值计算问题的并行算法设计及其分析方法，加强了学科发展趋势的论述，充分吸收了学术界的最新成果。该教材为“八五”国家规划教材(1991)，获得1995年国家优秀教材一等奖，1997年国家级教学成果二等奖，2006年入选“十一五”国家规划教材。
《并行计算机体系结构》教材，是以当代可扩放并行计算机系统结构为主题，着重论述了对称多处理机、大规模并行处理机、机群系统和分布共享存储多处理机系统的组成原理、结构特性、设计方法、性能分析，增加了相应系统的实例，强调了软件与硬件的结合。
《并行算法实践》教材，是以并行算法编程实现为主题，详细介绍了并行程序设计的有关内容、典型的非数值并行算法和数值并行算法的MPI编程实现过程，突出了算法设计与实现的结合。
2教学团队推动了系列课程的教学建设和改革
团队推动了教学改革，形成了完整的教改思路。将并行机体系结构、并行算法设计、并行数值计算和并行程序设计有机结合在一起，在国内形成一门新型“并行计算”课程。在保持本学科的经典完整内容的同时，力图反应本学科最新成果以及发展趋势。保持内容先进与新颖，广泛吸取国际多本同期同类教材中的优质内容。以计算机专业高年级本科生和研究生为主，兼顾信息科学、计算科学等相关专业的研究生，同时考虑国际交流的需要。并行计算课程于2003年入选首批国家精品课程。
团队在教改思路的指导下，加强了实验教学部分。实验教学强化学生“结构一算法一编程”一体化学习方法的意识，让学生充分理解对于求解一个给定问题的任何并行算法，都必须采用某种并行编程语言，最终运行在一台具体的并行计算机上。
团队在资源建设方面，针对不同的课程设置和专业要求，制作了中文和英文的两套电子讲稿， 并根据科学的最新发展不断加以补充和修订。对于教学中存在的一些难点和重点，采用了课件动画演示的方法来加强教学效果。此外，还针对部分内容进行了示范性教学录像，可在课堂教学中使用。
并行计算系列课程的推广需要加强网络教学。教学团队制作的网上教学环境是一个相对完整的自学环境，其中包括各章节的知识点、重点难点、例题讲解、习题实例和学习参考资料，并在网上提供讨论答疑。此外，为了更好地推广，在并行计算课程建设过程中，教学团队完成了示范教学录像(10学时)和全程教学录像(60学时上网。实验教学中的相关素材，如上机演示、示例程序等也都成为网上教学资源的一部分。
3教学团队创建了全国并行计算教育与培养基地
20世纪80年代中期到90年代中期，教学团队成员在全国各重点高校讲授并行算法，在全国各地推广并行算法研究。
20世纪90年代中期以来，随着国家高性能计算中心(合肥)的成立，教学团队逐渐成为了全国并行计算教育、培训I和人才培养基地。基地建设的成果先后获得2001年国家级教学成果二等奖，2001年安徽省教学成果一等奖。
教学团队在全国范围内开展课程推广和培训活动。2001年以来先后在贵州、成都、太原、大连、深圳等地举行课程讲习班，使得并行计算系列课程的教学成果逐步推广和辐射到全国各主要地区。
2006年中国科学技术大学与高等教育出版社联合成立了“高性能计算课程教学资源研发基地”。该基地以并行计算系列课程及其教材为建设目标，致力于在高性能计算的课程建设、教学内容、教学资源等方面进行合作开发。
4教学团队在全国推广并行计算课程
并行计算系列课程的形成，经过了长期的积累与建设，它的建设对我国该课程的教学起到示范与推动作用。为了将此成果尽早、尽快地推广并辐射到全国各地，我们采用了边建设、边推广的办法，在推广中不断地完善课程自身的建设。
我们非常重视与全国有关高校同行交流，虚心征求兄弟院校的意见和建议，取长补短以达到不断完善课程建设的目的。为此，我们曾分别在国内众多高校进行了有关并行算法方面的学术报告和并行计算方面的专题讲演，达到既传播教学成果又广泛吸纳各方意见的目的。
并行计算课程的建设，自始至终得到教育部高等学校计算机教学指导委员会和高等教育出版社的大力支持。近5年来，我们根据教育部统一安排，分别在全国各大地区举行过为期10天至1个月的“全国并行算法或并行计算”暑假教师(也包括研究生)课程讲习班，积极向全国推广并辐射并行计算教学成果。通过近几年的不断努力，并行计算系列课程的教学成果逐步推广和辐射到我国各主要地区。
5教学团队促进了学科建设和相关学科发展
多年来，我校并行计算的研究逐渐形成了并行算法“理论一设计一实现一应用”一套完整的学科体系，提出了并行计算“结构一算法一编程”一体化的研究方法。由于我们在并行计算方面有一支训练有素的研究队伍以及具有较扎实的理论基础与研究经验，所以能够连续不断地申请到国家自然科学基金(重点)，“863计划”(重点)和“973计划”以及“教育部博士点基金”等项目。并行计算的科研成果很好地促进了并行计算的教学建设。
同时，团队促进了并行计算学科和交叉学科的发展。通过教指委认证后各个高等学校都可开设该课程，完成了课程从少数研究型大学到多数普通院校的普及，为并行计算学科在国内的发展作出了贡献。并行计算的受益者除了计算机专业和计算数学专业的学生外，广大的计算应用型专业，如计算物理、计算化学等专业方向的学生，也从该系列课程中受益，促进了相关交叉学科的发展。
三、教学团队的进一步建设计划
教学团队的建设和发展是一个不断更新完善的过程，并行计算系列课程教学团队已经取得了一些成果，但在现有基础上还需要进一步加强相关建设，使得团队可以不断得到发展和提高。
1进一步加强基地建设
2006年中国科学技术大学与高等教育出版社联合成立了“高性能计算课程教学资源研发基地”我们将结合该基地的建设开发相关教学课件，提高教学质量，帮助学生更好地学习并行计算课程。
2适时修订《并行计算》系列教材
并行计算系列丛书中的《并行计算(第3版)》和《并行算法的设计与分析(第3版)》作为“十一五”国家规划入选教材，将在未来的三年内完成。目前课程教材的整体内容尚有些偏深，一般高校的普通计算机专业开始使用时，尚有一定的困难。针对目前习题数量偏少，习题质量有待提高的情况，在修订教材的同时将特别加强应用型例题和习题。在条件成熟的情况下，考虑编写并行计算系列教材的例题和习题选解。同时，增加更多的大型应用综合作业，以便于学生从“应用问题一设计算法一编程实现一机器调试运行”中了解实际应用问题求解的全过程。
3积极引进人才，进一步提高团队素质
在努力培养和建设已有教学团队的基础上，结合科大计算机系人才引进和教育部“111引智计划”的实施，聘请海外人员，定期和不定期举行并行计算的前沿与进展专题讲座。利用科大“全院办学，所系结合”的方针，邀请中科院计算所、软件所等我校兼职教授以短期、集中的方式讲授深层次的、带有科研背景的并行计算有关内容。同时，通过加强国际交流，提高团队在国际上的影响。
4进一步加强并行计算实验教学环节
并行计算系列课程是一门实践性很强的课程，除了系统的课堂理论学习外，还需要配有足够数量的实践内容，以巩固和加深学生对并行算法理论、设计技术、分析方法和具体实现等各个环节的整体理解。实践证明，这些实践环节是非常必要和重要的，它可以激发学生学习并行计算的积极性，缩小理论教学和实际应用能力之间的差距，引导学生进入一个思考和探索的世界，在这个世界里，他们是学习的主动参与者，而不再是被动的接受者。目前并行计算的实验部分的平台和实验内容还存在一定的局限，团队将在未来的建设中进一步完善。
双三角翼大迎角绕流的并行计算
本文在LU-SGS方法求解可压缩Navier-Stokes方程的串行程序基础上,发展了适合MPP系统类型的`并行计算机的并行算法程序,并针对双三角翼大迎角绕流问题,就不同的并行计算方法进行了对比研究,探讨了优化并行策略,提高计算效率和计算加速比等问题.
作 者：汪善武 杨国伟 周建军 庄礼贤 Wang Shanwu Yang Guowei Zhou Jianjun Zhuang Lixian 作者单位：中国科学技术大学力学和机械工程系,合肥,230026 刊 名：空气动力学学报 ISTIC EI PKU英文刊名：ACTA AERODYNAMICA SINICA 年，卷(期)：2000 18(2) 分类号：V211.3 关键词：并行算法 三角翼绕流 非定常流CUDA (Compute Unified Device Architecture) 模型是由英伟达 (NVIDIA) 公司推出的一种基于GPU通用计算的编程模型和计算体系。该架构不需要借助图像学API, 直接使用类C语言即可完成并行计算, 使得使用GPU处理图像中的复杂计算成为可能。
1 CUDA编程模型
CUDA将CPU串行处理和GPU并行处理完美的结合起来。一个完整的CUDA程序是由主机 (CPU) 程序和设备 (GPU) 程序共同组成, 主机程序主要是为设备程序的运行做前期准备工作, 主要包括数据初始化、数据拷贝、内核函数间数据交换等。而设备程序主要就是完成并行计算的任务。CUDA编程模型分为两个主要部分:CUDA软件架构和CUDA硬件架构。其中CUDA软件架构又包括了软件栈、通用编程模型和存储模型三个方面。下面将从上述内容对CUDA的编程模型进行介绍。
1.1 软件模型
根据NVIDIA的官方文档, CUDA的软件体系共分3个方面:CUDA设备驱动程序、CUDA运行时库和编程接口、CUDA官方函数库。其中, 设备驱动器是直接作用于GPU上的, 开发者可以通过CUDA运行时库和CUDA函数库中的函数调用来使用设备。CUDA编程模型可以根据不同的需求提供不同的API, 开发者可根据对GPU的控制程度来使用。并且为了很好的利用CUDA架构, CUDA还提供了一系列的辅助开发、调试的工具。
1.2 硬件模型
软件程序的运行是建立在硬件的基础上的, 而GPU之所以能够比CPU处理数据更加有效, 在于GPU中有更多的晶体结构可用于计算。而在CUDA的硬件架构中, 流处理器阵列是由多个线程处理器簇组成, 而每个TPC又是由多个流处理器组成的。每个流处理器拥有一套完整的逻辑处理单元, 就有一系列的功能, 如取值、编码、译码等。每个流处理器是由8个流处理单元和2组超级函数单元构成。
2 线程模型
在CUDA编程模型中是通过大量的并行线程来实现计算的, 因此CUDA架构下最小的执行单元线程 (thread) 。每个线程块中是由多个可以通信的线程组成, 每个线程和线程块都有唯一的标示ID, 则可以通过索引确切定位到每个线程。线程的索引和线程的ID是与线程块的维度所确定的, 一维线程索引和ID是相同的, 二维维度为 (m, n) 的线程块, 线程索引 (x, y) 所对应的线程ID为x+y*m;三维维度为 (m, n, k) 的线程块, 线程索引 (x, y, z) 所对应的线程ID为x+y*m+z*m*n。CUDA线程的开辟是根据所需解决问题的数据大小来确定的, 而每个线程块内的线程数由于其共享一个核心处理器的存储器资源, 则块内线程数量是有限制的, 这个可以通过NVIDIA给出的资料查询。一般为了使每个线程块的调度达到最优值, 每个块内的线程数一般设为16的倍数, 但不能超过限定值。
3 存储器模型
CUDA内部存储器的结构是由寄存器、全局存储器、共享内存、本地寄存器、常量内存和纹理内存组成。下面是对这6个存储器的介绍:
寄存器位于GPU晶体片中, 在各种CUDA存储结构中, 它的访问速度快, 因为它是线程所私有的, 不允许其他线程访问和使用。但由于GPU硬件的限制, 寄存器不是无限的, 每个线程块中的寄存器是事先分配好的。但如果内核函数中分配的寄存器数量超过了寄存器的总数, 编译器会默认的将数据转入设备端的本地内存中, 这样就会大大降低程序数据访问的效率。
全局寄存器也称之为线性寄存器, 占设备内存的DRAM的大部分空间, 在内核函数运行时, 所有的线程都可以读写其中的数据。正因如此, 它的访问速度较慢, 耗时较多, 线程访问全局寄存器一般都要花费几百个时间周期。全局寄存器一般在CPU中完成数据空间的开辟、数据的拷贝和传输、数据的释放等操作。
常量存储器位于显存中, 空间大小一般为64K, 是一段只读的地址空间, 由于其具有缓存并且无访问冲突的优势, 常常用于常数的访问。
本地存储器是位于编译器分配的全局存储中, 是归每个线程所私有的数据空间, 与全局存储器相同, 其在程序运行过程中不会缓存, 所以其访问速度也较慢。本地存储器一般用来存放内核函数所声明的变量。
共享存储器是可以被同一块中的所有线程访问的可读写存储器, 它的生存期就是块的生命期。在没有冲突的情况下, 访问共享存储器几乎与访问寄存器一样快, 是实现线程间通信的最好方法。在同一个块内, 所有的线程都能够读共享存储器中的数据, 相比于AMD的显卡来说, 共享存储器是NVIDIA显卡的一项特色。其和寄存器一样位于GPU的晶体芯片中, 所以其访问速度较之全局内存和本地内存来说, 其效率较高, 并且可以减少线程块中的线程通信的时间, 一般只有2个时间周期。但由于其空间较小, 一般每个SM有一个16K大小的共享寄存器, 并且其数据只能在一个线程块中共享。这就容易导致各线程块中的数据不同步, 容易引起数据混乱, 为保证数据在程序执行中的同步性, CUDA中使用_syncthreads () 函数来实现线程块的同步。
纹理存储器是GPU中专门用来渲染纹理的图像处理单元, 它是一块只读空间。在内核函数运行的过程中, 使用纹理寄存器首先需将数据与纹理绑定。纹理存储器与常数存储器一样具有缓存机制。纹理存储器相较于其它存储器有两大优势:一是纹理存储器中的数据可以反复使用, 避免了数据的重复读取, 提高了效率;二是可以拾取坐标对应位置附近领域内的像元数据, 该优势在对图像进行处理中, 可以提高局部性数据读取效率。
4 结语
21世纪人类面临的众多重要科技课题, 这些课题没有万亿次以上的计算能力是无法解决的。GPU与生俱来就有强大的计算能力, NVIDIA公司推出了CUDA架构使开发的难度大大降低, 程序员可以很容易地利用GPU这个计算工具进行并行程序的开发。现在GPU在非图形领域得到了广泛的应用, 基于GPU的通用计算研究也逐渐深入。
摘要：近年来, 图形处理器 (Graphic Process Unit, GPU) 的快速发展使得其逐步用于通用计算。在性能各异的并行计算平台中, 英伟达 (NVIDIA) 公司推出的计算统一设备架构 (Compute Unified Device Architecture, CUDA) 因为充分利用GPU (Graphic Processing Unit) 强大的计算能力实现了通用并行计算而受到研究者们的青睐。
关键词：图形处理器,CUDA,并行处理
参考文献
[1]胡杰.CPU-GPU异构平台计算模型的研究与应用[D].大连:大连理工大学, 2011.
[2]邹治海.CPU架构分析与功耗模型研究[D].上海:上海交通大学, 2011.
关键词：局域网,Matlab,并行计算,实验教学
在日常生活中遇到许多问题在求解的过程中都需要很大的计算量，如背包问题，邮递员问题等一系列NP问题。因此我们可以采用并行计算的方法来解决此类问题，并行计算教学已成为许多本科学校数学专业必修课程，为使并行计算的本科教学能够顺利实施，必须要有相应的实验教学环境[1]。
PC机群[2]是最容易实现的并行计算环境，Matlab是高校数学系学生常用的软件，大多高校数学系的学生都掌握Matlab的基本使用，因此本文考虑用Matlab搭建并行计算实验教学环境，其目的是服务于高校数学系并行计算教学和学习。本文通过实践给出并行计算实验教学环境的搭建过程，先搭建局域网，然后通过局域网搭建多台PC机并行计算环境，此方案适合并行计算实验教学和集中上机实习。
1 基于多台PC机实验室并行环境搭建
1.1 基本配置及原理介绍
在本文搭建的并行环境中，涉及的硬件有四台PC机、路由器、双绞线。操作系统为Windows XP。一台PC机为主机，其余三台客服机。
在Matlab并行机群中，每台参与计算的计算机中都需要启动一个叫Matlab Distributed Computing Engine(MDCE)的服务[3]通过Matlab R2009b构建的PC机群并行环境如图1。
1.2 实验室中Matlab并行计算机环境配置
先通过路由器将四台PC机连成局域网，然后通过Matlab在局域网搭建PC机群并行系统。在Matalb 2009b测试局域网及相关服务的连通性及配置PC机群。最后配置并行环境，Matalb的Parall菜单中Manager Configuration新建Job Manager配置，在Scheduler输入Job Manager名和所从属主机名，所选Job Manager必须是Admin center中已创建的，在jobs菜单下，输入job计划使用Worker的最大最小数目，设置完成之后，全部测试通过如图2，在窗口下放所有项显示为“passed”。
2 并行计算实例
首先通过J o b M a n a g e r传输代码：s e t(j o b,'FileDependencies',{'fun1.m','fun2.m','main.m'})其次设置文件关联，让Worker node访问网络文件和本地文件set(job,'PathDependencies',{'ipsharedir','/mnt/'})接着使用Configurations Manager设置.在matlab的菜单栏上选择Parallel->Manage Configurations...,启动Configurations Manager，设置jobmanager的属性(Properties...)
以简单实例测试PC机群并行计算环境的可行性，例求2+4,5+8和1+7的和，在PC机群并行计算环境2+4,5+8和1+7可分别由三台电脑独立完成，再由服务器将各电脑求得的值汇总后再计算如图3。具体操作如下：
⑴资源查找,创建对象:jm=findResource('scheduler','t ype','jobmanager','name','myjobmanager',…‘LookupURL’,‘node5’);需要修改的是有下划线参数,第一个即前面jobmanager的名字,第二个即本地主机的名字;
⑵创建工作,并将该工作所需的数据、程序发到各个worker处.job1=create Job(jm);%工作名为job1.
set(job1,‘FileDependencies’{‘bb1.m’,‘bb2.m’,‘bb3.m’,…'W_FDJ1.mat','W_FDJ2.mat','W_FDJ3.mat'})注:set()函数就是将该工作所需的数据、程序发到各个worker处,本程序不需要用到;
⑶创建任务c r e at eTa s k(j o b1,@s u m,1,{2,4});createTask(job1,@sum,1,{5,8});createTask(job1,@sum,1,{1,7}).为job1创建了3个任务,@sum代表函数头,1代表返回参数个数,此处为1个,{2,4}代表函数sum的输入参数。
3 结束语
本文针对以Matlab软件为基础的并行环境的构建.给出了构建并行环境的搭建过程，并进行了优劣对比。对于本科院校开设《并行算法设计》课程教学有所帮助，在计算机实验室内搭建并行系统，有利于对并行算法的验证以及对并行算法进行研究。
参考文献
[1]百度百科.并行计算简介[DB/OL].http://baike.baidu.com/view/1666.htm,2012-3.
[2]百度百科.Windows环境下的Matlab并行机群计算配置及应用[DB/OL].http://wenku.baidu.com/view/f042ee4ecf84b9d528ea7a5a.html.
遥感技术的发展,伴随着遥感图像的分辨率不断提高,导致每一景图像的数据量大增,计算量也相应增加。根据图像数据本身存储的规律性以及相关性特点,其算法也具有一致性、邻域性、行顺序性的特点,自然就为图像并行计算创造了良好的条件。主要体现在:几何图形的并行性、相邻并行性、像素位的并行性和操作的并行性[1]。并行处理总的来说可以分为两类:数据并行性和任务并行。目前对于任务分配的研究取得了一定的成果,提出很多算法模型以及各种任务优先图。如启发式任务分配算法[2]多核处理器与网络处理器任务分配算法的研究等[3]。但专门针对集群环境图像处理过程的图像融合系统中任务分配调度研究相对较少。虽然图像融合的算法和应用取得了一定的进步,但快速有效地提高计算的效率仍是一个具有挑战性的研究课题。图像融合作为图像处理和模式识别过程的重要阶段,涉及到几个问题,其中任务并行对图像处理难度较大,因为同一任务的算法内部之间数据的相关性较大,不易分解,鉴于此我们提出采用数据并行处理的思路,吸取动态负载均衡的任务分配思想提出数据并行计算技术的算法模型。
1 集群环境下的图像融合并行计算
1.1 图像预处理
图像融合的目的就是将多传感器的个体优势转化成融合后的综合优势,更好地为判读解译过程提供服务。将其并行化是提高融合效率、满足图像的快速甚至实时处理要求的有效途径,因此对图像实施诸如增强、消畸变、配准、去噪等预处理,是保证图像融合的关键。本文提到的预处理是对预处理图像进行数据“区域”的划分,这里所提及的“区域”是指一个相互连通的、具有一致性属性的像素集。因此必须先对图像进行灰度处理,然后依据图像的灰度值对图像进行划分,以得到目标对象区域最小边界,最后统计出这些含有目标对象最小多边形的个数,以便将数据分配给集群机进行计算。
图像存储的规律性,是图像以矩阵进行存储与计算的基础,因此改善矩阵计算的并行性是提高图像处理性能的一个重要手段。本文采用四叉树结构对图像进行区块划分与存储。其基本思想是:首先获取待划分区块的四等分线,对每一等份继续按上述方法进行划分,一直等分到子象限上仅为目标对象区域最小长方形区域为止,然后舍弃不含目标对象已划分的区块,统计出含有目标区块的总数。这样就大大减少了对不含目标对象区域的计算时间,区块划分与编码方法如图1所示,所得块状结构用四叉树结构进行组织存储,即把2n×2n像元组成的阵列当作树的节点,树的高度为n级(最多为n级)。每个节点有分别代表北西(NW)、北东(NE)、南西(SW)、南东(SE)四个象限的四个分支。存储树结构如图2所示。
1.2 集群体系数据划分与并行计算
由并行模式的理论可知,分解方法有功能分解和数据分解两种。功能分解指的是将整个执行过程按一定的分解粒度对执行过程进行分解;数据分解指将待融合的图像先进行划分以获得子图,然后再在子图上施加适当的计算。通常对图像分解采用规则的分解,如条状划分或多维划分。虽然子域理论可以小到只有一个像素,而条状划分最小粒度是一行。与文献[6]提到的影像数据划分策略不同,同时也与文献[7]提到的基于小波包串行融合算法中的数据划分策略不同,其思想只是依据图像的区块大小进行划分,如图3所示。在此我们按照上一节介绍的四叉树结构的划分与存储思想,先把一幅图像进行图像的预处理,划分区块获得目标区域的数量,这些数量也就是我们进行并行计算的子图数量。我们仅关注含有目标的区块,因为就目标识别而言,所要计算的目标对象相对较少。如图4所示。依据集群体系结构对处理器节点层级分配策略,采用集中式处理结构,可以自适应地分配处理器节点层级与子图的数量,通过监测各处理器运行状态及预计执行时间,使用任务队列的方式适时地调配待处理的子图数据到处理器节点。
1.2.1 集群体系数据分配策略
分布式集群体系结构四叉树数据处理(以下简称为任务)分配模型可以考虑两方面内容。其一就是任务粒度的划分;其二就是各处理节点的任务分配。由于数据的划分已经在数据预处理阶段完成,下面主要讨论节点的任务分配问题。
如图5所示,首先将系统中所有的网络节点进行分级,初始时分级方法对应四叉树结构,主控节点对应根节点,依次类推。其中主控节点负责向各二级节点分配任务,并收集各二级节点的负载信息;二级节点在收到主控节点分配的任务之后,对三级节点进行调度,安排三级节点进行相应的工作;二级节点同时将自己的负载情况向主控节点汇报,主控节点根据提供的消息在二级节点之间进行负载平衡;三级节点在收到二级节点的命令之后,开始执行相应的任务,并将执行结果返还给二级节点。
考虑到二级计算节点所起的桥梁作用,其它除主控根与树叶位置外的节点算法也类同,因此有必要重点讨论一下二级计算节点的具体算法,描述如图6所示。
在进行具体的算法实现中,采用开源的p RPL函数库辅助实现四叉树节点信息的获取及调度,算法的核心代码如下:
1.2.2 集群体系时间成本计算
传统的单节点图像融合计算就是根据多光谱与高光谱图像的信息对整幅图像各像素点顺序扫描计算,因此融合时间相对较长。然而,集群体系图像融合并行计算的时间总开销主要包括图像分割时间、传输时间、节点图像融合时间和图像再分割时间、返回结果传输时间以及图像拼接规整时间等组成。由于我们摒弃了绝大部分的非目标区域的计算时间,同时采用并行计算与任务动态调度的思想,总计算时间与效率均有改善。具体计算公式为:
其中Max[Tn1,Tn2,Tn3,Tn4]表示按四叉树结构按单任务划分后对下级节点再分割与计算的最长时间,因此这个计算式是一个递归计算过程,取决于递归划分的粒度与计算节点的个数。每划分一次,其计算时间都将有一定的减少,划分后即有:
时间成本计算代码如下:
1.3 图像融合的并行计算
本文采用标准的图像融合方法,通常按如下步骤进行:
1)将原始图像增强、消畸变、校准、去噪;
2)对多光谱图像进行RGB到IHS的变换;
3)对真彩色图像和IHS多光谱图像的亮度成分进行直方图匹配。
首先,用真彩色图像的亮度成分作为融合图像的亮度成分,然后做逆变换以获得融合的RGB图像。
标准融合方法的结果依赖于采用的IHS系统,最常用的亮度变换公式为:
其次,被融合的两幅图像的亮度成分应当在融合之前进行匹配。为校准亮度,要计算每幅图像的亮度的均值和标准差,并用于调整一幅图像相对于另一幅参考图像的亮度成分。其表达式为:
其中I表示原来的亮度值;I'表示校准后的亮度值;σ1,m1分别是第一幅图像的亮度的均值和标准差,而σ2,m2分别是第二幅图像的亮度的均值和标准差。校准了亮度后,两幅图像可用下式进行逆变换到RGB平面:
具体的功能实现过程中,借助IDL函数库实现栅格图像的融合处理,提高并行运算的效率。主要代码如下:
1.4 数据的收集规整
对上述除主控核外的各级核计算结果,主控核负责按划分块即子图的索引ID及其相应的位置信息逐块进行无缝连接,形成一幅完整的融合图像,以便进一步的计算处理。至此,图像融合的整个过程完毕。
2 实验结果与性能分析
基于以上遥感图像的集群并行计算模型与四叉树结构分块策略,我们选取大小为200M左右的高光谱与多光谱遥感影像为融合数据,其中高光谱影像分辨率为14253×14312,数据大小为196Mb,多光谱影像分辨率为7129×7151,数据大小为196Mb,并将图像分别划分为4,16,64块,以单机、集群PC机的个数为1,4,16,64进行了相关测试,测试结果为图像融合进行10次所得的平均值。
测试节点计算环境为:集群系统中每个节点的CPU都为酷睿2代,内存4GB,实验中总共用到了64个节点,整个集群系统通过速度为1Gb/s的以太网相连,系统通过图像划分、融合、合成等步骤,同比单机图像融合计算的效率有所提高。测试结果见表1。
从表1可知,如果采用单机对于一个遥感图片处理,计算时间的代价将大于没有进行集群分割与并行策略。在数据分块数少于计算节点数的情况下,所花费的时间数与等数据块花费的时间相同。对单节点而言,随着分块数的增加,花费的时间也相应增加。另外,随着分块数与节点数的增加,总时间花费减少。
3 结语
基于四叉树结构数据划分策略在海洋遥感目标识别中,可以减少非目标区域的计算时间;整个算法的执行时间不仅跟图像数据划分有关,而且与计算节点数目有关;采用动态任务分配与调度算法也能减少并行运算时间。由于本算法主要关注的是对图像目标区域的划分策略与并行效率,对处理结果的收集与整理考虑欠缺,因此在融合的精度方面将在下一步的研究中加以改进。
摘要：集群体系下的大规模并行计算,是高性能计算的基础。遥感图像处理效率的提高,有赖于并行计算技术的应用。在分析已有网格计算环境下分布式任务分配方法的基础上,针对海上遥感图像目标物数量相对较少的特点,首先利用四叉树结构理念对目标区域进行划分,同时采用动态负载均衡的任务分配策略与并行计算思想,提出对目标区域图像进行融合处理的集群体系任务分配算法处理模型。通过对比验证,表明该集群体系下算法模型能有效地提高图像融合的速度。
关键词：集群计算,并行计算,四叉树结构,图像融合
参考文献
[1]程英蕾.多源遥感图像融合方法研究[D].西北工业大学,2006.
[2]刘轶,等.一种面向多核处理器并行系统的启发式任务分配算法[J].计算机研究与发展,2009,46(6):1058-1064.
[3]刘轶,等.多核处理器大规模并行系统中的任务分配问题及算法[J].小型微型计算机系统,2008,29(5).
[4]Liu Zhen,Rhonda R.Optimal parallel processing of random task graphs[J].Journal of Scheduling,2001,3(4):139-156.
[5]沈占锋,等.高分辨率遥感影像并行处理数据分配策略研究[J].哈尔滨工业大学学报,2006,38(11).
[6]程英蕾,等.一种多传感器图像并行融合新方法[J].空军工程大学学报:自然科学版,2006,7(6).
[7]刘振英,等.一个有效的动态负载平衡算法[J].软件学报,2001,12(4):563-569.
[8]翟亮,等.一种新型的遥感影像压缩质量评价指标[J].武汉大学学报:信息科学版,2007,32(10).
【天津大学并行计算】推荐阅读：
天津大学章程06-21
天津大学考研真题06-02
天津大学招生方向06-24
天津职业大学机械设计07-28
天津城建大学招生网05-23
天津理工大学android06-10
天津工业大学机械实习07-24
天津大学博士生导师06-11
天津商业大学法学专业怎么样06-26
《天津财经大学珠江学院学生毕业实习报告》06-29
