Speaker: Assoc. Prof. Julian Mestre, University of Sydney

Title: Theoretical Foundations of Profile Guided Binary Optimization

Synopsis: Profile-guided binary optimization (PGO) is an effective technique in modern compiles to improve performance by optimizing how binary code is laid out in memory. At a very high level, the idea is to collect information about typical executions and then use this information to reorder how code blocks are laid out in memory to minimize instruction cache misses, which in turn translates into running time performance gains. Given a graph G=(V, E) where vertices represent blocks of code and edges represent jumps, the objective is to find an ordering of V leading to fast executions. Ext-TSP is an objective function over vertex orderings that has been empirically shown to be well correlated with performance gain of the reordered binary. The problem generalizes the classical MAX-TSP objective and the maximum bandwidth-bounded subgraph problem. We show that Ext-TSP is APX-hard to approximate in general, and we give a (k + 1)-approximation algorithm for general graphs and a PTAS for some sparse graph classes such as planar or treewidth-bounded graphs. Interestingly, the problem remains challenging even on very simple graph classes; indeed, there is no exact n^{o(k)} time algorithm for trees unless the ETH fails. We complement this negative result with an exact in n^{O(k)} time algorithm for trees. This is joint work with S. Pupyrev and S. W. Umboh.

Bio: Julian is an Associate Professor at the School of Computer Science at the University of Sydney and a Research Scientist at Meta. He is broadly interested in the design and analysis of efficient algorithms for combinatorial optimization problems such as covering, scheduling, routing and matching problems.

WED 30 MAR 4 PM – 5 PM AEST

ZOOM Meeting ID: 873 1557 5255; Password: 778635