并行計算題目答案匯總

1、第題（1）什么是并行計算？（2）它的優(yōu)點有哪些？（3）可以通過哪些結構完成并行計算？1并行計算就是在并行計算或分布式計算機等高性能計算系統(tǒng)上所做的超級計算。（P3）2計算極大地增強了人們從事科學研究的能力，大大地加速了把科技轉化為生產力的過程，深刻地改變著人類認識世界和改造世界的方法和途徑。計算科學的理論和方法，作為新的研究手段和新的設計與創(chuàng)造技術的理論基礎，正推動著當代科學與技術向縱深發(fā)展。（P4）3單指令多數據流SIMD、對稱多處理機SMP、大規(guī)模并行處理機MPP、工作站機群COW、分布共享存儲DSM多處理機。（P22）第2題什么是網絡計算？它的特點？它與分布式計算、集群計算的關系？（P1

2、04）網絡計算：在工作站機群COW環(huán)境下進行的計算稱為網絡計算。特點：網絡計算結合了客戶機/服務器結構的健壯性、Internet面向全球的簡易通用的數據訪問方式和分布式對象的靈活性，提供了統(tǒng)一的跨平臺開發(fā)環(huán)境，基于開放的和事實上的標準，把應用和數據的復雜性從桌面轉移到智能化的網絡和基于網絡的服務器，給用戶提供了對應用和信息的通用、快速的訪問方式。與分布式計算、集群計算的關系：分布式計算是一門計算機科學，它研究如何把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計算機進行處理，最后把這些計算結果綜合起來得到最終的結果。集群計算是使用多個計算機，如典型的個人計算

3、機或UNIX工作站；多個存儲設備；冗余互聯，來組成一個對用戶來說單一的高可用性的系統(tǒng)。因此，網絡計算與分布式計算和集群計算都是屬于計算密集型，數據密集型和網絡密集型應用。第3題 表征并行系統(tǒng)的性能指標有哪些？并行系統(tǒng)的加速比如何定義？它能否完全確定系統(tǒng)的性能？為什么？a. 表征并行系統(tǒng)的性能指標主要有：CPU和存儲器的基本性能指標，通信開銷以及系統(tǒng)機器的成本、價格與性價比，還有系統(tǒng)加速比和系統(tǒng)可擴放性（p88頁3.3）；其中CPU和存儲器的基本性能指標包括：工作負載，并行執(zhí)行時間，存儲器的層次結構和存儲器的帶寬。b. 并行系統(tǒng)的加速比，是指對于一個給定的應用，并行算法的執(zhí)行速度相對于串行算法的

4、執(zhí)行速度另快了多少倍。c. 加速比并不能完全確定系統(tǒng)的性能；因為評價并行計算性能的指標，除了加速比外，并行計算的可擴放性也是主要性能指標之一即并行系統(tǒng)性能隨處理器數的增加而按比例提高的能力。（個人理解的，大家參考第三章吧）第4題 節(jié)點度的定義？它在并行計算中的作用。（第9頁）作用：百度也沒找到答案。定義：射入或射出一個節(jié)點的邊數稱為節(jié)點度。 在單向網絡中，入射和出射邊之各稱為節(jié)點度。第5題 等效率函數的定義、作用及應用。（P89）參考答案：為了維持一定的效率E（介于0與1之間），當處理器數p增大時，需要相應地增大問題規(guī)模W的值。由此定義函數為問題規(guī)模W隨處理器數P變化的函數，稱此函數為等效率函

5、數。等效率函數是等效率度量標準，而等效率度量是并行計算可擴放性評測的依據之一。應用舉例：按照等效率函數的定義，對于某一并行算法（或并行程序），為了維護運行效率保持不變，隨著處理器數目的增加，若只需增加較小的工作量（即問題規(guī)模），比如說W隨p呈線性或亞線性增長，則表示該算法具有良好的可擴放性；若需要增加非常大的問題規(guī)模，比如說W隨p呈指數級增長，則表示該算法是不可擴放的。第6題 6.1 等速度函數的定義，作用及應用？答：該題的答案在課本P90-P91面?？梢宰孕袇⒖颊n本復習。6.2 表面-容積效應的定義及應用？答：該題答案在課本P168面（2，3，4段）。同學們可以參考復習。第7題 頁數：P16

