The Computer Engineering and Systems Group (CESG) Department of Electrical and Computer Engineering

Publications

Papers

The materials are presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. My main research is in Electronic Design Automation (EDA) though I also work on algorithms and computational complexy when the problems involve deep theory and have potential applications beyond EDA. Some papers are simultaneously listed in two categories because of the overlap.

 

Layout Synthesis

  • P. Pan, W. Shi and C. L. Liu, “Area minimization for hierarchical floorplans,” Proceedings of ACM/IEEE International Conference on Computer-Aided Design (ICCAD), Santa Clara, CA, Nov. 1994, pp. 436-440.
  • W. Shi, “An optimal algorithm for area minimization of slicing floorplans,” Proceedings of ACM/IEEE International Conference on Computer-Aided Design (ICCAD), San Jose, CA, Nov. 1995, pp. 480-484.
  • P. Pan, W. Shi and C. L. Liu, “Area minimization for hierarchical floorplans,” Algorithmica, Vol. 15, No. 6, June 1996, pp. 550-571.
  • W. Shi, “A fast algorithm for area minimization of slicing floorplans”, IEEE Transactions on Computer-Aided Design of Integraetd Circuits and Systems, Vol. 15, No. 12, Dec. 1996, pp. 1525-1532. IEEE Explore
  • W. Shi and C. Su, “The rectilinear Steiner arborescence problem is NP-complete”, Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), San Fransisco, CA, Jan. 2000, pp. 780-787.
  • W. Shi and Z. Li, “An O(nlogn) time algorithm for optimal buffer insertion”, Proceedings of 40th Design Automation Conference (DAC), Anaheim, CA, June 2003, pp. 580-585.
  • W. Qiu and W. Shi, “Minimum moment Steiner trees”, Proceedings of 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, Jan 2004, pp. 481-488.
  • W. Shi, Z. Li and C. Alpert, “Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost”, Proceedings of 2004 Asia and South Pacific Design Automation Conference (ASP-DAC), Yokohama, Japan, Jan. 2004, pp. 609-614.
  • Z. Li, C.-N. Sze, C. J. Alpert, J. Hu and W. Shi, “Making fast buffer insertion even faster via approximation techniques”, Proceedings of 2005 Asia and South Pacific Design Automation Conference (ASP-DAC), Shanghai, China, Jan. 2005, pp. 13-18. slides
  • Z. Li and W. Shi, “An O(bn^2) time algorithm for buffer insertion with b buffer types”, Proceedings of 2005 Design, Automation and Test in Europe (DATE), Munich, Germany, March 2005, pp. 1324-1329. Slides
  • C.-N. Sze, C. J. Alpert, J. Hu and W. Shi, “Path based buffer insertion”, Proceedings of 42nd ACM/IEEE Design Automation Conference (DAC), Anaheim, CA, June 2005, pp. 509-514.
  • W. Shi and Z. Li*, “A fast algorithm for optimal buffer insertion”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 6, June 2005, 879-891. * IEEE Circuits and Systems Society 2007 Outstanding Young Author Award
  • Z. Li and W. Shi, “An O(mn) time algorithm for optimal buffer insertion of nets with m sinks”, Proceedings of 2006 Asia and South Pacific Design Automation Conference (ASP-DAC), Yokohama, Japan, Jan. 2006, pp. 320-325. slides.
  • Z. Li and W. Shi, “An O(bn^2) time algorithm for optimal buffer insertion with b buffer types”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 25, No. 3, March 2006, pp. 484-489.
  • W. Shi and C. Su, “The rectilinear Steiner arborescence problem is NP-complete”, SIAM Journal on Computing, Vol. 35, No. 3, 2006, pp. 729-740.
  • S. Hu, C. Alpert, J. Hu, S. Karandikar, Z. Li, W. Shi and C. N. Sze, “Fast algorithms for slew constrained minimum cost buffering”, Proceedings of 43rd Design Automation Conference (DAC), San Francisco, July 2006, pp. 308-313.
  • M. Waghmode, Z. Li and W. Shi, “Buffer insertion in large circuits with constructive solution search techniques”, Proceedings of 43rd Design Automation Conference (DAC), San Francisco, July 2006, pp. 296-301.
  • M. Waghmode, K. Gulati, S. P. Khatri, W. Shi, “An efficient, scalable hardware engine for Boolean satisfiability”, IEEE International Conference on Computer Design (ICCD), San Jose, Oct 2006.
  • Z. Jiang, S. Hu, J. Hu, Z. Li and W. Shi, “A new RLC buffer insertion algorithm”, IEEE International Conference on Computer Aided-Design (ICCAD), San Jose, Nov. 2006, pp. 553-557.
  • Z. Li, C. Alpert, S. Quay, S. Sapatnekar and W. Shi, “Probabilistic congestion prediction with partial blockages”, Proceedings of 8th International Symposium on Quality Electronic Design (ISQED), San Jose, CA, March 2007, pp. 841-846.
  • Z. Jiang, S. Hu, J. Hu and W. Shi, “A linear time algorithm for RLC buffer insertion”, Proceedings of 8th International Symposium on Quality Electronic Design (ISQED), San Jose, CA, March 2007, pp. 171-175.
  • Z. Li, Y. Zhou and W. Shi, “Wire sizing for non-tree topology”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 26, No. 5, May 2007, 872-880.
  • Z. Jiang, S. Hu and W. Shi, “A new twisted differential line structure in global bus design”, 2007 Design Automation Conference, San Diego, CA, June 2007, pp. 180-183.
  • C.-N. Sze, C. J. Alpert, J. Hu and W. Shi, “Path based buffer insertion”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 26, No. 7, July 2007, 1346-1355.
  • Z. Jiang and W. Shi, “Circuit-wise buffer insertion for million plus gates”, TECHCON, Austin, TX, 2007.
  • S. Hu, C. J. Alpert, J. Hu, S. Karandikar, Z. Li, W. Shi and C. N. Sze, “Fast algorithms for slew constrained minimum cost buffering”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 26, No. 11, Nov. 2007, 2009-2022.
  • Y. Liu, J. Hu and W. Shi, “Multi-scenario buffer insertion in multi-core processor designs”, ACM International Symposium on Physical Design (ISPD), 2008, 15-22.
  • Z. Jiang and W. Shi, “Circuit-wise buffer insertion and gate sizing algorithm with scalability”, Design Automation Conference (DAC), Anaheim, CA, June 2008, 708-713.
  • R. Kanj, R. V. Joshi, Z. Li, J. B. Kuang, H. Ngo, Y. Zhou, W. Shi, S. R. Nassif, “SRAM methodology for yield and power efficiency: per-element selectable supplies and memory reconfiguration schemes”, ISLPED 2008, pp. 87-92.
  • Y. Liu, J. Hu and W. Shi, “Buffering interconnect for multicore processor designs”, IEEE Transactions on Computer-Aided Design of Integraetd Circuits and Systems, Vol. 27, No. 12, December 2008, pp. 2183-2196.
  • Z. Li, D. A. Papa, C. J. Alpert, S. Hu, W. Shi, C. C. N. Sze, Y. Zhou, “Ultra-fast interconnect driven cell cloning for minimizing critical path delay”, Proceedings of ACM International Symposium on Physical Design (ISPD), March 2010, pp. 75-82.
  • Y.-L. Huang, J. Hu and W. Shi, “Lagrangian relaxation for gate implementation selection”, Proceedings of ACM International Symposium on Physical Design (ISPD), March 2011.

