文档介绍：第二章并行计算基础
组成并行计算机的各个部分:
节点(node):每个节点由多个处理器构成,可以直接进行输入输出(I/O)操作;
互联网络(work):所有节点通过互联网络相互连接通信;
内存(memory):内存由多个存储模块组成
1、与节点对称的分布在互联网络的两侧;
2、位于各个节点的内部。
第二章并行计算基础
内存模块与节点分离
内存模块位于节点内部
多级存储体系结构
解决内存墙(memory wall)性能瓶颈问题;
节点内部的cache称为二级cache(L2 cache);
处理器内部更小的cache成为一级cache(L1 cache);
L1 cache连接CPU寄存器和L2 cache,负责缓存L2 cache中的数据到寄存器中。
多级存储体系结构
并行计算机的多级存储结构主要包括两个问题:
Cache的映射策略,即cache如何从内存中取得数据进行存储;
节点内部或者节点之间内存的访问模式。
cache原理,cache以cache线为基本单位,每条cache包含L个字,每个字8个字节。例如,L=4,则表示cache线包含4*8=32个字节。内存空间分割成块(block),每个块大小与cache线长度一致,数据在内存和cache之间的移动以cache线为基本单位。
For i=1 to M
A[i]=A[i]+2*B[i]
如果操作数存在cache中,称该次访问是命中的,否则,该次操作是“扑空”的。
多级存储体系结构
cache的映射策略(内存块和cache线之间如何建立相互映射关系):
直接映射策略(direct mapping strategy):每个内存块只能被唯一的映射到一条cache线中;
K-路组关联映射策略(K-way set association mapping strategy):Cache被分解为V个组,每个组由K条cache线组成,内存块按直接映射策略映射到某个组,但在该组中,内存块可以被映射到任意一条cache线;
全关联映射策略(full association mapping strategy):内存块可以被映射到cache中的任意一条cache线。
访存模型
UMA(Uniform Memory Access)模型:该模型内存模块与节点分离,分别位于互联网络的两侧
物理存储器被所有节点共享;
所有节点访问任意存储单元的时间相同;
发生访存竞争时,仲裁策略平等对待每个节点,即每个节点机会均等;
各节点的CPU可带有局部私有高速缓存;
外围I/O设备也可以共享,且每个节点有平等的访问权利。
访存模型
NUMA(Non-Uniform Memory Access)模型:该模型内存模块分布在各个节点内部,所有局部内存模块均构成并行计算机的全局内存模块。内存模块在物理上是分布的,在逻辑上是全局共享的,这种模型也称之为“分布式共享访存模型”
物理存储器被所有节点共享,任意节点可以直接访问任意内存模块;
节点访问内存模块的速度不同,访问本地存储模块的速度一般是访问其他节点内存模块的3倍以上;
发生访存竞争时,仲裁策略对节点可能是不等价的;
各节点的CPU可带有局部私有高速缓存(cache);
外围I/O设备也可以共享,但对各节点是不等价的。
访存模型
COMA(Cache-Only Memory Access)模型:全高速缓存存储访问模型
各处理器节点中没有存储层次结构,全部高速缓存组成了全局地址空间;
利用分布的高速缓存目录进行远程高速缓存的访问;
COMA中的高速缓存容量一般都大于2级高速缓存容量;
A时,数据开始时可以任意分配,因为在运行时它最终会被迁移到要用到它的地方。
并行计算模型
SIMD同步并行计算模型
共享存储的SIMD模型(PRAM模型);
分布存储的SIMD模型(SIMD互联网络模型)
MIMD异步并行计算模型
异步PRAM模型
BSP模型
LogP模型
C3模型
同步并行计算模型
SIMD共享存储模型假定存在着一个容量无限大的共享存储器,有有限或无限个功能相同的处理器,且均具有简单的算术运算和逻辑判断功能,在任何时刻各处理器均可通过共享存储单元相互交换数据。
SIMD共享存储模型(PRAM模型)
PRAM-EREW (Exclusive-Read and Exclusive-Write),不允许同时读和同时写;
PRAM-CREW (Concurrent-Read and Exclusive-Write) ,允许同时读但不允许同时写;
PRAM-CRCW (Concurrent-Read and Concurrent-Write) ,允许同时读和同时写。
优点:
适合于并行算法的表达、分析和比较;
使用简单,很多诸如处