6、4全局通信：是指有很多任務參與交換數據的一種通信模式，全局通信中，每個任務與很多別的任務通信。局部通信：局部通信時，每個任務只與較少的幾個近鄰通信。結構化通信：結構化通信值，一個任務和其近鄰形成規(guī)整結構（如樹、網格等）。非結構化通信：非結構化通信中，通信網則可能是任意圖。第8題 表面容積效應的定義、應用？（P168）答：定義是一個任務的通信需求比例于它所操作的子域的表面積，而計算需求卻比例于子域的容積。其應用是：表面容積效應啟發(fā)我們，在其他條件等同的情況下，高維分解一般更有效，因為相對于一個給定的容積（計算）它減少的表面積（通信），因此從效率的角度，增加力度的最好辦法是在所有的維組合任務。第9

7、題 mpi編程模型中的基本通信概述MPI(Message Passing Interface)定義：MPI是94年5月發(fā)布的一種消息傳遞接口。它實際上是一個消息傳遞函數庫的標志說明，吸取了眾多消息傳遞系統(tǒng)的優(yōu)點，是目前國際上最流行的并行編程環(huán)境之一。具有的優(yōu)點：具有可移植性和易用性，有完備的異步通信功能；有正式和詳細的精確定義。何為通信體：在基于MPI編程模型中，計算是由一個或多個彼此調用庫函數進行消息收、發(fā)通信的進程所組成。所謂通信體，就是一個進程組加上進程活動環(huán)境，其中進程組就是一組有限和有序的進程的集合。最基本的MPI：MPI_INIT:啟動MPI計算；MPI_FINALIZE:結束MP

8、I計算；MPI_COMM_SIZE：確定進程數；MPI_COMM_RANK：確定自己的進程的標識符；MPI_SEND:發(fā)送一條消息；MPI_RECV:接受一條消息；群體通信：群體通信提供了MPI中獨立的安全的消息傳遞。不同的通信庫使用了獨立的通信體，它隔離了內部和外部的通信，避免了在通信庫被調用的和退出時的同步，也保證了在同一通信體的通信操作胡不干擾。點到點通信的數據傳送有阻塞和非阻塞兩者機制；阻塞和非阻塞有四種通信模式：1、標準模式；2、緩沖模式；3、同步模式；4、就緒模式；第10題 什么事共享存儲并行編程?P323 第二段在共享存儲的編程模式中,各個處理器可以對共享存儲器中的數據進行存取,

9、數據對每個處理器而言都是可訪問到的,不需要在處理器之間進行傳送,即數據通信時通過讀/寫共享存儲單元來完成.它的基本思路是什么? P323 第三段粗體字1任務劃分; 2任務調度 2.1靜態(tài) 調度2.1.1確定模式 2.1.2非確定模式 2.2動態(tài)調度 3任務同步 4任務通信.第11題 MPI基本函數有哪些？每一個函數的作用及使用？參考：352頁。每一函數的作用：參考352353頁 有六個基本函數 MPI_INIT ：啟動MPI計算；MPI_FINALIZE：結束MPI計算；MPI_COMM_SIZE：確定進程數； MPI_COMM_RANK：確定自己的進程標識符；MPI_SEND：發(fā)送一條消息；

10、MPI_RECV：接收一條消息；第12題 找不到第13題 MPI的基本函數有哪些？每個函數的作用及使用？MPI 中有 1.double MPI_Wtime(void) 取得當前時間， 計時的精度有 double MPI_Wtick(void) 取得C/C+ time.h 有 clock_t clock(void) 取得當前時間， 計時的精度有 常數 CLOCKS_PER_SEC 定義。2.Int MPI_Init(int *argc ,char *argv)MPI的初始化例行函數，用于初始化MPI運行的環(huán)境，必須調用，還是首先調用，僅調用一次。3.MPI_Finalize(void) 結束MP

11、I執(zhí)行的環(huán)境，該函數一旦被調用，就不能調用MPI的其它的函數（包括MPI_init）4.MPI_Send(void *buf,int count,MPI_Datatype datatype,int dest,int tag,MPI_Comm comm)將緩沖區(qū)的count個datatype數據類型的數據發(fā)送到目的進程阻塞型：需要等待指定的操作的實際完成，或至少所涉及的數據被MPI系統(tǒng)完全的備份后才返回 如：MPI_Send和MPI_Recv都是阻塞型的。5.MPI_Recv(void *buf,int count,MPI_Datatype datatype,int source,int tag

12、,MPI_Comm comm.,MPI_Status *status)從指定進程source接收信息，并且該數據的類型和本接收進程指定的數據類行一樣6.MPI_Isend(void *buf,int count,MPI_Datatype datatype,int dest,int tag,MPI_Comm comm.,MPI_Requst *request)非阻塞地發(fā)送信息。在發(fā)送數據完成之前，對數據操作是把安全的，因為隨時可能與正在后臺執(zhí)行的MPI操作發(fā)生沖突。所以用戶使用非阻塞型發(fā)送數據必須調用其他函數來等待或查詢操作完成的情況。該函數遞交一個信息發(fā)送的請求MPI系統(tǒng)在后臺完成消息的發(fā)送，

