Information Technology Reference
In-Depth Information
2 . 5 ) time algorithm in [ 8 , 14 ] and a
1 . 5 log
O
) time algorithms in [ 9 , 13 ].
In the last decades many works have been devoted to specific instances of this
problem (e.g., see [ 5 , 6 ]).
In this paper, motivated by a renewed interest in the VLSI field, we present
a generalization of the rectilinear polygon decomposition problem. This new
problem is motivated as follows.
Motivation. Currently, microprocessors and application-specific integrated cir-
cuits have thousands of gates switching simultaneously. The impulsive and repet-
itive current drawn by these active devices from the power delivery network
(PDN) is a challenging issue for a correct and reliable PDN design and a severe
source of electromagnetic noise generation [ 17 ]. The PDN for modern medium-
to-high-speed digital printed circuit boards (PCBs) is usually formed from one
or more pair of conducting parallel planes used as “power” and “ground”. The
PDN for digital circuitry has evolved over time, as signal and clock speeds have
increased, from discrete power supply wires, to discrete traces, to area fills and
ground islands on single/two-layer slow-speed boards, to the planar power bus
structure used extensively in today's multi-layer high-speed PCBs.
Noise generated in the power bus can be easily propagated throughout the
board. Propagated noise can affect the operation of other active devices (sig-
nal integrity) [ 15 ]. Among the possible techniques to study the generation and
propagation of noise there is the so-called Cavity Model [ 11 ] in which facing
portions of power bus are considered electromagnetic resonant cavities. Given a
real-world board's layout, one of the primary requirements for the application
of this technique is the geometric identification of all the cavities and their con-
nectivity. Then, a suitable processing of the geometrical cavities' boundaries is
requested for a correct and not over-detailed electromagnetic modeling. After
these actions, the geometry dataset (containing also the electrical parameters)
is ready for being input to the cavity model solver .
From a geometrical point of view, a power bus corresponds to a simple poly-
gon with holes. Two facing polygons
(
n
O
(
n
n
L 1 and
L 2 form a cavity; this cavity is geometrically defined as a polyhedron having
the polygon
P 1 and
P 2 located at parallel layers
L 2 as
height. The currently available cavity model solvers require that such a polygon
P
P
=
P 1 ∩ P 2 as base area and the distance from
L 1 and
must be either a rectangle and isosceles triangle or a rectangle . This and other
constraints lead to solve the problem of computing cavities [ 4 ] according to the
following two steps:
P (a polygon is
octilinear when its angles are all multiple of 45 ). As usual, this simplification
must be performed according to some error criterion;
2. decompose the octilinear polygon
1. “simplify” each base polygon
P
into an octilinear polygon
P into octilinear triangles and rectangles.
The problem at the former step as been studied in [ 3 ]. In this work we address
the polygon decomposition problem at the latter step.
Results. The main aim of this paper is to study the decomposition of octilinear
polygons with holes into octilinear triangles and rectangles. We call this problem
Search WWH ::




Custom Search