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

计算机科学与技术

3 y i = y i + a ij x j

4 else mid = └(i+i’)/2 ┘

5 spawn MAT-VEC-MAIN-LOOP(A, x, y, n, i, mid)

6 MAT-VEC-MAIN-LOOP(A, x, y, n, mid+1, i’)

7 sync

该代码递归地 spawn 循环中的前半部分迭代，使其和后半部分迭代并行执行，然后执行一条 sync 语句，创建了一棵二叉树式的执行过程，其中叶子为单独的循环迭代，如图 27.4 所示。

现在来计算对于 n ×n 矩阵， MAT-VEC 的 work T 1 (n) ，也就是计算

其串行化版本的运行时间，这个串行化版本可以通过把 parallel for 循环替换成普通的 for 循环得到。由此，我们得到 T 1 (n)= Θ(n2 ) ，因为第5 到7 行的两重嵌套循环所产生的平方级运行时间占支配地位。在这个分析中，我们忽略掉了实现并行循环的递归 spawn 的开销。事实上，和其串行化版本相比，递归spawn 的开销确