练习 3.40

Warning

本题的解答有误，正等待修复中，具体请见： https://github.com/huangz1990/SICP-answers/pull/14

定义 P 为 (set! x (* x x)) ，定义 Q 为 (set! x (* x x x)) ，以下是并行执行 P 和 Q 时可能产生的计算序列（ ? 符号表示执行过程被其他操作打断）：

1. P –> Q
2. Q –> P
3. (set! x (* x ?)) –> Q –> x –> (set! x (* x x))
4. (set! x (* x ? ?)) –> P –> x –> x –> (set! x (* x x x))
5. (set! x (* x x ?)) –> P –> x –> (set! x (* x x x))

以上计算序列会产生以下结果：

1. (set! x (* 10 10)) => x = 100 => (set! x (* 100 100 100)) => x = 1,000,000
2. (set! x (* 10 10 10)) => x = 1,000 => (set! x (* 1000 1000)) => x = 1,000,000
3. (set! x (* 10 ?)) => (set! x (* 10 10 10)) => x = 1,000 => (set! x (* 10 1000)) => x = 10,000
4. (set! x (* 10 ? ?)) => (set! x (* 10 10)) => x = 100 => (set! x (* 10 100 100)) => x = 100,000
5. (set! x (* 10 10 ?)) => (set! x (* 10 10)) => x = 100 => (set! x (* 10 10 100)) => x = 10,000

Note

以下是 @ZHHY 提供的答案修正信息：

以上解释符号不太清晰

P：(set! x (* x x))``应理解为两次读取``x``与一次写入``x，我们分别记作r11，r12，w1 Q：(set! x (* x x x))``应理解为三次读取``x``与一次写入``x，我们分别记作r21，r22，r23，w2

在保持r11，r12，w1和r21，r22，r23，w2各自内部顺序不变，可以交错排序，因此有 7!/(3!4!) = 35 种不同排法

但考虑到正真影响最后结果的却是 （1）w1，w2 的顺序 （2）w1，r21，r22，r23 的顺序 （3）w2，r11，r12 的顺序

考虑（1）将影响最后的写入操作、（2）将影响Q的读取操作进而影响w2、（3）将影响P的读取操作进而影响w1

分两类

类一：最后完成写操作的是w1，因此它始终在r21，r22，r23之后，所以没有（2）的影响，也就不会影响w2的结果，w2 == 1,000，这时只考虑（3） （i） w2-r11-r12：r11和r12都读取 x=1,000，故 w1 = 1,000,000 （ii） r11-w2-r12：r11读取 x=10，r12读取，x=1,000，故 w1 = 10,000 （iii） r11-r12-w2：r11和r12都读取 x=10，故 w1 = 100

类二：最后完成写操作的是w2，因此它始终在r11，r12之后，所以没有（3）的影响，也就不会影响w1的结果，w1 == 100，这时只考虑（2） （i） w1-r21-r22-r23：r21，r22和r23都读取 x=100，故 w2 = 1,000,000 （ii） r21-w1-r22-r23：r21读取 x=10，r22和r23读取，x=100，故 w2 = 100,000 （iii） r21-r22-w1-r23：r21和r22都读取 x=10，r23读取 x=100，故 w2 = 10,000 （iv） r21-r22-w1-r23：r21，r22和r23都读取 x=10，故 w2 = 1,000

综合以上结果，最后可能的值一共有5种：100，1,000，10,000，100,000，1,000,000

串行化

如果将串行化之后的过程 (s (lambda () (set! x (* x x)))) 定义为 P1 ， (s (lambda () (set! x (* x x x)))) 定义为 P2 ，那么 P1 和 P2 有以下可能的计算序列：

1. P1 –> P2
2. P2 –> P1

它们分别计算出以下结果：

1. (* 10 10) => 100 => (* 100 100 100) => 1,000,000
2. (* 10 10 10) => 1000 => (* 1000 1000) => 1,000,000

因为乘法的交换率原则，只要 P1 和 P2 的执行步骤不交错的话，那么它们之间的运行先后顺序是没有关系的，这也是加速一些并行操作常用的技巧。

讨论

blog comments powered by Disqus