并行计算翻译.doc

3. GPU-FWA:ALGORITHM AND IMPLEMENTATION(GPU-FWA-GPU Fireworks Algorithm烟花算法与实现)在一个负担得起的成本的情况下，GPU提供了巨大的计算能力。但目前尚不清楚传统范式是否适用于表达在有效地实现架构上对GPU并行的方式。在本节中,我们提出一个方法致力于GPU大规模并行体系结构。该算法的目标在CUDA平台上实现:a. 优质的解决方案。该算法和先进的算法比较，可以找到好的解决方案。b. 良好的伸缩性。当问题变得复杂时，该算法可以在一种正常且较好的方式扩展。C.易于实现和可用性，即一些控制变量引导优化，这些变量是健壮性的也是易于选择的。为了实现这个目标，在原有的FWA算法下做些改进，汲取这种特殊架构带来的好处。该算法的伪代码描述是A1.1 像其他群体智能算法,GPU-FWA是一种迭代算法。在每个迭代中,每一个烟花做一个本地的独立搜索。然后,一种信息交流机制被触发去利用启发式信息指导搜索过程。机制应该在探索和利用之间做一个平衡。算法是自描述的,剩下的是使A1.2 A1.3 明确.下面我们分别详细解释这两个算法。3.1 FWA搜索算法 模仿烟花在天空的爆炸过程。FWA产生一定数量的火花来探索相邻的解空间。较适合值的烟花可以在较小的振幅情况下产生更多火花。这种策略旨在把更多的计算资源放在更多潜在的位置。从而在探索和利用之间做一个平衡。在A1.2中，我们采取这种策略，但是是一种贪心的方式，即不是在FWA的全局选择过程。每个烟花都更新为当前的最佳火花。这种机制展现了一种加强的爬山行为搜索。每个烟花生成一定数量的火花。火花的确切数量(m)取决于依照特定的GPU硬件架构。这种固定编码的烟花激增更适合gpu的并行实现。正如2.2节中提到的，在使能的cuda GPU里，线程是被扭曲的。现在，对所有的使能的cuda GPU的线程束（warp）都是32位的。每个线程束（warp）分配一定数量的流处理器(SPs)。所有线程在同一线程束（warp）中一次执行一个共同的指令在这些流处理器（SPs）。老一辈的特斯拉架构8,号这个数量是8个,费米架构9是16个。与我们的实验设置(GeForce 560 ti,见4.1节。),线程束（warp）的大小是32,并分配给16 流处理器。为了避免硬件资源的浪费,m应该是16或多个16。但是没有必要选择m大于16.当m较大容易过度到一个特定的位置。而更好的细化搜索可以通过运行实现更多的激增。作为一个经验法则,m在费米架构GPU应该是16和32的，在上一代特斯拉的架构是8或16。因此每个烟花的火花可以由踏板（treads）在一个线程束（warp）生成,而线程束（warp）在2.2节提到的,不需要任何额外的同步开销。也可以从A1.2中看到，它不像FWA，在GPU-FWA烟花在每个爆炸过程不交换信息,并为每个烟火的火花数量是固定的。这样带来了以下好处：首先,全局通信在烟花需要显式同步,这意味着相当大的开销。通过让这个算法执行一个给定的迭代次数，没有交换信息,时间就会大大减少。其次,每个烟火的火花产生的数量动态确定,计算任务通过优化过程必须动态分配。在控制操作下，GPU是低效的,动态计算的任务是容易损害GPU的整体性能。通过修复火花数量,我们每个烟花可以分配线程束（warp）,这种方式,所有的火花是隐式同步，没有额外的开销。最后，在一个块线程里实现爆炸。它可以充分利用共享内存,因此,一旦烟花的位置和适当性从全局内存加载,不需要访问全局内存。全局内存访问的延迟可以大大减少。3.2 吸引和拒绝变换（Attract-Repulse Mutation）当启发式信息用于指导本地搜索,其他策略应采取保持烟花群的多样性。保持烟花群的多样性对优化过程的成功是至关重要的。在FWA中，高斯变换的介绍增加了烟花群的多样性，在这个突变过程,生成额外的火花 m。生成这样一个火花,首先,比例因子g从g(1;1)分布中产生。随机选择的烟花，每个烟花对应的维度和当前最好的烟花之间的距离乘以g。因此,新的火花可以接近最好的烟花或进一步远离它。类似高斯变换，在GPU的FWA中，一种称为attract-repulse变换的机制(ar-mutation)提出了实现这一目标通过一种明确的方式。如A1.3说明，Xi 描述为第i个火花（firework）。而Xbest描述为最适合的火花（firework）。ar-mutation背后的哲理,如图4所示。不是最好的火花（firework），他们要么被最好的烟花吸引“帮助”开发当前的最佳位置或拒绝最好的烟花来探索更多的空间。“吸引”和“拒绝”之间的选择反映了开发和探索的平衡。在15中使用高斯变换。但可以采取各种分布。均匀分布是最简单和容易使用,我们需要在该算法采取这种策略。理论上分析ar-mutation机制,这个过程可以简化为一个一阶Markorv链。,给i的那个x0 = 1,下一个状态由Eq.3生成.T在a，b之间服从正态分布，并且0a1然后第t个状态可以由下面的方程表示：我们可以计算预期的位置我们可以从Eq.4中看到，如果a的预期，即A大于1，则期望x是指数增长；否则A小于1，则期望x是指数减少。图5演示了一个仿真结果,树过程服从U(0:9;1:11)(= 1:005),U(0:9;1:1)(= 1),和U(0:9;和)(= 0:995)。模拟显示,即使在A= 1是很小的扰动,结果往往分歧无限放到或者收敛于0.至于ar-mutation,这意味着烟花要么被可行性范围拒绝，要么被当前最好的位置吸引。这两种情况导致多样性丧失。为了确保烟花可以在搜索空间更稳定的“徘徊”。A应该等于1，这分布应该是S=U（1+，1-），其中属于（0，1）.然而,随着搜索范围是有限的，因此应该更小心的赋值，且A设置成1.