1、1、討論某一種算法的可擴(kuò)放性時(shí)，一般指什么？88答：討論某一種算法的可擴(kuò)放性時(shí)，實(shí)際上是指該算法針對(duì)某一特定機(jī)器結(jié)構(gòu)的可擴(kuò)放性2、使用“DoinParallel"語(yǔ)句時(shí)，表示的是什么含義105答：表示算法的若干步要并行執(zhí)行3、并行計(jì)算機(jī)的存儲(chǔ)訪問(wèn)類型有哪幾種？26答：存儲(chǔ)訪問(wèn)類型有：UMA（均勻存儲(chǔ)訪問(wèn)）、NUMA（非均勻存儲(chǔ)訪問(wèn)）、COMA（全高速緩存存儲(chǔ)訪問(wèn)）、CC-NUMA（高速緩存一致性非均勻存儲(chǔ)訪問(wèn)）、NORMAl（非遠(yuǎn)程存儲(chǔ)訪問(wèn)）4、什么是同步？它有什么作用？如何實(shí)現(xiàn)？107答：同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須相互等待。作用：確保個(gè)處理器的正確工作順序以及對(duì)共享可

2、寫數(shù)據(jù)的正確訪問(wèn)（互斥訪問(wèn)）。實(shí)現(xiàn)方法：用軟件、硬件和固件的方法實(shí)現(xiàn)。5在并行加速比的計(jì)算中，常用的三種加速比定律分別是哪三種？（P83）答：常用的三種加速比定律分別是：適用于固定計(jì)算負(fù)載的Amdahl定律，適用于可擴(kuò)放問(wèn)題白GGustafson定律和受限于存儲(chǔ)器的Sun和Ni定律。6、試比較Amdahl定律、Gustafson定律、Sun和Ni定律三種加速定律的應(yīng)用場(chǎng)合。83答：Amdahl定律適用于固定計(jì)算負(fù)載的問(wèn)題Gustafson定律適用于可擴(kuò)放性問(wèn)題Sun和Ni定律適用于受限于存儲(chǔ)器的問(wèn)題。7 .并行算法的基本設(shè)計(jì)技術(shù)有哪些？它們的基本思想是什么？139答：（1）基本技術(shù)有：劃分設(shè)計(jì)

3、技術(shù)（又分為均勻劃分技術(shù)、方根劃分技術(shù)、對(duì)數(shù)劃分技術(shù)和功能劃分技術(shù)卜分治設(shè)計(jì)技術(shù)、平衡樹(shù)設(shè)計(jì)技術(shù)、倍增設(shè)計(jì)技術(shù)、流水線設(shè)計(jì)技術(shù)等。（2）基本思想分別如下：a.劃分設(shè)計(jì)技術(shù)：（P139）將一原始問(wèn)題分成若干部分，然后各部分由相應(yīng)的處理器同時(shí)執(zhí)行。b.分治設(shè)計(jì)技術(shù)：（P144）將一個(gè)大二復(fù)雜的問(wèn)題分解成若干特性相同的子問(wèn)題分而治之。若所得的子問(wèn)題規(guī)模仍嫌過(guò)大，可反復(fù)使用分治策略，直至很容易求解諸子問(wèn)題為止。c.平衡樹(shù)設(shè)計(jì)技術(shù)：（P149）將輸入元素作為葉節(jié)點(diǎn)構(gòu)筑一顆平衡二叉樹(shù)，然后自葉向根往返遍歷。d.倍增設(shè)計(jì)技術(shù)：（P151）又叫指針跳躍技術(shù)，特別適合處理以鏈表或有向有根樹(shù)之類表示的數(shù)據(jù)結(jié)構(gòu)。每

4、當(dāng)遞歸調(diào)用時(shí)，所要處理的數(shù)據(jù)之間的距離將逐步加倍，經(jīng)過(guò)k步后就可完成距離為2k（2的k次方）的所有數(shù)據(jù)的計(jì)算。e.流水線設(shè)計(jì)技術(shù)：（P153）將一個(gè)計(jì)算任務(wù)t分成一系列子任務(wù)t1,t2,t3,.,tm,使得一旦tm完成，后繼的子任務(wù)就可立即開(kāi)始，并以同樣的速率進(jìn)行計(jì)算。8 .并行計(jì)算模型一般可分為哪幾種模型？108答：PRAM模型、APRAM模型、BSP模型、logP模型。9、主要的并行計(jì)算模型有哪些？它們的主要思想是什么？108答：并行計(jì)算模型主要有：PRAM模型、APRAM模型、BSP模型、logP模型。思想：PVP系統(tǒng)中使用了專門設(shè)計(jì)的高帶寬的交叉開(kāi)關(guān)網(wǎng)絡(luò)將VP連向共享存儲(chǔ)模塊，存儲(chǔ)器可

