作業(yè)答案-華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系

1、作業(yè)答案-華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系習(xí)題 2.6 (P75)根據(jù)節(jié)有關(guān)SP2的介紹，試答復(fù)： SP設(shè)計(jì)者為了趕上市場(chǎng)作了什么決策？ SP設(shè)計(jì)者為了到達(dá)系統(tǒng)通用采用了什么相應(yīng)的技術(shù)？ SP系統(tǒng)是如何支持4種SSI的：?jiǎn)我贿M(jìn)入點(diǎn)、單一文件層次、單一控制點(diǎn)和單一作 業(yè)管理系統(tǒng)？ SP設(shè)計(jì)者為了增加帶寬，在通信子系統(tǒng)中主要使用了什么技術(shù)？答案：IBM Sp2系統(tǒng)主要包含一下的一些特性： 為了趕上市場(chǎng)，遵循 Moore定律，采用靈活的機(jī)群結(jié)構(gòu)； 為了到達(dá)系統(tǒng)通用采用了標(biāo)準(zhǔn)的系統(tǒng)環(huán)境和標(biāo)準(zhǔn)的編程模式； 采用局部的單一系統(tǒng)映象支持 4種SSI。 為了增加帶寬，在通信子系統(tǒng)主要實(shí)現(xiàn)了同時(shí)連接以太網(wǎng)和高性能

2、開(kāi)關(guān)網(wǎng)。習(xí)題 3.4 (P99)綜合比較等效率、等速度和平均延遲可擴(kuò)放性度量標(biāo)準(zhǔn)之間的異同性。答案：三種度量可擴(kuò)放性的標(biāo)準(zhǔn)是相互等效的。三種度量方法的根本出發(fā)點(diǎn)都是抓住了影響算法可擴(kuò)放性的根本參數(shù) T o,只是等效率標(biāo)準(zhǔn)采用解析計(jì)算的方法得到T o ；等速度標(biāo)準(zhǔn)將 To隱含在所測(cè)量的執(zhí)行時(shí)間中；而平均延遲標(biāo)準(zhǔn)那么是保持效率為 恒值時(shí)，通過(guò)調(diào)節(jié) W與p來(lái)測(cè)量并行與串行執(zhí)行時(shí)間，最終通過(guò)平均延遲反映 出T。，所以等速度與平均延遲標(biāo)準(zhǔn)都是輔之以測(cè)試手段而得到有關(guān)性能參數(shù)來(lái) 評(píng)判可擴(kuò)放性的；而等效率標(biāo)準(zhǔn)那么是通過(guò)解析計(jì)算開(kāi)銷(xiāo)參數(shù)To來(lái)評(píng)判可擴(kuò)放性的。習(xí)題 3.6 (P99)使用40MHZ主頻的標(biāo)量處理

3、器執(zhí)行一個(gè)典型測(cè)試程序，其所執(zhí)行的指令數(shù)及所需的周期數(shù)如表所示。試計(jì)算執(zhí)行該程序的有效CPI、MIPS 。指令類(lèi)型指令數(shù)時(shí)鐘周期數(shù)整數(shù)算術(shù)45,0001數(shù)據(jù)傳送32,0002浮點(diǎn)15,0002控制轉(zhuǎn)移8,0002答案：機(jī)器的時(shí)鐘周期為T(mén)，程序中指令總條數(shù)為 IC，執(zhí)行每條指令所需的平均時(shí)鐘周期數(shù)為CPI，那么一個(gè)程序在 CPU上運(yùn)行的時(shí)間 T為：T =I cX CPI Xt= C XtCPI = C/I CC= (45 000+32 000*2+15 000*2+8 000*2) = 155 000CPI =1.55MIPS( Million Instructions Per Second)M

4、IPS = Ic / (TX106)= f / (CPIX106 )= (40 X 106 )/(1.55 X 106)25.8作業(yè)(2)習(xí)題5.3P136頁(yè)給定序列(33,21,13,54,82,33,40,72和8個(gè)處理器，試按照下述算法構(gòu)造一個(gè) 在PRAM-CRCW模型上執(zhí)行的快排序所用的二叉樹(shù)。(包括root值，Lc和 Rc值，最后用處理器號(hào)表示的樹(shù))輸入：A1.n和n個(gè)處理器，并且Ai保存在Pi的LM中 輸出：二叉排序樹(shù) root, Lc1.n, Rc1.n在 SM 中Begi n(1) for each Pi par-do(1.1) root=i(1.2) fi=root(1.3)

5、 Lci=Rci=n+1end for(2) repeat for each P, iroot par-doif (A i Afi) or (A i= Afi and ifi) the n(2.1) Lcfi =i(2.2) if i=Lc fi then exit else fi= Lcfi end if else(2.3) Rcfi=i(2.4) if i=Rcfi then exit else fi= Rcfi e nd ifend ifend repeatEnd答案：以下給出一種正確答案：排序過(guò)程的數(shù)據(jù)分布如下(a)初始數(shù)據(jù)處理器編號(hào)12345678對(duì)應(yīng)的Ai3321135482334

6、072(b)執(zhí)行完算法中的(1)循環(huán)root = 6(c)執(zhí)行完一次(2)循環(huán)處理器編號(hào)12345678對(duì)應(yīng)的Lc i:1對(duì)應(yīng)的Rc i8(d)再執(zhí)行完一次(2)循環(huán)處理器編號(hào)12345678對(duì)應(yīng)的Lc i:317 :對(duì)應(yīng)的Rc i85(e)再執(zhí)行完一次(2)循環(huán)處理器編號(hào)12345678對(duì)應(yīng)的Lc i3147對(duì)應(yīng)的Rc i285所構(gòu)造出的用處理器號(hào)表示的二叉樹(shù)如下列圖:【633以上只是給出了一種情況，如果數(shù)據(jù)改變了，也要會(huì)做習(xí)題6.3P158頁(yè)P(yáng)RAM上對(duì)數(shù)劃分算法描述如6.3所示。 試分析上述算法的時(shí)間復(fù)雜度。 答案：常數(shù)級(jí)，0(1)習(xí)題6.6P158頁(yè) 試分析算法6.9的總運(yùn)算量 W n ? 假定序列為(1，2，3，4，5，6，7, 8)，試用算法6.9求其前綴和。算法6.9前綴和：n個(gè)元素x1,x2,xn，前綴和是n個(gè)局部和，這里 S=X1 + Xi, K i1 the n/該結(jié)點(diǎn)為其父結(jié)點(diǎn)的左兒子Ch,j=Ch+1,(j-1)/2*Bh,jend ifend forend forend答