求求并行不要寄

链表操作与分析

MPI常用的API与应用

MPI：一种基于信息传递的并行编程技术（接口标准）。

Pthreads常用的API及其应用、互斥锁、忙等待（自旋锁）的实现与应用

Pthreads标准定义了创建和操纵线程的一整套API。

OpenMP常用的编译指令及其子句应用

用于共享内存并行系统的多处理器程序设计的一套指导性编译处理方案。OpenMp提供了对并行算法的高层的抽象描述，程序员通过在中加入专用的pragma来指明自己的意图，由此编译器可以自动将程序进行并行化，并在必要之处加入同步互斥以及通信。

• parallel指令
  • 用在一个代码段之前，表示这段代码将被多个线程并行执行
    
• for指令
  • 用于for循环之前，将循环分配到多个线程中并行执行，必须保证每次循环之间无相关性。单独使用不会实现并发执行，也不会加快运行速度，需配合parallel，表示for循环的代码将被多个线程并行执行。
    

课本典型案例：矩阵向量乘、曲边梯形面积计算、通过数学求和公式计算π、蒙特卡洛方法计算π、奇偶交换排序。

第一章 为什么要并行计算 2

重点：并行程序设计的重要性

我们需要让程序能够更快地运行，有更加逼真的图像。为了达到这一目的，就需要将串行程序改写为并行程序

1.1 为什么需要不断提升性能

计算问题和需求在增加， 更复杂的问题有待解决

1.2 为什么要构建并行系统

因为我们想要提高计算机的性能，而性能的提高则需要提高晶体管密度
更小的晶体管 = 更快的处理器
更快的处理器 = 更高的能耗
功率消耗增加 = 热量增加
增加的热量 = 不可靠的处理器.
从单核系统转向多核处理器，也就是说我们要引入并行性。

1.4 怎么编写并行程序

任务并行和数据并行 占6分

任务并行
将任务划分为不同的子任务，由不同的核来完成，多个核协同完成总任务
数据并行
是指将待解决问题所需要处理的数据分配给各个核，每个核在分配到的数据集上执行大致相似的操作

2021考题

二.1 简答题
（1）在并行计算任务处理过程中，广泛采用哪两种方法？
答： 任务并行和数据并行 (2 分)
（2）假如 P 教授进行“英国文学调查”的授课，她有 100 个学生，还有 4 个助教。
学期结束的时候，要进行一次期末测试，试卷包括 5 道题，为了给学生打分，P 教
授和他的助教进行试卷批改，可以采用什么方法，并对方法进行阐述。
答：
第一种方案：按照每人批改 100 份试卷中的一道题 任务并行 (2 分)
第二种方案：按照每人批改 20 份试卷 数据并行 (2 分)

核与核之间通常需要进行协同它们的任务.
通信（ Communication ）：一个或多个核将其当前的部分总和发送给另一个核.
负载平衡（ Load balancing ）：在内核之间均匀地分配工作，这样一个内核就不会负载过重。
同步（Synchronization）：因为每个核都有自己的工作节奏，所以要确保核不会比其他核走得太远

1.5 并发并行分布式

并发计算：多个任务可以在任何时刻进行。
并行计算：多个任务紧密合作来解决一个问题。
分布式计算：可能需要与其他程序合作来解决问题。

第二章 并行硬件和并行软件 4

重点：理解什么是并行计算以及并行体系结构、 Flynn 分类法、性能分析、并行加速比与效率；并行程序性能优化

2.1 冯诺依曼体系结构的特点及其瓶颈

瓶颈：主存与CPU之间分离
我们需要知道：

1. 数据和指令是存在主存中的
2. 数据和指令是通过互连结构传输到CPU的，这个互连结构通常是总线。
3. 因为互连结构限定了指令和数据访问的速率，所以程序运行所需要的大部分数据和指令被有效地与CPU隔离开。
   

2.2 冯·诺伊曼模型的改进

三种改进措施：缓存（caching）,虚拟存储器（或虚拟内存）、低层次并行

2.2.1 缓存

缓存将互连通路加宽，使得一次内存访问能存取一整块代码和数据，而不只是单条指令和单条数据。这些块称为高速缓存块或者高速缓存行。
而且不再是将所有数据和指令存储在主存中，可以将部分数据块或者代码存储在一个靠近cpu寄存器的特殊存储器里。

高速缓冲存储器-cahe-缓存

程序访问完一个存储区域往往会访问接下来的区域，这个原理称为局部性。在访问完一个内存区域（指令或者数据），程序会在不久的将来（时间局部性）访问邻近的区域（空间局部性）。

2.2.2 虚拟存储器

如果我们运行一个非常大的程序或者一个访问非常大数据集的程序，所有的指令和数据可能都不能放进主存中。利用虚拟存储器(或虚拟内存)，使得主存可以作为辅存的缓存。它通过在主存中只存放当前执行程序所需要用到的部分，来利用时间和空间局部性；那些暂时用不到的部分存储在辅存的块中，称为交换空间(swap space)中。

2.2.3 低层次并行

指令级并行

指令级并行(Instruction-Level parallelism, ILP)通过让多个处理器部件或者功能单元同时执行指令来提高处理器的性能。有两种主要方法来实现指令级并行：流水线和多发射。流水线是指将功能单元分阶段安排；多发射是指让多条指令同时启动。

流水线多发射问题

• 流水线
  • 一条指令完整的执行步骤包括取指令、指令译码、执行指令三个步骤。流水线方法就是将指令的执行分成若干个小步骤，分别交由不同的线程处理，每个线程只完成自己负责的那一部分。
• 多发射
  • 通过增加硬件的方式，将取指令和指令译码实现并行，一次性取出多条指令，然后分发给多个并行的指令译码器，进行译码，然后对应交给不同的功能单元去处理。这样，在一个时钟周期里，能够完成的指令就不只一条了。这种 CPU 设计，叫作多发射

2.3 并行硬件

2.3.1 Flynn分类法 占6分

Flynn分类法，是基于指令流和数据流的数量对计算机进行分类的方法。

一系列修改那些流经数据处理单元的数据（数据流）的命令，可以被认为是一个指令流。