TECHNICAL FIELD

[0001] The present disclosure generally relates to the field of for Microfluidics enable Digital Microfluidic Biochip (DMFB). More particularly, the present invention relates to techniques for reallocation of terminals of nets in the DMFB to minimize the crossovers among the nets with minimum degradation of routing performance, such that the resource binding constraints defined during synthesis are preserved.

BACKGROUND

[0002] Micro-fabrication technologies have brought around revolutionary changes in the microfluidic devices in terms of their capability to manipulate micro volumes of fluid in terms of digital entities namely droplets. In Digital microfluidic biochips (DMFB) these tiny droplets are transported and individually treated on a planar surface. This in turn allows for the development of a system that is specifically reconfigurable. Microfluidic operations are generally classified as basic operations namely merging, mixing and splitting, storage, and transportation, followed by detection.

[0003] The dynamic reconfigurability incorporated in DMFBs allows for cells to be shared by multiple droplets’ paths in a time -multiplexed manner. If the DMFB system is designed for the execution of multiple bioassay protocols involving heterogeneous samples, this sharing may result in a major problem termed cross-contamination. Such contaminations caused by bead retention and liquid residue between successive transportation of different droplet samples often result in an erroneous reaction producing incorrect detection outcomes. Wash droplets scheduled to clean up residues left behind by a droplet require greater timing overhead for their routing. Excessive and prolonged contamination may also result in the breakdown of the electrodes. This generates physical defects and causes unwanted behaviours during the actuation procedure. Hence, these aforesaid phenomena motivate the development of technique that generate disjoint droplet route paths.

[0004] Thus, there exists a need of techniques for reallocating the terminals of nets in the DMFB.

SUMMARY

[0005] The present disclosure overcomes one or more shortcomings of the prior art and provides additional advantages discussed throughout the present disclosure. Additional features and advantages are realized through the techniques of the present disclosure. Other embodiments and aspects of the disclosure are described in detail herein and are considered a part of the claimed disclosure.

[0006] In one non-limiting embodiment, the present disclosure discloses a method for reallocation of terminals of nets in Digital Microfluidic Biochip (DMFB), the terminals of the nets comprise at least a source and a target, the method comprising: identifying positions of the source and the target for each net included in a layout of a bioassay, the layout comprises a plurality of nets; estimating a shortest collision-free path between the source position and target position for each net; arranging the plurality of nets in a non-decreasing order of minimum value of the shortest collision- free paths; identifying dependencies existing in the layout, wherein the dependencies comprise at least one of module dependency and Input/Output (KO) dependency; generating a droplet intersection graph (GD) showing intersections of routing paths between the source and the target, wherein each vertex (Vi) represents a net and each edge (Ei) represents crossover between two nets implying possible contamination, assigning preferences to each vertex (Vi), wherein assigning the preferences comprises arranging the vertices (Vi) of the graph (GD) in descending order of their degrees, wherein for vertices with degree zero, no preference is assigned, assigning constraints for net reallocation specific to dependency types; performing reallocation of the at least one of the source and the target based on the dependencies existing in the layout and the assigned preferences, said dependencies comprises module dependency and I/O dependency, wherein performing the reallocation comprises: in case of the module dependency, reallocating respective the source or target to respective symmetric position, and in case of the I/O dependency, performing swapping of the source and target swapping; updating the droplet intersection graph (GD) and determining whether a number of crossovers after performing the reallocation are less than a number of crossovers present before the performing the reallocation, upon determining that the number of crossovers after performing the reallocation are higher than the number of crossovers present before the performing the reallocation, maintaining the reallocation; upon determining that the number of crossovers after performing the reallocation are higher than the number of crossovers present before the performing the reallocation, reverting the reallocation and performing segment wise edge flipping, wherein the segment wise edge flipping comprises diverting the estimated route path for the net to avoid crossovers; updating the droplet intersection graph (GD) and determining whether a number of crossovers after performing the segment wise edge flipping is less than a number of crossovers present before the performing the segment wise edge flipping; upon determining that the number of crossovers after performing the segment wise edge flipping are less than the number of crossovers present before the performing the segment wise edge flipping, maintaining the segment wise edge flipping; upon determining that the number of crossovers after performing the segment wise edge flipping are higher than the number of crossovers present before the performing the segment wise edge flipping, reverting the segment wise edge flipping; after performing reallocation or segment wise edge flipping, generating an output layout containing route paths which comprises a reduced number of crossovers; from the route paths, identifying a set of friction zones (F); performing detour of neighbouring net segments constituting friction zones to avoid prolonged stalling; and generating a final output layout.

