Placement of defect-tolerant digital microfluidic biochips using the T-tree formulation

ABSTRACT

Droplet-based microfluidic biochips have recently gained much attention and are expected to revolutionize the biological laboratory procedures. As biochips are adopted for the complex procedures in molecular biology, its complexity is expected to increase due to the need of multiple and concurrent assays on a chip. In this article, we formulate the placement problem of digital microfluidic biochips with a tree-based topological representation, called T-tree. To the best knowledge of the authors, this is the first work that adopts a topological representation to solve the placement problem of digital microfluidic biochips. We also consider the defect tolerant issue to avoid to use defective cells due to fabrication. Experimental results demonstrate that our approach is more efficient and effective than the previous unified synthesis and placement framework.

REFERENCES

• 1: Kiarash Bazargan , Ryan Kastner , Majid Sarrafzadeh, Fast Template Placement for Reconfigurable Computing Systems, IEEE Design & Test, v.17 n.1, p.68-83, January 2000 [doi>10.1109/54.825678]
• 2: Lei Cheng , Liang Deng , Martin D. F. Wong, Floorplanning for 3-D VLSI design, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120899]
• 3: Ding, J., Chakrabarty, K., and Fair, R. B. 2001. Scheduling of microfluidic operations for reconfigurable two-dimensional electrowetting arrays. IEEE Trans. Comput. Aid. Design Integrat. Circ. Syst. 20, 1463--1468.
• 4: William E. Dougherty , Donald E. Thomas, Unifying behavioral synthesis and physical design, Proceedings of the 37th conference on Design automation, p.756-761, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337769]
• 5: Fair, R. B., Srinivasan, V., Ren, H., Paik, P., Pamula, V., and Pollack, M. 2003. Electrowetting-based on-chip sample processing for integrated microfluidics. In Proceedings of IEEE International Electron Device Meeting. 32.5.1--32.5.4.
• 6: S. Fekete , E. Köhler , J. Teich, Optimal FPGA module placement with temporal precedence constraints, Proceedings of the conference on Design, automation and test in Europe, p.658-667, March 2001, Munich, Germany
• 7: Brent Goplen , Sachin Sapatnekar, Efficient Thermal Placement of Standard Cells in 3D ICs using a Force Directed Approach, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.86, November 09-13, 2003 [doi>10.1109/ICCAD.2003.60]
• 8: Zhenyu (Peter) Gu , Jia Wang , Robert P. Dick , Hai Zhou, Incremental exploration of the combined physical and behavioral design space, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065635]
• 9: ITRS. The international technoloy roadmap for semiconductors: http://public.itrs.net/.
• 10: Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, 4598 (May), 671--680.
• 11: Jai-Ming Lin , Yao-Wen Chang, TCG: a transitive closure graph-based representation for non-slicing floorplans, Proceedings of the 38th conference on Design automation, p.764-769, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379062]
• 12: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 13: Stefan Thomas Obenaus , Ted H. Szymanski, Gravity: Fast placement for 3-D VLSI, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.298-315, July 2003 [doi>10.1145/785411.785413]
• 14: Andrew J. Ricketts , Kevin Irick , N. Vijaykrishnan , Mary Jane Irwin, Priority scheduling in digital microfluidics-based biochips, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 15: Srinivasan, V., Pamula, V., Paik, P., and Fair, R. 2004. Protein stamping for maldi mass spectrometry using an electrowetting-based microfluidic platform. In Proceedings of the International Society for Optical Engineering. 26--32.
• 16: Fei Su , K. Chakrabarty, Architectural-level synthesis of digital microfluidics-based biochips, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.223-228, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382576]
• 17: Fei Su , Krishnendu Chakrabarty, Design of Fault-Tolerant and Dynamically-Reconfigurable Microfluidic Biochips, Proceedings of the conference on Design, Automation and Test in Europe, p.1202-1207, March 07-11, 2005 [doi>10.1109/DATE.2005.115]
• 18: Fei Su , Krishnendu Chakrabarty, Unified high-level synthesis and module placement for defect-tolerant microfluidic biochips, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065797]
• 19: Su, F., Chakrabarty, K., and Fair, R. B. 2006. Micrpfluidic-based biochips: technology issues, implementation platforms, and design-automation challenges. IEEE Trans. Comput.-Aid. Design Integrat. Circ. Syst. 25, 4, 211--223.
• 20: tutorgig. http://www.tutorgig.com/encyclopedia.
• 21: D. F. Wong , C. L. Liu, A new algorithm for floorplan design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.101-107, July 1986, Las Vegas, Nevada, United States
• 22: Jen-Yi Wuu , Tung-Chieh Chen , Yao-Wen Chang, SoC test scheduling using the B-tree based floorplanning technique, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120937]
• 23: Yu Xia , Malgorzata Chrzanowska-Jeske , Benyi Wang , Marcin Jeske, Using a Distributed Rectangle Bin-Packing Approach for Core-based SoC Test Scheduling with Power Constraints, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.100, November 09-13, 2003 [doi>10.1109/ICCAD.2003.148]
• 24: Yamazaki, H., Sakanushi, K., Nakatake, S., and Kajitani, Y. 2000. 3d-packing by meta data structure and packing heuristics. IEICE Trans. Fundam. Electr. Commun. Comput. Science E83-A, 4, 639--645.
• 25: Ping-Hung Yuh , Chia-Lin Yang , Yao-Wen Chang, Temporal floorplanning using the T-tree formulation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.300-305, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382590]
• 26: Ping-Hung Yuh , Chia-Lin Yang , Yao-Wen Chang , Hsin-Lung Chen, Temporal floorplanning using 3D-subTCG, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
Microfluidics, biochip, placement