An integer programming approach to optimal basic block instruction scheduling for single-issue processors

详细信息    查看全文

• 作者：Michael Jü ; nger ^{mjuenger@informatik.uni-koeln.de" class="auth_mail" title="E-mail the corresponding author} ; Sven Mallach ; ^{mallach@informatik.uni-koeln.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：68M07 ; 68M20 ; 68N20 ; 68W01 ; 90C10 ; 90C27
• 刊名：Discrete Optimization
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：22
• 期：part_PA
• 页码：37-65
• 全文大小：935 K

文摘

We present a novel integer programming formulation for basic block instruction scheduling on single-issue processors. The problem can be considered as a very general sequential task scheduling problem with delayed precedence constraints. Our model is based on the linear ordering problem and has, in contrast to the last IP model proposed, numbers of variables and constraints that are strongly polynomial in the instance size. Combined with improved preprocessing techniques and given a time limit of ten minutes of CPU and system time, our branch-and-cut implementation is capable to solve all but eleven of the 369,861 basic blocks of the SPEC 2000 integer and floating point benchmarks to proven optimality. This is competitive to the current state-of-the art constraint programming approach that has also been evaluated on this test suite.