Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-05-22
2003-12-16
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06665850
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to the field of integrated circuit design, and particularly to a method for implementing a spanning tree method for K-dimensional space.
BACKGROUND OF THE INVENTION
The complexity encountered in the design and production of integrated circuits has grown exponentially as the number of features, speed and size of the integrated circuits has grown. For instance, integrated circuits may be found in an ever increasing range of products. To provide the desired functionality for the products, circuits may be designed specifically for the contemplated usage and/or generalized circuits may be employed capably of providing usage desired by a wide range of manufacturers and end users.
There are a wide variety of considerations that must be addressed in the design of the integrated circuit, such as timing considerations. For instance, sections of a chip may be able to perform operations in different amounts of time, such as based on the complexity of the calculation. Additionally, the transfer of data between components of an integrated circuit may be performed in different lengths of time, such time depending distance the information must travel to arrive at a desired component, and the like.
To address these timing considerations, integrated circuit may be arranged in an optimal manner, buffers employed to store data so that it is ready when needed, and the like. However, previous methods utilized to compute the placement of buffers, routing and the like were inefficient and overly complex.
Therefore, it would be desirable to provide a spanning tree system and method for K dimensional space.
SUMMARY OF THE INVENTION
Accordingly, the present invention is directed to a spanning tree method for K dimensional space. To address timing driven buffer insertion and clock routing problems clusters of points must be constructed in 3-dimensional space. The first and second dimensions are coordinates on a plane, while the third dimension is time which is arrival pin time for buffers insertion and clock latency for clock routing. In a first aspect of the present invention, a method includes partitioning an input set of points into a binary tree of partitions so that each leaf partition has maximally a defined number of points. Graph edges are made for the points by connecting each point to its closest point in every of 2
K
subspaces and the number of graph nodes is then reduced to a predefined value.
In an additional aspect of the present invention, a method for partitioning an integrated circuit includes partitioning an input set of points into a binary tree of partitions so that each leaf partition of the binary tree has maximally a defined number of points. Graph edges for the points are made by connecting each point to 2
K
closest points. The starting number of graph points is then factorized by decreasing a number of components in the set of graph points until that number becomes equal to a predefined specified program input parameter C.
In a further aspect of the present invention, a system includes a memory suitable for storing a program of instructions and a processor communicatively coupled to the memory, the processor suitable for performing a program of instructions. The program of instructions configures the processor to partition an input set of points into a binary tree of partitions so that each leaf partition of the binary tree has maximally a defined number of points. Graph edges are made for the points by connecting each point to its closest point in every of 2
K
subspaces. The number of graph nodes is reduced by factorizing a number of constructed components in the set of graph points until it becomes equal to a predefined specified program input parameter C.
It is to be understood that both the forgoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention as claimed. The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate an embodiment of the invention and together with the general description, serve to explain the principles of the invention.
REFERENCES:
patent: 5615128 (1997-03-01), Scepanovic et al.
patent: 5696692 (1997-12-01), Saldanha et al.
patent: 5818729 (1998-10-01), Wang et al.
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 6067409 (2000-05-01), Scepanovic et al.
Andreev Alexander E.
Vukovic Vojislav
Dinh Paul
Smith Matthew
Suiter-West PC LLO
LandOfFree
Spanning tree method for K-dimensional space does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Spanning tree method for K-dimensional space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning tree method for K-dimensional space will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3129554