Stax (6): References and Appendices

Previous: Part Five　Caching, Discussion, Models, and Measurement; Summary and Exercises　｜　Table of Contents

References

[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.

Appendix A　Source Code Index

All paths in Table A.1 are relative to the repository root, and .../stax/ denotes tensorplay/compiler/backends/stax/.

Table A.1　Source Code Index

Appendix B　Measurement Scripts

The data of 第 Section 13were measured with the full version of the following script (here written in the single-case form; the full version additionally measures single-operator baselines, training cases, and call overhead).

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)))

When taking measurements, the thread count should be pinned (tp.set_num_threads), other load should be shut off, and the compilation cache directory (TP_CACHE_DIR) should be pointed at a well-defined location, so that cold compilations can be told apart from cache hits. To produce confidence intervals as in Proposition 13.2, all readings must be kept rather than only the median; to rule out drift between measurement sessions, the two execution modes should be timed alternately (Section 13.5).

Appendix C　Hints and Solutions for Selected Exercises

Exercise 1. Let $N = 128n$. Eager execution consists of, in order, the addition (reading $2N$, writing $N$), relu (reading $N$, writing $N$), the multiplication by 2 (reading $N$, writing $N$), and the row-wise summation (reading $N$, writing $n$), for a total of $8N + n$ elements, i.e. $4100n$ bytes; there are $4N = 512n$ operations, giving an arithmetic intensity of about $0.125$ FLOP/byte. After fusion only $2N$ elements are read and $n$ are written, $1028n$ bytes in total, with an arithmetic intensity of about $0.498$. By Proposition 1.1 the external input is read at least once and the external output written at least once, so the lower bound is exactly $4(2N + n)$ bytes, which the fused execution attains. With the summation removed the lower bound is $3N$ elements ($12N$ bytes) while eager execution moves $7N$ elements, so the fraction saved drops from about 75% to $4/7 \approx 57%$.

Exercise 5. (1) It holds exactly (a signaling NaN is turned into a quiet NaN, so it holds if the two are not distinguished). (2) It does not hold: for $x = -0$, $-0 + 0 = +0$. (3) It holds exactly under round-to-nearest (the remark about signaling NaN is the same as in (1)). (4) It does not hold: the result is NaN when $x$ is NaN or $\pm\infty$, and $-0$ when $x < 0$ or $x = -0$. (5) It does not hold: the result is NaN when $x = \pm\infty$ or NaN. (6) It holds exactly: $0.5$ is exactly representable, and both sides are correct roundings of the same real value. (7) It does not hold: $1/3$ is not exactly representable; for example, in float32, $5/3$ and $5 \cdot \mathrm{fl}(1/3)$ differ in the last bit.

Exercise 16. The coefficients are respectively $n - 1 = 1,048,575$; for $k = 16$, $n/16 - 1 + 15 = 65,550$; for $k = 1024$, $1023 + 1023 = 2046$; and for tree summation $\log_2 n = 20$. A $W$-way accumulator is a segmented summation with $k = W$, whose error-bound coefficient is about $n/W$; when $W$ is too small this term dominates. The typical error given by Corollary 13.1 likewise decreases as $W$ grows.

Exercise 18. Suppose the greedy algorithm first uses the $s$-th slot at time $\tau$. This means that slots numbered $1, \dots, s-1$ are all occupied at that moment and that their buffers are live at $\tau$; together with the newly allocated buffer this gives $|L(\tau)| \ge s$. Hence the number of slots used is $\le \max_\tau |L(\tau)|$; the inequality in the other direction holds for any allocation. When the sizes differ the greedy algorithm is no longer optimal. Take four buffers (sizes in parentheses, intervals are lifetimes): $A(1)$ on $[1, 3]$, $B(1)$ on $[2, 6]$, $C(1)$ on $[3, 4]$, $D(2)$ on $[5, 6]$. The maximum sum of live sizes is 3. Ordering by left endpoint and taking the lowest free address gives $A \to 0$, $B \to 1$, $C \to 2$; when $D$ is allocated, the free addresses 0 and 2 are not adjacent, so it can only be placed at $[3, 5)$, using 5 units in total. By contrast $B \to 0$, $A \to 1$, $C \to 2$, $D \to [1, 3)$ needs only 3 units.

Exercise 20. There are 6 topological orders in total. $acbd$ and $bdac$ have peak 6; the other four ($abcd$, $abdc$, $bacd$, $badc$) have peak 9. The smallest-peak-first rule may take either $a$ or $b$ in the first step (the increment is the same), and chooses $c$ (or $d$) in the second step, because executing it immediately releases the buffer of size 4, giving an order with peak 6.

