Parallel 并行计算相关知识

Question

并行计算（Parallel Computing）

并行计算（平行计算）是相对于串行计算来说的。

它是一种一次可执行多个指令的算法，目的是提高计算速度，及通过扩大问题求解规模，解决大型而复杂的计算问题。

所谓并行计算可分为时间上的并行（流水线技术）和空间上的并行（多个处理器并发的执行计算）。

基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。

• 用于多核处理器
• 缓存算法

并行算法（parallel algorithms）

概念

• 串行算法（serial algorithms）一般只有一种模型，即为随机存取机器模型（random access machine model）
• 并行算法及并行空间，有许多其他模型。如：动态多线程模型（dynamic multithreading），适用于多核机器中，为内存共享的编程而设计，不适用于分布式编程
• 衍生（spawn）：衍生的代码可以跟着父程序同时执行
• 同步（sync）：等待所有子程序完成，才执行这条指令
• 调度:把动态的、不断延伸的程序，映射到可用的处理器上
• 多线程计算，并行指令流，它其实是个有向无环图（DAG）

并行时间

设：Tp：任意程序运算在 p 个处理器上的运行时间

T1；功（work），串行运行时间

T∞：关键路径长度，DAG 中最长路径

• Tp ≥ T1/p
• Tp ≥ T∞

T1/Tp = Θ(p) —— 线性加速

T1/Tp ＞ Θ(p) —— 超级线性加速 （对于这个模型不可能，其他有可能通过类似缓存的机制实现）

P^ = T1/Tp —— 并行度，是能达到的最大速度，用功除以最短路径长度，是关键路径上可以并行完成的平均分量的功

调度算法

目的

调度的目的是：将计分配到 p 个处理器上，通常在实时操作系统上

贪心调度

在每一步做地尽可能多

1. 第一种：完整步骤：p 个线程则用 p 个处理器
2. 第二种：不完整步骤：多于 p 个线程运行 p 个线程；少于 p 个线程就全部线程运行

一个贪婪算法执行任意计算 G，若功为 T1，关键路径为 T∞，p 个处理器

Tp ≤ T1/p + T∞

• T1/p：完整步骤
• T∞：不完整步骤

贪心算法是线性加速度：P^ = T1/T∞

Cilk

Cilk —— 英特尔 Cilk 语言，多用于并行编程的语言

cilk int fib(int n) {
	if (n < 2) {
    	return n;
	}
	else {
    	int x, y;
    
    	x = spawn fib(n - 1);
    	y = spawn fib(n - 2);
    
    	sync;
    
    	return x + y;
	}
}