Tabu search-based synthesis of dynamically reconfigurable digital microfluidic biochips

ABSTRACT

Microfluidic biochips are replacing the conventional biochemical analyzers, and are able to integrate on-chip all the necessary functions for biochemical analysis. The "digital" microfluidic biochips are manipulating liquids not as a continuous flow, but as discrete droplets, and hence they are highly reconfigurable and scalable. A digital biochip is composed of a two-dimensional array of cells, together with reservoirs for storing the samples and reagents. Several adjacent cells are dynamically grouped to form a virtual device, on which operations are executed. During the execution of an operation, the virtual device can be reconfigured to occupy a different group of cells on the array. In this paper, we present a Tabu Search metaheuristic for the synthesis of digital microfluidic biochips, which, starting from a biochemical application and a given biochip architecture, determines the allocation, resource binding, scheduling and placement of the operations in the application. In our approach, we consider moving the modules during their operation, in order to improve the completion time of the biochemical application. The proposed heuristic has been evaluated using three real-life case studies and ten synthetic benchmarks.

REFERENCES

• 1: Advanced Liquid Logic. http://www.liquid--logic.com/technology.html.
• 2: K. Bazargan, R. Kastner, and M. Sarrafzadeh. Fast template placement for reconfigurable computing systems. IEEE Design and Test of Computers, 17(1):68--83, 2000.
• 3: K. Chakrabarty and J.Zeng. Design automation methods and tools for microfluidic-based biochips. Springer, 2006.
• 4: K. Chakrabarty and F. Su. Digital Microfluidic Biochips: Synthesis, Testing, and Reconfiguration Techniques. CRC Press, Boca Raton, FL, 2006.
• 5: K. Chakrabarty and J. Zeng. Design automation for microfluidics-based biochips. ACM Journal on Emerging Technologies in Computing Systems,1(3):186--223, 2005.
• 6: M. Cho and D. Z. Pan. A high-performance droplet router for digital microfluidic biochips. In Proceedings of International Symposium on Physical Design, pages 200--206, 2008.
• 7: R. P. Dick, D. L. Rhodes, and W. Wolf. TGFF: task graphs for free. In Proceedings of the Sixth International Workshop on Hardware/Software Codesign, pages 97--101, 1998.
• 8: R. B. Fair. Digital microfluidics: is a true lab-on-a-chip possible? Microfluidics and Nanofluidics, 3(3):245--281, 2007.
• 9: F. Glover and M.Laguna. Tabu Search. Kluwer Academic Publishers, 1997.
• 10: E. Maftei, P. Paul, J. Madsen, and T. Stidsen. Placement-aware architectural synthesis of digital microfluidic biochips using ILP. In Proceedings of the International Conference on Very Large Scale Integration of System on Chip, pages 425--430, 2008.
• 11: E. Maftei, P. Paul, and F. P. Vladicescu. Synthesis of reliable digital microfluidic biochips using Monte Carlo simulation. In Proceedings of the European Safety and Reliability Conference, pages 2333--2341, 2008.
• 12: G. D. Micheli. Synthesis and Optimization of Digital Circuits. McGraw-Hill Science, 1994.
• 13: M. G. Pollack, A. D. Shenderov, and R. B. Fair. Electrowetting-based actuation of droplets for integrated microfluidics. Lab Chip Journal, 2:96--101, 2002.
• 14: H. Ren, V. Srinivasan, and R. B. Fair. Design and testing of an interpolating mixing architecture for electrowetting-based droplet-on-chip chemical dilution. In Proceedings of the International Conference on Transducers, Solid-State Sensors, Actuators and Microsystems, pages 619--622, 2003.
• 15: Silicon Biosystems. http://www.siliconbiosystems.com.
• 16: F. Su and K. Chakrabarty. Architectural-level synthesis of digital microfluidics-based biochips. In Proceedings of International Conference on Computer Aided Design, pages 223--228, 2004.
• 17: F. Su and K. Chakrabarty. Unified high-level synthesis and module placement for defect-tolerant microfluidic biochips. In Proceedings of the 42nd annual conference on Design automation, pages 825--830, 2005.
• 18: F. Su and K. Chakrabarty. Module placement for fault-tolerant microfluidics-based biochips. ACM Transactions on Design Automation of Electronic Systems, 11(3):682--710, 2006.
• 19: F. Su, W. Hwang, and K. Chakrabarty. Droplet routing in the synthesis of digital microfluidic biochips. In Proceedings of Design, Automation and Test in Europe, volume 1, pages 73--78, 2006.
• 20: T. Thorsen, S. Maerkl, and S. Quake. Microfluidic largescale integration. Sci., 298:580--584, 2002.
• 21: D. Ullman. NP-complete scheduling problems. Journal of Computing System Science, 10:384--393, 1975.
• 22: T. Xu and K. Chakrabarty. Integrated droplet routing and defect tolerance in the synthesis of digital microfluidic biochips. In Proceedings of Design Automation Conference, pages 948--953, 2007.
• 23: P. H. Yuh, S. Sapatnekar, C.-L. Yang, and Y.-W. Chang. A progressive-ILP based routing algorithm for cross-referencing biochips. In Proceedings of Design Automation Conference, pages 284--289, 2008.
• 24: P. H. Yuh, C.L. Yang, and Y.W. Chang. Temporal floorplanning using the T-tree formulation. In Proceedings of International Conference on Computer Aided Design, pages 300--305, 2004.
• 25: P. H. Yuh, C. L. Yang, and Y. W. Chang. Placement of digital microfluidic biochips using the T-tree formulation. In Proceedings of Design Automation Conference, pages 931--934, 2006.
• 26: P.H. Yuh, C.L. Yang, and Y.W. Chang. Placement of defect-tolerant digital microfluidic biochips using the T-tree formulation. ACM Journal on Emerging Technologies in Computing Systems, 3(3), 2007.
• 27: P.H. Yuh, C.L. Yang, Y.W. Chang, and H.L. Chen. Temporal floorplanning using three dimensional transitive closure subGraph. ACM Transactions on Design Automation of Electronic Systems, 12(4), 2007.
• 28: Y. Zhao and K. Chakrabarty. Cross-contamination avoidance for droplet routing in digital microfluidic biochips. In Proc. Des., Automat. Test Conf., pages 1290--1296, 2009.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Performance

Keywords:
biochips, microfluidics, reconfigurability