VLSI Design and CAD

Principal Investigator: P. Banerjee

Sponsor: Defense Advanced Research Projects Agency (DARPA), 9/96 – 9/98

In this research, we are investigating parallel algorithms for several CAD tools with the objective of reducing the design turnaround times of these tools and to enable larger problems to be solved. All of the CAD tools are being developed using the Message-Passing Interface (MPI) and the ProperCAD library. This allows the parallel algorithms to run on shared-memory multiprocessors, distributed-memory message-passing multicomputers, and networks of workstations. Specifically, we are developing parallel algorithms for cell placement, global routing, layout verification and extraction, combinational and sequential logic synthesis, behavioral simulation, test generation, and fault simulation.

Investigators: P. Banerjee, S. Hauck, M. Sarrafzadeh

Sponsor: DARPA, 9/97 – 8/00

This research project seeks to develop a complete adaptive solution for general-purpose computing systems. It includes research in adaptive computer architectures, configuration-management techniques, high-level compilation, mapping algorithms, template-based physical design, software / algorithms optimized for adaptive systems, and defense applications of adaptive computing. A key specific aim is to produce a general-purpose computing paradigm simple enough to become the standard mass-market computing model, yet with enough power to enable several orders-of-magnitude speedup for defense applications. This will yield a future defense computing solution with the price and availability advantages of commercial off-the-shelf hardware.

Principal Investigator: S. Hauck

Sponsor: Motorola, Inc. (University Partnership in Research Program), 9/97 – 8/01

Field-programmable gate arrays (FPGA’s) hold significant promise for high-performance computing, including signal processing. When combined with a standard digital signal processing (DSP), a powerful computing paradigm can be created. This research includes investigations into new FPGA architectures, mapping tools, and applications that can demonstrate the potential of these systems.

Investigators: S. Hauck and M. Sarrafzadeh

Sponsor: National Science Foundation (NSF) with matching funds from AT&T and Northwestern
University and an REU Supplement from NSF , 6/97 – 5/99

The goal of this research is to develop fast mapping tools and architectures for logic emulations that can greatly reduce the mapping time, and thus radically improve the speed and usefulness of logic emulation. We are developing technology mapping tools that integrate decomposition and covering. Further, we are developing placement tools that use partitioning methods to do higher-quality global placement. Combined, these will improve both the mapping times and resulting quality of FPGA-based implementations. Routing complexity estimators are also being developed to guide algorithm choice, exploiting the mapping time / quality tradeoffs in many techniques. We are also considering new FPGA architectures for logic emulators, developing systems that can support much faster mapping times and yet still achieve high-quality results. By integrating all of these steps together, we are creating a complete mapping-time oriented tool suite for logic emulation which can exploit the mapping time / quality tradeoff in these systems.

Investigators: S. Hauck and M. Sarrafzadeh

Sponsor: AT&T, 9/94 – 8/98

In the modern VLSI market, it is important to get new products from ideas to chips in the shortest time. At the same time, it is desirable to reduce the financial risk of prototyping new ideas.
Thus, minimizing the design, development, verification, production, and testing cycle is crucial.
Field-programmable gate arrays (FPGA’s) have been introduced as a potential solution to this need. Their programmability makes them attractive for prototyping and creates potential applications in the portable-product market. We propose a methodology in which a fast-covering algorithm is used as an evaluation engine for the decomposition phase. We are investigating an integrated decomposition and covering algorithm for LUT-based FPGA’s targeting minimum area, which uses the same methodology.

Principal Investigator: D. T. Lee

Sponsor: Office of Naval Research (ONR), 6/95 – 9/99

