本文概览
问：该课已是20年前的课了，为什么还要学习？回答：据知情人士透露，当下ustc开这门课还是沿用陈院士这份课件。
本文主要贡献：
- 整理详尽的笔记，文字部分大多是老师说过的话。
- 网上能找到的课件与录像有差别，我在录像中逐页截取复原ppt。并分成小段放在合适的位置。
温馨提示：
- 不要因为第一集的音质而放弃（神评：你吼那么大声干嘛啦！），之后剧集有改善。但仍需集中注意力避免空耳。
- 3-6集是另一位教授讲的，还是陈院士的气场听着过瘾，所以暂无3-6集笔记。
- 关于嵌入的课件的问题：经多次尝试，发现把PPT母版背景去掉就可以预览，否则显示“An error occurred”（原因实在不详）。所以，在往后的篇目中均展示白色背景课件。但由于本篇内容网上流传的课件与录像中的差别较大，是我截图下来的，无法编辑，所以仍无法预览。若有需要请点击每个ppt后附带的下载按钮或到本站文件系统看看。
以下是正文
Introduction
首先计算机科学家将任务转换为数值计算问题。计算机科学家选择并行算法和编程语言。特定领域的专家使用这些算法。这都是并行计算研究的范畴。所以在此给出非形式化定义：在并行计算机系统上用多台计算机联合求解一个给定问题就是并行计算。
术语：
- 计算方法：数值分析，考虑的是：收敛时间、精度、计算速度
- 算法：具体实现方法的步骤。即方法+步骤
- 程序：执行算法的一段代码
- 软件：解决问题的一套程序，包括计算程序、工具、环境、可视化等等
以上术语在写论文时不要混用。
【硬件平台】并行计算机系统
分为common architecture与supper architecture。此处非常简短，见ppt。
【理论基础】并行算法
分类
分类是为了方便讲述。所以有不同维度的分类方法。
- 算法：解题方法和步骤的精确描述。
- 并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。
- 数值算法：基于数值计算原理，使用代数运算的一类算法。比如提及矩阵、微分方程求解。
- 非数值算法：基于比较关系，使用符号运算的一类算法。比如sorting类算法。
- 同步算法：一种隐含同步要求的诸进程执行必须相互等待的一类并行算法。
- 异步算法：一种显式同步要求的诸进程执行不必相互等待的一类并行算法。
- 分布算法：泛指由通信链路连接的多个场点或节点，协同完成计算的一类并行算法。物理位置的分散。
- 确定算法：算法的每一步都明确指定下一步如何进行的一类算法。
- 随机算法：算法执行时，随机从指定范围内选择某些参数，以决定算法的运行过程的一类算法。
并行计算模型（重要）
是什么：
- model是公共结构的抽象。
- 曙光、银河是具体的机器，而在model层面可以分成共享存储、分布式存储等等。对于不同种类的架构，设计不同的算法。
包括（三要素）：
- 抽象出一组参数。这组参数能反映并行计算机系统的特性，比如cpu速度、内存。
- 行为：同步或异步。
- 开销函数。在执行前就能预测时间复杂度。
作用：
- model的重要性在于它是算法设计师和体系结构师之间的桥梁。设计算法时，是不知道它将来要运行于哪个机器上的。FFT是很通用的算法，我们希望这个算法设计好后可以运行在各种机器上，而不是只能运行在曙光上。
- 所以要把不同架构抽象为一个数学模型。算法面向这个数学模型来实现。这个模型，确切说是并行算法的设计模型
三代计算模型：
讲这三代是为了说明每一代所考虑的瓶颈是在哪，所以要关注每一代强调什么。第一代认为主要复杂度在于计算。第二代认为瓶颈在通信开销，第三代认为瓶颈是层次化存储模型导致的访存开销。
- 第一代：共享存储模型
- 需要同步
- 内存要多大有多大，带宽要多高有多高
- 不实际
- 但因此出现了很多图灵奖得主
- 第二代：分布式
- 将计算和存储分离
- BSP
- 显式的块同步，将计算划分为多个“super step”，每个“super step”内允许异步计算和通信，但所有处理器必须在“super step”结束时通过全局同步
- 通过三个参数（处理器数p、同步时间间隔L、带宽因子g）抽象计算与通信的分离，强调批量通信与同步的平衡，适合粗粒度并行任务（如大规模图处理）
- LogP
- 隐式同步，通过点对点消息传递完成通信，无需全局同步，允许处理器在等待消息时继续执行其他任务，从而减少同步开销
- 通过四个参数（网络延迟L、处理器通信开销o、带宽间隔g、处理器数P）直接建模网络性能瓶颈，关注细粒度通信的异步性和带宽限制，适用于分布式存储系统
- 第三代：层次化
并行算法的设计策略（policy）和方法（method）
设计策略（policy）
- 直接并行化穿行算法
- 设计全新的并行算法
- 借用
- 例子：图论中所有点对的最短路径 <---> 矩阵乘法
- 要考虑1.当前问题与原问题的相似性对偶性 2.借用的开销
设计方法（method）
- partition
- 一开始就分好了
- 分而治之
- 递归的分解
- pipeline
- 时空特点
- 迭代法
- 要保证问题的解是不断收敛的（近似求解）。收敛性是由数值计算原理确保的。所以我们在使用迭代法时不考虑收敛性，一般考虑的是迭代开销和误差。
mapping，scheduling，load balance的解释
做算法的第一步就是将问题分解。
- 数据分解（domain）
- 某个问题公认使用某个数据集。
- 功能分解/任务分解
- 以计算为中心
然后是将任务变成进程。（算法一旦执行）
从process（进程）到processor（处理器），这个过程叫assignment（指派）或者mapping（映射）。
mapping分为静态mapping与动态mapping。mapping时要注意的问题是 1.负载均衡 2.通讯不能太频繁。而这只是运行前的安排。
当运行过程中，又会出现个性化、不平衡的情况：有些处理器性能好，数据简单，导致运行时间短，另一些处理器运行时间长。这就是另一个问题了：scheduling（调度）或者迁移（migrating）
scheduling就是任务在处理器之间迁移。调度的结果就是决定 1.如何mapping 2.时间的问题：mapping在同一处理器上的任务谁先谁后。scheduling也分为静态scheduling和动态scheduling。
我们的宗旨就是load balance，这也分为静态负载均衡和动态负载均衡。
以后都要学到。
评价指标
speedup（加速比）
- 四个人干到底比一个人干快多少？有个段子讲：盖一幢房子1个人需要10天，那么10个人需要一天，240个人只需1小时。这显然没考虑到并行时的通信开销。
- 所以为了衡量算法的快慢，定义加速比=串行耗时/并行耗时。
- 关于加速比的两个定理
- Amdahl（阿姆达尔）定理：“如果不可加速的比例是0.1，那么用多少个处理器都只能加速10倍”，占据一二十年的历史，让很多做并行的人失去信心转行
- Gustafson（古斯塔夫森）定理（1988）：1024个处理器将任务加速了1023倍，挽救了人们对并行处理技术的信心
- 这两个定理都对，只是前提的设置不同，所以看似结果完全不同。
效率
- 这是为了衡量机器的忙闲程度，利用率
- 定义为效率=加速比/处理器数
scalability（可扩展性）
- 这个翻译并不精准，不然extensibility找谁？
- 可以理解为，放缩能力
- “这个算法，用四个处理器效果是这样的，那用1024个处理器呢，是坏还是好？”
【软件支持】并行程序设计
离不开体系结构。所以先讨论并行计算机体系结构。
语言。
并行化三条路：
- 全自动并行化，全交给compiler：很难。
- 编译制导，可行。
- 并行库。在串行算法中调用并行库函数。
【发展动力】并行应用程序
浅浅的讲。
传统的应用
新型应用