The 1982 MICRO 15 progress report by Jacobs, Prins, Siegel and Wilson proposed a Metropolis-style ('Monte Carlo') optimizer for FPS Array Processor assembly language (APAL): a stochastic search that randomly applies six elementary transformations, verifies meaning preservation with deliberately conservative ('safe') semantic checks, and accepts changes with an annealing-like probability that is tightened over time. The report identified six unresolved issues: quantifying and reducing the false negatives of the safe checks without compromising safety; the unknown convergence properties and computer time of the optimizer, with no systematic method for choosing the metric, acceptance schedule, and guidance heuristics; imprecise base-register/address resolution that forces over-approximation when verification subtasks fail; the conceptually specified but unimplemented T6 primitive-group movement across cycles and control-flow paths; unspecified space/time bounds and graceful-termination strategies for the IS_NEEDED/EQUIVALENT tracking procedures; and the design trade-off between deterministic heuristic guidance and the robustness advantage of nondeterminism. The Cornell group never published a completion or evaluation of the system, and its FPS/APAL target is long obsolete; later stochastic code optimizers treat the search empirically and either abandon safe verification or restructure it, so the convergence/expected-time characterization and the quantified safety-versus-precision trade-off of conservative equivalence verification remain open.

Background

In the late 1970s and early 1980s, scientific computing groups attached dedicated array processors to general-purpose hosts; a common example was the Floating Point Systems (FPS) AP-120B/AP-190B family, programmed in an assembly-like language called APAL. These machines were 'horizontal': each machine cycle issued one wide instruction word whose fields independently steered several functional units (adders, multipliers, memory interfaces); the arithmetic units were pipelined, so a result became available only after a latency of several cycles; and the memory-fetch pipeline advanced even on otherwise empty cycles. Naively translated APAL code therefore left functional units idle, and good performance required rearranging and consolidating instructions — a problem closely related to microcode compaction, the reordering of horizontally encoded operations to shorten the schedule — while register conflicts and branches complicated any reordering. Deterministic optimizers of the time relied on heuristics tailored to specific input classes; the contrasting deterministic global approach, trace scheduling (compacting along predicted execution traces for Very Long Instruction Word, i.e. VLIW, machines), was being developed at the same time (Fisher's ELI-512, 1983).

Jacobs, Prins, Siegel and Wilson (MICRO 15, 1982) proposed a non-deterministic strategy for APAL: treat optimization as a stochastic search of the space of programs equivalent to the input. At each step the optimizer randomly proposes one of six elementary, undirected transformations — T1 deletes a no-operation (NOP) cycle, T2 inserts one, T3 and T4 delete or insert a 'primitive group' (the smallest self-contained set of actions occurring within a cycle), T5 switches a register or memory alias, and T6 moves a primitive group to a different cycle — then checks that the transformation preserves program meaning, computes an estimated performance metric (for example a weighted count of cycles in the most deeply nested loops), and accepts the change with a Metropolis-style probability that is tightened as the run proceeds. This is the statistical-physics acceptance scheme popularized the following year as 'simulated annealing' by Kirkpatrick, Gelatt and Vecchi (1983): worsening moves are accepted early with a temperature-dependent probability and later almost never.

Two design facts make the problem hard and are central to the question. First, general program equivalence is undecidable, so the transformation-specific semantic checks were deliberately 'safe', i.e. conservative: they never accept a meaning-changing transformation, at the price of sometimes rejecting an equivalent one (a false negative). Second, the metric is only an estimate of running time — the paper itself states that no exact, efficiently computable function maps APAL programs to true running time. The machine is modeled uniformly as named 'value objects' (registers, memory slots, pipeline registers, status bits) with explicit and implicit per-cycle USE (read) and DEF (write) relations — implicit transfers model hardware that advances every cycle, such as the memory-fetch pipeline and delayed availability of results in status bits. Verification is done on the fly by two tracking procedures: IS_NEEDED forward-tracks a set of value objects to decide whether a write's values are ever used, and EQUIVALENT backward-tracks two objects to decide whether they hold the same value at a given cycle; both use per-block TODO/DONE bookkeeping to cross basic-block boundaries (a basic block is a maximal branch-free sequence of cycles). A hand-worked inner-product example reduced a 20-cycle loop to 4 cycles, showing the intended compaction power. The paper is explicitly a progress report — the system was under construction at Cornell University — and it states its own limits: the transformation set reaches only a proper subset of all semantically equivalent programs, and the metric is inexact, so the realistic objective is the metrically best reachable program, judged by expected time to a good solution — a program whose estimated metric is within a stated factor of the metrically best reachable program — rather than absolute optimality. The unresolved issues that the report itself identifies form the problem.

Problem Statement

Resolve the six issues that Jacobs, Prins, Siegel and Wilson (1982) themselves identified as unresolved for their Metropolis-style ('Monte Carlo') code optimizer — a stochastic search over meaning-preserving transformations, equipped with safe, conservative semantic verification, on the FPS Array Processor APAL system as described in the report (modeled by its value-object machine description; the extinct hardware is reachable today only through emulation):

  1. Verification precision under safety. The semantic checks must remain safe — they never accept a meaning-changing transformation — and therefore conservatively reject some genuinely equivalent transformations. Quantify the practical rate of such false negatives on realistic code, and reduce it without compromising safety.

  2. Convergence and computer time. The convergence properties and the amount of computer time required by the optimizer are unknown; the choice of metric, the annealing/acceptance schedule, and heuristic guidance for where to attempt transformations currently reflect intuition and must be empirically tuned. Provide systematic methods to select or adapt these parameters, and to predict the expected time to reach a good solution.

  3. Precise yet safe address/value resolution. Verification subtasks such as the upward (backward) computation of base-register values for address resolution can fail, forcing conservative over-approximation. Design more precise yet safe address/value-resolution procedures that remain tractable across large, changing programs.

  4. Complete the T6 transformation. The T6 transformation — moving a primitive group across cycles and control-flow paths — is specified conceptually but not implemented. Develop and integrate the semantic verification and cross-path control-flow movement needed for a correct and efficient T6 implementation and its integration with the existing transformation set.

  5. Resource bounds for tracking. The space and time behavior of the forward/backward tracking procedures (IS_NEEDED and EQUIVALENT) on large codes is unspecified. Establish space/time bounds for them, and strategies for graceful termination or incremental refinement when tracking would exceed a resource budget.

  6. Guidance versus robustness. Determine how much deterministic heuristic focusing of the stochastic search (to reduce wasted transformations) can be incorporated before the nondeterminism that gives the method its robustness across diverse inputs is lost; this design question must be answered empirically.

References

  1. Dean Jacobs, Jan Prins, Peter Siegel, Kenneth Wilson, 'Monte Carlo techniques in code optimization', ACM SIGMICRO Newsletter 13(4):143–148 (Proceedings of the 15th Annual Workshop on Microprogramming, MICRO 15), 1982. DOI: 10.1145/1014194.800944, https://doi.org/10.1145/1014194.800944
  2. Joseph A. Fisher, 'Very Long Instruction Word architectures and the ELI-512', Proceedings of the 10th Annual International Symposium on Computer Architecture (ISCA '83), pp. 140–150, 1983. DOI: 10.1145/800046.801649, https://doi.org/10.1145/800046.801649
  3. S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, 'Optimization by Simulated Annealing', Science 220:671–680, 1983. DOI: 10.1126/science.220.4598.671, https://doi.org/10.1126/science.220.4598.671
  4. A. De Gloria, P. Faraboschi, 'A Boltzmann Machine approach to code optimization', Parallel Computing 17(9):969–982, 1991. DOI: 10.1016/S0167-8191(05)80042-0, https://doi.org/10.1016/S0167-8191(05)80042-0
  5. A. De Gloria, P. Faraboschi, M. Olivieri, 'A Non-deterministic Scheduler For A Software Pipelining Compiler', Proceedings of the 25th Annual International Symposium on Microarchitecture (MICRO 25), pp. 41–44, 1992. DOI: 10.1109/MICRO.1992.696998, https://doi.org/10.1109/MICRO.1992.696998
  6. Steven J. Beaty, 'Genetic Algorithms versus Tabu Search for Instruction Scheduling', in Artificial Neural Nets and Genetic Algorithms, Springer, pp. 496–501, 1993. DOI: 10.1007/978-3-7091-7533-0_72, https://doi.org/10.1007/978-3-7091-7533-0_72
  7. Kenneth G. Wilson, 'Universities and the future of high-performance computing technology', Proceedings of the National Computer Conference (AFIPS '83), p. 469, 1983. DOI: 10.1145/1500676.1500735, https://doi.org/10.1145/1500676.1500735
  8. A. Pnueli, M. Siegel, E. Singerman, 'Translation Validation', Tools and Algorithms for the Construction and Analysis of Systems (TACAS '98), Lecture Notes in Computer Science, Springer, pp. 151–166, 1998. DOI: 10.1007/bfb0054170, https://doi.org/10.1007/bfb0054170
  9. Eric Schkufza, Rahul Sharma, Alex Aiken, 'Stochastic superoptimization', Proceedings of the 18th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2013), pp. 305–316, 2013. DOI: 10.1145/2451116.2451150, https://doi.org/10.1145/2451116.2451150 (also arXiv:1211.0557, https://arxiv.org/abs/1211.0557)
  10. Rahul Sharma, Eric Schkufza, Berkeley Churchill, Alex Aiken, 'Conditionally correct superoptimization', Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2015), pp. 147–162, 2015. DOI: 10.1145/2814270.2814278, https://doi.org/10.1145/2814270.2814278
  11. Rudy Bunel, Alban Desmaison, M. Pawan Kumar, Philip H.S. Torr, Pushmeet Kohli, 'Learning to superoptimize programs', International Conference on Learning Representations (ICLR 2017), 2017. arXiv:1611.01787, https://arxiv.org/abs/1611.01787
  12. Andrea Lecchini-Visintini, John Lygeros, Jan M. Maciejowski, 'Stochastic Optimization on Continuous Domains With Finite-Time Guarantees by Markov Chain Monte Carlo Methods', IEEE Transactions on Automatic Control 55(12):2858–2863, 2010. DOI: 10.1109/TAC.2010.2078170, https://doi.org/10.1109/TAC.2010.2078170