<p>Floorplanning is one of the most critical steps in the very large-scale integration (VLSI) physical design flow. It directly influences the performance, power, and area of high-performance chips. In computational science, floorplanning is a widely studied NP-hard problem. It requires generating a non-overlapping placement, i.e., a floorplan, for a set of circuit blocks interconnected by nets, each of which connects a subset of the blocks. The objective is to minimize the bounding box area of the floorplan and the total half-perimeter wirelength (HPWL) of the nets. This paper presents a reduction framework for solving the floorplanning problem, which reformulates it into a series of fixed-width floorplanning subproblems for systematic exploration and optimization. To solve each subproblem, we propose an improved beam search algorithm (IBSA) that integrates a heuristic construction guided by a combined ranking of area and wirelength scores. To balance local exploitation and global exploration in the beam search process, we adopt an adaptive hierarchical evaluation paradigm where the granularity of evaluation varies from local, look-ahead, to global views. Extensive experiments on the well-studied MCNC and GSRC benchmark suites show that, in the area-only setting, IBSA establishes new best-known upper bounds in terms of floorplan area. Under joint optimization of area and wirelength, IBSA produces smaller areas at comparable HPWL than the state-of-the-art floorplanners. Moreover, IBSA shows competitive runtime performance on the tested instances.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A reduction framework with an improved beam search algorithm for non-slicing VLSI floorplanning

  • Canhui Luo,
  • Yaozhong Zhao,
  • Yan Li,
  • Zhouxing Su,
  • Qingyun Zhang,
  • Junwen Ding,
  • Zhipeng Lü

摘要

Floorplanning is one of the most critical steps in the very large-scale integration (VLSI) physical design flow. It directly influences the performance, power, and area of high-performance chips. In computational science, floorplanning is a widely studied NP-hard problem. It requires generating a non-overlapping placement, i.e., a floorplan, for a set of circuit blocks interconnected by nets, each of which connects a subset of the blocks. The objective is to minimize the bounding box area of the floorplan and the total half-perimeter wirelength (HPWL) of the nets. This paper presents a reduction framework for solving the floorplanning problem, which reformulates it into a series of fixed-width floorplanning subproblems for systematic exploration and optimization. To solve each subproblem, we propose an improved beam search algorithm (IBSA) that integrates a heuristic construction guided by a combined ranking of area and wirelength scores. To balance local exploitation and global exploration in the beam search process, we adopt an adaptive hierarchical evaluation paradigm where the granularity of evaluation varies from local, look-ahead, to global views. Extensive experiments on the well-studied MCNC and GSRC benchmark suites show that, in the area-only setting, IBSA establishes new best-known upper bounds in terms of floorplan area. Under joint optimization of area and wirelength, IBSA produces smaller areas at comparable HPWL than the state-of-the-art floorplanners. Moreover, IBSA shows competitive runtime performance on the tested instances.