A Cluster-Based Parallel Router for DMFBs

A Cluster-Based Parallel Router for DMFBs

A common-path based approach

Prasanta Kr. Roy

Dept. of CSE/IT Siliguri Institute of Technology

Siliguri,West Bengal, India

Asit Barman

Dept. of CSE/IT Siliguri Institute of Technology

Siliguri, West Bengal, India

Abstract One of the recent areas of research is the use of microfluidics for building up biochips, the digital microfluidic biochips (DMFB). This paper deals with a challenging problem related to the design of DMFB. Specifically the design problem considered is related to high performance droplet routing, where each droplet has a single source location and a single target location. The objectives are (i) minimizing the number of electrodes used in the DMFB, and (ii) minimizing the total routing time of all the droplets or arrival time of a droplet that is the last to arrive at its target(Latest Arrival Time). We propose a simple clusterbased algorithm for concurrent path allocation to multiple droplets, based on the Soukups routing algorithm [19], together with the use of stalling, and possible detouring of droplets in cases of contentions. Selection of the droplets is based on their respective source to target Eucledean paths. The empirical results are quite encouraging.

Keywords Microfluidics, Biochips ,Layout, Routing and Algorithms.

1. INTRODUCTION

   Due to the advancements in microfabrication and microelectromechanical systems (MEMS), the microfluidic technology has gained much attention recently. The composite micro-systems could perform conventional biological laboratory procedures on a small and integrated system by manipulating micro-liter or nano-liter fluids. Therefore, the micro-fluidic biochips are used in several common procedures in molecular biology, such as the clinic diagnosis and the DNA sequence analysis. These biochips can be termed as lab-on-a-chip [6] as it replaces highly repetitive laboratory tasks by replacing cumbrous lab equipments with composite micro-system. The advantage of such biochips over huge and heavy systems is that they provide design flexibility, higher sensitivity and are of smaller size and lower cost. They enable the control of micro- or nano-liters of fluids, thus reducing sample size, reagents volume and power consumption.

   Basically, the functioning of a DMFB is based on the principle of electrowetting-on-dielectric (EWOD) [10]. As shown in Fig.1, a biochip consists of an array of electrodes guided by two parallel plates. The top plate is applied a ground voltage and the bottom plate is applied a high voltage to ease the transportation of nanoliter or microliter droplets

   through the arrays. Each parallel plate electrode pair is treated as unit cell in the biochip, as shown in the Fig.2. The small fluidic droplets move from one unit cell to its neighboring unit cell by the application of proper voltage at the bottom plate. The applied voltages are changed according to the need for moving the droplets from one electrode to the other, and the process can be controlled by a processor of predefined clock frequency that determines the velocity of movement of the droplets [12]. Recently, [7] described a coplanar microfluidic device, which is an array without a top plate.

   Due to their digital nature, any operation on droplets can be accomplished with a set of library operations like VLSI standard library, controlling a droplet by applying a sequence of preprogrammed electric signals (Actuation sequences) [5]. Therefore, a hierarchical cell-based design methodology can be applied to a DMFB. Thus, a natural consequence of this is that large scale complex DMFB can be designed as done in VLSI, once strong CAD frameworks are ready. However, CAD research for DMFB design has started very recently. In [12], the first top down methodology for a DMFB is proposed, which mainly consists of architecture level synthesis and geometry-level synthesis.

   Fig 1: Schematic of assembled Digital microfluidic EWOD Chip [18]

   Fig 2: Unit cell of a DMFB [2]

   The geometry-level synthesis in DMFBs broadly involves module placement and droplet routing. During module placement, the location of each module is determined to

   minimize chip area or response time. In droplet routing, the path of each droplet transports it without any unexpected mixture under design requirements. As in the module placement, a cell can be used to transport different droplets during different time intervals (time-multiplexing), which increases the complexity of routing. The most critical goal of droplet routing is routability as in VLSI [17], while satisfying timing constraint and maximizing fault tolerance [6]. Synthesis procedure of digital microfluidic biochip involves optimization of certain cost functions under some resource constraints [12]. During placement of cells, area optimization as well as resource sharing is essential for easier subsequent phases. Typically, in droplet routing, some of the parameters optimized are the throughput, time and resource utilization.

   The rest of the paper is organized in the following manner. Section II discusses the related works available in existing literature, and Section III summarizes the major contributions of our work. Section IV discusses some preliminary concepts related to droplet routing. Section V introduces the problem formulation while Section VI discusses the proposed Algorithm along with an example of 2-pin net. Section VII summarizes the results, and Section VIII makes the concluding remarks.

