Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 12 of 12 for “"Equality saturation"”.
-
Practical and Flexible Equality Saturation
… difficult decision. A recent technique called equality saturation mitigates this “rewrite choice” issue by allowing many rewrites to apply simultaneously. Despite its promise, the technique’s applicability has been limited by lack of flexibility and poor scalability. This thesis offers …
-
Dynamic set reasoning: Specifying and optimizing monitor encodings
… also present a set of MLTL rewrite rules and use equality saturation to optimize MLTL monitor encodings automatically. After applying equality saturation to a set of human-authored MLTL formulas, our experimental evaluation found a ~35% average monitor size reduction.
-
CHASE OPTIMAL AT SPEED: COMBINATORIAL PROBLEM SOLVING IN COMPUTING SYSTEMS
Equality saturation provides a fundamentally different methodology from traditional phase-ordered optimization: instead of rewriting a program or circuit in-place, it accumulates many equivalent representations in an e-graph and delays commitment to a specific form until an explicit extraction …
-
E-graphs modulo theories - with applications to associative-commutative operators
… theorem proving which provide the basis for equality saturation, a method to automatically derive equational consequences from a starting set of terms, equations, and identities. E-graphs have generated a lot of interest since the publication of the Egg paper by Willsey et al. [23], which …
-
Oatlog: A high-performance e-graph engine
… as the phase ordering problem. This motivates equality saturation, a technique in which the compiler compactly represents many program variants using e-graphs and later extracts the optimal representation using a global profitability heuristic. Equality saturation can improve code quality while …
-
Programming Language Tools and Techniques for Computational Fabrication
… by recovering latent structure. An equality saturation based second decompilation phase discovers even high-level representations using dynamic rewrites and inverse transformations. A second application of dynamic rewrites in the domain of carpentry shows wider applicability of this …
-
EXTENDING DIOSPYROS AUTO-VECTORIZATION TO LLVM
… the Diospyros project to apply a search-based equality saturation method to find vector instructions. Results show that the Diospyros LLVM pass generates vector code with good runtime performance on stencil and convolution kernels, but poor results on other kernels indicate future work is …
-
Towards heterogeneity-aware automatic optimization of time-critical systems via graph machine learning
… our novel code-to-graph representation based on equality saturation, which outperforms state-of-the-art methods at estimating execution time. Third, we show how our 150M+ instances heterogeneity-aware dataset was built. Lastly, we redesign a graph-level embedding algorithm, making it converge …
-
Generation of Compiler Backends from Formal Models of Hardware
… two case studies: first, Glenside, which uses equality saturation to increase the 3LA compiler’s ability to offload operations to machine learning accelerators, and second, Lakeroad, a technology mapper for FPGAs which uses program synthesis and semanticsextracted from Verilog to map hardware …
-
Lightweight Formal Methods for Correct, Efficient Systems Programming
… combines an efficient term-rewriting strategy, equality saturation, with translation validation to find correct, fast vectorizations for specialized linear algebra tasks on digital signal processors. The Kani verifier for Rust leverages compiler invariants to improve the performance of …
-
A domain-extensible compiler with controllable automation of optimisations
… contribution is to introduce sketch-guided equality saturation, a semiautomated technique that allows performance engineers to guide program rewriting by specifying rewrite goals as sketches: program patterns that leave details unspecified. We evaluate this approach by applying 7 realistic …
-
Learning-Assisted Techniques for Agile Arithmetic Design on FPGAs
… I introduce IMpress, a framework that leverages equality saturation to automatically produce a wide range of equivalent integer multiplication expressions corresponding to various hardware implementations and costs. IMpress is based on a learning-assisted cost model to address the difficulty in …