Binary code analysis is widely used to help assess a program’s correctness, performance, and provenance. Binary analysis applications often construct control flow graphs, analyze data flow, and use debugging information to understand how machine code relates to source lines, inlined functions, and data types. To date, binary analysis has been single-threaded, which is too slow for convenient use in performance tuning workflows where it is used to help attribute performance to complex applications with large binaries.
This paper describes our design and implementation for accelerating the task of constructing control flow graphs (CFGs) from binaries by using multithreading. Prior research focuses on algorithms for analysis of challenging code constructs encountered while constructing CFGs, including functions sharing code, jump tables, non-returning functions, and tail calls. These algorithms are described from a program analysis perspective and are not suitable for direct parallel implementation. We abstract the task of constructing CFGs as repeated applications of several core CFG operations that include creating functions, basic blocks, and edges. We then derive CFG operation dependency, commutativity, and monotonicity. These operation properties guide our design of a new parallel analysis for constructing CFGs. Using 64 threads, we achieved as much as 25$\times$ speedup for constructing CFGs and 8$\times$ for a performance analysis tool that leverages our new analysis to recover program structure.
Mon 1 MarDisplayed time zone: Eastern Time (US & Canada) change
11:10 - 12:10
|Synthesizing Optimal Collective Algorithms|
Zixian Cai Australian National University, Zhengyang Liu University of Utah, Saeed Maleki Microsoft Research, Madan Musuvathi Microsoft Research, Todd Mytkowicz Microsoft Research, Jacob Nelson Microsoft Research, Olli Saarikivi Microsoft Research, RedmondLink to publication
|Parallel Binary Code Analysis|
Xiaozhu Meng Rice University, Jonathon Anderson Rice University, John Mellor-Crummey Rice University, Mark W. Krentel Rice University, Barton P. Miller University of Wisconsin - Madison, Srđan Milaković Rice UniversityLink to publication
|Compiler Support for Near Data Computing|
Mahmut Taylan Kandemir Penn State University, USA, Jihyun Ryoo Penn State University, USA, Xulong Tang University of Pittsburgh, USA, Mustafa Karakoy TUBITAK-BILGEM, TurkeyLink to publication
|Scaling Implicit Parallelism via Dynamic Control Replication|
Michael Bauer NVIDIA, Wonchan Lee NVIDIA, Elliott Slaughter SLAC National Accelerator Laboratory, Zhihao Jia Carnegie Mellon University, Mario Di Renzo Sapienza University of Rome, Manolis Papadakis NVIDIA, Galen Shipman Los Alamos National Laboratory, Patrick McCormick Los Alamos National Laboratory, Michael Garland NVIDIA, Alex Aiken Stanford UniveristyLink to publication