高级计算机体系结构第一次作.doc

计算机体系结构第一次作业 计算机学院 1.3 在PRAM模型上，假定算法A、B和C的执行时间分别为7n,nlogn/4和nloglogn,试问： 1）用大O 表示的时间复杂度是多少？ 2) 三个算法，何者最快？何者最慢？ 3）当n=1024时，三个算法何者最快？何者最慢？ 4）如何解释上述1）和3）的不同结论？ 答：(1)算法A、B和C的时间复杂度分别为O（n）、O（nlogn）和O（nloglogn）。 (2)算法A执行的最快，算法B执行的最慢。原因：当n的值足够大时，O（n）O（nloglogn）O（nlogn）。所以算法A执行的最快，算法B执行的最慢。 (3)当n=1024时，7nnloglognnlgon/4，所以，算法B最快，算法A最慢。 (4) 实际程序计算中，n的值一般都比较大（远大于1024=210），然而当n=1024时，logn可能仍然大于1，却小于10，所以loglogn的值小于1，从而n nlogn. 也就是说，时间复杂度是数量级的概念，忽略了常数系数，而3) 是计算出具体结果，因此会有差别。 所以结论不同。 1.8 给出如下串行程序代码段： for(i=0;iN;i++) A[i] = b[i]*b[i+1]; for(i=0;iN;i++) C[i] = A[i]+A[i+1]; 试用库例程方式，写出其等效的并行代码段； id=my_process_id(); p=number_of_processes(); for ( i= id; iN; i=i+p) A[i]=b[i]*b[i+1]; barrier(); for (i= id; iN; i=i+p) c[i]=A[i]+A[i+1]; 试用Fortram 90中的数组操作，写出其等效的并行代码段； my_process_id,number_of_processes(), and barrier() A(0:N-1)=b(0:N-1)*b(1:N) c=A(0:N-1)+A(1:N) 试用SGI PowerC Program, 写出其等效的并行代码段。 #pragma parallel #pragma shared(A,b,c) #pragma local(i) { # pragma pfor iterate(i=0;N;1) for (i=0;iN;i++) A[i]=b[i]*b[i+1]; # pragma synchronize # pragma pfor iterate (i=0; N; 1) for (i=0;iN;i++)c[i]=A[i]+A[i+1]; } 2.1 计算执行程序的有效CPI、MIPS速率及总的CPU执行时间。（图表省略） 答： CPI为执行每条指令所需要的平均的时钟周期数。所以，CPI为： CPI=(45000*1+32000*2+15000*2+8000*2)/(45000+32000+15000+8000) =1.55 MIPS=In/(Te*10^6)=Rc/(CPI*10^6) =25.8 Tcpu=In*CPI*Tc=(45000*1+32000*2+15000*2+8000*2)/(40*10^6) =3.785ms 2.2 计算 答： (1)在单处理机上执行该程序的平均CPI值为： 1*60%+2*18%+4*12%+8*10%=2.24 (2)计算相应的MIPS速率 MIPS=Rc/(CPI*10^6)=40*10^6/(2.24*10^6)=17.86 2.3 如题，计算： 1）渐近带宽r∞=? 2）半峰值信息长度 = ? [提示：to=46μs] 答：(1)渐近带宽r∞=1 / 0.035=28.6MB/S (2)半峰值消息长度m1/2=to* r∞=46us*28.6MB/S=1315.6B 2.9假设N=500，P=6，比照表2.12，试列出采用不同调度算法的结果 调度算法 任务分配粒度随时间的变化 静态调度 84 84 84 84 84 84 84 84 84 84 84 84 SS 1 1 1 1 1 1 1 1 1 1 1 1 BSS(k=20) 20 20 20 20 20 20 20 20 20 20 20 20 GSS 83 69 56 47 39