5、以兆字節(jié)每秒的速度向處理器提供數(shù)據(jù)。這樣的機(jī)器通常不適用高速緩存，而是使用大量的向量寄存器和指令緩沖器。SMPSMP系統(tǒng)使用商品微處理器(具有片上或外置高速緩存)，它們經(jīng)由高速總線(或交叉開(kāi)關(guān))連向共享存儲(chǔ)器。系統(tǒng)是對(duì)稱的，每個(gè)處理器可等同地訪問(wèn)共享存儲(chǔ)器、IO設(shè)備和操作系統(tǒng)服務(wù)。正是對(duì)稱，才能開(kāi)拓較高的并行度；也正是共享存儲(chǔ)，限制系統(tǒng)中的處理器不能太多(一般少于64個(gè))，同時(shí)總線和交叉開(kāi)關(guān)互連一旦做成也難于擴(kuò)展。MPPMPP一般是指超大型計(jì)算機(jī)系統(tǒng)，它具有如下特性：1、處理節(jié)點(diǎn)采用商品微處理器；2、系統(tǒng)中有物理上的分布式存儲(chǔ)器；3、采用高通信帶寬和低延遲的互連網(wǎng)絡(luò)(專門設(shè)計(jì)和定制的)；4、能

6、擴(kuò)放至成百上千乃至上萬(wàn)個(gè)處理器；5、它是一種異步的MIMD機(jī)器，程序系由多個(gè)進(jìn)程組成，每個(gè)都有其私有地址空間，進(jìn)程間采用傳遞消息互相作用。DSMDSM和SMP的主要差別是，DSM在物理上有分布在各節(jié)點(diǎn)中的局存，從而形成了一個(gè)共享的存儲(chǔ)器。對(duì)用戶而言，系統(tǒng)硬件和軟件提供了一個(gè)但地址的編程控件。DSM相對(duì)于MPP的優(yōu)越性是編程較容易。COWCOW的重要界線和特征是：1、COW的每個(gè)節(jié)點(diǎn)都是一個(gè)完整的工作站，這樣的節(jié)點(diǎn)有時(shí)叫做“無(wú)頭工作站”，一個(gè)節(jié)點(diǎn)也可以是一臺(tái)PC或SMP;2、各節(jié)點(diǎn)通過(guò)一種低成本的商品網(wǎng)路互連；3、各節(jié)點(diǎn)內(nèi)總是有本地磁盤，而MPP節(jié)點(diǎn)內(nèi)卻沒(méi)有；4、節(jié)點(diǎn)內(nèi)的網(wǎng)絡(luò)接口是松散耦合到I/

7、O總線上的，而MPP內(nèi)的網(wǎng)絡(luò)接口是練到處理節(jié)點(diǎn)的存儲(chǔ)總線上的，因而可謂是緊耦合式的；5、一個(gè)完整的操作系統(tǒng)駐留在每個(gè)節(jié)點(diǎn)中，而MPP中通常只是個(gè)微核，COW的操作系統(tǒng)是工作站UNIX,加上一個(gè)附加的軟件層，以支持單一系統(tǒng)映像、并行度、通信和負(fù)載平衡等。10 .根據(jù)處理器對(duì)共享存儲(chǔ)單元同時(shí)讀、同時(shí)寫的限制，PRAM模型可以分為哪幾種模型？P109答：不允許同時(shí)讀和同時(shí)寫(Exclusive-ReadandExclusive-Write)的PRAM模型，簡(jiǎn)記之為PRAM-EREW。(2)允許同時(shí)讀不允許同時(shí)寫(Concurrent-ReadandExclusive-Write)的PRAM模型，簡(jiǎn)記

8、之為PRAM-CREW。(3)允許同時(shí)讀和同時(shí)寫(Concurrent-ReadandConcurrent-Write)的PRAM模型，簡(jiǎn)記之為PRAM-CRCW。顯然，允許同時(shí)寫是不現(xiàn)實(shí)的，于是又對(duì)PRAM-CRCW模型做了進(jìn)一步的約定：(1)只允許所有的處理器同時(shí)寫相同的數(shù)，此時(shí)稱為公共(Common)的PRAM-CRCW,簡(jiǎn)記之為CPRAM-CRCW;(2)只允許最優(yōu)先的處理器先寫，此時(shí)稱為優(yōu)先(Priority)的PRAM-CRCW,簡(jiǎn)記之為PPRAM-CRCW;允許任意處理器自由寫，此時(shí)稱為任意(Arbitrary)的PRAM-CRCW,簡(jiǎn)記之為APRAM-CRCW。11 .APRA

