算法导论第三版新增27章中文版(20)

计算机科学与技术

i=1 ，2 ， ,n 。我们可以通过并行地计算y 的所有项来进行矩阵- 向量的乘法操作，如下：

MAT-VEC(A,x) 1 n = A.rows

2 令 y 为一个新的长度为 n 的向量

3 parallel for i = 1 to n

4 y i = 0

5 parallel for i = 1 to n

6 for j = 1 to n

7 y i = y i + a ij x j

8 return y

在这段代码中，第 3 行和第 5 行中的 parallel for 关键字表示这两个循环中的迭代都可以并发执行。编译器可以把 parallel for 循环实现为基于嵌套并行的分治式子例程。例如，第 5 到 7 行中的 parallel for 循环可以被实现为对 MAT-VEC-MAIN-LOOP(A,x,y,n,l,n) 的调用，子例程 MAT-VEC-MAIN-LOOP 是编译器生成的辅助子例程，如下：

MAT-VEC-MAIN-LOOP(A, x, y, n, i, i’)

1 if i == i’

2 for j = 1 to n