多核结构与程序设计复习 2012年 杨全胜 http://www.njyangqs.com/ 东南大学成贤学院计算机系
复习 要掌握的概念 并发与并行计算的概念及区别 指令级并行、数据级并行和线程级并行。各自举例，多核系统并行更主要的是应用哪一级并行？ SMT和CMP的异同点 层次性存储结构和Cache映射策略 分布式存储、共享式存储和分布式共享存储的概念、优点和缺点。 开发并行软件的步骤、问题分解的方法、同步的类型
复习 要掌握的概念 负载均衡的概念，如何获得负载均衡？ 进程、线程的概念、状态和状态转换图 临界区的概念，多个线程进入临界区的限制，可以使多个线程操作临界区的时候满足这些限制的方法。 死锁的概念。产生死锁的的原因和必要条件，预防死锁的办法 OpenMP编程中的并行、同步、归约、调度等问题。
复习 有一只铁笼子，每次只能放入一只动物，猎手向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪，试用P、V操作写出能同步执行的程序。 猎手进程 农民进程 动物园进程 饭店进程 P(s) P(s) P(s1) P(s2) 放入虎 放入猪 买老虎 买猪 V(s1) V(s2) V(s) V(s) 其中S初值=1，S1=S2=0
复习 分析程序 设有两个优先级相同的进程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.
复习 请用OpenMP编写并行程序，在一个有200000个正整数的数组中查找数60，给出它在数组中的位置(假设该数组中只有一个60） 要求用同步的方法 为减少开销，要求不用同步的方法（提示：假设核数不大于10，用omp_get_num_procs()函数来获得核数，根据核数决定线程数。）
复习 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< 200000; i++){ location += find(i); location--；
复习 答 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;
复习 #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;
复习 数值积分法和蒙托卡罗法计算π值。（自看）