1 PeF P oissons E quation Based Large-Scale Fixed-Outline F loorplanning

2025-05-01 0 0 1.1MB 14 页 10玖币

侵权投诉

PeF: Poisson’s Equation Based Large-Scale

Fixed-Outline Floorplanning

Ximeng Li, Keyu Peng, Fuxing Huang and Wenxing Zhu

Abstract—Floorplanning is the ﬁrst stage of VLSI physical

design. An effective ﬂoorplanning engine deﬁnitely has positive

impact on chip design speed, quality and performance. In this

paper, we present a novel mathematical model to characterize

non-overlapping of modules, and propose a ﬂat ﬁxed-outline

ﬂoorplanning algorithm based on the VLSI global placement

approach using Poisson’s equation. The algorithm consists of

global ﬂoorplanning and legalization phases. In global ﬂoor-

planning, we redeﬁne the potential energy of each module

based on the novel mathematical model for characterizing non-

overlapping of modules and an analytical solution of Poisson’s

equation. In this scheme, the widths of soft modules appear as

variables in the energy function and can be optimized. Moreover,

we design a fast approximate computation scheme for partial

derivatives of the potential energy. In legalization, based on the

deﬁned horizontal and vertical constraint graphs, we eliminate

overlaps between modules remained after global ﬂoorplanning,

by modifying relative positions of modules. Experiments on the

MCNC, GSRC, HB+ and ami49 x benchmarks show that, our

algorithm improves the average wirelength by at least 2% and

5% on small and large scale benchmarks with certain whitespace,

respectively, compared to state-of-the-art ﬂoorplanners.

Index Terms—Fixed-outline ﬂoorplanning, Global ﬂoorplan-

ning, Poisson’s equation, Legalization, Constraint graph.

I. INTRODUCTION

FLOORPLANNING is the ﬁrst stage of VLSI physical

design ﬂow. With widespread usage of IP cores and huge

number of cells integrated in modern chips, ﬂoorplanning

needs to handle hundreds or even thousands of circuit modules

within a ﬁxed-outline. Especially, some more complex issues

need to be considered during ﬂoorplanning, such as timing,

thermal, power and voltage-island [1], [2]. However, it is well

known that the fundamental ﬂoorplanning problem is NP-

hard. Hence designing a high performance algorithm for the

fundamental large-scale ﬂoorplanning is a challenge, which

will have an impact on the performance and yield of the ﬁnal

ICs. In this paper, we focus on designing a ﬂat analytical

engine for the ﬁxed-outline ﬂoorplanning.

Fixed-outline ﬂoorplanning can be described as placing a set

of rectangular modules into a ﬁxed rectangular area without

overlap, while minimizing the total wirelength among the

modules. Floorplanning usually includes two types of circuit

modules, hard modules and soft modules. The width and

height of a soft module can be changed within a certain range

meanwhile maintaining a certain area. So far, works for ﬁxed-

outline ﬂoorplanning can be divided into three categories:

The authors are with the Center for Discrete Mathematics and Theoretical

Computer Science, Fuzhou University, Fuzhou 350108, China (Corresponding

author: Wenxing Zhu, e-mail: wxzhu@fzu.edu.cn).

heuristic methods for small-scale problem, multilevel heuristic

methods for large-scale problem, and analytical approaches.

Heuristic methods for small-scale ﬁxed-outline ﬂoorplan-

ning problem ﬁrst adopt a ﬂoorplan representation, then use

heuristic algorithms to search for an optimal solution in the

representation space, and ﬁnally decode the optimal represen-

tation to the corresponding ﬂoorplan. Floorplan representation

method also determines the complexity of transforming a ﬂoor-

plan into its representation, and the complexity of decoding

a representation into its corresponding ﬂoorplan. Floorplan

representation methods can be summarized in Table I.

TABLE I

SUMMARY OF FLOORPLAN REPRESENTATIONS

Representation Solution Space Packing Time Flexibility

Normalized Polish Expression O(n!22.6n/n1.5)O(n)slicing

Corner Block List [3]O(n!23n)O(n)Mosaic

Twin Binary Sequence [4]O(n!23n/n1.5)O(n)Mosaic

O-tree [5]O(n!22n/n1.5)O(n)compacted

B*-tree [6]O(n!22n/n1.5)O(n)compacted

Corner Sequence [7]≤(n!)2O(n)compacted

Sequence Pair [8](n!)2O(n2)general

TCG-S [9](n!)2O(nlog n)general

ACG [10]O((n!)2)O(n2)general

In Table I, O-tree [5] and B*-tree [6] are two commonly

