Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-03-04
2002-07-02
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06415425
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to placing cells on a programmable logic device, and more particularly, placing cells using a density surface representation.
BACKGROUND
Field programmable gate arrays (FPGAs), first introduced by XILINX in 1985, are becoming increasingly popular devices for use in electronics systems. For example, communications systems employ FPGAs in large measure for their re-programmability. In general, the use of FPGAs continues to grow at a rapid rate because they permit relatively short design cycles, reduce costs through logic consolidation, and offer flexibility in their re-programmability. The capabilities of and specifications for XILINX FPGAs are set forth in “The Programmable Logic Data Book,” published in 1998 by XILINX, Inc., the contents of which is incorporated herein by reference.
The challenges facing today's floorplanning tools are that timing constraints are becoming ever more stringent, and the number of cells to be placed is increasing rapidly. Thus, finding a feasible placement using present tools can take a very long time. Two types of processes are generally known to be used. A first type of process attempts to maintain a feasible placement throughout the placement process, and one or more selected parameters are optimized, for example, wire length and timing. While feasible placements are produced by these processes, the algorithms are generally understood to take a very long time.
A second type of placement process is termed “analytical.” Analytical processes treat cells as points. The first phase distributes cells over the placement area while attempting to reduce wire-length. The first phase of the analytical processes oftentimes produce a placement that is not feasible, and a subsequent phase is required to eliminate the overlaps while keeping the wire-length low. Thus, the more overlaps that remain after the first phase of the analytical process the more time the subsequent phase will require to produce a feasible placement. Thus, a process that executes quickly and that reduces the overlaps in a placement would therefore be desirable.
SUMMARY OF THE INVENTION
The method of the present invention generally uses a density surface representation of a placement in spreading cells. By considering the entire surface density, the cells can be moved in a manner that quickly minimizes the number of overlaps while keeping the wire-length low.
In one embodiment, a method is provided for analytical placement of cells using density surface representations. The placement of cells is characterized as a density surface function using a two-dimensional continuous function. The cells are iteratively moved from areas having higher densities of placed cells to areas having lower densities of placed cells using the density surface function.
The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.
REFERENCES:
patent: 5943243 (1999-08-01), Sherlekar et al.
patent: 6067409 (2000-05-01), Scepanovic et al.
patent: 6068662 (2000-05-01), Scepanovic et al.
patent: 6155725 (2000-12-01), Scepanovic et al.
patent: 6182271 (2001-01-01), Yahagi
patent: 6192508 (2001-02-01), Malik et al.
Wakabayashi et al, “An Optimal Pin Assignment Algorithm with Improvement of Cell Placement in Standard Cell Layout,” IEEE, Nov. 1996, pp. 381-384.*
Wakabayashi et al, “Timing-Driven Pin Assigment with Improvement of Cell Placement in Standard Cell Layout,” IEEE, Jun. 1997, pp. 1552-1555.*
Hans Eisenmann, Frank M. Johannes, “Generic Global Placement and Floorplanning”, Institute of Electronic Design Automation, Technical University Munich, 80290 Munich, Germany, Copyright 1998, pp. 269-274.
“The Programmable Logic Data Book 1998”, published by Xilinx, Inc., located at 2100 Logic Drive, San Jose, California 95124.
Chaudhary Kamal
Nag Sudip K.
Maunu LeRoy D.
Siek Vuthe
Xilinx , Inc.
LandOfFree
Method for analytical placement of cells using density... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for analytical placement of cells using density..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for analytical placement of cells using density... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2839957