并行计算概述

并行计算基本概念

并行化方法

域分解

首先确定数据如何划分到各个处理器，然后确定每个处理器所需要做的事情。

任务分解

首先将任务划分到各个处理器，然后确定各个处理器需要处理的数据。

流水线

将一个任务拆分成多个步骤，通过不同步骤在时间上的重叠达到“并行”的效果。

并行计算硬件环境

PRAM模型

PRAM全称为Parallel Random Access Machine，它具备以下特点：

1. 每个处理器可同时从共享的内存中读取数据到自己的寄存器
2. 每个处理器执行计算过程，数据存储在本地寄存器
3. 每个处理器可同时将数据写入到共享的内存（存在潜在冲突）

PRAM模型可以衍生出以下模型：

模型	特点
EREW	任意两个处理器不能并发读，也不能并发写
CREW	可以并发读，但不能并发写
CRCW	可以并发读，也可以并发写

根据PRAM模型，可以对前缀求和 作出并行算法设计：

处理器

SIMD体系

SIMD是一条指令同时操作多个数据，适合数据级并行的计算机体系结构。

Flynn分类法（Flynn’s Taxonomy）是计算机体系结构领域最经典的分类方法之一。它根据指令流（Instruction Stream）——机器执行的指令序列，和数据流（Data Stream）——由指令流调用的数据序列两个维度的"单"（Single）或"多"（Multiple）组合，将计算机体系结构分为四类：

类型	全称	指令流	数据流	典型代表	特征
SISD	Single Instruction Single Data	单	单	早期单核CPU（如Intel 8086）、传统冯·诺依曼架构	顺序执行，一次处理一个任务的一> 份数据
SIMD	Single Instruction Multiple Data	单	多	GPU、向量处理器、Intel SSE/AVX指令集	一条指令同时操作多个数据，适合数据级并行
MISD	Multiple Instruction Single Data	多	单	极少见，主要用于容错系统（如航天器冗余控制）	多个指令同时处理同一数据，理论意义大于实际
MIMD	Multiple Instruction Multiple Data	多	多	多核CPU、分布式计算集群、高性能服务器	多个独立指令流处理多个数据流，实现任务级并行

多核处理器

进入21世纪，曾预言“CPU主频18个月翻一番”的摩尔定律不再适用于当下处理器的发展方向。

限制单核性能主要有以下几个方面：

1. 功耗墙：CPU越小，单位面积产生的热量越多，散热越困难。
2. 存储墙：CPU缓存占据了70%以上的芯片面积，限制了性能的进一步提升。

多核处理器的特点：

1. 多个复杂度适中，相对低功耗的处理核心并行工作。
2. CPU时钟频率基本不变、

GPU

GPU将更多元件用于数据处理，而非控制和存储。

可以将GPU视作超大规模并行协处理器和SPMD（单程序多数据）模式，实现了数据并行。

互连网络

静态互连网络：处理单元之间有固定连接的一类网络，在程序执行期间这种点到点的链接保持不变：

动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态。包括总线、交叉开关等

内存访问模式

并行计算系统的体系结构

多线程并行程序设计

多线程基本概念

线程（Thread）是进程上下文（contex）中执行的代码序列，也称作轻量级进程。

在支持多线程的系统中，进程是资源分配的实体，线程是被调度执行的基本单元。

在计算机中，系统通过线程池管理线程。一个线程池可维护多个线程，等待调度器分配可并发执行的任务。避免了在短处理时间任务时创建与销毁线程的代价。

共享存储访问

计算机采用层次结构存储系统。

竞态条件与临界区

但是这样会出现竞态条件（Race Conditions）：当两个或多个线程试图在同一时刻访问共享内存或读写某些共享数据时，寄存器的值可能无法及时更新，导致最后的结果取决于线程的执行顺序。

为了解决这一困境，提出了临界区的概念：包含访问共享数据的代码。因此，在临界区内，任意时刻至多只能有一个线程在执行相关代码。

互斥锁

互斥锁（mutex）是实现线程同步的一种方法。线程对共享资源访问之前必须先获得锁，否则线程将保持等待状态，直到该锁可用。

实例分析

假设现有一段长文本，要求统计其中3的个数

普通的串行代码应为：

 1int *array;
 2int length;
 3int count;
 4
 5int countThree() {
 6    int i;
 7    count = 0;
 8    for (i=0; i<length; i++) {
 9        if (array[i] == 3) {
10            count++;
11        }
12    }
13    return count;
14}

运用域分解并行化方法，将其划分为若干个子数据段：

 1int t;
 2int *array;
 3int length;
 4int count;
 5
 6int countThree() {
 7    int i;
 8    count = 0;
 9    // 创建线程
10    for (i=0; i<t; i++) {
11        thread_create(countThree_thread, i);
12    }
13    return count;
14}
15
16void countThree_thread(int id) {
17    int length_per_thread = length / t;
18    int start = id*length_per_thread;
19
20    for (i = start; i<start+length_per_thread; i++) {
21        if (array[i] == 3) {
22            // 加互斥锁
23            mutex_lock(m);
24            count ++;
25            // 解锁
26            mutex_unlock(m);
27        }
28    }
29}

但是，此并行算法的性能远不及串行算法：

这是因为加锁会消耗时间，同时所有线程两两互斥可看作串行逻辑，并没有变化。

改进方法：加锁过程应当放在循环计数外。当每个线程分别计数完成后，再将各个数目相加得到总数目。

 1...
 2int private_count[MaxThreads];
 3mutex m;
 4
 5void countThree_thread(int id) {
 6    int length_per_thread = length / t;
 7    int start = id*length_per_thread;
 8
 9    for (i = start; i<start+length_per_thread; i++) {
10        if (array[i] == 3) {
11            private_count[id]++;
12        }
13    }
14    // 汇总时必须加锁，防止出现竞争
15    mutex_lock(m);
16    count += private_count[id];
17    mutex_unlock(m);
18}

修改后并行效率大幅提升，但仍与串行有差距。这是因为计算机系统的cache一致性与伪共享，虽然不同线程的private_count形式上互不干扰，但在缓存中可能处于一个缓存块中，在更新数据时会发生阻塞。

一种解决办法是强行将计数器的占用加大，使它们分别位于不同的缓存块中。

PThread多线段

主要操作函数：

Java多线程

创建方法：

1. 通过Thread类的子类实现多线程。
2. 定义一个实现Runnable接口的类实现多线程。