Optimization of On-Chip Polymerase Chain Reaction - Hardware/Software Co-Design and Optimization for Cyberphysical Integration in Digital Microfluidic Biochips - page 128

The device d p k C 1 may be placed anywhere outside O .d p 1:::k ;d p k C 1 / .However,we
place it on a grid point such that the value of Area .d p 1:::k C 1 / is minimized, where
Area .d p 1:::k C 1 / is the area occupied and contoured by devices d p 1 , d p 2 ; :::; d p k ,
d p k C 1 .Thevalueof Area .d p 1:::k C 1 / is calculated according to ( 5.6 ).
This procedure of device placement is illustrated in Fig. 5.3 b, where in the
presence of a heater H ,aDED 1 , and a reservoir R 1 , we show how a new reservoir
R 2 can be optimally placed. We also assume that the heater is placed at the origin
of the layout as the first step of our algorithm.
In each subsequent iteration, we select the device from the top of the priority
queue Q dev . The device is optimally placed with respect to the resources so far
placed in each iteration.

5.3.4 Optimization of Device Placement Results

For a given ordering of devices, the placement results that satisfies all the device-
proximity constraints can be derived by the device placer introduced in Sect. 5.3.3 .
Assume that we have N r indistinguishable reservoirs, N d indistinguishable DEs,
and N h heaters. Thus the number of possible priority queues that contain all
the devices (i.e., the number of candidate solution for device placement on PCR
biochip), is given by:

.N r C N d C N h /Š
N r ŠN d ŠN h Š

:

We can apply the following two alternative approaches in order to select the “best”
candidate solution based on the cost function introduced in Sect. 5.3.2 .

5.3.4.1 Approach 1: Enumeration of All the Possible Ordering of Devices

In practice, only a few EDs are integrated on a biochip due to their high fabrication
costs, and a single heating/cooling module suffices. The number of reagents required
in a typical mixing procedure after DNA amplification is around 8. It is customary
to place the output ports of reservoirs around the boundary of the chip and the heater
in the interior. Therefore, the number of possible orderings significantly reduces in
a practical scenario. Hence we can execute the above-mentioned heuristic algorithm
exhaustively on all orderings. The value of the cost function introduced in Sect. 5.3.2
can be calculated for the placement of each device. The placement that corresponds
to the minimum value of the cost function is selected as an “optimal solution”.