13、請求的句柄通過Request變量返回給MPI進程，供隨后查詢/等待消息的完成用注意：阻塞型和非阻塞型相差一個I。7.MPI_Wait(MPI_Request *request,MPI_Status *status) 通信請求的完成與檢測MPI_Wait是阻塞型函數，必須等待通信的完成才返回。該檢測函數等待，檢測一個通信器請求的完成成功返回時，status中包含關于所完成的通信的信息，相應的通信請求被釋放，request被程MPI_REQUST_NULL。8.MPI_Test(MPI_Request *request,int *flag,MPI_Status *status)MPI_TEST 與

14、MPI_Wait剛好相反的。MPI_TEST是非阻塞函數該函數檢測指定的通信請求，不論通信是否完成都立刻返回9.MPI_Iprobe(int source ,int tag,MPI_Comm comm.,int *flag,MPI_Status *status)消息的探測函數 是屬于非阻塞函數，它不論是否有符合條件的消息都立刻返回10.MPI_Probe(int source ,int tag,MPI_Comm comm.,MPI_Status *status) 消息的探測檢查要接收的信息是否到達 信息到達了才能返回MPI_Probe屬于阻塞型函數，它等待直到一個符合條件的消息到達后才返回如果

15、探測到符合條件的消息flag=true，否則flag=false11.MPI_Get_count(MPI_Status *status,MPI_Datatype datatype,int *count) 該函數返回以指定的數據類型為單位，接收到數據的個數，接收信息是使用的是最大個數，搞函數準確地知道接收信息的個數12.MPI_Type_contiguous(int count,MPI_Datatype oldtype,MPI_Datatype *newtype)新數據類型newtype由count個老數據類型olodtype按域（extent）連續(xù)存放構成.新定義數據類型函數。如：count=

16、5，OLDTYPE=INYTRGER，則新的數據類型NEWTYPE為5個整數13.MPI_Type_vector(int count,int blocklength,int stride,MPI_Datatype oldtype,MPI_Datatype *newtype)新數據類型newtype由count個數據塊構成。每個數據塊由blockelength個連續(xù)存放的oldtype構成。相鄰的兩個數據塊的位移相差stride x extent（oldtype）個字節(jié)新定義數據類型 如：count=3，BLOCKLENGTH=2，STRIDE=3，OLDTYPE=INTEGER，則調用此函數后

17、得到的新的數據類型NEWTYPE為6個整數組成，其中在原始數組中從開始取2個隔1隔再取2個，再隔一個取2個構成14.MPI_Type_indexed(int count,int array_of_blocklengths,int *array_of_displacements,MPI_Datatype, oldtype,MPI_Datatype *newtype)新的數據類型newtype由count個數據塊構成，第i個數據塊包含arry_of_blocklengths(i)個連續(xù)存放的oldtype，字節(jié)位移為arry_of_displacements(i)*extent(oldtype)。

18、ARRAY_OF_BLOCKLENTHS和ARRAY_OF_DLSPLACEMENRS由OLDTYPE定義的元素個數來度量注意：MPI_Type_indexed與MPI_Type_vector的區(qū)別在每個數據塊的長度可以不同，數據塊間也可以不等距15.MPI_Type_commit(MPI_Datatype *datatype)提交數據類型，一個數據類型被提交之后就可以和MPI的原始數據類型完全一樣地在消息傳遞中使用使用自定義的數據類型之前，必須調用此函數16.MPI_Type_free(MPI_Datatype *datatype)釋放指定的數據類型。函數返回后。Datatype將被置成MP

