并行计算翻译.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 之间服从正态分布，并且01然后第 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.图6所描述的,从左到右,从上到下,分别采取从0.9到 0.1在仿真时,当 x > 100时，X 在10被截断X 以不同的速度收敛到0作为一种趋势,对于更快的收敛,反之亦然但是确切的收敛速度是最合适的,是取决于任务的它依赖于目标函数和在运行迭代算法的数量。