文摘

著名的全局优化SCE-UA方法,已广泛应用于环境领域的模型参数校准,是一种有效的和健壮的方法。然而,SCE-UA方法具有很高的计算负载禁止SCE-UA高维复杂问题中的应用。近年来,计算机的硬件,如多核cpu和许多核心gpu,显著提高。这些更强大的新硬件和软件生态系统提供了一个机会来加速SCE-UA方法。在本文中,我们提出了两个平行SCE-UA方法和实现他们在英特尔多核CPU和NVIDIA GPU许多核心的OpenMP CUDA Fortran,分别。摘要Griewank基准函数采用测试和比较串行和并行SCE-UA的表演方法。根据比较的结果,一些有用的建议给出了指导如何正确使用平行SCE-UA方法。

1。介绍

有很多领域的智能优化算法的参数优化的环境模型,如遗传算法(GA) [1)和粒子群优化(PSO) (2,3]。在这些算法中,慢吞吞地复杂的进化方法开发了亚利桑那大学(SCE-UA)被认为是一个有效的和健壮的校准环境模型的全局优化技术4- - - - - -9]。然而,对于高维度问题,复杂目标函数响应面,和高目标函数计算负载,resource-demanding和耗时。这个缺点唤起需要高效的加速度SCE-UA方法。SCE-UA方法本质上是平行的,应该加速算法层面上。此外,并行算法需要强大的并行计算硬件上实现。随着并行计算技术的发展,最好的方法是利用异构计算系统,它是由多核的中央处理单元(cpu)和许多核心图形处理单元(gpu)。然而,在之前的文献中,该算法并行化水平分析和基于异构并行计算系统SCE-UA方法很少。

并行计算已经越来越流行了几十年的一种或另一种形式。在早期一般都局限于从业者获得大型和昂贵的机器。今天,情况有很大的不同。几乎所有消费者的桌面和笔记本电脑与多核cpu。多核CPU的硬件系统是建立在一组处理器访问一个常见的内存。这种架构被公认为共享内存系统。通过将几个核心芯片,多核处理器提供一种提高微处理器的性能。在多核处理器的编程模型,并行实现通过创建“线程”代表单独的任务由不同的CPU核。与多核cpu,几个现有的或新的编程模型和环境可以帮助用户(10]。例如,OpenMP Pthread, Cilk [11),甚至MATLAB可以被视为工具,帮助用户实现程序在多核cpu上。那些工具,OpenMP是采用并行化的SCE-UA方法在多核CPU系统由于其简单性和良好的效率。

许多核心GPU和多核CPU是两种完全不同的硬件系统。GPU是一种高度并行,多线程,许多核心处理器与巨大的计算能力和内存带宽很高,说明了数据1(一)和1 (b)(12,13]。NVIDIA CUDA介绍(统一计算设备架构),通用并行计算平台和编程模型,利用并行计算引擎的NVIDIA gpu来解决复杂的计算问题。CUDA指导程序员的问题分割成粗子问题可以解决独立并行块的线程,每个子问题成细块,可以解决合作中的所有线程并行块(13]。因此,我们采用CUDA Fortran的工具SCE-UA方法在许多核心NVIDIA GPU的并行系统。

本文的目标是以下。()罕见的先前的文献是关于SCE-UA并行化和加速度的方法。我们分析的哪一部分SCE-UA方法可以并行。我们重新设计,加速了SCE-UA方法的算法水平和方法非常适合于多核CPU和GPU许多核心。()多核cpu和许多核心gpu尚未申请SCE-UA方法的并行化和加速度。我们在这两种硬件实现并行SCE-UA系统利用OpenMP和CUDA Fortran。(摘要)Griewank基准函数测试和比较串行和并行SCE-UA的表演方法。根据比较的结果,给出一些有用的建议来指导如何正确使用平行SCE-UA方法。

2。方法

2.1。串行SCE-UA方法(Serial-SCE-UA)

