Placement of clock objects under constraints

Details Placement of clock objects under constraints Placement of clock objects under constraints

2002-08-08

2004-09-07

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

06789244

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to network flow, and more particularly to the application of network flow techniques to constrained optimization problems.
BACKGROUND OF THE INVENTION
Many practical problems can be formulated and solved using network flow techniques. Some examples of such problems are: finding the fastest route between two locations in a city, determining the most efficient way to transport products from distribution centers to clients, and how best to route electricity from generating stations to buildings in a city. At a high-level, network flow techniques are applied as follows: First, the problem to be solved is analyzed and a “flow network” representing the problem is formulated. A flow network is a directed graph consisting of a set of nodes and edges. At least one of the nodes is designated as a source node; at least one of the nodes is designated as a sink node. Edges in the graph have a property called capacity and may also have a property called cost.
Intuitively, edges can be viewed as pipes and edge capacities represent the amount of fluid that may be sent through a pipe, and edge costs represent the cost of sending fluid through a pipe. Prior art techniques can be used to find the minimum cost, maximum network flow through the network from the source node(s) to the sink node(s). The solution to a network flow problem is a flow value for each edge (possibly zero). The network flow solution is translated into a solution for the original problem being solved; for example, flow along a particular edge in the network may imply the shipping of goods from a particular distribution center to a particular client. One limitation of the applicability of network flow techniques however is that they cannot be applied to problems having certain types of constraints. This is because these prior art techniques require that the network for which a flow is computed must be static. This eliminates the possibility of having dependencies in the flow network. Unfortunately, real life problems often have constraints and consequently, there are many problems to which network flow techniques cannot be applied.
A specific example will be used to illustrate the issue. In many engineering and operations research applications, it is important to be able to determine the optimal matching between a set of objects (e.g., electronic components, resources, people, etc.) with a set of slots (e.g., physical locations, tasks, buildings, people, etc.). An example is illustrated in FIG.
1
A. It comprises a set of objects
102
,
103
, . . . , and
104
and a set of slots
106
,
107
,
108
, . . . , and
109
. The number of slots may be the same as or more than the number of objects. As a result, every object should match with one and only one of the slots.
FIG. 1A
shows a matching in which objects
102
-
104
are matched with slots
107
,
106
and
109
, respectively. Each edge in
FIG. 1A
has an associated cost, with the aim being to match the maximum number of objects to slots such that the cost of the matching is minimized. One method to find the minimum cost, maximum matching is the so-called “Hungarian algorithm”. Information on this algorithm can be found in D. B. West, “Introduction to Graph Theory,” Prentice Hall, Upper Saddle River, N.J., 2001.
It has been realized that the determination of the optimal matching is similar to the determination of maximum size, minimum cost flow in a flow network.
FIGS. 1B
shows a network
130
. Elements that are substantially the same in
FIGS. 1A-1B
share the same reference numerals. In
FIG. 1B
, network
130
contains a “virtual source”
132
that originates flows to various objects in a source vertex set
134
. Virtual source
132
is not a physical source, and it is added to facilitate the determination of the optimal matching. The flows from the selected slots are collected by a “virtual sink”
138
. Virtual sink
138
is not a physical sink, and it is added to complete the flow.
The possible connections between the objects, slots, virtual source, and virtual sink are called “edges.”
FIG. 1B
shows the set of edges. Three of them are shown as reference numerals
142
-
144
. There is one requirement in the flow network
130
for the matching problem: edges do not exist between objects and between slots. Thus, there is no edge between objects
102
-
104
. Similarly, there is no edge between slots
106
-
109
. Each edge is associated with a “capacity” and a “cost.” Various prior art methods have been developed to find edges between virtual source
132
and virtual sink
138
that can deliver the maximum size, minimum cost flow from the source to the sink. Edges between vertex sets
134
and
136
with non-zero flow constitute the edges of a maximum size, minimum cost matching of objects to slots. These edges correspond to the optimal matching between objects and slots in FIG.
1
A. Information on various network flow techniques can be found in R. K. Ahuja, T. L. Magnanti and J. B. Orlin, “Network Flows,” Prentice Hall, 1993.
Prior art methods assume that the objects in vertex sets
134
and
136
are independent. However, in many applications (such as computer-aided design), some of the objects are related to each other. An example in computer-aided design is the placement of low voltage differential signaling (LVDS) input-output (I/O) ports (i.e., objects) in field programmable gate array (FPGA) devices. In an FPGA, there are many input-output block (IOB) sites (i.e., slots). Because LVDS is a differential standard, each LVDS input or output is built using two adjacent IOB sites whereas inputs or outputs of other I/O standards require only a single IOB. Consequently, the differential signals of LVDS need to be placed to adjacent IOBs.


REFERENCES:
patent: 5311443 (1994-05-01), Crain et al.
patent: 5835751 (1998-11-01), Chen et al.
patent: 6080206 (2000-06-01), Tadokoro et al.
patent: 6249902 (2001-06-01), Igusa et al.
patent: 6286128 (2001-09-01), Pileggi et al.
patent: 6421818 (2002-07-01), Dupenloup et al.
patent: 6557145 (2003-04-01), Boyle et al.
patent: 6567967 (2003-05-01), Greidinger et al.
Tanizawa and Kawahara “Clock Driven DEsign Method (CDDM) for Deep Sub-Micron ASICs,” Proceedings of the Eight Annua IEEE Internatinal ASIC Conference and Exhibit, Sep. 18-22, 1995, p. 241-244, Sep. 1995.*
Saigo et al. “Clock Skew Reduction Approach for Standard Cell,” Proceedings of the IEEE Custom Integrated Circuits Conference, May 1990.*
Dai et al. “Cost-Driven Layout for Thin-Film MCMs,” MCM-93, Proceedings., IEEE Multi-Chip Module Conference, Mar. 1993.*
Dutt, et al., “A Probability-Based Approach to VLSI Circuit Partitioning”, Department of Electrical Engineering, Univ. of Minnesota, Minneapolis, pp. 100-105, 1996.*
Cong, J et al. “Interconnect design for deep submicron ICs”, Computer-Aided Design, 1997. Digest of Technical Papers., 1997 IEEE/ACM International Conference on, Nov. 9-13, 1997. pp.:478-485.

Affiliated with

Also associated with

Rating

Placement of clock objects under constraints does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Placement of clock objects under constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Placement of clock objects under constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3220283