In this project, we are building an interactive tool for visualizing geometric algorithms in distributed environments. The tool will provide features such as: interactive visualization of program states for debugging; high-level graphical input / output manipulation facilities for geometric objects; geometric algorithm animation; reuse of existing data structures; and algorithm implementation. It will also provide for distributed execution among heterogeneous machines at different sites. GeoSheet Version 1.0 for visualization of geometric algorithms manipulating 2-D objects has been implemented and runs under the SunOS X-windows environment. In this project, we are enhancing the graphical user interface of GeoSheet, developing software tools for visualizing 3-D objects, implementing geometric algorithms for 2-D and 3-D problems, and implementing interactive debugging facilities and animation. The project also involves maintenance of the system on the World Wide Web, coordinating with researchers in the community to convert their non-visualized software into visualized software to run in our environment, and establishing a geometric software library that is useful for academic researchers in computational geometry as well as engineering practitioners who work in related fields including VLSI layout and routing, geometric modeling, and virtual reality.

Principal Investigator: D. T. Lee

Sponsor: NSF, 9/98 – 8/99

This project investigates fundamental geometric problems in computational geometry, including those that arise in VLSI computer-aided design. We propose a new model of the Voronoi diagram based on non-symmetric distance measures, and study the characteristics and computational properties of this new model. We also investigate bi-criteria optimization problems in the plane such as shortest-path-tree or minimum-spanning-tree routing with constraints on maximum delay, Steiner minimum-tree routing with fixed orientations, and other optimization problems such as topological via minimization and compaction. These optimization problems are studied for computational complexity, and efficient heuristics and implementations are developed. Web-based visualization software tools that help to design and disseminate usable geometric codes will be implemented. All software will be implemented in the C++ and Java programming languages with the use of the visualization package developed at Northwestern University. The overall goals of this research are to apply geometric techniques to tackle problems that arise in computational geometry as well as related engineering fields, especially VLSI CAD. This will increase the impact of computational geometry on applied areas. An environment for training individuals at both the intellectual and practical levels will be provided. This should benefit education in the area of algorithm design and geometric computing.

Principal Investigator: M. Sarrafzadeh

Sponsor: NSF, 2/96 – 1/99

Performance-driven issues related to deep submicron geometries, reliability, and other factors make the VLSI placement problem a real challenge. Even the classical (area-minimization) placement problem is not completely understood. Previously, we demonstrated several issues that must be considered in designing a placement algorithm. We are building on this work to design a new class of placement algorithms called NRG. In addition to good placement algorithms, we need good predictors that can quickly estimate the placement cost function. We are working on methodologies for designing a good predictor. The main idea is to reduce the placement search space and then find a very fast placement in the reduced space. Placement results are good only if the subsequent routing step is made easy. We are working on integrated placement and routing approaches, adopting a hierarchical approach. Preliminary results show significant improvement over existing techniques.

Principal Investigator: M. Sarrafzadeh

Sponsor: Motorola Center for Telecommunications Research, 8/98 – 9/99

The goal of this project is to develop a methodology, hardware, and software support to make feasible the vision of a three-month design cycle for multimedia processors. We intend to circumvent ad-hoc analyses and development schemes, and provide the level of automation necessary to effectively search the design space and quickly generate the optimized variant. A key focus is parameterization, which circumvents redundant designs. We have identified a set of projects eventually leading to an optimized multimedia processor synthesis environment: (1) hardware design of a class of micro-sequencers with varying performance and functionality; (2) development of a general methodology for parameterization of DSP-based data paths; and (3) development of a micro-sequencer-based hardware-software partitioner for the control part of the design.

Principal Investigator: M. Sarrafzadeh

Sponsor: Motorola, Inc., 9/94 – 8/98

This project explores behavioral-level power estimation, a means to quickly evaluate competing algorithms or architectures to discover which likely has lower power requirements. Such an early evaluation permits the algorithm or architecture selection to have a more significant impact on power consumption than power-minimization techniques applied to logic, netlist, or layout levels. However, a difficulty in this approach lies in the large number of unknowns at the behavioral level. At this level, it is possible that little or no information about the architecture is given. This presents a problem since one operation type may be executable by several different functional-unit types which use different amounts of power (e.g. ripple-adder versus carry-lookahead). Even if the functional units are assumed to have known power requirements and the architecture is well specified, much of the power can be consumed by buses or other interconnections, which have widely varying capacitance according to their lengths resulting from placement and routing.