9、M模型中有四類指令，它們分別是哪些?110APRAM模型中有四類指令：全局讀：將全局存儲(chǔ)單元中的內(nèi)容讀入局存單元中；局部操作：對(duì)局存中的數(shù)執(zhí)行操作，其結(jié)果存入局存中；全局寫：將局存單元中的內(nèi)容寫入全局存儲(chǔ)單元中；同步：同步是計(jì)算中的一個(gè)邏輯點(diǎn)，在該點(diǎn)各處理器均需等待別的處理器到達(dá)后才能繼續(xù)執(zhí)行其局部程序.12、并行計(jì)算的物質(zhì)基礎(chǔ)是什么？3答：并行計(jì)算的物質(zhì)基礎(chǔ)是高性能并行計(jì)算機(jī)(包括分布式網(wǎng)絡(luò)計(jì)算機(jī))。課本第一章大標(biāo)題下面，第3頁(yè)13 .在并行計(jì)算中，對(duì)于點(diǎn)對(duì)點(diǎn)的通信，測(cè)量開(kāi)銷一般使用的方法有哪些？(P80)對(duì)于點(diǎn)到點(diǎn)的通信，測(cè)量開(kāi)銷使用兵-乓方法：節(jié)點(diǎn)0發(fā)送M個(gè)字節(jié)給節(jié)點(diǎn)1;節(jié)點(diǎn)1從節(jié)點(diǎn)0接

10、收M個(gè)字節(jié)后，立即將消息發(fā)回節(jié)點(diǎn)0.總的時(shí)間除以2,即可得到點(diǎn)到點(diǎn)通信時(shí)間，也就是執(zhí)行單一發(fā)送或接收操作的時(shí)間。兵-乓方法可一般化為熱土豆法，也稱救火隊(duì)法：節(jié)點(diǎn)0發(fā)送M個(gè)字節(jié)至節(jié)點(diǎn)1,節(jié)點(diǎn)1再將其發(fā)送給節(jié)點(diǎn)2,以此類推，最后節(jié)點(diǎn)N-1再將其返回給節(jié)點(diǎn)0,最后時(shí)間再除以N即可。14 .在Amdahl定律中，以f表示串行分量的比例，隨著處理器數(shù)目的無(wú)限增大，并行系統(tǒng)所能夠達(dá)到的加速上限是什么？83答：S=1/f15、并行計(jì)算機(jī)系統(tǒng)的互聯(lián)有哪三種類型？9靜態(tài)、動(dòng)態(tài)和標(biāo)準(zhǔn)三類16、從并行程序設(shè)計(jì)的角度來(lái)看，分布存儲(chǔ)系統(tǒng)的主要特點(diǎn)有哪些？這些特點(diǎn)導(dǎo)致了哪些并行編程模型？348答：從并行程序設(shè)計(jì)的角度來(lái)看

11、，分布存儲(chǔ)系統(tǒng)的主要特點(diǎn)：系統(tǒng)通過(guò)互連網(wǎng)絡(luò)將多個(gè)處理器連接起來(lái)，每個(gè)處理器均有自己的局部存儲(chǔ)器，所有的局部存儲(chǔ)器就構(gòu)成了整個(gè)地址空間；整個(gè)地址空間有局部和全局兩種編址方式。上述的特點(diǎn)，導(dǎo)致了分布存儲(chǔ)系統(tǒng)的兩種并行編程模型：數(shù)據(jù)并行模型和消息傳遞模型。17 .并行計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)模型包括有哪幾種？(P22)答：大型并行機(jī)系統(tǒng)一般分為六類：?jiǎn)沃噶疃鄶?shù)據(jù)流SIMD并行向量處理機(jī)PVP對(duì)稱多處理機(jī)SMP大規(guī)模并行處理機(jī)MPP工作站機(jī)群COW分布共享存儲(chǔ)多處理機(jī)DSM18 .在分析并行算法的復(fù)雜度時(shí)，主要有哪些指標(biāo)來(lái)分析的？106答：主要的指標(biāo)有：(1)運(yùn)行時(shí)間t(n)：運(yùn)行時(shí)間就是算法運(yùn)行在給定的模型

12、上求解問(wèn)題所需的時(shí)間，通常包括計(jì)算時(shí)間和通信時(shí)間，分別用計(jì)算時(shí)間步和選路時(shí)間步作為單位(2)處理器數(shù)p(n)：它是求解給定問(wèn)題所用的處理器數(shù)目(3)并行計(jì)算的成本c(n)：它定義為并行算法的運(yùn)行時(shí)間t(n)與所需的處理器數(shù)目p(n)的乘積(4)總運(yùn)算量W(n)：并行算法所完成的總的操作量。19 .對(duì)于高速并行計(jì)算主要有哪幾種類型的應(yīng)用需求？P5答：對(duì)高速并行計(jì)算的需求是廣泛的，但歸納起來(lái)主要有三種類型的應(yīng)用需求：1)計(jì)算密集型應(yīng)用，如大型科學(xué)工程計(jì)算與數(shù)值模擬；2)數(shù)據(jù)密集型應(yīng)用，如數(shù)字圖書(shū)館和數(shù)據(jù)倉(cāng)庫(kù)等；3)網(wǎng)絡(luò)密集型應(yīng)用，如協(xié)同工作、遙控和遠(yuǎn)程醫(yī)療診斷等。20 .什么是通信？它的功能是什么