used ﬂoorplan representations, followed by the most preferred

simulated annealing algorithm. Parquet [11] used sequence

pair as the representation, on which a ﬂoorplan is also op-

timized using simulated annealing. Since the running time of

this kind of algorithms grows very fast with the problem scale,

they cannot be applied to large-scale ﬂoorplanning directly.

A methodology to cope with this issue is the multilevel

framework with the heuristic search methods.

The core idea of multilevel heuristic search methods is

reducing the size of solution space multilevelly by clustering

or partitioning, and thus can handle large-scale problem.

Clustering-based ﬂoorplanning methods, e.g., MB*-tree [12],

merge modules from the bottom to up, until the number of

modules is small enough, and then solve the ﬂoorplanning

problem. The solution is reﬁned in each level of de-clustering,

leading ﬁnally to a solution of the original problem. A dis-

advantage of clustering-based ﬂoorplanning is that, modules

cannot be clustered from a global perspective in the early

clustering stage, which limits the solution quality. Instead,

partitioning-based methods decompose the original large-scale

ﬂoorplanning problem into several small-scale sub-problems,

until they are small enough and solved directly. Finally,

solutions of sub-problems are merged and optimized level

by level, leading to a solution of the original problem. Capo

[13], DeFer [14], IMF [15] and QinFer [16] are state-of-the-

arXiv:2210.03293v1 [cs.AR] 7 Oct 2022

art partitioning-based ﬂoorplanning methods. Most of them

use hMetis [17] for the partitioning. Compared to clustering-

based ﬂoorplanning methods, partitioning-based ones can con-

sider wirelength information in the early ﬂoorplanning stage.

However, they cannot accurately calculate the wirelength in

the partitioning stage.

Since ﬂoorplanning is similar to the VLSI placement prob-

lem in some degree, a number of analytical ﬂoorplanning

methods have been proposed based on the frameworks of

VLSI placement approaches. They include Analytical [18], AR

[19], UFO [20] and F-FM [1], etc. Generally, these methods

analogously have the global ﬂoorplanning stage which deter-

mines “rough” positions of modules, and a legalization stage

which eliminates the overlaps between modules and deter-

mines the exact positions of all modules and the widths of soft

modules. Furthermore, combining with multilevel framework,

these analytical methods can solve large-scale ﬂoorplanning

problems well. Table II summarizes the global ﬂoorplanning

and legalization stages of the above methods, respectively.

TABLE II

SUMMARY OF ANALYTICAL FLOORPLANNING METHODS

method global ﬂoorplanning legalization

Analytical [18]bell-shaped smoothing

and Density control function pl2sp() in Parquet-4 [11]

F-FM [1]placement model

based on NTUplace [21]

gradual partition based on

position and area +ST-Tree [22]

Ref. [2]placement model

based on NTUplace [21]SAINT [23]

AR [19]Attractor-Repeller model SOCP based on relative position matrix

UFO [20] Push-Pull model SOCP based on constraint graph

Floorplanners Analytical [18], F-FM [1] and Ref. [2] use

density-control in the global ﬂoorplanning stage. In Analytical

[18], cell density is calculated according to the current posi-

tions and widths of modules, in which soft modules are treated

as hard ones. Then the density function is smoothed using the

bell-shaped function. During legalization, overlaps between

modules are removed using the function pl2sp() in Parquet-4

[11] to get a legal ﬂoorplan. Similarly, F-FM [1] and Ref. [2]

treat all soft modules as hard blocks, and use global placement

for global ﬂoorplanning. In legalization, F-FM [1] uses the

ST-tree [22] with the gradual partition based on positions and

areas of modules, and then adopts the simulated annealing

algorithm to optimize the positions and widths of modules.

As for the ﬂoorplanner in Ref. [2], SAINT [23] is used for

legalization. The main idea is using polygon to approximate

the curve of area of every soft module, and building an ILP

model to achieve legalization of modules.

Earlier ﬂoorplanners AR [19] and UFO [20] directly regard

all soft and hard modules as squares, and further abstract

them as circles. Then, Attractor-Repeller and Push-Pull models

are proposed for global ﬂoorplanning respectively. Both of

them use second-order cone programming (SOCP) to obtain

legal solutions in the legalization stage. The difference is that,

AR uses relative position matrix, while UFO uses constraint

graph. It must be remarked that solving SOCP is rather time-

consuming when the problem size is moderate or large.

Note that ﬂoorplanning problem contains hard and soft

modules. However, state-of-the-art analytical ﬂoorplanners

