并行計(jì)算-期末考試模擬題原題(共10頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上Reviews on parallel programming并行計(jì)算 英文班復(fù)習(xí)考試范圍及題型：（110章）1 基本概念解釋?zhuān)籘ranslation (Chinese)2 問(wèn)答題。Questions and answer3 算法的畫(huà)圖描述。Graphical description on algorithms4 編程。AlgorithmsReviews on parallel programming并行計(jì)算1 基本概念解釋?zhuān)籘ranslation (Chinese)SMPMPPCluster of WorkstationParallelism, pipelining

2、, Network topology, diameter of a network, Bisection width, data decomposition, task dependency graphs granularity concurrency process processor,linear array, mesh,hypercube, reduction, prefix-sum, gather, scatter, thread s, mutual exclusion shared address space,synchronization, the degree of concur

3、rency, Dual of a communication operation, 2 問(wèn)答題。Questions and answerChapter 1 第1章1)Why we need parallel computing? 1）為什么我們需要并行計(jì)算？答：2)Please explain what are the main difference between parallel computing and sequential computing 2）解釋并行計(jì)算與串行計(jì)算在算法設(shè)計(jì)中的主要不同點(diǎn)在那里？答：Chapter 2 第2章1)What are SIMD, SPMD and M

4、IMD denote? 1）解釋SIMD, SPMD 和 MIMD是什么含義。答：2)Please draw a typical architecture of SIMD and a typical architecture of MIMD to explan.2）請(qǐng)繪制一個(gè)典型的SIMD的體系結(jié)構(gòu)和MIMD的架構(gòu)。答：3)What are the two typical communication models of Parallel Platforms? You can give a short introduction on Massage Passing and Shared addr

5、ess space models.3）并行平臺(tái)的兩個(gè)典型的通信模式是什么？你可以給一個(gè)簡(jiǎn)短的介紹信息傳遞和共享地址空間模型。能說(shuō)出Massage Passing和Shared address space models兩種通訊模型。答：4)In the ideal parallel random access machine(PRAM), what are the meaning of EREW, CREW and CRCW?4）在理想并行計(jì)算模型中（parallel random access machine(PRAM), EREW, CREW, 和CRCW表示的意思是什么？答：Chapter

6、 3 第3章1)Be able to explain at least 2 kinds of the basic decomposition techniques, i.e., Recursive decomposition, Data decomposition, Exploration decomposition and Speculative decomposition.1）能夠解釋的基本的把問(wèn)題分解技術(shù)，至少有2種，例如，遞歸分解，數(shù)據(jù)分解，探索分解和投機(jī)分解。 (1)遞歸分解， 如快速排序 (2)數(shù)據(jù)分解，矩陣乘法，矩陣與向量的乘法，按行或格網(wǎng)的數(shù)據(jù)劃分。 (3)探索分解，人工智能中

7、的狀態(tài)空間的問(wèn)題求解、如16數(shù)碼問(wèn)題。 (4)投機(jī)分解， 利用處理器大多數(shù)時(shí)間處于空閑的特點(diǎn)，把后面可以先計(jì)算的任務(wù)，提前計(jì)算出，在許多情況下會(huì)加速程序的運(yùn)行。如對(duì) case, if 語(yǔ)句的句子同時(shí)計(jì)算出來(lái)。答：2)When the work balance of tasks become bed, which is scheduled based on data decomposition, what methods can improve the work balance of tasks, block-cyclic distribution, Randomized block distr

8、ibutions and graph partitioning.2）當(dāng)平衡工作的任務(wù)成為基于數(shù)據(jù)分解，有什么方法可以改善平衡工作的任務(wù)。 對(duì)稀疏矩陣或在同一數(shù)據(jù)集合上，操作密度不同的計(jì)算，如何達(dá)到調(diào)度平衡的問(wèn)題, 具體方法是什么： (1)block-cyclic distribution （采用在一個(gè)矩陣上循環(huán)安排任務(wù)計(jì)算完成的方法） (2)對(duì)矩陣的下標(biāo)采用隨機(jī)映射的方法 (3)圖劃分的方法答：Chapter 4 第4章1)Be familiar with the basic communication operations as well as their implementations o

9、n the typical models, hypercube, linear array and mesh (graphical description) 1）熟悉的基本通信業(yè)務(wù)，以及對(duì)他們的典型模式實(shí)現(xiàn)，超立方體，線性陣列和網(wǎng)狀（圖形描述）one to all broadcast; all to one reductionall to all broadcast; all to all reductionscatter, gather, all reduce, prefix sum，all to all personalized communication. Circular shift個(gè)

10、人認(rèn)為以下的1-4更為重要，算法實(shí)現(xiàn)沒(méi)必要記住，但是要知道每個(gè)操作具體是怎么做的答：2)be able to use basic communication operation to design parallel algorithms, e.g.matrix-vector multiplication, shortest path trees and minimum spanning tree.2）能使用基本的通信操作設(shè)計(jì)并行算法，例如：矩陣向量乘法，最短路徑樹(shù)和最小生成樹(shù)。答：Chapter 5 第5章1)The formulae of speedup, efficiency and co

11、st of a parallel algorithm and be able to give a short exolaination.1）并行算法的加速，效率和成本的計(jì)算公式，并能給出一個(gè)簡(jiǎn)短解釋。 (1)知道并行算法的分析測(cè)度，以及相應(yīng)的測(cè)度計(jì)算公式。 (2)并行算法并行加速比S，S = Ts/Tp ， Tp 和Ts 表示 并行算法和串行算法的時(shí)間復(fù)雜性。 (3)效率E = E= S/p= Ts/（Tp*p）, (4)費(fèi)用cost = P * Tp答：2)The proof on Amdahls law: If a problem of size W has a serial compon