13、？164答：所謂通信，就是為了進(jìn)行并行計(jì)算，諸任務(wù)之間所需進(jìn)行的數(shù)據(jù)傳輸。它的功能是進(jìn)行數(shù)據(jù)交換與傳輸。21 .在BSP模型中，計(jì)算是如何實(shí)現(xiàn)的？112在BSP模型中，計(jì)算系由一系列用全局同步分開(kāi)的周期為L(zhǎng)的超級(jí)步(superstep)所組成。在各超級(jí)步中，每個(gè)處理器均執(zhí)行局部計(jì)算，并通過(guò)選路器接收和發(fā)送消息；然后作一全局檢查，以確定該超級(jí)步是否已由所有的處理器完成；若是，則前進(jìn)到下一超級(jí)步，否則下一個(gè)L周期被分配給未曾完成的超級(jí)步。22 .用于獲得等速度可擴(kuò)性標(biāo)準(zhǔn)的方法有哪些？92答：1.測(cè)量法2 .計(jì)算法3 .預(yù)計(jì)法23.描述的，哪些參數(shù)可以用來(lái)描述logP模型？113答：l(Latenc

14、y)表示在網(wǎng)絡(luò)中消息從源到目的地所遭到的延遲o(Overhead)表示處理器發(fā)送或接收一條消息所需的額外開(kāi)銷g(Gap)表示處理器可以連續(xù)進(jìn)行消息發(fā)送或接收的最小時(shí)間間隔P(Processor)表示處理器/存儲(chǔ)器模塊數(shù)24、并行算法的一般設(shè)計(jì)過(guò)程可以分為那些步驟？160答：過(guò)程可分為四步，即是任務(wù)劃分(Partitioning)通信(Communication)分析、任務(wù)組合(Agglomeration)、和處理器映射(Mapping),簡(jiǎn)稱為PCAM設(shè)計(jì)過(guò)程。25、目前，并行軟件與并行硬件的發(fā)展如何？答：并行硬件：包括對(duì)稱處理機(jī)和大規(guī)模并行1、當(dāng)代主流的并行計(jì)算機(jī)是可擴(kuò)放的并行計(jì)算機(jī),處理機(jī)

15、以及機(jī)群系統(tǒng)；2、機(jī)群技術(shù)是發(fā)展可擴(kuò)放并行計(jì)算的主流趨勢(shì)；3、并行硬件正在成為計(jì)算機(jī)處理技術(shù)中廣為應(yīng)用的一部分。并行軟件：2861、并行軟件的發(fā)展落后于并行硬件；2、和串行系統(tǒng)的應(yīng)用軟件比，現(xiàn)今的并行系統(tǒng)的軟件甚少且不成熟;3、并行軟件的缺乏是發(fā)展并行計(jì)算的主要障礙;4、不幸的是，這種狀態(tài)似乎仍在繼續(xù)著。26 .當(dāng)在實(shí)際的并行機(jī)中設(shè)計(jì)并行程序時(shí)，絕大部分均是使用擴(kuò)展的FORTRAN和C語(yǔ)言的方法，目前有哪些擴(kuò)展的方法？(書(shū)上288頁(yè))目前的三種擴(kuò)展方法：1.庫(kù)函數(shù)法2.新語(yǔ)言結(jié)構(gòu)法3.編譯制導(dǎo)法27 .試比較Amdahl定律、Gustafon定律、Sun和Ni定律三種加速定律之間的關(guān)系？83A

16、mdahl定律和Gustafson定律都是通過(guò)增加處理器數(shù)量來(lái)達(dá)到提高計(jì)算速度的目的，而Sun和Ni定律是通過(guò)增加存儲(chǔ)空間來(lái)求得更好或者更精確的解的。Sun和Ni定律是Amdahl定律和Gustafson定律的一般化，其加速比另兩者高。28 .現(xiàn)在的并行編程風(fēng)范有哪些？P290(1)相并行：一個(gè)并行程序是由一些超級(jí)步組成：每個(gè)超級(jí)步內(nèi)，各個(gè)進(jìn)程執(zhí)行獨(dú)自的計(jì)算，然后繼之以交互作用。(2)分治并行：一個(gè)父進(jìn)程將其工作負(fù)載分成一些小的負(fù)載并將它們指派給一些子進(jìn)程，這些子進(jìn)程并行地完成各自的計(jì)算，其計(jì)算結(jié)果由父進(jìn)程歸并之。(3)流水線并行：一些進(jìn)程形成流水線作業(yè)法，諸進(jìn)程在流水線的不同地段同時(shí)重疊地執(zhí)

