多核考前复习

一、 选择（每小题1分，共20分）1. Intel Core i7处理器属于flynn分类法区分那种计算机类型（ B ）A.SISD 单指令流单数据流计算机B.MIMD 多指令流多数据流计算机C.SIMD 单指令流多数据流计算机D.MISD多指令流单数据计算机2. 以不属于线程状态的是（ C ）A. 新建B. 运行C. 发布D. 阻塞3. 以下线程状态的转换不可能发生的是（ B ）A. 新建-就绪B. 新建-终止C. 就绪-运行D. 阻塞-就绪4. 并行编程模型中属于显式模型的是（ A ）A. Win32 APIB. OpenMPC. TBBD. PVM5. IEEE为要在各种不同UNIX操作系统上运行一致软件，而定义API的一系列互相关联的标准，这个标准的集合是（ A ）A.POSIXB.Win32C.LSBD.W3C6. 能够在非共享内存系统使用的多核模型是（ C ） A. Win32 APIB. OpenMPC. MPID. TBB7. Intel Vtune的主要作用是（ A ）A. 寻找程序热点B. 检查堆栈使用C. 排除数据竞争D. 优化负载均衡8. Intel Thread Profiler主要用于解决何种问题（ D ） A. 寻找程序热点B. 检查堆栈使用C. 排除数据竞争D. 优化负载均衡9. 不属于任务分解的特点是（ B ）A. 基于应用的自身特点生成线程执行独立的任务。B. 问题的步骤需要同步。C. 线程间可异步执行。D. 线程访问内存时要保证原子性，避免数据竞争。10. 不属于数据分解的特点是（ C ）A. 相同的操作请求不同的数据B. 适合执行密集循环计算C. 可以避免处理数据竞争的问题D. 数据处理可以并行化11. 以下软件工程中的场景，适合任务分解的是（ B ）A.机场使用不同的计算机处理军用和民用航班的信息B.大型软件安装过程中，显示该软件的介绍或教程C.网络游戏公司统计当天用户的平均游戏时间D.使用EditPlus编写代码点击保存时同时生成.bak备份文件12. 以下软件工程中的场景，不适合数据分解的是（ C ）A.分析天文望远镜传回的巨幅照片，发现新的星系。B.股票交易软件分析历史数据，试图找到其中规律C.使用打开较大的Microsoft Word文章时，用户能马上输入文字D.人口普查统计学龄儿童的人数13. OpenMP的调度策略中，将for循环做不平均分块的是（ C ）A. static B. dynamicC. guided D. runtime14. 如果设定Ts表示串行程序在单核上执行的时间，Tp表示在多个核多线程执行的时间，p表示处理器的个数或多核处理器的核数目，关于效率Ep的计算公式是（ B ）A. Ep=Ts/TpB. Ep=Ts/Tp/pC. Ep=Ts/pD. Ep=Tp+p/Ts15. Win32 API编程中创建线程的语句：HANDLE CreateThread (LPSECURITY_ATTRIBUTES lpThreadAttributes, DWORD dwStackSize, LPTHREAD_START_ROUTINE lpStartAddress, LPVOID lpParameter, DWORD dwCreationFlags, LPDWORD lpThreadId); 其中lpStartAddress是指： （ C ）A. 在系统中使用方法进程高级设置B. 线程堆栈大小C. 函数指针，指向实际运行的代码D. 线程ID16. Win32 API编程中，事件一般不适用那种情况（ D ）A. 通知计算完成 B. 通知数据可用C. 通知消息就绪D. 通知外设状态异常17. 不属于OMP对于for循环优化的约束是（ D ） A. 循环语句中的第三个表达式（for循环的步长）必须是整数加或整数减操作，加减的数值必须是一个循环不变量。B. 如果比较操作为,=，那么循环变量的值在每次迭代时都必须减少。C. 循环必须是单入口、单出口，循环内不允许有能够到达循环外的跳转语句，循环外不允许有能够进入到循环内的跳转语句。D. 必须使用Microsoft VC+作为编程语言18. 如果一个程序的全部（所有的代码）只能串行执行，那么（ A ）A. 增加计算机的处理器数量无济于事B. 应该使用OpenMP来优化C. 应该使用Win32API来优化D. 应该使用任务分解的方法19. 线程检查器Intel Thread Checker的主要作用是监控程序执行过程中的线程行为，发现其中存在（ B ）A. 数据同步现象 线程阻塞 线程死锁问题B. 数据竞争现象 线程阻塞 线程死锁问题C. 数据竞争现象 线程同步 线程死锁问题D. 数据竞争现象 线程阻塞 内存不足问题20. 以下那种软件使用了线程池技术 （ A ） A. Apache HttpdB. MS WordC. 360安全卫士D. AutoCAD二、 简答（每小题6分，30分）21. 同时多线程(SMT)类型的处理器和单芯片多处理器(CMP)的本质区别是什么？CMP的执行核心是相互独立的处理器，有自己的执行单元和体系结构资源。SMT多个逻辑执行核心公用执行单元。22. 试述进程和线程的主要区别(1) 进程有独立的地址空间，线程共享进程空间(2) 进程通讯使用操作系统原语，而线程使用的是设计语言原语。(3) 进程上下文切换是重量级的，而线程是轻量级的。23. 关于并行价值可以从哪些方面进行分析？并行代价（经济，资源，人力），资源利用，并行性能预测24. OpenMP使用三种调度策略:static静态,dynamic动态,guided指导来优化for循环的运行，其中guided策略与dynamic相比有什么区别？优点是什么？guided策略程序一次运行的循环块分块由大到小，dynamic策略则分块固定。guided策略块的数目一般比较小，减小调度开销。25. 简述在Win32 API编程中的事件操作中，人工重置事件和自动重置事件的区别：人工重置事件是指使用SetEvent，ResetEvent来激发状态，所有线程均被恢复为可调度线程。自动重置事件当事件被SetEnvet激活后等待时间中，线程中只要有一个返回，系统就会自动将事件设置为非激活状态。三、 填空（每小题2分，共.30分）程序：读取文本文件计算单词数#include #include （26）FILE *fd; int TotalEvenWords = 0, TotalOddWords = 0, TotalWords = 0;const int NUMTHREADS = 4;int GetNextLine(FILE *f, char *Line) if (fgets(Line, 132, f)=NULL) if (feof(f)return EOF; else return 1;int GetWordAndLetterCount(char *Line)int Word_Count = 0, Letter_Count = 0;for (int i=0;i132;i+)if (Linei!=0) & (Linei!=0) & (Linei!=n) Letter_Count+; else if(Letter_Count!=0) if (Letter_Count % 2) TotalOddWords+; Word_Count+;Letter_Count = 0; elseTotalEvenWords+;Word_Count+;Letter_Count = 0; if (Linei=0) break;return (Word_Count); DWORD WINAPI CountWords(LPVOID arg) BOOL bDone = FALSE ; char inLine132;while (!bDone) bDone = (GetNextLine(fd, inLine) = EOF); if (!bDone) TotalWords += GetWordAndLetterCount(inLine) ; （27）return 0 ;int main()HANDLE hThreadNUMTHREADS;fd = fopen(InFile1.txt, r); / Open file for readfor (int i = 0; i NUMTHREADS; i+) hThreadi = （28）CreateThread (NULL,0,CountWords,NULL,0,NULL);WaitForMultipleObjects(NUMTHREADS, hThread, TRUE, INFINITE);fclose(fd); printf(Total Words = %8dnn, TotalWords); printf(Total Even Words = %7dnTotal Odd Words = %7dn, TotalEvenWords, TotalOddWords);程序：积分法计算pi#include stdafx.h#include #include long long num_steps = 1000000000;double step;int _tmain(int argc, _TCHAR* argv)clock_t start, stop;double x, pi, sum=0.0;int i;step = 1./( （29）double )num_steps;start = clock();#pragma omp parallel for private( （30） x) （31）reduction(+:sum)for (i=0; inum_steps; i+)x = (i + .5)*step;sum = sum + 4.0/(1.+ x*x);pi = sum*step;stop = clock();printf(The value of PI is %15.12fn,pi);printf(The time to calculate PI was % （32）f secondsn,(double)(stop - start)/1000.0);return 0;程序：输入文件为一系列的单精度浮点数，找出连续4个浮点数乘积最大的情况，输出首单元序号#include stdafx.h#include #include #include #include #include #define NUM_THREADS 2HANDLE *threadHandles;int num,index=0;float *farray, product=0;CRITICAL_SECTION gCS;DWORD WINAPI comp (LPVOID pArg) float product1,productmax; int i,part,indexfirst; part = *(int*)pArg); indexfirst=part; for ( i=part;iproductmax) productmax=product1; indexfirst=i; （33）EnterCriticalSection(&gCS); if(productproductmax) product=productmax; index=indexfirst; LeaveCriticalSection(&gCS); return 0;int main(int argc, char *argv) struct stat buf; threadHandles = new （34）HANDLENUM_THREADS; int i; int arraynumNUM_THREADS;/*读取文件内容*/ if(stat(argv1,&buf) / get the file size exit(0); num = buf.st_size/sizeof(float); farray = (float *)malloc(buf.st_size); FILE *fp= （35） fopen(argv1,rb); fread( farray, sizeof(float), num, fp); fclose(fp);/*/ （36）InitializeCriticalSection(&gCS); for(i=0;iNUM_THREADS;i+)arraynumi=i; threadHandlesi=CreateThread(NULL, 0, comp, (37)&arraynumi, 0, NULL); WaitForMultipleObjects(NUM_THREADS,threadHandles, (38)TRUE ,INFINITE); DeleteCriticalSection(&gCS);/*/ printf(乘积=% (39)f 首数的序号=%dn, product, index); for(int j=index;jindex+4;j+) printf(farray%d=%f,n,j, (40)farrayj ); free(farray);/*/return 0;四、 综合分析（20分）案例： 最小二乘法应用在研究两个变量(x, y)之间的相互关系时，通常可以得到一系列成对的数据(x1, y1、x2, y2. xm , ym)；将这些数据描绘在x -y直角坐标系中, 若发现这些点在一条直线附近，可以令这条直线方程：Y = b1X +b0。并且这条线对于这些点来说，能够使得各个数据点到该直线的垂直距离最短。最小二乘法就是来计算这条直线的方法。例如：X表示二手车使用的年数，Y表示该年限二手车的平均价格。X：1，2，3，4，5，6，7，8，9，10；Y：26510，19430， 14940， 10870， 7650， 5380，4840， 2900， 2260， 2040；最小二乘法的应用在于给定一个年数，能够根据这些数据反映出估计价格。其公式为：计算该公式的程序如下：sumx = 0.0; sumy = 0.0; sumx2 = 0.0; sumxy = 0.0; for (x = 0; x n; x+) sumx = sumx + x; sumy = sumy + yx; sumx2 = sumx2 + (41)pow (x, 2.0); sumxy = sumxy + (x * yx); b1 = (sumxy - (sumx * sumy) / ( (42)double )n) / (sumx2-(pow(sumx,2.0)/(double)n); b0 = ( (43)sumy - (b1) * sumx) / (double)n;完成其中空白。（6分）44.应该使用何种工具来分析串行程序？你使用的何种并行化策略？为什么？（4分）Intel Vtune经分析得出，计算sumx sumy sumx2 sumxy四个值的for循环部分是程序的热点，可以使用OpenMP作为编程模型，因为OpenMP有专门针对for循环的优化字句。修改后的程序：sumx = 0.0; sumy = 0.0; sumx2 = 0.0; sumxy = 0.0; # （45）pragma omp parallel for （46）reduction( （47）+: sumx, umy, sumx2, sumxy )for (x = 0; x n; x+) sumx = sumx + x; sumy = sumy + yx; sumx2 = sumx2 + (41)pow (x, 2.0); sumxy = sumxy + (x * yx); b1 = (sumxy - (sumx * sumy) / ( (42)double )n) / (sumx2-(pow(sumx,2.0)/(double)n); b0 = ( (43)sumy - (b1) * sumx) / (double)n;48.小明发现他的程序与串行版本相比得出sumx sumy sumx2 sumxy的值都偏小，应该使用何种软件分析问题？可能的问题出在那里？（4分）Intel Thread Checker没有reduction 子句，照成了循环过程中发生了写写冲突，部分计算结果被覆盖。二分 1typedef intMAXSIZE SeqList; 2typedef char KeyType; 3int BinSearch(SeqList R，KeyType K) 4 /在有序表R1.n中进行二分查找，成功时返回结点的位置，