高级计算机体系结构第一次作.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)当nnloglognnlgon/4，所以，算法B最快，算法A最慢。(4) 实际程序计算中，n的值一般都比较大（远大于1024=210），然而当n=1024时，logn可能仍然大于1，却小于10，所以loglogn的值小于1，从而n nlogn. 也就是说，时间复杂度是数量级的概念，忽略了常数系数，而3) 是计算出具体结果，因此会有差别。 所以结论不同。1.8 给出如下串行程序代码段： for(i=0;iN;i+) Ai = bi*bi+1; for(i=0;iN;i+) Ci = Ai+Ai+1;1) 试用库例程方式，写出其等效的并行代码段；id=my_process_id();p=number_of_processes();for ( i= id; iN; i=i+p) Ai=bi*bi+1;barrier();for (i= id; iN; i=i+p) ci=Ai+Ai+1;2) 试用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)3) 试用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+) Ai=bi*bi+1; # pragma synchronize # pragma pfor iterate (i=0; N; 1) for (i=0;iN;i+)ci=Ai+Ai+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*106)=Rc/(CPI*106) =25.8 Tcpu=In*CPI*Tc=(45000*1+32000*2+15000*2+8000*2)/(40*106) =3.785ms2.2 计算答： (1)在单处理机上执行该程序的平均CPI值为： 1*60%+2*18%+4*12%+8*10%=2.24(2)计算相应的MIPS速率MIPS=Rc/(CPI*106)=40*106/(2.24*106)=17.86 2.3 如题，计算： 1）渐近带宽r=? 2）半峰值信息长度 = ? 提示：to=46s 答：(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，试列出采用不同调度算法的结果调度算法任务分配粒度随时间的变化静态调度848484848484848484848484SS111111111111BSS(k=20)202020202020202020202020GSS836956473932272219161311FS424242424242212121212121TSS(d=2)424038363432302826242220AS1412108765