2. RELATED WORKS

   Recently digital microfuidic biochip integration has been a major research area and designers attempt for optimization of the ever increasing complex design [11].

   Droplet routing is a critical step in Biochip design automation deciding the performance of the system to a great extent. Several droplet routing algorithms have been proposed so far. A graph coloring approach was proposed in [3], which is applied to each successive cycle of direct addressing solution. In this work direct addressing was defined as the control mechanism of droplet movement over the electrodes by direct addressing of the micro-controller control unit. An acyclic graph was generated based on the movement time of the droplets and coloring was done based on concurrent routing of droplets. Direct addressing method was also used in [16] where the droplet routing problem is mapped into graph clique model. Droplet routing time is optimized by optimal partitioning of the clique model. [9] explored the use of direct addressing mode in their work of routing for biochip, making use of integer linear programming (ILP) approach to solve the problem. In [4], dynamic reconfigurability of the microfluidic array is exploited during run-time. The proposed method starts with an initial placement technique. A series of 2-D placement configurations, in different time spans, is obtained in the module placement phase. Then appropriate routing paths are determined to complete droplet routing. The authors decompose a given problem into a series of subproblems, based on their initial placement and solve them sequentially to find the ultimate solution. [2] proposed a high performance droplet routing algorithm using a grid based representation. Their proposed algorithm initially checks which droplets can be routed freely (without any obstacle or blockage due to other droplets). Then the droplets are arranged to route in parallel without considering blockage. Routing of the remaining droplets is considered in presence of blockage and a concession zone was introduced to

   ascertain feasibility of the routing. Finlly a compaction based algorithm was run to optimize the solution. In [8], a network flow based algorithm was proposed for droplet routing. The proposed method was based on non-intersecting bounding box technique. The bounding box of each net was determined first. Then a non-intersecting set of bounding boxes were chosen to route first. The remaining nets were routed using min-cost max-flow algorithm. [1] proposed an A* search algorithm with stalling. The states of the source- target pairs at different times are differentiated using a graph representation. Then optimal path from source to target was chosen using the A* search algorithm. Pin constraint based biochip design was also proposed in recent past [13]. Main objective of pin-constraint based design technique is to optimize number of control pins by proper modeling of assays and their operations. This also requires scheduling of the bio assays and paths for net routing. A partition-based technique for pin-constraint based design was proposed in [15].

3. CONTRIBUTION OF OUR WORK

   In all previous approaches as stated in Section II concurrent routing is attempted only for those droplets whose paths are clear (i.e. no blockage has been encountered while routing from source to target). Then for those remaining Source- Target pairs which got blocked, the droplets are routed sequentially by making any other source, which blocks the said droplet to stall for certain period of pre-calculated time while the said droplet is cleared off.

   In this paper attempt is made to provide an overall concurrent approach for all sources (whether Stuck, Stalled or clear). Here we consider the EWOD model, and propose a high- performance droplet router for a DMFB. Characteristics of the proposed method are summarized as follows:

   • Concurrent routing of all the droplets between respective source and target electrode pairs along with the most significant path.

   • If more than one droplets are trying to occupy the same cell at the same timestamp, then stalling of droplet is possible until that cell is free.

   • Formation of clusters consisting of a number of droplets which reside closer to each-other and finding a common path for a particular cluster. So that routing for all the droplets within a cluster can be done using only one common path. This reduces total number of cells utilization.

