Method and apparatus for circuit partitioning and trace...

Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C716S030000, C716S030000

Reexamination Certificate

active

10792933

ABSTRACT:
Methods and apparatuses for incremental circuit partitioning and incremental trace assignment. In one embodiment of the present invention, a cost function based on both the partitioning solution and the trace assignment solution is used for the partitioning of a circuit; in reducing the cost function, blocks of circuits are moved among partitions and the trace assignment are updated accordingly to evaluate the cost function. In one embodiment, the traces and nets are grouped according to the partitions they connect for trace assignment. In one embodiment, a flow diagram is constructed for assigning nets to traces; and, maximum flow algorithms are used. In one embodiment, a flow diagram includes feedthrough solutions, in which flow conservation is not preserved at certain nodes. In one embodiment, integer linear programming techniques are used for assigning nets to traces. In one embodiment, a distribution of nets, which defines the numbers of blocks that each net has in each partition, is computed and maintained for efficient determination of the number of nets in net groups.

REFERENCES:
patent: 5113352 (1992-05-01), Finnerty
patent: 5218551 (1993-06-01), Agrawal et al.
patent: 6480991 (2002-11-01), Cho et al.
patent: 6907592 (2005-06-01), Dante
patent: 6996512 (2006-02-01), Alpert et al.
patent: 7107563 (2006-09-01), Kong
C. Fiduccia and R. Mattheyses, “A linear-time heuristic for improving network partitions”, In Proceedings of the Design Automation Conference, 1982.
Scott Hauck and Gaetano Borriello, “Logic Partition Orderings for Multi-FPGA Systems”, ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, pp. 32-38, Feb. 1995.
Scott Hauck and Gaetano Borriello, “An Evaluation of Bipartitioning Techniques”, IEEE Trans. On CAD, vol. 16, No. 8, pp. 849-866, Aug. 1997.
Thomas H. Corman, et al., “Introduction to Algorithms”, the MIT Press, Nineteenth printing, Chapter 27, pp. 579-629, 1997.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for circuit partitioning and trace... 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 and apparatus for circuit partitioning and trace..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for circuit partitioning and trace... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-3861893

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.