Exercise 24. For example, let $t(1, 1) = 2$, $t(2, 1) = t(1, 2) = 3$, $t(8, 8) = 1$, and 5 for every other configuration. Starting from $(1, 1)$, all of its neighbours are slower, so the algorithm terminates immediately, while the global optimum lies at $(8, 8)$.

Exercise 25. The capacity constraint is $2T \cdot 32 + T^2 \le 49,152$, which evaluates to $24,576$ for $T = 128$ and $81,920$ for $T = 256$, so $T = 128$. The transfer volume $Q = 4(2 \cdot 4096^3 / 128 + 4096^2) \approx 4.36 \times 10^9$ bytes gives an arithmetic intensity of about 31.5 FLOP/byte, far below $I_{\max} = 2 \cdot 4096 / 12 \approx 683$. Fusing the tail saves about $2mn$ elements, i.e. $1.34 \times 10^8$ bytes, roughly 3.1% of $Q$.

Exercise 31. Let $j$ be the task that finishes last, and let it start at $\tau$. Before $\tau$ every processing unit is busy, and all of them are busy with tasks other than $j$, so $P\tau \le \sum_{i \ne j} c_i$, whence $T = \tau + c_j \le \frac1P \sum_i c_i + (1 - \frac1P) c_j$, after which $c_j$ is relaxed to $\max_i c_i$ to obtain the result. A tight example: $P(P-1)$ unit-length tasks scheduled ahead of a single task of length $P$; list scheduling then takes $(P - 1) + P = 2P - 1$, exactly equal to the improved bound.

Exercise 33. (1) $p(j) = j - 1$, $\delta = -1 \prec 0$: sequential fusion is legal, parallel fusion is not. (2) $\delta = +1$: neither kind of fusion is legal. (3) Have each program instance first recompute the one $a$ value it needs that belongs to the adjacent instance (the halo), before computing the $b$ values it is responsible for; the cost is one extra computation and one extra read per block, and the smaller the blocks the larger the fraction of redundancy.

Exercise 35. (1) Numbering by rows, reading takes $\lceil 24/16 \rceil = 2$ row blocks and 16 column blocks, 18 in total; for $G = 4$ it is $4 + 6 = 10$; for $G = 8$ it is $8 + 3 = 11$. (2) When $G$ does not divide $W$, the last group is not full; the number of row blocks read is $\min(G, W)$ and the number of column blocks is $\lceil W/G \rceil$.

Exercise 41. (1) $\sum_{i=4}^{11}\binom{15}{i}/2^{15} = 31,616/32,768 \approx 0.965$. (2) Taking $j = 1$ and $k = n$, the coverage probability is $1 - 2^{1-n}$, which is $0.992$ for $n = 8$ and $0.984$ for $n = 7$, so the smallest $n$ is 8. (3) Applying Proposition 13.2 to the medians of $r$ sessions gives an interval for the median of “the distribution of session medians”, which reflects the differences between sessions; pooling all $rn$ readings together instead wrongly assumes that they are identically distributed, and the resulting interval is much narrower while no longer having the claimed coverage probability.

Exercise 46. (1) By the proof of Theorem 5.1, the reverse of an addition costs 2 operations and the reverse of a multiplication 4, so the total cost is at most 5 times the forward cost. (2) The forward sweep computes prefix products $p_k = p_{k-1} x_k$; the reverse sweep starts from $\bar p_n = 1$ and uses $\bar x_k = \bar p_k, p_{k-1}$, $\bar p_{k-1} = \bar p_k, x_k$, for $O(n)$ operations in total. Computing the partial derivatives one at a time ($n - 2$ multiplications each) costs $\Theta(n^2)$ operations. (3) Forward mode obtains one directional derivative $Jv$ at a time, with $J$ being $1 \times n$; sweeping the $n$ coordinate directions takes $n$ applications, consistent with the case $m = 1$ and large $n$ in Proposition 5.2.

