UCSD VLSI CAD Laboratory

Areas of Interest

VLSI CAD, combinatorial algorithms, bioinformatics

Biographical Sketch

Qinke Wang (b. Dec. 1976, DaLian, P.R. China) received from Tsinghua University a M.S. in Computer Software in 2001 and a B.S. in Computer Science and Technology in 1998. He joined the Computer Science Department at UCSD in Sep. 2001, is a graduate research assistant in the field of VLSI CAD under Prof. Andrew B. Kahng since Sep. 2002, and is expected to receive a Ph.D. degree in Computer Science in June. 2006. Qinke Wang received a Jacob Fellowship in 2001, ICCD2005 Best Paper award, ICCAD2005 Best Paper nomination, and First Place of the ISPD2005 placement contest. His research interests include VLSI physical design and VLSI design-manufacturing interface, and is open to new research ideas.

CV/Resume.

Overview of Research

The foci of Qinke's past researches are on (i) analytical framework of circuit placement with constrained nonlinear optimization techniques and its extensions to a variety of placement tasks across many aspects of physical implementation, (ii) optimization during circuit placement for chip manufacturability and yield, (iii) detailed placement algorithm, (iv) optimization of production cost (mask and reticle cost) related to multi-project wafers, (v) planning of hierarchical, uniform power distribution in early design stages, with optimization for worst IR-drop or total metal area, and (vi) analysis of key deployment and methodology issues associated with the Y-architecture, a novel architecture for on-chip interconnect with three uniform routing directions.

(1) APlace: A General Analytic Placement Framework.

Analytical placement methods have received increased attention from both academia and industry in recent years. We propose and implement APlace, a general analytical placement framework, which has high solution quality and strong extensibility.

APlace regards global placement as a constrained nonlinear optimization problem: APlace divides the placement area into uniform grids, and seek to minimize certain placement objectives such as total half-perimeter wirelength (HPWL) under the constraint that total module area in every grid is equalized. APlace applies smooth approximations of placement objectives and density control function and solves the constrained optimization problem using the simple Quadratic Penalty method and a Conjugate Gradient solver.

The general APlace framework has been extended to address a variety of placement tasks across many aspects of physical implementation, such as mixed-size placement, timing-driven placement, power-aware placement, voltage-drop-aware placement, aberration-aware timing-driven placement and I/O-core co-placement, and is shown to be competitive in a wide variety of contexts. Recently, APlace won the First Place of ISPD05 Placement Contest.

We have published seven conference papers at ISPD04, ICCAD04, ISPD05, DAC05, ICCD05, ICCAD05 and DATE06 in this area and a journal version at TCAD05, and have submitted one journal version to JEA. Among them, the ICCAD05 paper is a Best Paper nominee.

(2) Supply Voltage Degradation Aware Analytical Placement.

Increasingly significant power/ground supply voltage degradation in nanometer VLSI designs leads to system performance degradation and even malfunction. Existing techniques focus on design and optimization of power/ground supply networks. We propose supply voltage degradation aware placement, e.g., to reduce maximum supply voltage degradation by relocation of supply current sources. We represent supply voltage degradation at a P/G node as a function of supply currents and effective resistances in a DC P/G network, and integrate supply voltage degradation in the APlace analytical placement framework. We have published one conference paper and won Best Paper award at ICCD05.

(3) Lens Aberration Aware Timing-Driven Placement.

Process variations due to lens aberrations are to a large extent systematic, and can be modeled for purposes of analyses and optimizations in the design phase. As process margins reduce, and as improvements in reticle enhancement techniques control variations due to other sources with increased efficacy, lens aberration-induced variations gain importance. Therefore, we propose an aberration-aware, timing-driven analytical placement approach that accounts for aberration-induced variations during placement. Our approach minimizes the design's cycle time, and prevents hold-time violations, under systematic aberration-induced variations. We have one conference publication to appear at DATE06.

(4) Detailed Placement.

I have developed a detailed placer , which is comprised of three phases: (i) global moving where cells are moved globally to reduce wirelength, (ii) whitespace distribution where whitespace is optimally distributed to minimize wirelength while maintaining the relative cell ordering in every layout row with a dynamic programming algorithm, and (iii) cell order polishing where successive small windows of cells are optimally re-ordered. The three phases of detailed placement are iterated until negligible improvements in wirelength are observed. The idea of cell order polishing is commonly applied in academic placers. For example, Capo's RowIroning technique permutes several cells in one row assuming equal whitespace distribution between cells. FengShui's cell ordering technique permutes six objects in one or more rows regarding whitespace as pseudo cells and thus largely increases the number of objects. We present a branch-and-bound algorithm that permutes the order of a few cells in one or multiple rows, and simultaneously considers the optimal placement for each permutation in a small window. Thus, our algorithm allows more accurate, overlap-free permutations and does not have to shift other cells. We observe that the cost of placing the first part of a permutation in one row is not related to the order of the remaining cells. Therefore, by constructing the permutations in lexicographic order and reusing previous data, the runtime of the accurate algorithm is similar to that of other detailed placers.

(5) Multi-Project Wafer and Reticle Cost Optimization. Multi-project wafers allow customers to share the expensive cost of a mask set and result in faster prototyping. Our research considers ways to minimize production costs for multi-project wafers. We have published one conference paper at ISPD04 and one journal version at TCAD05.

(6) Power Grid Planning. Our research addresses planning of hierarchical, uniform power distribution in early design stages, so that for a fixed total routing area the worst-case IR-drop on the power mesh is minimal, or for a given IR-drop tolerance the power mesh achieves the IR-drop specification with minimal routing area. This work is published in ASP-DAC04.

