《并行计算：模型与算法》研读兴趣
《并行计算：模型与算法》研读兴趣
概念：并发、并行与分布式
并发：多个线程在同一时间段内同时执行。更多地考虑控制问题，包括同步和互斥等经典问题。
并行：多个线程在同一时刻同时执行。主要面向具体计算问题。
分布式：多个进程在多个通过网络互联的处理器上同时执行。
回顾算法复杂度的概念
复杂度表示所用到的符号有：
$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} }$}