- 并行计算的意义
- 解决计算挑战的必经之路
- 现在并行计算很成熟
- 分布式集群
- 多核
- 开发环境
- 并行计算的三个方面
- 并行计算机体系结构
- 并行编程
- 并行算法
- 并发和并行
- 并发（Concurrency）：两个或多个线程在同时进行
- 并行（Parallelism）：两个或多个线程在同事执行
- 加速比
- 加速比 = 串行算法执行时间 / 并行算法执行时间
- 描述对程序并行化之后获得的性能收益
- Amdahl 定律 - 固定问题规模
- 加速比 = 1 / (S + (1 - S) / n)
- S：程序中串行部分的比例
- n：机器规模或处理器核的数目
- Gustafson 定律 - 固定时间
- 扩展加速比 = ( 1 - S ) * n + S
- Flynn 分类法
- 根据指令和数据流如何执行分类
- 分为四种
- SISD (Single Instruction, Single Data stream)
- 普通 PC 和工作站
- 受限于内部信息传输速度
- SIMD (Single Instruction, Multiple Data Streams)
- CRAY
- Intel MMX
- MISD (Multiple Instructions, Single Data Stream)
- 理论模型
- 或者用于容错性
- 流水线
- MIMD (Multiple Instructions, Multiple Data Streams)
- 理想的并行机模型
- 异步
- 分类
- Shared Memory
- 限制：可靠性和可扩展性，内存组件故障将导致整个系统故障
- Distributed Memory
- 可擴展性
- IPC 通訊
- SPMD（Single Program, Multiple Data）
- 同一程序对于不同数据给不同处理器执行
- MPMD
- Shared Memory
- SISD (Single Instruction, Single Data stream)
- 共享存储器结构
- 无共享体系
- 共享磁盘体系
- 共享存储体
- 并行计算机模型
- 定义：通过语义属性和性能属性描述
- 操作和开销
- 三种操作
- 计算操作
- 并行操作：管理线程 / 进程，例如创建终结 / 上下文切换
- 进程间同步操作
- 四种开销
- 并行开销：进程管理引起
- 通信开销：处理器交换信息
- 同步开销：执行同步操作
- 负载不平衡开销：部分处理器空闲然而部分繁忙
- 三种操作
- 不可并行：Affman 函数 / 工作流
- PRAM 模型
- Parallel Random Access Machine
- n 个处理器，1 个共享空间，1 个公共时钟
- 唯一的开销是负载不平衡开销
- 应用
- 串行：2N - 1，N 次乘，N - 1 次加
- 并行：[2N - 1 - (n - 1)] / n + logn
- N>>n，加速比为 n
- 优点：简单
- 缺点：零通信开销不可能
- APRAM 模型（不考）
- 同步路障
- 各自的时钟，但是可以加入同步指令
- BSP 模型
- 由 n 个处理器-存储器对组成
- 分布式 MIMD
- 内存访问模型
- 多级存储体系结构
- CPU
- 寄存器
- Cache：直接映射 / n 路组关联映射 / 全关联映射
- 局部存储
- 远程存储
- 并行计算机访问模型
- UMA（Uniform Memory Access）
- 物理存储器被所有节点共享
- 所有节点访问任意存储单元的时间相同
- 发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等
- 各节点的 CPU 可带有局部私有高速缓存
- 外围 I/O 设备也可以共享，且每个节点有平等的访问权利
- NUMA（Non-Uniform Memory Access）
- 物理存储器被所有节点共享，任意节点可以直接访问任意内存模块
- 节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的 3 倍以上
- 发生访存竞争时，仲裁策略对节点可能是不等价的
- 各节点的 CPU 可带有局部私有高速缓存
- 外围 I/O 设备也可以共享，但对各节点是不等价的
- COMA（不考）
- NORMA（不考）
- CC-NUMA（不考）
- UMA（Uniform Memory Access）
- 串行一致性：写直达，回写
- 监听一致性：写无效，写更新
- 多级存储体系结构
- 典型并行计算系统
- SMP（对称存储多处理器）
- UMA
- 结构对称
- 存储器和 I/O 负载大
- 扩展性差
- PVP（并行向量处理机）
- MPP（大规模并行处理）
- Cluster（集群）
- 各个节点都是完整的计算机
- 各个节点都有操作系统
- SMP（对称存储多处理器）
- 并行编程：算法构造并行程序的活动
- 三种并行编程模型
- 共享存储器编程
- 消息传递编程
- 数据并行编程
-
显式并行和隐式并行
- 代码中使用语言构造的显式说明
- 编译器的优化
-
三种显式编程模型特点
特点 数据并行 消息传递 共享存储 控制流 单 多 多 同步 松散同步 异步 异步 地址空间 单 多 单 交互 隐式 显式 显式 数据分配 隐式或半显式 显式 隐式或半显式 可移植性 SMP/DSM/MPP 基本主流并行计算机 SMP/DSM 存储 半隐式 显式 隐式 OpenMP 是共享存储
- 分解方式
- 任务分解
- 数据分解
- 数据流分解
- 任务分解
- 打开文档后可以立刻输入
- 后台在加载
- 设计模式
- 任务并行：任务分解/数据分解
- 分治：任务分解/数据分解
- 几何分解：数据分解
- 流水线：数据流分解
-
进程和线程
- 所谓线程就是操作系统中能够进行运算调度的最小单位
- 所谓进程就是一个或多个线程组成，并且需要系统资源的一个地址空间
-
线程 API 的实现层次
- 操作系统层(如Win32 API)
- 库或运行时环境(MFC, .net框架)
- 专门的多线程库(pthread)
-
创建线程
// Basic CreateThread(); ExitThread(); // Widely Used _beginthreadex(); _endthreadex(); // For MFC AfxBeginThread(); AfxEndThread(); // paras _beginthreadex(security, stack_size, start_address, arglist, initflag, threadID); _endthreadex(return_val);
-
线程/进程号
GetCurrentProcess(); GetCurrentThread(); GetCurrentProcessId(); GetCurrentThreadId();
-
管理线程
SuspendThread(); ResumeThread(); TerminateThread(); // paras (thread, exit_code)
-
互锁函数
InterlockedIncrement(); InterlockedDecrement(); InterlockedExchange(); InterlockedExchangePointer(); InterlockedExchangeAdd(); InterlockedCompareExchange(); // paras InterlockedExchange(&pointer, TRUE); // return pointer old value and pointer = TRUE
-
临界区
void InitializeCriticalSection(); void EnterCriticalSection(); void LeaveCriticalSection(); void DeleteCriticalSection(); // paras LPCRITICAL_SECTION // type CRITICAL_SECTION address
注意 __finally 执行 Leave
-
内核对象同步
WaitForSingleObject(); // paras (thread, milliseconds) // return value WAIT_OBJECT_0 WAIT_TIMEOUT WAIT_FAILED
WaitForMutlipleObjects(); // paras (count, objects, fWaitAll, milliseconds) // fWaitAll // TRUE: 所有对象 // FALSE: 一个对象 // return value WAIT_OBJECT_0 WAIT_OBJECT_0 + 1 ... WAIT_OBJECT_0 + dwCount - 1 WAIT_TIMEOUT WAIT_FAILED
-
事件
CreateEvent(security, reset, init_state, name); SetEvent(hEvent); ResetEvent(hEvent);
-
信号量对象/互斥量对象
CreateSemaphore(); ReleaseSemaphore(); CreateMutex(); ReleaseMutex();
-
线程池
QueueUserWorkItem(); SetThreadPriority(HANDLE hPriority, int nPriority); // 进程优先级 + 线程相对优先级 SetThreadAffinityMask(); SetProcessAffinityMask(); GetSystemInfo();
-
线程局部存储（TLS，Thread Local Storage）
- 用于存储线程局部数据
- 线程之间相互独立
TlsAlloc(void); // 返回一个 TLS 索引 TlsSetValue(index, value); TlsGetValue(index); TlsFree(index);
-
The entry of C programs
- main function
-
fork
- 返回值 0：子进程
-
终止一个进程
- 从 main 中返回
- 调用 exit
- 调用 _exit
- 最后一个线程结束
- 调用 abort
- 被信号中断
- 最后一个线程取消
-
exit & _exit
- _exit 是系统调用，立刻停止
- exit 是库函数
- exit handler：
atexit(function pointer);
-
wait & waitpid
pid_t wait(int *status); pid_t waitpid(pid_t pid, int *status, int options); // paras pid == -1; // 同 wait pid > 0; // 特定的子进程 pid == 0; // 任何一个子进程 pid < 0; // 组号为 n 的有个结束
-
signal
signal(signum, handler);kill(pid, signal); raise(signal); // return value 0 // success 1 // failure
-
alarm & pause
alarm(seconds); // 超时 return 0 pause(seconds); // 等待 return -1
-
signal mechanism
- signal set
- signal mask
- signal pending
-
POSIX thread
pthread_create(thread, attr, start_index, args); pthread_exit(ret_val); pthread_join(); pthread_detach();
// mutex pthread_mutex_init(mutex, attr); pthread_mutex_lock(mutex); pthread_mutex_unlock(mutex); pthread_mutex_destroy(mutex); pthread_mutex_trylock(mutex);
// TLS pthread_key_create(key, void); pthread_key_delete(key); pthread_getspecific(key); pthread_setspecific(key, value);
-
Code Structure
#include <omp.h> #pragma omp parallel
-
Programming Model
-
主线程 Master Thread
omp_set_num_threads(4); omp_get_thread_num(); // 1 #pragma opm parallel { omp_get_thread_num(); // 4 }
#pragma opm parallel num_threads(4) { omp_get_thread_num(); // 4 }
-
-
同步
-
critical 临界区
- 只有一个线程能进入
-
atomic 原子
- 原子操作
-
barrier
#pragma omp barrier #pragma omp master #pragma omp single
-
ordered：顺序执行
-
-
for
#pragma omp parallel { #pragma omp for for (i = 0; i < N; i++) { // do sth } // i is private(i) for each thread }
#pragma omp paraller for for (i = 0; i < N; i++) { // do sth }
-
Reduction
reduction (operation:list)#pragma omp parallel for reduction(+:avg) for (i = 0; i < N; i++) { avg += A[i]; }
-
Lock
omp_init_lock(); omp_set_lock(); omp_unset_lock(); omp_test_lock(); omp_destroy_lock();
-
Runtime
omp_set_num_threads(); omp_get_num_threads(); omp_get_thread_num(); omp_get_max_threads(); omp_in_parallel(); omp_num_procs(); omp_set_dynamic(0); omp_get_dynamic();
-
Data Sharing
- shared
- private
- 对于每个子进程新建一个副本
- 不初始化
- 在 Region 外 OpenMP 2.5 是未定义
- firstprivate
- 会被初始化
- 其余同 private
- default(private|shared|none)
-
OpenMP 3.0 Tasks
#pragma omp task // 例如遍历链表 #pragma omp taskwait // 例如遍历树
#pragma omp parallel { #pragma omp for private(p) for (int i = 0; i < numlists; i++) { p = listheads[i]; while(p) { #pragma omp task process(p); p = next(p); } } }
-
flush
- barriers
- entry
- exit
- lock
- atomic entry
-
OpenMP 3.0
#pragma omp task untied