【毕业学位论文】（Word原稿）创新计算机体系结构设计的FMM算法分析-软件工程

创新计算机体系结构设计的 法分析 创新计算机体系结构设计的 法分析 摘要 为了设计专注于高性能计算的新型计算机体系结构，需要研究典型应用，藉此了解系统结构应具备的主要特性。 本文 作为设计创新高性能计算机体系结构的准备工作的一部分，针对应用 程序 在计 算和访存等方面的特性，给出 了 专为 题中的 法 而 优化的体系结构设计策略 。 近年来出现的一些新型计算机体系结构都不约而同的把注意力放在了提高硬件执行效能之上，为此这些新型计算机体系往往针对某些特定范围的应用做了优化。 类似于 体系 结构 中，由于 存在 针对图形处理优化的体系 设计 和特殊硬件， 其 在图形相关的领域 有着 非常好的应用。 而 诸如类 的 可重构体系结构， 往往 具有 粗颗 粒度的 动态 可重构 的硬件设计 ， 从而 能够针对不同应用 的 特点 ，动态的 给予硬件相应的优化配置，保证硬件总能最大程度的发挥自身的 性能。 依照 以上 所述的基于应用分析的 研究方法 ，本 文选取了 题这样一个应用范畴作为分析对象。 题又称多体问题， 是天体物理学 、流体力学以及 分子动力学的基本问题之一，用来模拟一个系统中 相互作用的粒子 的运动规律 。一般可以被描述为： 在 一定的空间中，分布着 多个 粒子，每对粒子之间都存在着相互作用力（如万有引力、库仑力等），使这些粒子发生运动。它们的初始位置和速度是已知的，每隔一定的 时间， 通过 计算粒子之间的作用力，来更新它们的位置和速度。 题早在三百多年前已被提出，几百年来人们经过对它的 不断研究和实验，已经总结出相当成熟和可靠的算法。随着科技的不断发展， 题的规模也随之不停地扩大，现今已 达到了 上亿、甚至上百亿 的规模。这 样大规模的运算对计算机的运算 速度提出了非常大 的挑战， 因此， 题是高性能计算领域最具代表性、 影响力和 挑战性的问题之一。 问题的常见算法有如下几种 ：直接套用公式计算的 法；使用密 度网格计算势能的 法；把计算划分为远程区域与近程区域的 法。 其中 法又包括 法 以及改进型的 法 。为了从这些算法中挑选出具有代表性的 文从时间复杂度和计算精度 等 几个方面对它们进行了分析。 法是最直接 最简单 的算法，时间复杂度为 O( 法是一种在粒子系统里计算引力的方法，它的基本原理是把一个由粒子组成的系统转换成一个密度 的网格（或“筛”），通过该密度网格求解得到 势能，然后，根据粒子在网格中所处的单元以及在单元中的位置，将力应用到每个粒子上去。 它的 时间复杂度是 O(其中 离散网格大小 。但 此只适用于粒子彼此之间距离较远的系统。 法应用树形结构对空间进行划分，并以此将 题的计算划分为近程与远程。它被广泛地应用于天体力学。可快速计算各点受到的力，计算复杂度为 O( 虽然 该算法的 误差范围 小于 1%， 但也只能 够处理天体力学 范畴 的问题。 法 则 是对 法的改进，区别于 法在每个结点处直接计算作用力， 法通过 计算 多项展开式的方法 来实现 不同区域 之间 势能 的转换 ，即 通过计算 及它们之间的转换， 法可以将 题的时间复杂度降低到O(N)。 同时 ， 通过控制 法中多项展开式的截断值 ， 还 能够依据 不同应用 对精度的不同需求 控制 其 计算精度。 以此 ， 本文认为 法相较于 法和 法 更具有 优势， 创新计算机体系结构设计的 法分析 更加适合 作为 新型 高性能计算 机 的典型应用加以分析。 一个流体力学的应用程序， 它通过使用 法来 模拟二维空间中的 毕奥萨伐尔 （ 方程。 在流体力学中，可以把流体看作是由大量的粒子所组成，并通过计算众多粒子的速度，来模拟 程或者 程，这种方法叫做涡流质点方法（ 由于涡流粒子的数量巨大，各自计算又相互独立且依赖粒子间的相互作用，因此可以看作是 题加以解决。 是依据涡流质点方法设计出的应用程序，用来计算在二维空间中高斯分布下 的涡流粒子按照毕奥萨伐尔定律发生的速度变化。 C+实现，以 基础设计了相关的数据结构和算法，并初步实现了 的并行。 用四叉树结构对二维空间进行划分，并 据此划分 出近程区域与远程区域。 在此基础之上， 照先自底向上再自顶向下的顺序 执行算法 ，依次为 ： 生成底层划分的 照划分层次从下往上传递 每层划分中转换 远程区域的 上往下传递 后由 换到每个粒子的速度。 用中涉及到四叉树、本地列表和交互列表等数据结构，本文对他们的 内存占用做了定量分析。 为了探讨 算和访存的特点，针对 序中的各个阶段， 本文还 给出了定量的计算量和访存量分析。最后 根据 以上分析， 初步给出了针对 法优化的体系结构方案 ，包括计算单元的种类与数量、访存单元的配置比例和片上缓存的设计 策略，具体包括：运算器阵列以双精度 基本运算单元；需要放置特殊运算单元以满足双精度除法和自然指数运算的需要；为了保证不出现访存瓶颈，至少需要为每个运算器阵列配置一个独立的访存单元；片上缓存应设计为可编程而不是一般 的 构 ；针对片上缓存的大小，需要调整算法迭代的次序和并行计算分块的策略 。 最后，本文 还 指出了在体系机构设计 的后续阶段 ， 法分析还需要继续跟进的一些 工作。 关键词： 体系结构、高 性能计算， 题 ， 法 创新计算机体系结构设计的 法分析 o we to of As of an of on of as to a in to do to a a be to In to of In in a of is of to be to is of of is to a of of as be as in a of of a by or of if in of is at of we of at or of of in is in be of in a to s as a we as a of to of be a 创新计算机体系结构设计的 法分析 to a to in TM H (is H 3M, 3M PP is a ( PM a to of to to PM ( in g of As a M BH a or an to BH is in a of BH as In to H an is of H to MM we to It (N) to On MM be by of MM it be to of M H is we a to do is an to of MM to in In of be by of in it in is as a to is In a of be as is in a is an +, to It a to in on by of an as a to as of we to In P In a to to to at of to in At to of 2M ( 2P ( as as of in a MM is is on by a of 创新计算机体系结构设计的 法分析 in to of of at is to be as a to of MM to be At as a a is to be in to of of 创新计算机体系结构设计的 法分析 第 1 页 共 2 页 目 录 第一章 绪论 . 1 法 . 1 M 算法（ 子网格算法） . 1 M 算法（ 结构算法） . 2 合算法 . 2 种新型高性能计算机体系结 构 . 2 重构专用处理器 . 2 用计算图形处理器 . 3 结 . 3 第二章 法过程分析 . 3 M 算法 . 4 法概述 . 4 法分析 . 4 H 算法 . 4 法概述 . 5 法分析 . 5 法 . 6 法概述 . 6 法分析 . 7 结 . 7 第三章 法应用分析 . 7 用简介 . 8 据结构分析 . 8 于四叉树的空间划分 . 8 居列表、本地列表与交互列表 . 9 法流程分析 . 11 始化 . 11 底向上运算 . 11 顶向下运算 . 12 算量、访存量分析 . 12 阶段计算量 . 13 阶段访存量 . 13 阶段访存计算比 . 14 对新型体系结构的分析 . 15 算单元配置 . 15 存单元配置 . 15 上缓存配置 . 15 结 . 16 创新计算机体系结构设计的 法分析 第 2 页 共 2 页 第四章 结论 . 16 参考文献 . 17 谢辞 . 18 创新计算机体系结构设计的 法分析 第 1 页 共 18 页 第一章 绪论 题又称多体问题， 是天体物理学 、流体力学以及 分子动力学 的基本问题之一 ，用来 模拟 一个系统中 N 个 相互作用的 粒子 的运动规律 。一般 可以 被描述为： 在 一定的空间中，分布着 N 个粒子 ，每对 粒子 之间 都 存在着 相互作用力（如 万有引力 、库仑力等）， 使这些粒子 发生运动。 它 们的初始位置和速度是已知的，每隔一定的 时间 ， 通过 计算 粒子 之间的作用 力 ， 来 更新 它 们的位置和速度 1。 题早在三百多年前已被提出，几百年来人们经过对多体问题不断地研究和实验，已经总结出相当成熟和可靠的算法。随着科技的不断发展， 题的规模也随之不 停地扩大，现今已 达到了上亿、 甚至上 百 亿的规模。这 样 大规模的运算对计算机的运算 速度提出了很 高的挑战， 而 题 中 各 对作用力计算 相互独立的特性 ，表明其更适合应用并行计算的方法来解决。 因此， 题是高性能计算领域最具代表性、最有影响力以及最有挑战性的问题之一。 为了设计出 创新 高性能计算机体系结构，需要通过分析 样的典型应用，找出其 对计算、存储和通信等特性 的要求，从而以应用自身为出发点，提出针对应用 优化的 体系结构 设计方案。 法 题可以被看作是 一组已知初始值的常微分方程组，即已知初始值，在 i 不等于 j 时 ，解出下列二阶常微分方程组 1： 3() , 1 , 2 , . . . ,n i j j m q qm q j (1) 在公式 (1)中， 代表 n 个质点质量的常量。 , 21是以时间 t 为变量描述质点位置的三维矢量函数。 题的数值模拟实 质上是求解关于时间的常微分方程组。 通常将直接计算公式 (1)的方法称为 法（ 法），在每个时间步迭代时都需要计算每对粒子之间的相互作用，其时间复杂度为 O( 法的优点是精确度高，并且易于并行化处理。但其缺点也很明显，就是算法复杂度较高 ，当问题规模很大时，使用这种算法模拟问题的效率很低。因此，找到时间复杂度更低的 题算法是高性能计算领域的挑战之一，至今 学术界 已提出了下面 几类优化算法 2： M 算法（ 子网格算法） 法是一种在粒子系统里计算引力的方法，它的基本原理是把一个由粒子组成的 系统转换成一个密度的网格（或“筛”），通过该密度网格求解得到 势能，然后，根据粒子在网格中所处的单元以及在单元中的位置， 再 将 作用 力应用到每个粒子上去 3。 在离散的网格空间中，假设粒子分布在网格顶点间，这种情况下，计算势能比较容易，因为泊松等式 ，即公式 (2)中， 2 4 G (2) 是势能函数， G 是牛顿常量， 是密度，即网格内粒子的数量，用快速傅立叶变换（ 换成更简单的公式 (3)。 创新计算机体系结构设计的 法分析 第 2 页 共 18 页 24 G (3) 其中， k 代表了共动波数 (作用在粒子上的力可以取势能函数的梯度获得。 法的优点是速度很快，时间复杂度是 O(其中 离散网格大小。 法的缺点是，如果粒子之间的距离较小，用这种方法计算得到的粒子之间的力是不精确的，它只能用于计算长距离间粒子互相作用的力 3。 M 算法（ 结构算 法） 法也 叫多层算法，是一种 经过 改进 的 法 2。在这种算法中，粒子被分为远程粒子和邻近粒子。远程粒子的受力计算是用了近似计算的方法将远程粒子团（簇）的作用近似地看成一个粒子的作用从而减少计算量，其本质上是把大系统切成小立方体，只计算小立方体之间的引力，这样原来 1000 个点，可能只切成 10 个立方体，从而大大降低计算复杂度。近距离的粒子（邻近粒子）则采用 法。在实际过程中近距离的粒子要比远程的粒子少的多，因此影响算法复杂度的主要因素是对远程粒子的计算。近距离的粒子虽然使用了法，但是由于所占 的比重微乎其微，并不会对算法的效率产生重大的影响。因此，采用 法有利于快速计算和并行划分。 法中的典型算法包括 法（ 4和 法（ 速多极子算法） 5。 法可快速计算各点受到的力，时间复杂度为O(但 误差 通常只有 过对于某些研究领域来说，如天体力学，这个精度已足够。 法通过层次划分和位势函数的多极子（ 开计算各点位势，以 O(N) 的时间复杂度可达到任 意精度。 采用树结构的算法还有 法和 法，而 法是 法和多极子算法的结合。 合算法 除了上述两种主要的算法外，也有混合各种算法以达到更好计算效果的尝试。 法 3、 3M3（自适应网格）、 （粒子树 法等都是 混合算法。通常，在混合算法中， 于计算远程粒子之间的力，而直接计算粒子之间的力的 法则用于计算邻近 粒 子之间的力。 种新型 高性能计算机体系结构 近年来出现了几种新型的高性能计算机体系 结构 ， 它们不约而同的把关注点放 在了提高性能功耗比、性能价格比之上。这些 新型体系结构的共同点在于它们都是 通过前期的应用分析和巧妙的硬件配置， 设计出针对特定 范围的 应用优化 过 的体系结构， 以此来充分利用高性能计算机的处理能力 。常见的几种新型高性能计算机体系结构 包括：可重 构专用处理器 、通用计算图形处理器等。 重构专用处理器 可重构处理器 是 指 硬件上具有可编程特性的一类处理器，他们的芯片中具有 可配置 的 硬件 控制点， 处理器依赖 于 不同的 硬件配置 来满足特定的计算 需求 ， 以 最大限度的发挥硬件性能。 可重构处理器不同于 等传统可重构 硬件的关键在于，可重构处理器 往往是 粗颗粒度上的可重构， 且通常 只有部分可重构 ，并 具有 动态可重构 的特性 。 因而 可重构专用处理器不仅可以为某个特定 应用提供类似于专用处理器的性能，而且能够根据不同应用的特性 动态 调整硬件体系，以保证处理器的通用性。 典型的可重构专用处理器 如 和 等。 专为具有数据 级 并行、计算高度规则和吞吐量巨大 这三种特性的 一类应用设计的新型体系结构， 主要应用 于 图像处理和视频压缩等领域 6。 它 由 一块可重构 的 处理器阵列、 一颗 通用 处理器 和一组高带宽的访存部件组成。其中通用处理器 为一颗 心 ， 用以执行输入的程序 ， 并根据程序逻辑 动态的 控制可 重构处理器阵列的配置 与计算 ，从而 实现 针对不同应用的动态可重构。 为 一颗 典型的 可重构处理器，具有粗颗粒度可重构，部分 可重构和动态可重构的特点。 创