Optimal Offset Assignment
The offset assignment problem reorders variables stored in memory to minimize their address computation overhead. This problem is central in the compilation of signal processing programs where address computation can account for as much as a third of their size. This talk presents an integer programming approach to the general version of the offset assignment problem. The approach combines two state-of-the-art methods to deliver, for the first time, optimal solutions to 98% of the instances of the OffsetStone benchmark. The availability of optimal solutions for non-trivial problem instances enables the first comprehensive evaluation of the quality of several state-of-the-art heuristics.