Analytical [18], F-FM [1] and Ref. [2] take soft modules

as hard ones in global ﬂoorplanning. Moreover, they must

be incorporated in the multilevel framework to handle large-

scale ﬂoorplanning problem. Apparently, these will affect the

solution quality.

In this paper, we focus on the fundamental ﬁxed-outline

ﬂoorplanning problem. This is because algorithms for ﬂoor-

planning with complex issues are extended from those for

the fundamental ﬂoorplanning. Notice that Poisson’s equation

based VLSI global placement methods [24], [25] do not use

multilevel framework. They are ﬂat while achieve state-of-

the-art results. In this paper, we will propose a high perfor-

mance ﬂoorplanning engine by extending this type of methods

to large-scale ﬁxed-outline ﬂoorplanning with hard and soft

modules.

To achieve this goal, we must not only consider optimizing

the shapes of soft modules in global ﬂoorplanning, but also

design a high performance legalization algorithm correspond-

ingly. Contributions of this paper are summarized as follows:

•We propose a novel mathematical model to characterize

non-overlapping of modules. Then under the concept

of electrostatic system [24], we redeﬁne the potential

energy of modules based on the analytical solution of

Poisson’s equation in [25]. This allows the widths of soft

modules to appear as variables in the established ﬁxed-

outline global ﬂoorplanning model, and the derivative

with respect to the widths of soft modules can be easily

obtained.

•We give a fast approximate computation scheme for the

partial derivative of the potential energy, and design a

ﬁxed-outline global ﬂoorplanning algorithm based on the

global placement method using Poisson’s equation.

•By deﬁning horizontal and vertical constraint graphs,

we present a fast legalization algorithm to remove over-

laps between modules after global ﬂoorplanning. The

algorithm modiﬁes relative positions of modules and

compresses the ﬂoorplan to obtain ﬁnally a legal solution.

•Within acceptable running time, our ﬂoorplanning algo-

rithm obtains better results on large-scale benchmarks.

The average wirelength is at least 5% less than state-

of-the-art multilevel heuristic search algorithms, and is at

least 8% less than state-of-the-art analytical ﬂoorplanning

algorithms. On small-scale benchmarks, it has similar

improvements.

The remainder of this paper is organized as follows. Section

II is the preliminaries. Section III proposes a novel math-

ematical model to characterize non-overlapping of modules,

gives our global ﬂoorplanning model based on Poisson’s

equation, and provides a fast computation scheme for the

partial derivatives. In Section IV, we detail our ﬁxed-outline

global ﬂoorplanning algorithm and legalization algorithm.

Experimental results and comparisons are presented in Section

V, and conclusion is summarized in Section VI.

II. PRELIMINARIES

This section presents the problem of ﬁxed-outline ﬂoorplan-

ning, introduces the wirelength model and principle of the

Poisson’s equation method for handling modules overlap in

VLSI global placement.

A. Fixed-outline Floorplanning Problem

The ﬂoorplanning area is a rectangle with four edges parallel

to the coordinate axes, with the lower left corner at the origin,

and upper right corner at (W, H). Let V=Vs∪Vhbe the

set of rectangular modules, where Vsand Vhrepresent the

sets of soft and hard modules, respectively. For each module

vi∈V, its width, height, area and the coordinate of the center

point are wi,hi,Aiand (xi, yi), respectively. For each module

vi∈Vs, the aspect ratio, calculated as the ratio of height to

width, is between ARl

iand ARu

i. Moreover, let Ebe the set

of nets ei,i= 1,2, . . . , m, for which W L(ei)is the half-

perimeter wirelength. Let W L(E) = Pei∈EW L(ei). Then

the ﬁxed-outline ﬂoorplanning problem can be described as

min W L(E)

s.t. overlap = 0

aspect ratio is suitable

all modules are within the ﬁxed-outline.

(1)

In this paper, the objective of model (1) adopts the LSE

(Log-Sum-Exp) wirelength function. Moreover, the ﬁrst con-

straint in (1) ensures that all modules do not overlap. The

second constraint means that the aspect ratio of every soft

module meets the upper and lower bounds. The third constraint

indicates that all modules are located within the ﬁxed-outline.

B. VLSI Global Placement Based on Poisson’s Equation

ePlace [24] is a representative VLSI global placement

method. In ePlace, each module viis regarded as a positively

charged particle with electric quantity qi, which is proportional

to its area Ai. Thus the placement problem is modeled as

a two-dimensional electrostatic system, in which the electric

potential ψ(x, y)and the electric ﬁeld ξ(x, y)satisfy that