19、I_DATATYPE_NULL。17.MPI_Barrier(MPI_Comm comm)該函數用于進程間的同步。一個進程調用該函數后將等待直到通信器comm中的所有進程都調用了該函數才返回18.MPI_Bcast(void *buffer,int count,MPI_Datatype datatype,int root,MPI_Comm comm)廣播數據 通信器comm中進程號為root的進程（根進程）將自己buffer中的內容同時發(fā)送給通信器的所有其他的進程。19.MPI_Gather(void *sendbuf,int sendcount,MPI_Datatype sendtype,v

20、oid *recvbuf,int recvcount,MPI_Datatype recvtype,int root,MPI_Comm comm)收集數據 所有進程（包括根進程）將sendbuf中的數據發(fā)送給根進程。根進程將這些數據按進程號的順序依次接收到recvbuf中，發(fā)送數據和接收的數據類型與長度必須相匹配。即發(fā)送的類型必須具有相同的序列。20.MPI_Scatter(void *sendbuf,int sendcount,MPI_Datatype sendtype,void *recvbuf,int recvcount,MPI_Datatype recvtype ,int root, M

21、PI_Comm comm)分散數據。指根進程將一個大的數據塊分成小塊分別散發(fā)給各個進程（包括根進程自己）它是數據收集的逆操作21.MPI_Allgather(void *sendbuf,int sendcount,MPI_Datatype sendtype,void *recvbuf,int recvcount,MPI_Datatype recvtype ,MPI_Comm comm)22.MPI_Alltoall(void *sendbuf,int sendcount,MPI_Datatype sendtype,void *recvbuf,int recvcount,MPI_datatype

22、 recvtype ,MPI_Comm comm)全部到全部 每個進程散發(fā)自己的一個數據塊，并且收集并裝所有進程散發(fā)過來的數據塊，我們稱該操作為數據的“全散發(fā)收集”，它既被認為是數據的全收集的擴展，也可以被認為是數據的散發(fā)擴展。23.MPI_Reduce(void *sendbuf ,void *recvbuf,int count,MPI_Datatype datatype,MPI_Op op ,Int root,MPI_Comm comm)在組內所有的進程中，執(zhí)行一個規(guī)約操作，并把結果存放在指定的進程中24.MPI_Allreduce(void *sendbuf ,Void *recvbuf

23、,int count,MPI_Datatype datatype,MPI_Op op,MPI_Comm comm)全規(guī)約25.MPI_Comm_size(MPI_Comm comm.,int *size) 該函數返回與該組通信因子相關的進程數26.MPI_Comm_rank(MPI_Comm comm.,int *rank)該函數返回該進程在指定通信因子中的進程號，每個進程在不同的通信因子中的進程號可能不同。27.MPI_Comm_dup(MPI_Comm comm.,MPI_Comm * newcomm)復制通信因子到newcomm，若復制comm被破壞，原來的comm仍然保存28.MPI_

24、Comm_split(MPI_Comm comm.,int color,int key,MPI_Comm* newcomm)該函數劃分comm所對應的進程組為不相交的字進程組，每個進程組中包含color相同的所有的進程29.MPI_Comm_free(MPI_Comm *comm) 釋放通信因子30.MPI_Intercomm_create(MPI_Comm local_comm,int local_leader.MPI_Comm peer_comm,int remote_leader,int tag,MPI_Comm *newintercomm)第14題 倍增設計技術與流水線設計技術的定義和

25、異同？P151倍增技術又叫指針跳躍技術，特別適合處理以鏈表或有向有根數之類表示的數據結構。每當遞歸調用時，所要處理的數據之間的距離將逐步加倍，經過K步后就可完成距離2的k次方的所有數據的計算。流水線技術基本思想是將一個計算任務t分成一系列子任務t1，t2，tm使得一旦t1完成，后繼的子任務就可立即開始，并以同樣的速率進行計算。第15題 什么是PVP、MPP、COW？它們的異同點。PVP并行向量處理機MPP大規(guī)模并行處理機，它是指由成百上千乃至上萬個處理器組成的大型計算機系統(tǒng)。COW工作站機群，指的是并行計算系統(tǒng)將一群工作站用某種結構的網絡互連起來，充分利用各工作站的資源，統(tǒng)一調度、協調處理，以

26、實現高效并行計算。異同點：（P25）屬性PVPMPPCOW結構類型MIMDMIMDMIMD處理器類型專用定制商用商用互連網絡定制交叉開關定制網絡商用網絡通信機制共享變量消息傳遞消息傳遞地址空間單地址空間多地址空間多地址空間系統(tǒng)存儲器集中共享分布非共享分布非共享訪存模型UMANORMANORMA代表機器Cray C-90，Cray T-90，銀河1號IntelParagon,IBMOption White曙光-1000/2000Berkeley NOW，Alpha Farm第16題 SMP的特點及應用結構？P40 答：共享存儲的SMP系統(tǒng)結構具有如下特懷：對稱性、單地址空間 、高速緩存及其一致性

