Net Separation-Oriented Printed Circuit Board Placement via Margin Maximization Chung-Kuan Cheng Chia-Tung Ho and Chester Holtz ckcheng c2ho chholtzeng.ucsd.edu

2025-05-02 0 0 1.06MB 6 页 10玖币

侵权投诉

Net Separation-Oriented Printed Circuit Board Placement via Margin Maximization

Chung-Kuan Cheng Chia-Tung Ho and Chester Holtz∗

{ckcheng, c2ho, chholtz}@eng.ucsd.edu

Department of Computer Science and Engineering

University of California San Diego

La Jolla, CA, 92037

Abstract— Packaging has become a crucial process due to the

paradigm shift of More than Moore. Addressing manufacturing

and yield issues is a signiﬁcant challenge for modern layout

algorithms.

We propose to use printed circuit board (PCB) placement as

a benchmark for the packaging problem. A maximum-margin

formulation is devised to improve the separation between nets.

Our framework includes seed layout proposals, a coordinate

descent-based procedure to optimize routability, and a mixed-

integer linear programming method to legalize the layout. We

perform an extensive study with 14 PCB designs and an open-

source router. We show that the placements produced by NS-

place improve routed wirelength by up to 25%, reduce the

number of vias by up to 50%, and reduce the number of DRVs by

79% compared to manual and wirelength-minimal placements.

I. INTRODUCTION

Packaging technology continues to advance from Printed

Circuit Boards, Flip-Chip, Integrated Fan-Out (InFO), Chip-

on-Wafer-on-Substrate (CoWoS) [1], Integrated Fan-Out

(InFO) [2], to System-on-Integrated-Circuit (SoIC) [3] for

More than Moore. However, the integration of the packages

encounters signiﬁcant manufacturability and yield issues due

to components with arbitrary shape, non-Manhattan routing

directions, vias of larger than routing track pitches, high

resistance, and/or reliability problems. In this paper, we use

Printed Circuit Board placement as a test vehicle to improve

manufacturability and yield. We separate nets in 2D space to

minimize net crossings, and encourage same layer routing.

Our goal is to minimize post-route design rule violations, and

reduce via usage. We additionally expect a reduction in the

routed metal length.

The PCB placement problem exhibits additional challenges

compared to Integrated Chip (IC) placement including arbi-

trary component shapes, board boundaries, multiple layers,

and routing constraints. Conventional analytical IC placers

[4] suffer from several key issues which prevent conver-

gence to good—or even reasonable—solutions (with respect

to wirelength and routability): (1) The vanilla RePlace [4]

implementation fails to ﬁnd good solutions for multi-layer

designs with diversely sized components. (2) The rate of

convergence of the algorithm is dependent on design-speciﬁc

parameters—e.g. ﬁller cells and anchor weights.

In this work, we propose and apply a gradient descent-

based algorithm to optimize wirelength, component density,

*Corresponding author

and routability and a mixed-integer linear program (MILP)

for local legalization. The computational bottleneck introduced

by the MILP is addressed by integrating global relative posi-

tioning constraints derived from the gradient-based placement

stage. Furthermore, our framework involves very few design-

dependent parameters. This allows our framework to be gen-

erally applied to a variety of designs without a costly tuning

stage.

A. Contribution

Our contributions can be summarized as follows:

1) We propose the NS-Place framework for PCB layout

which minimizes net congestion using a support vector

machine-like formulation and performs legalization by

solving a congestion-aware MILP.

2) We demonstrate that the routed placements produced by

our framework have fewer design rule violations and

vias, and shorter total metal length compared to manual

placements.

In section II, we review previous work. In section III, we

describe our routability objective. The NS-Place placement

framework, including initialization and the MILP-based le-

galizer is described in Section IV. In section V, we present

experimental results on real PCB testcases. We conclude in

section VI.

II. RELATED WORK

In this section we review the previous work with respect to

cost and congestion-driven placement and PCB layout.

A. Cost-driven placement

Conventional global placement strategies for ICs seek to

minimize wirelength subject to density constraints. Density

constraints are typically integrated with the objective to yield

an unconstrained relaxation (e.g. as in [4]):

min

x,y (X

e=(i,j)∈E

W l(e;x, y) + λD(x, y)) (1)

where W l(·;·)is a function that takes a net instance eas

input and returns the cumulative wirelength„ and D(·)is a

density penalty. In the context of IC layout, the wirelength of

a net is commonly modelled as the half-perimeter wirelength

(HPWL) or a smooth alternative and Dis a smooth density [5].

Overlap constraints are typically satisﬁed over the placement

process by gradually increasing the weight λ, at the cost of

increased wirelength. The current state-of-the-art IC placement

algorithms [5], [4] solve Problem 1 in this manner. We adopt

a similar formulation for PCB placement.

arXiv:2210.14259v1 [cs.CG] 25 Oct 2022

B. Congestion-driven Placement

A typical method of estimating routing demand is to con-

sider pin or feasible routed-wire density [6]. Other methods

include applying Rent’s rule [7], or more sophisticated routing

models; for example relying on the construction of rectilinear

Steiner trees or the external evaluation of a router [8]. State

of the art techniques for congestion-aware placement include

mPL [7], a multilevel analytical placer based on non-linear

optimization and estimating the routing demand based on a

two-pin connection routing model, ROOSTER [8]: a min-

cut placer which models nets by Rectilinear Steiner Minimal

Trees, and APlace [9], a multilevel analytical placer based

