Unified high-level synthesis and module placement for defect-tolerant microfluidic biochips

ABSTRACT

Microfluidic biochips promise to revolutionize biosensing and clinical diagnostics. As more bioassays are executed concurrently on a biochip, system integration and design complexity are expected to increase dramatically. This problem is also identified by the 2003 ITRS document as a major system-level design challenge beyond 2009. We focus here on the automated design of droplet-based microfluidic biochips. We present a synthesis methodology that unifies operation scheduling, resource binding, and module placement for such "digital" biochips. The proposed technique, which is based on parallel recombinative simulated annealing, can also be used after fabrication to bypass defective cells in the microfluidic array. A real-life protein assay is used to evaluate the synthesis methodology.

REFERENCES

• 1: R. B. Fair et al., "Electrowetting-based on-chip sample processing for integrated microfluidics", Proc. IEDM, pp. 32.5.1--32.5.4, 2003.
• 2: International Technology Roadmap for Semiconductors (ITRS), http://public.itrs.net/Files/2003ITRS/Home2003.htm.
• 3: J. Zeng and T. Korsmeyer, "Principles of droplet electrohydrodynamics for lab-on-a-chip", Lab on a Chip, pp. 265--277, 2004.
• 4: 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]
• 5: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 6: 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]
• 7: Kia Bazargan , Seda Ogrenci , Majid Sarrafzadeh, Integrating scheduling and physical design into a coherent compilation cycle for reconfigurable computing architectures, Proceedings of the 38th conference on Design automation, p.635-640, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379038]
• 8: Israel Koren , Adit D. Singh, Fault Tolerance in VLSI Circuits, Computer, v.23 n.7, p.73-83, July 1990 [doi>10.1109/2.56854]
• 9: G. Li and N. Aluru, "Efficient mixed-domain analysis of electrostatic MEMS", IEEE Trans. CAD, vol. 22, pp. 1228--1242, 2003.
• 10: T. Mukherjee and G. K. Fedder, "Design methodology for mixed-domain systems-on-a-chip {MEMS design}", Proc. IEEE VLSI System Level Design, pp. 96--101, 1998.
• 11: S. K. Tewksbury, Challenges Facing Practical DFT for MEMS, Proceedings of the 16th IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems, p.11-17, October 24-26, 2001
• 12: T. Zhang et al., Microelectrofluidic Systems: Modeling and Simulation, CRC Press, Boca Raton, FL, 2002.
• 13: V. Srinivasan et al., "Protein stamping for MALDI mass spectrometry using an electrowetting-based microfluidic platform", Proc. SPIE, vol. 5591, pp. 26--32, 2004.
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Samir W. Mahfoud , David E. Goldberg, Parallel recombinative simulated annealing: a genetic algorithm, Parallel Computing, v.21 n.1, p.1-28, Jan. 1995 [doi>10.1016/0167-8191(94)00071-H]
• 16: J. C. Bean, "Genetics and random keys for sequencing and optimization", ORSA J. Computing, vol. 6, pp. 154--160, 1994.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.3 Reliability and Testing**

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
biochip, defect tolerance, microfluidics, placement, synthesis