BRIEF DESCRIPTION OF THE DRAWINGS

[0007] The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed embodiments. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the figures to reference like features and components. Some embodiments of system and/or methods in accordance with embodiments of the present subject matter are now described, by way of example only, and with reference to the accompanying figures, in which:

[0008] Fig. 1 illustrates schematic view of DMFB, in accordance with an embodiment of the present subject matter.

[0009] Fig. 2a-c illustrates operations on the terminals, in accordance with an embodiment of the present subject matter.

[0010] Fig. 3 illustrates a flow chart of a method for reallocation of terminals of nets in Digital Microfluidic Biochip (DMFB), in accordance with an embodiment of the present subject matter. [0011] Fig. 4a illustrates layout with a set of preplaced 2-pin nets, in accordance with an embodiment of the present subject matter.

[0012] Figure 4b illustrates dependencies, in accordance with an embodiment of the present subject matter.

[0013] Figure 4c illustrates high level synthesis graph, in accordance with an embodiment of the present subject matter.

[0014] Figure 4d illustrates shows the intersections of the routing paths, in accordance with an embodiment of the present subject matter.

[0015] Figure 4e-f illustrate a reservoir bound I/O graph GR for each target connected with an I/O dependent or module dependent source, in accordance with an embodiment of the present subject matter.

[0016] Figure 4g-k illustrate a final layout, in accordance with an embodiment of the present subject matter.

[0017] Figure 5 illustrates a process of reallocation of terminals, in accordance with an embodiment of the present subject matter.

[0018] Figure 6-7 illustrate a combined plot and combined dependency, in accordance with an embodiment of the present subject matter.

[0019] Figure 8 illustrates a system for reallocation of terminals of nets in Digital Microfluidic Biochip (DMFB), in accordance with an embodiment of the present subject matter.

[0020] Fig. 9-10 illustrate special cases of source target swapping, in accordance with an embodiment of the present subject matter.

[0021] Fig. 11 illustrates a bioassay distributed into two sub-problems, in accordance with an embodiment of the present subject matter.

[0022] It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative systems embodying the principles of the present subject matter. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and executed by a computer or processor, whether or not such computer or processor is explicitly shown.

DETAILED DESCRIPTION

[0023] The present invention will be described herein below with reference to the accompanying drawings. In the following description, well known functions or constructions are not described in detail since they would obscure the description with unnecessary detail. [0024] Fig. 1 shows a schematic view of a Digital Microfluidic Biochip (DMFB). In DMFB the tiny droplets are transported and individually treated on a planar surface. The microfluidic 2D array is composed of a set of basic cells. The cells are made up of two parallel aligned glass plates. The bottom plate is a patterned array of individually controlled electrodes, and the top plate is a continuous ground electrode. The filler medium, usually silicone oil, along with the targeted droplet is sandwiched between these two plates. Using time-varying voltages that turns on and off the electrodes forming the 2D array. The interfacial tension between electrode surface and the droplets is modulated using varying potential between them. This in turn actuates them to be transported within the 2D array and facilitates the execution of scheduled microfluidic operations.

[0025] In the design flow for DMFB chips, for any given operation sequence, a significant stage to be followed after the scheduling and the resource allocation is the module placement. The next subsequent stage is considered to be the transportation of the droplets between the ports at the different module boundaries, termed as a net. In a DMFB, different types of modules may be placed at the same location at different sub-stages at separate time intervals, while some may remain fixed/non- reconfigurable after placement, namely optical photo -detectors and waste reservoirs. Moreover, the bioassay involves a time span and precedence over the operations. Hence this is divided into a set of subproblems. The subproblems are implemented sequentially in stages based on the pre-scheduling operation. Each subproblem is subsequently related to its preceding and succeeding subproblem.

[0026] In the present disclosure, for a given placement of modules within a 2D array, a cross - contamination-aware relocation technique for the terminals of the individual nets is disclosed such that the respective bindings of the source and target terminals/pins to the modules are not violated and the subsequent droplet routing performance is improved. The proposed method considers minimization of crossings of the droplet routes typically for cross- contamination minimization. The proposed method may be applied for an individual problem that constitutes a complete bioassay and may be extended for multiple interdependent subproblems which together constitute a complete bioassay.

[0027] The present disclosure aims to reduce the number of irredundant (naive) contaminations using a careful relocation of net terminals such that the routing performance is not degraded. The present disclosure uses a conservative approach, which start with possible minimumlength routes of the nets and attempt to remove crossovers among them such that the route lengths are minimally affected. The present disclosure also considers issues of module interdependency and reservoir binding through a high level synthesis graph.

