《并行计算:模型与算法》研读兴趣
《并行计算:模型与算法》研读兴趣
概念:并发、并行与分布式
并发:多个线程在同一时间段内同时执行。更多地考虑控制问题,包括同步和互斥等经典问题。
并行:多个线程在同一时刻同时执行。主要面向具体计算问题。
分布式:多个进程在多个通过网络互联的处理器上同时执行。
回顾算法复杂度的概念
复杂度表示所用到的符号有:
$f(n)=\Theta(g(n))$: 存在常数$c_1 \ge 0$,$c_2 \ge 0$,以及正整数$n_0$,对所有$n \ge n_0$有$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$。
$f(n)=O(g(n))$: 存在常数$c_1 \ge 0$,以及正整数$n_0$,对所有$n \ge n_0$有$0 \le f(n) \le c_1 g(n)$。
$f(n)=\Omega(g(n))$: 存在常数$c_1 \ge 0$,以及正整数$n_0$,对所有$n \ge n_0$有$0 \le c_1 g(n) \le f(n)$。
$f(n)=o(g(n))$: 对任意$c_1 \ge 0$,存在正整数$n_0$,对所有$n \ge n_0$有$0 \le f(n) \le c_1 g(n)$。
针对并行计算,具有研究价值的算法的简要描述
最大值。输入为一个数组$A[n]={a_1,\dots,a_n}$,输出该数组中最大值。
矩阵转置。输入为一个按行存储的矩阵$A[n][n]={ a_{11},\dots,a_{1n};a_{21},\dots,a_{2n};\dots;a_{n1},\dots,a_{nn} }$,输出为矩阵的转置$A’[n][n]={ a_{11},\dots,a_{n1};a_{12},\dots,a_{n2};\dots;a_{1n},\dots,a_{nn} }$。
$$A’[n][n]={ a_{11},\dots,a_{n1};a_{12},\dots,a_{n2};\dots;a_{1n},\dots,a_{nn} }$$
{$A’[n][n]={ a_{11},\dots,a_{n1};a_{12},\dots,a_{n2};\dots;a_{1n},\dots,a_{nn} }$}