(多线程一个简单的模板计算) 计算科学中存在很多这样一类的算法， 这类算法对一个数组中的一些单元进行填值，所填值取央于已经计算出的邻近单元值，并且计算过程中这些信息一直不变。这种在计算期间邻近单元不发生改变的模式称为模板(stencil)计算。例如，有一个计算最长公共子序列的模板算法，其中c[i, j]的值只取决于c[i-1, j]、 c[i, j-1]和c[i-1, j-1]以及两个给定输入串中的元素xi和yi。輸人的序列是固定不变的,但算法在二维数组c中填写,使得在三个単元c[i-1, j]、c[i, j 1]和c[i-1, j一1]完成后オ计算单元c[i, j]。
本题中,我们探讨如何在一个 nXn的数組A上使用嵌套并行来实现一个简单的模板计算,其中存人单元A[i, j]的值仅取决于A[i', j'],这里i'<i, j 'くj(并且当然有i'
i或者j'j)。换句话说,一个单元的值只取决于它的上边值和左边单元的值, 以及一些数組之外的静态信息。 此外,整个过程中的假设, 一旦计算A[i, j]吋所需要的单元都已填写完，就可以在
(1)的吋同内填人A[i, j]。
划分nXn的数组A内4个n/2Xn/2的子数组:
划分nXn的数组A内4个n/2Xn/2的子数组:
现在看到，可以递归地填人子数组Am中的单元，因为它并不依赖其他三个子数组中的单元。一旦A11完成， 可以递归地并行填人A1z和A21中的单元，这是因为它们都依赖于A11但彼此之间不依赖。 最后，递归地填人A22中的单元。
a.基于分解式(27.11)和上面的讨论， 给出用分治算法SIMPLE-STENCIL来执行这个简单模板计算的多线程伪代码。(不用担心基础情形的处理，这取决于特定的模板。)给出并求解对应规模n的工作量和持续时间的递归式。并行度又是多少?
b.修改上面题(a)的解答，将nXn的数组划分为9个n/3Xn/3的子数组，递归下去使得尽可能得到更多的并行性。分析该算法。 该算法与题(a)中的算法相比，并行度如何?
a.基于分解式(27.11)和上面的讨论， 给出用分治算法SIMPLE-STENCIL来执行这个简单模板计算的多线程伪代码。(不用担心基础情形的处理，这取决于特定的模板。)给出并求解对应规模n的工作量和持续时间的递归式。并行度又是多少?
b.修改上面题(a)的解答，将nXn的数组划分为9个n/3Xn/3的子数组，递归下去使得尽可能得到更多的并行性。分析该算法。 该算法与题(a)中的算法相比，并行度如何?
c. 对照题(a)和(b),按如下推广。选择一个整数b≥2。将-一个nXn数组划分为b2个子数组，每个大小都为n/bXn/b,递归下去使得尽可能得到更多的并行性。关于n和b，该算法的工作量、持续时间和并行度各是多少?使用这种方法， 证明;对任何选择的b≥2,其并行度一定是O(n)。(提示:最后一个问题，证明对于任何选择的b≥2，并行度是n的指数，其指数严格小于1。)
d.给出一个求解这个简单模板问题的多线程算法的伪代码，使得并行度达到O(n/lgn)。使用工作量和持续时间概念，论证该问题事实上有(n)的固有并行度。然而， 我们使用分治法的多线程伪代码，实际上达不到这个最大的并行度。
d.给出一个求解这个简单模板问题的多线程算法的伪代码，使得并行度达到O(n/lgn)。使用工作量和持续时间概念，论证该问题事实上有