SCE-UA方法是专门设计来处理遇到的特点在环境模型校准。该方法是基于合成四个概念:()结合确定性和概率方法;()系统的进化点生成参数空间的“复杂”,全球改善的方向;()竞争进化;()复杂的洗牌。这些元素使SCE-UA方法有效的合成和健壮,并灵活高效。详细介绍SCE-UA算法的基本理论可以发现在段的论文5,14]。段提供了MATLAB和Fortran 77 SCE-UA代码在他的官方网站。这两个版本在单核CPU串行代码和实现。他们可以被视为标准SCE-UA代码。摘要串行SCE-UA CPU修改代码段的MATLAB版本和Fortran 90年实现。这个连环SCE-UA CPU代码利用性能比较的基线。

2.2。多核cpu并行SCE-UA方法(OMP-SCE-UA)和许多核心gpu (CUDA-SCE-UA)

2.2.1。总体描述

在这项研究中,我们提出了一个并行SCE-UA方法,实现多核CPU的OpenMP和许多核心CUDA GPU的Fortran,分别。SCE-UA方法本质上是并行的,应重新设计来实现并行化。根据SCE-UA算法的计算流程,以下部分SCE-UA方法是并行的:(初始化的复合物,)复合物的演化,()随机数生成,()复合物的排序和重新排列。并行SCE-UA方法的流程图如图2。

2.2.2。平行的初始化复合物

复合物的进化之前,SCE-UA方法随机产生一组初始点构成初始复合物,每个点代表一个潜在的解决方案问题。生成步骤包括生成初始点和目标函数的计算每个点的价值。代的初始点可以并行,需要并行随机数生成器将部分中描述2.2。4。计算目标函数值为每一个初始点无关其他点,也可以并行。假设我们需要生成《不扩散核武器条约》初始点及其对应的目标函数值,我们创建《不扩散核武器条约》线程的CPU或GPU。在每个线程,我们计算的目标函数值对应的随机生成的点。通过使用多核CPU和GPU许多核心,《不扩散核武器条约》线程可以并行执行获得目标函数的值。

2.2.3。平行进化的复合物

复合物改善目标函数值的进化演变总会在复合物对全球最佳。复杂的进化的过程本质上是平行的,应该并行。对于每一个复杂的进化循环,我们创建总会在线程来表示总会在复合物和发展这些并行线程CPU或GPU实现平行进化。停止准则是满意时,复杂的进化是停了下来。在每一个复杂的进化循环,对于每个复杂,我们执行CCE(复杂的竞争演化)和点序列重新排列nspl步骤。CCE包含三个典型操作模仿下坡的遗传算法和单纯形算法,其中包括单纯形选择(选择),最坏点反射(交叉),和反射失败点随机再生(突变)。在突变步骤中,我们需要一个并行随机数生成器部分中描述2.2。4。点序列重新排列利用快速排序算法排序的进化点增加目标函数值和重新点序列根据目标函数值。之后,该算法准备下一轮CCE操作。

2.2.4。并行随机数生成

在初始化和复合物的进化,我们需要为每个线程生成均匀分布随机数。由于初始化和演化过程平行,随机数生成过程应该并行地运行。我们设计以下并行随机数生成方法:(1)对于每个线程,我们生成一个随机数序列,分别为(15- - - - - -17]。这种方法的承诺,每个线程的生成过程无关其他线程和担保所生成的随机数序列的高质量。(2)为了避免不同的随机数序列之间的相关性,获得更好的随机特性,我们采用不同的随机生成的种子每个线程和利用梅森素数的旋风随机数发生器而不是广泛使用线性同余发生器(18,19]。对于每个线程,分别生成随机种子采用和梅森素数的捻线机满足随机数生成器生成的随机数序列对应的线程。

2.2.5。复合物的并行排序和重新排列

