Lec6 程序优化 习题

计算机系统院系 学号 姓名 授课教师 密封线一、 单项选择题（每小题1分，共20分）1. 二、 填空题 ( 每空1 分，共 10 分 )1. 3. 三、 判断对错（每小题1分，共10分，在题前打 X 符号）1.2. 四、简答题2. 列举几种程序优化的方法，并简述其原理。至少2种，每种2.5分1） 代码移动，通过将代码从循环中移出减少计算执行的频率（编译优化）2） 用简单方法替代复杂操作，如移位、加替代乘法/除法（编译优化）3） 共享共用子表达式，重用表达式的一部分（编译优化）4) 减少过程调用（编译优化）5) 消除不必要的内存引用（编译优化）6) 循环展开，局部变量累积（编译优化，CPU指令并行优化）7） 减少分支，如可以用条件表达式替代if-else（防止流水线PC取错造成的影响）8） 调整循环次序，充分利用缓存（Cache优化）9） 利用速度更快的CPU指令，如浮点数计算指令SIMD六、综合设计题（每小题10分，共20分）1. 程序优化: 矩阵cn,n = an,n * bn,n ，采用 48题 I7 CPU。块64B。 for(int i=0;in;i+) for(int j=0;jn;j+) ci,j=0; for(int k=0; kn;k+)ci,j+=ai,k*bkj; 请针对该程序进行速度优化，写出优化后的程序，并说明优化的依据。代码优化，三个思路：编译优化、CPU优化、缓存优化编译优化：尽量用局部变量，减少不必要的内存访问；循环展开，减少循环边界检查CPU优化：尽量制造指令并行（流水），方法也是循环展开，多路累积 for(int i=0;in;i+) for(int j=0;jn;j+) acc1=0; acc2=0; for(int k=0; klen;/* 获取向量中指定下标的元素值，保存在指针参数val中*/int get_vec_element(*vec v, size_t idx, float *val)if (idx = v-len)return 0;*val = v-dataidx;return 1;/*计算向量元素的和*/void vector_sum(vec *v, float *sum) long int i; *sum = 0;/初始化为0 for (i = 0; i vec_length(v); i+) float val;get_vec_element(v, i, &val);/获取向量v中第i个元素的值，存入val中*sum = *sum + val; /将val累加到sum中 编译优化：1. 代码移动（移出循环），vec_length(v)2. 减少函数调用，get_vec_element(v,i,&val)3. 减少不必要的内存引用，指针*sum = *sumCPU优化：1. 使用循环展开，多路累积采用任一种优化方法都10分void vector_sum(vec *v, float *sum) long int i; long int length = vec_length(v); float *d = get_vec_start(v); float t = 0; for (i = 0; i length; i+) t = t + di; *dest = t;把函数vec_length移到循环外 避免每个循环的边界检查 用临时/局部变量累积结果3. 现代超标量CPU X86-64的Cache的参数s=5，E=1，b=5，若M=N=64, 请优化如下程序，并说明优化的方法（至少CPU与Cache各一种）。void trans(int M, int N, int AMN, int BNM) for (int i = 0; i M; i+) for (int j = 0; j N; j+) Bji =Aij; 面向CPU的优化方式：指令级并行，可以用循环展开面向Cache的优化：主要采用矩阵分块的代码优化方式优化的说明合理可行CPU 循环展开void trans(int M, int N, int AMN, int BNM