《并行计算：模型与算法》研读兴趣

《并行计算：模型与算法》研读兴趣

• 概念：并发、并行与分布式

  并发：多个线程在同一时间段内同时执行。更多地考虑控制问题，包括同步和互斥等经典问题。

  并行：多个线程在同一时刻同时执行。主要面向具体计算问题。

  分布式：多个进程在多个通过网络互联的处理器上同时执行。

• 回顾算法复杂度的概念

  复杂度表示所用到的符号有：

  • $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} }$}