27、、低通信延遲 缺點：欠可靠、可觀的延遲、慢速增加的帶寬、不可擴放性總線或交叉開關P/CP/CP/CSMSMI/O66應用結構：P24SMP系統(tǒng)使用商品微處理器（具有片上或外置高速緩存），它們經由高速總線（或交叉開關）連向共享存儲器。其系統(tǒng)是對稱的，每個處理器可等同地訪問共享存儲器、I/O設備和操作系統(tǒng)服務！結構如下所示：P23第17題：Amdahl定律主要內容？ 應用范圍及主要結論？ Gustafson定律主要內容？ 應用范圍及主要結論？Sun和Ni定律主要內容？ 應用范圍及主要結論？以上三個定律之間的異同點？ 解：(P83 至 P88)1）Amdah1定律主要內容：P83 固定負載的加速公式

28、：應用范圍及主要結論：應用范圍：對于很多科學計算，實時性要求很高，即在有些類應用中時間是個關鍵因素，而計算負載是固定不變的。主要結論：意味著隨著處理器數目的無限增大，并行系統(tǒng)所能達到的加速之上限為1/f.2）Gustafson 定律： P85應用范圍及主要結論：對于很多大型計算，精度要求很高，即在此類應用中精度是個關鍵因素，而計算時間是固定不變的。它意味著隨著處理器數目的增加，加速幾乎與處理器數成比例的線性增加，串行比例f不再是程序的瓶頸，這對并行系統(tǒng)的發(fā)展是個非常樂觀的結論。2）Sun和Ni定律: P86 應用范圍及主要結論：只要存儲空間許可，應盡量增大問題規(guī)模以產生更好和更精確的解（此時可

29、能使執(zhí)行時間略有增加）。主要結論：G（p）=1時就是Amdahl加速定律； G（p）=p 變?yōu)?f + p（1-f），就是Gustafson加速定律G（p）p，相應于計算機負載比存儲要求增加得快，此時 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加速為高。第18題 并行編程模型有哪些？它們中每一種模型的特點？應用范圍？PRAM模型 P109-110 異步PRAM模型 P110-111 BSP模型 P111-113 logP模型 P113-115第19題 什么是并行計算的系統(tǒng)結構模型？他的分類？每一種系統(tǒng)結構模型的主要特點？比較它們的異同點？目前常用的有哪些結構模型？為

30、什么？1什么是并行計算的系統(tǒng)結構模型？答：沒有找到2他的分類？(P22)答：并行計算的系統(tǒng)結構分兩大類：單指令多數據流SIMD和多指令多數據流MIMD；其中多指令多數據流MIMD包括：并行向量處理機PVP、對稱多處理機SMP、大規(guī)模并行處理機MPP、工作站機群COW和分布共享存儲DSM多處理機。3每一種系統(tǒng)結構模型的主要特點？(P22-P24)PVP：課本沒有講到（平行向量處理機最大的特點是系統(tǒng)中的CPU是專門定制的向量處理器（VP）。系統(tǒng)還提供共享存儲器以及與VP相連的高速交叉開關維基百科）SMP：課本沒有講到（對稱多處理機最主要的特征是系統(tǒng)的對稱性，即每個處理器可以以同等代價訪問各個共享存

31、儲器維基百科）MPP：（P24第二段）它具有如下特性：a. 處理節(jié)點采用商用處理器；b. 系統(tǒng)中有物理上的分布式存儲器；c. 采用高通信帶寬和低延遲的互聯網絡（專門設計和定制的）；d. 能擴放至成百上千乃至上萬個處理器。e. 它是一種異步的機器，程序系由多個進程組成，每個都有其私有地址空間，進程間采用傳遞消息互相作用。DSM：課本沒有講到，網絡沒找到COW：（P24第四段）COW的重要界限和特征是：a. COW的每個節(jié)點都是一個完整的工作站，這樣的節(jié)點有時叫作“無頭工作站”，一個節(jié)點也可以是一臺PC或SMP；各節(jié)點通過一種低成本的商品（標準）網絡（如以太網、FDDI和開關等）互連（有的商用機群

