论文部分内容阅读
随着高性能计算机的应用与发展,大规模分布式并行处理成为国家科技发展历程中不可或缺的工具。然而,目前高性能计算机面临的突出问题是实际获取的性能低,特别是在成百上千处理器的高性能计算机上许多科学计算与工程应用并行软件,难以获得理想的绝对计算速度和并行效率。 影响并行应用程序计算性能发挥的主要瓶颈之一是消息传递通信模块设计或使用的不合理,导致出现全局通信频率过高,或导致通信堵塞。数据分析表明,聚合通信开销往往占据全部消息传递通信开销的80%以上。明显,提高应用软件通信性能存在两种途径。其一是压缩全局通信的频率,其二是提高集群通信的性能。因此,本文把聚合通信算法的效率作为研究重点。 聚合通信包括很多全局操作,比如广播通信(Broadcast),同步(Barrier)、全局归约(Reduce),散布(Scatter)、聚集(gather)等等。每一种操作都有许多不同的实现算法,有的算法也可以适用于多种全局通信操作。所有的全局通信,也无非是一对多,多对多,多对一这三种模式中的一种,而且很多聚合通信的实现是由其他聚合通信的组合来实现的。因此,本文中选择了有代表性的全局归约作为主要研究对象。 理论和实验是研究比较聚合通信算法的两大主要方法。实验测试主要是通过在不同的集群上测试不同聚合通信算法的执行效率,进行横向的比较。而理论上的研究就是通过定义描述聚合通信的通信模型来研究聚合通信算法的时间复杂度。为了能够在理论上更准确的研究聚合通信算法,需要确定一个恰当的通信模型用来描述聚合通信算法。聚合通信是基于点对点通信来实现的。因此,可以采用基于点对点的并行计算模型来研究聚合通信。一个恰当的模型可以为聚合通信算法提供精确的定量分析,有助于算法的设计与研究。在本文中就采用了目前广泛应用的并行计算模型LogGP模型和经常用来评估聚合通信算法复杂度的α+nβ模型。这两个模型都是基于点对点通信的,因此它们一定存在着一些联系,在本文中对这两个模型之间的关系进行了研究并建立了这两个模型之间的关系表达式。 然而,在对聚合通信的理论分析中,用这两种模型模拟聚合通信算法的复杂度时,并不能得到令人满意的结果,特别是对那些处理长消息通信的复杂算法的模拟出现了很大的误差,有时相对误差会超过50%。为了研究这种