Masters Thesis: Measurement-driven DSP Superoptimization

Join our Team

About this opportunity:

The Ericsson Many Core Architecture (EMCA) is an in-house developed ASIC architecture designed for computation in mobile networks. Among its components is a custom digital signal processor (DSP) core, for which we maintain a custom compiler. Applications running on the EMCA DSP have strict real-time constraints and limited hardware resources, making the performance and memory footprint of compiler-generated code very important. 

Superoptimization takes fragments of the code being compiled and searches for the cheapest fragment that computes the same result. The candidates come from a search over possible programs, and a Satisfiability Modulo Theories (SMT) solver such as Z3 proves equivalence before one is accepted. A notable example is Souper, which works on LLVM Intermediate Representation (IR). 

A previous thesis project adapted Souper  to our tool chain and ran it offline over DSP application code. That work is the starting point for this project: a superoptimizer that already runs against our EMCA DSP target. One limiting factor in that project was the cost model, and this follow-up explores an alternative. Souper decides which fragment is cheapest from a table of fixed per-operation costs. Such a table can only guess, because the chosen fragment then passes through the rest of the compiler and is transformed further on its way to machine code. On a Very Long Instruction Word (VLIW) DSP, the gap is wide enough that Souper both accepts rewrites that are slower on the hardware and discards real improvements.

What you will do:

1. Survey the state of the art in superoptimization.
2. Use the compiler back-end as the cost model. Instead of scoring candidates using a static instruction-cost table, whose entries provide estimated costs for individual instructions, compile them for the target DSP and measure properties of the generated code. This allows the search to be guided by the compiler's own cycle and size estimates. Compiling every candidate makes the search considerably slower than using a table, so a central question is whether the better cost information is worth that price.
3. Expand the set of DSP instructions the superoptimizer can reason about. Examples of native DSP operations are multiply-accumulate and bit-field operations, which the compiler exposes through intrinsics. This should enable the superoptimizer to discover efficient uses of DSP-specific instructions that are not represented by more general operations.
4. Evaluate offline on production DSP code. The superoptimizer is a tool for compiler developers and is not meant to run inside the compiler, so the deliverable is a set of suggested optimizations to build into the production compiler. The evaluation will consider performance improvements and memory footprint reductions. 

The project is hands-on: your work can directly influence our production compiler and DSP program performance. You will work with SMT-based reasoning about programs, target-specific compiler passes, a VLIW instruction set, and real hardware constraints.

The skills you bring: 

This is a technically advanced thesis project suitable for: 

• Master’s student in Computer Science or Computer Engineering.
• You have experience in C/C++ and enjoy working with low-level programming, compilers, and assembly-level optimization. 
• You have (or are willing to develop) skills in LLVM development and formal methods.