A Massively Parallel 2D Rectangle Placement Method

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.