第一章并行计犷机模 1计算技术的现状 2多处理机和多计算机 23多向量机和S|MD计算机 4并行计算机的抽象模型 25可扩展的范围和设计
2 第一章 并行计算机模型 ◼ 1 计算技术的现状 ◼2 多处理机和多计算机 ◼ 3 多向量机和SIMD计算机 ◼ 4 并行计算机的抽象模型 ◼ 5 可扩展的范围和设计
2多处理机和多计算机 、共享存储型多处理机 1.UMA模型 UMA--Uni form Memory Access 结构和特点:
3 2 多处理机和多计算机 ◼ 一、共享存储型多处理机 ◼ 1. UMA模型 ◼ UMA --Uniform Memory Access ◼ 结构和特点：
处理机 系统互连 (总线,交叉开关,多级网络) SM SMm 共享存储器 UMA多处理机模型
4
紧耦合系统( tightly coup led system a多处理机由于高度资源共享 口系统的互连采用总线、交叉开关、或多 级网络形式 对称( symmetric)多处理机 a当所有处理机都能同样访问所有外 围设备时
5 ◼ 紧耦合系统(tightly coupled system) ❑ 多处理机由于高度资源共享 ❑ 系统的互连采用总线、交叉开关、或多 级网络形式 ◼对称(symmetric)多处理机 ❑当所有处理机都能同样访问所有外 围设备时
例 Fortran程序可在单处理机上顺序执 行,分析0PU的运行时间,假设条件: 所有数组A(),B(1),G(1)都有N个 元素; 分析:求和 Fortran程序
6 ◼ 例 Fortran程序可在单处理机上顺序执 行，分析CPU的运行时间，假设条件： ◼ 所有数组A(I)，B(I)，C(I)都有N个 元素； ◼ 分析：求和Fortran程序
L1: Do 10I=1, N L2:A(I)=B(I)+c() L3: 10 Continue L4: SUM=0 L5: Do 20J=1, N L6: SUM=SUM+A(J) L7: 20 Continue 假定取指令和加载数据的开销可以忽略不 计 口所有数组已经装人主存储器,并且短程序段 已经装入高速缓冲存储器。 忽略总线争用或存储器存取冲突问题
7 ◼ L1: Do 10 I＝1，N ◼ L2: A(I)＝B(I)+C(I) ◼ L3:10 Continue ◼ L4: SUM＝0 ◼ L5: Do 20 J＝1，N ◼ L6: SUM＝SUM+A(J) ◼ L7:20 Continue ◼ 假定取指令和加载数据的开销可以忽略不 计； ❑ 所有数组已经装人主存储器，并且短程序段 已经装入高速缓冲存储器。 ◼ 忽略总线争用或存储器存取冲突问题
再假设: 执行代码行L2,L4和L6,每行要用一个 机器周期。 执行程序控制语句L1,L3,L5和L7所需 的时间可以忽略。 假定经过共享存储器的处理机之间的每 次通信操作需要k个周期。 结论:CPU用2N个周期
8 ◼再假设： ◼ 执行代码行L2，L4和L6，每行要用一个 机器周期。 ◼ 执行程序控制语句L1，L3，L5和L7所需 的时间可以忽略。 ◼ 假定经过共享存储器的处理机之间的每 次通信操作需要k个周期。 ◼结论：CPU用2N个周期
串行程序并行化 在M一处理机系统上执行程序 口将循环操作划分成M段,每段有 L=N/M个元素 口假设经过共享存储器的处理机 之间的每次通信操作需要 k个周期
9 串行程序并行化 ◼在M—处理机系统上执行程序 ❑将循环操作划分成M段，每段有 L＝N／M个元素。 ❑假设经过共享存储器的处理机 之间的每次通信操作需要： ◼ k个周期
Doa||表示所有M段在M台处理机上 并行执行 Doall k=1. m Do 10I=L(k-1)+1, kLo A(=B(+C( 10 Continue SUM(K=0 Do 20J=1. L SUM(K=SUM(K)+ A(L(k-1)+J 20 Continue 口 ENDall 10
10 ◼ Doall表示所有M段在M台处理机上 并行执行 ◼ Doall k＝1，M ◼ Do 10 I＝L(k-1)+1，kL。 ◼ A(I)＝B(I)+C(I) ◼ 10 Continue ◼ SUM(k)＝0 ◼ Do 20 J＝1，L ◼ SUM(k) = SUM(k) + A(L(k-1)+ J) ◼ 20 Continue ◼ ENDall
分析: 口循环1是L个周期;循环2是L个周期 口总时间: 2L+h(k+1)=2NM+(k+1)|og2M
11 ◼ 分析： ❑ 循环1是L个周期；循环2是L个周期 ❑ 总时间： ◼ 2L+ h(k+1)=2N/M+(k+1) log2M