5、并行计算中的理论考量与机器实现

并行计算中的理论考量与机器实现

1. 理论考量 - 复杂度与数据依赖

1.1 依赖类型概述

在并行计算中，存在多种依赖类型，主要包括竞争（Contention）、归纳变量（Induction Variable）、前向依赖（Forward Dependency）、后向依赖（Backward or Recursion Dependency）和运行时中断（Run - Time Break）。变量“id”对于每个进程是唯一的，其取值范围是从 0 到进程数减 1，即 0, 1, …, nprocs - 1。

1.2 竞争（Contention）

竞争指的是在同一个循环中，一个变量既被读取又被写入。只有当对该变量的访问实现同步时，才能得到正确的结果。以下是一个示例代码：

/* access to the variable sum must be synchronized */ sum ↑ 0; loop i = 1...n sum ↑ sum + ai; end loop

假设这个循环由两个进程执行，且 n = 2，我们期望循环结束时 sum = a1 + a2。但两个进程可能在 sum 值为 0 时同时访问它，各自加上向量 a 的分量，最终结果将取决于哪个进程最后写入，可能是 a1 或者 a2。

1.3 归纳变量（Induction Variable）

归纳变量是根据自身定义的变量，例如下面代码中的 i：