高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)第一次作

1、計(jì)算機(jī)體系結(jié)構(gòu)第一次作業(yè)計(jì)算機(jī)學(xué)院1.3 在 pram 模型上，假定算法a、b 和 c 的執(zhí)行時(shí)間分別為7n,nlogn/4和 nloglogn, 試問(wèn)：1 ) 用大o 表示的時(shí)間復(fù)雜度是多少？2) 三個(gè)算法，何者最快？何者最慢？3) 當(dāng) n=1024 時(shí)，三個(gè)算法何者最快？何者最慢？4) 如何解釋上述1 )和 3) 的不同結(jié)論？答：算法 a、b 和 c 的時(shí)間復(fù)雜度分別為0 ( n) 、0 ( nlogn ) 和 0 ( nloglogn ) 。(2) 算法 a 執(zhí)行的最快， 算法 b 執(zhí)行的最慢。 原因：當(dāng) n 的值足夠大時(shí)， 0( n) 0 ( nloglogn ) 0 ( nlogn

2、) 。所以算法a 執(zhí)行的最快，算法b 執(zhí)行的最慢。(3) 當(dāng) nnloglognnlgon/4 ，所以，算法b 最快，算法a 最慢。(4) 實(shí)際程序計(jì)算中，n 的值一般都比較大( 遠(yuǎn)大于 1024=2 10)，然而當(dāng) n=1024 時(shí)， logn 可能仍然大于1 ，卻小于10，所以 loglogn 的值小于1 ，從而n nlogn. 也就是說(shuō)，時(shí)間復(fù)雜度是數(shù)量級(jí)的概念，忽略了常數(shù)系數(shù)，而3) 是計(jì)算出具體結(jié)果，因此會(huì)有差別。所以結(jié)論不同。1.8 給出如下串行程序代碼段：for(i=0;in;i+) ai = bi*bi+1; for(i=0;in;i+) ci = ai+ai+1; 1) 試用

3、庫(kù)例程方式，寫(xiě)出其等效的并行代碼段；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 中的數(shù)組操作，寫(xiě)出其等效的并行代碼段；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、 寫(xiě)出其等效的并行代碼段。#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 計(jì)算執(zhí)行程序的有效cpi、mips 速率及總的cpu 執(zhí)行時(shí)間。 ( 圖表省略 ) 答：cpi 為執(zhí)行每條指令所需要的平均的時(shí)鐘周期數(shù)。所以，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 計(jì)算答：(1) 在單處理機(jī)上執(zhí)行該程序的平均cpi 值為：1*60%+2*18%+4*12%+8*10%=2.24 (2)計(jì)算相應(yīng)的mips 速率mips=rc/(cpi*10a6)=40*10a6/(2.24*10a6)=17.86 2.3 如題，計(jì)算：1 )

6、 漸近帶寬 r a=? mi 2 ) 半峰值信息長(zhǎng)度=?提示： t o=46 ps 答：漸近帶寬r-=1 / 0.035=28.6mb/s (2)半峰值消息長(zhǎng)度mi1/2=to* r - =46us*28.6mb/s=1315.6b 2.9 假設(shè) n=500 ，p=6 ，比照表 2.12 ，試列出采用不同調(diào)度算法的結(jié)果調(diào)度算法任務(wù)分配粒度隨時(shí)間的變化靜態(tài)調(diào)度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