Hardware Reference
In-Depth Information
where ˛ and ˇ are user-specified weight parameters that can be adjusted to count
the relative importance of each metric. For two device placement results G
1
and G
2
,
if F.G
1
/<F.G
2
/,thenG
1
will be considered as the better device placement result.
5.3.3
Device Placement on a PCR Biochip
The device placement problem in a biochip has the following two characteristics:
•
The layout of a digital microfluidic biochip usually consists of a discrete 2D array
of identical electrodes; hence, we can assume that the devices and electrodes are
constrained to stay on integer grid points.
•
C
.d
a
;d
b
/, the minimum distance between two devices d
a
and d
b
, depends on
the device pair.
Since each pair of devices may require a distinct constraint on separation spacing,
the overall search space may become very large and we conjecture that the problem
of finding a minimum-area layout is an NP-hard problem [
25
]. Hence to develop
our design tool, a greedy algorithm based on an iterative method is proposed in this
section.
We assume that the PCR layout will be built on a “digital plane”, which is the set
of all points possessing integer coordinates [
26
]. Mathematically, the digital plane
can be represented as
2
,where
is the set of integers. The center of every physical
device/electrode is assumed to be placed on a “digital point”, i.e., a point in
Z
Z
2
[
26
].
If d
a
and d
b
stand for two devices to be placed on the chip, we draw a circle
with radius
Z
.d
a
;d
b
/, centered at d
a
. The region inside the circle is defined as the
“forbidden region” of d
b
with respect to d
a
. The set of all electrodes that completely
or partially overlap with the forbidden region of d
b
is written as O
.d
a
;d
b
/
. Note that
O
.d
a
;d
b
/
can be considered as a “digital object” in
C
2
as it is a set of digital points
[
26
]. Figure
5.3
a shows an example of the digital object corresponding to the heater.
If d
b
is placed on an electrode that is not an element of O
.d
a
;d
b
/
, then the
distance between their centers will be no less than
Z
.d
a
;d
b
/. In other words, the
corresponding separation constraint will be satisfied. As shown in Fig.
5.3
a, if the
reservoir is placed at the boundary or outside of the heater's digital object, the
separation constraint for the reservoir and the heater will be satisfied.
In order to minimize the area of the chip, all the devices need to be placed as
closely as possible. An example of valid and compact placement of a reservoir R
2
in the presence of a heater H ,aDED
1
, and a reservoir R
1
is shown in Fig.
5.3
b.
The isothetic convex envelope [
26
] that tightly encloses the union of three forbidden
regions (corresponding to H , D
1
,andR
1
, each with respect to R
2
) is displayed here
as a digital object. Note that for a valid placement, the reservoir R
2
should not be
placed inside this object; also for compactness, it should be placed as closely as
possible so that the total area of the chip including all the resources is minimized.
In the initial stage of device placement, all the devices of the PCR biochip
are listed in a priority queue, Q
dev
. The ordering of devices in Q
dev
is randomly
C
