Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1997-09-24
2001-10-09
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06301694
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of hierarchical graph partitioning. More specifically, the present invention provides a hierarchical circuit partitioning method for programmable logic devices (PLDs).
As integrated circuits (ICs) become faster, smaller and less expensive, integrated circuits increasingly impact almost every aspect of our daily lives. Although advances in semiconductor fabrication have drastically reduced the cost for producing conventional integrated circuits, the design process is still very expensive and time consuming.
Programmable logic devices (PLDs) offer an alternative to conventional ICs. PLDs are a type of integrated circuit having programmable logic elements and a programmable interconnect. Because PLDs may be programmed to emulate desired digital circuits, the development time needed to go from design to chip implementation may be reduced.
One particular class of PLDs is CPLDs. Each CPLD generally includes two components, logic elements and interconnections. The logic elements may be programmed or configured to perform specific logic functions, for example, NAND, NOR, exclusive OR, etc. The interconnections are routing resources that may be programmed to interconnect the logic elements with each other and with external input/output pins.
Although PLDs have distinct advantages over conventional ICs, configuring the devices is often difficult and computationally expensive. For example, the logic functions must be partitioned (i.e., mapped) among the various logic elements. Poor partitioning wastes interconnection resources and limits the number of functions that may be placed on a PLD.
Similar partitioning problems are found in many other areas. For example, in parallel processing applications, processing tasks must be efficiently partitioned among specific processors. Other partitioning problems will be readily apparent to those of skill in many various arts. In general, the problem is mapping a number of interconnected elements (i.e., logic functions) to a set of resources (i.e., logic elements.)
It is known to arrange these types of partitioning problems as hierarchical graphs. This allows mathematical and computer programming techniques to be used in solving the problem. The graph is arranged with interconnected nodes (or containers) representing the resources and elements representing the elements to be partitioned amongst the elements.
Finding an optimal solution to the problem of graph partitioning is computationally difficult. As the number of elements and resources increase, the number of computations expands exponentially. For large numbers of elements and resources, finding the optimal solution is not possible in a practical sense. Consequently, heuristic techniques have been developed to find good solutions in a reasonable amount of time. However, as PLDs become more and more dense, improved techniques are desirable to closer approximate the optimal solution, and to efficiently manage the number of computations.
Accordingly, there is a need for improved techniques for partitioning hierarchical graphs, and in particular, for an efficient technique for partitioning logic function to particular logic elements within a PLD.
SUMMARY OF THE INVENTION
The present invention provides systems and methods for partitioning hierarchical graphs. It is useful, for example, in mapping logic functions to specific logic elements of a PLD.
The system takes as input a set of elements (i.e., logic functions) and partitions them among various resources represented by containers or nodes of a graph (i.e., logic elements.) An initial partitioning is done by placing each of the elements into containers. Then, the system defines a window over a subportion of the graph, and repartitions the elements within that window. The system slides the window to a new location, and repeats the repartitioning for the elements within the newly located window. This provides an efficient method for partitioning a graph. In one embodiment, this process is recursive, and the window slides recursively from the root of the hierarchical graph to the leaf nodes.
In an embodiment of the invention, if problems are encountered while the elements are being partitioned, the problems are recorded. Typically, these problems prevent the elements from being legally placed within the window. When the window is moved to a previous location of the hierarchical structure in which problems have been recorded, the recorded problems may be taken into account so that the problems will not appear during subsequent partitioning.
In another aspect of the invention, a window may be optionally inflated to a larger size if the elements within the window of the hierarchical structure are not legally placed. By increasing the size of the window, the invention may analyze more information which allows the elements to be legally placed within the containers of the window.
Typically, the window is then deflated back to its original size after the partitioning succeeds.
Other features and advantages of the present invention will become apparent upon consideration of the following detailed description and the accompanying drawings, in which like reference designations represent like features throughout the figures.
REFERENCES:
patent: 3617714 (1971-11-01), Kernighan et al.
patent: 4617479 (1986-10-01), Hartmann et al.
patent: 4791590 (1988-12-01), Ku et al.
patent: 4871930 (1989-10-01), Wong et al.
patent: 4903107 (1990-02-01), Chan et al.
patent: 4918379 (1990-04-01), Jongepier
patent: 5031111 (1991-07-01), Chao et al.
patent: 5128871 (1992-07-01), Schmitz
patent: 5187671 (1993-02-01), Cobb
patent: 5189628 (1993-02-01), Olsen et al.
patent: 5218551 (1993-06-01), Agrawal et al.
patent: 5224056 (1993-06-01), Chene et al.
patent: 5229953 (1993-07-01), Isozaki et al.
patent: 5241224 (1993-08-01), Pedersen et al.
patent: 5260610 (1993-11-01), Pedersen
patent: 5260611 (1993-11-01), Cliff et al.
patent: 5305229 (1994-04-01), Dhar
patent: 5309371 (1994-05-01), Shikata et al.
patent: 5311443 (1994-05-01), Crain et al.
patent: 5341308 (1994-08-01), Mendel
patent: 5359538 (1994-10-01), Hui et al.
patent: 5392227 (1995-02-01), Hiserote
patent: 5469003 (1995-11-01), Kean et al.
patent: 5475830 (1995-12-01), Chen et al.
patent: 5477474 (1995-12-01), Southgate et al.
patent: 5485396 (1996-01-01), Brasen et al.
patent: 5485547 (1996-01-01), Maruno
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5513124 (1996-04-01), Trimberger et al.
patent: 5519629 (1996-05-01), Snider
patent: 5521836 (1996-05-01), Hartoog et al.
patent: 5557533 (1996-09-01), Koford et al.
patent: 5574893 (1996-11-01), Southgate et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5745363 (1998-04-01), Rostoker et al.
patent: 5825660 (1998-10-01), Cagan et al.
patent: 5847965 (1998-12-01), Cheng
patent: 5870313 (1999-02-01), Boyle et al.
patent: 5892682 (1999-04-01), Hasley et al.
patent: 5903461 (1999-05-01), Rostoker et al.
patent: B1 4617479 (1993-09-01), Hartmann et al.
Hamada et al., “An Efficient Multi-Level Placement Technique Using Hierarchical Partitioning,” IEEE, pp. 2044-2047, 1991.*
Limqueco et al., “Optimizing Large Networks by Repeated Local Optimization Using a Windowing Scheme,” pp. 1993-1996, IEEE, 1992.*
Hassoun et al., “Graph Partitioning Using a Reduced Connectivity Matrix for VLSI Applications,” IEEE, pp. 2040-2043, 1991.*
Overhauser et al., “Multilevel Circuit Partitioning for Switch-Level Timing Simulation,” ISCAS88, pp. 1361-1364, 1988.*
Wei et al., “Towards Efficient Hierarchical Designs by Ratio Cut Partitioning,” IEEE, pp. 298-301, 1989.*
Chatterjee et al., “A New Simultaneous Circuit Partitioning and Chip Placement Approach Based on Simulated Annealing,” Proceedings of Design Automation Conference, 1990, pp. 36-39.
Kernigham B. W. and S. Lin, “An Efficient Heuristic Procedure for Partitioning Graphs,” The Bell Systems Technical Journal, Feb. 1970, vol. 49, No. 2, pp. 291-307.
Krishnamurthy, “An Improved Min-Cut Algorithm for Partitioning VLSI Networks,” IEEE Transactions on Computer
Lee Fung Fung
Tse John
Altera Corporation
Garbowski Leigh Marie
Smith Matthew
Townsend and Townsend / and Crew LLP
LandOfFree
Hierarchical circuit partitioning using sliding windows does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical circuit partitioning using sliding windows, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical circuit partitioning using sliding windows will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2577016