sampsyo
commented
5 years ago Sounds good! It seems important to put some serious thought into that cost model—it will require a nuanced idea of the imaginary machine you're running on to convincingly argue about exactly how much cheaper a scalar instruction should be than a vector instruction, for example. Maybe you want to estimate the number of execution cycles on a notional machine?
I plan to implement divergence analysis and optimize instruction streams based on this. With knowledge of redundant lanes/PEs, vector instructions will be replaced with scalar ones and branch divergences can be know a priori and be replaced with non-divergent branches (i.e. PTX bra.uni) . These are important in SIMD and SIMT execution models.
I will implement divergence analysis using a forward dataflow analysis pass following algorithms in literature. Once the variables have been determined, we can do peephole optimizations to replace instructions with more efficient instructions. Additional vector instructions will also be added to the interpreter to express more programs, building upon my previous work in Project 1.
The performance of the optimized code can be estimated by assigning a cost to each instruction. Scalar instructions will be cheaper than vector instructions and known convergent branches will be cheaper than statically unknown branches.