4. DROPLET ROUTING FOR DMFB

   The goal of droplet routing in a DMFB is to find an efficient schedule for each droplet, which transports it from its source(s) to target(s), while satisfying all the constraints. This appears to be similar to VLSI routing where wires need to be connected under design rules. However, DMFB routing differs from VLSI routing in the following ways:

   • DMFB routing allows multiple droplets to share the same spot during different time intervals [1, 4] like time division multiplexing. VLSI routing, on the

     other hand, makes one single wire permanently and exclusively occupy the routing area.

   • DMFB routing allows a droplet to stall or stand-by at a spot, if needed.

   • VLSI routing requires 2D spacing by design rules, but DMFB routing needs 3D spacing by dynamic and static fluidic constraints.

     The droplet routing problem in DMFBs is typically modeled in terms of a 2D-grid (see Fig 3). For each droplet, there exists a set of source grid locations, and a set of target grid locations. Objective is to route every droplet, if feasible, from its source location to its target location, subject to several constraints. Some of these constraints are discussed below. For a successful droplet routing, a minimum spacing between droplets must be maintained to prevent accidental mixing. In some cases, however, such as in 3-terminal nets, droplet merging is desired. Thus, the microfluidic modules placed on the array are considered as obstacles in droplet routing. In order to avoid conflicts between droplet routes and assay operations, a segregation region may be considered around the functional region of microfluidic modules. In this way, droplet routing can easily be isolated from active microfluidic modules. For multiple droplet routes that may intersect or overlap with each other, fluidic constraint rules must be introduced to avoid undesirable behavior. To optimize droplet movement and their reachability at the target cells, the droplets move concurrently in time-multiplexed manner. Since all the droplets are moving in parallel, there can be unwanted mixtures if their keep-off distance is not observed.

     Let xi(t) and yi(t) denote the location of droplet, Di at time t. Suppose we have two droplets Di and Dj initially at time t. To avoid mixing of these two droplets they must not be located adjacent or diagonally adjacent to each other. Therefore at time t, We must ensure that either |xi(t) xj(t)| 2 or |yi(t) yj(t)| 2 for these two droplets. This constraint is generally called Fluidic constraint [2], should be satisfied for any time t during routing.

   • Static constraint: | xti xtj | 2 or | yti ytj | 2

   • Dynamic constraint: | xt+1i xtj | 2 or | yt+1i ytj | 2

   Or | xti xt+1j | 2 or | yti yt+1j | 2.

5. PROBLEM FORMULATION

   Droplet routing in DMFB attempts to optimize number of electrodes used to route all the droplets from source to target and the droplet routing time [12]. These two optimized parameters in turn optimize area, routability and throughput. The droplet routing problem can be formulated as follows:

   Given a two-dimensional array of electrodes placed over a square microfluidic biochip (a square layout area) as shown in Fig. 3, and the source-target locations (pair of array cells) of the droplets, we have to establish the possible shortest paths between the source and target locations for each droplet taking into consideration the fluidic constraints mentioned in Section 4. A successful droplet routing (referred to as a net) establishes routing path between source and target locations of all the droplets with minimum usage of electrodes available to them.

   With this problem formulation we propose a novel technique to solve droplet routing problems in the subsequent Section. The novelty of our approach is in the overall concurrent approach for all sources (whether Stuck, Stalled or Cleared). In the process, in certain cases (specifically when more blocked sources are encountered), an improvement in Total Routing time has been observed. However in some cases the number of cells covered may be marginally increased due to larger number of occurrences of detours in the concurrent approach.