Exercise 47. (1) The lower bound is about $4096^3 / (2\sqrt3 \cdot \sqrt{49,152}) - 49,152 \approx 8.9 \times 10^7$ words, whereas the transfer volume of the tiled version is about $1.09 \times 10^9$ words, a factor of about 12 apart. The transfer volume of the tiled version is independent of $B_K$ ($B_K$ constrains $T$ only through the capacity constraint), and the gap decomposes into two factors: $\sqrt S / T \approx 221.7/128 \approx 1.73$, i.e. the tiling does not use the full capacity; and about $4\sqrt 3 \approx 6.9$, i.e. the constant in Theorem 9.1 is itself not tight (a known tighter lower bound is about $2mnk/\sqrt S$). (2) Some processor computes at least $mnk/P$ products; apply the proof of Theorem 9.1 to that processor alone. (3) Strassen’s algorithm does not compute all $mnk$ products, so the premise of the theorem does not hold; its lower bound is stated in terms of the expansion property of the computation graph and is of order $\Omega\bigl((n/\sqrt S)^{\log_2 7} S\bigr)$.

Exercise 48. (1) $\mathrm{vs}(P_4) = 1$ and $\mathrm{vs}(C_4) = 2$. $P_4$ has 3 edges and $K = 4$, so the interval given by the proof is $[8, 11]$; $C_4$ has 4 edges and $K = 5$, giving $[15, 19]$. Enumerating all topological orders, the minimum peaks are 11 and 18 respectively, both of which lie inside the corresponding interval. (2) Every node of the tree has exactly one user, so the minimum peak of each subtree can be computed bottom-up in the Sethi–Ullman manner, and the evaluation order of the subtrees can be decided by sorting on the difference between the subtree peak and its output size.

Exercise 50. (1) $\Theta = \begin{pmatrix}0&1\1&0\end{pmatrix}$ maps $(1, -1)$ to $(-1, 1) \prec 0$, so the exchange is not legal; $(1, -1)$ has a negative component, so the loop band is not fully permutable. (2) The skew matrix $\Theta = \begin{pmatrix}1&0\1&1\end{pmatrix}$ maps the three distance vectors to $(1, 1)$, $(0, 1)$ and $(1, 0)$ respectively, all of them nonnegative, so the computation can be tiled. (3) One needs $c_1 \ge 1$, $c_2 \ge 1$, $c_1 - c_2 \ge 1$; for example $c = (2, 1)$ and $\theta = 2i + j$; iterations with the same $\theta$ (iterations on the line $2i + j = $ constant) have no dependences between them and can be executed in parallel.

Exercise 51. (1) $\beta(3, 3) = \binom63 = 20$. With a chain of length 6, $s = 3$ and $t = 2$, take $m = \beta(3, 1) = 4$ according to the recursion of Theorem 5.4: advance 4 steps and save $z_4$; reverse the last two steps with the remaining slots (from $z_4$ advance 1 step and save $z_5$, execute reverse step 6 and release $z_5$; execute reverse step 5 on $z_4$) and release $z_4$; then reverse the first 4 steps with repetition count 1 and all 3 slots (from $z_0$ advance 1 step and save $z_1$, advance 1 more step and save $z_2$, advance 1 more step to get $z_3$ and execute reverse step 4; execute reverse step 3 on $z_2$ and release $z_2$; execute reverse step 2 on $z_1$ and release $z_1$; execute reverse step 1 on $z_0$). The forward steps $\phi_1, \phi_2, \phi_3$ are each computed twice, $\phi_4, \phi_5$ once each, $\phi_6$ need not be computed at all, and at most 3 slots are occupied at any time. (2) For $t = 2$ one needs $\binom{s+2}{2} \ge 1000$, so $s = 44$; for $t = 3$, $s = 17$; for $t = 4$, $s = 10$. (3) With uniform segmentation and at most two computations per step, about $2\sqrt{1000} \approx 63$ units of storage are needed; the binomial scheme needs only 44 slots at $t = 2$, and paying for one extra recomputation brings it down to 17.

Exercise 52. (1) By the sufficient condition of Proposition 9.3, $N \ge \ln 100 / 0.01 \approx 460.5$, so take 461; solving $(0.99)^N \le 0.01$ directly requires only $N \ge 459$. (2) Following Exercise 24, construct a “trap” whose local optimum lies among the slowest 10%: all of its neighbours are slower, while the globally better configurations lie elsewhere and are in the majority, so the probability that random search falls into the trap is negligible. (3) Under noise, “fastest” should become “measured fastest”, and $G_q$ should be relaxed to the configurations whose true running time is at most $(1 + \eta_{\max})/(1 - \eta_{\max}) \approx 1 + 2\eta_{\max}$ times the quantile; successive halving eliminates half of the candidates per round and doubles the number of measurements, so the total number of measurements over $N$ candidates is about $N \log_2 N$ units of the initial budget.

Previous: Part Five　Caching, Discussion, Models, and Measurement; Summary and Exercises　｜　Table of Contents