[0028] According to an embodiment, the objective of droplet transportation is to route all the specified droplets from their respective sources to the prescheduled targets within a 2D grid with satisfying all the associated fluidic and timing constraints. Each of source and target combination is termed as a net. A 2-pin is comprised of a single source and a target. A combination of two sources, single mixer and single target forms a 3-pin net. For each 3-pin net, droplet merging takes place at prespecified locations called mixers.

[0029] According to an embodiment, to reduce cross-contamination during routing detour is performed so as to avoid crossover of routing paths. For 3-pin nets, droplets from different sources referring to the same net may be allowed to share the same locations or paths since, in such cases, mixing does not affect the accuracy of results. Such crossovers or sharing of cells are termed as allowable contamination. However, any attempt to reduce the number of crossovers during routing of droplets is likely to lead in compromising on the latest arrival time (which involves the critical path) and cell utilization in order to accommodate necessary detours. The crossings of the droplet routes can be of two types: native and redundant. The crossings which are inherent for a given module placement, and cannot be removed by changing the route path or by stretching are called native crossings, while the ones which can be removed by detour or by stretching are defined as redundant crossings

[0030] According to an embodiment, a layout obtained from architectural level synthesis has to satisfy certain design specifications based on resource binding and scheduling. These design specifications are often represented in terms of certain constraints namely dependency and resource binding constraints. While module dependency constraint indicates if any source, target, or mixer location for a net is in close proximity to a module preplaced within the 2D grid, the resource binding constraint ensures that a layout position in a DMFB is not used by more than one module, if their usage overlaps in schedule. The present disclosure defines two such dependencies and four interdependencies as defined below.

Dependency on Module: If for a net any source, target, and mixer location lie at the boundary of a preplaced module within the 2D grid, the location is considered as module dependent. Associating a terminal of a net with a different port of the same module without violation of the dependency on module may eliminate certain crossings of nets (both native and redundant).

Dependency on I/O: If a source/target location of a net lies on the boundary of the 2D grid, it is considered to be I/O dependent.

Module Interdependency: If a net has its source and target attached to two different modules namely MS and MT respectively, the modules MS and MT are defined to be interdependent.

I/O to Module Interdependency: For a net, where source/target is observed as I/O dependent as well as module dependent respectively or vice versa, the net is said to have I/O to module dependency. Such a dependency implies that the input operation (for the I/O bound source) is followed sequentially by an operation at the dependent module, or that the module operation is sequentially followed by the dependent output operation.

I/O or Module to Independent Target Interdependency: This is applicable to 2-pin as well as 3-pin nets where the source is I/O or module dependent and the target does not have any dependency. The independent target locations are considered to be fixed and maybe designated for optical detection or incubation or some other specialized microfluidic operations. However, the I/O bound source can be relocated to any other predefined reservoir bound location at the boundary while maintaining the reservoir binding constraints.

I/O to I/O Interdependency: For 2-pin nets, if both source and the target become I/O dependent, it is defined as I/O to I/O interdependency. This is possible for 3-pin nets as well, where two sources are I/O dependent. Droplets from these sources merge at a mixer and the resultant droplet is transported to a target that is either independent or module dependent.

An example of I/O bound source estimation for a bioassay distributed into two sub -problems with a given set of design specification is shown in Figure 11.

[0031] The present disclosure aims to provide constrained crossing-aware terminal relocation for enhanced droplet routing in Digital Micro-fluidic Biochips (CCT). To provide solution to the problem by considering inputs such as a set of M modules with specific height and width for every module, a set of N reservoirs and dispensing ports, a set of nets with pre-specified legal positions for their source, target and(optionally) mixers, and the overall width and height of the layout. [0032] In an embodiment, for every net, the present disclosure assigns a legal position to every source, target, and (optionally) mixer within the layout such that (i) the number of crossovers of the net routes is minimal and (ii) total length of all the routes is reasonably small (implying minimization in utilization of resources). For reducing the number of crossings between any two orthogonal routing paths, three operators are used:

Edge-flipping - this involves identification of staircase segments in a path, and locally flipping the segment as shown in see Figure 2a.

Source -target swapping - identification of a pair of nets which are crossing each other such that if either the sources or the targets are respectively swapped, the crossing will be eliminated as shown in Figure 2b. According to an embodiment, the source -target swapping is the interchange of positions of a pair of vertices of two edges so as to remove the crossover between them. Two special cases of source target swapping are displayed in Figures 9a-9c and 10 — 10c.

Sifting of a route path for a net as shown in Figure 2c.

