WPI - Computer Science Department, MS Thesis Presentation Ronghan Che "Accelerating Binary Function Matching: A Study of Three GPU-Based Approaches"
10:00 a.m. to 11:00 a.m.
Ronghan Che
MS Student
WPI – Computer Science Department
Tuesday, December 10, 2024
Time: 10:00 a.m. – 11:00 a.m.
Location: Fuller Labs 141
Advisor: Prof. Robert Walls
Reader: Prof. George Heineman
Abstract :
Binary function matching is used in tasks such as code optimization and security in embedded systems. This thesis focuses on accelerating function matching algorithms by implementing GPU-based dynamic programming approaches to improve computational performance. We build upon Libdec0de, a function matching optimizer designed to enhance accuracy by leveraging contextual information. Libdec0de extends the traditional Viterbi algorithm by not only identifying the most likely sequence of function matches but also retaining the entire rank of candidate functions at each step.
We developed three GPU-accelerated implementations. The Naïve Approach serves as a baseline, where each thread handles all edges leading to a node in a column, and all thread blocks process columns sequentially. The Parallel Estimation Approach divides the computation into multiple segments that can be processed concurrently. The Fine-Grained Approach achieves greater parallelism by assigning each thread to compute a single edge, with thread blocks managing all edges leading to a node in a column.
Our experimental result demonstrate performance improvements with GPU acceleration. The Naïve Approach, serving as a baseline, achieves faster execution times than CPU implementation. Both the Parallel Estimation and Fine-Grained approaches further enhance performance, with the Parallel Estimation Approach excelling in scalability for deeper graphs with fewer nodes per column, albeit with accuracy trade-offs. The Fine-Grained Approach maintains high accuracy while achieving speedups, particularly in scenarios with larger number of nodes per column. These findings highlight the potential of GPU acceleration in advancing the efficiency of binary function matching algorithms.
-----