论文部分内容阅读
一、前言
计算机的出现推动了人类在科学技术的各个领域的发展,这些发展反过来又向计算机提出了更高的要求。人类面临着许多被称之为“巨大挑战”(Grand Challenge)的问题有待于解决,例如,对生物遗传基因、气象预报、流体动力学、石油勘探、地震预测、新材料设计、环境污染以及海洋潮汐等领域的研究。这些问题涉及到科学发展的各个重要方面,包括未来人类的生存环境和当今科学技术的最前沿问题,代表了其它学科对计算机科学提出的巨大挑战。这些问题的解决无一例外地都需要高性能计算(high-performance computing,HPC),需要使用具有每秒万亿次浮点处理能力( FLOP)的计算机。实践证明,并行处理是提高计算性能、满足不断增长的应用需求的有效途径,然而,计算机要能够及时地计算出一个以五公里为网格的大气模型,至少要具备每秒20 万亿次浮点运算的能力。这对于目前的计算机来说,还是难以达到的。由此,科学研究领域正在越来越依赖于高性能计算,并行处理已经成为进一步提供高性能计算的有力手段。在大多数并行系统里面,加速比是并行程序的重要指标之一,它的大小直接反映并行算法的优劣。
二、分布式演化算法
在自然界,由于组成生物群体中各个体之间的差异,对所处环境有不同的适应和生存能力,遵照自然界生物进化的基本原则,适者生存、优胜劣汰,将要淘汰那些最差个体,通过交配将父本优秀的染色体和基因遗传给子代,通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下,基因会发生突变,产生新基因和生命力更强的新个体;但突变是非遗传的,随着个体不断更新,群体不断朝着最优方向进化,遗传算法是真实模拟自然界生物进化机制进行寻优的。
演化算法总是会过早趋向于收敛,故而需要加以改进。分布式演化算法就是在这种背景下产生的。在分布式演化算法中种群被分离成一些小的子群体,从而形成了隔离的物种。当收敛之后将一些个体从不同的子种群输入某一子种群,则带来一些新的基因构造块,同时迁移来的个体将对子群体的平均适应值带来很大的改变。这两个因素加在一起将诱导新物种形成,从而伴随着一个快速进化阶段。这样,使分布式演化算法能在一定程度上避免过早收敛的发生,从而可以提高解题的速度和质量。
三、加速比的引入
(一)并行加速比的概念
绝对加速比(Absolute Speedup):这个定义考虑的是一个问题用N个处理器来节到底能提高多快。它把最好的串行算法与并行算法进行比较。绝对加速比根据考虑或不考虑机器资源又分为两种情况,一种是机器依赖,另一种是机器独立。
第一种情况(机器依赖)
第二种情况(机器独立)
相对加速比(Relative Speedup)由于实际情况的限制,不存在最好的串行算法可供应用。可以将加速比定义为同一并行算法在单节点上运行时间与在多个节点构成的处理机系统上的运行时间相比。这种定义侧重于描述算法和并行计算机本身的可扩展性。
(二)并行加速比思想的精细化
最初,最基本的加速比的提出是为了确立一种无尺度、容易理解的度量并行计算机性能的手段。超流水线有时会产生非常高的加速比,但往往可能是因为非常低效的串行计算所导致,而并非像人们期望的那样,具有很高效的并行计算能力。一些导致串行计算低效的因素包括低效率的Cache 管理以及大数据规模的容量要求等等。
为了保持无尺度测量性能的优点,后来从最初的绝对加速比转为相对加速比(一个算法在单一处理器上执行时间比上在一系列处理器单元上执行的并行时间)的概念。这一系列处理机应该被固定,而且应该具有相似可类比的执行单元。(比如:相似的指令执行速率,相称的指令执行时间等等)
今后作为一种更为复杂的并行加速比模型的建立,它应该重点考虑那些导致并行计算低效率的主要因素:串行部分和有重复冗余的工作,相互间通信及其控制以及阻塞及其控制。这种模型应该允许并行算法的描述相对独立于系统结构,而不受限于具体机群系统的特征,加速比本身就是针对算法而言,并非针对某一个并行机系统,这点是非常值得重视的。例如,一个带有通信复杂度为P=O(P)的算法比起一个通信复杂度为P=O(P2)的算法就更具备可扩展性。这一点意味着前者可获得的最大加速比会更高,而且能够在一个大数量的处理器环境下得以维持。但是,即使这样高级别的描述也容易引起误解。例如,一个三维FFT算法具有通信复杂度P=O(P2),但是允许网络间的并行通信。这样一个算法可能会比一个复杂度是P=O(P),但是在通信方面严格遵循串行化的算法更加高效。
四、加速比数据分析
分布式演化计算其通信的时间开销与计算的时间开销相比是微不足道的,这就能保证采用分布式算法能够取得线性或者超线性的加速比。由于IGT算法已经能够求得小规模的TSP问题的最优解,所以试验时,在考虑现有的实验条件中机器结点的数量和配置的前提下,选取了chn144、ad198和lin318共3个TSP问题,用来计算分析分布式算法所能取得的加速比,根据加速比的定义,采用相对加速比能更好地反应出实验的准确性。
(一)对于chn144的加速比测定实验
演化参数:种群规模=100,临界速度=900,变异概率=0.02,映射概率=0.05,最大停止改变代数=200000,并行参数:进程数=16,迁移间隔=1000
(二)对于ad198的加速比测定实验
演化参数:种群规模=100,临界速度=900,变异概率=0.02,映射概率=0.05,最大停止改变代数=200000,并行参数:进程数=16,迁移间隔=5000
(三)对于lin318的加速比测定实验
演化参数:种群规模=100,临界速度=900,变异概率=0.02,映射概率=0.05,最大停止改变代数=200000,并行参数:进程数=16,迁移间隔=40000
(四)实验数据分析和总结
通过对上述三个数据处理表格的比较,验证了分布式演化算法并行处理能大大提高运行速度的预测的正确性,并且其加速比和节点数的比例大体一致,虽然所取节点数的个数较少,但可以粗略看出来并行演化算法可以取得大致的线性加速比。由于演化计算有很大的随机性和不可预测性,且实验的数据个别相差较大,特别当问题比较复杂时,运行相差的时间可能很大,它可能直接影响到平均值并不是最好的时间,进而进一步影响加速比。当然,影响加速比的因素还有很多:比如采用区域分割、拼接网络措施可以提高加速比;负载平衡对加速比也有较大的影响,平衡负载是提高并行效率比较直接有效的方法;网络规模也是影响加速比的一个重要参数,扩大网络规模可以提高加速比的值,本次设计采用的是局域网内的结点计算机,因而传输的速率比较快,为并行计算提供了优越条件。
五、小结
加速比是对分布式演化算法并行加速的在数据层面上的体现,同时对并行算法的理论研究具有重要的意义。本文实验在PVM平台下,通过对多个TSP问题在不同的节点机器数下进行测试,求出能得到的加速比。由于采用的是局域网,网络传输速率较快, 而且该算法是计算密集型的,在一定的迁徙间隔下通讯占用时间不会随宿主机的增加而显著增加,而是停留在一定的数量级上,所以并行算法在一定扩展范围内可以取得接近线性的加速比。同时影响加速比的因素还有很多,如负载平衡、网络规模以及迁移率和迁移间隔等参数,调整优化这些参数可以使算法效率进一步提高。
并行演化算法在很多领域起着重要的作用,通过设计更加优秀的并行算法,改善优化网络拓扑结构,提高并行计算的加速比,发挥巨大的威力,使其在各个领域中做出更大的贡献。
参考文献:
[1] Olssen P. and Johnson S. A data parallel implem station of an exp licit method for thethree dimension comprseeible N S equation. Parallel Computing, 1990
[2] Michalewicz Z How to Solve It--Modern Heuristick.Berlin Heidelberg:Springer-Verlag, 2000
[3] 沈志宇, 并行程序设计 长沙:国防科技大学出版社,1996
[4] 谢超,麦联叨,都志辉 关于并行计算系统中加速比的研究与分析,计算机工程与应用2003年
计算机的出现推动了人类在科学技术的各个领域的发展,这些发展反过来又向计算机提出了更高的要求。人类面临着许多被称之为“巨大挑战”(Grand Challenge)的问题有待于解决,例如,对生物遗传基因、气象预报、流体动力学、石油勘探、地震预测、新材料设计、环境污染以及海洋潮汐等领域的研究。这些问题涉及到科学发展的各个重要方面,包括未来人类的生存环境和当今科学技术的最前沿问题,代表了其它学科对计算机科学提出的巨大挑战。这些问题的解决无一例外地都需要高性能计算(high-performance computing,HPC),需要使用具有每秒万亿次浮点处理能力( FLOP)的计算机。实践证明,并行处理是提高计算性能、满足不断增长的应用需求的有效途径,然而,计算机要能够及时地计算出一个以五公里为网格的大气模型,至少要具备每秒20 万亿次浮点运算的能力。这对于目前的计算机来说,还是难以达到的。由此,科学研究领域正在越来越依赖于高性能计算,并行处理已经成为进一步提供高性能计算的有力手段。在大多数并行系统里面,加速比是并行程序的重要指标之一,它的大小直接反映并行算法的优劣。
二、分布式演化算法
在自然界,由于组成生物群体中各个体之间的差异,对所处环境有不同的适应和生存能力,遵照自然界生物进化的基本原则,适者生存、优胜劣汰,将要淘汰那些最差个体,通过交配将父本优秀的染色体和基因遗传给子代,通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下,基因会发生突变,产生新基因和生命力更强的新个体;但突变是非遗传的,随着个体不断更新,群体不断朝着最优方向进化,遗传算法是真实模拟自然界生物进化机制进行寻优的。
演化算法总是会过早趋向于收敛,故而需要加以改进。分布式演化算法就是在这种背景下产生的。在分布式演化算法中种群被分离成一些小的子群体,从而形成了隔离的物种。当收敛之后将一些个体从不同的子种群输入某一子种群,则带来一些新的基因构造块,同时迁移来的个体将对子群体的平均适应值带来很大的改变。这两个因素加在一起将诱导新物种形成,从而伴随着一个快速进化阶段。这样,使分布式演化算法能在一定程度上避免过早收敛的发生,从而可以提高解题的速度和质量。
三、加速比的引入
(一)并行加速比的概念
绝对加速比(Absolute Speedup):这个定义考虑的是一个问题用N个处理器来节到底能提高多快。它把最好的串行算法与并行算法进行比较。绝对加速比根据考虑或不考虑机器资源又分为两种情况,一种是机器依赖,另一种是机器独立。
第一种情况(机器依赖)
第二种情况(机器独立)
相对加速比(Relative Speedup)由于实际情况的限制,不存在最好的串行算法可供应用。可以将加速比定义为同一并行算法在单节点上运行时间与在多个节点构成的处理机系统上的运行时间相比。这种定义侧重于描述算法和并行计算机本身的可扩展性。
(二)并行加速比思想的精细化
最初,最基本的加速比的提出是为了确立一种无尺度、容易理解的度量并行计算机性能的手段。超流水线有时会产生非常高的加速比,但往往可能是因为非常低效的串行计算所导致,而并非像人们期望的那样,具有很高效的并行计算能力。一些导致串行计算低效的因素包括低效率的Cache 管理以及大数据规模的容量要求等等。
为了保持无尺度测量性能的优点,后来从最初的绝对加速比转为相对加速比(一个算法在单一处理器上执行时间比上在一系列处理器单元上执行的并行时间)的概念。这一系列处理机应该被固定,而且应该具有相似可类比的执行单元。(比如:相似的指令执行速率,相称的指令执行时间等等)
今后作为一种更为复杂的并行加速比模型的建立,它应该重点考虑那些导致并行计算低效率的主要因素:串行部分和有重复冗余的工作,相互间通信及其控制以及阻塞及其控制。这种模型应该允许并行算法的描述相对独立于系统结构,而不受限于具体机群系统的特征,加速比本身就是针对算法而言,并非针对某一个并行机系统,这点是非常值得重视的。例如,一个带有通信复杂度为P=O(P)的算法比起一个通信复杂度为P=O(P2)的算法就更具备可扩展性。这一点意味着前者可获得的最大加速比会更高,而且能够在一个大数量的处理器环境下得以维持。但是,即使这样高级别的描述也容易引起误解。例如,一个三维FFT算法具有通信复杂度P=O(P2),但是允许网络间的并行通信。这样一个算法可能会比一个复杂度是P=O(P),但是在通信方面严格遵循串行化的算法更加高效。
四、加速比数据分析
分布式演化计算其通信的时间开销与计算的时间开销相比是微不足道的,这就能保证采用分布式算法能够取得线性或者超线性的加速比。由于IGT算法已经能够求得小规模的TSP问题的最优解,所以试验时,在考虑现有的实验条件中机器结点的数量和配置的前提下,选取了chn144、ad198和lin318共3个TSP问题,用来计算分析分布式算法所能取得的加速比,根据加速比的定义,采用相对加速比能更好地反应出实验的准确性。
(一)对于chn144的加速比测定实验
演化参数:种群规模=100,临界速度=900,变异概率=0.02,映射概率=0.05,最大停止改变代数=200000,并行参数:进程数=16,迁移间隔=1000
(二)对于ad198的加速比测定实验
演化参数:种群规模=100,临界速度=900,变异概率=0.02,映射概率=0.05,最大停止改变代数=200000,并行参数:进程数=16,迁移间隔=5000
(三)对于lin318的加速比测定实验
演化参数:种群规模=100,临界速度=900,变异概率=0.02,映射概率=0.05,最大停止改变代数=200000,并行参数:进程数=16,迁移间隔=40000
(四)实验数据分析和总结
通过对上述三个数据处理表格的比较,验证了分布式演化算法并行处理能大大提高运行速度的预测的正确性,并且其加速比和节点数的比例大体一致,虽然所取节点数的个数较少,但可以粗略看出来并行演化算法可以取得大致的线性加速比。由于演化计算有很大的随机性和不可预测性,且实验的数据个别相差较大,特别当问题比较复杂时,运行相差的时间可能很大,它可能直接影响到平均值并不是最好的时间,进而进一步影响加速比。当然,影响加速比的因素还有很多:比如采用区域分割、拼接网络措施可以提高加速比;负载平衡对加速比也有较大的影响,平衡负载是提高并行效率比较直接有效的方法;网络规模也是影响加速比的一个重要参数,扩大网络规模可以提高加速比的值,本次设计采用的是局域网内的结点计算机,因而传输的速率比较快,为并行计算提供了优越条件。
五、小结
加速比是对分布式演化算法并行加速的在数据层面上的体现,同时对并行算法的理论研究具有重要的意义。本文实验在PVM平台下,通过对多个TSP问题在不同的节点机器数下进行测试,求出能得到的加速比。由于采用的是局域网,网络传输速率较快, 而且该算法是计算密集型的,在一定的迁徙间隔下通讯占用时间不会随宿主机的增加而显著增加,而是停留在一定的数量级上,所以并行算法在一定扩展范围内可以取得接近线性的加速比。同时影响加速比的因素还有很多,如负载平衡、网络规模以及迁移率和迁移间隔等参数,调整优化这些参数可以使算法效率进一步提高。
并行演化算法在很多领域起着重要的作用,通过设计更加优秀的并行算法,改善优化网络拓扑结构,提高并行计算的加速比,发挥巨大的威力,使其在各个领域中做出更大的贡献。
参考文献:
[1] Olssen P. and Johnson S. A data parallel implem station of an exp licit method for thethree dimension comprseeible N S equation. Parallel Computing, 1990
[2] Michalewicz Z How to Solve It--Modern Heuristick.Berlin Heidelberg:Springer-Verlag, 2000
[3] 沈志宇, 并行程序设计 长沙:国防科技大学出版社,1996
[4] 谢超,麦联叨,都志辉 关于并行计算系统中加速比的研究与分析,计算机工程与应用2003年