求解带有预放置矩形块的布局问题的启发式算法

摘要

在超大规模集成电路设计中,一些特别重要的部件,如RAM、ROM、CPU等经常被优先放置,而其他元件则被两两互不重叠地放置在芯片的剩余区域.这类问题能被形式化为带有预放置矩形块的布局问题.基于占角和最大穴度优先的放置策略,为该问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC得到了验证.