Parallel algorithms for slicing based final placement

This paper presents parallel algorithms for solving the final placement problem of rectangular modules assuming predefined neighborhood relations between the modules to be placed. By enumerating all arrangements, i.e. slicing structures, of local module subsets optimum solutions are obtained. They are combined in a global evaluation step such that the local solutions fit well into the global arrangement. Increased size of the enumerated local subproblems leads to placements that are closer to a global optimum. The resulting higher computational demands can be met by using parallel computers that provide huge amounts of computing power and distributed memory. Therefore, we propose new algorithms for the enumeration on message-passing parallel computers. Experimental results show that significant speedups as well as better results can be achieved.