Home Events AI-based Optimisation Seminar Series 30 Mar 2022


Mar 30 2022


4:00 pm - 5:00 pm



AI-based Optimisation Seminar Series 30 Mar 2022

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.


ZOOM Meeting ID: 873 1557 5255; Password: 778635

More Info

Zoom Link

The event is finished.


Mar 30 2022

Advancing an industry-ready optimisation toolkit, while training a new generation of industry practitioners and over 120 young researchers, who will vanguard a highly skilled workforce of change agents for industrial transformation.

Monash University
Clayton, Victoria, 3080

University of Melbourne
Parkville, Victoria, 3010

© 2021 ARC Industrial Transformation Training Centre in Optimisation Technologies, Integrated Methodologies and Applications (OPTIMA)