Name
Abstract | ||
|---|---|---|
The paper investigates the following multiple-way network-partitioning problem: given a network with sizes for its cells, partition the cells of the network into multiple blocks so as to minimize the number of nets interconnecting cells in different blocks while balancing the blocks' sizes. There is conflict between the two objectives, the minimizing of cutset costs and size balancing. The concepts of balance cost and balance gain are used to represent the degree of size balancing of a partition. A new cost function is proposed which accommodates the inherent conflict by combining the two objectives into a single weighted sum. An iterative improvement algorithm for the network-partitioning problem that uses the cost function is then presented. In comparison with existing algorithms, which are efficient only when the variance in the cell sizes is not too large, the proposed algorithm deals with a large size variance efficiently without any performance degradation. Experimental results for a variety of networks show that the proposed algorithm outperforms the Sanchis algorithm, which is the only existing multiple-way network-partitioning algorithm that the authors have found. The performance gap between the proposed algorithm and the Sanchis algorithm becomes bigger as the variance in cell size and/or the number of blocks to be partitioned increase. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1016/0010-4485(93)90084-2 | COMPUTER-AIDED DESIGN |
Keywords | Field | DocType |
ELECTRONICS-DESIGN AUTOMATION, CIRCUIT PARTITIONING, MULTIPLE-WAY NETWORK-PARTITIONING PROBLEMS, KERNIGHAN-LIN ALGORITHM, CUTSETS, SIZE BALANCES | Mathematical optimization,Computer science,Circuit design,Algorithm,Automation,Partition (number theory),Electronic circuit,Integrated circuit,Performance gap,Partition method | Journal |
Volume | Issue | ISSN |
25 | 5 | 0010-4485 |
Citations | PageRank | References |
1 | 0.37 | 10 |
Authors | ||
3 | ||