Hardware Reference
In-Depth Information
Fig. 4.4 ( a ) Partitioning of a
sequencing graph; ( b )the
interdependency of
macro-operation M T ,
operation L and operation R
a
R
L
b
R
L
M T
T
A directed tree
loss of generality, we assume that operations 1 5 are executed in 1 4 mixers.
The corresponding result for the placement of the modules on a 7 7 array is shown
in Fig. 4.3 g. Each mixing module has one storage unit inside. When the mixing
operation is completed, the product droplet stays inside the corresponding storage
unit. Based on the module-placement for operations 1 5, module-placement
for other succeeding operations can be obtained. For example, the regions where
operations 1 and 2 are implemented will be assigned to their successor operations.
In this way, the module placement of operations in the directed-tree structure are
determined. The schedules of operations in the directed-tree can also be determined
based on their input/output interdependency.
4.3.2
Synthesis for Sequencing Graphs in General Cases
For sequencing graphs that are not directed trees (i.e., there are nodes whose out-
degrees are greater than 1, as shown in Fig. 4.4 a), we can derive their synthesis
results using the following steps:
1. Graph partitioning: First we determine the set of nodes f N n 1 ;N n 2 ; :::; N n k g
whose out-degrees are greater than 1, then remove all the edges directed away
from these nodes. Then the graph is partitioned into multiple directed trees
f T 1 ;T 2 ; :::; T n g , and each node in f N n 1 ;N n 2 ; :::; N n k g becomes the root node
in a directed tree.
2. Synthesis for directed trees: We apply operation-interdependency-aware syn-
thesis to each directed tree, and derive the corresponding synthesis results.
3. Sorting of directed trees: For any pair of trees T A and T B , we suppose there
exists a node O T A 1 2 T A and a node O T B 1 2 T B , such that O T A 1 is the predecessor
of O T B 1 . Then the relationship between trees T A and T B is expressed as T A <
T B . Any two elements T x and T y in f T 1 ;T 2 ; :::; T n g may stand in any of three
mutually exclusive relationships to each other: T x <T y ,orT x >T y ,orT x D T y
(neither of the other two). The conflicting case (i.e., “T x <T y and T x >T y ”) will
never occur. The proof can be found in Lemma 4.1 of this section.
4. Merge the synthesis results: The synthesis result of f T 1 ;T 2 ; :::; T n g are
merged together according to their order. If T x
<T y then operations in T x
Search WWH ::




Custom Search