17、行操作以達(dá)到整體并行的效果。(4)主-從并行：這種并行也稱之為放牧式并行。(5)工作池并行：這種并行的優(yōu)點(diǎn)是易于達(dá)到負(fù)載平衡，因?yàn)楣ぷ髫?fù)載是動(dòng)態(tài)地分配給空間進(jìn)程的。29.消息傳遞模型有哪些特點(diǎn)？P314答：消息傳遞模型具有以下特點(diǎn)：(1) 多線程：消息傳遞程序系由多個(gè)進(jìn)程組成，每個(gè)進(jìn)程都有其控制線和可執(zhí)行不同的代碼；控制并行和數(shù)據(jù)并行均可支持(2) 異步并行性：消息傳遞程序的諸線程彼此異步地執(zhí)行，使用諸如路障和阻塞通信的方法來(lái)同步各線程。(3) 分開(kāi)的地址空間：并行程序的進(jìn)程駐留在不同的地址空間內(nèi)。(4) 顯式相互作用：程序員必須解決包括數(shù)據(jù)映射、通信、同步和聚合等相互作用問(wèn)題;進(jìn)程只在其擁有

18、的數(shù)據(jù)上執(zhí)行計(jì)算(5) 顯式分配：負(fù)載和數(shù)據(jù)均由用戶分配給進(jìn)程30、共享存儲(chǔ)的編程模型的特點(diǎn)有哪些？317答：多線程性、異步性、單地址空間31.什么是logP模型？它的特點(diǎn)是什么？113logP模型是一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通信的多處理機(jī)模型其中通信網(wǎng)絡(luò)由一組參數(shù)來(lái)描述：l表示在網(wǎng)絡(luò)中消息從源到目的地所遭到的延遲o表示處理器發(fā)送或接收一條消息所需的額外開(kāi)銷g表示處理器可連續(xù)進(jìn)行消息發(fā)送或接收的最小時(shí)間間隔P表示處理器/存儲(chǔ)器模塊數(shù)特點(diǎn)：l.logP模型將現(xiàn)代和將來(lái)的并行機(jī)的特性進(jìn)行了精確的綜合，以少量的參數(shù)L、o、g和p刻畫(huà)了并行機(jī)的主要瓶頸2.logP模型無(wú)須說(shuō)明編程風(fēng)格或通信協(xié)議，它可以等同

19、地用于共享存儲(chǔ)、消息傳遞和數(shù)據(jù)并行等各種風(fēng)范3.logP模型的可用性已經(jīng)由諸如播送、求和、FFT、LU分解、排序、圖的連通性等算法得以證實(shí)4.如果使logP模型中白參數(shù)g=0,L=0和o=0,則logP就等同于PRAM,同時(shí)logP模型也是BSP模型的改進(jìn)和細(xì)化；在一個(gè)超級(jí)步中消息一旦到達(dá)處理器就可立即使用它，而不必像BSP那樣一定要等到下一個(gè)超級(jí)步；logP模型全部采用消息同步而不像BSP那樣要用專門的硬件支持32題：i述BSP和logP兩個(gè)并行計(jì)算模型是否存在等效性？116答：兩者本質(zhì)上是等效的，且可以相互模擬：用BSP去模擬logP所進(jìn)行的計(jì)算時(shí)，通常會(huì)慢常數(shù)倍，而用logP去模擬BSP

20、所進(jìn)行的計(jì)算時(shí)，通常也會(huì)慢對(duì)數(shù)倍。33、在并行計(jì)算算法設(shè)計(jì)中，什么是循環(huán)映射？173循環(huán)映射也就是采用某種枚舉方法，輪流地將各處理器分配給諸計(jì)算任務(wù)。這種方法可能使負(fù)載平衡，但犧牲了局部性且通信可能會(huì)增加。此外，塊循環(huán)分配也是一種可能的處理器映射方法，此時(shí)，任務(wù)按塊的形式輪流分配給處理器。34 .在并行算法的基本操作中，彳f么是數(shù)據(jù)交換方式？183答：數(shù)據(jù)交換方式可以歸結(jié)為處理器之間的通信操作，而通信操作各式各樣，包括研究通信操作與處理器之間的互聯(lián)拓?fù)洌ㄐ胚x擇策略和消息傳遞機(jī)制關(guān)系。參考第八章前言35 .對(duì)稱多處理機(jī)SMP的主要結(jié)構(gòu)特性有哪些？40答：對(duì)稱性；但地址空間；高速緩存及其一致性；