G. Hasteer and P. Banerjee,* "A parallel algorithm for state assignment of finite state machines,’’
IEEE Trans. Computers, vol. 47, pp. 242–246, Feb. 1998.

S. Ramaswamy, S. Sapatnekar, and P. Banerjee,* "A framework for exploiting data and functional
parallelism on distributed memory multicomputers," IEEE Trans. Parallel and Distributed
Systems, vol. 8, pp. 1098–1116, Nov. 1997.

S. Hauck,* "The roles of FPGA’s in reprogrammable systems," Proc. IEEE, vol. 86, pp. 615–639,
April 1998.

S. Hauck* and G. Borriello, "Pin assignment for multi-FPGA systems," IEEE Trans. Computer-Aided
Design of Integrated Circuits and Systems, vol. 16, pp. 956–964, Sept. 1997.

D. T. Lee,* C. D. Yang and C. K. Wong, "Finding rectilinear paths among obstacles in a two-layer
Interconnection model," Int’l. J. Computational Geometry and Applications, vol. 7, pp. 581–598,
Dec. 1997.

D. Z. Chen, D. T. Lee,* R. Sridhar, and C. N. Sekharan, "Solving the all-pair shortest path query
problem on interval and circular-arc graphs," Networks, vol. 31, pp. 249–257, July 1998.

H.-F. S. Chen and D. T. Lee,* "On crossing minimization problem," IEEE Trans. Computer-Aided
Design, vol. 17, pp. 406–418, May 1998.

E. Papadopoulou and D. T. Lee,* "A new approach for the geodesic Voronoi diagram of point in a
simple polygon and other restricted polygonal domains," Algorithmica, vol. 20, pp. 319–352,
April 1998.

L. H. Tseng, P. Heffernan and D. T. Lee,* "Two guard walkability of simple polygons,"
Int’l. J. Computational Geometry and Applications, vol. 8, pp. 85–116, Feb. 1998.

_______

M. Sarrafzadeh,* D. Knol, and G. Tellez, "A delay budgeting algorithm ensuring maximum flexibility in
placement," IEEE Trans. Computer Aided Design, vol. 16, pp. 1332–1341, Nov. 1997.

A. Farrahi, G. Tellez and M. Sarrafzadeh,* "Exploiting sleep mode for memory partitions and other
applications," VLSI Design, vol. 7, no. 3, pp. 271-287, 1998.

W.-L. Lin, C. K. Wong, and M. Sarrafzadeh,* "Floating Steiner trees," IEEE Trans. Computers,
vol. 47, pp. 197–211, Feb. 1998.

S. Raje and M. Sarrafzadeh,* "Scheduling with multiple voltages," INTEGRATION: The VLSI Journal,
vol. 23, pp. 37–59, 1997.

G. Tellez and M. Sarrafzadeh,* "On distance-preserving rectilinear Steiner trees," VLSI Design, vol. 7,
no. 1, April 1998.

D. Chakrabarti, A. Lain, and P. Banerjee,* "Evaluation of compiler and runtime library approaches for
supporting parallel regular applications," Proc. Int’l. Parallel Processing Symp. (IPPS-98),
Orlando, FL, April 1998.

J. Chandy and P. Banerjee,* "A parallel circuit-partitioned algorithm for timing-driven standard cell
placement," Proc. Int’l. Conf. Computer Design (ICCD-97), Austin, TX, Oct. 1997.

G. Hasteer, A. Mathur, and P. Banerjee,* "A framework for equivalence checking of multi-phase
FSM’s," Proc. Int’l. High-Level Design Validation and Test Workshop, Oakland, CA, Nov. 1997.

G. Hasteer, A. Mathur, and P. Banerjee,* "An implicit algorithm for finding steady states and its
application to FSM verification," Proc. Design Automation Conf. (DAC-98), San Francisco, CA,
June 1998.

