多核程序设计：第二章 并行计算基础.ppt

*
第二章 并行计算基础
小节
章节
重点内容

关于并行计算
什么是并行计算，怎么并行计算

并行计算机体系结构
多级存储体系，Cache，并行访存模型。

并行计算模型
同步并行计算和异步生的。运用共享资源分布式计算的知识实现的关于动态任务调度的并行模式就是动态任务调度模式，它的突出特点就是可以实现并行计算。
*
并行计算机体系结构
组成并行计算机的各个部分：
节点（node）：每个节点由处理器构成，可以直接输入输出。
互联网络（interconnect network）：所有节点通过互联网络相互连接通信。
内存 （memory）：由多个存储模块组成。
*
并行计算机体系结构
内存模块与节点分离
内存模块位于节点内部
*
多级存储体系结构
内存墙性能瓶颈问题：
微处理器发展得益于主频和流水线技术，仍然遵循摩尔定律，
内存模块的容量也以每年几乎翻一番的速度发展
但是内存访问速度相对较慢，数据存取速度难以满足微处理器的峰值计算速度
解决方法就是在内存和处理器之间增加一个高速缓存cache
*
多级存储体系结构
在下面的多级存储模型中，从下往上，每个字节的成本越来越高，但访存延迟越来越小，带宽越来越高。
多级存储体系结构
Cache分类：目前有多级Cache
在节点内部的cache称为二级cache（L2 cache）。
在处理器内部更小的cache称为一级cache（L1 cache）。
L1 cache连接CPU寄存器和L2 cache，负责缓存L2 cache中的数据到寄存器中。
多级存储体系结构
Cache的主要功能
解决内存墙性能瓶颈问题
主要实现方法
提高cache命中率，即减少访问内存的次数
cache命中率：程序执行过程中cache命中的总次数和内存访问总次数的比值
方法依据
程序的数据访问具有局部性
时间局部性
空间局部性
*
多级存储体系结构
Cache的原理
cache以cache线为基本组成单位，每条cache线包含L个字，每个字为8个字节。内存空间分割成块，每块大小与cache线长度一致。数据在内存和cache之间的移动以cache线为基本单位。
Cache的基本问题
映射规则
查找方法
替换方法
写策略
*
多级存储体系结构
Cache的映射策略
直接映射策略（direct mapping strategy）
每个内存块只能唯一的映射到一条cache线中
K－路组关联映射策略
Cache被分解为若干个组，每个组由K个Block组成，内存块按Cache组数进行分块
组间直接映射，组内全相联映射
全关联映射策略
内存块可以被映射到Cache中的任意Cache线
Hall? Cubicle? Study room?
*
More chances
Easy to be found
Hard to be found
Could be occupied
Cache organization
全相联
直接映射
组相联
*
Big hall
Cubicle
Classroom
多级存储体系结构
写策略
命中时：
写直达（write through）
写回（write back）
失效时：
按写分配 (write allocate)
不按写分配 (no-write allocate)
*
程序结构与Cache效率---循环交换
每次访问间隔100个元素
for (k = 0; k < 100; k = k+1)
for (j = 0; j < 100; j = j+1)
for (i = 0; i < 5000; i = i+1)
a[i][j] = 2 * a[i][j];
连续访问100个元素
for (k = 0; k < 100; k = k+1)
for (i = 0; i < 5000; i = i+1)
for (j = 0; j < 100; j = j+1)
a[i][j] = 2 * a[i][j];
改善空间局部性提高命中率
*
程序结构与Cache效率----循环融合
访问a、c时2次miss
for (i = 0; i < N; i = i+1)
for (j = 0; j < N; j = j+1)
a[i][j] = 1/b[i][j] * c[i][j];
for (i = 0; i < N; i = i+1)
for (j = 0; j < N; j = j+1)
d[i][j]