Browse Prior Art Database

Algorithm for Partitioning Improvement

IP.com Disclosure Number: IPCOM000080642D
Original Publication Date: 1974-Jan-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Donath, WE: AUTHOR

Abstract

This algorithm essentially consists of generating a set of "move sequences" with associated costs. The move sequence with lowest cost is investigated if it actually represents an improvement of the partition, without violating any of the constraints; if that is the case, it is accepted and the partition is modified, and the process of generating move sequences is started over. Otherwise, new move sequences are generated from this move sequence by adding one more move to this sequence, unless the move sequence has reached some preset length, when it is discarded.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Algorithm for Partitioning Improvement

This algorithm essentially consists of generating a set of "move sequences" with associated costs. The move sequence with lowest cost is investigated if it actually represents an improvement of the partition, without violating any of the constraints; if that is the case, it is accepted and the partition is modified, and the process of generating move sequences is started over. Otherwise, new move sequences are generated from this move sequence by adding one more move to this sequence, unless the move sequence has reached some preset length, when it is discarded.

The process stops either when the process runs out of move sequences or when it reached a preset limit on the number of move sequences to be investigated. Also, the move sequence list is finite; should its capacity be exceeded, then move sequences with the largest cost are discarded.

More detail regarding the implementation of the algorithm is as follows: 1. Manipulation of Move Sequences.

The lowest level of the process is the move sequence file (MSF), which consists of three arrays:
1) The index array.
2) The primary file.
3) The secondary file. The primary file holds, for each move sequence, the following:
1) The cost of the move sequence.
2) A set of moves, each consisting of node number and the

module it is to be moved to.
3) A delimiter (0 in our case). The index array holds a set of pointers to the first entry in each move sequence which corresponds to the cost.

Newly generated move sequences are added to the primary file; should the primary file be filled, "garbage collection" is done by transferring the contents of the primary file in order of the secondary file, and changing the values of the index list. The secondary file may be smaller than the primary file, in which case the capacity of the secondary file may be exceeded; in that case, transfer of move sequences is stopped and the move sequence list is truncated, before the secondary list is copied back onto the primary move sequence list. 2. Gener...