M. Kandemir, P. Banerjee,* A. Choudhary,* J. Ramanujam, and N. Shenoy, "A generalized
framework for global communication optimization," Proc. Int’l. Parallel Processing Symp.
(IPPS/SPDP’98), Orlando, FL, March-April 1998.

M. Kandemir, J. Ramanujam, P. Banerjee,* and A. Choudhary,* "Optimizing spatial locality in loop
nests using linear algebra," Proc. 7th Int’l. Workshop on Compilers for Parallel Computers,
Linkoping, Sweden, June 1998.

M. Kandemir, N. Shenoy, P. Banerjee,* J. Ramanujam, and A. Choudhary,* "Minimizing data and
synchronization costs in one-way communication," Proc. 1998 Int’l. Conf. Parallel Processing
(ICPP’98), Minneapolis, MN, Aug. 1998.

V. Kim and P. Banerjee,* "Parallel algorithms for power estimation," Proc. Design Automation Conf.
(DAC-98), San Francisco, CA, June 1998.

V. Krishnaswamy and P. Banerjee,* "Parallel-compiled event-driven VHDL simulation," Proc. Int’l.
Conf. Supercomputing (ICS-98), Melbourne, Australia, July 1998.

P. Prabhakaran and P. Banerjee,* "Simultaneous scheduling, binding and floorplanning in high-level
synthesis," Proc. 11th Int’l. Conf. VLSI Design (VLSI Design’98), Chennai, India, Jan. 1998.

P. Prabhakaran and P. Banerjee,* "Parallel algorithms for scheduling, binding, and floorplanning in
high-level synthesis," Proc. Int’l. Conf. Circuits & Systems (ISCAS-98), Monterey, CA, May 1998.

S. Roy and P. Banerjee,* " Resynthesis of sequential circuits for low power," Proc. Int’l. Conf. Circuits
& Systems (ISCAS-98), Monterey, CA, May 1998.

S. Roy, A. Harm, and P. Banerjee,* "POWERSHAKE: A low-power driven clustering and factoring
methodology for Boolean expressions," Proc. Design, Automation and Test in Europe Conf.
(DATE’98), Paris, France, Feb. 1998.

Z. Xing and P. Banerjee,* "A parallel algorithm for zero-skew clock-tree routing," Proc. Int’l. Symp.
Physical Design (ISPD’98), Monterey, CA, April 1998.

Z. Xing and P. Banerjee,* "A parallel algorithm for timing-driven global routing for standard cells,"
Proc. Int’l. Conf. Parallel Processing (ICPP’98), Minneapolis, MN, Aug. 1998.

S. Hauck,* Z. Li, and E. J. Schwabe,* "Configuration compression for the Xilinx XC6200 FPGA," IEEE
Symp. FPGA’s for Custom Computing Machines, 1998.

S. Hauck* and S. Knol, "Data security for Web-based CAD," Proc. Design Automation Conf.,
pp. 788–793, 1998.

M. Enos, S. Hauck,* and M. Sarrafzadeh,* "Logic partitioning with replication," Int’l. Conf. Computer-
Aided Design (ICCAD’97), San Jose, CA, Nov. 1997.

H.-F. S. Chen and D. T. Lee,* "A faster one-dimensional topological compaction algorithm,"
Proc. 8th Int'l. Symp. Algorithms and Computation, Singapore, Dec. 1997, pp. 303–313.

E. Papadopoulou and D. T. Lee,* "Critical area computation — A new approach," Proc. Int'l Symp.
Physical Design, Monterey CA, April 1998, pp. 89–94.

M. Sarrafzadeh,* D. Knol and G. Tellez, "A solution to large-scale timing-driven placement problems,"
Proc. 1997 Design Automation Conf. (DAC-97).

K. Bazargan, S. Kim, and M. Sarrafzadeh,* "Nostradamus: Floorplanner of uncertain designs,"
Proc. 1998 Int’l. Symp. Physical Design (ISPD 98).