on non-linear optimization and stochastic estimates of the

routing demand. Similar to our work, [10] propose to minimize

a smooth upper bound on the crossing number to reduce

edge crossings in the context of graph visualization, but their

formulation is incapable of handling multi-pin nets.

These techniques generally suffer from inadequate esti-

mation or prohibitive computational cost. In contrast, the

framework proposed in this work is rigorous and does not

rely on rerunning the placement algorithm or applying post-

placement optimization.

C. PCB Placement

Examples of previous work on the PCB placement prob-

lem include [11], [12], [13], [14]. These techniques rely on

various meta-heuristics to produce non-overlapping layouts

while taking into account various metrics such as thermal

and power characteristics of components, timing, and tidiness.

In general, these methods suffer from drawbacks—e.g. are

computationally expensive, incapable of rotating components,

or evaluated on synthetic or toy benchmarks. In contrast, our

framework is efﬁcient, capable of rotating modules, extensible,

and validated on production PCB designs placed by industry

experts. We additionally acknowledge the similarity of the

PCB placement problem to macro placement, and point the

reader to [15] for a review of relevant techniques.

III. NET SEPARATION-ORIENTED PLACEMENT

A. Preliminaries

net e∈ E

pin matrices Ae∈Rp×2

coordinates and orientation x, y ∈Rn

+,r∈ {0,1}n

density & net separation cost weight λD, λNS ∈R+

convex hull coefﬁcients u∈R2, γ ∈R

wirelength smoothing parameter c∈R+

Fig. 1: Notation & key terms

Let x, y ∈Rn

+be vectors corresponding of coordinates of

ncomponents such that the i-th component has coordinates

encoded in the i-th row of [x:y];[x:y]i. Let Edenote a set

of mnets. We aim to assign coordinates so that the resulting

layout has small cumulative wirelength, layout density, and

routing congestion.

B. NS-Place Objective

Our method may be expressed concisely as the following

unconstrained optimization problem given λ:

min

x,y X

e∈E

[W a(e;x, y) + λNSNs(e;x, y)] + λDD(x, y)(2)

where W a and Dcorresponds to weighted-average wirelength

and density terms, and Ns corresponds to the proposed net

separation term described in Sec. III.D.

C. Wirelength and density-driven optimization

Many modern techniques for analytic placement rely on

quadratic optimization with terms associated with attraction of

connected cells, and repulsion of overlapping cells. A typical

approach is to represent individual nets as rectangles and

to minimize the sum-perimeters over all nets. Repulsion is

often applied between overlapping nodes to reduce density. In

this work, we adopt the smooth continuous and differentiable

weighted-average wirelength (Wa) model [16] for wirelength

cost. The horizontal net-wirelength for net eis given by

W a(e)

x=Pi∈exiexp (xi

Pi∈eexp (xi

c)−Pi∈exiexp (−xi

Pi∈eexp (−xi

where cis a parameter that controls the smoothness and

approximation error. We then write the wirelength of e:

W a(e;x, y) = W a(e)

x+W a(e)

The density term corresponds to the mixed-size module bin-

based density objective described in [9]. The placement area

is divided into Bbins, and the placer seeks to equalize the

overlap at each bin. For a bin b, let xbbe the x-coordinate of

the center and wbbe the width. Then the smoothed overlap

Θx(b, i)in the x-direction between bin band module iwith

width wiand height hiis

Θx(b, i) = 









1−2d2

x/w2

b,if 0≤dx≤wb/2

2(dx−wb)2/w2

b,if wb/2≤dx≤wb

0if wb≤dx

where dx=|xi−xb|. The overlap in the y-direction is deﬁned

similarly. The density function of bin bis then

Db(x, y) = X

CiΘx(b, i)Θy(b, i)(3)

where Ciis a normalization factor such that

PbCiΘx(b, i)Θy(b, i) = wihi—the area of module i.

Finally, D(x, y) = Pb(Db(x, y)−Pi(wihi)

B)2.

D. Net-separation optimization via margin maximization

As mentioned in Sec. II, typical approaches to model

routing congestion rely on estimating or expressing the routed

wire density as a function of pin-density and the feasible

routing-area (e.g. the pin-bounding box [6]). The goal is then

to minimize this notion of wire-density. In this work, we model

the feasible routing region as the convex-hull of the net-pins,

and our goal is to separate routing regions. This prevents over-

estimation of the routing density as shown in Fig. 2. The

method consists of two steps:

1) Given two nets, ﬁnd the max-margin separator h.

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

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

10 玖币 0人已下载

立即下载

摘要：

NetSeparation-OrientedPrintedCircuitBoardPlacementviaMarginMaximizationChung-KuanChengChia-TungHoandChesterHoltz{ckcheng,c2ho,chholtz}@eng.ucsd.eduDepartmentofComputerScienceandEngineeringUniversityofCaliforniaSanDiegoLaJolla,CA,92037AbstractPackaginghasbecomeacrucialprocessduetotheparadigmshiftof...

展开>> 收起<<

Net Separation-Oriented Printed Circuit Board Placement via Margin Maximization Chung-Kuan Cheng Chia-Tung Ho and Chester Holtz ckcheng c2ho chholtzeng.ucsd.edu.pdf

共6页,预览2页

还剩页未读，继续阅读

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

Net Separation-Oriented Printed Circuit Board Placement via Margin Maximization Chung-Kuan Cheng Chia-Tung Ho and Chester Holtz ckcheng c2ho chholtzeng.ucsd.edu

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: