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

1、作業(yè)( 1) 習(xí)題 2.6 (P75) 根據(jù) 2.3.1 節(jié)有關(guān) SP2 的介紹，試回答： 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í)

2、現(xiàn)了同時(shí)連接以太網(wǎng)和高性能開(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ò)平均延遲反映 出To,所以等速度與平均延遲標(biāo)準(zhǔn)都是輔之以測(cè)試手段而得到有關(guān)性能參數(shù)來(lái) 評(píng)判可擴(kuò)放性的；而等效率標(biāo)準(zhǔn)則是通過(guò)解析計(jì)算開(kāi)銷參數(shù)To 來(lái)評(píng)判可擴(kuò)放性 的。 習(xí)

3、題 3.6 (P99) 使用40MHZ主頻的標(biāo)量處理器執(zhí)行一個(gè)典型測(cè)試程序，其所執(zhí)行的指令數(shù)及所需的周 期數(shù)如表所示。試計(jì)算執(zhí)行該程序的有效CPI、MIPS 。 指令類型 指令數(shù) 時(shí)鐘周期數(shù) 整數(shù)算術(shù) 45,000 1 數(shù)據(jù)傳送 32,000 2 浮點(diǎn) 15,000 2 控制轉(zhuǎn)移 8,000 2 答案：機(jī)器的時(shí)鐘周期為t，程序中指令總條數(shù)為Ic，執(zhí)行每條指令所需的平均時(shí)鐘 周期數(shù)為CPI，則一個(gè)程序在 CPU上運(yùn)行的時(shí)間 T為： T =lCx CPI x t= C x t CPI = C/I C C= (45 000+32 000*2+15 000*2+8 000*2) = 155 000 C

4、PI =1.55 MIPS( Million Instructions Per Second) (CPI x 106 ) MIPS = Ic / ( T x 106) = f / =(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) Lci=Rci=n+1 end for (2) repeat for each P, iroot par-do if (A i Afi) or (A i= Afi and i1 the n該結(jié)點(diǎn)為其父結(jié)點(diǎn)的左兒子 Ch,j=Ch+1,(j-1)/2*Bh,j end if end for end for end 答案：W n =3n 初始化將Aj值賦給相應(yīng)的B0,j； 正向遍歷