A Massively Parallel 2D Rectangle Placement Method

Abstract

Layout design is a frequently occurring process that often
combines human and computer reasoning. Because of the combinatorial
nature of the problem, solving even a small size input involves searching
a prohibitively large state space. An algorithm PEMS (Pseudo-exhaustive
Edge Minimizing Search) is proposed for approximating a 2D rectangle
packing variant of the problem. The proposed method is inspired
by MERA (Minimum Enclosing of Rectangle Area) [1] and MEGA
(Minimum Enclosing Under Gravitational Attraction) [2], yet produces
higher quality solutions, in terms of final space utilization. To address
the performance cost, a CUDA based acceleration algorithm is developed
with significant speedup.