6. ALGORITHM

   1. For each droplet (Di) , calculate the Euclidean distance from source Si to target Ti. for all ,0<i<n.

   2. Form clusters consisting of droplets which reside closer to each-other.

   3. For each cluster (Ci), assign priority in terms of total no. of droplets within a cluster.(the cluster which contains max. no. of droplets should be given 1st priority and so on). All droplets within a cluster will be assigned to same priority.

      1. If several clusters have same number of droplets then the cluster which have maximum source- target pair distance should be given higher priority than the next.

   4. For each cluster Ci try to find a common path (the path which covers maximum source-target pair distance within a cluster should be considered as the common path of that cluster).

      1. For each droplet Di try to route towards the tar- get Ti using that common path incrementing their timestamps (timestamp for each droplet initially assigned to 0) using Sukups algorithm [19].

         1. For each cell check whether there is a blockage to the next cell towards that path. If exists, avoid that cell and take a different cell. If the new cell also has a blockage then try to backtrack.

         2. For each cell check whether there is a collision or not. If yes then stall the loer priority droplet and increment timestamp for the higher priority droplet until that collision has been avoided. If still it is not possible to avoid collision within that selected path, then take a different path and repeat step 4(a).

   5. Finally, calculate the maximum timestamp to route from Si to Ti , which is the overall time and (total no. of used cells-2*total number of source-target pairs), which is the total cells utilization.

   Thereby all the source target pairs are routed with concurrent effect and the Maximum timestamp (which provides the latest Arrival time) as well as the path length (in terms of Number of cells) has been considerably reduced.

   A. An Example

   Let us consider a 2-pin network with 2 blockages and 2 source-target pairs {S1,T1} and {S2,T2}, as shown in Fig 3, assuming that both S1 and S2 belongs to the same cluster. As we mentioned that the common path within a cluster should be that one which have maximum source-target pair distance. Here maximum distance occupied by {S1,T1} pair, so this will be considered as the common path for both source-target pairs.

   To route both the droplets concurrently within a cluster using the selected common path, we use Sukups algorithm[19].Here the source-target pair distance for S1 to T1 is maximum so that the path from S1 to T1 should be selected as the common path. Now we start from timestamp 0 for both the droplets. When the timestamp switches from 0 to 1, S1 moves to the next cell towards direction of the target, but S2 cannot switch to the next cell because there is a violation of the fluidic constraint. Hence, S2 has to wait (stall) at that position for that many timestamps until fluidic constraint is satisfied. When the timestamp switches from 1 to 2, S1 will move to the next cell and S2 also moves from initial position to the next cell since there is no violation of fluidic constraint. When timestamps for both the droplets are at 3, S2 moves towards the direction of its target since it has a clear path and S1 finds the common path. Now S2 has to move towards the direction of the target using this common path (at timestamp 4).Similarly, at timestamp 4, the path of S1 towards the target is blocked. So it has to select another cell towards the direction of the target (at timestamp 5). At timestamp 6 S1 will get the actual path through which it started to route. In this manner the overall routing for both the droplets is made concurrently.

   Fig 3: Routing of a 2-pin net considering 2 source-target pairs

   Fig 3: Routing of a 2-pin net considering 2 source-target pairs

   Finally, at timestamp 6, S2 finds its target column and at timestamp 7 its target has been achieved. Hence, the Latest Arrival Time for {S2,T2} is 7 and total number of cells used to route from S2 to T2 is 7.

   Similarly, at timestamp 9, S1 finds its target column and at timestamp 12 its target has been achieved. Hence, the Latest

   Arrival Time for {S1,T1} is 12 and total number of cells used to route from S1 to T1 is 13.

   Now, we can easily find the overall time to route both the droplets concurrently and overall cell utilization as-

   Overall Time = Maximum {S1 to T1, S2 to T2}

   = Maximum {12, 7} = 12

   Overall cell utilization = {total no. of used cells – 2*total

   number of source-target pairs}

   = {16 (2 * 2) } = 12

7. EXPERIMENTAL RESULTS

   The droplet routing algorithm has been applied on Benchmark Suite 2 [2] with the hardest test bench cases. The source and target with obstacle layout along with final route table (Table 1, Table 2) is shown below for two sample test cases.

   In Fig.4 and Fig.5 , # implies Blockage, Si implies

   Source[i] and Ti implies Target[i].

   It is found that the latest arrival times corresponding to all the tests are reduced considerably as compared with other algorithms [2]. Secondly, there is no failure in routing of droplets in all the cases as it occurs in some of the cases in other algorithms.

   Finally ,the number of electrode usage has been marginally increased in some of the cases , reason being a trade off is made between stalling and detouring , causing higher level of reduction in overall time whereas increase in number of detouring, which results in marginal increase in electrode usage.

   Fig 4. Layout for Test 3

   Table 1. Detailed result for Test 3 with Overall Time = 16 and Overall Cell Utilization = 54

   Fig 5. Layout for Test 4

   Table 2. Detailed result for Test 4 with Overall Time = 15 and Overall Cell Utilization = 52

8. CONCLUSION

