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

1、计算机体系结构第一次作业计算机学院1.3 在 pram 模型上，假定算法a、b 和 c 的执行时间分别为7n,nlogn/4和 nloglogn, 试问：1 ) 用大o 表示的时间复杂度是多少？2) 三个算法，何者最快？何者最慢？3) 当 n=1024 时，三个算法何者最快？何者最慢？4) 如何解释上述1 )和 3) 的不同结论？答：算法 a、b 和 c 的时间复杂度分别为0 ( n) 、0 ( nlogn ) 和 0 ( nloglogn ) 。(2) 算法 a 执行的最快， 算法 b 执行的最慢。 原因：当 n 的值足够大时， 0( n) 0 ( nloglogn ) 0 ( nlogn

2、) 。所以算法a 执行的最快，算法b 执行的最慢。(3) 当 nnloglognnlgon/4 ，所以，算法b 最快，算法a 最慢。(4) 实际程序计算中，n 的值一般都比较大( 远大于 1024=2 10)，然而当 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) 试用

3、库例程方式，写出其等效的并行代码段；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,

4、 写出其等效的并行代码段。#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=(4500

5、0*1+32000*2+15000*2+8000*2)/(45000+32000+15000+8000) =1.55 mips=i n/(te*10a6)=rc/(cpi*10w) =25.8 tcpu=i n*cpi*tc=(45000*1+32000*2+15000*2+8000*2)/(40*10a6) =3.785ms 2.2 计算答：(1) 在单处理机上执行该程序的平均cpi 值为：1*60%+2*18%+4*12%+8*10%=2.24 (2)计算相应的mips 速率mips=rc/(cpi*10a6)=40*10a6/(2.24*10a6)=17.86 2.3 如题，计算：1 )

6、 渐近带宽 r a=? mi 2 ) 半峰值信息长度=?提示： t o=46 ps 答：渐近带宽r-=1 / 0.035=28.6mb/s (2)半峰值消息长度mi1/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 32 27 22 19 16 13 11 fs 42 42 42 42 42 42 21 21 21 21 21 21 tss(d=2) 42 40 38 3