并行计算

rel## Threads / Process

• Process，进程
  • 共享变量和存储空间
  • 私有栈空间和指令指针
  • Eg. MPI
• Thread，线程
  • 私有变量、存储空间、栈空间和指令指针
  • Eg. OpenMP

Threads

• 程序员将程序分解为可并行执行和访问共享数据的单个指令序列（线程）。

单核多线程

• 实现
  • 时间片轮转等 OS 调度机制来模拟并发执行
  • 硬件支持的同一核心内的并行线程处理（Hyper-Threading/SMT）

硬件线程/软件线程

• 硬件线程：CPU 核心通过硬件支持的并发执行单位
• 软件线程：由操作系统或运行时环境（如 OpenMP、Pthreads）创建和管理的执行单元

Fork-join

• Spawned threads may recursively create further threads.
  • Slave threads join with the thread that spawned them.
  • Can also create detached threads, that don’t do a join when they terminate.

• Single thread: Execute statements in program order until blocked or end of time slice.
• Multi-threaded: Instructions of different threads are interleaved in arbitrary order.
  • Race Condition: Eg. Using the same shared variable with load and store.

线程安全

• A routine is thread safe if it can be called from multiple threads simultaneously and always produces correct results.
  • Eg. Standard I/O (POSIX 标准，glibc 实现中会加 Mutex 锁)
• Routines that access shared data may require special care to be made thread safe.
• If a routine is not thread safe, it must be executed by only one thread at a time in a “critical section”.

临界区域

• Critical sections / MUTual EXclusion
• 一次只运行一个代码块
• Multiple changes can be made to data without interruption, so that data transitions from safe state to safe state
• Also appears in operating systems and programming languages, e.g. Java’s synchronized statement..

锁

• （阻塞式）锁和死锁：locks
• 非阻塞式锁（类似 try_acquire_lock），

Thread-Level Parallelism

Parallel programming language / library

Compiler directives (e.g. OpenMP)

• 程序员在顺序程序中插入编译器指令，指定并行性并指示共享数据，编译器将其转换为线程。
• 仍然使用线程，但由系统管理线程。
• 易于编程（虽然失去了一些灵活性）。对编译器的要求较低
• 最受欢迎的选项。