Floorplan Design for Complex VLSI Systems
Rapid advances in semiconductor technology have led to a dramatic increase in the complexity of VLSI circuits. For chips with tens or hundreds millions of devices, a hierarchical approach is needed to manage the enormous circuit complexity. Floorplanning tools, which determine the placement of all circuit blocks at each level of the hierarchy, play a crucial role in the divide-and-conquer solution to the layout of a complex chip.
In this talk, we will present a floorplanner FAST-SP based on the sequence-pair (SP) floorplan representation. We present an O(n loglog n) SP-to-floorplan translation algorithm based on longest common subsequence computation. Our algorithm is significantly faster than the traditional quadratic-time graph-based algorithm. The fast SP-to-floorplan translation algorithm allows our simulated annealing based floorplanner to examine a larger number of candidate floorplans in shorter runtime and produce better quality floorplans. In order to be useful in practice, an automatic floorplanning tool must be able to handle user-specified placement constraints. FAST-SP can handle a large variety of placement constraints including pre-placed constraint, range constraint, boundary constraint, abutment constraint, alignment constraint, and performance constraint.
Since the positions of circuit blocks greatly affect interconnect bus structures, it is important that bus planning can be considered during the floorplanning stage. Based upon a careful analysis of the relationship between bus ordering and block ordering in the floorplan represented by a sequence pair, we derive feasibility conditions on sequence pairs that could guide FAST-SP to simultaneously determine the positions of all blocks and buses. Finally, we will conclude the talk with a brief description of some of our other floorplanning research works (e.g., floorplanning for FPGAs, shuttle masks, and 3-D ICs).
Bio of the speaker
Martin D.F. Wong received the B.Sc. degree in Mathematics from the University of Toronto and the M.S. degree in Mathematics from the University of Illinois at Urbana-Champaign. He obtained the Ph.D. degree in Computer Science from the University of Illinois at Urbana-Champaign in 1987.
Dr. Wong is currently Professor of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign (UIUC). Before he joined UIUC, he was a Bruton Centennial Professor of Computer Sciences at the University of Texas at Austin (UT-Austin). Dr. Wong's research interests are computer-aided design (CAD) of very large scaled integrated circuits (VLSI), design and analysis of algorithms, and combinatorial optimization. He has published over 270 technical papers and has graduated 31 Ph.D. students. He is a coauthor of "Simulated Annealing for VLSI Design" (Kluwer Academic Publishers, 1988) and two invited articles in the Wiley Encyclopedia of Electrical and Electronics Engineering (1999).
Dr. Wong received the 2000 IEEE CAD Transactions Best Paper Award for his work on interconnect optimization. He also received best paper awards at DAC-86 and ICCD-95 for his work on floorplan design and routing, respectively. His ICCAD-94 paper on circuit partitioning has been included in the book "The Best of ICCAD - 20 Years of Excellence in Computer Aided Design" published in 2002.
Dr. Wong was the General Chair of the 1999 ACM International Symposium on Physical Design (ISPD-99) and was the Technical Program Chair of the same conference in 1998 (ISPD-98). He is on the Steering Committee of ISPD (ISPD-01, ISPD-02, and ISPD-05). He also regularly serves on the technical program committees of many other VLSI conferences (e.g., DAC, ICCAD, ISPD, DATE, ASPDAC, ISCAS, FPGA, SASIMI, GLS-VLSI, SSMSD). Dr. Wong has served as an Associate Editor for IEEE Transactions on Computers (1985-2000) and Guest Editor of four special issues for IEEE Transactions on Computer-Aided Design. He is currently on the Editorial Boards of ACM Transactions on Design Automation of Electronic Systems and IEEE Transactions on Computer-Aided Design.