[0033] According to an embodiment, according to method for net terminal relocation to reduce contamination, initially, the nets are sorted in descending order of their number of crossovers. This requires time Ts. Next, the nets are considered in the sorted order. The chosen net is moved to the lower track by repeatedly swapping its path with its neighbour. This is done in time Tn (say). At every move, the number of crossovers before and after the move is recorded. In the next round, the same net is moved to the upper track Tn with respect to the one with which it has encountered a crossover, and the total number of changes in crossovers is recorded. Among the upward and downward movement of the net, the one yielding maximum reduction in number of crossovers is the local optimum. The net is moved to the position of local optima and locked. In case there is no reduction in number of crossovers, the position of the net is not changed. These operations are repeated for every net. Thus, in the worst-case, for n nets, total time taken is given by T _totai = Ts + 2n x Tn. In the worst-case, a net can have (n-1) neighbours. Thus, Tn = a(n-l) where a is a constant. Now, sorting can be done in the worst-case scenario of time O(n log n). Thus, Ts = O(n log n). Hence worstcase time complexity of sifting is O(n2). Among these three operators discussed above, the operator source-target swapping only can reduce the native crossovers. The other two operators can reduce the redundant crossovers. From the description of the three operators, the following observations are found. First observation is that the operator edge -flipping does not change the length of a routing path. From its description, the operator sifting, when applied to a pair of routing paths may be considered to be a generalization of edge -flipping. Hence, the following observation holds for sifting. The second observation is that the operator sifting applied to a pair of routing paths, does not change the length of the routing paths. However, it can be necessarily employed to reduce redundant crossovers.

[0034] These new heuristic operators are employed for rearranging the route path for a given net through terminal relocation for the modules. For any net with module-to-module dependency reallocation of the respective source ports to any possible symmetric location of the module (mentioned later) may eliminate any redundant crossover with possible improvement in route performance. A skilled person would appreciate the fact that a redundant crossing can otherwise be avoided through long detours. This definitely affects the routing performance as the whole route path is normally confined within the predetermined routing zone - thereby maintaining the respective arrival time and cell utilization for the net to be the same. However long detours not only exceed the routing zones resulting in degradation in route performance but also may inflict new cross-overs by interfering with the routing zones of other nets. In such cases using terminal reallocation for the modules dependent nets redundant crossovers can be eliminated. At the same time scopes of terminal reallocation are explored with an additional advantage of shrinkage in the routing zone for the respective network. This in turn enhances the performance of routing in terms of parameters like the latest arrival time and utilization of cells.

[0035] Referring to Fig. 3 of the present disclosure which illustrates a method for reallocation of terminals of nets in Digital Microfluidic Biochip (DMFB). The proposed method initially does pre- process to decompose every 3-pin net into two numbers of 2-pin nets. The method 300 starts with an initial set of source and target locations for every net satisfying the dependency constraints. Subsequently, it works in two phases. Phase I performs shortest route path estimation for each net for the given set of locations, bypassing the obstacles and arranging the nets in non-descending order of their respective Manhattan distances. Phase II performs the proposed terminal relocation for enhanced route performance with minimal crossover keeping the dependency constraints unchanged. Subsequently, an appropriate combination of the three operators discussed above is applied to the route paths to reduce the remaining redundant crossovers.

[0036] At step 302, the method recites identifying positions of the source and the target for each net included in a layout of a bioassay. According to present disclosure, all 3-pin nets are reduced into a combination of three 2 pin nets namely si m, s2 m and m t. Every 2-pin net has a set of legal positions for its source and target which may be bound with any of the following: a port of a binding module, a reservoir or dispensing component, and other operational module e.g. detector or buffer locations within the biochip layout.

[0037] At step 304, method recites estimating a shortest collision-free path between the source position and target position for each net. The method at step 306, the method comprises arranging the plurality of nets in a non-decreasing order of minimum value of the shortest collision- free paths.

[0038] At step 308, the method recites identifying dependencies existing in the layout. The dependencies comprise at least one of module dependency and Input/Output (I/O) dependency. Further, at step 310, a droplet intersection graph G _D (V _D , E _D ) showing intersections of routing paths between the source and the target is formed. Each vertex (V _D ) represents the sets of net listed in P and edge (E _D ) represents crossover between two nets implying possible contamination. The edge (E _D ) exists if there is a crossover between nets v _; and Vj, (Vj, v, C V _D ). Let the highest degree among the vertices be D.

