Method for placing modules on a carrier
First Claim
1. Method for placing modules consisting of moveable modules and fixed modules on a carrier using a computer, a module list containing dimensions of the modules and a network list containing connections of the modules, comprising the steps of:
- a) arranging all movable modules on the placement region of the carrier by global placement such that the overall center of gravity of the modules lies on an area center of gravity of the placement region and all fixed modules are arranged at edges of the placement region;
b) in a partitioning step,b1) subdividing the placement region into sub-regions,b2) dividing the modules into subsets and assigning the subsets to the sub-regions on the basis of the position of the modules determined in step a),b3) ultimately defining the size of the sub-regions by the ratio of subsets of the modules assigned to the sub-regions;
c) simultaneously arranging the modules in a global placement for all sub-regions given mutual influencing that extends beyond the sub-regions and taking into consideration connections contained in the network list, such that overall centers of gravity of the subsets of the modules respectively lie on area centers of gravity of the sub-regions;
d) in a further partitioning step,d1) dividing the sub-regions into further sub-regions,d2) assigning the modules to the further sub-regions on the basis of the position of the modules defined in step c),d3) ultimately defining the size of the further sub-regions by the ratio of the modules assigned to in the further sub-regions;
e) continuing the steps c) and d) until at most a predetermined plurality of k modules is assigned to every sub-region.
1 Assignment
0 Petitions
Accused Products
Abstract
Method for placing modules on a carrier. Modules, for example cells, are placed on a carrier, for example a chip, with the method. For placement, the modules are arranged such on the placement region of the carrier that the center of gravity of the modules falls onto the center coordinates of the placement region (global placement S1). Subsequently, the placement region is partitioned into sub-regions, modules are allocated to the sub-regions and the area of the sub-regions is defined in the ratio of the area of the modules allocated to these sub-regions (partitioning, S2). In the next step, a global placement is again carried out, i.e. the modules are arranged such in the sub-regions that the modules allocated to the sub-regions have their center of gravity falling onto the center coordinates of these sub-regions. The steps of global placement and of partitioning follow one another until only at most k modules are still present per sub-region. The ultimate position of the modules is then implemented with the assistance of an optimization step (S3), wherein the position for the modules whereat the area exploitation is optimum is calculated taking the position of the modules achieved in the global placement into consideration.
-
Citations
16 Claims
-
1. Method for placing modules consisting of moveable modules and fixed modules on a carrier using a computer, a module list containing dimensions of the modules and a network list containing connections of the modules, comprising the steps of:
-
a) arranging all movable modules on the placement region of the carrier by global placement such that the overall center of gravity of the modules lies on an area center of gravity of the placement region and all fixed modules are arranged at edges of the placement region; b) in a partitioning step, b1) subdividing the placement region into sub-regions, b2) dividing the modules into subsets and assigning the subsets to the sub-regions on the basis of the position of the modules determined in step a), b3) ultimately defining the size of the sub-regions by the ratio of subsets of the modules assigned to the sub-regions; c) simultaneously arranging the modules in a global placement for all sub-regions given mutual influencing that extends beyond the sub-regions and taking into consideration connections contained in the network list, such that overall centers of gravity of the subsets of the modules respectively lie on area centers of gravity of the sub-regions; d) in a further partitioning step, d1) dividing the sub-regions into further sub-regions, d2) assigning the modules to the further sub-regions on the basis of the position of the modules defined in step c), d3) ultimately defining the size of the further sub-regions by the ratio of the modules assigned to in the further sub-regions; e) continuing the steps c) and d) until at most a predetermined plurality of k modules is assigned to every sub-region. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. Method for placing modules consisting of moveable modules and fixed modules on a carrier upon employment of a module list containing dimensions of the modules and of a network list containing connections of the modules, comprising the steps of:
-
a) arranging all movable modules on the placement region of the carrier by global placement such that the overall center of gravity of the modules lies on an area center of gravity of the placement region and all fixed modules are arranged at edges of the placement region; b) in a partitioning step, b1) subdividing the placement region is subdivided into sub-regions, b2) assigning the modules to the sub-regions on the basis of the position of the modules determined in step a), b3) ultimately defining the size of the sub-regions in the ratio of the modules to be arranged in the sub-regions; c) simultaneously arranging the modules in a global placement for all sub-regions such that their overall center of gravity respectively lies on area centers of gravity of the allocated sub-regions, the area centers of gravity of the placement region and of the sub-regions being their respective center coordinates and, for the global placement, x, y coordinates of the modules being simultaneously determined such that ##EQU4## becomes a minimum and such that secondary conditions ##EQU5## for 1≦
r≦
R are observed for the placement region or, respectively, for every sub-region, whereby the characters employed in the equations have the following significances;
space="preserve" listing-type="tabular">______________________________________ m module number n network number M = ( . . . , m, . . . ) set of the module numbers N = ( . . . , n, . . . ) set of the network numbers M.sub.b C M set of the movable modules M.sub.f C M set of the fixed modules b number of movable modules f number of fixed modules x = ( . . . x.sub.n . . . x.sub.m . . . ) vector of the x-coordinates of all networks and modules y = ( . . . y.sub.n . . . y.sub.m . . . ) vector of the y-coordinates of all networks and modules u.sub.nm x-coordinate of the terminal of the network n at the module m v.sub.nm y-coordinate of the terminal of the network n at the module m t.sub.nm = 1 in case the network n is connected to the module m 0 in case it is not connected w.sub.n weighting factor of the network n F.sub.m surface requirement of the module m r number of the placement region PL or of a sub-region PLT M.sub.r C M.sub.b set of modules onto which the secondary condition r is applied X.sub.r, Y.sub.r center coordinates of the r.sup.th placement region PL, PLT R number of sub-regions PLT[.] ______________________________________d) in a further partitioning step, d1) dividing the sub-regions into further sub-regions, d2) allocating the modules to the further sub-regions on the basis of the position of the modules defined in step c), d3) ultimately defining the size of the further sub-regions in the ratio of the modules to be arranged in the further sub-regions; e) continuing the steps c) and d) until at most a prescribable plurality of k modules is allocated to every sub-region. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14, 15, 16)
-
Specification