Method for placing modules on a carrier

Claim 2

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.

Claim 3

Method according to claim 1, wherein the area centers of gravity of the placement region and of the sub-regions are their respective center coordinates.

Claim 4

Method according to claim 1, wherein the global placement and partitioning is ended when one module is arranged in every sub-region.

Claim 5

Method according to claim 1, wherein the optimum area exploitation ensues by identifying all possible divisions of the sub-regions having up to k modules upon utilization of the results of the global placement.

Claim 6

Method according to claim 4, wherein the arrangement of the modules in the sub-regions is optimized in that all possible sectionings are identified for every sub-region and the modules are allocated to the sub-areas that have arisen; wherein the dimensions of the smallest rectangular region wherein the modules can be placed overlap-free are calculated for every sectioning and module allocation and the various possible dimensions of a sub-area are combined in a form function; and wherein this is implemented for all sub-regions and the dimensions of all allowable module arrangements are calculated by addition of the form functions of all sub-regions.

Claim 7

Method according to claim 5, wherein the rotational positions of the modules are optimized.

Claim 8

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: ______________________________________ 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.

Claim 9

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: ______________________________________ 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.

Claim 10

Method according to claim 7, wherein the fixed modules are displaceable in x-direction or, respectively, y-direction at the edges of the placement region.

Claim 11

Method according to claim 8, wherein the allocation of the modules to the sub-regions ensues by sorting the modules according to the x, y-coordinates.

Claim 12

Method according to claim 9, wherein the subdivision of the placement region and of the sub-regions ensues by horizontal and vertical lines of section and modules sub-sets are allocated to the sub-regions achieved by the sectionings.

Claim 13

Method according to claim 10, wherein a respective bipartition of every region ensues in the partitioning.

Claim 14

Method according to claim 11, wherein modules whose allocated connections transgress the line of section are allocated to the sub-regions given the additional application of the min-cut principle.

Claim 15

Method according to claim 7, wherein the global placement and partitioning is ended when one module is arranged in every sub-region.

Claim 16

Method according to claim 7, wherein the optimum area exploitation ensues by identifying all possible divisions of the sub-regions having up to k modules upon utilization of the results of the global placement.

Claim 17

Method according to claim 14, wherein the arrangement of the modules in the sub-regions is optimized in that all possible sectionings are identified for every sub-region and the modules are allocated to the sub-areas that have arisen; wherein the dimensions of the smallest rectangular region wherein the modules can be placed overlap-free are calculated for every sectioning and module allocation and the various possible dimensions of a sub-area are combined in a form function; and wherein this is implemented for all sub-regions and the dimensions of all allowable module arrangements are calculated by addition of the form functions of all sub-regions.

Claim 18

Method according to claim 15, wherein the rotational positions of the modules are optimized.