告别免费午餐拥抱多核时代—SuperMap空间分析并行计算实践Written by:Objects 2013-3-12 11:20:00SuperMap空间分析并行计算实践信息技术（InformationTechnologies，简称IT）领域，绝大多数定律都会随着技术的进步被人们淡忘，但有一些却可以经受住时间的考验，对信息技术发展带来持久而深远的影响，“摩尔定律”便是其中典型代表。
“摩尔定律”支配下的信息技术，64位系统和多核计算日益普及，如何充分利用64位系统和多核环境下的计算资源成为系统设计和开发人员必须面对的问题。
地理信息系统（Geographic InformationSystem，简称GIS）中的空间分析服务具有算法逻辑复杂、数据规模庞大的特点，属于一种计算密集型服务。
针对该特点，我们将并行计算技术引入传统空间分析计算过程，充分利用64位大内存和多核计算资源，大幅提升空间分析计算性能。
一、摩尔定律下的免费午餐摩尔定律是由英特尔创始人之一戈登·摩尔（Gordon Moore）提出。
其内容为：当价格不变时，集成电路上可容纳的电子元件数目，约每隔24个月（现在普遍流行的说法是每隔18个月）便会增加一倍，性能也将提升一倍。
换言之，相同性能的芯片产品，每隔18个月价钱就会降低一半。
该定律自1965年提出以来，始终较好的预测了半导体产业的发展趋势，又由于半导体产业的巨大影响力，该定律辐射到包括微处理器、移动电话、个人电脑、互联网等在内的众多IT领域。
几十年来，包括处理器速度、内存容量、网络传播速度等关键IT指标的发展大都符合摩尔定律的描述。
我们有理由认为，摩尔定律在一定程度上揭示与展现了信息技术令人惊讶的进步速度。
诞生于1946年的世界上第一台电子计算机，其计算速度是每秒5000次加减法运算，而今天个人电脑的计算速度是每秒500亿次浮点运算。
三十五年前的英特尔8086处理器仅有三万个晶体管，而今天一个基于Nehalem架构的英特尔酷睿i7处理器集成了7.74亿个晶体管。
图1 摩尔定律曲线（, 2012）伴随着硬件技术的飞速发展，操作系统和各种应用软件无偿享用着硬件提升带来的“免费午餐”。
由于处理器生产厂商致力于摩尔定律描述下的时钟频率提升，单线程的应用程序无需进行任何修改就可以在新的处理器上获得更高的性能，而功能更为强大，计算资源需求更多的操作系统和应用软件又刺激着消费者进行硬件升级，从而构成了个人电脑工业的生态链。
另一方面，Google（谷歌）公司的前CEO埃里克·施密特在一次采访中指出，如果你反过来看摩尔定律，一个IT公司如果今天和十八个月前卖掉同样多的、同样的产品，它的营业额就要降低一半。
IT界把它称为反摩尔定律（Reverse Moore's Law）。
这个带着悲情色彩的反摩尔定律使得IT行业不可能像传统行业那样只追求量变，而必须不断寻找革命性的创造发明，不断追赶技术的前进脚步。
那些技术发展赶不上摩尔定律要求的公司，只能被市场无情的淘汰，任何一个大公司都要保持足够的警惕和研发投入，而任何一个小公司都有可能遇到让自己成长为下一个IT巨人的技术变革，这是一个最好的时代，也是一个最坏的时代。
二、多核时代的计算要求在单核CPU时代，处理器生产厂商提升CPU运算能力的主要途径是提高主频。
作为CPU的主要性能指标，主频标志着每单位时间内CPU 能够执行运算指令的数量。
实际上，在单核CPU时代，处理器已经实现了多线程运算，通过在逻辑上模拟出多个CPU内核，以实现多任务调度和并发处理。
然而，这些处理过程始终由单个CPU以线程切换方式完成，运算负载由单个CPU承担。
而多核CPU则在真正意义上实现了内核级别并行，与传统的单核CPU相比，多核CPU带来了更强的并行处理能力和更高的计算密度，同时大大减少了散热和功耗。
而多核时代的到来这也迫使应用系统告别“免费午餐”，使用多线程（或多进程）方式来充分利用多核环境下的计算资源。
图2 256核服务器的CPU任务管理器（George Chu, 2010）当前，双核和四核的个人电脑已经非常普及，而服务器的内核数量更是被不断刷新，但另一方面，由于目前针对多核开发和优化的应用程序还相对较少，使得用户无法切身感受多核计算环境下的性能提升。
根本原因是并行程序的开发难度非常之大，程序设计与开发人员需要面对包括任务并行化、内存管理与使用、线程竞争与死锁、多线程程序调试等诸多技术问题。
为了解决这些问题，众多并行计算模型和框架应运而生，粉墨登场。
三、跨平台的并行框架由于SuperMap软件产品需要具有跨平台的特性，因此我们在进行并行计算框架的选择时，需要考虑其不同平台间的支持能力。
当前业界应用较为广泛的跨平台并行计算框架，主要包括面向线程并行的OpenMP 框架和TBB框架，面向进程并行的MPI框架，以及OpenMP与MPI的混合模式（Hybrid）。
OpenMP（Open Multiprocessing）：是一个支持多种平台的共享内存并行计算API，支持平台包括Solaris、AIX、HP-UX、GNU/Linux、Mac OS X和Windows，支持语言包括C、C++和Fortran。
它由一组编译器指令、API和环境变量构成，适合于将已有代码进行并行化改进。
图3 OpenMP并行计算示意图（，2012）TBB（Intel Threading Building Blocks）：是一个由英特尔公司开发的C++模板库，主要目的是使得软件开发者更好的利用多核处理器。
该库为开发者提供了一些线程安全的容器和算法，使得开发者无需过多关注系统线程的创建、同步、销毁等操作，将精力集中于业务逻辑的并行化，可以与OpenMP互为补充。
MPI（Message Passing Interface）：是一个有着广泛使用基础以及专业审查委员会管理的并行计算标准，其设计主要面向大规模机器和群集系统的并行计算，其具体实现包括OpenMPI、MPICH和LAM-MPI等。
Hybrid：即混合并行计算模式，主要是指在单机环境中使用OpenMP 进行线程级别的并行，并同时在由单机组成的群集环境中通过MPI进行任务间的消息传递和并行计算，使用难度较高。
表1 并行计算框架对比比较项目OpenMP TBB MPI并行粒度线程线程进程不支持支持不支持内存分配总体来说，并没有哪种并行计算框架可以适用于各种应用开发，较为合理的方案是根据应用程序特点选择适合自身的技术框架。
当你需要将已有程序进行并行化改进，而且希望快速看到改进效果时，OpenMP 是一个较理想的选择。
当你希望从零开始，完成一个并行化程序的开发时，可能需要更多的关注TBB和MPI。
而当你希望应用程序既实现单机线程级别的并行，又可以在多机群集环境中发挥并行计算优势时，就需要使用较为复杂的混合模式进行设计和开发。
四、并行计算下的空间分析GIS空间数据随着采集、传输、处理技术的进步，其规模不断膨胀，导致传统串行空间分析方法面临巨大压力。
而并行计算技术凭借其对于多核计算资源的充分利用，以及可扩展的计算能力为海量空间数据的分析提供了一种解决方案。
本文中，我们主要以GIS空间分析中的水文分析为代表，分享SuperMap水文分析模块在并行计算方面的相关研究和实践工作。
水文分析是水文科学、地理信息科学与计算机科学的交叉结合产物，主要利用DEM栅格数据构建水系模型，利用水系模型进行水流方向、累积汇水量、流域、河网等水文要素的计算与提取，实现DEM表面水流过程的模拟和重现。
可广泛应用于农林业、区域规划、灾害预测等诸多领域，是GIS空间分析中的重要组成部分。
由于水文分析是一个完整的工作流程与分析体系，因此涉及较多分析方法，主要包括：填充伪洼地、计算流向、计算累积汇水量、划分流域（包括计算流域盆地、提取汇水点和流域分割）、提取水系网络（包括提取栅格水系、河流分析、连接水系和提取矢量水系）图4 水文分析流程图（SuperMap，2012）由于水文分析模块涉及分析功能较多，而应用最为广泛的是基于DEM提取矢量水系，因此我们针对该流程进行并行计算实践，主要涉及填充伪洼地、计算流向、计算累积汇水量、计算流域盆地和水系矢量化功能。
我们主要使用OpenMP并行计算框架，并根据具体算法使用非连续内存管理、线程池、线程任务分配等技术手段，进行水文分析相关功能的并行计算改进，以期达到充分利用多核计算资源，提升水文分析性能的目的。
为了验证改进算法的有效性，我们选取了三组不同规模的DEM数据进行测试和分析。
表2 DEM数据列表数据编号行数目列数目数据量A 3601 3601 35 MBC 18001 32401 1.5 GB为了保证测试效果，我们使用Dell ® PowerEdge ®服务器进行测试，其处理器为2个英特尔®至强®八核处理器，单核主频为2.0 GHz，内存为32 GB，操作系统为64位Red Hat® Enterprise Linux Server。
首先使用双线程并行与原串行算法进行比较，测试结果如表3所示。
表3 双线程并行计算性能统计功能点数据A 数据B 数据C 串行并行串行并行串行并行加速比 1.62 1.46 1.52时间单位：秒图5 数据C双线程并行测试结果从测试结果中可以看出，双线程并行算法相对于传统串行算法有较为明显的性能提升。
由于各功能实现算法不同，内部并行化所使用的技术手段也存在差异，因此各算法性能提升幅度不同。
但从总时间来看，三组数据的加速比分别达到了1.62、1.46和1.52，即水文分析各功能均可以通过并行计算技术大幅提升原算法性能。
为了进一步测试不同线程数目下并行算法的性能提升幅度，我们选择了填充伪洼地和流向分析两个功能，分别使用不同的线程数目进行分析性能测试。
图6 数据C填充伪洼地功能测试结果图7 数据C流向分析功能测试结果从图6和图7可以看出，改进后的并行算法性能随着线程数目的增加而提升，但由于算法内部无法实现完全的并行化，在线程数目增大到8时，算法性能提升幅度减小，算法时间趋于平稳。
流向分析功能由于算法结构较适宜进行并行化处理，计算任务可以较均匀的分配到多个线程上，因此分析性能的提升与线程数目的增加表现出较好的一致性。
尽管“摩尔定律”支配下的信息技术仍处于飞速发展当中，但以64位技术和多核计算平台为代表的发展趋势迫使应用系统开发进行重新思考。
如何行之有效的进行并行程序的设计与开发已成为衡量一个IT公司能否充分利用计算资源的重要指标。
空间分析是GIS的灵魂，而SuperMap空间分析研发团队始终紧跟技术发展脚步，优化空间分析算法，在并行计算领域进行了多项卓有成效的研究和改进。