Modeling and Simulation

    • W. Shi, J. Liu, N. Kakani and T. Yu, “A fast hierarchical algorithm for 3-D capacitance extraction”, Proceedings of 35th Design Automation Conference (DAC), June 1998, San Francisco, CA, pp. 211-217. [DAC slides]. DAC Best Paper Award.
    • W. Shi, J. Liu, N. Kakani and T. Yu, “A fast hierarchical algorithm for 3-D capacitance extraction”, IEEE Transactions on Computer-Aided Design of Integraetd Circuits and Systems, Vol. 21, No. 3, March 2002, pp. 330-336.
    • H. Mahawar, V. Sarin, and W. Shi, “Fast inductance extraction of large VLSI circuits,” Proceedings of 2002 International Parallel and Distributed Processing Symposium (IPDPS) , Fort Lauderdale, FL, April 2002, pp. 415-421.
    • H. Mahawar, V. Sarin and W. Shi, “Solenoidal basis method for efficient inductance extraction”, Proceedings of 39th Design Automation Conference (DAC), New Orleans, LA, June 2002, pp. 751-756.
    • S. Yan, J. Liu and W. Shi, “Improving boundary element methods for parasitic extraction”, Proceedings of 2003 Asia and South Pacific Design Automation Conference (ASP-DAC),Kitakyushu, Japan, Jan. 2003, pp. 261-267.
    • Z. Li, X. Lu and W. Shi, “An algorithm for process variation reduction based on SVD”, Proceedings of 2003 IEEE International Symposium on Circuits and Systems (ISCAS), Bangkok, Thailand, May 2003, Vol. 4, pp. 672-675.
    • F. Yu and W. Shi, “A divide-and-conquer algorithm for 3D capacitance extraction”, Proceedings of 5th International Symposium on Quality Electronic Design (ISQED), San Jose, CA, March 2004, pp. 253-258.
    • X. Lu, Z. Li, W. Qiu, H. Walker and W. Shi, “PARADE: Parametric delay evaluation under process variation”, Proceedings of 5th International Symposium on Quality Electronic Design (ISQED), San Jose, CA, March 2004, pp. 276-280.
    • S. Yan, V. Sarin and W. Shi, “Sparse transformations and preconditioners for hierarchical 3-D capacitance extraction with multiple dielectrics”, Design Automation Conference, San Diego, CA, June 2004, pp. 788-793.
    • W. Shi and F. Yu, “A divide-and-conquer algorithm for 3D capacitance extraction”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 23, No. 8, Aug. 2004, pp. 1157-1163.
    • S. Yan, V. Sarin and W. Shi, “Fast capacitance extraction using inexact factorization” 13th Topical Meeting on Electrical Performance of Electronic Packaging (EPEP), Portland, OR, Oct. 2004, pp. 285-288.
    • S. Yan, V. Sarin and W. Shi, “Sparsification and precondition for capacitance extraction”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 9, Sept. 2005, 1420-1426.
    • Y. Tian, W. Shi and R. Mercer, “Impact of photolithography and mask variability on interconnect parasitics,” Proceedings 25th Annual BACUS Symposium on Photomask Technology,Monterey, California, Oct. 2005.
    • P. Li and W. Shi, “Model order reduction of linear networks with massive ports via frequency-dependent port packing”, Proceedings of 43rd Design Automation Conference (DAC), San Francisco, July 2006, pp. 267-272.
    • Y. Yi, P. Li, V. Sarin and W. Shi, “A preconditioned hierarchical algorithm for impedance extraction of interconnects in packages”, 15th Topical Meeting on Electrical Performance of Electronic Packaging (EPEP), Scottdale, Oct. 2006.
    • S. Yan, V. Sarin and W. Shi, “Fast 3D capacitance extraction by inexact factorization and reduction”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 25, No. 10, Oct. 2006, pp. 2282-2286.
    • Y. Zhou, Z. Li, Y. Tian, W. Shi and F. Liu, “A new methodology for interconnect parasitics extraction considering photo-lithography effects”, Proceedings of 2007 Asia and South Pacific Design Automation Conference (ASP-DAC), Yokohama, Japan, Jan. 2007, pp. 450-455. ASPDAC Best Paper Award
    • Y. Zhou, Z. Li, R. N. Kanj, D. A. Papa, S. Nasiff, W. Shi, “A more effective Ceff for slew estimation”, Proc. International Conference on IC Design and Technology ICIDT, Austin, Texas, May 2007.
    • Y. Zhou, Z. Li and W. Shi, “A hybird BEM algorithm for capacitance extraction in multi-layer, conformal and embedded dielectrics using hybrid boundary element method”, 2007 Design Automation Conference, San Diego, CA, June 2007, pp. 835-840.
    • Y. Yi, P. Li, V. Sarin and W. Shi, “Impedance extraction for 3-D structures with multiple dielectrics using preconditioned boundary element method”, Proceedings of International Conference on Computer-Aided Design (ICCAD), 2007.
    • Y. Yi, S. Yan, V. Sarin, and W. Shi, “Development of fast 3D parasitic extraction using hierarchical method for integrated circuits and packages”, Proceedings of IEEE International Symposium on Antennas and Propagation (AP-S), July 2008, pp. 1-4.
    • Y. Yi, V. Sarin and W. Shi, “An efficient inductance extraction algorithm for 3-D interconnects with frequency dependent nonlinear magnetic materials”, Proceedings of 17th IEEE conference on Electrical Performance of electronic Packaging (EPEP), Oct. 2008, pp. 217-220.
    • Y. Yi, P. Li, V. Sarin and W. Shi, “A preconditioned hierarchical algorithms for impedance extraction for 3-D structures with multiple dielectrics”, IEEE Transactions on Computer-Aided Design of Integraetd Circuits and Systems, Vol. 27, No. 11, November 2008, pp. 1918-1927.
    • U. Doddannagari, S. Hu and W. Shi, “Fast characterization of parameterized cell library”, Proceedings of 2009 International Symposium on Quality Electronic Design (ISQED), San Jose, CA, March 2009.
    • Y. Zhou, R. N. Kanj. Z. Li, W. Shi, S. Nassif, “The impact of BEOL Lithography effects on the SRAM cell performance and yield”, Proceedings of 2009 International Symposium on Quality Electronic Design (ISQED), San Jose, CA, March 2009.
    • Yang Yi, R. Wenzel, Vivek Sarin, and Weiping Shi, “Inductance extraction for interconnects in the presence of nonlinear magnetic materials”, IEEE Transactions on Computer-Aided Design of Integraetd Circuits and Systems, Vol. 28, No. 7, July 2009, pp. 1106-1110.

