W&M Featured Events
[PAST EVENT] Ruiqin Tian, Computer Science - Dissertation Proposal [Zoom]
Abstract:
Compiler optimization is a long-standing research field that enhances program performance with a set of rigorous code analysis and transformation. Traditional compiler optimization focuses on general programs or program structures without considering too much high-level application operation or data structure knowledge. In this thesis, we claim that an integrated view of the application and compiler
is helpful to further improve program performance. Particularly, we study such integrated optimization opportunities for three kinds of applications: irregular tree-based query processing systems such as B+ tree, security enhancement such as buffer overflow protection, and tensor/matrix-based linear algebra computation.
B+ tree is widely used in many applications, such as file systems and databases. Improving the performance of the B+ tree query processing system is important to these applications. Latch-free B+ tree query processing is efficient since the queries are processed in small batches and no locks are used. But in order to avoid long latency, the batch size can not be very large. However, the emerging modern
processors provide opportunities to process larger batches in parallel with acceptable latency. From studying the real data, we find that there are lots of redundant and unnecessary queries especially when the real data is highly skewed. We propose a query sequence transformation framework Qtrans to reduce the redundancies in queries by applying classic data-flow analysis to queries. To further confirm
the effectiveness, we integrate Qtrans to an existing BSP-based B+ tree query processing system, PALM tree. The evaluations show that the throughput can be improved up to 16X.
Heap buffer overflows are still top vulnerabilities in C/C++ programs. The most common approach is to check overflows before every memory access. However, even the state-of-the-art of this approach incurs 40% performance overhead. By analyzing dozens of bugs, we find that all heap overflows are related to arrays. This observation gives us an opportunity to reduce the overhead by only checking the array-related memory accesses. We propose Prober to automatically detect and protect array related heap objects. Prober is composed of Prober-Static and Prober-Dynamic. Prober-Static can correctly identify and instrument the array-related allocations, Prober-Dynamic can protect the objects in runtime. In this thesis, our contributions lie on the Prober-Static side. The key challenge is to correctly identify the array related allocations, i.e. no false-negative and no false-positive. We propose a hybrid method. Some objects can be identified as array-related (or not) by static analysis. For the remaining ones, we instrument the basic allocation type size statically and then determine the real allocation size in runtime. The allocation is array-related if allocated memory can hold multiple objects. The evaluations show Prober-Static is
effective.
Tensor algebra is widely used in many applications, such as scientific computation, machine learning, data analytics. The data is usually sparse in these applications. Improving the performance of sparse tensor algebra is still challenging. Existing works either target some specific hardware platforms or specific tensor operations. We design and build a high-performance sparse tensor algebra compiler to support varied sparse tensor formats and multiple hardware platforms. In order to represent the sparse tensors in a more uniform way, we propose a set of format attributes and propose an internal storage format for the sparse tensors based on the format attributes. We then propose a code generation algorithm to automatically generate the computation kernel code. Our prototype system shows comparable performance compared with the state-of-the-art sparse tensor algebra compiler system, however, supports a broader spectrum of architectures.
Bio:
Ruiqin Tian has been working on her Ph.D. degree in the Department of Computer Science at William & Mary since Fall 2015. Her research interests are compiler optimizations for high-performance computing, compiler analysis, and runtime optimizations. Her Ph.D. research has been published in CGO 2019, ASE 2020, and LCPC 2020. She received her B.Eng degree from Northeastern Petroleum University in 2012 and an M.Sc degree from the University of Chinese Academy of Sciences in 2015. She has been working as a Ph.D. research intern at Pacific Northwest National Lab since Feb 2020.