Cross function block partitioning and placement of a circuit...

Details Cross function block partitioning and placement of a circuit... Cross function block partitioning and placement of a circuit...

2001-07-09

2003-12-02

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

06658636

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of circuit partitioning. More specifically, the present invention relates to the partitioning of a circuit design for the purpose of implementing or emulating the circuit design using a number of reconfigurable logic devices.
2. Background Information
FIG. 1
illustrates a typical prior art approach to partitioning a circuit design for the purpose of implementing or emulating the circuit design using a number of reconfigurable logic devices, such as field programmable gate arrays (FPGA). As illustrated, because of the complexity of modern day circuit designs, typically, a circuit design, such as integrated circuit (IC) design
102
having multiple functional blocks (FB), FB-a
104
a
, FB-b
104
b
, and so forth, would be provided to a partitioner, such as partitioner
104
, along functional block lines, and correspondingly partitioned. For example, a processor design having an instruction fetch and dispatch block, an arithmetic logic unit (ALU), a floating point processing unit (FPU), an on-chip cache memory block, a bus interface unit, and so forth, would be provided to partitioner
104
along these functional block lines, and correspondingly partitioned.
As illustrated, the partitioning would result in x
1
partitions
106
a
for FB-a
104
a
, x
2
partitions
106
b
for FB-b
104
b
and so forth. The partitions would be provided in turn to a “compiler”, such as compiler
108
, to be correspondingly compiled into a number of corresponding configuration files
110
a
-
110
n
for configuring the reconfigurable logic resources of a number of corresponding logic devices to correspondingly implement or realize the constituting elements of the corresponding partitions
106
a
-
106
n
of the function blocks
104
a
-
104
n
. In other words, for x
1
, x
2
, . . . xn partitions
106
a
-
106
n
for FB-a
104
a
through FB-n
104
n
, x
1
, x
2
, . . . xn configuration files for a total of x
1
+x
2
+ . . . xn logic devices would result.
This prior art partitioning approach may be inefficient in its usage of reconfigurable logic devices for various circuit designs, especially for IC designs where the partitioning of each function block results in one or more “small” partitions of consituting elements. Examples of IC designs where such phenomenon may occur include but are not limited to IC designs having multiple clock domains. In the multiple clock domain case, while the majority of the constituting elements of a functional block would operate in one clock domain, for various purposes, e.g. for interfacing with other function blocks that operate in other clock domains, each function block typically has small groups of consituting elements that operate in one or more of the other clock domains. Since each reconfigurable logic device typically supports only a single clock domain, accordingly the “small” partitions of constituting elements are resulted.
As those skilled in the art would appreciate that corresponding implementation or realization of these “small” partitions of constituting elements in corresponding logic devices often results in leaving a substantial amount of the reconfigurable logic resources of the corresponding logic devices unused. The amount of left over or wastage increases over time, as successive generations of reconfigurable logic devices tend to be equipped with more and more reconfigurable logic resources.
Accordingly, an improved approach to partitioning a circuit design for implementation or emulation on a number of reconfigurable logic devices is desired.
SUMMARY OF THE INVENTION
A first and a second netlist of a first and a second function block of a circuit design are correspondingly partitioned into at least a first and a second partition, and a third and a fourth partition respectively. The first and third partitions include majorities of the constituting elements of the first and second netlists respectively. The second and fourth partitions include minorities of the constituting elements of the first and second netlists. Placements of the constituting elements of the first and third partitions are correspondingly determined. The second and fourth partitions are merged to form a composite partition, which in turn is partitioned for joint determination of placement of these minority constituting elements of the first and second netlists of the first and second function blocks on logic devices.
In one embodiment, the second and fourth partitions operate in the same clock domain, while the first and third partitions operate in one or more other clock domains.


REFERENCES:
patent: 5224056 (1993-06-01), Chene et al.
patent: 5329470 (1994-07-01), Sample et al.
patent: 5341308 (1994-08-01), Mendel
patent: 5448496 (1995-09-01), Butts et al.
patent: 5475830 (1995-12-01), Chen et al.
patent: 5513124 (1996-04-01), Trimberger et al.
patent: 5526276 (1996-06-01), Cox et al.
patent: 5598343 (1997-01-01), Roy et al.
patent: 5731985 (1998-03-01), Gupta et al.
patent: 5784290 (1998-07-01), Kung et al.
patent: 5862149 (1999-01-01), Carpenter et al.
patent: 5971588 (1999-10-01), Scepanovic et al.
patent: 6108494 (2000-08-01), Eisenhofer et al.
patent: 6212670 (2001-04-01), Kaviani
patent: 6286128 (2001-09-01), Pileggi et al.
patent: 6339836 (2002-01-01), Eisenhofer et al.
patent: 6397169 (2002-05-01), Shenoy et al.
patent: 6438735 (2002-08-01), McElvain et al.
patent: 6480991 (2002-11-01), Cho et al.
patent: 6490713 (2002-12-01), Matsumoto
patent: 2002/0023252 (2002-02-01), Lee et al.
patent: 2002/0144227 (2002-10-01), Das et al.
patent: 2002/0194572 (2002-12-01), McElvain et al.
patent: 2003/0005398 (2003-01-01), Cho et al.
patent: WO 94/06210 (1994-03-01), None
Brasen et al., “Using cone structures for circuit partitioning into FPGA packages”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, No. 7, Jul. 1998, pp. 592-600.*
Kuznar et al., “PROP: a recursive paradigm for area-efficient and performance oriented partitioning of large FPGA netlists”, 1995 IEEE/ACM International Conference on Computer-Aided Design, Nov. 5, 1995, pp. 644-649.*
Saucier et al., “Partitioning with cone structures”, 1993 IEEE/ACM International Conference on Computer-Aided Design, Nov. 7, 1993, pp. 236-239.*
NN87013460, “The TAU Algorithm”, IBM Technical Disclosure Bulletin, Vol. 29, No. 8, Jan. 1, 1987, pp. 3460-3463 (6 pages).*
The Programmable Gate Array Design Handbook, © 1986 XILINX, Inc.
G. Snider et al., “The Teramac Configurable Compute Engine”, pp. 44-53, Proceedings of 5thInternational Workshop on Field Programmable Logic and Applications, Aug. 29, 1995, Oxford, UK.

Affiliated with

Also associated with

Rating

Cross function block partitioning and placement of a circuit... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cross function block partitioning and placement of a circuit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cross function block partitioning and placement of a circuit... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3173990