Testing and Diagnosis

  • M.-F. Chang, W. Shi and W. K. Fuchs, “Optimal wafer probe testing and diagnosis of k-out-of-n structures,” Proceedings of International Conference on Computer-Aided Design (ICCAD),Santa Clara, CA, Nov. 1989, pp. 238-241.
  • M.-F. Chang, W. Shi and W. K. Fuchs, “Optimal diagnosis procedures for k-out-of-n structures,” IEEE Transactions on Computers, Vol. 39, No. 4, April 1990, pp. 559-564.
  • W. Shi and W. K. Fuchs, “Optimal interconnect diagnosis,” Proceedings of IEEE 1993 Asian Test Symposium, Beijing, China, Nov. 1993, pp. 197-200.
  • W. Shi and W. K. Fuchs, “Optimal interconnect diagnosis of wiring networks”, IEEE Transactions on VLSI Systems, Vol. 3, No. 3, Sept. 1995, pp. 430-436. IEEE Explore
  • W. Shi and D. B. West, “Optimal structural diagnosis of wiring networks”, Proceedings of 27th International Symposium on Fault Tolerant Computing (FTCS), Seattle, WA, June 1997, pp. 162-171.
  • Z. Li, X. Lu, W. Qiu, W. Shi and H. Walker, “A circuit level fault model for resistive opens and bridges”, Proceedings of 21st IEEE VLSI Testing Symposium (VTS), Napa Valley, CA, April 2003, pp. 379-384.
  • W. Qiu, Z. Li, X. Lu, W. Shi and H. Walker, “Combined delay fault modeling and simulation,” TECHCON, Dallas, TX, Aug. 2003.
  • W. Qiu, Z. Li, X. Lu, W. Shi and H. Walker, “CodSim: A combined delay fault simulator”, Proceedings of IEEE International Conference on Defect and Fault Tolerance in VLSI Systems, Cambridge, MA, Nov. 2003, pp. 79-86.
  • Y. Tian, M. Grimaila, W. Shi and M. R. Mercer, “Minimizing defective part level using a linear programming based optimal test selection method”, Proceedings of 12th Asian Test Symposium, Xi’an, China, Nov. 2003, pp. 354-359. [IEEE Explore]
  • X. Lu, Z. Li, W. Qiu, W. Shi and H. Walker, “Longest path selection for delay test under process variation”, Proceedings of 2004 Asia and South Pacific Design Automation Conference (ASP-DAC), Yokohama, Japan, Jan. 2004, pp. 98-103.
  • W. Qiu, J. Wang, X. Lu, Z. Li, H. Walker and W. Shi, “At-speed test for path delay faults using practical techniques”, 2004 IEEE International Workshop on Defect Based Testing, Napa Valley, CA, April 2004.
  • W. Qiu, X. Lu, J. Wang, Z. Li, H. Walker and W. Shi, “A statistical fault coverage metric for realistic path delay faults”, Proceedings of 22nd VLSI Testing Symposium (VTS), Napa Valley, CA, April 2004, pp. 37-42.
  • Z. Li, X. Lu, W. Qiu, W. Shi and H. Walker, “A circuit level fault model for resistive opens and bridges”, ACM Transactions on Design Automation of Electronic Systems, Vol. 8, No. 4, Oct. 2003, pp. 546-559.
  • X. Lu, Z. Li, W. Qiu, H. Walker and W. Shi, “A circuit level fault model for resistive MOS gate short”, 5th International Workshop on Microprocessor Test and Verification, Austin, TX, September 2004, pp. 97-102.
  • W. Qiu, J. Wang, D. M. H. Walker, D. Reddy, X. Lu, Z. Li, W. Shi, and H. Balachandran, “K Longest Paths per Gate (KLPG) test generation for scan-based sequential circuits”,Proceedings International Testing Conference (ITC), Charlotte, NC, Oct. 2004, pp. 223-231.
  • J. Wang, X. Lu, W. Qiu, Z. Yue, S. Fancler, W. Shi, and D. M. H. Walker, “Static compaction of delay tests considering power supply noise”, Proceedings of 23rd IEEE VLSI Testing Symposium (VTS), Palm Springs, CA, May 2005, pp. 235-240.
  • J. Wang, Z. Yue, X. Lu, W. Qiu, W. Shi and D. M. H. Walker, “A vector-based approach for power supply noise analysis in test compaction,” Proceedings 36th IEEE International Test Conference (ITC), Austin, TX, Nov., 2005, 517-526.
  • Y. Tian, M. R. Grimaila, W. Shi and M. R. Mercer, “An optimal test pattern selection method to improve the defect coverage,” Proceedings 36th IEEE International Test Conference (ITC), Austin, TX, Nov., 2005, pp. 762-770.
  • X. Lu, Z. Li, W. Qiu, H. Walker, and W. Shi, “Longest path selection for delay test under process variation”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 12, Dec. 2005, pp. 1924-1929.