21、低通信延遲。36 .設(shè)計(jì)大規(guī)模并行處理機(jī)MPP系統(tǒng)時(shí)，應(yīng)該考慮那些問(wèn)題？P49答:應(yīng)考慮以下問(wèn)題：1.可擴(kuò)放性2.系統(tǒng)成本3.通用性和可用性4.通信要求5.存儲(chǔ)器和I/O能力37.在并行計(jì)算技術(shù)發(fā)展過(guò)程中，大力發(fā)展工作站機(jī)群COW的原因是什么？65答：大力發(fā)展工作站機(jī)群COW的原因有：COW在實(shí)用上有以下明顯的優(yōu)點(diǎn)：1.投資風(fēng)險(xiǎn)小。2.編程方便。3.系統(tǒng)結(jié)構(gòu)靈活。4.性能、價(jià)格比高。5.能充分利用分散的計(jì)算資源。6.可擴(kuò)放性好。（具體詳見(jiàn)課本P65）38、工作負(fù)載的度量物理量有哪些？78答：工作負(fù)載即計(jì)算操作的數(shù)目，其度量物理量有執(zhí)行時(shí)間、浮點(diǎn)運(yùn)算數(shù)和指令數(shù)。8539 .在gustafson定

22、律中，其基本出發(fā)點(diǎn)是什么？從該定律中可以得出什么結(jié)論?答:Gustafson加速定律的基本出發(fā)點(diǎn)是：(1)對(duì)于很多大型計(jì)算，精度要求很高，即此類應(yīng)用中精度是個(gè)關(guān)鍵因素，而計(jì)算時(shí)間是固定不變的。此時(shí)為了提高精度，必須加大計(jì)算量，相應(yīng)地亦必須增多處理數(shù)才能維持時(shí)間不變；(2)除非學(xué)術(shù)研究，在實(shí)際應(yīng)用中沒(méi)有必要固定工作負(fù)載而使計(jì)算程序運(yùn)行在不同數(shù)目的處理器上，增多處理器必須相應(yīng)地增大問(wèn)題規(guī)模才有實(shí)際意義。從定律中我們可以知道，隨著處理器數(shù)目的增加，加速幾乎與處理器數(shù)成比例的線性增加，串行比例f不再是程序的瓶頸。40 .在并行加速比白計(jì)算中，Sun和Ni定律的基本思想是什么？86答:其基本思想是只要存

23、儲(chǔ)空間許可，應(yīng)盡量增大問(wèn)題規(guī)模以產(chǎn)生更好或更精確的解(此時(shí)可能使執(zhí)行時(shí)間略有增加)。41、MPI中的六個(gè)基本函數(shù)?基本函數(shù)：MPI_INITMPI_FINALIZEMPI_COMM_SIZEMPI_COMM_RANKMPI_SENDMPI_RECVpage352功能：?jiǎn)?dòng)MPI計(jì)算結(jié)束MPI計(jì)算確定進(jìn)程數(shù)確定自己的進(jìn)程標(biāo)識(shí)符發(fā)送一條消息接收一條消息42、什么是并行計(jì)算？實(shí)施并行計(jì)算有什么作用？104答：并行計(jì)算就是在并行計(jì)算機(jī)或分布式計(jì)算機(jī)等高性能計(jì)算系統(tǒng)上所做的超級(jí)計(jì)算。實(shí)施并行計(jì)算的作用有：快速解決大型且復(fù)雜的計(jì)算問(wèn)題，利用非本地資源，節(jié)約成本一使用多個(gè)廉價(jià)”計(jì)算資源取代大型計(jì)算機(jī)，同時(shí)克

24、服單個(gè)計(jì)算機(jī)上存在的存儲(chǔ)器限制。43、什么是節(jié)點(diǎn)度、網(wǎng)絡(luò)直徑？9答：射入或射出一個(gè)節(jié)點(diǎn)的邊數(shù)稱為節(jié)點(diǎn)度，在單向網(wǎng)絡(luò)中，入射和出射邊之和稱為節(jié)點(diǎn)度。網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最長(zhǎng)距離，即最大路徑數(shù)稱為網(wǎng)絡(luò)直徑。拓展：對(duì)分網(wǎng)絡(luò)各半所必須移去的最少邊數(shù)稱為對(duì)剖寬度。44 .設(shè)計(jì)并行算法一般有哪些策略？它們的主要思想是什么？101策略：并行化、全新法、借用法。思想：并行化法就是直接講一個(gè)串行算法并行化；全新法就是根據(jù)問(wèn)題的特性，從頭開(kāi)始設(shè)計(jì)一個(gè)新的并行算法；借用法就是借用已知某類問(wèn)題的現(xiàn)有算法，球解另一類與之有內(nèi)在相似性的問(wèn)題。45 .什么是工作站機(jī)群COW,它有哪些優(yōu)勢(shì)？P64工作站機(jī)群COW是實(shí)現(xiàn)并

