Multiple-layer contour searching method and apparatus for circuit building block placement
First Claim
1. A method for compacting a set of objects, comprising the steps of:
- (a) defining a set of N unrefined objects, each of said unrefined objects having at least one object profile, each of said objects having at least one layer;
(b) defining a set of refined objects;
(c) defining an object area, said object area having a vertical axis defining an upper and a lower end, said object area having a horizontal axis having a base width;
(d) placing said set of unrefined objects within and at said upper end of said object area, said placement defining a first unrefined configuration;
(e) removing a first removed object from said set of unrefined objects by selecting a lowest unrefined object along a longest critical path;
said first unrefined configuration no longer including said first removed object, said first removed object no longer included in said set of unrefined objects;
(f) defining a first unrefined profile for at least one of said layers of said first unrefined configuration;
(g) defining a first refined profile for a first refined configuration, said first refined profile located within and at a lower end of said object area;
(h) finding a lowest cost for placing said first removed object along said first refined profile by iteratively positioning the first removed object along the first refined profile at matching points selected according to a matching of a curvature between a refined side of the first removed object and the first refined profile and a matching of a curvature between an unrefined side of the first removed object and the first unrefined profile; and
(i) placing said first removed object at a point along said first refined profile associated with said lowest cost.
4 Assignments
0 Petitions
Accused Products
Abstract
Apparatus and methods for two-dimensional compaction of object collections defines an initial set of unrefined objects and an initial compaction direction. One by one, each unrefined object is taken from the unrefined object configuration and placed within a refined configuration. Both unrefined and refined configurations possess profiles along which the selected object is placed. Pruning rules select which locations to investigate more closely, by eliminating those positions that clearly do not provide compaction improvement. Various orientations and/or shapes of an object can be tried to improve the compaction or the group of objects. Once a best location for the object is found, the object is included in the refined object set, new unrefined and refined profiles are constructed, and a new unrefined object is selected to place. Once all unrefined objects have been selected and placed, the compaction process for the chosen direction has completed. The process can continue for other compaction directions, and as many times as required, to compact the collection of objects within a certain tolerance. The cost function employed to determine best object positions can include costs of wire interconnection lengths.
52 Citations
21 Claims
-
1. A method for compacting a set of objects, comprising the steps of:
-
(a) defining a set of N unrefined objects, each of said unrefined objects having at least one object profile, each of said objects having at least one layer; (b) defining a set of refined objects; (c) defining an object area, said object area having a vertical axis defining an upper and a lower end, said object area having a horizontal axis having a base width; (d) placing said set of unrefined objects within and at said upper end of said object area, said placement defining a first unrefined configuration; (e) removing a first removed object from said set of unrefined objects by selecting a lowest unrefined object along a longest critical path;
said first unrefined configuration no longer including said first removed object, said first removed object no longer included in said set of unrefined objects;(f) defining a first unrefined profile for at least one of said layers of said first unrefined configuration; (g) defining a first refined profile for a first refined configuration, said first refined profile located within and at a lower end of said object area; (h) finding a lowest cost for placing said first removed object along said first refined profile by iteratively positioning the first removed object along the first refined profile at matching points selected according to a matching of a curvature between a refined side of the first removed object and the first refined profile and a matching of a curvature between an unrefined side of the first removed object and the first unrefined profile; and (i) placing said first removed object at a point along said first refined profile associated with said lowest cost. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A system for compacting of a set of objects, comprising:
-
a logic processor; an object register connected to said logic processor for storing data related to said set of objects, each of said objects having a position attribute for determining its position within a defined two-dimensional area; an unrefined object register connected to said logic processor for storing a listing of a set of unrefined objects of said set of objects; an unrefined profile register connected to said logic processor for storing an unrefined profile of said set of unrefined objects; a refined object register connected to said logic processor for storing a listing of a set of refined objects of said set of objects; a refined profile register connected to said logic processor for storing a refined profile of said set of refined objects; and a cost optimizer operated on by said logic processor for selecting one of said unrefined objects stored in said unrefined object register, said cost optimizer determining a position attribute for said selected object by matching a curvature of said selected object with a curvature of said unrefined profile and by matching a curvature of said selected object with a curvature of said refined profile. - View Dependent Claims (21)
-
Specification