32、也使用定做的網絡）；給節(jié)點內總是有本地磁盤，而節(jié)點卻沒有；節(jié)點內的網絡接口是松散耦合到IO總線上的，而MPP內的網絡接口是連到處理器節(jié)點的存儲總線上的，因而可以是緊耦合式的；一個完整的操作系統(tǒng)駐留在每個節(jié)點中，而MPP中通常只是個微核，COW的操作系統(tǒng)是工作站，加上一個附加的軟軟件層，以支持單一系統(tǒng)鏡像、并行度、通信和負載平衡等。目前常用的有哪些結構模型？為什么？答：課本沒講（最后一段，機群相對于有性能價格比高的優(yōu)勢，所以在發(fā)展可擴放并行計算機方面呼聲很高。）第20題 什么是串行程序設計？（286頁，第二段）它的優(yōu)缺點？（286頁，第三段，點）并行程序設計與串行程序設計的異同點？（287頁，表

33、12.1）為什么從串行程序設計會發(fā)展到并行程序設計？（沒找到） 能否以一個樣例程序來分析？（沒找到）第21題 并行計算的性能評測分類與作用：P78全頁，P88第二段第22題 試分析在現今科技及經濟社會發(fā)展中，有哪些并行需求的模型1計算密集型 2 數據密集型 3 網絡密集型第23 題 什么是并行計算的性能評測？它有什么作用？分作哪幾類？說說每一類性能測評的思路、特點。答：并行計算的性能評測與并行計算機體系結構、并行算法和并行程序設計一道構成了并行研究的四大分支。它是指依據某些性能指對并行計算的性能進行評估和測試。并行計算的性能與所使用的并行計算機本身的性能有關。大致可分為機器級的性能評測、算法級

34、的性能評測和程序級的性能評測。機器機的性能評測主要包括CPU和存儲器的成本、價格和性/價比等；算法級的性能評測主要包括加速、效率和可擴放性等；程序級的性能評測主要包括基本測試程序、數學庫測試程序和并行測試程序等。（77頁）第24題 并行算法的基本設計技術？它又如何分類？每一類的定義？特點和思路？（P140）基本技術：劃分設計技術，分治設計技術，平衡樹設計技術，倍增設計技術，流水線設計技術如何分類：從使用并行處理操作最樸素的思想出發(fā)，就可以導出所謂劃分設計技術，它是將一原始問題分成若干個部分，然后各部分由響應的處理器同時執(zhí)行。從求解問題的方法學和求解策略出發(fā)，則可導出所謂分治設計技術，它是將是一

35、個大而復雜的問題分解成若干個特性相同的子問題，然后使用各個擊破的方法求解之。從針對求解問題的特性出發(fā)，也可導出一些有效的并行算法設計技術，包括平衡樹技術和倍增技術等。每一類的定義、特點、思路：劃分設計技術：P140，分治設計技術：P144，平衡樹設計技術：P149，倍增設計技術：P151 流水線設計技術：P153第25題 概括對共享存儲單元間的讀/寫的限制。可以如何對并行存儲訪問模型分類？各類模型的主要特點？答：高速緩存目錄DIR用以支持分布高速緩存的一致性，在物理上有分布在各節(jié)點的局存，從而形成了一個共享的存儲器。對用戶而言，系統(tǒng)硬件和軟件提供了一個單地址的編程空間。模型分類：（）均勻存儲訪

36、問。特點：1、物理存儲器被所有處理器均勻共享 2、所有處理器訪問任何存儲單元取相同的時間3、每臺處理器可帶私有高速緩存 4、外圍設備也可以以一定形式共享（）非均勻存儲訪問特點：1、被共享的存儲器在物理上是分布在所有的處理器中的，其所有本地存儲器的集合就組成了全局地址空間2、處理器訪問存儲器的時間是不一樣的3、每臺處理器照例可私帶有高速緩存，且外設也可以以某種形式共享。COMA（CacheOnly Memory Access）全高速緩存訪問特點1）各處理器節(jié)點沒有存儲層次結構，全部高速緩存組成了全局地址空間2）利用分布的高速緩存目錄D進行遠程高速緩存的訪問3）中的高速緩存容量一般都大于級高速緩存

