上一节:第五节 缓存、讨论、模型与测量;小结与习题 | 目录
参考文献
[1] Williams S, Waterman A, Patterson D. Roofline: An Insightful Visual Performance Model for Multicore Architectures[J]. Communications of the ACM, 2009, 52(4): 65-76.
[2] Jones N D, Gomard C K, Sestoft P. Partial Evaluation and Automatic Program Generation[M]. Englewood Cliffs: Prentice Hall, 1993.
[3] Johnsson T. Lambda Lifting: Transforming Programs to Recursive Equations[C]// Functional Programming Languages and Computer Architecture (FPCA). Berlin: Springer, 1985: 190-203.
[4] Cytron R, Ferrante J, Rosen B K, Wegman M N, Zadeck F K. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph[J]. ACM Transactions on Programming Languages and Systems, 1991, 13(4): 451-490.
[5] Reed J, DeVito Z, He H, Ussery A, Ansel J. torch.fx: Practical Program Capture and Transformation for Deep Learning in Python[C]// Proceedings of Machine Learning and Systems (MLSys). 2022.
[6] King J C. Symbolic Execution and Program Testing[J]. Communications of the ACM, 1976, 19(7): 385-394.
[7] Weiser M. Program Slicing[J]. IEEE Transactions on Software Engineering, 1984, SE-10(4): 352-357.
[8] IEEE Computer Society. IEEE Standard for Floating-Point Arithmetic: IEEE Std 754-2019[S]. New York: IEEE, 2019.
[9] Griewank A, Walther A. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation[M]. 2nd ed. Philadelphia: SIAM, 2008.
[10] Chen T, Xu B, Zhang C, Guestrin C. Training Deep Nets with Sublinear Memory Cost[J]. arXiv preprint arXiv:1604.06174, 2016.
[11] Jain P, Jain A, Nrusimha A, et al. Checkmate: Breaking the Memory Wall with Optimal Tensor Rematerialization[C]// Proceedings of Machine Learning and Systems (MLSys). 2020.
[12] Cormen T H, Leiserson C E, Rivest R L, Stein C. Introduction to Algorithms[M]. 3rd ed. Cambridge: MIT Press, 2009.
[13] Edmonds J, Karp R M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems[J]. Journal of the ACM, 1972, 19(2): 248-264.
[14] Hendrycks D, Gimpel K. Gaussian Error Linear Units (GELUs)[J]. arXiv preprint arXiv:1606.08415, 2016.
[15] Ansel J, Yang E, He H, et al. PyTorch 2: Faster Machine Learning Through Dynamic Python Bytecode Transformation and Graph Compilation[C]// Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 2024.
[16] Ragan-Kelley J, Barnes C, Adams A, Paris S, Durand F, Amarasinghe S. Halide: A Language and Compiler for Optimizing Parallelism, Locality, and Recomputation in Image Processing Pipelines[C]// Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2013: 519-530.
[17] Chan T F, Golub G H, LeVeque R J. Algorithms for Computing the Sample Variance: Analysis and Recommendations[J]. The American Statistician, 1983, 37(3): 242-247.
[18] Higham N J. Accuracy and Stability of Numerical Algorithms[M]. 2nd ed. Philadelphia: SIAM, 2002.
[19] Cousot P, Cousot R. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints[C]// Proceedings of the 4th ACM Symposium on Principles of Programming Languages (POPL). 1977: 238-252.
[20] Kennedy K, McKinley K S. Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution[C]// Languages and Compilers for Parallel Computing (LCPC). Berlin: Springer, 1993: 301-320.
[21] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. San Francisco: W. H. Freeman, 1979.
[22] Sethi R. Complete Register Allocation Problems[J]. SIAM Journal on Computing, 1975, 4(3): 226-248.
[23] Tillet P, Kung H T, Cox D. Triton: An Intermediate Language and Compiler for Tiled Neural Network Computations[C]// Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages (MAPL). 2019: 10-19.
[24] Milakov M, Gimelshein N. Online Normalizer Calculation for Softmax[J]. arXiv preprint arXiv:1805.02867, 2018.
[25] Hong J W, Kung H T. I/O Complexity: The Red-Blue Pebble Game[C]// Proceedings of the 13th Annual ACM Symposium on Theory of Computing (STOC). 1981: 326-333.
[26] Graham R L. Bounds on Multiprocessing Timing Anomalies[J]. SIAM Journal on Applied Mathematics, 1969, 17(2): 416-429.
[27] Frostig R, Johnson M J, Leary C. Compiling Machine Learning Programs via High-Level Tracing[C]// Proceedings of the Conference on Systems and Machine Learning (SysML). 2018.
[28] Chen T, Moreau T, Jiang Z, et al. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning[C]// Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 2018: 578-594.
[29] Allen R, Kennedy K. Optimizing Compilers for Modern Architectures: A Dependence-based Approach[M]. San Francisco: Morgan Kaufmann, 2001.
[30] Pugh W. The Omega Test: A Fast and Practical Integer Programming Algorithm for Dependence Analysis[C]// Proceedings of the 1991 ACM/IEEE Conference on Supercomputing. 1991: 4-13.
[31] Feautrier P. Some Efficient Solutions to the Affine Scheduling Problem. Part I. One-dimensional Time[J]. International Journal of Parallel Programming, 1992, 21(5): 313-347.
[32] Bondhugula U, Hartono A, Ramanujam J, Sadayappan P. A Practical Automatic Polyhedral Parallelizer and Locality Optimizer[C]// Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2008: 101-113.
[33] Dao T, Fu D Y, Ermon S, Rudra A, Ré C. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness[C]// Advances in Neural Information Processing Systems (NeurIPS). 2022.
[34] Pearlmutter B A. Fast Exact Multiplication by the Hessian[J]. Neural Computation, 1994, 6(1): 147-160.
[35] Sabne A. XLA: Compiling Machine Learning for Peak Performance[R]. Google, 2020.
[36] Lattner C, Amini M, Bondhugula U, et al. MLIR: Scaling Compiler Infrastructure for Domain Specific Computation[C]// Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization (CGO). 2021: 2-14.
[37] Hoefler T, Belli R. Scientific Benchmarking of Parallel Computing Systems: Twelve Ways to Tell the Masses When Reporting Performance Results[C]// Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC). 2015.
[38] Baur W, Strassen V. The Complexity of Partial Derivatives[J]. Theoretical Computer Science, 1983, 22(3): 317-330.
[39] Loomis L H, Whitney H. An Inequality Related to the Isoperimetric Inequality[J]. Bulletin of the American Mathematical Society, 1949, 55(10): 961-962.
[40] Irony D, Toledo S, Tiskin A. Communication Lower Bounds for Distributed-Memory Matrix Multiplication[J]. Journal of Parallel and Distributed Computing, 2004, 64(9): 1017-1026.
[41] Dahlhaus E, Johnson D S, Papadimitriou C H, Seymour P D, Yannakakis M. The Complexity of Multiterminal Cuts[J]. SIAM Journal on Computing, 1994, 23(4): 864-894.
[42] Arnborg S, Corneil D G, Proskurowski A. Complexity of Finding Embeddings in a k-Tree[J]. SIAM Journal on Algebraic and Discrete Methods, 1987, 8(2): 277-284.
[43] Kinnersley N G. The Vertex Separation Number of a Graph Equals Its Path-Width[J]. Information Processing Letters, 1992, 42(6): 345-350.
[44] Griewank A. Achieving Logarithmic Growth of Temporal and Spatial Complexity in Reverse Automatic Differentiation[J]. Optimization Methods and Software, 1992, 1(1): 35-54.
[45] Griewank A, Walther A. Algorithm 799: Revolve: An Implementation of Checkpointing for the Reverse or Adjoint Mode of Computational Differentiation[J]. ACM Transactions on Mathematical Software, 2000, 26(1): 19-45.
[46] Irigoin F, Triolet R. Supernode Partitioning[C]// Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). 1988: 319-329.
[47] Wolf M E, Lam M S. A Data Locality Optimizing Algorithm[C]// Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 1991: 30-44.
[48] Schrijver A. Theory of Linear and Integer Programming[M]. Chichester: Wiley, 1986.
[49] Zheng L, Jia C, Sun M, et al. Ansor: Generating High-Performance Tensor Programs for Deep Learning[C]// Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 2020: 863-879.
[50] Kjolstad F, Kamil S, Chou S, Lugato D, Amarasinghe S. The Tensor Algebra Compiler[J]. Proceedings of the ACM on Programming Languages, 2017, 1(OOPSLA): 77:1-77:29.
[51] Baghdadi R, Ray J, Ben Romdhane M, et al. Tiramisu: A Polyhedral Compiler for Expressing Fast and Portable Code[C]// Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization (CGO). 2019: 193-205.
[52] Winskel G. The Formal Semantics of Programming Languages: An Introduction[M]. Cambridge: MIT Press, 1993.
[53] Bergstra J, Bengio Y. Random Search for Hyper-Parameter Optimization[J]. Journal of Machine Learning Research, 2012, 13: 281-305.
[54] Li L, Jamieson K, DeSalvo G, Rostamizadeh A, Talwalkar A. Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization[J]. Journal of Machine Learning Research, 2018, 18(185): 1-52.
[55] Darte A. On the Complexity of Loop Fusion[J]. Parallel Computing, 2000, 26(9): 1175-1193.
[56] Leroy X. Formal Verification of a Realistic Compiler[J]. Communications of the ACM, 2009, 52(7): 107-115.
[57] Gilbert J R, Lengauer T, Tarjan R E. The Pebbling Problem is Complete in Polynomial Space[J]. SIAM Journal on Computing, 1980, 9(3): 513-524.
附录 A 源码索引
表 A.1 中的路径均相对于仓库根目录,.../stax/ 表示 tensorplay/compiler/backends/stax/。
表 A.1 源码索引
| 主题 | 源码位置 | 节 |
|---|---|---|
| 编译入口、特化与守卫 | tensorplay/compiler/_core/api.py、guards.py | 2 |
| 分派的第一级入口 | src/bindings/python/Stax.cpp | 2.4 |
| 追踪器与守卫回放 | tensorplay/graph/tracer.py、proxy.py | 3 |
| 图变换 | tensorplay/graph/passes/ | 4.1 至 4.7 |
| 算子级分解表 | tensorplay/_decomp/decompositions.py、.../stax/op_lowerings.py | 4.8 |
| 函数化 | tensorplay/graph/passes/functionalize.py | 4.9 |
| 自动微分与最小割划分 | tensorplay/compiler/_core/aot_autograd.py | 5 |
| 降级与循环级中间表示 | .../stax/graph_lowering.py、op_lowerings.py、ir.py | 6.1 至 6.7 |
| 循环体与值域分析 | .../stax/loop_body.py、index_propagation.py、bounds.py | 6.8 |
| 调度、融合与内存规划 | .../stax/scheduler.py、choices.py、memory.py、codegen/memory_planning.py | 7 |
| CPU 代码生成 | .../stax/codegen/cpp.py、cpu_vec_isa.py | 8 |
| GPU 代码生成与启动配置 | .../stax/codegen/triton.py、runtime/triton_heuristics.py | 9 |
| 矩阵乘模板 | .../stax/templates/ | 9.8 |
| CUDA Graphs | tensorplay/compiler/backends/cudagraphs.py | 9.9 |
| 符号形状与形状守卫 | tensorplay/export/_symbolic_dims.py、.../stax/sizevars.py | 10.2、10.3 |
| 动态模式的捕获与守卫 | tensorplay/graph/experimental/_symbolic_trace.py、_symbolic_dispatch.py、.../stax/shape_guards.py | 10.4 |
| 符号大小的梯度公式 | config/derivatives.yaml、tpx/src/SymbolicShapes.cpp | 10.4 |
| 代码缓存与并行编译 | .../stax/codecache.py、async_compile.py | 11.1、11.2 |
| 后端入口与回退 | .../stax/backend.py | 11.3 |
| 调试后端 | tensorplay/compiler/backends/debugging.py | 11.4 |
| 注意力的模式匹配 | .../stax/graph_passes/fuse_attention.py | 9.10 |
| omni_attention 接口与块掩码 | tensorplay/nn/attention/omni_attention.py | 9.10 |
| 注意力模板 | .../stax/attention/、.../stax/codegen/templates/omni_*.jinja | 9.10 |
| 矩阵乘模板与配置 | .../stax/codegen/templates/triton_mm.py.jinja、.../stax/heuristics/template/gemm.py | 9.8 |
| 融合的打分与合法性 | .../stax/choices.py(score_fusion、can_fuse) | 7.3 |
| 前向模式自动微分 | tensorplay/autograd/forward_ad.py、functional.py | 5.7 |
| 依赖于数据的算子的回退 | .../stax/op_lowerings.py(make_fallback) | 10.5 |
| 最小割划分 | tensorplay/compiler/_core/aot.py(partition_min_cut) | 5.4、5.8 |
| 激活检查点 | tensorplay/utils/checkpoint.py(checkpoint、checkpoint_sequential) | 5.8 |
| 扫描节点 | .../stax/ir.py(Scan)、op_lowerings.py(cumsum) | 7.7 |
附录 B 测量脚本
第 13 节的数据由以下脚本的完整版测得(单个用例的写法;完整版另含单算子基线、训练用例与调用开销的测量)。
import statistics, time
import tensorplay as tp
def timeit(fn, *args, warmup=3, repeat=15):
for _ in range(warmup):
fn(*args)
samples = []
for _ in range(repeat):
t = time.perf_counter()
fn(*args)
samples.append(time.perf_counter() - t)
return statistics.median(samples)
def case(fn, args, bytes_eager, bytes_fused):
eager = timeit(fn, *args)
compiled = tp.compile(fn, strict_native=True)
compiled(*args) # 首次调用:编译
comp = timeit(compiled, *args)
err = float((compiled(*args) - fn(*args)).abs().max())
return {
"eager_ms": eager * 1e3, "compiled_ms": comp * 1e3, "speedup": eager / comp,
"eager_GBps": bytes_eager / eager / 1e9, "compiled_GBps": bytes_fused / comp / 1e9,
"max_abs_err": err,
}
rows, cols = 8192, 2048
N = rows * cols
x, w = tp.randn(rows, cols), tp.randn(rows, cols)
print(case(lambda x, w: (tp.relu(x + w) * 2).sum(-1), (x, w),
bytes_eager=4 * (8 * N + rows), bytes_fused=4 * (2 * N + rows)))
测量时应固定线程数(tp.set_num_threads),关闭其他负载,并把编译缓存目录(TP_CACHE_DIR)指向一个确定的位置,以区分冷编译与缓存命中。若要按命题 13.2 给出置信区间,应保存全部读数而不只是中位数;若要排除时段间的漂移,应让两种执行方式交替计时(13.5 节)。
附录 C 部分习题的提示与解答
习题 1. 记 $N = 128n$。即时执行依次为加法(读 $2N$、写 $N$)、relu(读 $N$、写 $N$)、乘 2(读 $N$、写 $N$)与按行求和(读 $N$、写 $n$),共 $8N + n$ 个元素,即 $4100n$ 字节;运算 $4N = 512n$ 次,算术强度约 $0.125$ FLOP/byte。融合后只读 $2N$、写 $n$,共 $1028n$ 字节,算术强度约 $0.498$。由命题 1.1,外部输入至少读一次、外部输出至少写一次,下界恰为 $4(2N + n)$ 字节,融合执行达到它。去掉求和后下界为 $3N$ 个元素($12N$ 字节),即时执行为 $7N$ 个元素,节省的比例从约 75% 降为 $4/7 \approx 57%$。
习题 5. (1)精确成立(信号 NaN 会被转为静默 NaN,若不区分二者则成立)。(2)不成立:$x = -0$ 时 $-0 + 0 = +0$。(3)在就近舍入下精确成立(信号 NaN 的说明同(1))。(4)不成立:$x$ 为 NaN 或 $\pm\infty$ 时结果为 NaN,$x < 0$ 或 $x = -0$ 时结果为 $-0$。(5)不成立:$x = \pm\infty$ 或 NaN 时结果为 NaN。(6)精确成立:$0.5$ 可精确表示,两端是同一个实数值的正确舍入。(7)不成立:$1/3$ 不可精确表示,例如 float32 中 $5/3$ 与 $5 \cdot \mathrm{fl}(1/3)$ 在最后一位上不同。
习题 16. 系数分别为 $n - 1 = 1,048,575$;$k = 16$ 时 $n/16 - 1 + 15 = 65,550$;$k = 1024$ 时 $1023 + 1023 = 2046$;树形求和为 $\log_2 n = 20$。$W$ 路累加器相当于 $k = W$ 的分段求和,误差界的系数约为 $n/W$,$W$ 过小时这一项占主导。推论 13.1 给出的典型误差同样随 $W$ 增大而减小。
习题 18. 设贪心算法在时刻 $\tau$ 第一次启用第 $s$ 个槽位,这意味着编号 $1, \dots, s-1$ 的槽位此刻都被占用,它们的缓冲区在 $\tau$ 时刻活跃,连同新分配的缓冲区,$|L(\tau)| \ge s$。故所用槽位数 $\le \max_\tau |L(\tau)|$;反方向的不等式对任何分配都成立。大小不同时贪心算法不再最优。取四个缓冲区(括号内为大小,区间为生存期):$A(1)$ 于 $[1, 3]$,$B(1)$ 于 $[2, 6]$,$C(1)$ 于 $[3, 4]$,$D(2)$ 于 $[5, 6]$。活跃大小之和的最大值为 3。按左端点排序、取最低的可用地址,得 $A \to 0$、$B \to 1$、$C \to 2$;$D$ 分配时空出的是不相邻的地址 0 与 2,只能放在 $[3, 5)$,共用 5 个单位。而 $B \to 0$、$A \to 1$、$C \to 2$、$D \to [1, 3)$ 只需 3 个单位。
习题 20. 共 6 个拓扑序。$acbd$ 与 $bdac$ 的峰值为 6,其余四个($abcd$、$abdc$、$bacd$、$badc$)的峰值为 9。最小峰值优先规则第一步在 $a$、$b$ 之间任取一个(增量相同),第二步选择 $c$(或 $d$),因为它的执行使大小为 4 的缓冲区随即释放,得到峰值为 6 的次序。
习题 24. 例如令 $t(1, 1) = 2$,$t(2, 1) = t(1, 2) = 3$,$t(8, 8) = 1$,其余配置为 5。从 $(1, 1)$ 出发,它的每个邻居都更慢,算法立即终止,而全局最优在 $(8, 8)$。
习题 25. 容量约束为 $2T \cdot 32 + T^2 \le 49,152$,$T = 128$ 时为 $24,576$,$T = 256$ 时为 $81,920$,故 $T = 128$。传输量 $Q = 4(2 \cdot 4096^3 / 128 + 4096^2) \approx 4.36 \times 10^9$ 字节,算术强度约 31.5 FLOP/byte,远小于 $I_{\max} = 2 \cdot 4096 / 12 \approx 683$。尾部融合节省约 $2mn$ 个元素,即 $1.34 \times 10^8$ 字节,约占 $Q$ 的 3.1%。
习题 31. 设最后完成的任务 $j$ 开始于 $\tau$。$\tau$ 之前所有工作单元都在忙,且忙的都是 $j$ 以外的任务,故 $P\tau \le \sum_{i \ne j} c_i$,于是 $T = \tau + c_j \le \frac1P \sum_i c_i + (1 - \frac1P) c_j$,再以 $\max_i c_i$ 放大 $c_j$ 即得。紧的例子:$P(P-1)$ 个长度为 1 的任务排在一个长度为 $P$ 的任务之前,列表调度的完成时间为 $(P - 1) + P = 2P - 1$,恰等于改进后的界。
习题 33. (1)$p(j) = j - 1$,$\delta = -1 \prec 0$:顺序融合合法,并行融合不合法。(2)$\delta = +1$:两种融合都不合法。(3)让每个程序实例在计算自己负责的 $b$ 之前,先重算它所需的、属于相邻实例的那一个 $a$ 值(光晕),代价是每块多一次计算与多一次读取,块越小,冗余的比例越高。
习题 35. (1)按行编号读取 $\lceil 24/16 \rceil = 2$ 个行块与 16 个列块,共 18 个;$G = 4$ 时为 $4 + 6 = 10$ 个;$G = 8$ 时为 $8 + 3 = 11$ 个。(2)$G$ 不整除 $W$ 时,最后一组不满,读取的行块数为 $\min(G, W)$,列块数为 $\lceil W/G \rceil$。
习题 41. (1)$\sum_{i=4}^{11}\binom{15}{i}/2^{15} = 31,616/32,768 \approx 0.965$。(2)取 $j = 1$、$k = n$,覆盖概率为 $1 - 2^{1-n}$,$n = 8$ 时为 $0.992$,$n = 7$ 时为 $0.984$,故最小的 $n$ 为 8。(3)对 $r$ 个轮中位数应用命题 13.2,得到的是"轮中位数的分布"的中位数的区间,它反映了时段之间的差异;把 $rn$ 个读数合在一起,则错误地假定了它们同分布,区间会窄得多,却不再有所声称的覆盖概率。
习题 46. (1)由定理 5.1 的证明,加法的反向为 2 次运算,乘法为 4 次,总代价至多为前向的 5 倍。(2)前向计算前缀积 $p_k = p_{k-1} x_k$;反向趟从 $\bar p_n = 1$ 开始,$\bar x_k = \bar p_k, p_{k-1}$,$\bar p_{k-1} = \bar p_k, x_k$,共 $O(n)$ 次运算。逐个计算每个偏导数(各为 $n - 2$ 次乘法)共需 $\Theta(n^2)$ 次。(3)前向模式一次只得到一个方向导数 $Jv$,$J$ 是 $1 \times n$ 的,取遍 $n$ 个坐标方向需要 $n$ 次,与命题 5.2 中 $m = 1$、$n$ 很大的情形一致。
习题 47. (1)下界约为 $4096^3 / (2\sqrt3 \cdot \sqrt{49,152}) - 49,152 \approx 8.9 \times 10^7$ 个字,分块的传输量约为 $1.09 \times 10^9$ 个字,相差约 12 倍。分块的传输量与 $B_K$ 无关($B_K$ 只通过容量约束限制 $T$),差距可以分解为两个因子:$\sqrt S / T \approx 221.7/128 \approx 1.73$,即分块没有用满容量;以及约 $4\sqrt 3 \approx 6.9$,即定理 9.1 的常数本身不紧(已知更紧的下界约为 $2mnk/\sqrt S$)。(2)某个处理器至少计算 $mnk/P$ 个乘积,对它单独应用定理 9.1 的证明即可。(3)Strassen 算法不计算全部 $mnk$ 个乘积,定理的前提不成立;它的下界以计算图的扩张性质表述,阶为 $\Omega\bigl((n/\sqrt S)^{\log_2 7} S\bigr)$。
习题 48. (1)$\mathrm{vs}(P_4) = 1$,$\mathrm{vs}(C_4) = 2$。$P_4$ 有 3 条边,$K = 4$,证明给出的区间为 $[8, 11]$;$C_4$ 有 4 条边,$K = 5$,区间为 $[15, 19]$。穷举全部拓扑序,最小峰值分别为 11 与 18,都落在区间中。(2)树上每个节点只有一个使用者,可以按 Sethi–Ullman 的方式自底向上计算每棵子树的最小峰值,并按子树峰值与输出大小的差值排序决定子树的求值次序。
习题 50. (1)$\Theta = \begin{pmatrix}0&1\1&0\end{pmatrix}$ 把 $(1, -1)$ 映为 $(-1, 1) \prec 0$,交换不合法;$(1, -1)$ 有负分量,循环带不是完全可置换的。(2)偏斜 $\Theta = \begin{pmatrix}1&0\1&1\end{pmatrix}$ 把三个距离向量分别映为 $(1, 1)$、$(0, 1)$、$(1, 0)$,全部非负,可以分块。(3)需要 $c_1 \ge 1$、$c_2 \ge 1$、$c_1 - c_2 \ge 1$,例如 $c = (2, 1)$,$\theta = 2i + j$;$\theta$ 相同的迭代(直线 $2i + j = $ 常数上的迭代)之间没有依赖,可以并行执行。
习题 51. (1)$\beta(3, 3) = \binom63 = 20$。链长 6、$s = 3$、$t = 2$ 时,按定理 5.4 的递推取 $m = \beta(3, 1) = 4$:前进 4 步保存 $z_4$;以剩余槽位反演后两步(从 $z_4$ 前进 1 步保存 $z_5$,执行反向第 6 步,释放 $z_5$;在 $z_4$ 上执行反向第 5 步),释放 $z_4$;再以重复数 1、全部 3 个槽位反演前 4 步(从 $z_0$ 前进 1 步保存 $z_1$,再前进 1 步保存 $z_2$,再前进 1 步得 $z_3$,执行反向第 4 步;在 $z_2$ 上执行反向第 3 步,释放 $z_2$;在 $z_1$ 上执行反向第 2 步,释放 $z_1$;在 $z_0$ 上执行反向第 1 步)。前向步骤 $\phi_1, \phi_2, \phi_3$ 各计算两次,$\phi_4, \phi_5$ 各一次,$\phi_6$ 不必计算,任何时刻至多占用 3 个槽位。(2)$t = 2$ 时需要 $\binom{s+2}{2} \ge 1000$,$s = 44$;$t = 3$ 时 $s = 17$;$t = 4$ 时 $s = 10$。(3)均匀分段在每步至多计算两次的前提下需要约 $2\sqrt{1000} \approx 63$ 个单位的存储,二项式方案在 $t = 2$ 时只需 44 个槽位,且多付一次重算即可降到 17 个。
习题 52. (1)由命题 9.3 的充分条件,$N \ge \ln 100 / 0.01 \approx 460.5$,取 461;直接解 $(0.99)^N \le 0.01$ 只需 $N \ge 459$。(2)仿照习题 24 构造一个局部最优位于最慢 10% 之中的"陷阱":它的邻居都更慢,而全局较好的配置分布在别处并占多数,随机搜索落入陷阱的概率可以忽略。(3)噪声下应把"最快"改为"实测最快",并把 $G_q$ 放宽为真实耗时不超过分位点的 $(1 + \eta_{\max})/(1 - \eta_{\max}) \approx 1 + 2\eta_{\max}$ 倍的配置;连续减半每轮淘汰一半候选,把测量次数加倍,$N$ 个候选的总测量次数约为 $N \log_2 N$ 量级的初始单位。
上一节:第五节 缓存、讨论、模型与测量;小结与习题 | 目录