多核结构与程序设计复习 2012年 杨全胜 http://www.njyangqs.com/ 东南大学成贤学院计算机系.

Presentation on theme: "多核结构与程序设计复习 2012年 杨全胜 http://www.njyangqs.com/ 东南大学成贤学院计算机系."— Presentation transcript:

1 多核结构与程序设计复习 2012年 杨全胜 东南大学成贤学院计算机系

2 复习 要掌握的概念 并发与并行计算的概念及区别 指令级并行、数据级并行和线程级并行。各自举例，多核系统并行更主要的是应用哪一级并行？
SMT和CMP的异同点 层次性存储结构和Cache映射策略 分布式存储、共享式存储和分布式共享存储的概念、优点和缺点。 开发并行软件的步骤、问题分解的方法、同步的类型

3 复习 要掌握的概念 负载均衡的概念，如何获得负载均衡？ 进程、线程的概念、状态和状态转换图
临界区的概念，多个线程进入临界区的限制，可以使多个线程操作临界区的时候满足这些限制的方法。 死锁的概念。产生死锁的的原因和必要条件，预防死锁的办法 OpenMP编程中的并行、同步、归约、调度等问题。

4 复习 有一只铁笼子，每次只能放入一只动物，猎手向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪，试用P、V操作写出能同步执行的程序。 猎手进程    农民进程    动物园进程      饭店进程    P(s)        P(s)        P(s1)          P(s2)    放入虎     放入猪       买老虎         买猪    V(s1)       V(s2)       V(s)           V(s) 其中S初值=1，S1=S2=0 

5 复习 分析程序 设有两个优先级相同的进程P1和P2如下（不考虑时间片轮转），S1和S2初值均为0，求：P1，P2并发执行结束后，x,y,z分别是多少？要给出分析过程。            进程P1                  进程P2            y:=4;                      x:=1;            P(s1);                    V(s1);            z:=x+2;                  x:=x+1;            V(s2);                     P(s2)            y:=z-y;                  z:=z+y+x; 解：因为P1、P2是并发进程，所以P1和P2调度顺序不确定。假设P1先执行，当P1执行到P(s1)时，s1=-1，P1阻塞，此时当调度程序调度到P2时，P2在执行V(s1)时，唤醒P1,不阻塞而继续执行，当执行到P(s2)时，阻塞，此时，X=2, 然后执行到P(s2)p2阻塞，P1可以顺利执行完，此时Y=0,z=4;当P2再次被唤醒、调度时，继续执行P2的最后一处语句，此时y=0，z=4.所以最后结果是：x=2,y=0,z=6.如果P2先执行，结果同上 最后结果是：x=2,y=0,z=6.

6 复习 请用OpenMP编写并行程序，在一个有200000个正整数的数组中查找数60，给出它在数组中的位置(假设该数组中只有一个60）
要求用同步的方法 为减少开销，要求不用同步的方法（提示：假设核数不大于10，用omp_get_num_procs()函数来获得核数，根据核数决定线程数。）

7 复习 1）用同步的方法 int a[200000]={…}; static long num_steps=200000;
int location =0; int find(int x) { If(a[x] == 60) return(x+1); } return(0); void main() { int i; #pragma omp parallel for reduction(+:sum) for (i=0; i< ; i++){ location += find(i); location--；

8 复习 答 int a[200000]={…}; int found = 0, lfound[10]={-1，-1，-1，-1，-1，-1，-1，-1，-1，-1}; int Ncore = omp_get_num_procs ()； int nstep=200000/Ncore;

9 复习 #pragma omp parallel for for (k=0;k<Ncore;k++){
for(j=k*nstep; j< (k+1)*nstep;j++) { if(a[j]==60){ lfound[k]= j ; } for (i=0;i<Ncore;i++) if(lfound[i]!=-1) found=lfound[k] return found;

10 复习 数值积分法和蒙托卡罗法计算π值。（自看）