TY - GEN
T1 - Dynamic iterative method for fast network partitioning
AU - Jeong, Chang Sung
AU - Song, Young Min
AU - Jo, Sung Up
PY - 2000
Y1 - 2000
N2 - In this paper, we address multiway network partitioning problem of dividing the cells of network into multiple blocks so as to minimize the number of nets interconnecting cells in different blocks while balancing the blocks' sizes. The sequential iterative improvement algorithm for the problem consists of several passes each of which is performed by repeatedly iterating the move operation. Therefore, the whole execution time taken by the algorithm is greatly affected by the number of the move operations and the execution time for each move operation. We present a fast parallel algorithm for solving the multiway network partiotioning problem by reducing both of them. We propose a new dynamic iterative method which reduces the number of move operations executed at each pass dynamically, and hence speed up the whole algorithm sharply. Moreover, we reduced the execution time of each move by its parallelization using the proper cell distribution.
AB - In this paper, we address multiway network partitioning problem of dividing the cells of network into multiple blocks so as to minimize the number of nets interconnecting cells in different blocks while balancing the blocks' sizes. The sequential iterative improvement algorithm for the problem consists of several passes each of which is performed by repeatedly iterating the move operation. Therefore, the whole execution time taken by the algorithm is greatly affected by the number of the move operations and the execution time for each move operation. We present a fast parallel algorithm for solving the multiway network partiotioning problem by reducing both of them. We propose a new dynamic iterative method which reduces the number of move operations executed at each pass dynamically, and hence speed up the whole algorithm sharply. Moreover, we reduced the execution time of each move by its parallelization using the proper cell distribution.
UR - https://www.scopus.com/pages/publications/84944048003
UR - https://www.scopus.com/pages/publications/84944048003#tab=citedBy
U2 - 10.1007/3-540-45492-6_9
DO - 10.1007/3-540-45492-6_9
M3 - Conference contribution
AN - SCOPUS:84944048003
SN - 9783540675532
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 81
EP - 88
BT - High Performance Computing and Networking - 8th International Conference, HPCN Europe 2000, Proceedings
A2 - Bubak, Marian
A2 - Afsarmanesh, Hamideh
A2 - Hertzberger, Bob
A2 - Williams, Roy
PB - Springer Verlag
T2 - 8th International Conference on High Performance Computing and Networking, HPCNEurope 2000
Y2 - 8 May 2000 through 10 May 2000
ER -