Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-10-12
2004-08-17
Coby, Frantz (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C709S251000, C709S227000, C711S114000, C711S165000, C257S208000, C365S205000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06778999
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for distributing a set of objects among a set of containers, for example, in an integrated circuit, and in particular relates to a method for improving the distribution of a set of circuits on a chip, balancing the load and/or fanout of a set of equivalent clock drivers in a clock tree, or placing data files on servers in a computer network.
2. Description of Related Art
Many integrated circuit design and other applications may be analogized as a set of objects, each of which is assigned to or placed in one of a set of containers. For example, in a clock optimization application on an integrated circuit, the containers may represent clock nets, with the objects representing clock sinks at specific locations on a chip. In a chip placement application, the containers may represent regions of a chip and the objects may represent circuits to be placed on the chip. In a network computing application, the containers may represent network server computers and the objects might represent large data files or databases residing on those servers.
In such an analog, one may assume that the application has the following characteristics:
Each object starts out assigned to an initial container, according to some set of criteria. In the clock optimization application an initial location-based sink clustering may define an initial set of clock nets. In the chip placement application an initial force-directed placement might be used to establish an initial placement. In the network workload optimization application, the initial assignment might place each file on the server closest to the file's point of creation.
The containers have some spatial relationship with each other, i.e., each container X has a set of closest neighbor containers, each at some distance from X. In the clock optimization application the distance might be the rectilinear distance between the centroids (mean sink X and Y coordinates) of neighboring nets. In the chip placement application the distance might be the rectilinear distance between the centers of adjacent regions. In the network workload optimization application the distance might be inversely related to the channel capacity between adjacent servers.
Each container has some capacity and each object has a size, and the initial assignment of objects to containers may cause some containers to exceed their capacity, i.e., contain too many objects, and others may be underfilled, i.e., have too few objects. Alternatively, an objective of the object distribution may be to equalize the occupancy of all containers; this can be seen as equivalent to the capacity model by considering the capacity of each container to be the average occupancy of all containers. In the clock optimization application the objective might be to equalize the load (occupancy) of each clock net, and the size of each clock sink might be related to its input load. In the chip placement application the container capacity might be the amount of uncommitted area in the region represented by the container, and the size of the circuits to be placed might be the areas they occupy. In a network workload optimization application the server capacity might be the available processing power of the server and the file size might be related to the frequency of queries related to it and the computation required to respond to those queries. Alternatively, the server capacity might be related to the disk space available to store the files and the file size might be related to the disk space required to store the file.
There is some cost associated with moving an object from its initial container which increases rapidly with the distance that the object is moved. In the clock optimization application this might be because of the additional wire required to connect widely separated sinks. In the chip placement application, this might be because of the additional wire required to connect nets to a circuit which is moved from its “ideal” location. In the network optimization application this might be the network bandwidth required to move the files.
A common approach to improving the distribution of objects between containers is to consider a pair or other small set of neighboring containers and to redistribute the objects between those containers so as to equalize the occupancy of each relative to its capacity. This is done repeatedly on all pairs or sets of neighboring clusters until convergence is achieved or some iteration limit is reached. This may require many iterations over all pairs of neighbors. One may consider the following list of numbers, representing the occupancy of a serially connected set of containers, and assume that the objective is to equalize the occupancy of all containers:
90
50
50
50
10
The iterative method described above might proceed as follows. Each of the following lines represents the state after the underlined pair of containers has been balanced. In each step it is assumed that the iterative algorithm always attacks the pair of neighbors with the largest occupancy difference, which are shown underlined:
EXAMPLE I
1.
70
70
50
50
10
2.
70
70
50
30
30
3.
70
60
60
30
30
4.
70
60
45
45
30
5.
70
53
52
45
30
6.
62
61
52
45
30
7.
62
61
52
38
37
8.
62
61
45
45
37
9
62
53
53
45
37
10.
58
57
53
45
37
11.
58
57
49
49
37
12.
58
57
49
43
43
13.
58
53
53
43
43
14.
58
53
48
48
43
15.
56
55
48
48
43
16.
56
52
51
48
43
17.
56
52
51
46
45
18.
56
52
49
48
45
19.
54
54
49
48
45
20.
54
52
51
48
45
21.
54
52
51
47
46
22.
54
52
49
49
46
23.
54
51
50
49
46
24.
52
52
50
49
46
25.
53
52
50
48
47
26.
53
52
49
49
47
27.
53
51
50
49
47
28.
52
52
50
49
47
29.
52
52
50
48
48
30.
52
51
51
48
48
31.
52
51
50
49
48
Two observations can be made from this example. First, it takes a long time to converge. Second, it doesn't actually converge to a completely balanced solution. The latter occurs because the granularity of objects prevents any local redistribution (since the final occupancy difference between all pairs of adjacent containers is one), even though a better global balance could be achieved by setting the occupancy of each container at 50.
Bearing in mind the problems and deficiencies of the prior art, it is therefore an object of the present invention to provide an improved method for distributing a set of objects on an integrated circuit.
It is another object of the present invention to provide a method for distributing a set of objects on an integrated circuit which converges more quickly than prior art methods.
A further object of the invention is to provide a method for distributing a set of objects on an integrated circuit which achieves better balance than prior art methods.
It is yet another object of the present invention to provide a method for distributing a set of objects on an integrated circuit which may be used for placement of a set of circuits on a chip, balancing the load and/or fanout of a set of equivalent clock drivers in a clock tree, or distributing large data files, e.g., databases, on network server computers.
Still other objects and advantages of the invention will in part be obvious and will in part be apparent from the specification.
SUMMARY OF THE INVENTION
The above and other objects and advantages, which will be apparent to one of skill in the art, are achieved in the present invention which is directed to, in a first aspect, a method of determining redistribution of objects among three or more containers in a network comprising determining an initial set of objects in each of the containers and identifying neighboring pairs of containers. The method then includes determining a cost of moving objects between each of the neighboring pairs of containers, determining a desired change in occupancy of each container, and subsequently determining a desired total size of a set of objects to be moved between each identified neighboring pair of containers by solving a set of simultaneous linear equations. The method may further include redistributing the objects among the neighboring pai
Coby Frantz
DeLio & Peterson LLC
International Business Machines - Corporation
Peterson Peter W.
LandOfFree
Method for distributing a set of objects in computer... 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 for distributing a set of objects in computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for distributing a set of objects in computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3330681