练习 3.40

Warning

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

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

  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 ,那么 P1P2 有以下可能的计算序列:

  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

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

讨论

blog comments powered by Disqus