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: S. Hauck, P. Banerjee, 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 – 6/00

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 University Partnership in Research Program.

Principal Investigator: S. Hauck

Sponsor: Motorola, Inc., 9/97-8/01

This research focuses on the use of reconfigurable hardware in the execution and acceleration of digital signal processing applications. In particular, we are examining the use of optimizations to the programming structures of FPGAs to more fully harness the benefits of run-time reconfiguration. Furthermore, we plan to explore new reprogram able computational and routing structures which will perform the calculations required in DSP applications more efficiently than current commercial designs. This research will work to enable the design of a coupled DSP-FPGA System On a Chip (SOC) that will achieve a higher performance than DSP-only systems.

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 – 2/00

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 Inc., 9/97-8/99

The goal of the application specific processor synthesis (ASPROS) project is to develop a methodology, hardware, and software support to make the three-month design cycle vision for multimedia processors a reality. One goal of ASPROS is to circumvent ad-hoc analysis and development -schemes and provide the level of automation necessary to effectively search the design space and to quickly generate the optimized variant. A key focus in ASPROS is parameterization. Parameterization circumvents redundant designs. A set of projects eventually leading to an optimized multimedia processor synthesis environment has been identified. These projects are: (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 datapaths, and (3) Development of a micro-sequencer based hardware-software partitioner for the control part of the design. In the ASPROS project, we will also study power and area estimation and optimization.

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.

D. T. Lee, "Computational geometry I, II, Chap. 19 and 20 in Algorithms & Theory of Computation Handbook, ," M. J. Atallah, ed., CRC Press, 1999.

P. Banerjee, S. Mohan, P. Mazumder, D. Krishnaswamy, and E. M. Rudnick,

"Parallel Implementations, Chapter 8 in Genetic Algorithms for VLSI Design, Layout & Test Automation, P. Mazumder and E. M. Rudnick, eds., pp. 252-294, Prentice Hall PTR, 1999.

* ( For ease of identification, each citation in this and the following sections will begin with the group faculty member(s)’ name(s))

P. Banerjee, G. Hasteer and A. Mathur, "Efficient Equivalence Checking of Multi-Phase Designs Using Phase Abstraction and Retiming," ACM Transactions on Design Automation of Electronic Systems (TODAES) Special Issue on High Level Design, Validation and Testing, Oct. 1998, pp. 600-625.

P.Banerjee and J. Chandy, "A Parallel Circuit Partitioned Algorithm for Timing-Driven Standard Cell Placement," Journal of Parallel and Distributed Computing, Vol. 57, No. 1, pp. 64-90, April 1999.

S. Hauck, G. Borriello, and C. Ebeling, "Mesh Routing Topologies for Multi-FPGA Systems," IEEE Transactions on VLSI Systems, Vol. 6, No. 3, pp. 400-408, September 1998.

S. Hauck, Z. Li, and E. J. Schwabe, "Configuration Compression for the Xilinx XC6200 FPGA," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 8, pp. 1107-1113, August, 1999.

D.T. Lee and H. -F. Steven Chen "On Crossing Minimization Problem," IEEE Trans. Computer-Aided Design, (18,4): 463-474, April 1999.

D.T. Lee, O. Aichholzer, F. Aurenhammer, D.Z. Chen and E. Papadopoulou, "Skew Voronoi Diagram," Int’l J. Comput. Geometry & Applications, 9(3): 235-247, June 1999.

D.T.Lee, A.H. Farrahi and M. Sarrafzadeh, "Two-way and Multi-way partitioning a set of intervals for clique-width maximization," Algorithmica, 23(3): 187-210, March 1999.

D.T. Lee and E. Papadopoulou and "Critical Area Computation via Voronoi Diagrams," IEEE Trans. Computer-Aided Design, (18,4): 463-474, April 1999.

M. Sarrafzadeh and J. D. Cho, "Mixed LP and Mincost Flow-based Four-bend Global Routing in Two Dimensional Arrays, IEEE Transactions on CAD, pp. 793-802, September 1998.

M. Sarrafzadeh, J.-D. Cho and S. Raje, "Fast Approximation Algorithms on Maxcut, k-color Ordering for VLSI Applications," IEEE Transactions on Computers, Vol. 47, No. 11, November 1998, pp. 1253-1266.

M. Sarrafzadeh, Kia Bazargan and Sam Kim "Nostradamus: Floorplanner of Uncertain Designs," IEEE Transactions on CAD, April 1999.

P. Banerjee and J. Chen, "Parallel Construction Algorithms for BDDs," Proc. of the 1999 International Symposium on Circuits and Systems (ISCAS’99), Orlando, FL, June 1999.

P. Banerjee and Y. Yuan, "Incremental Capacitance Extraction and Its Application to Iterative Timing-Driven Detailed Routing," Proc. of the 1999 International Symposium on Physical Design (ISPD-99), Monterey, CA, April 1999.

P. Banerjee and Y. Yuan, "Fast Potential Integrals for Signal Integrity Analysis," Proc. of the ACM/IEEE International Workshop in Timing Issues in the Specification and Synthesis of Digital Systems (TAU’99), Monterey, CA, March 1999.

P. Banerjee, J. Crenshaw, M. Sarrafzadeh, and P. Prabhakaran, "An Incremental Floor-Planner," Proc. of the 9^th Great Lakes Symposium on VLSI, Ann Arbor, MI, March 1999.

P. Banerjee and Y. Yuan, "ICE: Incremental 3-Dimenional Capacitance and Resistance Extraction for an Iterative Design Environment," Proc. of the 9^th Great Lakes Symposium on VLSI, Ann Arbor, MI, March 1999.

P. Banerjee, M. Sarrafzadeh, P. Prabhakaran, J. Crenshaw, "Simultaneous Scheduling, Binding and Floorplanning for Interconnect Power Optimization," Proc. of the 1999 VLSI Design Conference, Goa, INDIA, Jan. 1999.

P. Banerjee, D. Chakrabarti, P. Joisha, J. Chandy, D. Krishnaswamy and V. Krishnaswamy, "WADE: A Web-Based Automated Parallel CAD Environment," Proc. of the International Conference on High Performance Computing (HiPC’98), Chennai, INDIA, Dec. 1998.

P. Banerjee, G. Hasteer and A. Mathur, "Efficient Equivalence Checking of Multi-Phase Designs Using Retiming," Proc. of the 1998 International Conference on Computer-Aided Design (ICCAD-98), San Jose, CA, Nov. 1998.

P. Banerjee, and S. Roy, "Power Drive: A fast, canonical POWER estimator for DRIVing synthEsis," Proc. of the 1998 International Conference on Computer-Aided Design (ICCAD-98), San Jose, CA, Nov. 1998.

P. Banerjee, S. Roy and A. Harms, "A Low Power Logic Optimization Methodology Based on a Fast Power Driven Mapping," Proc. of the International Conference on Computer Design (ICCD-98)Austin, TX, Oct. 1998.

S. Hauck and Z. Li, "Don't Care Discovery for FPGA Configuration Compression", ACM/SIGDA Symposium on Field-Programmable Gate Arrays, pp. 91-98, 1999.

S. Hauck, and W. D. Wilson, "Abstract: Runlength Compression Techniques for FPGA Configurations", IEEE Symposium on FPGAs for Custom Computing Machines, 1999.

D. T. Lee, S. L. Chang and C. -H. Wu, "A Muscular-Like Compliance Control for Active Vehicle Suspension," Proc. 1999 IEEE International Conference on Robotics and Automation, Detroit, MI May 1999.

M. Sarrafzadeh and S. Raje, "Scheduling with Multiple Voltages under Resource Constraints,"Proceeding of 1999 Int’l Symposium on Circuits and Systems (ISCAS), pp. 350-353, May 30-June 2, 1999, Miami, Florida.

M. Sarrafzadeh and T.Takahashi, "A Fast Algorithm for Routability Testing", Proceeding of 1999 ISCAS, May 30-June 2, 1999, Miami, Florida.

M. Sarrafzadeh and M. Wang "Congestion Minimization During Placement," Proceedings of the 1999 Intern. Symposium on Physical Design (ISPD99), Monterey, CA.

M. Sarrafzadeh, A. Ranjan and K. Bazargan "Floorplanning 1000 Times Faster," System Level Interconnect Prediction (SLIP 99), Monterey, CA.

M. Sarrafzadeh and M. Wang, "Can Fast Algorithms Be Used as Good Predictors?" ( position statement), System Level Interconnect Prediction (SLIP 99), Monterey, CA.

M. Sarrafzadeh, K. Bazargan and R. Kastner, "3-D Floorplanning: Simulated Annealing and Greedy Placement Methods for Reconfigurable Computing Systems," 10^th IEEE Int’l Workshop on Rapid System Prototyping, June 16-18, 1999, Clearwater, Florida.

M. Sarrafzadeh and K. Bazargan, "Fast Online Placement for Reconfigurable Computing Systems," Proceedings of IEEE FCCM: Symposium on Field Programmable Custom Computing Machines, April 21-23 1999, Napa Valley, CA.

M. Sarrafzadeh, "Slack Equalization Nalgorithm: Precise Slack Distribution for Low-level Synthesis and Optimization," Workshop on Logic Synthesis (IWLS), June 1999 , Lake Tahoe, CA.

P. Banerjee, distinguished lecture, Computer Science Department, University of Florida, January 1999.

P. Banerjee, invited speaker, Georgia Institute of Technology, January 1999.

S. Hauck, "The Future of Reconfigurable Systems", Carnegie Mellon University, October 14, 1998. S. Hauck, "Reconfiguration Architectures for Adaptive Computing Systems", University of Washington, January 29,1999.

S. Hauck, "The Roles of Reconfigurable Logic in Systems-on-a-Chip", Motorola, April 27, 1999.

S. Hauck, panel oganizer, "FPGAs in the Era of System-on-a-Chip", International Symposium on Field Programmable Gate Arrays, 1999.

D.T. Lee, organizer, Summer Institute on Mobile Computing, Academia Sinica, Taipei, Taiwan, July-Aug. 1999

D. T. Lee, co-chair, International Conference on Computing and Combinatorics (COCOON’99), Tokyo, Japan, July 199.

D. T. Lee, " Critical area computation – A new approach based on Voronoi Diagrams," Dept. of Elect. Eng. and Computer Science, Univ. of Illinois at Chicago, Feb. 1999.

M. Sarrafzadeh, session chair, Int’l. Symposium on Physical Design (ISPD), Monterey, CA, April 6-8, 1999.