Some experimental results on placement techniques

Abstract

Seven placement algorithms - one constructive-initial placement algorithm and six iterative-improvement algorithms - were programmed and run on six problems ranging in size from 60 to 1300 modules. These problems included placing IC packs on a card, cards on a board and circuits on an LSI chip. It was found that the new force-directed pairwise relaxation algorithm was the best algorithm for the larger problems and was competitive with the other algorithms for the smaller problems. Other questions relating to placement strategies (such as, what are the advantages of constructive - initial start vs. random start and what is the best transformation of the placement problem to an associated quadratic assignment problem) are also answered.