25、行計(jì)算的一種新主流技術(shù)，是屬于分布式存儲(chǔ)的MIMD并行計(jì)算機(jī)結(jié)構(gòu)，系由工作站和互聯(lián)網(wǎng)絡(luò)兩部分組成。即它是將一群工作站用某種結(jié)構(gòu)的網(wǎng)絡(luò)互聯(lián)起來(lái)，充分利用各工作站的資源，統(tǒng)一調(diào)度、協(xié)調(diào)處理，以實(shí)現(xiàn)高效并行計(jì)算。優(yōu)勢(shì)：投資風(fēng)險(xiǎn)小，變成方便，系統(tǒng)結(jié)構(gòu)靈活，性價(jià)比高，可擴(kuò)放性好，能充分利用分散的計(jì)算資源。46 .并行系統(tǒng)的加速比是什么？它的作用是什么？（P83）并行系統(tǒng)的加速比是對(duì)于一個(gè)給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對(duì)于串行算法（或串行程序）的執(zhí)行速度加快了多少倍。加速比的作用對(duì)科學(xué)研究和工程應(yīng)用有所不同；科學(xué)研究中使用絕對(duì)加速：即對(duì)給定問(wèn)題，最佳串行算法所用的時(shí)間除以同一問(wèn)題其并行算法

26、所用的時(shí)間；工程應(yīng)用使用相對(duì)加速：即對(duì)給定問(wèn)題，同一個(gè)算法在單處理器上運(yùn)行的時(shí)間除以在多個(gè)處理器上運(yùn)行的時(shí)間。47、什么是可擴(kuò)放性？它的作用是什么？如何衡量其優(yōu)劣？88答：可擴(kuò)放性是指在確定的應(yīng)用背景下，計(jì)算機(jī)系統(tǒng)（或算法或編程等）性能隨處理器數(shù)的增加而按比例提高的能力。作用：用來(lái)描述并行算法能夠有效利用可擴(kuò)充的處理器數(shù)的能力。可用等效率、等速度和平均延遲方法來(lái)衡量它的優(yōu)劣。48 .什么是等效率函數(shù)，其作用是什么？89答：為了維持一定的效率（介于0與1之間），當(dāng)處理器P增大時(shí)，需要相應(yīng)地增大問(wèn)題規(guī)模W的值，由此定義函數(shù)fE（p）為問(wèn)題規(guī)模W隨處理器P變化的函數(shù)，稱此函數(shù)為等效率函數(shù)。作用是：根

27、據(jù)等效率函數(shù)可以判定某個(gè)函數(shù)是否具有擴(kuò)放性。49 .什么是域分解嗯功能是什么?162答:域分解也叫數(shù)據(jù)劃分，所要?jiǎng)澐值膶?duì)象是數(shù)據(jù)，這些數(shù)據(jù)可以是算法的輸入數(shù)據(jù)，計(jì)算的輸出數(shù)據(jù)，或者算法所產(chǎn)生的中間結(jié)果.它首先分解與問(wèn)題相關(guān)的數(shù)據(jù)（盡可能大致相等，其次將每個(gè)計(jì)算關(guān)聯(lián)到它所操作的數(shù)據(jù)上.功能:把原計(jì)算問(wèn)題分割成一些小的計(jì)算任務(wù)，以充分揭示并行執(zhí)行的機(jī)會(huì).50、在并行算法的設(shè)計(jì)過(guò)程中，細(xì)粒度任務(wù)、粗粒度任務(wù)與并行算法的關(guān)系是什么？答：在設(shè)計(jì)過(guò)程的劃分階段，致力于定義盡可能多的任務(wù)以增大并行執(zhí)行的機(jī)會(huì)。但是定義大量的細(xì)粒任務(wù)不一定能產(chǎn)生一個(gè)有效地并行算法，因?yàn)榇罅考?xì)粒度任務(wù)有金額能增加通訊代價(jià)和任務(wù)創(chuàng)