37、容量）使用COMA時，數據開始時可任意分配，因為在運行時它最終會被遷移到要用它的地方。CCNUMA（CoherentCache）高速緩存一致性非均勻存儲訪問特點：（） 絕大多數商用CCNUMA多處理機系統(tǒng)都使用基于目錄的高速緩存一致性協議（） 它在保留SMP結構易于編程的優(yōu)點的同時，也改善了常規(guī)SMP的可擴放性問題（） CCNUMA實際上是一個分布共享存儲的多處理機系統(tǒng)（） 它最顯著的優(yōu)點是程序員無需明確地在節(jié)點上分配數據。（）非遠程存儲訪問特點1.所有存儲器均是私有的 2.絕大多數都不支持遠程存儲器的訪問 3.在中，就消失了。頁碼：頁第26題 并行算法的基本設計技術？它又如何分類？每一類的定

38、義？特點與思路？并行算法的基本設計技術：從使用并行處理操作最樸素的思想出發(fā)，就可導出所謂劃分設計技術，它是將一問題分成若干個部分，然后各部分由相應的處理器同時執(zhí)行，這就是最基本的設計技術。它的分類：均勻劃分技術、方根劃分技術、對數劃分技術、功能劃分技術。均勻劃分技術定義、特點與思路（140頁 6.1.1）方根劃分技術定義、特點與思路（141頁 6.1.2）對數劃分技術定義、特點與思路（142頁 6.1.3）功能劃分技術定義、特點與思路（143頁 6.1.4）第27題 如何對并行算法的設計過程分步？每一步的主要內容是什么？P161162答：首先盡量開拓算法的并行性和滿足算法的可擴放性；然后著重優(yōu)

39、化算法的通信成本和全局執(zhí)行時間，同時通過必要的整個過程的反復回溯，以期最終達到一個滿意的設計選擇。也即分為四步：任務劃分、通信分析、任務組合和處理器映射。劃分：將整個計算分解成一些小的任務，其目的是盡量開拓并行執(zhí)行的機會通信：確定諸任務執(zhí)行中所需交換的數據和協調諸任務的執(zhí)行，由此可檢測上述劃分的合理性組合：按性能要求和實現的代價來考察前兩階段的結果，必要時可將一些小的任務組合成更大的任務以提高性能或減少通信開銷映射：將每個任務分配到一個處理器上，其目的是最小化全局執(zhí)行時間和通信成本以及最大化處理器的利用率第28題 在矩陣劃分中，有哪些劃分方法？每一方法的細節(jié)內容？(課本202頁)答：（1）在矩

40、陣劃分中，有兩種常見的劃分方法：帶狀劃分（又稱行列劃分）和棋盤劃分（又稱塊狀劃分）。 （2）帶狀劃分的細節(jié)內容：帶狀劃分分為塊帶狀劃分和循環(huán)帶狀劃分。所謂塊狀帶狀劃分，就是將矩陣整行或整列地分成若干個組，每組指派給一個處理器。所謂循環(huán)帶狀劃分，就是將若干行或若干列指派給一個處理器，而且這些行和列可以是連續(xù)的，也可以是等距相間。 棋盤劃分的細節(jié)內容：所謂棋盤劃分，就是將方陣劃分成若干個子方陣，每個子方陣指派給一個處理器，此時任一處理器均不包含整行或整列。棋盤劃分分為塊棋盤劃分和循環(huán)棋盤劃分。矩陣劃分成棋盤狀可和處理器連成二維網孔相對應。和帶狀劃分相比，棋盤劃分可開發(fā)更高的并行度。第29題 并行計

41、算中，點到點通信的含義？測量方法及方法的內容？點到點通信是指兩臺計算機之間相互交換信息，它具有安全、快捷、直觀、同步和經濟的特點（網上概念）P359第30題 系統(tǒng)的可擴放性與算法的可擴放性的定義是？特點是？ 評價并行計算性能的指標之一，在確定的應用背景下，計算機系統(tǒng)性能隨處理器數的增加而按比例提高的能力。一般情況下，增加處理器數，是會增大額外開銷和降低處理器的利用率的，所以對于一個特定的并行系統(tǒng)、并行算法貨并行程序，它們能否有效利用不斷增加的處理器的能力影視受限的，度量這種能力就是可擴放性?？蓴U放性是算法和結構的組合。 p86第31題 什么是并行算法的復雜度？復雜度作用？可以通過哪些指標來分析

