Biomedical Engineering Reference
In-Depth Information
Distance = 8
Mixer
Interdependent
module pair
Detector
Figure 2.2
Illustration of module distance.
the overall synthesis time will be overwhelming due to the large number of
chromosomes and evolution steps in the synthesis flow. Moreover, since we
only care about the final synthesis result, we need to reduce the effort spent
to generate route plans for the intermediate designs. Therefore, we adopt
simple estimates of routability, instead of precisely calculating droplet routes
at each step.
The module distance
M
ij
is defined as the length of the shortest path
between two interdependent modules
M
i
and
M
j
, assuming that there are
no obstacles between them. By interdependent module, we refer to module
pairs where the operation of one module depends on the operation of the
other module
(Figure 2.2)
.
For example, if optical detection is to be carried out for a mixed droplet,
then the optical detector and the mixer are interdependent. Note that in many
cases, two interdependent modules may not be able to operate in successive
time steps; for example, a mixed droplet may have to wait for a few cycles
since the detector may be busy processing another detection step when the
mixing is finished. In such cases, a storage unit is needed, and we consider
the storage unit and the detector as interdependent modules. The mixer and
the storage unit are also interdependent modules.
Thus, droplets are routed only between interdependent modules. The mod-
ule distance is calculated for each interdependent module pair. Although the
module distance
M
ij
may not be exactly the same as the shortest path length,
especially if there are obstacles in the form of other modules on the array,
M
ij
is still a good estimate of routability between
M
i
and
M
j
.
Note that in some scenarios, the locations of two interdependent modules
may overlap on the array. In this case, we set the corresponding module dis-
tance to zero. Since our goal is to guarantee the routability of modules in the
synthesized biochip, we adopt the average module distance (over all inter-
dependent modules) as a design metric. Similarly, we adopt the maximum
module distance to approximate the maximum length of droplet manipula-
tion and use it for routability estimation. For each chromosome considered