[0039] At step 312 the method recites assigning preferences to each vertex (V , wherein assigning the preferences comprises arranging the vertices (Vi) of the graph (G _D ) in descending order of their degrees. No preference is assigned for vertices with degree zero. Further, the method performs reallocated binding of the sources of the I/O bound nets with an aim to reduce path length for each such net and attempts to reduce contamination in the process.

[0040] The method at step 314 recites assigning constraints for net reallocation specific to dependency types. In an embodiment, wherein when the DMFB is realising a bioassay which is formulated, scheduled and placed within a single layout, the assigned constraints for the net reallocation specific to dependency types comprises: cl: all target locations are initially kept fixed; c2: an I/O bound source location can be relocated to any closer reservoir location; c3: module bound sources can be relocated to any symmetric position bound with same module M; c4: a target location bound to a module can also be relocated at a symmetric position bound to same module; c5: target locations reserved as waste reservoir are fixed; c6: for any independent source or target (unbound), no relocation is allowed; and c7: the I/O bound source locations for 3 -pin net can be repositioned such that two sources are symmetrically equidistant from the mixer.

[0041] The method further at steps 316 comprises performing reallocation of the at least one of the source and the target based on the dependencies existing in the layout. The dependencies comprise module dependency and I/O dependency. Said the reallocation comprises, in case of the module dependency, reallocating respective the source or target to respective symmetric position, and in case of the I/O dependency, performing swapping of the source and target swapping.

[0042] The method further comprises updating the droplet intersection graph (GD) and determining whether a number of crossovers after performing the reallocation are less than a number of crossovers present before the performing the reallocation, upon determining that the number of crossovers after performing the reallocation are higher than the number of crossovers present before the performing the reallocation, maintaining the reallocation. Further, upon determining that the number of crossovers after performing the reallocation are higher than the number of crossovers present before the performing the reallocation, the method further comprises reverting the reallocation and performing segment wise edge flipping, wherein the segment wise edge flipping comprises diverting the estimated route path for the net to avoid crossovers.

[0043] The method further recites updating the droplet intersection graph (G _D ) and determining whether a number of crossovers after performing the segment wise edge flipping is less than a number of crossovers present before the performing the segment wise edge flipping. Upon determining that the number of crossovers after performing the segment wise edge flipping are less than the number of crossovers present before the performing the segment wise edge flipping, maintaining the segment wise edge flipping.

[0044] The method further recites that upon determining that the number of crossovers after performing the segment wise edge flipping are higher than the number of crossovers present before the performing the segment wise edge flipping, reverting the segment wise edge flipping. After performing reallocation or segment wise edge flipping, the method at 318 recites generating an output layout containing route paths which comprises a reduced number of crossovers. Furthermore, the method at 320 recites identifying a set of friction zones (F) from the route path. The method further recites performing detour of neighbouring net segments constituting friction zones to avoid prolonged stalling and generating a final output layout.

[0045] Figure 4a shows the layout with a set of preplaced 2-pin nets (a, b, c, d, e, f, g, h). All the reservoir bound I/O locations (at the borders) together with respective pre -estimated route paths for each net are specified. The crossover locations are marked in green. The total number of crossovers existing for the estimated route path is 16. The dependencies stated above are identified as shown in Figure 4b and Tables la and lb. A high-level synthesis graph is plotted as shown in Figure 4c, based on this set of dependencies.

[0046] Further, Graph GD shows the intersections of the routing paths as shown in Figure 4d where each vertex vi represents a net and each edge e _; represents intersection (crossover) between two nets implying possible contamination. Each vertex v _; is assigned a value shown in a square box beside the vertex indicating the Manhattan distance di for the associated net. Table gives the degree of each vertex in graph G _D and its preference assigned as described above in the subroutine. Figures 4e and 4f represent a reservoir bound I/O graph GR for each target connected with an VO dependent or module dependent source. Each square vertex v _; in GR represents a target whereas each vertex r, represents a reservoir bound I/O location (port). Here for each such target v _; all I/O locations q are connected through an edge e (v _i( q) indicating the possible accessibility. The shortest possible location of the reservoir from each specific target is computed and finally the tentative new placement of the source location for the given net is asserted.

[0047] Step 1. Each source for the corresponding target is relocated to the closest reservoir bound location according to ascending order of preference as computed in T _pr . However, for any target, if its preferred location already got occupied through an earlier allocation with higher preference, the next possible closest locations are checked and assigned accordingly. The final allocation lines in G _R . The final layout after completion of all reallocations of ports for module to module dependent nets is displayed in figure 4g together with final intersection graph G _D as shown in figure 4h and the final preference table T _pr . It is found that the overall contamination is reduced to 2.

[0048] Step 2. From the layout one friction zone comprising four cells denoted in gray is identified. Two nets e and h are involved in the friction. By choosing an alternate path for h (having lower Manhattan distance than that of e) and arranging for necessary deviation to avoid hard blockage, friction zone M2 is eliminated. The layout with friction zone is shown in Figure 4i.

[0049] Step 3. For the current placement with two contaminations as computed through initial route estimation, possibility of new reallocation as well as detour for the nets e, g and h (involved in the current crossover) are explored. For the 2-pin net g the I/O dependent source is reallocated to the next closest position (if not already occupied) and the new route path (with necessary detour) is explored for the avoidance of cross-contamination. At the same time a new friction zone is developed between nets g and e necessitating further detour as shown in Figure 4j.

[0050] Step 4. Finally, to avoid cross-contamination between e and h where no I/O dependent sources are involved, a long detour for e has to be introduced. The final layout with no contamination and no friction zone is shown in Figure 4k. The dependency diagram that corresponds to the final layout is given in figure 4k and is in conformance with the earlier dependency diagram as shown in earlier (in figure 4b). The initial route performances together with those computed after each assigned placement step are displayed in Table 2. It is found that after Step 3 the layout has the optimum output.

[0051] In the earlier embodiments, the present disclosure considers bioassays that are formulated, scheduled and placed within a single layout. However, in certain cases, a bioassay may be divided into a set of sequential microfluidic operations using same group of cells within a layout. The cells of a layout, in such cases, are reconfigured as different modules in different sequences. Each such set of sequential microfluidic operations is termed as a subproblem and the overall bioassay is said to be divided into a set of such subproblems.

[0052] In such cases, for each subproblem the I/O dependencies are calculated with input locations or waste dispenser locations being specified in the same subproblem. The module dependencies and module to I/O dependencies for the given subproblem are calculated with module locations specified for either preceding or following subproblems. The procedure for formulating the total dependency for the overall testbench is as follows:

1. Plotting all subproblem layouts showing the nets and modules within a single 2D array of the given dimension as a combined layout. Example of such combined layout for In-Vitro 1 testbench with 11 subproblems as illustrated in appears in Figure 6a.

2. Marking each source, target and mixer as isj, itj and iMxj respectively. Here i denotes the subproblem number and j denotes a net number in the subproblem. The modules are represented as xMy, where x represents subproblem number and y represents a module number in the subproblem. The waste dispenser cell is marked as shaded in Figure 6a.

3. In the combined layout, First marking the locations representing inputs indicating the reservoir binding to the source locations and formulate the I/O dependency graph. The locations bound with single net are marked as Rx (where x is the serial number of the reservoir).

[0053] The locations bound with multiple nets are marked as Rmx (where x = reservoir number to be bound). For reservoirs bound with multiple nets any tentative relocation of the reservoir involves relocation of respective sources for all the nets bound to the reservoir to the new location. Then formulate the module dependency using combined layout. The dependency implementations are given as follows: Module to Source dependency, Target to Module dependency, and Source to Waste dependency.

[0054] In the Module to Source dependency, if any source of a net (iSj) is adjacent to a module (xMy) and the net subproblem number (j) > module subproblem number(y) the source dependency exists for the specified net with the specified module. However, there can be multiple modules adjacent with the given net.

[0055] In the Target to Module dependency, if any target of a net (iSj) is adjacent to a module (xMy) and the net subproblem number (j) < module subproblem number(y) source dependency exists for the specified net with the specified module.

[0056] In Source to Waste dependency, this indicates any source (iSj) (generally output from a module) for a 2-pin net with net number j and the target (iTj) being located at the waste dispenser (W). This dependency is termed as source to waste dependency. Based on the types of dependency information obtained for the combined layout a combined dependency diagram is generated as shown in Figure 6b.

[0057] According to an embodiment, the method 300 recites that when the DMFB is realising a bioassay which is formulated, scheduled and placed into multiple stages as multiple subproblems, for each subproblem, the I/O dependencies are calculated with input locations or waste dispenser locations being specified in the same subproblem, and the module dependencies and module to I/O dependencies for the given subproblem are calculated with module locations specified for either preceding or following subproblems. Further, in order formulate the total dependency, all subproblem layouts showing the nets and modules are plotted within a single 2D array of the given dimension as a combined layout. In such combined layout, locations bound with single net are marked as Rx, where x is the serial number of the reservoir, and locations bound with multiple nets are marked as Rmx, where x = reservoir number to be bound. The combined plot for the overall layout after placement is shown in figure 7a. The final dependency diagram in terms of I/O and Module dependency for all nets in all subproblems are shown in Figure 7b. It is found that the number of I/O and module dependencies before and after placement remain the same.

[0058] In another embodiment, the assigned constraints for the net reallocation specific to dependency types comprises cl: all target locations are initially kept fixed; c2: an I/O bound source location, can be relocated to possible closest reservoir location of the same subproblem; c3: for multiple net bound reservoir all sources bound to the net are to be relocated to the same new location Rmx; c4: if both of the source and target are module-bound then relocate both preserving adjacency with their respective module to symmetrical positions such that the manhattan distance for the specified net is minimum; c5: if target or source is independent, maintaining its original location as it is considered as predetermined non-reconfigurable location; c6: if the target is located at waste dispenser location preserve its original location; c7: if it is a 3 -pin net comprising two sources (iSxj, iSyj), a single mixer (iMxj) and a single target (iTx): relocating each source in a similar manner as mentioned in cl, c2, c3, relocating the mixer (iMxj) such that distance (iSxj, iMxj) - distance (iSyjjMxj) 1, and relocate the target (iTxj) in a similar manner as mentioned in conditions c4 and c5, c8: an additional constraint for relocating the target iMxj is to be maintained. It states that distance (iMxj, iTxj) must remain the same as it was before relocation of both mixer and target. The Idea is to cover same number of cells necessary for mixing of the two source droplets for any specified net.

[0059] According to an embodiment, the method 300 also recites generating a reservoir bound I/O graph (G _R ) for each target connected with an I/O dependent source or a module dependent source, wherein each vertex v _; in GR represents a target whereas each vertex r, represents a reservoir bound I/O location. Here, for each target v _; all I/O locations p are connected through an edge ey (v _i; p) indicating the possible accessibility. The method further comprises reallocating reservoirs to I/O locations for each net based on binding information in the reservoir bound I/O graph GR. The nethod further recites that performing reallocation comprises reallocating at least one of the source, the target and mixer based on the binding information in the reservoir bound I/O graph.

[0060] According to another embodiment, the method further recites that after generating the output layout, determining whether all dependencies remain unchanged. Upon determining that the dependences are changed, the method recites discarding the relocation performed and again performing the reallocation based on the dependencies. Upon determining that the dependences remain unchanged, the method recites identifying the set of friction zones.

[0061] In this manner, the present disclosure discloses a method for intelligent net placement for a given 2D layout representing a bioassay (with an initial allocation of cells for modules as well as source and target locations for each net). Experimental results display considerable improvement in route performance and reasonable reduction in contamination (more than 65% in all cases). Thus, the present disclosure discloses the method for reallocation of terminals of nets in the DMFB which minimizes the crossovers among the nets with minimum degradation of routing performance such that the resource binding constraints defined during synthesis are preserved. The method can be easily understood from fig. 5, which shown flow of the method.

[0062] Referring to fig. 8, a system for reallocation of terminals of nets in Digital Microfluidic Biochip (DMFB) is illustrated in accordance with an embodiment of the present disclosure. The system 800 comprises a position identifying unit 802, a path estimation unit 804, a processing unit 806, and a graph generation unit 808. These entities may be communicatively coupled to each other via wireless or wired communication. These entities may be implemented as one or more processor, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, machine learning model and/or any devices that manipulate signals based on operational instructions. In an embodiment, the processing unit 206 may comprise one or more processors and a memory, but not limited thereto.

[0063] According to an embodiment, the position identifying unit 802 is configured to identify positions of the source and the target for each net included in a layout of a bioassay. The path estimation unit 804 is configured to estimate a shortest collision-free path between the source position and target position for each net.

[0064] Further, the processing unit 806 is configured to arrange the plurality of nets in a nondecreasing order of minimum value of the shortest collision -free paths, and identify dependencies existing in the layout, wherein the dependencies comprise at least one of module dependency and Input/Output (I/O) dependency. Further, the graph generation unit 808 configured to generate a droplet intersection graph (G _D ) showing intersections of routing paths between the source and the target, wherein each vertex (V,) represents a net and each edge (£,) represents crossover between two nets implying possible contamination.

[0065] Further, the processing unit 806 may assign preferences to each vertex (V,), wherein assigning the preferences comprises arranging the vertices (VJ of the graph (G _D in descending order of their degrees, wherein for vertices with degree zero, no preference is assigned. The processing unit 806 may assign constraints for net reallocation specific to dependency types and reallocate the at least one of the source and the target based on the dependencies existing in the layout and the assigned preferences, said dependencies comprises module dependency and I/O dependency, wherein performing the reallocation comprises: in case of the module dependency, reallocating respective the source or target to respective symmetric position, and in case of the I/O dependency, performing swapping of the source and target swapping. The segment wise edge flipping comprises diverting the estimated route path for the net to avoid crossovers.

[0066] After performing reallocation or segment wise edge flipping, the processing unit may generate an output layout containing route paths which comprises a reduced number of crossovers. The processing unit 806 may identify a set of friction zones (F) in the route paths and perform detour of neighbouring net segments constituting friction zones to avoid prolonged stalling. Lastly, the processing unit 806 may generate a final output layout.

[0067] In an embodiment, when the plurality of nets comprises one or more 3 -pin nets having two sources (SI, S2), a mixer (m) and a target(t), the processing unit may reduce each 3-pin net to three 2-pin nets namely (SI, m) , (S2, m) and (m, t), and reallocate at least one of the source, the target and the mixer based on the dependencies existing in the layout.

[0068] In another embodiment, when the DMFB is realising a bioassay which is formulated, scheduled and placed within a single layout, the assigned constraints for the net reallocation specific to dependency types comprises: cl: all target locations are initially kept fixed; c2: an I/O bound source location can be relocated to any closer reservoir location; c3: module bound sources can be relocated to any symmetric position bound with same module M; c4: a target location bound to a module can also be relocated at a symmetric position bound to same module; c5: target locations reserved as waste reservoir are fixed; c6: for any independent source or target (unbound), no relocation is allowed; and c7: the I/O bound source locations for 3-pin net can be repositioned such that two sources are symmetrically equidistant from the mixer.

[0069] Further, when the DMFB is realising a bioassay which is formulated, scheduled and placed into multiple stages as multiple subproblems, the processing unit may, for each subproblem, determine the I/O dependencies with input locations or waste dispenser locations being specified in the same subproblem, and determine the module dependencies and module to I/O dependencies for the given subproblem with module locations specified for either preceding or following subproblems. To determine the total dependency, all subproblem layouts showing the nets and modules are plotted within a single 2D array of the given dimension as a combined layout, wherein in the combined layout, locations bound with single net are marked as Rx, where x is the serial number of the reservoir, and locations bound with multiple nets are marked as Rmx, where x = reservoir number to be bound.

[0070] Further, when the DMFB is realising the bioassay which is formulated, scheduled and placed into the multiple stages as the multiple subproblems, the assigned constraints for the net reallocation specific to dependency types comprises: cl: all target locations are initially kept fixed; c2: an I/O bound source location, can be relocated to possible closest reservoir location of the same subproblem; c3: for multiple net bound reservoir all sources bound to the net are to be relocated to the same new location Rmx; c4: if both of the source and target are module-bound then relocate both preserving adjacency with their respective module to symmetrical positions such that the manhattan distance for the specified net is minimum; c5: if target or source is independent, maintaining its original location as it is considered as predetermined non-reconfigurable location; c6: if the target is located at waste dispenser location preserve its original location; c7: if it is a 3-pin net comprising two sources (iSxj, iSyj), a single mixer (iMxj) and a single target iTx): relocating each source in a similar manner as mentioned in cl, c2, c3, relocating the mixer (iMxj) such that distance (iSxj, iMxj) - distance (iSyjjMxj) 1, and relocate the target (iTxj) in a similar manner as mentioned in conditions c4 and c5; and c8: maintaining distance (iMxj, iTxj) same as it was before relocation of both mixer and target.

[0071] According to an embodiment, the graph generating unit may further generate a reservoir bound I/O graph ( G _R ) for each target connected with an I/O dependent source or a module dependent source, wherein each square vertex vi in the reservoir bound I/O graph (G _R ) represents a target whereas each vertex ri represents a reservoir bound I/O location. The processing unit may further reallocate reservoirs to I/O locations for each net based on binding information in the reservoir bound I/O graph (GR), wherein performing reallocation comprises reallocating at least one of the source, the target and mixer based on the binding information in the reservoir bound I/O graph G _R .

[0072] The processing unit may also determine whether all dependencies remain unchanged, after generating the output layout. Upon determining that the dependences are changed, the processing unit 806 may discard the relocation performed and again performing the reallocation based on the dependencies. Upon determining that the dependences remain unchanged, the processing unit 806 may identify the set of friction zones.

[0073] In this manner the disclosed system and method provide reallocation of terminals of nets in the DMFB which minimizes the crossovers among the nets with minimum degradation of routing performance such that the resource binding constraints defined during synthesis are preserved.

[0074] Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope and spirit of the disclosed embodiments.

[0075] Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer- readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., are non- transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, non-volatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media. [0076] Suitable processors/controllers include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of microprocessors, one or more microprocessors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) circuits, any other type of integrated circuit (IC), and/or a state machine.