初始化或洗牌进化循环后,最初的或进化的复合物应该在增加目标函数值排序和重新安排根据其对应的目标函数值。因为排序和重排过程本质上是平行的,我们应该并行化这些过程通过使用基数并行排序方法(20.,21)和并行排列方法。并行排序和重新安排也很多核心的多核CPU和GPU上实现。

2.3。串行和并行SCE-UA的实验研究

2.3.1。Griewank基准函数

串行和并行SCE-UA方法的性能比较是基于Griewank基准函数。Griewank全局优化问题是一个多通道最小化问题定义如下: 在这里,(即代表数量的维度。决策变量的数量)为。的全球最佳Griewank问题为为。作为一个简单的例子,演示了在图二维Griewank函数3。Griewank问题是足够复杂测试的全球房地产SCE-UA和尺寸可以改变测试SCE-UA的性能。因此,我们采用它作为基准函数在这个研究。

2.3.2。设置在这项研究中所用的硬件和软件

(1)在本研究中使用的硬件。在这项研究中,我们利用英特尔酷睿i7 - 4710总部与超线程CPU(4个CPU核和8个线程)和NVIDIA Geforce 850 GTX公司(DDR3版)(见图4)。我们可以看到从图4i7 - 4710 CPU总部已经8逻辑CPU核和GTX 850 GPU有640 CUDA GPU核心,这意味着CPU和GPU可以充分利用其计算能力通过使用并行8和640个线程,分别。

(2)本研究软件设置。SCE-UA方法有几个算法参数控制算法的收敛行为。他们是maxn优化之前,最大数量的目标函数试验允许终止;kstop,洗牌的循环中,目标函数必须改进指定的百分比pcento否则优化将终止;pcento百分率,目标函数必须改变指定数量的洗牌循环kstop否则优化终止;锐气、最小参数空间允许优化之前终止。为了公平的比较,我们设置参数如下:maxn= +∞;kstop= 5;pcento= 0.1;锐气= 0.000001。

为了分析串行和并行SCE-UA算法的性能,我们需要调整设置串行和并行算法来测试该算法的执行。这些设置是nopt决策变量的数量;总会在,数量的情结;nobj、循环数用于测试的目标函数计算开销(每个循环包含四个浮点算术运算,即。,包括一个加法,减法,乘法,一个部门。更大的nobj对应于更高的计算开销)。有一件事必须为了公平的比较,指出在GPU内存分配的时间消耗CPU和GPU之间的转移,从GPU回收,也被认为是在这个研究。单中的所有SCE-UA方法实现浮点精度。

3所示。结果与讨论

3.1。基于总执行时间的性能比较

在本节中,我们测试串行和并行SCE-UA的表演方法基于总执行时间(以秒为单位)。为了公平的比较,我们设置了nobj这些比较= 1000000。我们调整nopt和总会在对算法进行测试。

3.1.1。Serial-SCE-UA

总执行时间的连环SCE-UA显示在图5和表1。我们可以看到,越来越多的nopt总执行时间增加。至于增加的总会在,执行时间从43.95到46559.85年代比例不等。让nopt= 30为例(粗体行表1);的总会在从4到1024年增加2的倍数。我们可以观察到总的执行时间从130.04秒增加到28609.81年代大约同样多的两个。这是因为串行版本只使用一个CPU核心;的增加总会在当然,总执行时间增加的比例相同。为总会在< 16日执行时间不翻了一倍。这主要是因为更少的计算开销;使用的CPU资源的线程调度相对高于计算。线程的调度成本相对更多的时间使执行时间不翻了一倍。

3.1.2。OMP-SCE-UA

