并行计算
阐述
并行和并发 的区别
并发系统：支持两个或者多个动作的同时存在，每个动作是可以被中断的，从而可以在它们之间切换。
并行系统：支持两个或以上动作的同时执行
绿色线程：并发但不并行的线程
- 阻塞和非阻塞：线程在等待其他任务完成前能否做别的工作
- 同步和异步：操作是程序主动运行还是由某个事件驱动运行，例如按键或者网络信号
I/O 操作总是能触发高优先级的上下文切换，因为它们需要即时的反馈。
低级别并行（SIMD）
SIMD (single instruction, multiple data) 是指处理器针对特定结构的数据可以同时执行几个命令。它对应着 CPU 中具有的特殊指令（SSE、AVX 等等）。
多线程并行
如果可以将任务分解成几个不同的任务，则可以交由不同的线程同时执行，这就是多线程。通常需要分析数据之间的依赖关系图，然后来相应地分组。每个线程只需要面对一个 vCPU，而由运行时（动态语言，绿色线程）或者操作系统（静态语言，操作系统线程）来调度。
这也称为「共享内存计算」，因为所有的线程都是共享堆和其他数据的。注意，不同线程可能会产生数据冲突。
但是，构造一个新的线程是需要时间的（大约 50 ~ 100 ns），而且不能使用栈来存储数据。所以，每个线程所执行的内容要足够多（大约 1 μs）。
GPU 计算（数据并行，SPMD）
SPMD (single program, multiple data) 是指求解多个不同的问题，每个不同的问题由不同的数据描述。GPU 是一种有很多不同的核（因此能使用很多线程）的设备，它通常具有共享内存，并且这个内存和 CPU 的内存是不互通的，需要消息传递。
GPU 计算通常需要 SPMD 内核编译器，比如 CUDA。CUDA 能将类似于 C++ 的语言编译为 .ptx 内核，然后由很多个核同时执行这个内核函数。
function gpu_add2!(y, x)
index = threadIdx().x # this example only requires linear indexing, so just use `x`
stride = blockDim().x
for i = index:stride:length(y)
@inbounds y[i] += x[i]
end
return nothing
end
一次向 GPU 的内存传输通常需要 20 ~ 50 μs，所以一个操作通常最好需要 1 ms。
多进程并行（分布式计算）
多个进程之间并不共享内存，所以它允许不同的进程不在同一个硬件上。它们之间的共享数据需要通过消息传递（message passing）来实现。
- 主进程/工作进程模型（显式内存管理）
- 任务模型（隐式内存管理）
- 数组并行
- Map-Reduce 模型
- MPI（SPMD）
多进程并行也只适用于 1 ms 以上的任务。
总结
- Map-reduce 类
- 数组类
- 循环类
- 任务类
- SPMD 类
实例
并发实例：主事件循环
基本上每个带有运行时的语言（如 Julia、JavaScript 等）都带有自己的一套任务处理机制。程序具有一个主进程，主进程执行一个「主事件循环」来执行不同的任务，当任务执行到一个 yield point 的时候，主进程会停下来看看是否有别的任务可以切换过去的，例如垃圾收集和输入输出。
-
在 JavaScript 和 Python 中，几乎每个语句都有 yield point，导致效率比较低
-
在 Julia 中，密集运算的部分不会插入 yield point，只在分配内存、I/O 的时候插入
-
异步非阻塞：I/O
-
异步阻塞：原子类型
-
同步非阻塞：服务器
-
同步阻塞：常规运算
不同语言的实现：