12、ent Ws, prove that W/Ws is an upper bound on its speedup, no matter how many processing elements are used.2）Amdahl定理的證明：設(shè)W表示某算法A求解問(wèn)題的全部工作量，W= Ws+Wp, 其中 Ws 表示必須串行計(jì)算的工作量；Wp表示可以并行計(jì)算的工作量。試證明該算法的并行加速比的上界是W/Ws ，無(wú)論有多少個(gè)處理單元。答：Chapter 6 第6章1)Be able to describe the program architecture of a MPI program.1）能夠來(lái)

13、描述程序的MPI程序架構(gòu)。 #include <mpi.h> Main(int argc, char *argv) int npes, myrank; MPI_init(&argc, &argv); MPI_Comm_szie(MPI_COMM_WORLD, &npes); MPI_Comm_rank(MPI_COMM_WORLD, &myrank); 并行程序代碼部分 通訊結(jié)束部分 MPI_Finilize() 2)fundimental functions for MPI a)MPI_Init establishing a parallel co

14、mputational environment b)MPI_Finalize closes all parallel tasks c)MPI_Comm_size get the number of processes available d)MPI_Comm_rank get the id of process e)MPI_sendmessage sending functions f)MPI_Recv message receiving functions2）了解MPI的基本函數(shù) 1）MPI_INIT建立一個(gè)并行計(jì)算環(huán)境 2）MPI_Finalize關(guān)閉所有并行任務(wù) 3）MPI_Comm_s

15、ize獲得可用的進(jìn)程數(shù) 4）MPI_Comm_rank得到進(jìn)程ID 5）MPI_send消息發(fā)送功能 6）MPI_Recv消息接收功能3)Blocking and non-block message passing in MPI_Send. a)Return only after the corresponding MPI_Recv have been issued and the message has been sent to the receiver (blocking) completely. b)Initialize a process to copy the message int

16、o a buffer of the destination and then return (non-blocking with a buffer) without waiting the finish of the data transformation. Please give the corresponding sentences for the two kinds of massage passing in MPI.3）能說(shuō)明在MPI_Send中的阻塞的消息傳遞（blocking Message Passing）和無(wú)阻塞的消息傳遞（Non-blocking Message Passin

17、g）的含義和具體如何實(shí)現(xiàn)的。 1)只返回相應(yīng)的MPI_Recv后已經(jīng)下達(dá),消息被發(fā)送到接收器(阻塞)完全。 2)初始化一個(gè)流程來(lái)復(fù)制到緩沖區(qū)的消息的目的地,然后返回(無(wú)阻塞/非阻塞方式的緩沖區(qū))無(wú)需等待完成的數(shù)據(jù)轉(zhuǎn)換。請(qǐng)給相應(yīng)的句子的兩種消息傳入MPI。答：Chapter 7 第7章1)Be able to describe the program architecture of a Pthread program1）說(shuō)明一般利用Pthread編程的程序基本結(jié)構(gòu)（包含那幾個(gè)語(yǔ)句）。答：IEEE指定的一個(gè)標(biāo)準(zhǔn)的線程API，POSIX API。POSIX也稱(chēng)為Pthread線程的創(chuàng)建、終止 pth

18、read_create pthread_exit等待所有線程運(yùn)行完畢以便完成結(jié)果的合并 pthread_joinl #include pthread.h> int pthread_create( pthread_t *thread_handle, /id of the threadconst pthread_attr_t * attribute , void * (*thread_function) (void*), /*the main program content*/ void *arg ）； /*the pointer for the calculated result*/ l

19、int pthread_join ( pthread_t thread, void *ptr)l int pthread_exit()2)Be able to introduce the methods for synchronization, e.g. implementing critical section and atomic operations. Be able to write the corresponding sentences2）介紹同步的方法，例如：實(shí)施的關(guān)鍵部分和原子操作。能夠?qū)懗鱿鄳?yīng)的句子。答：3)Be able to write OpenMP programs fo

20、r matrix multiplication, computation and so on.3）能編寫(xiě)OpenMP程序的矩陣乘法，計(jì)算等。答：4)Be able to compare the advantage and shortcoming of Thread and OpenMP programming.4）能夠比較Thread和OpenMP編程的優(yōu)點(diǎn)和缺點(diǎn)。答：Chapter 8 第8章1)Algorithms for matrix transposition1）矩陣轉(zhuǎn)置算法算法：按mesh連接進(jìn)行塊轉(zhuǎn)置(不同處理器間) 進(jìn)行塊內(nèi)轉(zhuǎn)置(同一處理器內(nèi))答：2)Algorithms for

21、 matrix multiplications 2）矩陣乘法算法答：并發(fā)實(shí)現(xiàn)矩陣與向量的乘法。Chapter 9 第9章Be familiar with at least one sorting network as well as a parallel sorting algorithm.熟悉至少一個(gè)排序網(wǎng)絡(luò)，以及一個(gè)并行排序算法。答：奇-偶排序的并行算法 雙調(diào)排序Chapter 10 第10章Algorithms for shortest paths, Minimum Spanning Tree, Connected Components, Maximal Independent Set.最短路徑，最小生成樹(shù)，連接組件，極大獨(dú)立集的算法。答：3. Graphical description