本笔记为合作笔记，各讲内容分别由下述成员完成：
并行计算主要研究下面几个方面的内容
并行计算可以简单定义为同时利用多个计算资源解决一个计算问题
一般为：
在硬件可达到的性能与应用对性能的需求之间存在正反馈（Positive Feedback Cycle）
大数据时代
迄今为止，CPU 架构技术经历了四代即：电子管（Tube）、晶体管（Transistor）、集成电路（IC）和大规模集成电路（VLSI），这里只关注 VLSI。
VLSI 最的特色是在于对并行化的利用，不同的 VLSI 时代具有不同的并行粒度：
其中，有摩尔定律支持芯片行业的发展：“芯片上的集成晶体管数量每 18 个月增加一倍”。
发展趋势不再是高速的 CPU 主频，而是“多核”。（摩尔定律失效的原因之一）
局限：最终出现“收益下降（diminishing returns）” 这种解决方法的优点：程序员并不需要知道这些过程的细节
后来发展，延申出了并行计算机和并行计算集群。
从硬件角度来讲，今天的单个计算机都是并行计算机，主要体现为：
多个单独的计算机通过网络连接起来形成计算集群
LLNL 并行计算集群
最后得出结论，需要程序员学会并行编程。
用于度量并行程序的加速效果
\[Speedup = \frac{1thread\, execution \, time }{n\, thread \, execution \, time}\\ Speedup = \frac{1}{(1-p)+p/n}\\\]其中，p 表示程序可并发的部分占整个程序的比例。
A classification of computer architectures based on the number of streams of instructions and data
例如：单核计算机
例子：vector processor,GPUs
延申：SPMD,对称多处理器
多指令单数据流
How do uniprocessor computer architectures extract parallelism?
Goal of Computer Architects until about 2002:
Limits to Pipelining
最后得知结论，并行需要暴露给程序员，让软件来实现。
Thread Level Parallelism (TLP) :线程级并行
Concurrency vs Parallelism：并发和并行
定义POSIX: Portable Operating System Interface for UNIX
特点：共享堆，不共享栈
**线程调度：Thread Scheduling **
调度实现方式：
多道程序设计 Multitasking operating system
ILP 与 TLP 关系是什么意思？没看懂
超线程“Simultaneous Multithreading”
定义：既有多线程，又有指令级的并行
超线程，可以更好的占用处理器资源
Program access a relatively small portion of the address space at any instant of time
时间局部性
空间局部性
命中率，内存延迟
A parallel computer is a collection of processing elements that cooperate to solve large problems fast Some broad issues
定义：Multiple Instruction, Multiple Data (MIMD)
通信方式：
Shared memory: Communication through Memory
Message passing: Communication through Messages
For most machines, shared memory built on top of message passing network
Symmetric Multiprocessor
SISD 架构：单核计算机 SIMD 架构：向量处理器，GPUs MISD 架构：（没有符合的知名系统。。） MIMD 架构：现代并行系统
- 流水线有助于带宽而不是延迟
- 带宽受限于最慢的流水线阶段
- 加速潜力 = 流水线级数
- MIPS 流水线的 5 个阶段：Fetch->Decode->Execute->Memory->Write Back
- 流水线 CPI < 1
开销防止任意划分
- 阶段之间锁存器的成本限制了阶段内能做什么
- 设置最小数量的阶段
冒险阻止下一条指令在其指定的时钟周期内执行
- 结构冒险：尝试同时使用相同的硬件执行两个不同的操作
- 数据冒险：指令取决于仍在流水线中先前指令的结果
- 控制冒险：由于控制流程（分支和跳跃）中的指令和决策获取之间的延迟而造成的
超标量增加的冒险的发生
更多冲突的指令（时钟周期）
通过在指令流中查找并行性，称为“指令级并行”，向程序员隐藏并行性。
- 流水线：指令的各个部分重叠
- 超标量执行：同时执行多个操作
- VLIW（极长指令字）：让编译器指定哪些操作可以并行运行
- 向量处理：指定相似的操作组
- 乱序执行：允许长时间操作
动态调度，乱序执行
- 获取一堆指令，确定它们的依赖性并尽可能消除其依赖性，将它们全部扔到执行单元中，向前移动指令以消除指令间的依赖性。
- 如同按顺序执行
投机执行
- 猜测分支的结果，若猜测错误必须能够撤销结果
- 猜测的准确性随着流水线中同时运行的指令数量增加而降低
巨大的复杂性
许多组件的复杂性按 n² 来衡量
- 指令级并行利用循环或直线代码段内的隐式并行操作
- 线程级并行显式地表示为利用多个本质上是并行的线程执行
- 线程可被用于单处理器或多处理器上
- 并发性是指两个任务可以在重叠的时间段内启动、运行和完成。不一定意味着他们两个都会在同一时刻运行.例如在单线程机器上执行多任务。
- 并行性是指任务同时运行，例如多核处理器。
- POSIX: Portable Operating System Interface for UNIX
- Pthread: The POSIX threading interface
- Pthread 包括支持创建并行性、同步，不显式支持通信，因为共享内存是隐式的；指向共享数据的指针传递给线程。
- 只有堆上的数据可共享，栈上的数据不可共享。
- 在 main 之外声明的变量是共享的
- 可以共享堆上分配的对象（如果指针被传递）
- 栈上的变量是私有的，将指向这些变量的指针传递给其他线程可能会导致问题
- 通常通过创建一个大的“线程数据”结构体来完成，该结构体作为参数传递到所有线程中
- 在为 ILP 设计的数据路径中，由于代码中的阻塞或依赖关系，功能单元通常处于空闲状态。
- TLP 用作独立指令的来源，在暂停期间可能会使处理器繁忙。
- 当 ILP 不足时，TLP 被用于占用可能闲置的功能单元。
- 内存系统，而不是处理器速度，往往是许多应用程序的瓶颈。
- 内存系统性能主要由两个参数（延迟和带宽）影响。
- 延迟（Latency）是指从发出内存请求到处理器提供数据的时间。
- 带宽（Bandwidth）是存储系统将数据泵送到处理器的速率。
- 程序在任何时刻访问相对较小的地址空间。
- 时间局部性：如果一个项被引用，它很快就会再次被引用（例如循环、重用）。
- 空间局部性：如果引用了某个项，则其地址接近的项很快就会被引用（例如，直线代码、数组访问）。
- 以最便宜的技术呈现尽可能多的内存。
- 以最快的技术提供的速度提供访问。
- 缓存是处理器和 DRAM 之间的小型快速内存元素。作为低延迟高带宽存储，如果重复使用一条数据，缓存可以减少该内存系统的有效延迟。
- 缓存满足的数据引用部分称为缓存命中率。由存储系统上的代码实现的缓存命中率通常决定其性能。
- 并行结构一般是指并行体系结构和软件架构采取并行编程。主要目的是使更多任务或数据同时运行。并行体系结构是指许多指令能同时进行的体系结构；并行编程一般有以下模式：共享内存模式；消息传递模式；数据并行模式。
- 并行计算机是一组处理元素的集合，它们协同快速地解决一些大问题。
- 对称多处理器：内置多个处理器，共享内存通信，每个处理器运行操作系统的拷贝，例如现在的多核芯片。
- 通过主机的独立 I/O 的非统一共享内存：多处理器，每个都有本地内存，通用可扩展网络，节点上非常轻的 OS 提供简单的服务，调度/同步，用于 I/O 的网络可访问主机。
- 集群：多台独立机接入通用网络，通过消息沟通。
开头举了许多并行编程的模型的例子：计算$\pi$
1970s – early 1990s，并行机由它的并行模型和语言唯一决定。
Historically (1970s – early 1990s), each parallel machine was unique, along with its programming model and language。
并行架构发展迅猛：
从并行机器架构中分理出并行编程模型
具体化的通信和同步机制（Specifies communication and synchronization）
主要的：
共享内存（shared address space）: openMP
消息传递（message passing）: MPI
Tasks share a common address space
任务通过异步读取和写入此空间进行交互（Tasks interact by reading and writing this space asynchronously）
数据并行（data parallel）：eg: GPU
Data usually evenly partitioned across tasks
其他：
1. Control 控制
2. Naming 变量声明
3. Operations 操作
4. Cost 开销
Any processor can directly reference any memory location
便捷性：Convenient
Location transparency（位置透明）
类似的编程模型，以便在单处理器上进行时间共享
（Similar programming model to time-sharing on uniprocessors）
一般利用进程和线程来是实现
读写异步
tasks share a common address space, which they read and write asynchronously。
Various mechanisms such as locks / semaphores may be used to control access to the shared memory
优点
An advantage of this model from the programmer’s point of view is that the notion of data “ownership” is lacking, so there is no need to specify explicitly the communication of data between tasks。
Program development can often be simplified。
缺点
单机上，依赖编译器和硬件将程序变量转换成实物理地址，即全局地址。
Native compilers and/or hardware translate user program variables into actual memory addresses, which are global。
在分布式系统中，内存物理上分布在同一网络不同机器上，但是通过软件和硬件转换成全局地址。
On distributed shared memory machines, such as the SGI Origin, memory is physically distributed across a network of machines, but made global through specialized hardware and software。
SAS Machine Architecture
其中的典型架构：对称多处理器 One representative architecture: SMP
下面是实现原理
Used to mean Symmetric MultiProcessor：
All CPUs had equal capabilities in every area, e.g., in terms of I/O as well as memory access
Evolved(发展) to mean Shared Memory Processor：
Non-message-passing machines (included crossbar as well as bus based systems 系统总线)
Now it tends to refer to bus-based shared memory machines：
Small scale: < 32 processors typically
上面的架构在规模一大会出现问题（左图是有问题的初始架构，右边是改进的）
左边的问题：
互连的总线等成本问题 （Problem is interconnect）：
cost (crossbar) or bandwidth (bus)
带宽不会提升（Dance-hall: bandwidth is not scalable, but lower cost than crossbar）
改进成右边：
Distributed memory or non-uniform memory access (NUMA)：
Construct shared address space out of simple message transactions across a general-purpose network (e.g. read-request, read-response)。
呃……操作系统也学了，不说了
算了还是说一下：
利用 Amdahl’s Law 定律，分析如下：有的部分不能并行
还有其他的问题：
问题出在，一图便知：
有下列两种含义：
注意事项：Considerations
任务包含数据和它的进程，任务被调度到线程上进行执行（A task consists the data and its process, and task scheduler will attach it to a thread to be executed）。
任务有静态调度和动态调度。
额…RC 问题，还不知道吗？那操作系统挂定了…
定义：
一般来说，指的是多个线程在同一时间访问同样的内存位置，其中至少有一个线程进行写操作。
解决：
定义：
2 or more threads wait for each other to release a resource。
解决：
- 历史上（70 年代至 90 年代初），每台并行机都是独一无二的，其编程模型和语言也是独一无二的。架构=程序模型+通信抽象+机器，并行架构与编程模型相关。
- 现在，我们将编程模型与底层的并行机器体系结构分离开来。
- 主要编程模型有：共享地址空间、消息传递、数据并行；其他类型有：数据流、收缩阵列。
- 通过扩展“计算机体系结构”以支持通信与合作。旧：指令集架构；新：通信架构。
- 定义：关键抽象、边界和接口；实现接口的组织结构。
- 编译器、库和操作系统是重要的桥梁。
- 多道程序设计：无通信或同步，在程序级别
- 共享地址空间：如公告板
- 消息传递：如信件或电话，明确的点到点
- 数据并行：对数据进行更严格的全局操作，使用共享地址空间或消息传递实现
- 消息传递（message passing）：封装本地数据的独立任务，任务通过交换消息进行交互。
- 共享内存（shared memroy）：任务共享公用地址空间，任务通过异步读写此空间进行交互。
- 数据并行化（data parallelization）：任务执行一系列独立的操作，数据通常在任务之间均匀分区，也被称为“令人尴尬的并行”。
- 控制：如何创建并行性；应按什么顺序进行操作；不同的控制线程是如何同步的
- 命名：什么数据是私有的还是共享的；如何访问共享数据
- 操作：什么操作是原子操作
- 成本：我们如何计算运营成本
- 任何处理器都可以直接引用任何内存位置，由于加载和存储而隐式发生通信；方便；位置透明度；与单处理器时间共享类似的编程模型。
- 在这个编程模型中，任务共享一个公共地址空间，它们异步读写。可以使用各种机制，如锁/信号灯来控制对共享内存的访问。从程序员的角度来看，该模型的一个优点是缺乏数据“所有权”的概念，因此无需明确规定任务之间的数据通信。程序开发通常可以简化。在性能方面的一个重要缺点是，越来越难以理解和管理数据位置。将数据保持在处理器的本地，这样可以节省在多个处理器使用相同数据时发生的内存访问、缓存刷新和总线流量。不幸的是，控制数据位置很难理解，并且超出了普通用户的控制范围。
- SAS Machine Architecture
- Scaling Up
- 数据分解：将整个数据集分解为更小、离散的部分，然后并行处理它们
- 任务分解：根据独立子任务的自然集合划分整个任务
- 任务由数据及其进程组成，任务调度程序会将其附加到要执行的线程上。
- 任务操作比线程操作便宜得多。
- 通过窃取轻松平衡线程之间的工作量。
- 任务适合列表、树、地图数据结构
任务比线程多
- 更灵活地安排任务
- 轻松平衡工作量
任务中的计算量必须足够大，以抵消管理任务和线程的开销。
静态调度
任务是独立函数调用的集合，或者是循环迭代
动态调度
任务执行长度可变且不可预测 可能需要一个额外的线程来管理共享结构以保存所有任务
- 线程之间“竞争”以获取资源；执行令被假定，但不能保证;存储冲突最常见；多个线程并发访问同一内存位置，至少有一个线程正在写入；可能在任何时候都不明显
- 注意事项：互斥和同步、临界区、原子操作
- 两个或多个线程等待彼此释放资源；一个线程等待一个永远不会发生的事件，比如挂起的锁。
- 注意事项：始终按相同顺序锁定和解除锁定，并尽可能避免层次结构；使用原子操作
- 它在多个线程同时执行期间正常工作。
- 非线程安全标志 访问全局/静态变量或堆 分配/重新分配/释放具有全局范围（文件）的资源 通过句柄和指针间接访问
- 注意事项
任何更改的变量必须是每个线程的本地变量 例程可以使用互斥来避免与其他线程冲突
- 所有线程以相同的方式处理数据，但一个线程分配了更多的工作，因此需要更多的时间来完成它并影响整体性能。
- 注意事项
使内环平行
向细粒倾斜 选择合适的算法 分而治之，master and work, work-stealing
- 较大实体的细分程度，粗粒意味着越来越少的成分，细粒度意味着越来越小的成分
- 注意事项：细粒度将增加任务调度程序的工作量；粗粒度可能导致工作负载不平衡；设定适当粒度的基准
- 保护共享数据并确保任务按正确顺序执行，使用不当会产生副作用
- 注意事项
选择适当的同步原语 使用非锁定锁 降低锁粒度 不要做一个锁中心 为共享数据引入并发容器
主要分四个步骤：(Decomposition)解耦、(Assignment)分派、（Orchestration）配置、(mapping)映射。
图解如下：
Break up problem into tasks that can be carried out in parallel.
创建最少任务且使得所有的机器上的执行单元都处于忙碌状态
识别出依赖部分。（identifying dependencies）
一般是程序员来做这件事情。
分发任务给线程。
负载均衡，减少通信开销。
静态动态皆可，一般需要程序员来负责，也有非常多语言可以自动对此负责。
减少通信和同步的开销，保护数据的局部性，减少额外开销(overhead).
Mapping “threads” to hardware execution units.
分为四个部分：
图解：
Dividing computation and data into pieces
event-handler for GUI
another eg:
3D rendering in computer graphics
定义：
Determine values passed among tasks
分类：
Grouping tasks into larger tasks（小任务变大任务）
（提升性能）Improve performance：
（保持问题的可并行性）Maintain scalability of program：
举例：
（简化编程）Simplify programming (reduce software engineering costs)：
在消息传递型的编程模型中：In message-passing programming, goal often to create one agglomerated task per processor.
把任务分配到处理器上的过程：Process of assigning tasks to processors
分两种情况：静态任务和动态任务
静态任务(Static number of tasks)
Structured communication（有解构的通信）
Constant computation time per task
(a) Agglomerate tasks to minimize communication (b) Create one task per processor
Variable computation time per task
(a) Cyclically map tasks to processors
Unstructured communication（无结构的通信）
动态任务(Dynamic number of tasks)
决策树如下：
什么是增量式并行化？ Study a sequential program (or code segment) 研究串行程序（代码段） Look for bottlenecks & opportunities for parallelism 寻找并行性的瓶颈和机会 Try to keep all processors busy doing useful work 尽量让所有的处理器做有用的工作
Culler 并行设计流程？
Foster 并行设计流程？ Partitioning（划分） communication（通信） Agglomeration(归并，组合) mapping(聚合)
按数据分解和按任务分解的特点？ Exploit data parallelism 利用数据并行性 (Data/domain partitioning/decomposition) Divide data into pieces 将数据分成几部分 Determine how to associate computations with the data 确定如何将计算与数据相关联
Exploit task parallelism 利用任务并行性 (Task/functional partitioning/decomposition) Divide computation into pieces 将计算任务分成几部分 Determine how to associate data with the computations 确定如何将数据与计算关联
并行任务分解过程中应该注意的问题有哪些？ First, divide tasks among processors Second, decide which data elements are going to be accessed (read and/or written) by which processor
整合的意义是什么？ Improve performance 提高性能 Maintain scalability of program 保持程序的可扩展性 Simplify programming (reduce soft ware engineering costs) 简化编程（降低软件成本）
short version:Open Multi-Processing 开放多处理过程 long version: Open specifications for Multi-Processing via collaborative work between interested parties from the hardware and software industry, government and academia
OpenMP is an explicit (not automatic) programming model, offering the programmer full control over parallelization 一种显式（非自动）编程模型，为程序员提供对并行化程序的控制
OpenMP programs accomplish parallelism exclusively （仅仅） through the use of threads 通过对线程的使用来完成程序的并行化
#pragma omp parallel // 表明之后的结构化代码块被多个线程处理
#pragma omp parallel num_threads(thread_count) // 可自定义线程数量
omp_get_thread_num
omp_get_num_threads
#pragma omp critical // 只有一个线程能够执行对应代码块,并且第一个线程完成操作前，没有其他的线程能够开始执行这段代码
#pragma omp parallel for // parallel for 指令生成一组线程来执行后面的结构化代码块（必须是for循环）。
所有的 OpenMP 指令都有#pragma omp
private
private 子句可以解决私有变量的问题，一些共享变量在循环中，如果每个线程都可以访问的话，可能会出错，该子句就是为每个线程创建一个共享变量的私有副本解决循环依赖，如下所示。注 private 的括号中可以放置多个变量，逗号分隔
#pragma omp parallel for private (x)
for (i = 0; i <= 10;i++) {
x = i;
printf("Thread number: %d x: %d\n",omp_get_thread_num(),x);
}
int x = 44;
#pragma omp parallel for firstprivate (x)
for (i=0;i<=1;i++) {
//x = i;
printf("Thread number: %d x: %d\n",omp_get_thread_num(),x);
}
printf("x is %d\n", x);
lastprivate
告诉编译器，将最后一个离开并行化块的线程的最后一次循环迭代的私有副本赋值给原先的共享变量
int x = 44;
#pragma omp parallel for lastprivate (x)
for (i = 0;i <= 1;i++) {
x = i;
printf("Thread number: %d x: %d\n",omp_get_thread_num(),x);
}
printf("x is %d\n", x);
master
sections
#pragma omp parallel sections 在这条指令后的代码块才是进行并行执行，里面每一个 section 都只需要一个线程去执行，当然如果一个线程足够快允许实现，他可以执行多个 section
#pragma omp sections
{
#pragma omp section
{
printf("section0,threadid=%d\n",omp_get_thread_num());
sleep(1);
}
#pragma omp section
{
printf("section1,threadid=%d\n",omp_get_thread_num());
sleep(1);
}
#pragma omp section
{
printf("section2,threadid=%d\n",omp_get_thread_num());
sleep(1);
}
}
#pragma omp parallel sections num_threads(4)
{
#pragma omp section
{
printf("section3,threadid=%d\n",omp_get_thread_num());
sleep(1);
}
#pragma omp section
{
printf("section4,threadid=%d\n",omp_get_thread_num());
sleep(1);
}
#pragma omp section
{
printf("section5,threadid=%d\n",omp_get_thread_num());
sleep(1);
}
}
reduction
#pragma omp ……reduction<opreation : variable list>
opreation +、-、* 、& 、| 、&& 、|| 、^ 将每个线程中的变量进行规约操作例如 #pragma omp ……reduction<+ : total>就是将每个线程中的 result 变量的值相加，最后在所有从线程结束后，放入共享变量中，其实这也可以看作是 private 子句的升级版，下面的例子，最后共享的 total 中存入就是正确的值(浮点数数组数字之和)，其他操作符的情况可以类比得到
float total = 0.;
#pragma omp parallel for reduction(+:total)
for (size_t i = 0; i < n; i++) {
total += a[i];
}
return total;
barriers(障碍，屏障) memory fence(内存屏障) mutual exclusion(互斥)
The process of managing shared resources so that reads and writes occur in the correct order regardless of how the threads are scheduled 用户进程共享资源让读和写的操作以正确的顺序发生，无论线程是如何安排。
barriers mutual exclusion pthread_mutex_lock
A synchronization point at which every member in a team of threads must arrive before any member can proceed
double area, pni, x;
int i, n;
area = 0.0;
for (i = 0; i <n; i++) {
x = (i + 0.5)/n;
area += 4.0/(1.0 + x*x);
}
pi = area / n;
如果两个线程同时执行 area += 4.0/(1.0 + x*x);可能会在一个线程更新 area 的值之前另一个线程就对 area 进行读操作
- 这个for循环的并行会导致竞争的发生，原因是因为多个线程对同一个共享变量访问时间的非确定性导致结果可能出错，多个线程访问area += 4.0 / (1.0 + x*x)就可能导致竞争
```C
double area, pni, x;
int i, n;
...
area = 0.0;
#pragma omp for
for (i = 0; i <n; i++) {
x = (i + 0.5)/n;
area += 4.0/(1.0 + x*x);
}
pi = area / n;
```
Scope variables to be private to threads 设置线程专用的范围变量 如： Use OpenMPprivate clause 使用 openmpprivate 子句 Variables declared within threaded functions 在线程函数中申明变量 Allocate on thread’s stack (pass as parameter) 在线程堆栈上分配（作为参数传递）
Control shared access with critical region 控制关键区域的共享访问 如： Mutual exclusion and synchronization 互斥和同步
- 1. 变量私有化
- 使用OpenMP的private子句将变量变为私有
- 在线程函数内声明变量，这样变量将属于这个线程
- 在线程堆栈上进行分配
- 2、将共享变量放置进入临界区
- 3、互斥访问
- 信号量
- 互斥锁机制
Critical 确保一次只有一个线程执行结构化代码。
atomic 只能用在形如 x
- #pragma omp critical该指令保护了
1、WorkOne(i)的调用过程，也就是在WorkOne(i)函数内部也是临界区
2、从内存中找到index[i]值的过程
3、将WorkOne(i)的值加到index[i]的过程
4、将内存中index[i]更新的过程
后面跟的语句相当于串行执行
```C
#pragma omp parallel for
{
for(int i = 0; i < n; i++) {
#pragma omp critical
x[index[i]] += WorkOne(i);
y[i] += WorkTwo(i);
}
}
```
- Atomic指令只对一条指令形成临界区，而且语句的格式收到限制
1、将WorkOne(i)的值加到index[i]
2、更新内存中index[i]的值
只将单一一条语句设置为临界区
如果不同线程的index[i]非冲突的话仍然可以并行完成
只有当两个线程的index[i]相等时才会触发使得这两个线程排队执行这条语句
```C
#pragma omp parallel for
{
for(int i = 0; i < n; i++) {
#pragma omp atomic
x[index[i]] += WorkOne(i);
y[i] += WorkTwo(i);
}
}
```
核心利用率的衡量标准，计算公式为加速比/核心数
加速比：Speedup = 串行执行时间/并行执行时间
n 问题规模
p 核心数
S(n,p) 问题的加速比
Ts(n) 串行部分的时间花费
Tp(n) 并行部分的时间花费
Tr(n,p) 并行开销
S(n,p)<=( Ts(n)+Tp(n) )/( Ts(n)+Tp(n)/p+Tr(n,p) )
最大加速比：
Tp(n)/p：假设并行计算部分可以在核心完美分配
Tr(n,p)趋向于0
加速比是关于问题规模的递增函数
- Amdahl太过乐观，很多并行处理开销并没有考虑
1. 创建和终止线程所花费的时间，这是多线程并行的必须开销。
2. 工作量在核心之间平均分配，但是在实际运行时，这并不成立，先执行完任务的核心等待时间是另一种形式的开销，即所谓的负载不均衡。
- 所以进行Amdahl公式的改进，加上线程开销部分, 为了获得最大的加速比，我们就需要将并行开销尽可能减小，同时使用更多的核,改进后的公式如下所示
$\psi(n,p) \leq \frac{\sigma(n) + \varphi(n)}{\sigma(n) + \frac{\varphi(n)}{p} + \kappa(n,p)}$
n - 问题规模
p - 核心数
$\psi(n,p)$ - 在问题规模为n核心数为p的情况下并行的加速比
$\sigma(n)$ - 代码串行部分执行时间
$\varphi(n)$ - 代码并行部分执行时间
$\kappa(n,p)$ - 并行开销
- 如下图表示当我们的问题规模达到一定程度后，并行程序的加速比主要由并行部分来决定，因为随着问题规模的增加，程序串行部分也会逐渐较少，同时并行部分将占据主要时间，可以忽略掉串行时间的影响，加速比主要由并行部分决定
schedule (static [, chunk])
最好用作动态的特殊情况，以在计算越来越耗时的情况下减少调度开销
OpenMP 的调度方案，影响着循环迭代映射到线程的方式 动态调度：在执行循环期间分配线程的迭代次数 静态调度：在执行循环前分配线程的迭代次数
shedule(type[ , chunksize])子句是进行循环调度的指令
#pragma omp parallel for shedule(static, 2)
for(int i = 0; i < 12; i++) {
for(int j = 0; j <= i; j++) {
a[i][j] = ......
}
}
其具体分配如下，同一种颜色代表分配给同一个线程的任务
#pragma omp parallel for shedule(dynamic, 2)
for(int i = 0; i < 12; i++) {
for(int j = 0; j <= i; j++) {
a[i][j] = ......
}
}
#pragma omp parallel for shedule(guided)
for(int i = 0; i < 12; i++) {
for(int j = 0; j <= i; j++) {
a[i][j] = ......
}
}
Exchanging the nesting of for loops may
交换的嵌套 for 循环可以
Improve parallel program’s locality
提高并行程序的局部性
float *a, *b;
......
for(int i = 0; i < N; i++) {
//perfectly parallel
if(b[i] > 0.0) a[i] = 2.0;
else a[i] = 2.0 * fabs(b[i]);
//loop-carried dependence
b[i] = a[i - 1];
}
float *a, *b;
......
#pragma omp parallel
{
#pragma omp for
for(int i = 0; i < N; i++) {
//perfectly parallel
if(b[i] > 0.0) a[i] = 2.0;
else a[i] = 2.0 * fabs(b[i]);
//loop-carried dependence
}
#pragma omp for
for(int i = 0; i < N; i++) b[i] = a[i - 1];
}
Loop fusion
float *a, *b, x, y;
......
for(int i = 0; i < N; i++) a[i] = foo(i);
x = a[N - 1] - a[0];
for(int j = 0; j < N; j++) b[i] = bar(a[i]);
y = x * b[0] / b[N - 1];
float *a, *b, x, y;
......
#pragma omp parallel for
for(int i = 0; i < N; i++) {
a[i] = foo(i);
b[i] = bar(a[i]);
}
x = a[N - 1] - a[0];
y = x * b[0] / b[N - 1];
float *a, *b, x, y;
......
#pragma omp parallel
{
#pragma omp for //末尾存在隐式路障
for(int i = 0; i < N; i++) a[i] = foo(i);
#pragma omp single
x = a[N - 1] - a[0];
#pragma omp for //末尾存在隐式路障
for(int j = 0; j < N; j++) b[i] = bar(a[i]);
y = x * b[0] / b[N - 1];
}
Loop exchange
嵌套 for 循环交换循环顺序可能可以产生新的可并行化循环，或者可能增加并行循环的粒度
串行代码
for (int j =1; j < n; j++)
for (int i = 0; i < m; i++)
a[i][j] = 2 * a[i][j-1];
for (int j =1; j < n; j++)
#pragma omp parallel for
for (int i = 0; i < m; i++)
a[i][j] = 2 * a[i][j-1];
并行结果如下，数组每一列数据交给线程组进行并行化，一个线程一次得到的任务只有数组中一个元素，频繁的进行划分可能导致并行开销增大
#pragma omp parallel for
for (int i =1; i < n; i++)
for (int j= 0; j < m; j++)
a[i][j] = 2 * a[i][j-1];
并行结果如下，直接将整个数组按行划分给线程，一个线程一次得到的任务有一行的，并行循环粒度较高
每个独立的处理器（processor）都有独立私有的内存，通过互联网络连接起来的分布式内存系统，利用消息传递来编程的模型。
支持消息传递模型的系统的逻辑由 p 个处理器组成，每个处理器都有自己专用的地址空间
这两个约束虽然很繁重，但却使底层成本对程序员非常明确。
消息传递程序通常使用异步或松散同步的范例编写。
在异步模式中，所有并发任务都是异步执行的。
在松散同步模型中，任务或任务子集同步以执行交互。在这些交互之间，任务完全异步执行
大多数消息传递程序是使用单程序多数据（SPMD）模型编写的。
Non-buffered blocking => Buffered blocking
Buffered blocking 的操作
注意：\
a、缓冲区大小可能对性能影响显著
b、由于接受操作块（send-recv）的存在，使用缓冲块仍然可能出现死锁
相应的数据结构包含
typedef struct MPI_Status {\
int MPI_SOURCE;\
int MPI_TAG;\
int MPI_ERROR; };
int MPI_Get_count(MPI_Status *status, MPI_Datatype datatype, int *count)
MPI_Group_incl():进程集形成一个进程组\
MPI_Comm_create():为新的进程组创建一个通信子\
MPI_Comm_rank():为新的进程组定义序号\
MPI_Comm_free():释放进程组的资源\
MPI_Group_free():解进程组
MPI_Isend() 和 MPI_Irecv()
MPI provides an extensive set of functions for performing common collective communication operations.
MPI 提供了一套广泛的函数来执行公共的集体通信操作
Each of these operations is defined over a group corresponding to the
communicator.
这些操作都是在通信子对应的一个进程组上定义的
All processors in a communicator must call these operations.
在同一个通信子中的处理器必须调用这些操作
The barrier synchronization operation is performed in MPI using:
int MPI_Barrier(MPI_Comm comm) （阻塞到所有进程完成调用)
The one-to-all broadcast operation is:
int MPI_Bcast(void *buf, int count, MPI_Datatype datatype,
int source, MPI_Comm comm) The all-to-one reduction operation is:
int MPI_Reduce(void *sendbuf, void *recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, int target,
MPI_Comm comm)
int MPI_Reduce(void *sendbuf, void *recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, int target,
MPI_Comm comm)
Collective Commumication Operations
>>>int MPI_Allreduce(void *sendbuf, void *recvbuf,
>>>int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm
comm)
To compute prefix-sums, MPI provides:
int MPI_Scan(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)
The gather operation is performed in MPI using:
int MPI_Gather(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype recvdatatype, int target, MPI_Comm comm)
MPI also provides the MPI_Allgather function in which the data are gathered at all the processes.
int MPI_Allgather(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype recvdatatype，MPI_Comm comm)
int MPI_Scatter(void *sendbuf, int sendcount, MPI_Datatype senddatatype, void *recvbuf, int recvcount, MPI_Datatype recvdatatype, int source, MPI_Comm comm)
* 可参考文件 MPI.md
什么是 MPI 编程模型
MPI - the Message Passing Interface
* 参考老师 PPT，加粗部分即为重点内容。
MPI 是一个跨语言（编程语言如 C, Fortran 等）的通讯协议，用于编写并行计算机。支持点对点和广播。MPI 是一个信息传递应用程序接口，包括协议和和语义说明，他们指明其如何在各种实现中发挥其特性。MPI 的目标是高性能，大规模性，和可移植性。MPI 在今天仍为高性能计算的主要模型。与 OpenMP 并行程序不同，MPI 是一种基于信息传递的并行编程技术。消息传递接口是一种编程接口标准，而不是一种具体的编程语言。简而言之，MPI 标准定义了一组具有可移植性的编程接口。
消息传递并行编程模型的主要原则
* CH-8 p6
- 支持消息传递并行编程模型的设备，运行的多个进程应有自己独立的地址空间。
- 限制
- 每个数据单元必须归属于某一片划分好的地址空间，因此，必须显式划分并分配（place）数据。
- 无论是只读操作还是读写操作，都需要两个进程进行配合：拥有数据的进程以及操作发起的进程。
- 消息传递程序常常是异步或者松弛同步（loosely synchronous）的。
- 松弛同步：任务之间的交互同步进行，此外各个任务异步进行。
- 绝大多数的消息传递程序是由
single program multiple data - SPMD（单程序多数据流） 模型写的。
MPI 中的几种 Send 和 Receive 操作，包括原理和应用场景。
* CH-8 p9
Send 和 Receive 操作可分为以下三大类：
Non-buffered blocking 无缓冲阻塞
为保证传输安全，需要实现类似于“握手”的操作才能开始发送数据，容易导致空转和死锁。
Buffered blocking 缓冲阻塞
为了减轻空转和死锁现象，引入缓冲区。
有通信硬件支持下：发送端不会中断接收方。
无通信硬件支持下：发送端中断接收方，将数据存入接收端缓冲区。
Non-blocking 非阻塞
非阻塞的协议是不安全的。
通常，非阻塞协议需要与状态检查操作（check-status operation）同步使用。
参见
MPI_Get_count(), MPI_Statustypedef struct MPI_Status { int MPI_SOURCE; int MPI_TAG; int MPI_ERROR; }; int MPI_Get_count(MPI_Status *status, MPI_Datatype datatype, int *count)若使用得当，非阻塞的原语能够将通信与有效计算重叠进行。（When used correctly, these primitives are capable of overlapping communication overheads with useful computations.）
总体比较：
MPI 中的关键编程接口
参见
MPI.md - $2 MPI基本函数
什么是通信子
参见
MPI.md - $4 MPI集群通信 - $4.0 组 & 通信子
MPI 中解决死锁的方式有哪些？
- 重排代码，避免死锁。
- 在发送时，添加接收缓冲区。
- 将自己（发送端）的地址空间作为发送缓冲区。
- 使用非阻塞的 send/receive 方法。
MPI 中的集群（群组）通信操作子有哪些？原理是什么？
MPI 定义了一系列扩展函数以实现集群通信操作，这些操作都是基于一个与通信子关联的群组定义的。通信子中的所有处理器必须调用这些操作。
参见
MPI.md - $4 MPI集群通信
如何利用 MPI 实现 Matrix-Vector 乘积
对算式 $Ab=c$，有：
串行算法
略
三种并行算法
Row-wise block striped
- 将$A$各行拆分，$b$不动，各个进程完成两个向量的內积得到$c_i$.
- 调用
MPI_Allgatherv(...)聚合计算结果。MPI_Allgatherv(...)参见MPI.md - $4 MPI集群通信 - $4.3 多对多通信
Column-wise block striped
将$A，b$各列拆分，各个进程按图示工作。
调用
MPI_Alltoall(...)传送计算结果。其中每个进程完成计算后得到上图中$c_{0j},c_{1j}，c_{2j}，c_{3j},c_{4j}$。最后分组加和。
MPI_Alltoall(...)参见MPI.md - $4 MPI集群通信 - $4.3 多对多通信
Checkerboard block
将$A$棋盘化分块，按照行划分同样对 b 进行分段。
需要注意，进程数 p 是否为完全平方数影响 b 分块的过程。
使用
MPI_Dims_create(...)以及MPI_Cart_create(...)新建拓扑关系通信子。
MPI_Dims_create(...)，MPI_Cart_create(...)参见MPI.md - $5 MPI 逻辑分划规约计算。
三种算法的性能比较
MPI 和 OpenMP 结合的优势是什么？
运行较只使用 MPI 快。
- 只使用 MPI 时，消息在m*k 个进程间传递；
- 联合编程时，消息在m 个含有 k 个线程的进程间传递，代价较低。
特别地，考虑不同处理器数量的情况：
2,4CPUs：MPI + OpenMP 较慢
MPI + OpenMP 是共享内存带宽（memory bandwidth）的，MPI-only 不是。
6,8CPUs：MPI + OpenMP 较快
更低的通信开销。
程序的更多部分可以并行实现。
只使用 MPI 时，不涉及消息传递的并行过程无法实现。
允许更多通信与有效计算的叠加（overlap）。
如何利用 MPI+OpenMP 实现高斯消元法
* CH - 9 p53
0 - 简介
高斯消元法（Gaussian Elimination ）
- 用于求解系数矩阵$A$是稠密(dense)矩阵的方程$Ax=b$
- 化简得到三角矩阵系统$Tx=c$，$T$为三角矩阵
- 回代求解$x$
稀疏矩阵系统（sparse system）
- 高斯消元法对稀疏系统的适应性不好。
- 高斯消元法使得稀疏矩阵新添很多非 0 元素
- 增加了存储需求
- 增加了操作次数
迭代方法（Iterative Methods）
- 存储需求较高斯消元法更小。
- 含有 0 元素的计算会被忽略，大大减少了计算量。
雅各比方法（Jacobi Method）
收敛性（Convergence）
- 一般只能达到较慢的收敛速度，很难实际应用。
1 - 新方案思想
- 对 MPI 进行概要分析（？Profile execution of MPI program）。
- 致力于在计算密集型的函数或代码段处加入 OpenMP 指令。
2 - 串行代码
find_steady_state()
无法并行执行最外层 for 循环的原因
for循环并不是规范形式（canonical form）- 包含
break语句- 包含 MPI 功能函数
- 迭代之间存在数据依赖。
并行化本段 for 循环
- 处理
diff的更新（upadte）与检测（test）
- 若考虑将
if语句置入临界区（critical section），会增加额外开销并且降低加速比。（Putting if statement in a critical section would increase overhead and lower speedup.）- 考虑引入私有变量
tdiff- 在进行
MPI_Allreduce()规约之前，检测tdiff代替之前检测diff的步骤。3 - 并行化代码
4 - 基准化测试
考虑以下环境：
系统：包含 4 个双核处理器节点的商业集群。
- C+MPI 在 1,2, … ,8 进程上运行
- C+MPI+OpenMP 在 1,2,3,4 进程上运行
- 每个进程包含 2 个线程
- 包含 2,4,6,8 线程
结果示意：
总结分析：
Hybrid C+MPI+OpenMP program uniformly faster than C+MPI program.
混合编程在速度上显著快于 MPI 编程。
Computation/communication ratio of hybrid program is superior.
混合编程的“计算通信比”更胜一筹。理解为单位通信次数/时间内有效计算量更大。
Number of mesh points per element communicated is twice as high per node for the hybrid program.
混合编程内每个通信元素的网格点数是程序节点数的两倍。
Lower communication overhead leads to 19% better speedup on 8 CPU.
混合编程在 8CPU 下通过减少通信开销实现了 19%的加速。
假设运算为 A*b=c，其中 A 为矩阵，b、c 为向量
Partitioning through domain decomposition
通过域分解划分
Primitive task associated with
原始任务关联
有时会出现每个进程的结果个数不一样，所以不能使用 MPI_gather（因为要求每个进程的传输个数一样），所以使用 MPI_Allgatherv。
Partitioning through domain decomposition
通过域分解进行划分
此时为 A 的第 i 列乘以 b[i]。
一般的做法为行列转置，即把结果部分 c[i]由不连续存储的列元素变成连续存储的行形式表示，再统计获得最终结果。图在 PPT 的 16 页。
Vector b distributed by blocks among processes in first column of grid
矢量 B 在网格第一列的进程之间按块分布
注意 PPT 中第 20 页和第 21 页的图。
MPI + OpenMP 可以执行的更快
Sparse Systems
稀疏系统
Iterative Methods
迭代法
Methodology
方法
But achieving high efficiency requires careful consideration of the mapping from computations to processors, data to memories, and data access patterns
CUDA: Compute Unified Device Architecture
CUDA：计算统一设备架构
Provide an inherently scalable environment for Data-Parallel programming across a wide range of processors (Nvidia only makes GPUs, however)
为跨多种处理器的数据并行编程提供内在可扩展的环境(不过，NVIDIA 只制造 GPU)。
Make SIMD hardware accessible to general-purpose programmers. Otherwise, large fractions of the available execution hardware are wasted!
使 SIMD 硬件对通用程序员可访问。否则，大部分可用的执行硬件都会被浪费掉！
PPT 上没找到很多与传统多线程设计的区别，但我觉得其实就很类似 SIMD 和 MIMD 的区别？（hhh）
For GPU programming, there is low overhead for thread creation, so we can create one thread per loop iteration
Between GPUs of the same generation, many programs achieve linear speedup on GPUs with more “Cores”; (线性加速比)
The Cuda Thread abstraction will provide programmability at the cost of additional hardware
我个人的理解就是运行在设备上的 SPMD 核函数。
一个 kernel 结构如下：Kernel<<<Dg, Db, Ns, S>>>(param1, param2, ...)
1024*1*1 | 256*2*2 | 1*1024*1 | 2*8*64 | 4*4*64等）自己补充：CUDA 的操作概括来说包含 5 个步骤：
其中关键是第 3 步，能否写出合适的 kernel，决定了能否正确解决问题和能否高效的解决问题。
Cuda 对线程做了合适的规划，引入了 grid 和 block 的概念，block 由线程组成，grid 由 block 组成，一般说 blocksize 指一个 block 放了多少 thread；gridsize 指一个 grid 放了多少个 block。
Parallelism in the Cuda Programming Model is expressed as a 4-level Hierarchy
Cuda 编程模型中的并行性被表示为一个 4 层的层次结构。
Very fine granularity: do not expect any single thread to do a substantial fraction of an expensive computation – At full occupancy, each Thread has 21 32‐bit registers – … 1,536 Threads share a 64 KB L1 Cache / shared mem – GPU has no operand bypassing networks: functional unit latencies must be hidden by multithreading or ILP (e.g. from loop unrolling)
Technically, warp size could change in future architectures – But many existing programs would break
Threads within a block synchronize via barrier-intrinsics and communicate via fast, on-chip shared memory
Thread blocks of a kernel call must be parallel sub-tasks
Multiple Devices managed via multiple CPU threads
Unless data will be shared between Threads in a block, it should reside in registers - On Fermi, the 128 KB Register file is twice as large, and accessible at higher bandwidth and lower latency
cuda 提供了原生的原子操作，例如
CUDA provides a set of instructions which execute atomically with respect to each other
Frequently must also use the volatile type qualifier
MapReduce
More simply, MapReduce is A parallel programming model and associated implementation
Some MapReduceTerminology
一些 MapReduce 终端（猜测翻译成专有名词更合适？）。
Motivation: Large Scale Data Processing
动机：大规模数据处理。
Process data using special map() and reduce() functions
使用特殊 map()和 reduce()函数处理数据。
map() produces one or more intermediate values along with an output key from the input
reduce() combines those intermediate values into one or more final values for that same output key
使用 python 实现的分词程序。
import sys
import time
import re
p = re.compile(r'\w+')
for line in sys.stdin:
ss = line.strip().split(' ')
for s in ss:
#time.sleep(1)
if len(p.findall(s))<1:
#print s
continue
s = p.findall(s)[0].lower()
if s.strip() != "":
print "%s\t%s" % (s, 1)
import sys
current_word = None
sum = 0
for line in sys.stdin:
word, val = line.strip().split('\t')
if current_word == None:
current_word = word
if current_word != word:
print "%s\t%s" % (current_word, sum)
current_word = word
sum = 0
sum += int(val)
print "%s\t%s" % (current_word, str(sum))
Master notices particular input key/values cause crashes in map(), and skips those values on re-execution
Optimizations
Causes a mini-reduce phase to occur before the real reduce phase, to save bandwidth
Handles load balancing
Outline stays the same, but map and reduce change to fit the problem
它扩展了广泛使用的 MapReduce 计算模型。高效的支撑更多计算模式，包括交互式查询和流处理。spark 的一个主要特点是能够在内存中进行计算，及时依赖磁盘进行复杂的运算，Spark 依然比 MapReduce 更加高效。
MapReduce is great at one-pass computation, but inefficient for multi-pass algorithms. No efficient primitives for data sharing
MapReduce 在单程计算方面很好，但对于多路算法效率较低。没有有效的数据共享原语。
In this example, we use a few transformations to build a dataset of (String, Int) pairs called counts and then save it to a file.
text_file = sc.textFile("hdfs://...")
counts = text_file.flatMap(lambda line: line.split(" ")) \
.map(lambda word: (word, 1)) \
.reduceByKey(lambda a, b: a + b)
counts.saveAsTextFile("hdfs://...")
从图中某顶点 v 出发： （1）访问顶点 v； （2）依次从 v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和 v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。(百度)
时间复杂度$\theta(b^k)$, 空间复杂度$\theta(k)$, b 为宽度, k 为深度
假设状态空间树中的平均分支因子（每个节点的子节点数（平均值））为 b，搜索一棵深度为 k 的树需要检索：
个结点。空间复杂度为 Θ(k)
- Send nodes near the bottom of the stack（发送堆栈底部附近的结点），适用于均匀搜索空间；分配成本低。
- Send nodes near the cutoff depth（发送截止深度附近的结点），使用强启发式（尝试分配搜索空间中可能包含解决方案的部分）可以获得更好的性能。
- Send half the nodes between the bottom and the cutoff depth（发送底部和截止深度之间的一半结点），适用于均匀不规则的搜索空间。
我们将 v（p）定义为每个处理器在收到至少一个工作请求之后的工作请求总数；假设任意点的最大工作量是 W；则工作请求总数为 O(V(p)logW)。
- ARR：V(p) = O(p²)在最坏情况下
- GRR：V(p) = p
- RP：
最坏情况下 V(p)是无穷的。 平均状况下 V(p) = O(plogp)
- ARR：W = O(p²logp)
- GRR：最坏情况下 W = O(p²logp)
- RP：W = O(plog²p)
- ARR 性能较差，因为它会发出大量的工作请求。
- GRR 调度由于计数器上的争用而性能较差，尽管它发出的请求数最少。
- RP 是一个理想的折衷办法。
- 由于处理器探索的搜索空间是在运行时动态确定的，实际工作可能会有很大的差异。
- 使用 P 处理器产生大于 P 的加速的执行被称为加速异常。使用 P 处理器的小于 P 的加速被称为减速异常。
- 加速异常也表现在最佳优先搜索算法中。
- 如果启发式函数是好的，那么并行的 best-first 搜索中所做的工作通常比串行搜索中所做的工作要多。
- 负载均衡主要有哪些方式？分别有什么特点？
- 静态、动态负载均衡适用的场景是什么？
- 如何选择任务的粒度？
理想情况下, 所有处理器在程序运行时同时计算, 并同时结束他们被分派的任务.
问题: 实现更好的负载均衡
静态分派与动态分派
在每个线程运行前, 每个线程被分派的任务规模已经被确定. 即预先分派每个线程执行的任务. 这可以在编译期间分派, 也可以在运行期间依据运行参数分派(比如数据大小, 线程数量).
任务的开销(执行时间)和任务的数量是可预测的
周期性地进行预测并再动态分派, 在相邻再分配的时间间隔内, 为静态分派
任务的开销在较近的未来是可预测的.
程序在运行时动态地分派任务.
任务的开销和数量是不可预测的
考虑用工作队列的方式实现动态分派. 一个共享的工作队列, 里面有一些待完成的任务.
worker thread 可以执行两种操作
我们来分析一下任务的粒度对这种动态负载均衡方式的影响
理想的粒度还取决于许多因素.
考虑下列任务
如果简单地进行分派, 可能造成负责不均衡
解决的办法
这样可以避免所有 workers 需要进行同时同步.
当 worker 线程队列为空时, 会从别的队列中偷(steal)任务
- Latency 和 Throughput 的定义
- 通信时间的计算方法
- 并行程序中通信产生的原因
- 什么是天然通信？什么是人为通信？举例
- 什么是运算密度？
- 人为通信包括哪些？
- 减少通信代价的方式有哪些？
减少通信代价方法
- Reduce overhead of communication to sender/receiver
- Send fewer messages, make messages larger (amortize overhead)
- Coalesce (合并)many small messages into large ones
- Reduce delay
- Application writer: restructure code to exploit locality
- HW implementor: improve communication architecture
- Reduce contention
- Replicate contended resources (e.g., local copies, fine-grained locks)
- Stagger access to contended resources
- Increase communication/computation overlap
- Application writer: use asynchronous communication (e.g., async messages)
- HW implementor: pipelining, multi-threading, pre-fetching, out-of-order exec
- Requires additional concurrency in application (more concurrency than number of execution units)
优化通信
- Inherent vs. artifactual communication
- Inherent communication is fundamental given how the problem is decomposed and how work is assigned
- Artifactual communication depends on machine implementation details (often as important to performance as inherent communication)
- Improving program performance
- Identify and exploit locality: communicate less (increase arithmetic intensity)
- Reduce overhead (fewer, large messages)
- Reduce contention
- Maximize overlap of communication and processing (hide latency so as to not incur cost)
阻塞型 send/recv 如何避免死锁
传输延迟(Latency): 一个操作完成需要的时间.
吞吐量(Throughput/Bandwidth): 操作执行时的速度
增加吞吐量的方法
加快传输速度
加大带宽
上一节的讨论让我们知道, 虽然不可用减少 latency, 但可以增加 pipline 程度来提高 throughput.
对于无 pipline 的通信而言, 开销如下
\[T(n)=T_0+\frac{n}{B}\]对于以下情景考虑 pipline 方式
通信时间=本地开销+传输开销+传播开销+异地开销
通信开销=通信时间-overlap 部分
运算密度: 运算数量/通信数量
并行算法中必须要的通信, 是算法的组成部分
information that fundamentally must be moved between processors to carry out the algorithm given the specified assignment (assumes unlimited capacity caches, minimum granularity transfers, etc.)
如何减少? 通过改进算法
all other communication (artifactual communication results from practical details of system implementation)
System might have rules of operation that result in unnecessary communication
- Cache 冲突包含哪些类型？
- 提高 Cache 局部性的方式有哪些？
考虑 row-major traversal 的访问方法
其中蓝色为在 Cache 中的部分, 所以我们需要 change grid traversal order
- 减少数据竞争的方式有哪些？
Contention occurs when many requests to a resource are made within a small window of time
One possible answer is to decompose work by cells: for each cell, independently compute particles within it (eliminates contention because no synchronization is required)
assign one particle to each CUDA thread. Thread computes cell containing particle, then atomically updates list.
Alleviate contention for single global lock by using per-cell locks
- 预先决定分配的工作线程，不一定在编译时确定(分配算法可能取决于运行时参数，如输入数据大小、线程数等)。（分配包括按块和按行）
Assignment of work to threads is pre-determined,Not necessarily determined at compile-time (assignment algorithm may depend on runtime parameters such as input data size, number of threads, etc.)- 简单，本质上是零运行时开销
simple, essentially zero runtime overhead (in this example: extra work to implement assignment is a little bit of indexing math)
- 工作成本短时间可以预测
Cost of work is predictable for near-term future- 应用程序定期对自身进行配置并重新调整分配
Application periodically profiles itself and re-adjusts assignment
- 程序在运行时动态的确定分配，以确保负载分布良好（任意的执行时间和执行点数是不可预测的）
Program determines assignment dynamically at runtime to ensure a well distributed load. (The execution time of tasks, or the total number of tasks, is unpredictable.)- 使用工作队列动态分配
Dynamic assignment using a work queue
- 当工作的成本(执行时间)和工作量是可预测的(这样程序员就可以提前完成一项很好的任务)
When the cost (execution time) of work and the amount of work is predictable- 当工作是可预测的，但不是所有的工作都有相同的成本
When work is predictable, but not all jobs have same cost (see example below)- 当关于执行时间的统计数据是已知的(例如，平均成本相同)
When statistics about execution time are known (e.g., same cost on average)
不知道工作的成本与资源
有用比处理器更多的任务(很多小任务可以通过动态分配好工作负载平衡)
Useful to have many more tasks* than processors (many small tasks enables good workload balance via dynamic assignment)
- 激发小粒度的任务：
Motivates small granularity tasks
但希望尽可能少的任务的开销最小化管理任务
But want as few tasks as possible to minimize overhead of managing the assignment- 激发大粒度任务
Motivates large granularity tasks
理想的粒度取决于许多因素(在这门课中共同的主题:必须知道你的工作量,和你的机器)
Ideal granularity depends on many factors (Common theme in this course: must know your workload, and your machine)
- cilk_spawn foo (args);语义:调用 foo，但与标准函数调用不同，调用者可以继续异步执行 foo。
- 注意，cilk_spawn 抽象没有指定如何或何时计划执行派生调用。只是它们可以与调用者并发运行(以及由调用者生成的所有其他调用)
- cilk_spawn foo(args); Semantics: invoke foo, but unlike standard function call, caller may continue executing asynchronously with execution of foo.
- notice that the cilk_spawn abstraction does not specify how or when spawned calls are scheduled to execute. only that they may be run concurrently with caller(and with all other calls spawned by caller)
- 语义:当当前函数生成的所有调用都已完成时返回。(与派生调用“同步”) 注意:在包含 cilk_spawn 的每个函数的末尾都有一个隐式 cilk_sync(含义:当一个 Cilk 函数返回时，与该函数相关的所有工作都完成了)
- cilk_sync 确实是调度上的一个约束。所有派生调用必须在 cilk_sync 返回之前完成。
- Semantics: returns when all calls spawned by current function have completed. (“sync up” with the spawned calls) Note: there is an implicit cilk_sync at the end of every function that contains a cilk_spawn (implication: when a Cilk function returns, all work associated with that function is complete)
- cilk_sync does serve as a constraint on scheduling. All spawned calls must complete before cilk_sync returns.
先运行延续
- 在执行任何迭代之前，调用方线程派生都可以用于所有迭代
- 如果没有窃取，执行顺序与删除 cilk_spawn 的程序非常不同。
- caller thread spawns work for all iterations before executing any of it
- If no stealing,execution order is very different than that of program with cilk_spawn removed.
- 调用方线程只创建一个要窃取的项(表示所有剩余迭代的延续)
- 如果没有发生串列，线程将从工作队列中不断弹出 continuation，并为新的 continuation(更新值为 i)排队
- 执行顺序与删除派生的程序相同。
- caller thread only creates one item to steal(continuation that represents all remaining iterations)
- If no straling occurs, thread continually pops continuation from work queue, enqueues new continuation(with updated value of i)
- Order of execution is the same as for program with spawn removed.
- 本地线程从“尾部”(底部)推送/弹出
- 远程线程从“头部”(顶部)窃取
- 存在高效的无锁 dequeue 实现
dequeue per worker
- Local thread pushes/pops from the “tail” (bottom)
- Remote threads steal from “head” (top)
- Efficient lock-free dequeue implementations exist
- Idle threads randomly choose a thread to attempt to steal from
- Stealing from top of dequeue…
- Reduces contention with local thread: local thread is not accessing same part of dequeue that stealing threads do! \
- Steals work at beginning of call tree: this is a “larger” piece of work, so the cost of performing a steal is amortized (分摊) over longer future computation
- Maximizes locality: (in conjunction with run-child-first policy) local thread works on local part of call tree
如果线程没有窃取任何工作，那么在同步点上就不做任何事
no stealing
If no work has been stolen by threads, then there’s nothing to do at the sync point
- 启动 fork 的线程必须预先形成同步
- 因此，它等待所有生成的工作完成。在本例中，线程 0 是引发 fork 的线程。
- Thread that initiates the fork must preform the sync
- Therefore it waits for all spawned work to be complete. In the case, thread 0 is the thread initating the fork.
- Cilk_spawn 的原理是什么？
- Cilk_sync 的原理是什么？
- Cilk_spawn 的调度方式有哪些？各自有什么特点？
- Cilk_spawn 的任务在不同线程之间 steal 的过程
- Cilk_sync 的几种实现方式
常见的并行编程范式有两种
Fork-join pattern: Natural way to express independent work in divide-and-conquer algorithms
Cilk 框架的几个重要函数
cilk_spawn foo(args): “fork” (create new logical thread of control)
Semantics: invoke foo, but unlike standard function call, caller may continue executing asynchronously with execution of foo.
cilk_sync: “join”
Semantics: returns when all calls spawned by current function have completed.
Note: there is an implicit cilk_sync at the end of every function that contains
注意
cilk_spawn只保证 callee 可能与 caller 和其他 callees 一起执行cilk_sync起到调度上的约束作用例子
并行化快速排序
The Cilk Plus runtime maintains pool of worker threads
cilk_spawn将程序划分为两部分
以下是几个实现的细节
cilk_spawn后会将原 work 划分为spawned child和continuation, 选取一个执行, 另一个放到work queue那么, 现在有个问题, 当一个线程cilk_spawn后, 它是先执行spawned child还是continuation
以这个代码为例
for (int i = 0; i < N; i++) {
cilk_spawn foo(i);
}
cilk_sync;
执行顺序为 0, 1, 2 …
执行顺序为 N-1, N-2, N-3 …
如果没有 stealing, 其他线程无事可做, sync 的实现为nop
stalling join: Thread that initialtes the fork must perform the sync
对于每个由cilk_spawn和cilk_sync界定的代码块, 创建一个descriptor, 来描述这个代码块任务的完成情况
所有线程如果无事可做, 都会试图去偷任务. nitiated spawn thread 不一定是在 sync 后继续执行 work 的 initiated spawn thread
通信时间 = 程序通信时间+占有时间+网络延迟\
Total communication time = overhead + occupancy + network delay\
- 处理器与其缓存之间的通信
- 处理器与存储器之间的通信。(内存在同一台机器上)
- 处理器和远程存储器之间的通信。(集群中另一个节点上的内存，通过发送网络消息访问)
天然通信：根据指定的分配(假设无限容量缓存、最小粒度传输等)，必须在处理器之间移动才能执行算法的信息
Inherent communication: information that fundamentally must be moved between processors to carry out the algorithm given the specified assignment (assumes unlimited capacity caches, minimum granularity transfers, etc.)
人为通信：所有其他通信(人为沟通源于系统实现的实际细节)
Artifactual communication: all other communication (artifactual communication results from practical details of system implementation)
System might have a minimum granularity of transfer (result: system must communicate more data than what is needed)
Program loads one 4-byte float value but entire 64-byte cache line must be transferred from memory (16x more communication than necessary)
System might have rules of operation that result in unnecessary communication: Program stores 16 consecutive 4-byte float values, but entire 64-byte cache line is first loaded from memory, and then subsequently stored to memory (2x overhead)
Poor placement of data in distributed memories (data doesn’t reside near processor that accesses it the most)
Finite replication capacity (same data communicated to processor multiple times because local storage (e.g., cache) is too small to retain it between accesses)
- 通过改变网格遍历顺序来改进时间局部性
- 通过融合循环改进时间局部性
- 通过共享数据提高算法强度
- Improving temporal locality by changing grid traversal order
- Improving temporal locality by fusing loops
- Improve arithmetic intensity by sharing data
- 分布式工作队列可以减少争用
- 在大型并行机器上创建粒子数据结构网格
- 粒子层次并行化
- 使用细粒度锁
- distributed work queues serve to reduce contention
- create grid of particles data structure on large parallel machine
- parallelize over particles
- use finer-granularity locks
- 发送更少的消息，使消息更大(摊销开销)
- 合并(合)并成大的许多小消息
- 应用程序编写器:重构代码以利用局部性
- HW 实现者:改进通信架构
- 复制竞争资源(例如，本地副本、细粒度锁)
- 错开对争用资源的访问
- 应用程序编写器:使用异步通信(例如，异步消息)
- HW 实现者:流水线，多线程，预取，无序执行
- 应用程序中需要额外的并发性(并发性多于执行单元的数量)
- Send fewer messages, make messages larger (amortize overhead)
- Coalesce （合并）many small messages into large ones
- Application writer: restructure code to exploit locality
- HW implementor: improve communication architecture
- Replicate contended resources (e.g., local copies, fine-grained locks)
- Stagger access to contended resources
- Application writer: use asynchronous communication (e.g., async messages)
- HW implementor: pipelining, multi-threading, pre-fetching, out-of-order exec
- Requires additional concurrency in application (more concurrency than number of execution units)
- 求 MST 的 Prim 算法是一种贪婪算法。
- 首先选择一个任意的顶点，将它包含到当前的 MST 中。
- 通过插入最接近其中一个的顶点来增长当前 MST 顶点已经在当前 MST 中。
- Prim’s algorithm for finding an MST is a greedy algorithm.
- Start by selecting an arbitrary vertex, include it into the current MST.
- Grow the current MST by inserting into it the vertex closest to one of the vertices already in current MST.
- 该算法在 n 个外部迭代中工作，很难同时执行这些迭代。
- 内循环相对容易并行化
- 假设 p 为进程数，n 为顶点数。
- 邻接矩阵采用一维分块的方式进行分块，距离向量 d 进行相应的分块。
- 在每个步骤中，处理器选择本地最近的节点，然后进行全局约简以选择全局最近的节点。
- 这个节点被插入到 MST 中，并选择广播给所有处理器。每个处理器本地更新其 d 向量的一部分。
- The algorithm works in n outer iterations - it is hard to execute these iterations concurrently.
- The inner loop is relatively easy to parallelize
- Let p be the number of processes, and let n be the number of vertices.
- The adjacency matrix is partitioned in a 1-D block fashion, with distance vector d partitioned accordingly.
- In each step, a processor selects the locally closest node, followed by a global reduction to select globally closest node.
- This node is inserted into MST, and the choice broadcast to all processors. Each processor updates its part of the d vector locally.
- 跨进程划分图形，并在每个处理器上运行独立的连接组件算法。在这一点，我们有 p 个森林。
- 在第二步中，跨越森林两两合并，直到只剩下一个跨越森林。
- partition the graph across processes and run independent connected component algorithms on each processor. At this point, we have p spanning forests.
- In the second step, spanning forests are meged pairwise until only one spanning forest remains.
构造准则
算法流程
注意
实现
设置辅组数组 closedge[]
流程
lowcost[i] = min{ lowcost[i], Edge[v][i] }， 即用生成树顶点集合外各顶点 i 到刚加入该集 合的新顶点 v 的距离 Edge[v][i] 与原来它们到 生成树顶点集合中顶点的最短距离 lowcost[i] 做比较, 取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离并行算法流程
时间复杂度
并行算法每次迭代的时间复杂度为$O(n/p+logp)$
总时间复杂度为$O(n^2/p+nlogp)$
最短路径问题: 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
问题解法
本质上是贪心算法.
算法流程
S ← { v 0 };
dist[j] ← Edge[0][j], j = 1, 2, ..., n-1;dist[k] ← min { dist[i] }, i in V- S;
S ← S U { k };dist[i] ← min{ dist[i], dist[k] + Edge[k][i] },
对于每一个 i in V- S ;S = V, 则算法结束,否则转 2。和 Prim 的优化非常近似, 分析和完全考虑 Prim 的并行版本
使用的话, 复杂度为$O(n^3)$, 并行化有两种方法
可以使用 DFS 寻找图的连通分量
并行化可以使图在不同的处理器上运行不同生成树 DFS, 最后再合并.