ξ(x, y)=(ξx, ξy) = −∇ψ(x, y). ePlace [24] characterizes

ψ(x, y)as the solution of the Poisson’s equation











∇2ψ(x, y) = −ρ(x, y),(x, y)∈R, (2a)

n∇ψ(x, y) = 0,(x, y)∈∂R, (2b)

ZZR

ρ(x, y)dxdy=ZZR

ψ(x, y)dxdy= 0,(2c)

where Ris the rectangular placement area. Eq. (2a) is the

Poisson’s equation, ρ(x, y)is the charge density function

on R. Eq. (2b) is the Neumann boundary condition, where

∂Rand ˆ

nrepresent the boundary of area Rand the outer

normal vector of the boundary, respectively. Eq. (2c) is the

compatibility condition to ensure that the equation has a

unique solution.

The electric forces Fi=qiξ(xi, yi),i= 1,2, . . . , n,

guide the modules movement and henceforth reduce mod-

ules overlaps. Deﬁne the system potential energy N(V) =

Pvi∈VN(vi), where N(vi) = qiψ(vi)is the potential energy

of module vi. Then by ePlace [24], a necessary condition for

overlap = 0 is that the system potential energy N(V)is the

smallest. This allows to use the regularizing term N(V)to

transform the VLSI global placement problem into

min LSE(E) + λN(V)

s.t. all modules are in the placement area.(3)

Ref. [25] deﬁnes the density function

ρ(x, y) = X

vi∈V

ρi(x, y),(x, y)∈[0, W ]×[0, H],

ρi(x, y) = (1, if (x, y)∈Ri;

0, else,

(4)

where Ri=xi−wi

2, xi+wi

2×yi−hi

2, yi+hi

2, hi=

wi. Then by redeﬁning

ρ(x, y),ρ(x, y)−1

W H ZZR

ρ(x, y)dxdy,

Ref. [25] obtains an analytical solution of Eq. (2). The

truncated version is

ψ(x, y) =

u=0

p=0

aup cos uπ

Wxcos pπ

Hy,(5)

where Kis the truncation factor that controls the precision.

For fast global placement, assume that the placement area

is divided in to K×Kbins, and the density of each grid is

ˆρ(i, j) = X

vk∈V

Area(bini,j ∩Rk)

Area(bini,j ), i, j = 0,1, . . . , K −1.

(6)

By a similar redeﬁnition, Ref. [25] obtains an analytical

solution of Eq. (2), for which the truncated solution value at

(i+1

2, j +1

2)is

ψ(i, j) =

K−1

u,p=0

aup cos u(i+1

2)π

Kcos p(j+1

2)π

K.(7)

The coefﬁcient calculations for Eqs. (5) and (7) can be found

in [25].

III. GLOBAL FLOORPLANNING MODEL AND GRADIENT

CALCULATION

In this paper, the ﬁxed-outline ﬂoorplanning is decomposed

into two stages: global ﬂoorplanning and legalization. In global

ﬂoorplanning, partial overlaps between modules are allowed

and a “rough” ﬂoorplanning is built. In legalization, the over-

laps are eliminated and the ﬁnal legal ﬂoorplan is obtained.

To be able to optimize the shapes of soft modules in global

ﬂoorplanning, we propose in this section a novel mathematical

model to characterize non-overlapping of modules, and then

modify the VLSI global placement model (3) for ﬁxed-outline

global ﬂoorplanning. Based on the global ﬂoorplanning model,

we present a fast approximate scheme for calculating partial

derivatives of potential energy.

A. Global Floorplanning Model

First, we present a sufﬁcient and necessary condition for

non-overlapping of modules. According to Eq. (4), we can

prove the following results. The details will be clariﬁed in the

Appendix.

Lemma 1. Any two different modules viand vj∈Vare

non-overlapping if and only if RRRiρj(u, v)dudv= 0.

Let Area(Ri)be the area of module vi, we have

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1PeF:Poisson'sEquationBasedLarge-ScaleFixed-OutlineFloorplanningXimengLi,KeyuPeng,FuxingHuangandWenxingZhuAbstractFloorplanningistherststageofVLSIphysicaldesign.Aneffectiveoorplanningenginedenitelyhaspositiveimpactonchipdesignspeed,qualityandperformance.Inthispaper,wepresentanovelmathematicalmod...

展开>> 收起<<

1 PeF P oissons E quation Based Large-Scale Fixed-Outline F loorplanning.pdf

共14页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 PeF P oissons E quation Based Large-Scale Fixed-Outline F loorplanning

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: