您的位置: 首页 > 文章 > Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

分类: 文章 • 2023-12-26 23:29:09

1.啥是紧密（compact）：这里的压缩指的是过滤，filter，过滤出一个子集，也就是只留我们想要的（比如一把扑克牌里的方片）

（只计算我们关心的对象才更有意义，计算代价较小，需要更少空间）

2.

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

3.密集运算好一点？为啥

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

第一个稀疏运算要启动52个线程，而其中39个线程都是空的（线程成本较高）

第二个虽然过滤出方片会有成本，但是在接下来的映射步骤中它只启动13个线程

4.过滤的步骤

1）对每个元素进行判定

2）记录进数组里面

3）用不包含扫描的方法记录一共需要多少个地址

4）把过滤出来的结果放进地址里（放进输出数组里）

5.稀疏矩阵的表示方法

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

6.表示出来了怎么算？

将向量（x,y,z）与column的值相对应

列出column的xyz表示形式

之后对应相乘相加即可

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

本质是过滤掉了所有带0的项

所以越稀疏的矩阵越有效

7.排序（并行环境下）

奇偶排序法

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

8.归并排序

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

串行

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

并行

当归并到越顶层的时候，所占用的线程越少，也就是大部分SM都处于空闲状态，这是不利的，那么我们要考虑：

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

处理的三个阶段

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

9.双调排序网

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

什么是双调序列，为啥需要双调序列

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

只有一个转折点的就是双调序列

排序一个双调序列特别容易，为啥呢？

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

可以有效的缩小规模

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

10.单双归并排序

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

11.radix sort基数排序

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

将每个word的序号用二进制表示出来，从二进制表示数的最末位，把是0的按顺序排，再把是1的按顺序排

接着是倒数第二位，以此类推

一共交换的次数与二进制的位数相同

问题的解决难度与问题规模程正相关

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

12.快速排序

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

这就是递归，而到目前为止，我们所学的GPU是不支持递归的，那咋办？

先看自己手里有啥工具

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4

13.键排序（比如按照年级排姓名。如果排的东西太大，就直接另存一下，记一个地址就行）

Udacity cs344-Introduction to Parallel Programming笔记（超详细，CUDA，并行，GPU）---Unit 4