7.2 Motivation and Notation for Application-Specific Architectures
87
The realization of a set of experiments onto a microfluidic architecture requires
modules executing the operations. To realize an experiment, the payload droplet
has to traverse a sequence of modules executing the operations defined in the
experiment. In order to allow the traversal of a droplet from one module to another,
the modules are linked by connections (which are eventually realized by channels
and bifurcations). The used modules and their connections describe the architecture,
which is formally defined as follows:
Definition 7.2 Each operation o ∈ O can be realized by one or more instances of
a module. The function maxI : O → N defines the number of available instances
of a module realizing an operation o. Then, the total set of all available modules
and additionally the MPU is defined by ˆ
V := {MP U, (o i ) : o ∈ O and 1 ≤ i ≤
maxI(o)} (an element of this set is also called node in the following). Generally,
the nodes in this set are denoted as u ∈ V but in order to explicitly denote the
ith instance of a module implementing the operation o, also o i ∈ V is used in the
following. Further, the total set of all possible connections between these modules
and the MPU is defined by ˆ
E := {(u, v) : u, v ∈ ˆ
V }. An element (u, v) ∈ ˆ
E (also
called edge in the following) connects the output of the node u with the input of the
node v with a connection. Taking ˆ
V and ˆ
E, a superset architecture ˆ
G := ( ˆ
V , ˆ
E) can
be formed representing all possible architectures from the available modules. The
application-specific architecture G = (V , E) is a subset of the nodes V ⊆ ˆ
V and
edges E ⊆ ˆ
E from ˆ
G which realizes the given set of experiments and, at the same
time, satisfies physical constraints as well as further design objectives.
Example 7.3 Consider the set := {φ 1 , φ 2 , φ 3 } of experiments to be realized with
φ 1 := (f, m, d), φ 2 := (m, f, d), and φ 3 := (f, d, m). Additionally assume for
the operations O := {m, f, d} that there are maxI (m) = 2, maxI (f ) = 2, and
maxI (d) = 2 modules available. Then, an application-specific architecture realizing can be derived from the superset architecture ˆ
G := ( ˆ
V , ˆ
E) composed of the
MPU and available modules ˆ
V := {MP U, m 1 , m 2 , f 1 , f 2 , d 1 , d 2 } and possible
connections ˆ
E := {(MP U, MP U ), (MP U, m 1 ), (MP U, m 2 ), (MP U, f 1 ), . . .}.
This includes the solution requiring the minimal number of steps shown in Fig. 7.1b
and discussed before in Example 7.2.
Then, the question remains how to obtain an optimized application-specific
architecture. A naive realization, which always would allow for a realization of all
experiments with minimal steps and preventing a payload re-injection would be an
architecture in which, for each operation of an experiment, a dedicated module and
connection are built. But obviously, this would result in a too expensive architecture
with no reuse. Hence, in this chapter, the following research question is considered:
How to efficiently generate an application-specific architecture, which realizes the given
experiments with minimal steps and preventing payload re-injection while, at the same
time, keeps the architectural overhead with respect to modules and connections as small
as possible?
87
The realization of a set of experiments onto a microfluidic architecture requires
modules executing the operations. To realize an experiment, the payload droplet
has to traverse a sequence of modules executing the operations defined in the
experiment. In order to allow the traversal of a droplet from one module to another,
the modules are linked by connections (which are eventually realized by channels
and bifurcations). The used modules and their connections describe the architecture,
which is formally defined as follows:
Definition 7.2 Each operation o ∈ O can be realized by one or more instances of
a module. The function maxI : O → N defines the number of available instances
of a module realizing an operation o. Then, the total set of all available modules
and additionally the MPU is defined by ˆ
V := {MP U, (o i ) : o ∈ O and 1 ≤ i ≤
maxI(o)} (an element of this set is also called node in the following). Generally,
the nodes in this set are denoted as u ∈ V but in order to explicitly denote the
ith instance of a module implementing the operation o, also o i ∈ V is used in the
following. Further, the total set of all possible connections between these modules
and the MPU is defined by ˆ
E := {(u, v) : u, v ∈ ˆ
V }. An element (u, v) ∈ ˆ
E (also
called edge in the following) connects the output of the node u with the input of the
node v with a connection. Taking ˆ
V and ˆ
E, a superset architecture ˆ
G := ( ˆ
V , ˆ
E) can
be formed representing all possible architectures from the available modules. The
application-specific architecture G = (V , E) is a subset of the nodes V ⊆ ˆ
V and
edges E ⊆ ˆ
E from ˆ
G which realizes the given set of experiments and, at the same
time, satisfies physical constraints as well as further design objectives.
Example 7.3 Consider the set := {φ 1 , φ 2 , φ 3 } of experiments to be realized with
φ 1 := (f, m, d), φ 2 := (m, f, d), and φ 3 := (f, d, m). Additionally assume for
the operations O := {m, f, d} that there are maxI (m) = 2, maxI (f ) = 2, and
maxI (d) = 2 modules available. Then, an application-specific architecture realizing can be derived from the superset architecture ˆ
G := ( ˆ
V , ˆ
E) composed of the
MPU and available modules ˆ
V := {MP U, m 1 , m 2 , f 1 , f 2 , d 1 , d 2 } and possible
connections ˆ
E := {(MP U, MP U ), (MP U, m 1 ), (MP U, m 2 ), (MP U, f 1 ), . . .}.
This includes the solution requiring the minimal number of steps shown in Fig. 7.1b
and discussed before in Example 7.2.
Then, the question remains how to obtain an optimized application-specific
architecture. A naive realization, which always would allow for a realization of all
experiments with minimal steps and preventing a payload re-injection would be an
architecture in which, for each operation of an experiment, a dedicated module and
connection are built. But obviously, this would result in a too expensive architecture
with no reuse. Hence, in this chapter, the following research question is considered:
How to efficiently generate an application-specific architecture, which realizes the given
experiments with minimal steps and preventing payload re-injection while, at the same
time, keeps the architectural overhead with respect to modules and connections as small
as possible?