中國科學技術大學期末考試試卷

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

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

3、速度為每秒63.39 萬億次浮點運算。ibm 這 219 臺超級計算機的總運算速度為每秒1.214 千萬億次浮點運算，占500 強總運算能力的53% ，遠遠甩開了競爭對手。這是第一次一家公司的總速度突破千萬億次大關。ibm 將自己成功的原因歸結于富有彈性的操作平臺和強大的power 處理器等因素，其中藍色基因使用的就是power 處理器。(1) 請問文中提到的“排行榜”是按照什么方法對高性能計算機進行排序的？這種方法具有什么樣的優(yōu)點和不足？(2) 結合文中提到的高性能計算的應用，談談為什么中國需要自行研制高性能計算機，并請舉出兩種國產系列高性能計算機品牌。(3)結合課程所學知識，請對文中“ib

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

5、本排序：用一臺處理器將所有p2個樣本元素用串行排序算法排序之。（5） 選擇主元：用一臺處理器選取p-1 個主元，并將其播送給其余處理器。（6） 主元劃分：各處理器按主元將各自的有序段劃分成p 段。（7） 全局交換：各處理器將其轄段按段號交換到相應的處理器。（8） 歸并排序：處理器使用歸并排序將所接收的諸段施行排序。end 試證明：當 n _ p3時，上述算法的時間復雜度為o&log n ）。p 令 wij表示 p 中第 j 段中的元素數(shù)，試證明上述算法在執(zhí)行過程中，處理器中所積累p - 2n的元素數(shù)目不會超過2n/p, 即w：: 勺。jm p4. pram 上對數(shù)劃分算法描述如下：輸入

6、：兩非降有序序列a = ，, an）, b ,.,bn）,假定log m和 k（m）二 m logm 均為整數(shù)輸出：將 a 和 b 劃分成k（m）對段組（a，bj，使得 |bi|=logm , ta i 二 n，且對于所有1eiek （m）-1, a 和 bi中的每一個 i 元素均大于 a 斗和by中的每一個元素-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 試分析上述算法的時間復雜度。 令a =(0,1,2,7,9,11,16,17,18,19,23,24,25,27,28,30,33,34) b =(3,4