并行计算笔记

并行计算与并行应用的笔记。

并行计算（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语言，多用于并行编程的语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
    }
}