42、？（復雜度的概念在課本并沒有找到，以下為百度并個人總結后的答案）概念：并行算法復雜度指執(zhí)行并行算法時計算機所需占用消耗的資源。作用：復雜度用來衡量一個算法的優(yōu)劣，以便選擇合適算法和改進算法。通過以下幾個指標（第106頁）1、運行時間t(n)：即算法運行在給定模型上求解問題所需的時間，通常包含計算時間和通信時間。2、處理器數p(n)：求解給定問題所用的處理器數目3、并行算法的成本c(n)：定義為算法運行時間t(n)與所需處理器數p(n)的乘積，即c(n)=t(n)*p(n)4、總運算量W(n)：即并行算法所完成的總的操作數量。第32題 在并行計算中，有哪些方法可以實現同步？什么是同步？它有什么作

43、用？參考答案：有同步（Synchronization）是在時間上強使各執(zhí)行進程在某一點必須相互等待。在并行計算的各進程異步執(zhí)行過程中為了確保各處理器的正確工作順序以及對共享可寫數據的正確訪問（互斥訪問），程序員需在算法的適當點設置同步點。同步可用軟件、硬件和固件的辦法來實現，如，在logP模型中的路障是由硬件支持的；在MIMD-SM多處理器系統(tǒng)中用同步語句lock和unlock來確保對共享可寫數據的互斥訪問。（P107）第33題 現有哪些并行編程的風格？每一種特點？答：本人認為該題答案在課本P290面。不過不是十分的肯定。共有五種并行編程的風范：第一：相并行；第二：分治并行；第三：流水線并行；

44、第四：主-從并行；第五：工作池并行每一種的特點書里面P290 面有詳細的解釋，可以參考復習。第34題 論述并行軟件與并行硬件發(fā)展的關系？（P286）答：關系：1、并行軟件的發(fā)展落后于并行硬件；2、和串行系統(tǒng)的應用軟件相比，現今的并行系統(tǒng)甚少且不成熟；3、并行軟件的缺乏是發(fā)展并行計算的主要障礙；4、不幸的是，這種狀態(tài)似乎仍在繼續(xù)著。第35題 現有哪些并行編程風范 每一種的特點現在主要有以下機制并行編程規(guī)范：一：OpenMP編程是基于線程的并行編程模型；一個共享存儲的進程由多個線程組成，OpenMP就是基于已有的線程共享編程模型；其次OpenMP是一個外部的編程模型，而不是自動編程的模型。特點是:

45、簡單，移植性好，可擴展性好等；二：MPI并行編程；特點以下：具有可移植性和易用性；具有完備的異步通信功能；有正式和詳細的精確地定義。三：PVM（parallel virtual machine)并行編程:較為容易修改。四：基于數據并行的并行編程：能對大量的數據進行相同的，彼此獨立的操作。五：HPF（high performance Fortran）并行編程；特點：1、數據并行制導，2、數據映射制導，3、新內部函數和庫函數；第36題 找不到第37題 什么是PCAM設計方法學？它包括哪些內容？ 參考：160頁PCMA：從給定問題的描述出發(fā)，通過四個步驟，即任務劃分、通信分析、任務組合和處理器映射，

46、最終設計出一個能展示出并發(fā)性、可擴放行、局部性和模塊性的并行算法。此過程簡稱為PCAM設計過程，它是一種設計方法學。內容參考書本：第七章第38題 網絡結構的對稱與非對稱判定？各自特點？（找不到）第39題 什么是PCAM設計方法學，它包括哪些內容？不同階段，主要完成的任務？P160P161 答：PCAM設計方法學是實際設計并行算法的自然過程。其基本要點是：首先盡量開拓算法的并發(fā)性和滿足算法的可擴放性，然后著重優(yōu)化算法的通信成本和全局執(zhí)行時間，同時通過必要的整個過程的反復回溯，以期最終達到一個滿意的設計選擇。PCAM是 Partitioning 、Communication 、Agglomeration 和Mapping首字母的拼寫，它們代表了使用此法設計并行算法的四個階段！這四個階段包括：劃分、通信、組合、映射。在設計的第一和第二階段，關注的是并發(fā)性和可擴放性，并尋求開發(fā)出具有這些特性的并行算法。在設計的第三和第四階段，把注意力轉移到局部和別的與性能有關的問題上。第題并行編程工具與串行編程工具的發(fā)展關系？答：沒有找到。第41題 一到一傳輸：是指開始時p（處理器）中保存的信包m，只能按照播送路線發(fā)送到臨近的一個處理器，然后再通過該處理器發(fā)送到下一個處理