并行计算机体系结构

《并行计算机体系结构》由会员分享，可在线阅读，更多相关《并行计算机体系结构（18页珍藏版）》请在金锄头文库上搜索。

1、第 2 章并行计算机体系结构内容提要：2.1并行机网络互联拓扑结构2.2并行机访存模型与多级存储结构2.3并行机分类2.4并行机举例2.5并行计算机的发展史并行机网络互联拓扑结构 参考资料： 文献 1: 第节： 文献 2 ：详细阐述; 当代并行机拓扑结构: 并行机体系结构的几个要素： 结点：包含一个或多个 CPU, 这些 CPU 通过 HUB 或全互联交叉开关相互联接, 并共享内存，也可以直接与外部进行I/O操作： 路由器：联接讣算结点与互联网络，负责数据在结点间的路由寻址； 互联网络：将所有路由器以某种拓扑结构相互联接，保证它们之间可以自由地通 信。互联网络： 拓扑结构：将并行机各结点之间物

2、理上相互联接的关系用图来表示，其中图中结 点代 表并行机的结点，图中连线代表它所联接的两个结点的路由器之间存在物理 上的直接 联接关系，我们称该图为并行机互联网络拓扑结构： 拓扑结构的几个重要定义： 并行机规模：并行机包含的结点总数，或者包含的CPU总数： 结点度：互联网络拓扑结构中联入或联出的一个结点的边的条数，称为该结 点的 度： 结点距离：两个结点之间跨越的图的边的条数： 网络宜径：网络中任意两个结点之间的最长距离： 点对点带宽：图中边对应的物理联接的物理带宽： 点对点延迟：图中任意两个结点之间的一次零长度消息传递必须花费的时间。 延 迟与结点间距离相关，英中所有结点之间的最小延迟称为网

3、络的最小延迟, 所有 结点之间的最大延迟称为网络的最大延迟： 折半宽度：对分网络成两个部分（它们的结点个数至多相差 1）所必须去掉的 边 的网络带宽的总和； 总通信带宽：所有边的带宽之和； 互联网络评价： 大：结点度、点对点带宽、折半宽度、总通信带宽； 小：网络直径、点对点延迟：互联网络的分类：静态拓扑结构、动态拓扑结构、宽带互联网络； 静态拓扑结构：结点之间存在固泄的物理联接方式，程序执行过程中，结点间的 点 对点联接关系不变，例如：文献1： P10-P11,给出各类泄义的具体值，文献2详细 讨论: 一维阵列（Array）、环（Ring）； 多维网格（Mesh）、多维环（Torus）： 树（

4、Tree）：二叉树、X-树、星树、胖树： 超立方体（ Hypercube） ; 动态拓扑结构：结点之间无固左的物理联接关系，而是在联接路径的交叉点处用 电子 开关、路由器或仲裁器等提供动态联接的特性，主要包含单一总线、多层总 线、交叉 开关、多级互联网络： 单-总线：联接处理器、存储模块和I/O设备等的一组导线和插座，在主设备（处理器）和从设备（存储器）之间传递数据，特征有： 公用总线以分时工作为基础，各处理器模块分时共享总线带宽，即在同 一个 时种周期，至多只有一个设备能占有总线； 总线带宽二总线主频X总线宽度，例如ASUS主板的总线频率=150MHz,总线 宽度为 64 位，则该总线的带宽

5、审；监听协议与仲裁算法：选择哪个设备占有总线； 例如：微机主板外部数据总线、PCI总线、ASCI White每个结点包含16个 CPU, CPU之间通过总线共享局部存储器： 务层总线：各设备内部存在本地总线（结点、存储器、I/O设备），本地总线之间 以系统总线相互联接，系统总线一般在通信主板中实现，例如文献 1P14 图。 交义幵关（Crossbar Switcher）:所有结点通过交叉开关阵列相互连接，每个交叉 开关均为其中两个结点之间提供一条专用联接通路，同时，任意两个结点之间也 能找到一个交叉开关，在它们之间建立专用联接通路。交叉开关的状态可根据程 序的要求动态地设程为“开”和“关”。例

6、如 4x4 交叉开关联接 8 个结点（黑板 上画图说明）。交叉开关特征: 结点之间联接：交叉开关一般构成NxN阵列，但在每一行和每一列同时只 能有一个交叉点开关处于开”状态，从而它同时只能接通N对结点；结点与存储器之间的联接：每个存储器模块同时只允许一个结点访问， 故每一 列只能接通一个交叉点开关，但是为了支持并行存储访问，每一 行同时可 以接通多个交叉点开关。 交叉开关的成本为N2, N为端口数，限制了它在大规模并行机中的应用，一 般适合8-16个处理器的情形. 匕级联网络（MIN： Multistage Interconnection Network）:由多个单级交叉 开关 级联接尼来形成

7、大型交叉开关网络，相邻交叉开关级之间存在固定的物理联接拓 扑。为了在输入与输出之间建立联接，可以动态地设崟开关状态。 例如： 一般联接图：文献1图，其中ISC为该级互联网络，主要有混洗、蝶网、纵 横交叉等： （详细参考文献2） 蝶网、CCC网、Benes网：均为超立方体网络的推广，参考文献2的P215- P225。 Q网：等价于蝶网，参考文献1的P16图。 宽带互联网络： 快速以太网（10Mbps （82年）、100Mbps （94年）、lGbps （97年）：国际标 准，三代网络性能比较参考文献1的P18表，特征类似于单一总线： 分时共享、竞争仲裁：带宽100Mbps, 8台处理机共享，每台

8、处理机的平均带 宽为 Mbps。 FDDI：光纤分布式数据接口（Fiber Distributed Data Interface）采用双向光纤 令牌 环，所有结点联接在该环中，提供100-200Mbps数据传输速度，双向环提供冗余 通路以提供可靠性，距离可达 100米、2公里、60公里等，比快速以太网具有更 好的可靠性、适应性； Switcher：交叉开关，可同时为N/2对端口提供100Mbps的宜接联接通路，英 中 N为端口总数。多个Switcher堆叠（不多于7个）可形成多级Switcher。Beowulf 微机机群采用这种结构互联所有结点。（参考张林波讲义之图）。 ATM：异步传输模式（

9、ATM： Asynchronous Transfer Mode）是在光纤通信基础 上建立起来的一种新的宽带综合业务数字网的交换技术。介质无关的信息传输协 议，采用53字节的龙长短数据单元（cell）进行传输。大的数据包 进入ATM网 络时，分解成多个定长的单元，各个单元独立传输，到达目的地址后，这些单元 汇集成原来的数据包。ATM网络适合髙速度传输声音、图像、视频和数据等的所 有形式的媒体。 Mvrinet:专用机群互联网络，带宽可达200MB/秒，延迟小于10us。Infiniband ：专用机群互联网络，带宽可达秒，延迟小于 6us 。Qudrics: 专用机群互联网络，带宽可达 400M

10、B/ 秒，延迟小于 6us 。 HiPPI：髙性能并行接口（High Performance Parallel Interface） ,1993年标准（）形 成。单工点对点的数据传输界而，带宽可达 800Mb/so互联网络的路由选择算法： 定义： 数据包（Packet）：结点间数据在网络中传输的最小单位，一般为几十个、或者 几百个字节。 路由选择算法：网络中数据包传输的路径选择。 申请队列长度：在某条边上等待传输的数据包的个数。 常用路由选择算法： 贪心法：每个数据包沿最短路径传输（二维阵列举例），该方法容易在某一条 边上形成通信阻塞。 动态路由选择算法：数据包根据当前边的申请队列长度，动态地

11、改变传输路 径。 虫孔算法（Wormhole）：数据包分解为长度更小的字肖流，所有字节流在网络 中按动态路由选择算法在网络中传输，最后在目的地址合并还原成数据包。作业： 作业：假设网络包含P=2n=M3个结点，请给出一维阵列（环）、二维网格（Torus）、三维网格（Torus）、超立方体、二叉树（叶结点个数为P）、蝶网、 Benes 网的结点 度、点对点延迟（以跨越的边的条数为单位）、折半宽度（以边的条 数为单位）、 网络直径。 作业：假设存在 8个结点，分别联接在 lGbps 的快速以太网和 100Mbps 的 24端口 的 Switcher上，请问任意两个结点间的平均带宽为多少，如果结点数

12、增加一倍，则平均 带宽又为多少。并行机存储结构参考资料： 文献1:第节： 文献8、文献10； 并行机存储模块内存模块与结点分离结点0结点P图内存模块局部于结点内部结点0CPU0CPU1J tCacheCache结点PHUB 目 Mi-Router互联网络并行机访存模型 均匀访存模型（UMA： Uniform Memory Access）：内存模块与结点分离，分别位 于 互联网络的两侧（图），互联网络一般采用系统总线、交叉开关和多级网络，称 之 为紧耦合系统（ Tightly Coupled System） -具有如下特征:物理存储器被所有结点均匀共享；所有结点访问任意存储单元的时间相同； 访存

13、竞争时，仲裁策略对每个结点均是机会等价的； 各结点的CPU可带有局部私有高速缓存（Cache）：外围I/O设备也可以共享，且对各结点等价。 北均匀访存模型（NU2IA： Nonuniform Memory Access）：内存模块局部在各个结 点内部（图），所有局部内存模块构成并行机加全局内存模块。具有如下特征： 任意结点可以直接访问任意内存模块： 结点访问内存模块的时间不一致：访问本地存储模块的速度一般是访问其他 结点内存模块的 3倍以上：访存竞争时，仲裁策略对结点可能是不等价的： 各结点的CPU可带有局部私有髙速缓存（Cache）；外围 I/O 设备也可以共享。 Cache 一致性非均匀访

14、存模型（CC-NUMA： Coherent-Cache Nonuniform MemoryAccess）：存在专用硬件设备保证在任意时刻，冬结点Cache中数据与全局内存数据 的一致性，具有特征： 各 CPU 的局部 Cache 数据来源于全局内存，并保证所有结点中数据的一致性（画图简单说明）：大多数访存可以局部在本地高速 Cache； 基于目录的 Cache -致性协议（ Cache 原理参考下章）。 分布式访存模型（DMA： Distributed Memory Access）：各个结点的存储模块只能 被 局部CPU访问，其他结点无法直接访问局部存储模块，称之为分布式存储（图），具 有特征： 内存模块分布局部于各个结点，每个结点只能直接访问其局部存储模块，对 其他 结点的内存访问只能通过消息传递程序设计来实现； 每个结点均是一台由处理器、存储器、I/O设备组成的自洽计算机。500MHz Pentium-Ill Cluster多级存储结构:CPU寄存器本地局部内存一级Cache 二级 CacheIchip(MPI消息传递)访存延迟比例：容量(B)带宽(MB/s)延迟(ns)2566000处理机32K512K500M海量40002000120032080每位成本增加100100,000 微机机群1 : 3 : 40 : 160 : 50,000 Origin 200