28、建代價(jià)。如果每個(gè)任務(wù)的通訊伙伴是少的，則增加劃分粒度能減少通訊次數(shù)，同時(shí)還能減少總通訊量。對(duì)同一計(jì)算問(wèn)題，粗粒度劃分的通訊次數(shù)和通訊量均比細(xì)粒度劃分是有所下降。因此，在其他條件同等的情況下，對(duì)于一個(gè)給定的計(jì)算，高維分解減少了通訊。因此從效率的角度，增加粒度的最好辦法是在所有的維組合任務(wù)。（P168）細(xì)粒度并發(fā)性好，粗粒度通信開(kāi)銷低51.在并行計(jì)算中，什么是處理器映射？它的作用是什么？171答：處理器映射：在并行算法設(shè)計(jì)最后階段中，我們要指定每個(gè)任務(wù)要到哪個(gè)處理器上執(zhí)行。作用：減少并行算法的總執(zhí)行時(shí)間。52、什么是全局通信？它的主要特點(diǎn)是什么？166答：全局通信系指有很多任務(wù)參與交換數(shù)據(jù)的一種通

29、信模式。主要特點(diǎn)：每個(gè)任務(wù)與很多別的任務(wù)通信。53、什么是分布算法？實(shí)施它的優(yōu)點(diǎn)是什么？104分布算法是指算法的諸進(jìn)程的執(zhí)行不必相互等待的一類并行算法。54、什么是網(wǎng)絡(luò)計(jì)算？104答：網(wǎng)絡(luò)計(jì)算（Networkcomputing）是指計(jì)算機(jī)在網(wǎng)絡(luò)上一起工作。55、何為網(wǎng)絡(luò)對(duì)稱？9答：如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱網(wǎng)絡(luò)為對(duì)稱的。56.一個(gè)n立方中，它有多小個(gè)頂點(diǎn)？10有2的N次方個(gè)頂點(diǎn)的！57、MPP和機(jī)群相比，它的性能/價(jià)格比如何？請(qǐng)比較答：MPP性價(jià)比一般，而機(jī)群的性價(jià)比比較高。58、串行計(jì)算模型有理想的模型嗎？并行計(jì)算有理想的模型嗎？為什么？109答：串行計(jì)算模型有理想的模型，馮諾依曼機(jī)

30、是理想的串行計(jì)算模型；并行計(jì)算沒(méi)有理想的模型，因?yàn)橛捎诓⑿袡C(jī)在飛速發(fā)展之中，尚未定型，故目前尚沒(méi)有所謂的通用并行計(jì)算模型，也就沒(méi)有理想的模型。（來(lái)源網(wǎng)絡(luò)）59、什么是PRAM模型，它的特點(diǎn)是什么？108答：PRAM模型即并行隨即存取機(jī)器，也稱之為共享存儲(chǔ)的SIMD模型，是一種抽象的并行計(jì)算模型。特點(diǎn)：它是假設(shè)有一個(gè)無(wú)限大容量的共享存儲(chǔ)器，并且有多個(gè)功能相同的處理器，在任意時(shí)刻處理器可以訪問(wèn)共享存儲(chǔ)單元。60、在什么情況下可以稱一個(gè)并行算法是成本最優(yōu)的？106答：假設(shè)有p個(gè)處理器，Ts是串行最優(yōu)執(zhí)行時(shí)間，Tp是并行最優(yōu)執(zhí)行時(shí)間，則當(dāng)Tp的漸進(jìn)度和Ts的漸進(jìn)度是相同的話，那么稱這個(gè)算法的成本是最優(yōu)

31、的。61 .異步PRAM模型的主要特點(diǎn)是什么？109答：分相PRAM模型是一個(gè)異步的PRAM模型，簡(jiǎn)記之為APRAM,系由p個(gè)處理器組成，其特點(diǎn)是每個(gè)處理器都有其局存、局部時(shí)鐘和局部程序；處理器間的通信經(jīng)過(guò)共享全局存儲(chǔ)器；無(wú)全局時(shí)鐘，各處理器異步地獨(dú)立執(zhí)行各自的指令；處理器任何時(shí)間依賴關(guān)系需明確地在各處理器的程序中加入同步（路）障；一條指令可在非確定（無(wú)界）但有限的時(shí)間內(nèi)完成。參考課本P11062 .當(dāng)代主流的并行計(jì)算機(jī)是可擴(kuò)放的嗎？為什么？（p39,p88）答：是可擴(kuò)放的；因?yàn)檫@些并行計(jì)算機(jī)的性能都可以隨著處理器數(shù)的增加而按比例提高。63、在Amdahl定律中，串行分量、并行額外開(kāi)銷與加速的關(guān)系？84答：串行分量越大和并行額外開(kāi)銷越大，則加速越小10364、并行算法的設(shè)計(jì)與某一特定的并行計(jì)算模型關(guān)系如何?答：任何并行算法的設(shè)計(jì)都是基于某一特定的并行計(jì)算模型的，而并行計(jì)算模型都是從各種具體的并行機(jī)中抽象出來(lái)的，它能在一定程度上反