Manhattan routing with minimized distance to destination points

Details Manhattan routing with minimized distance to destination points Manhattan routing with minimized distance to destination points

2005-06-13

2008-05-20

Chiang, Jack (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

07376927

ABSTRACT:
For routing points to a center point, the points are grouped into a respective set disposed within each quadrant. Each point is Manhattan routed to any other point having a minimum Manhattan distance within a rectangle defined by each point and the center point, to result in at least one initial end point in each quadrant having at least one of the points. The at least one initial end point is Manhattan routed together to result in a respective final end point in each quadrant having at least one of the points. The respective final end points are routed to the center point with minimized routing distance.

REFERENCES:
patent: 3621208 (1971-11-01), Donald
patent: 5587922 (1996-12-01), Hendrickson et al.
patent: 5757656 (1998-05-01), Hershberger et al.
patent: 6178539 (2001-01-01), Papadopoulou et al.
patent: 6412100 (2002-06-01), Sasagawa et al.
patent: 6473891 (2002-10-01), Shively
patent: 6513149 (2003-01-01), Donato
patent: 6588003 (2003-07-01), Tetelbaum
patent: 6591411 (2003-07-01), Alpert et al.
patent: 6594811 (2003-07-01), Katz
patent: 6625611 (2003-09-01), Teig et al.
patent: 6651237 (2003-11-01), Cooke et al.
patent: 6851099 (2005-02-01), Sarrafzadeh et al.
patent: 7200827 (2007-04-01), Ku et al.
patent: 2005/0081173 (2005-04-01), Peyran
patent: 2006/0277520 (2006-12-01), Gennari
Sherwani N A et al, “Clock Layout for High-Performance ASIC Based on Weighted Center Algorithm”, ASIC Conference and Exhibit, 1991 Proceddings, Fourth Annual IEEE International Rochester, NY, USA 23-27, Sep. 1991, New York, NY, USA, IEEE, US, Sep. 23, 1991, pp. P15-5.1-P15-5.4, XP010048523, ISBN: 0-7803-0101-3.
Ellis G et al, “ A Hierarchical Decomposition Methodology for Single-Stage Clock Circuits”, Custom Integrated Circuits Conference, 1997, Proceedings of the IEEE 1997 Santa Clara, CA, USA May 5-8, 1997, New York, NY, USA, IEEE, US, May 5, 1997, pp. 115-118, XP010235274, ISBN: 0-7803-3669-0.
Kahng A B et al, “ A New Class of Iterative Steiner Tree Heuristics with Good Performance”, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, IEEE Service Center, Piscataway, NJ, US, vol. 11, No. 7, Jul. 1, 1992, pp. 893-902, XP000288551, ISSN: 0278-0070.
Elaheh Bozorgzadeh et al, “Creating and Exploiting Flexibility in Rectilinear Steiner Trees”, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, IEEE Service Center, Piscataway, NJ, US, vol. 22, No. 5, May 2003, pp. 605-615, XP011070725, ISSN: 0278-0070.
Jingsheng Cong et al, “Provably Good Performance-Driven Global Routing”, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, IEEE Service Center, Piscataway, NJ, US, vol. 11, No. 6, Jun. 1, 1992, pp. 739-752, XP000288536, ISSN: 0278-0070.
Cong J et al, “Performance Optimization of VLSI Interconnect Layout”, Integration, the VLSI Journal, North-Holland Publishing Company, Amsterdam, NL, vol. 21, No. 1, Nov. 1996, pp. 1-94, XP004015651, ISSN: 0167-9260.
Hwang F K, “A Primer of the Euclidean Steiner Problem” Annals of Operation Research Switzerland, vol. 33, No. 1-4, Dec. 1991, pp. 73-84, XP002391142, ISSN: 0254-5330.
Cohoon J P et al, “Critical Net Routing”, Proceedings of the International Conference on Computer Design-VLSI in Computers and Processors, Cambridge MA, Oct. 14-16, 1991, Los Alamitos, IEEE Comp. Soc. Press, US, Oct. 14, 1991, pp. 174-177, XP010025202, ISBN: 0-8186-2270-9.
Ellis Horowitz and Sartaj Sahni, “Fundamentals of Computer Algorithms” pp. 241-275, 1998, Computer Science Press, XP002392397, ISBN: 0-7167-8316-9.
Pages 430-433 of book entitled “Algorithms for VLSI Physical Design Automation”, 3rdEdition, 2001, by Naveed Sherwani, published by Kluwer Academic Publishers.

Affiliated with

Also associated with

Rating

Manhattan routing with minimized distance to destination points does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Manhattan routing with minimized distance to destination points, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Manhattan routing with minimized distance to destination points will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3983979