总执行时间的OpenMP SCE-UA显示在图6和表2。我们可以看到,越来越多的nopt总执行时间增加。至于增加的总会在总执行时间从13.32到6186.20年代不等。OpenMP版本所消耗的时间比串行版本。不同于串行版本,增加的总会在当总会在总执行时间增加小于16日根据同样的越来越多的不总会在。让nopt= 30为例(粗体行表2);的总会在从4到1024年增加2的倍数。我们可以观察到总的执行时间从34.02秒增加到3737.83秒。当总会在小于16岁,越来越多的总执行时间并不是两个(不到两个)。当总会在等于或大于16,增加多个约等于2。这是因为OpenMP版本可以使用最多8个CPU核(本研究中使用的CPU最多8核)。当总会在小于16岁的线程的数量等于所使用的CPU核。更大的总会在需要更多的CPU核的CPU可以提供足够的核心OMP-SCE-UA(当总会在小于16)来提高性能。因此,越来越多的总执行时间并不是两个(不到两个)。然而,当总会在等于或大于16日的增加总会在,OMP-SCE-UA需要更多的CPU核来提高性能。然而,只有8个CPU核和OMP-SCE-UA的CPU不能提供更多的计算资源来提高性能。因此,执行时间增加而增加的倍数总会在(当总会在等于或大于16)。

3.1.3。CUDA-SCE-UA

总执行时间的CUDA SCE-UA是显示在图7和表3。我们可以看到,越来越多的nopt总执行时间增加。至于增加的总会在总执行时间从224.62到1400.51年代不等。CUDA的性能版本是完全不同于串行和OpenMP。的增加总会在,执行时间变化小,减少一点。这是因为较低总会在(即。,less GPU threads) the GPU cannot hide the latency of the global memory access. The latency slows down the performance of the algorithm. With larger总会在GPU可以隐藏的延迟,同时启动多个线程,因此提高算法的性能。

3.2。加速比率分析

加速率统计数据显示在图8和表4和5。如图、表OpenMP版本变化的加速比从3.28 x 7.81 x,和加速比的CUDA版本从0.17倍到45.95倍不等。OpenMP的加速率都小于8 x版本。原因如下。OpenMP程序创建尽可能多的线程来充分利用所有的CPU核心。当线程的数量变得比8,因为CPU利用在这项研究中只有8 CPU核心,创建、管理、调度和销毁线程的CPU消耗更多的CPU资源和防止加速率大于8倍。至于CUDA的版本,当总会在(等于GPU)创建的线程的数量很小,CUDA的加速比版本小于OpenMP。这是因为时钟速度的核心是2.5 GHz CPU的时钟速度远高于GPU核心(902 MHz)。然而,当总会在是非常大的(总会在> 128),加速比的CUDA版本变得远高于OpenMP。这是因为GPU核心(640 CUDA GPU核心)多CPU(只有8 CPU核),可以推出更多并行线程来提高性能。至于OpenMP版本,加速率几乎达到最大值时总会在= 8和16,加速比不能成为更大的增加总会在。至于CUDA版本,加速比可以成为非常大的增加总会在和性能比OpenMP版本变得更加令人满意。最后,我们从图可以观察到8 (f)这一nopt(即。,的number of decision variables) has very little impact on the speedup ratio. This means that although the total execution time increases with the increasing of thenopt很少,加速比的关系nopt。

3.3。分析目标函数计算开销的影响

之间的关系nobj和加速比是显示在图9。我们设置nopt= 20。的总会在从4到1024不等。我们可以看到越来越多的nobj(即。,的increasing of the objective function computational overhead), the speedup ratio becomes larger. There is one difference between the OpenMP and the CUDA version. With the increasing of the总会在和nobj优化问题变得更加复杂和计算开销变得更重。加速比的增加程度OpenMP版本不是很宽,加速比是不高于8 x。的增加总会在的加速比CUDA版本变得远高于OpenMP版本,大约45 x。这些结果表明,CUDA版本执行比OpenMP的情况下解决问题的复杂和高计算负载目标函数。

3.4。优化精度比较

检查后优化的结果,我们发现所有的优化问题收敛于全局最优。这一事实表明,并行SCE-UA可以找到全球最佳的准确性连环SCE-UA。