Defect and Fault Tolerance

  • W. Shi and W. K. Fuchs, “Probabilistic analysis of memory repair and reconfiguration heuristics,” Proceedings of IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, Tampa, FL, Oct. 1989, pp. 185-195.
  • W. Shi and W. K. Fuchs, “Large area defect-tolerance tree architectures,” Proceedings of IEEE International Conference on Wafer Scale Integration, San Francisco, CA, Jan. 1991, pp. 127-133.
  • W. Shi, M.-F. Chang and W. K. Fuchs, “Harvest rate of reconfigurable pipelines,” Proceedings of IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, Hidden Valley, PA, Nov. 1991, pp. 93-102.
  • W. Shi and W. K. Fuchs, “Optimal spare allocation for defect-tolerant VLSI systems,” Proceedings of IEEE International Conference on Wafer Scale Integration, San Francisco, CA, Jan. 1992, pp. 193-199.
  • W. Shi and W. K. Fuchs, “Probabilistic analysis and algorithms for reconfiguration of memory arrays,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 11, No. 9, Sept. 1992, pp. 1153-1160.
  • W. Shi, “A general method to design and reconfigure loop-based linear arrays,” Proceedings of IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, Montreal, Canada, Oct. 1994, pp. 221-229.
  • W. Shi, M.-F. Chang and W. K. Fuchs, “Harvest rate of reconfigurable pipeline processor arrays,” IEEE Transactions on Computers, Vol. 45, No. 10, Oct. 1996, pp. 1200-1203.
  • W. Shi, K. Kumar and F. Lombardi, “On the complexity of switching programming in fault-tolerant configurable chips,” Proceedings of IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, Yamanashi, Japan, Oct. 2000, pp. 125-133.
  • K. Gulati, M. Waghmode, S. P. Khatri and W. Shi, “An efficient, scalable hardware engine for Boolean satisfiability and unsatisfiable core extraction”, IET Computers and Digital Techniques Journal, Vol 2, Number 3, May 2008, pp 214-229.
  • R. Kanj, R. Joshi, Z. Li, J. B. Kuang, N. Zhou, W. Shi, and S. Nassif, “Per-element-based memory supplies and reconfiguration schemes”, 4th Annual Austin Conference on Integrated Systems & Circuits, Oct. 2009.

