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

这篇具有很好参考价值的文章主要介绍了山东大学2022-2023多核复习课题目答案整理/往年题整理。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

复习课题目答案整理

快说谢谢刘老师，一般按照复习题考原题！！！
下面是2022-2023的版本，每年基本不变，今年新增CUDA部分，本文已包含相关考点

MPI

基本使用方法在笔记中

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

//n是行数or列数，p是线程数
quotient = n/p;//份额
remainder = n%p;//余数
if(my_rank<ramainder){
    my_n_count = quotient+1;
    my_first = myrank*my_n_count;
}else{
    my_n_count = quotient;
    my_first = my_rank*my_n_count+remainder;
}
my_last = my_first+my_n_count-1;

基本思路就是小于余数的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的结果

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

这样问的前提是每一行的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 <omp.h>
#include <iostream>
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(<op>:<var>),满足交换律即可
//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 【流水线】

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

（a）9ns

（b）9000ns

（c）重点在于，流水线的速度最终取决于最慢的功能单元，那直接看最后一个就可以了，取完成时间为2000ns，中间5步5ns，最后存2ns，共2007ns

习题2.5 【冯诺伊曼结构】

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

加入缓存和虚拟内存不会改变SISD类型，缓存和虚拟内存只是在硬件上缓解了冯·诺依曼瓶颈，没有对指令流和数据流做出改变；

但有些比较复杂的系统，在触发换页的时候会执行别的线程（因为阻塞），其实这是硬件多线程的一种，构成MIMD
加入流水线，提供单指令流，多数据流的服务，类型变为SIMD
加入多发射或硬件多线程，多发射可以看作把一个线程（指令流）在多个ALU上同时启动了一部分，分裂为多个指令流，构成MIMD

硬件多线程是在当前任务被阻塞时，系统试图切换到别的线程继续有用的工作，默认了多线程的存在，构成MIMD

CUDA

变量含义（理解），线程函数中i的计算，考察方式：代码纠错

一个常见的函数核函数形式如下：

__global__ add(){}

使用的时候需要add()<<<x,y>>>

__global__是核函数前缀，表示在主机调用，在设备执行的函数，此外类似的前缀还有__device__ __host__具体情况参见CUDA笔记

上面的x,y都是dim3类型的参数，x表示grid对block的组织方式，y表示block对thread的组织方式。【grid本身也可以被组织，但不考】

block一般组织为二维，thread一般组织为三维

但考试中比较常见的形式是<<<a,b>>> 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

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

两个问题

%操作符很慢，应该尽量避免使用这个符号，%会被CUDA编译成20多条指令，效率低下
- 这个好解决，改成乘法判断就行

注：SM采用的SIMT(Single-Instruction, Multiple-Thread，单指令多线程)架构，warp(线程束)是最基本的执行单元，一个warp包含32个并行thread，所以block大小一般要设计为32的倍数；同时由于SIMD架构，一个warp中的线程行为应尽量一致，如果不一致会带来大幅度的性能降低。

更多：理解CUDA中的thread,block,grid和warp - 知乎 (zhihu.com)