J. Crenshaw and M. Sarrafzadeh,* "Low-power-driven scheduling and binding," 1997 Great Lakes
Symposium on VLSI, Lafayette, Louisiana, Feb. 19-21, 1998.

A. Farrahi and M. Sarrafzadeh,* "TDD: Fast technology mapping with accurate prediction,"
1997 IEEE Int’l. ASIC Conference and Exhibit (ASIC'97).

S. Roy, M. Sarrafzadeh,* and P. Banerjee,* "Partitioning sequential circuits for low power," Proc. 11th
Int’l. Conf. VLSI Design (VLSI Design’98), Chennai, India, Jan. 1998.

M. Wang and M. Sarrafzadeh,* "NRG: Global and detailed placement," Int’l. Conf. Computer-Aided
Design (ICCAD’97), San Jose, CA, Nov. 1997.

M. Wang, M. Sarrafzadeh,* and P. Banerjee,* "Placement with incomplete data," Proc. Design
Automation Conf. (DAC-98), San Francisco, CA, June 1998.

P. Banerjee,* keynote speaker, Parallel and Distributed Computing Symp., Sept. 1997.

S. Hauck,* "An introduction to architectures, compilers, and configuration management for mass-
market adaptive computing," DARPA ACS PI Meeting, Nov. 1997.

S. Hauck,* "Triptych, Montage, CHIMAERA: Advanced FPGA technologies," Quicklogic Inc., Nov. 10,
1997.

S. Hauck,* "Configuration memory management for adaptive computing systems," U. Illinois Chicago,
Jan. 23, 1998; U. Washington, Jan. 30, 1998; UC Berkeley, April 17, 1998.

S. Hauck,* "The future of reconfigurable systems," keynote address, 5th Canadian Conf. on Field-
Programmable Devices, Montreal, June 1998.

D. T. Lee,* "Crossing minimization problem revisited," Avanti Corp., Fremont, CA, 1998.

M. Sarrafzadeh,* "Application-specific processor synthesis," Motorola, May 1998.

P. Banerjee,* session chair, "Compilers," at High-Performance Computing Symposium (HiPC’97),
Bangalore, India, Dec. 1997.

P. Banerjee,* session chair, "Compilers-II," at Int’l. Parallel Processing Symp., Orlando, FL, April 1998.

S. Hauck,* session and publicity chair, ACM/SIGDA Int’l. Symp. on Field Programmable Gate Arrays,
Monterey, CA, Feb. 1998.

S. Hauck,* session chair, IEEE Symp. FPGA’s for Custom Computing Machines, Napa, CA,
April 1998.

S. Hauck,* discussion leader, "Reconfigurable Device Architectures," at Configurable Computing
Workshop, Hewlett-Packard Labs, Bristol, England, June 1998.

D. T. Lee,* session chair, "Computational Geometry," at Int'l Symp. on Algorithms and Computation
(ISAAC'97), Singapore, Dec. 1997.

D. T. Lee,* conference organizer, Summer Institute on Parallel and Distributed Computing, Academia
Sinica, Taipei, Taiwan, July 1998.

D. T. Lee,* session chair, Int'l Conf. Computing and Combinatorics (COCOON'98), Taipei, Taiwan,
Aug. 1998.

M. Sarrafzadeh,* general chair, Int’l Symp. Physical Design, Monterey, CA, April 1998.

G. Hasteer, Equivalence Checking in a Modular Checking Framework, Computer Science Dept.,
University of Illinois at Urbana-Champaign, Dec. 1997. (P. Banerjee*)

S. Roy, Low-Power Driven Sequential Algorithms for Combinational and Sequential Circuits, ECE Dept.,
University of Illinois at Urbana-Champaign, Aug. 1998. (P. Banerjee*)

J. Crenshaw, Behavioral-Level Power Estimation, June 1998. (M. Sarrafzadeh*)