ON IMPLEMENTATION CHOICES FOR ITERATIVE IMPROVEMENT PARTITIONING ALGORITHMS

Iterative improvement partitioning algorithms such as the FM algorithm of Fiduccia and Mattheyses [8], the algorithm of Krishnamurthy [13], and Sanchis's extensions of these algorithms to multiway partitioning [16] all rely on efficient data structures to select the modules to be moved from one partition to the other, The implementation choices for one of these data structures, the gain bucket, is investigated, Surpr isingly, selection from gain buckets maintained as last-in-first-out ( LIFO) stacks leads to significantly better results than gain buckets m aintained randomly (as in previous studies of the FM algorithm [13], [ 16]) or as first-in-first-out (FIFO) queues. In particular, LIFO bucke ts result in a 36% improvement over random buckets and a 43% improveme nt over FIFO buckets for minimum-cut bisection, Eliminating randomizat ion from the bucket selection not only improves the solution quality, but has a greater impact on FM performance than adding the Krishnamurt hy gain vector. The LIFO selection scheme also results in improvement over random schemes for multiway partitioning [16] and for more sophis ticated partitioning strategies such as the two-phase FM methodology [ 2], Finally, by combining insights from the LIFO gain buckets with the Krishnamurthy higher-level gain formulation, a new higher-level gain formulation is proposed, This alternative formulation results in a fur ther 22% reduction in the average cut cost when compared directly to t he Krishnamurthy formulation for higher-level gains, assuming LIFO org anization for the gain buckets.