山东大学2022-2023多核复习课题目答案整理/往年题整理

复习课题目答案整理

快说谢谢刘老师，一般按照复习题考原题！！！

下面是2022-2023的版本，每年基本不变，今年新增CUDA部分，本文已包含相关考点

MPI

基本使用方法在笔记中

矩阵向量乘法中，行数或者列数不能被线程数整除的情况下，如何分配数据？

//n是行数or列数，p是线程数
quotient = n/p;//份额
remainder = n%p;//余数
if(my_rank 
基本思路就是小于余数的rank多算一份，然后考虑用什么公式去划定一个范围my_first和my_last
 
以n=11，p=3为例子
 
rank
0
1
2
my_n_count
4
4
3
first
0
4
8
last
3
7
10
 
MPI_Reduce的问题，可以看到Process1的调用“写错了”，问最终b和d的结果
 
这样问的前提是每一行的dest是全部一致的，否则会崩溃
确定最终结果的关键在于，提交的output内存位置，实际上只有dest的会被使用，所以以dest的为准
因为MPI是分布式编程模型，我们不可能指定另外一台机器上的目标内存地址，所以除了dest的实际上交个NULL值也可以，因为不会被使用 
假设dest为0，最终结果b=a+c+a=4，d=c+a+c=5
假设dest为1，最终结果d=a+c+a=4, b=c+a+c=5
集合通讯和点对点通讯的区别
 
见课本3.4.3 p69
 
在通信子中，所有进程都必须调用相同的集合通信函数；试图把集合通信函数（eg.MPI_Reduce）和点对点通信函数(MPI_Recv)相匹配的做法是非法的
在集合通信中，每个进程调用时填写的dest_process参数必须保持一致，填写不一致会导致进程崩溃
点对点通信函数使用标签和通信子来匹配，但集合通信中依赖通信子和调用顺序来匹配。
output实际上只对dest有意义，对于其他的进程虽然仍然需要填写该参数，即使是一个NULL值
块划分，循环划分，块-循环划分
 
见课本3.4.6 p72 掌握程度：会画表就行
 
pthread
 
它在复习课中没有涉及，简单列几个
 
pthread_create（） prthead_join（）
 
create中会传入rank变量，上下界的确定和MPI保持一致
 
对于共享编程模型，需要处理临界区问题，接下来就是忙等，互斥量等
 
忙等在面对线程数量大于核数的时候，会大量挂起线程，线程挂起状态和运行状态转换有较大开销
 
后面还有信号量，生产者消费者等【考的概率不大了，课上几乎也没讲，本质不是这门课的内容】
 
OpenMP
 
基本的使用方法见笔记，基本是个自动化的东西，围绕#pragma omp parallel进行的
 
5.1 如果已经定义宏_OPENMP,它是一个int类型的十进制数。编写一个程序打印它的值，解释它的含义。
 
#include #include using namespace std;
int main(int argc, char **argv) {
    cout<<"_OPENMP:"<<_OPENMP;
    return 0;
}
 
结果是_OPENMP：201511
 
答：_OPENMP的输出值具有yyyymm的形式。OPENMP标准声明，只要该宏被定义，代表的是OPENMP标准的发布时间。
 
化解循环依赖
 
#pragma omp parallel for num_thread(count)
//可补充的还有
//reduction(:),满足交换律即可
//default（none）share(a) privite(b)
 
首先不是所有的循环依赖都可以被化解,因为pragma omp for本身就是一条捷径，实在不行可以用类似MPI的思路划定上下界去解答
 
比如：冒泡排序不可化解，奇偶交换排序可以化解
 
PPT中的循环依赖化解是直接找一个公式，每个点分别去算就可以了
 
这部分不难，笔记中更详细点。
 
第2章
 
Cache循环效率，按行访问按列访问哪个快？
 
​ 显然是按行访问快，因为C语言是行主序，多维数组在内存中也是一个超大的一维数组，每次都按高速缓存行可容纳的数量换入换出。按列访问显然在内存中是跳着访问的，会让Cache命中率减低，导致更频繁的换入换出，耗费更多时间，降低运算效率。
 
​ 实际分析中可以分析一下置换次数，来得出效率高低的结论【课本15】
 
Cache一致性问题概念，解决方式及其特点
 
课本2.3.4，p28，并行程序设计导论期末复习_wutu0513的博客-CSDN博客_并行程序设计期末考试
 
习题2.1 【流水线】
 
（a）9ns
 
（b）9000ns
 
（c）重点在于，流水线的速度最终取决于最慢的功能单元，那直接看最后一个就可以了，取完成时间为2000ns，中间5步5ns，最后存2ns，共2007ns
 
习题2.5 【冯诺伊曼结构】
 
 
加入缓存和虚拟内存不会改变SISD类型，缓存和虚拟内存只是在硬件上缓解了冯·诺依曼瓶颈，没有对指令流和数据流做出改变；
 
但有些比较复杂的系统，在触发换页的时候会执行别的线程（因为阻塞），其实这是硬件多线程的一种，构成MIMD
 
 
加入流水线，提供单指令流，多数据流的服务，类型变为SIMD
 
 
加入多发射或硬件多线程，多发射可以看作把一个线程（指令流）在多个ALU上同时启动了一部分，分裂为多个指令流，构成MIMD
 
硬件多线程是在当前任务被阻塞时，系统试图切换到别的线程继续有用的工作，默认了多线程的存在，构成MIMD
 
CUDA
 
变量含义（理解），线程函数中i的计算，考察方式：代码纠错
 
一个常见的函数核函数形式如下：
 
__global__ add(){}
 
使用的时候需要add()<<>>
 
__global__是核函数前缀，表示在主机调用，在设备执行的函数，此外类似的前缀还有__device__ __host__具体情况参见CUDA笔记
 
上面的x,y都是dim3类型的参数，x表示grid对block的组织方式，y表示block对thread的组织方式。【grid本身也可以被组织，但不考】
 
block一般组织为二维，thread一般组织为三维
 
但考试中比较常见的形式是<<>> a,b都是整形值
 
这样子实际上是组织了一个一维有a个block的grid，一维有b个thread的block
 
则我们可以给出映射公式：
 
int i = blockDim.x*blockId.x+threadId.x;
//blockDim指block的尺寸，blockId指目前线程所在block在x维度的位置，threadId同理
//详细见CUDA笔记
  
另外也可能考一下block划分
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Q50ZedGB-1676900597092)(C:\Users\laoshuaib\AppData\Roaming\Typora\typora-user-images\image-20230203193133967.png)]
 