Theory of Computation

  • H. Edelsbrunner and W. Shi, “An O(nlog^2h) time algorithm for three-dimensional convex hull problem,” SIAM Journal on Computing, Vol. 20, No. 2, April 1991, pp. 249-259.
  • S. Greibach, W. Shi and S. Simonson, “Single tree grammars”, Theoretical Studies in Computer Science, edited by J. D. Ullman, Academic Press, 1992, pp. 73-99.
  • W. Shi and D. B. West, “Optimal algorithms for finding connected components of an unknown graph”, Proceedings of 1st International Conference on Combinatorics and Computing (COCOON), Xian, China, Aug. 1995, Lecture Notes in Computer Science 959, pp. 131-140.
  • F. Shahrarkhi and W. Shi, “Efficient deterministic algorithm for embedding graphs on books”, Proceedings of 2nd International Conference on Combinatorics and Computing (COCOON), Hong Kong, June 1996, Lecture Notes in Computer Science 1090, pp. 162-168.
  • W. Shi and D. B. West, “Diagnosis of wiring networks: An optimal randomized algorithm for finding connected components of unknown graphs”, SIAM Journal on Computing, Vol. 28, No. 5, 1999, pp. 1541-1551. SIAM Journal Online
  • W. Shi and C. Su, “The rectilinear Steiner arborescence problem is NP-complete”, Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), San Fransisco, CA, Jan. 2000, pp. 780-787.
  • F. Shahrokhi and W. Shi, “On crossing sets, disjoint sets and page number”, Journal of Algorithms, Vol. 34, No. 1, Jan. 2000, pp. 40-53. [Ideal Library]
  • W. Shi and D. West, “Structural diagnosis of wiring networks: Finding connected components of unknown subgraphs”, SIAM Journal on Discrete Mathematics, Vol. 14, No. 4, Oct. 2001, pp. 510-523. [SIAM Journal Online]
  • W. Qiu and W. Shi, “Minimum moment Steiner trees”, Proceedings of 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, Jan 2004, pp. 481-488.
  • W. Shi and C. Su, “The rectilinear Steiner arborescence problem is NP-complete”, SIAM Journal on Computing, Vol. 35, No. 3, 2006, pp. 729-740.