The observations made in this paper reveal that the proposed algorithm provides considerable improvement in latest arrival time for concurrent routing for multiple nets (source- target pairs) .The algorithm is tested on Benchmark suite 2 which is designed for 2 pin nets. The proposed algorithm can be extended for 3 pin nets and multiple pin nets.

REFERENCES

1. Boahringer. K. F. Modeling and controlling parallel tasks in droplet based microfluidic systems. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 25(2):334 – 344, February 2006.

2. Cho Minsik and Pan. David Z. A high-performance droplet routing algorithm for digital microfluidic biochips. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 27(10):406-419, October 2008.

3. Akella S. Griffith E. J. and Goldberg. M. K. Performance characterization of a reconfigurable planar-array digital microfluidic system. IEEE Transactions Computer-Aided Design

   of Integrated Circuits and Systems, 25(10):340-352, February 2006.

4. Hwang William,Su Fei and Chakrabarty Krishnendu. Droplet routing in the synthesis of digital microfluidic biochips. In Proceedings of Design Automation and Test in Europe, 2006.

5. Zeng X., Liu L.Wu, J ,Yue. R. Droplets Actuating Chip Based On EWOD. Springer-Verlog, 2007.

6. Mukherjee. T. Design automation issues for biofluidic microchips. In Proceedings of International Conference on Computer Aided Design, page 463 – 470, November 2005.

7. Pollack M.G, Paik P,Pamula V.K and Chakrabarty K. Coplanar digital microfluidics using standard printed circuit board Processes.In Proceedings of in MicroTAS, 2005.

8. Yang C.L, Yuh P.H. and Chang. Y.W.Bioroute: A networkflow based routing algorithm for digital microfluidic biochips. In Proceedings of IEEE/ACM InternationalConference o Computer Aided Design, pages 752-757, 2007.

9. Yang Chia-Lin,Chang Yao-Wen,Yuh Ping-Hung, Sapatnekar Sachin. A progressive-ilp based routing algorithm for Crossreferencing biochips. In Proceedings of Design Automation Conference, pages 284 – 289, June 2008.

10. Ren H., Paik P, Pamula V. K, Fair R. B., Srinivasan V. and Pollack.M.G. Electrowetting-based on-chip sample processing for integrated microfluidics. In Proceedings of IEEE International Electron Devices Meeting (IEDM), pages 32.5.1-32.5.4, 2003.

11. Tailor T.D.,Ivanov V.,Evans R. D., Griffin P. B., Srinivasan,V.Pamula V. K., Pollack M. G. Fair R. B. , Khlystov A.and Zhou J.. Chemical and biological applications of digital- microfluidic devices. IEEE Design and Test for Computers, 24:10-24, 2007.

12. Su Fei and Chakrabarty Krishnendu. Architectural-Level synthesis of digital microfluidics-based biochips. In Proceedings of IEEE International Conference on CAD, pages 223-228,2004

13. Su F, Xu T. , Hwang W. and Chakrabarty. K. Automated design of pin-constrained digital microfluidic biochips under droplet- interference constraints. ACM Journal on Emerging Technologies in Computing Systems, 3(14), 2007.

14. Rivest Robert L., Cormen Thomas H, Leiserson. Charles E.

    Introduction to Algorithms. MIT, 1990.

15. Xu T. and Chakrabarty. K. Droplet-trace-based array partitioning and a pin assignment algorithm for the automated design of digital microfuidic biochips. In Proceedings of IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis, pages 112-117, 2006.

16. Xu T. and Chakrabarty. K. A cross-referencing-based droplet manipulation method for high-throughput and pin- constraineddigital microfluidic arrays. In Proceedings of Design Automation and Test in Europe, pages 552 – 557, April 2007.

17. Xu T. and Chakrabarty. K. Integrated droplet routing in the synthesis of microfluidic biochips. In Proceedings of Design Automation Conference, pages 948 – 953, 2007.

18. Paik Philip. Y., Pamula Vamsee K. and Chakrabarty Krishnendu, Adaptive Cooling of Integrated Circuits Using Digital Microfluidics IEEE Transactions on Very Large Scale Integration(VLSI) Systems, vol. 16, no. 4, April 2008.

19. Soukup J,Fast Maze Router Proceedings of the 15thACM IEEE Design Automation Conference, Pages 100-102,1978