【课程】并行计算导论

2023-07-30 21:21| 来源: 网络整理| 查看: 265

目录并行计算介绍推动并行化计算能力因素 —— 从晶体管到浮点运算速度内存及磁盘速度的因素数据通信因素并行计算适用范围在工业及设计中的应用科学计算中的应用商业应用计算机系统中的应用并行编程平台隐式并行：微处理器系统结构的发展趋势流水线与超标量执行超长指令字（VLIW）处理器内存系统性能的局限使用高速缓存改善有效内存延迟内存带宽的影响躲避内存延迟的其他方法并行计算平台剖析并行平台的控制结构并行平台的通信模型并行平台的物理组织理想并行计算机的体系结构并行计算机互连网络网络拓扑结构静态互联网络评价动态互连网络评价多处理器系统中的高速缓存一致性并行计算机的通信成本

并行计算介绍推动并行化计算能力因素 —— 从晶体管到浮点运算速度摩尔定律：芯片的晶体管数量每18个月增长一倍。内存及磁盘速度的因素总体计算速度并非仅仅由处理器一个因素所决定，也取决于内存系统向处理器提供数据的能力。DRAM：动态随机存取存储器处理器与动态随机存取存储器之间的净有效带宽也对持续计算速度产生影响。内存系统的总体性能是由高速缓存能够满足总内存需求的部分决定的数据通信因素并行计算适用范围在工业及设计中的应用机翼设计内燃机设计高速电路设计结构设计科学计算中的应用一些最新的并行计算技术专门针对生物信息学方面的应用而发展的计算物理/化学，强调对尺度从量子现象到大分子结构之间变化过程的理解天体物理，银河系的演化过程及热核反应气象模型、矿物勘探、洪水预测等商业应用超级计算机计算机系统中的应用并行编程平台

传统意义上的串行计算机是由经数据通道连接到处理器的内存所组成的，处理器、内存及数据通道形成计算机系统总体处理速度的瓶颈。 → \rightarrow → 多处理器、多数据通道、多内存单元。

隐式并行：微处理器系统结构的发展趋势流水线与超标量执行为了提高单个流水线的速度，可以将任务分成更小的单元，这样就能使流水线变长，增加执行时的重叠时间(overlap)超标量执行的相关性：程序中的指令很可能彼此相关：真实数据相关性(true data dependency) 多个流水线分享有限的资源：资源相关性(resource dependency) 控制流程造成指令间的相关性：分支相关性（branch dependency）/ 过程相关性（procedural dependency）超标量体系结构的性能受到可用指令级并行性的限制：垂直浪费（vertical waste）：一个周期中执行部件没有指令发送水平浪费：一个周期周只用到部分执行部件例：如果总共8个可用周期中只有3个用于计算，这就意味着代码段的运算速度不会超过处理器峰值浮点运算速度的3/8 超长指令字（VLIW）处理器由超标量处理器抽出的并行性通常收到指令预测的限制，在常规处理器中，用于动态相关性分析的硬件逻辑一半占总逻辑的5% - 10%，复杂度大约以发送指令数的二次方增长，导致瓶颈。超长指令字把能够并发执行的指令并入到一个组里，作为一个超长指令字。内存系统性能的局限内存系统可能由多级缓存构成，当它收到一条内存字请求，在l纳秒的延迟后，会返回大小为b的包含请求字的数据块。l称为内存的延迟（latency），数据从内存送到处理器的速度决定了内存系统的带宽（bandwidth）

E.g. 内存延迟对性能的影响考虑某一处理器以1 GHz （1纳秒时钟）运行，与之相连的DRAM（动态随机存取存储器）有100纳秒的延迟。假设处理器有2个乘法-加法部件，在每个1纳秒的周期内能执行四条指令。这样处理器的峰值速度就使4 GFLOPS。由于内存延迟时间等于100个周期，并且块大小为1个字，每次发送内存请求时，处理器在处理数据前必须等待100个周期。考虑计算向量点积，每一次浮点运算都要取一次数据。最大速度为100MFLOPS （100纳秒1次）。

使用高速缓存改善有效内存延迟高速缓存：低延迟高带宽的存储器。由高速缓存提供的数据份额称为高速缓存命中率（hit ratio）。许多应用程序有效的运算速度不仅仅受CPU处理速度的限制，还受能送到CPU的数据传送速度的限制 → \rightarrow → 内存首先（memory bound）。高速缓存命中率严重影响受内存首先程序的性能。 E.g. 继上个例子加入一个32KB 和延迟时间为1纳秒的高速缓存。进行3232的矩阵A和B相乘。将两个矩阵取到高速缓存中等同于2K字（23232），200微秒。两个nn的矩阵相乘需要进行2n^3次运算（nn(2n))，64K操作。每个周期执行4条指令，需要16K周期。总时间大概是216微秒。是前一个例子的30倍。在一段段的时间间隔内重复引用数据项的概念称为引用的时间本地性（temporal locality）。内存带宽的影响数据在内存与处理器间传送的速度。假设某一内存请求返回4个字的连续块，这种4个字的单一单元也称为高速缓存行（cache line）。在上上例中，如果把块大小增加到4个字，两次访问能取出每个向量中的4个元素，最大速度变成40MFLOPS。内存中连续的数据字被连续的指令使用，如果以计算为中心，那么就有内存访问的空间本地性（spatial locality）。如果计算不具有空间本地性，那么有效带宽就会比最大带宽小得多。躲避内存延迟的其他方法预取（prefetching）：预测要浏览的网页，并提前发送请求多线程（multithreading）：打开多个浏览器，每个浏览器访问不同的网页一次访问多个页面，在多个访问中分摊延迟。并行计算平台剖析并行平台的控制结构

