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