中國(guó)科學(xué)技術(shù)大學(xué)期末考試試卷

1、-1 -名詞解釋1. 請(qǐng)給出下列縮寫的全稱，并加以解釋mpp、pcam 、apram 2. 請(qǐng)簡(jiǎn)要解釋下列術(shù)語(yǔ)的含義共享變量模型、 numa 、加速比、 logp1?現(xiàn)在市場(chǎng)上常見的雙cpu 的計(jì)算機(jī)采用的是什么結(jié)構(gòu)？簡(jiǎn)述該結(jié)構(gòu)的特性。2. 何謂高速緩存一致性問(wèn)題？請(qǐng)簡(jiǎn)述一致性維護(hù)的基本策略。3. 請(qǐng)簡(jiǎn)述并舉例說(shuō)明amdahl 定律。4?請(qǐng)問(wèn)如何將一個(gè)mpmd 程序改寫為 spmd 程序？二、綜合題1. 閱讀以下題為“占據(jù)半壁江山ibm 繼續(xù)統(tǒng)治超級(jí)計(jì)算機(jī)排行榜”大眾新聞報(bào)道，回 答問(wèn)題。根據(jù)超級(jí)計(jì)算機(jī)500 強(qiáng)組織最近發(fā)布的調(diào)查報(bào)告，ibm 繼續(xù)在超級(jí)計(jì)算機(jī)領(lǐng)域處于絕對(duì)的統(tǒng)治地位。此調(diào)查每半

2、年進(jìn)行一次，這是自1993 年以來(lái)的第 26 次調(diào)查。目前，世界上500 臺(tái)最強(qiáng)悍的超級(jí)計(jì)算機(jī)中有219 臺(tái)屬于 ibm，其中前三名更是全部出自ibm之手。位列第二的hp 擁有 169 臺(tái)。位列榜首的依舊是大名鼎鼎的藍(lán)色基因- - blue gene/l ，運(yùn)算速度為每秒280.6 萬(wàn)億次浮點(diǎn)運(yùn)算。這一速度不久前剛剛刷新了世界記錄。這臺(tái)超級(jí)計(jì)算機(jī)是為美國(guó)國(guó)家核安全局打造的，主要用于模擬核試驗(yàn)。緊隨其后的也是藍(lán)色基因，不過(guò)是ibm 自己的 watson blue gene(wbg)系統(tǒng)，運(yùn)算速度為每秒91.29 萬(wàn)億次浮點(diǎn)運(yùn)算。第三名是位于勞倫斯-利沃莫爾國(guó)家實(shí)驗(yàn)室的asc purple ，運(yùn)算

3、速度為每秒63.39 萬(wàn)億次浮點(diǎn)運(yùn)算。ibm 這 219 臺(tái)超級(jí)計(jì)算機(jī)的總運(yùn)算速度為每秒1.214 千萬(wàn)億次浮點(diǎn)運(yùn)算，占500 強(qiáng)總運(yùn)算能力的53% ，遠(yuǎn)遠(yuǎn)甩開了競(jìng)爭(zhēng)對(duì)手。這是第一次一家公司的總速度突破千萬(wàn)億次大關(guān)。ibm 將自己成功的原因歸結(jié)于富有彈性的操作平臺(tái)和強(qiáng)大的power 處理器等因素，其中藍(lán)色基因使用的就是power 處理器。(1) 請(qǐng)問(wèn)文中提到的“排行榜”是按照什么方法對(duì)高性能計(jì)算機(jī)進(jìn)行排序的？這種方法具有什么樣的優(yōu)點(diǎn)和不足？(2) 結(jié)合文中提到的高性能計(jì)算的應(yīng)用，談?wù)劄槭裁粗袊?guó)需要自行研制高性能計(jì)算機(jī)，并請(qǐng)舉出兩種國(guó)產(chǎn)系列高性能計(jì)算機(jī)品牌。(3)結(jié)合課程所學(xué)知識(shí)，請(qǐng)對(duì)文中“ib

4、m 將自己成功的原因歸結(jié)于富有彈性的操作平臺(tái)和強(qiáng)大的 power 處理器等因素”進(jìn)行分析評(píng)論。2. 假定 a44和 b44已加載到如下所示的4 4處理器陣列上，試用圖表示cannon 矩陣乘法的具體過(guò)程問(wèn)答題-2 -3. mimd 機(jī)器上 psrs 排序算法描述如下：輸入：長(zhǎng)度為 n 的無(wú)序序列， p 臺(tái)處理器，每臺(tái)處理器有n p 個(gè)元素輸出：長(zhǎng)度為 n 的有序序列begi n （1） 均勻劃分： n 個(gè)元素均勻地劃分成p 段，每臺(tái)處理器有n/p 個(gè)元素。（2） 局部排序：各個(gè)處理器利用串行排序算法，排序n/p 個(gè)數(shù)。（3） 選擇樣本：每臺(tái)處理器各從自己的有序段中選取p 個(gè)樣本元素。（4） 樣

5、本排序：用一臺(tái)處理器將所有p2個(gè)樣本元素用串行排序算法排序之。（5） 選擇主元：用一臺(tái)處理器選取p-1 個(gè)主元，并將其播送給其余處理器。（6） 主元?jiǎng)澐郑焊魈幚砥靼粗髟獙⒏髯缘挠行蚨蝿澐殖蓀 段。（7） 全局交換：各處理器將其轄段按段號(hào)交換到相應(yīng)的處理器。（8） 歸并排序：處理器使用歸并排序?qū)⑺邮盏闹T段施行排序。end 試證明：當(dāng) n _ p3時(shí)，上述算法的時(shí)間復(fù)雜度為o&log n ）。p 令 wij表示 p 中第 j 段中的元素?cái)?shù)，試證明上述算法在執(zhí)行過(guò)程中，處理器中所積累p - 2n的元素?cái)?shù)目不會(huì)超過(guò)2n/p, 即w：: 勺。jm p4. pram 上對(duì)數(shù)劃分算法描述如下：輸入

6、：兩非降有序序列a = ，, an）, b ,.,bn）,假定log m和 k（m）二 m logm 均為整數(shù)輸出：將 a 和 b 劃分成k（m）對(duì)段組（a，bj，使得 |bi|=logm , ta i 二 n，且對(duì)于所有1eiek （m）-1, a 和 bi中的每一個(gè) i 元素均大于 a 斗和by中的每一個(gè)元素-3 -begi n （1） j（0） = 0 ; j（k（m） = n-4 -(2) for i =1 to k(m) -1 par-do (2.1)求 rank(bnogm : a) (2.2)j(i)二 rank(bhogm : a) end for (3) for i =0 to k(m)_1 par-do(3.2) a =(aj(i)卄?，aj( 申) end for end 試分析上述算法的時(shí)間復(fù)雜度。 令a =(0,1,2,7,9,11,16,17,18,19,23,24,25,27,28,30,33,34) b =(3,4