(7) The Y Interconnect Architecture. The Y-architecture for on-chip interconnect is based on pervasive use of 0-, 120-, and 240-degree oriented semi-global and global wiring. Its use of three uniform directions exploits on-chip routing resources more efficiently than traditional Manhattan wiring architecture. Our research provides a complete, technically in-depth analysis of key deployment and methodology issues associated with the Y-architecture for semiconductor ICs, including throughput analysis, estimates of wirelength savings, clock and power distribution methodology, wireability, and manufacturing. We have published two conference papers at SLIP03 and ICCAD03 and one journal paper at TCAD05 in this area.

Publications

[J5] A. B. Kahng, C.-H. Park, P. Sharma and Q. Wang, "Lens Aberration Aware Placement for Timing-Improvement", submitted to IEEE Transactions on Computer-Aided Design, 2005.

[J4] A. B. Kahng, S. Reda and Q. Wang, "Anatomy of an Analytic Placer", submitted to ACM Journal of Experimental Algorithmics, 2005.

[J3] A. B. Kahng, I. Mandoiu, Q. Wang, X. Xu, and A. Zelikovsky, "Multi-Project Reticle Floorplanning and Wafer Dicing", IEEE Transactions on Computer-Aided Design, to appear.

[J2] A. B. Kahng, and Q. Wang, "Implementation and Extensibility of an Analytic Placer", IEEE Transactions on Computer-Aided Design 24(5) (2005), pp. 734-747.

[J1] H. Chen, C. K. Cheng, A. B. Kahng, I. Mandoiu, Q. Wang and B. Yao, "The Y-architecture for On-Chip Interconnect: Analysis and Methodology", IEEE Transactions on Computer-Aided Design 24(4) (2005), pp. 588-599.

[C13] C. J. Alpert, A. B. Kahng, C. N. Sze and Q. Wang, "Timing-Driven Steiner Trees are (Practically) Free", Proc. Design Automation Conference, July 2006, to appear. (Short)

[C12] A. B. Kahng and Q. Wang, "A Faster Implementation of APlace", Proc. ACM/IEEE Intl. Symp. Physical Design, 2006, pp. 218-220. (Short Invited)

[C11] A. B. Kahng, C.-H. Park, P. Sharma and Q. Wang, "Lens Aberration-Aware Timing-Driven Placement", Proc. Design Automation and Testing in Europe, 2006, pp. 890-895.

[C10] A. B. Kahng, S. Reda and Q. Wang, "Architecture and Details of a High Quality, Large-Scale Analytical Placer", Proc. ACM/IEEE Intl. Conf. on Computer-Aided Design, 2005, pp. 891-898. (Best Paper Nomination)

[C9] A. B. Kahng, B. Liu and Q. Wang, "Supply Voltage Degradation Aware Analytical Placement", Proc. ACM/IEEE Intl. Conf. on Computer Design, 2005, pp. 437-443. (Best Paper Award; 5 out of 310 submissions)

[C8] Y.-S. Cheon, P.-H. Ho, A. B. Kahng, S. Reda and Q. Wang, "Power-Aware Placement", Proc. Design Automation Conference, 2005, pp. 795-800.

[C7] A. B. Kahng, S. Reda and Q. Wang, "APlace: A General Analytic Placement Framework", Proc. ACM/IEEE Intl. Symp. Physical Design, April 2005, pp. 233-235. (Short Invited, 1st Place of ISPD05 Placement Contest)

[C6] A. B. Kahng, and Q. Wang, "An Analytic Placer for Mixed-Size Placement and Timing-Driven Placement", Proc. ACM/IEEE Intl. Conf. Computer-Aided Design, Nov. 2004, pp. 565-572.

[C5] A. B. Kahng, and Q. Wang, "Implementation and Extensibility of an Analytic Placer", Proc. ACM/IEEE Intl. Symp. Physical Design, April 2004, pp. 18-25.

[C4] A. B. Kahng, I. Mandoiu, Q. Wang, X. Xu, and A. Zelikovsky, "Multi-Project Reticle Floorplanning and Wafer Dicing", Proc. ACM/IEEE Intl. Symp. Physical Design, April 2004, pp. 70-77.

[C3] H. Chen, C. K. Cheng, A. B. Kahng, M. Mori and Q. Wang, "Optimal Planning for Mesh-Based Power Distribution", Proc. ASP-DAC 2004, Jan. 2004, pp. 444-449.

[C2] H. Chen, C. K. Cheng, A. B. Kahng, I. Mandoiu, Q. Wang and B. Yao, "The Y-architecture for On-Chip Interconnect: Analysis and Methodology", Proc. IEEE/ACM Intl. Conf. Computer-Aided Design, Nov. 2003, pp. 13-19.

[C1] H. Chen, C. K. Cheng, A. B. Kahng, I. Mandoiu and Q. Wang, "Estimation of Wirelength Reduction for ��-Geometry vs. Manhattan Placement and Routing", Proc. ACM Intl. Workshop on System-Level Interconnect Prediction, April 2003, pp. 71-76.

Qinke Wang and Lizhu Zhou, "Schema Based Data Storage and Query Optimization for Semi-structured Data", Proc. 1st Int. Conf. Web-Age Information Management (Lecture Notes in Computer Science, Vol. 1846, Springer), Jun. 2000, pp. 389-398.

Qinke Wang and Lizhu Zhou, "Schema-Based Rearrangement of Semi-structured Data", Proc. 16th National Conf. of Database, Aug. 1999, China, pp.581-586.