并行计算机存储结构多级存储体系结构为了解决存储墙memorywall.ppt

* 并行程序设计相关问题 数据依赖 循环引起的数据依赖 for (i = 1;i100;i++) a[i] = a[i-1]*32 循环独立但数据是依赖的  task 1 task 2 ------ ------  X = 2 X = 4  . . . .  Y = X^2 Y = X^3 * 并行程序设计相关问题 数据依赖 如何处理数据依赖: 分布式存储结构- 通信要求数据在同步点上。 共享存储结构-在任务间采用同步“读/写”操作 * 并行程序设计相关问题 负载均衡 负载均衡 是指在任务之间分发工作的方法，该方法要所有的任务在所有的时候保持忙 负载均衡对于并行程序的性能是很重要的。 * 并行程序设计相关问题 如何获得负载平衡 相等地划分每个任务所接受的工作 对于数组和矩阵操作每个任务完成相似的工作，在任务间均衡地分布数据集。 对于循环迭代，让每次迭代的工作相似，在任务间均衡地分布迭代。 如果使用不同性能特性的不同机制的混合，确定使用一些性能分析工具来发现任何负载的不均衡，并相应调整工作。 * 并行程序设计相关问题 如何获得负载平衡 使用动态工作指派 即使数据在任务间均衡分布，有些类型的问题依然会引起负载不均衡 当任务要执行的工作量是变化的，或者是不可预测的时候，使用一个诸如任务池的调度器是有帮助的。每个任务完成自己的工作后，从队列中获得新的工作 可能有必要设计一个算法来检测和处理在代码中动态发生的负载不均衡问题。 * 并行计算基础 内容 什么是并行计算 弗林经典分类 并行计算机存储结构 并行编程模型 并行程序设计相关问题 程序性能优化方法 * 程序性能优化方法 性能评估 Amdahl定律 * 程序性能优化方法 性能评估 Amdahl定律 程序潜在的加速(speedup)是用的可并行的那部分code(P)来定义的Sspeedup = 1/(1-P) 如果代码没有任何部分可并行，P = 0 并且 speedup = 1 (没有加速). 如果所有的代码都可以并行，P = 1 并且speedup是无穷 (理论上). 如果一半的代码可以并行化，则最大的speedup = 2, 意味着代码会以2倍的速度执行。 * 程序性能优化方法 性能评估 Amdahl定律 引入执行并行部分工作的处理器的个数，这时P = 并行部分, N = 处理器个数并且 T = 串行部分=1-P, 上述公式可以改成: * 程序性能优化方法 串行程序性能优化 调用高性能的库函数，比如BLAS，FFTW等. 是用合适的编译器优化选项。 合理定义数组维数 … S个(多体交叉存储) int a[m][n]; for(i=0,iM,i++) a[i][j]=… //n和S是什么关系比较好？ C语言中的数组是行主序的 * int a[128][40960]; int b[128][40960]; for(int i=0;i128;i++) { for(int j=0;j40960;j++) a[i][j] = b[i][j]; } for(int i=0;i40960;i++) { for(int j=0;j128;j++) a[j][i] = b[j][i]; } 程序性能优化方法 嵌套循环的顺序对于数据访问的局部性是很重要的 * int a=0; for(int i=0;i100000000;i++) { for(int j=0;j5;j++) a ++; } for(int i=0;i5;i++) { for(int j=0;j100000000;j++) a ++; } 程序性能优化方法 嵌套循环的顺序对于数据访问的局部性是很重要的 * 程序性能优化方法 for(i=0;in;i++) for(j=0;jn;j++) a[i]+=b[j]; for(j=0;jn;j+=s) for(i=0;in;i++) for(jj=j;jjmin(j+s-1,n);jj++) a[i]+=b[jj] 数据分块 * 程序性能优化方法 for(i=0;in;i++) d+=a[i]; for(i=0;i(n%4),i++) d+=a[i]; for(i=((n%4)+1);in;i+4) d+=a[i]+a[i+1]+a[i+2]+a[i+3]; 循环展开 * 程序性能优化方法 并行程序性能优化 减少通信量，提高通信粒度 在全局