创新计算机体系结构设计的 fmm 算法分析

《创新计算机体系结构设计的 fmm 算法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、创新计算机体系结构设计的FMM算法分析创新计算机体系结构设计的FMM算法分析摘要为了设计专注于高性能计算的新型计算机体系结构，需要研究典型应用，藉此了解系统结构应具备的主要特性。本文作为设计创新高性能计算机体系结构的准备工作的一部分，针对应用程序在计算和访存等方面的特性，给出了专为N-body问题中的FMM算法而优化的体系结构设计策略。近年来出现的一些新型计算机体系结构都不约而同的把注意力放在了提高硬件执行效能之上，为此这些新型计算机体系往往针对某些特定范围的应用做了优化。类似于GPGPU（General-PurposeComp

2、utingonGraphicsProcessingUnits）的体系结构中，由于存在针对图形处理优化的体系设计和特殊硬件，其在图形相关的领域有着非常好的应用。而诸如MorphoSys之类的可重构体系结构，往往具有粗颗粒度的动态可重构的硬件设计，从而能够针对不同应用的特点，动态的给予硬件相应的优化配置，保证硬件总能最大程度的发挥自身的性能。依照以上所述的基于应用分析的研究方法，本文选取了N-body问题这样一个应用范畴作为分析对象。N-body问题又称多体问题，是天体物理学、流体力学以及分子动力学的基本问题之一，用来模拟一个系统中

3、相互作用的粒子的运动规律。一般可以被描述为：在一定的空间中，分布着多个粒子，每对粒子之间都存在着相互作用力（如万有引力、库仑力等），使这些粒子发生运动。它们的初始位置和速度是已知的，每隔一定的时间，通过计算粒子之间的作用力，来更新它们的位置和速度。N-body问题早在三百多年前已被提出，几百年来人们经过对它的不断研究和实验，已经总结出相当成熟和可靠的算法。随着科技的不断发展，N-body问题的规模也随之不停地扩大，现今已达到了上亿、甚至上百亿的规模。这样大规模的运算对计算机的运算速度提出了非常大的挑战，因此，N-body问题是高

4、性能计算领域最具代表性、影响力和挑战性的问题之一。N-body的问题的常见算法有如下几种：直接套用公式计算的PP（ParticletoParticle）算法；使用密度网格计算势能的PM（ParticleMeshMethod）算法；把计算划分为远程区域与近程区域的TM（TreeMethod）算法。其中TM算法又包括BH（Barnes-Hut）算法以及改进型的FMM（FastMultipoleMethod）算法。为了从这些算法中挑选出具有代表性的N-body算法，本文从时间复杂度和计算精度等几个方面对它们进行了分析。2PP算法是最直

5、接最简单的算法，时间复杂度为O(N)。PM算法是一种在粒子系统里计算引力的方法，它的基本原理是把一个由粒子组成的系统转换成一个密度的网格（或“筛”），通过该密度网格求解得到势能，然后，根据粒子在网格中所处的单元以及在单元中的位置，将力应用到每个粒子上去。它的时间复杂度是O(NglogNg)，其中Ng为离散网格大小。但PM算法对于距离较近的粒子精度很低，因此只适用于粒子彼此之间距离较远的系统。BH算法应用树形结构对空间进行划分，并以此将N-body问题的计算划分为近程与远程。它被广泛地应用于天体力学。可快速计算各点受到的力，计算复

6、杂度为O(NlogN)。虽然该算法的误差范围小于1%，但也只能够处理天体力学范畴的问题。FMM算法则是对BH算法的改进，创新计算机体系结构设计的FMM算法分析区别于BH算法在每个结点处直接计算作用力，FMM算法通过计算多项展开式的方法来实现不同区域之间势能的转换，即ME（MultipoleExpansion）和LE（LocalExpansion）。通过计算ME和LE以及它们之间的转换，FMM算法可以将N-body问题的时间复杂度降低到O(N)。同时，通过控制FMM算法中多项展开式的截断值，还能够依据不同应用对精度的不同需求控制其

7、计算精度。以此，本文认为FMM算法相较于PM算法和BH算法更具有优势，更加适合作为新型高性能计算机的典型应用加以分析。PetFMM是一个流体力学的应用程序，它通过使用FMM算法来模拟二维空间中的毕奥－萨伐尔（Biot-Savart）方程。在流体力学中，可以把流体看作是由大量的粒子所组成，并通过计算众多粒子的速度，来模拟Euler方程或者Navier-Stokes方程，这种方法叫做涡流质点方法（VortexParticleMethod）。由于涡流粒子的数量巨大，各自计算又相互独立且依赖粒子间的相互作用，因此可以看作是N-body问

8、题加以解决。PetFMM就是依据涡流质点方法设计出的应用程序，用来计算在二维空间中高斯分布下的涡流粒子按照毕奥－萨伐尔定律发生的速度变化。PetFMM由C++实现，以PETSc为基础设计了相关的数据结构和算法，并初步实现了CPU上的并行。PetFMM使用四叉树结