Computer Science Events
[PAST EVENT] Shasha Wen, Computer Science - Ph.D. Dissertation Proposal
Abstract:
Complex code bases with several layers of abstractions have abundant inefficiencies that affect the performance. These inefficiencies arise due to various causes such as developers? inattention to performance, inappropriate choice of algorithms and inefficient code generation among others. In the operation level, redundant computation is a severe type of inefficiency where the same operator is operated on the same operands. In the data level, value redundancy is a kind of inefficiency where the same values are repeatedly computed, stored, or retrieved over the course of execution. To eliminate the redundancies, lots of work has been done during compiling phase. However, not all redundancies can be easily detected or eliminated with compiler optimization passes due to aliasing, limited optimization scopes, and insensitivity to input and execution contexts act as severe deterrents to static program analysis.
We develop a dynamic profiler to pinpoint and quantify redundant computations in an execution. Our methodology?Runtime Value Numbering (RVN)?is based on the classical value numbering technique but works at runtime instead of compile time. RVN works on unmodified, fully-optimized binaries.
Microscopic observation of whole executions at instruction- and operand-level granularity breaks down abstractions and helps recognize redundancies that masquerade in complex programs. We then developed REDSPY?a fine-grained profiler to pinpoint and quantify value redundancies in program executions. Value redundancy may happen over time at same locations or in adjacent locations, and thus it has temporal and spatial locality. REDSPY identifies both temporal and spatial value locality. Furthermore, REDSPY is capable of identifying values that are approxi- mately the same, enabling optimization opportunities in HPC codes that often use floating point computations.
RVN and REDSPY both provide insightful optimization guidance by apportioning redundancies to their provenance?source lines and full calling contexts. We apply RVN and REDSPY on programs that were optimization targets for decades and guided by the tools, we were able to eliminate redundancies that resulted in significant speedups.
Bio:
Shasha Wen is a Ph.D. candidate at William & Mary. She received her B.S. and M.S. degree at Computer Science from Beihang University. She works on performance profiling area with her PhD advisor, Dr. Xu Liu.