3.5。一些有用的建议如何正确利用平行SCE-UA方法

在仔细检查结果,我们给出一些有用的建议如何正确利用平行SCE-UA方法:(1)两个串行和并行版本可以给正确的优化结果。因此,对于正常的问题,串行和并行版本都是适用的,可以收敛到全局最优。对于简单的问题(总会在< 256),串行和并行版本都好使用但并行版本可能无法获得满意的加速比,因为创建的开销,调度,和销毁线程通常是高于优化算法的计算开销。因此,对于简单的问题(总会在< 256),我们建议使用串行版本。(2)并行版本运行速度比串行版本特别是复杂(总会在> 128)和高维问题(nopt> 40)。因此,我们建议使用并行版本的这些问题。对于复杂的问题相对较小总会在(总会在< 256),我们建议使用OpenMP版本获得更好的性能。对于复杂的大问题总会在(总会在> 128),CUDA版本是一个更好的选择。至于问题的目标函数计算负载很高,我们建议使用CUDA的版本。(3)我们应该宣布并行版本需要更多的内存比串行版本。这是由于并行版本需要创建数组和向量分别为每个线程以确保并行执行的正确性。因此,对于非常复杂和高维度问题,并行版本可能需要更多的内存和导致内存溢出。我们建议使用64位exe在64位操作系统来应对这些问题,因为64位程序可以使用更多的内存比32位程序。问题的维数(nopt)非常不影响加速比;唯一的限制是内存大小。更大的nopt需要更多的内存来存储大而复杂的人口。因此,对于这些问题我们建议安装更多的CPU内存OpenMP版本或采用Tesla GPU卡(通常有更多的GPU内存)CUDA版本提供更多的内存来确保成功执行的优化。

4所示。结论

在本文中,我们提出了并行SCE-UA方法和实现它在英特尔多核CPU和NVIDIA GPU许多核心的OpenMP和CUDA Fortran。串行和并行SCE-UA代码优化在同一水平,以确保一个公平的比较。摘要Griewank基准函数采用测试和比较串行和并行SCE-UA的表演方法。根据比较的结果,一些有用的建议给出了指导如何正确使用平行SCE-UA。可以表示三个结论:(1)两个串行和并行版本可以获得全球最佳满意的概率。我们现在可以生产可靠的全球最佳状态估计对于大型复杂优化问题由串行和并行版本的SCE-UA方法。(2)实验研究是由使用Griewank基准函数。这个基准测试函数体现了许多全局优化中遇到的典型问题。因此,这里的平行SCE-UA派生的建议可以被认为是大多数应用程序的指导方针。(3)随着新开发的并行SCE-UA方法,我们现在可以生产可靠和更快的估计全球最适条件对于大型复杂优化问题通过使用并行SCE-UA方法。OpenMP版本推荐使用中问题和CUDA版本推荐使用在大型问题。

相互竞争的利益

作者宣称没有利益冲突。

确认

这项研究是由优秀青年科学家的IWHR科研项目“研究和应用Xinanjiang模型参数的快速全局优化方法基于高性能异构计算”(没有。KY1605 JZ0145B052016),具体研究中国水利水电研究所(批准号Fangji 1240),第三个子项目:洪水预测、控制和防汛辅助软件Development-Flood控制预警通信系统和洪水预报、洪水控制和预防辅助软件开发江西省鄱阳湖区域(0628 - 136006104242,JZ0205A432013和SLXMB200902),中国NNSF洪水数值模拟技术基于戈杜诺夫实验方案及其机制研究(没有。51509263),中国的NNSF,研究综合评估风险和利益的动态控制模型在汛期水库水位(没有。51509268),中国NNSF估算区域蒸散遥感数据使用基于理论由变频控制/ LST梯形(没有空间。41501415)。作者欣然承认的支持NVIDIA公司捐赠的特斯拉K40 GPU用于这项研究。