并行计算的处理器可以在单一控制部件的集中控制下运行，也可以独立运行。

单指令流多数据流（single instruction strem， multiple data stream， SIMD）单一控制部件向每个处理部件分派指令。同样的指令被所有的处理部件同时执行。多指令流多数据流（multiple instruction stream， multiple data stream， MIMD），用同一程序的多个实例在不同数据上执行。并行平台的通信模型

并行任务间有两种主要的数据交换方式：访问共享数据空间以及交换消息。

共享地址空间平台：支持SPMD编程的共享地址空间平台也称为多处理器（multiprocessor），如果处理器访问系统中任何内存字（全局或本地）的时间都相同，平台就归类为一致内存访问（uniform memory access，UMA）。消息传递平台：从计算机逻辑观点上说，消息传递平台由p个处理节点构成，每个节点都有自己的独立地址空间。运行在不同节点上的进程之间的交互必须用消息来完成，消息传递（message passing）。并行平台的物理组织理想并行计算机的体系结构

串行计算模型（随机访问计算机或RAM）的一种自然扩展包含p个处理器以及大小不受限制的全局内存，所有处理器同样可以访问该内存。所有处理器访问同样的地址空间，共享一个公用的时钟，但在每个周期内可以执行不同指令。并行随机访问计算机（parallel random access machine， PRAM）。

并行计算机互连网络互连网络提供多个处理节点之间或处理器与内存模块之间的数据传输的机制。互连网络氛围静态和动态两种。动态网络也称为非直接网络，其节点通过开关网络与其他节点相连。网络拓扑结构基于总线的网络包含一个所有节点公用的共享介质。总线的成本与节点数目p是线性关系。网络中任意两个节点间的距离是常数（O（1））。对于一般程序来说，大多数访问的数据对节点是本地的，对于这样的程序，可以为每个节点提供高速缓存，似有数据存放在节点的高速缓存中，只有远程数据才通过总线存取。交叉开关网络：一种非拥塞网络，连接一个处理节点与存储区不会拥塞其他任何处理节点与存储区之间的连接。要实现这样的网络，需要的开关节点总数为 θ ( p b ) \theta(pb) θ(pb),从成本的角度上讲，交叉开关网络的可扩展性不好。多级网络：（multistage interconnection network），比总线网络在性能方面的可扩展性强，又比交叉开关网络在成本上可扩展性强。omega网络是一种常用的多级互连网络，级数为logp，p是输入的数目，也是输出的数目。网络成本随 θ ( p l o g p ) \theta(plogp) θ(plogp)增加。在omega网络中，某一处理器对某一存储区的访问可能不允许其他处理器对其他存储区的访问，具有这种性质的网络称为阻塞网络（blocki network）。全连接网络：（completely-connected network），每个节点到其他所有节点都存在直接通信链路。全连接网络是交叉开关网络的静态对应网络，因为在这两种网络中，任意输入/输出对之间的通信都不会阻塞其他任何对之间的通信。星型连接网络：某一处理器作为中央处理器，其他的每个处理器有一条通信链路与中央处理器相连。中央处理器是星型结构的瓶颈。线性阵列、格网和k-d格网：k-d格网是一种拓扑结构，它有d维，每一维上有k个节点。一般而言，d维超立方体由连接两个(d-1)维超立方体的相应节点构成。基于树的网络：（tree network），是指网络中任意一对节点间只存在一条通路的网络。线性阵列和星型连接网络都是树网络的特例。静态互联网络评价直径：网络中任意两个处理节点之间的最长距离称为网络直径（diameter）连通性：（connectivity），连通性的一个度量是将一个网络分为两个不连通的网络需要删去的最少弧数目。对分宽度及对分带宽：（bisection width），是把网络分为两个相等网络时必须删去的最小通信链路数目。动态互连网络评价多处理器系统中的高速缓存一致性无效协议（invalidate）和更新协议（update），在变量的n个副本中，当处理器修改变量的一个副本时，要么必须使其他的副本无效，要么必须使其他的副本更新。假共享：（false sharing）不同的处理器更新相同高速缓存行中不同部分的情况。并行计算机的通信成本

决定通信延迟的主要参数有：

启动时间：在发送节点和接受节点处理消息所花费的时间每站时间：当消息离开一个节点后，需要花一定的时间到达路径上的下一个节点。消息头在两个直接连接的节点间传递所花费的时间称为每站时间，也称为节点延迟（node latency）每字传送时间

【本文地址】

公司简介

联系我们