Architectures for Parallel Slicing Enumeration in VLSI Layout

This paper presents parallel algorithms for solving the final placement problem of rectangular cells with predefined neighborhood relations. Optimum solutions for small cell subsets are obtained by enumerating all arrangements, i.e. slicing structures. These solutions are combined in a global construction step such that they fit well into the global arrangement.An increased size of the enumerated local subproblems leads to placements that are closer to a global optimum. However, this requires significantly larger computing resources. Parallel computers provide huge amounts of computing power and memory that can be used to meet these high demands.In this paper, we present new algorithms to solve this problem on several parallel architectures. By adjusting the granularity of the algorithm to the properties of the specific target architecture, we achieve significant speed-ups.