即a=(N+b-1)/b,这样保证一定有一个block
 
共享内存同步问题
 
__share__CUDA中的线程协作主要是通过共享内存实现的。使用关键字**“share”**声明共享变量，将使这个变量驻留在共享内存中，该变量具有以下特征：
 
位于线程块的共享存储器空间中
与线程块具有相同的生命周期
仅可通过块内的所有线程访问
当然，只要对__share__声明的变量进行更新操作，就必须使用__syncthreads()进行同步
 
提高题：Reduction的Kernel1 -->Kernel2
 
两个问题
 
%操作符很慢，应该尽量避免使用这个符号，%会被CUDA编译成20多条指令，效率低下 
这个好解决，改成乘法判断就行
注：SM采用的SIMT(Single-Instruction, Multiple-Thread，单指令多线程)架构，warp(线程束)是最基本的执行单元，一个warp包含32个并行thread，所以block大小一般要设计为32的倍数；同时由于SIMD架构，一个warp中的线程行为应尽量一致，如果不一致会带来大幅度的性能降低。
 
更多：理解CUDA中的thread,block,grid和warp - 知乎 (zhihu.com)
 
 
减少warp分支行为【考点】
 
 
原来的问题在于，奇数号线程空闲，导致warp分支严重
 
 
图中的解决办法是，让线程直接去访问偶数号的位置
 
到这里为止就结束了，但这里还是很简单。。。有时间再看后面的吧，大概率不考了