Ravichandran, Lim, and Niemier develop the first cell-level placement of quantum-dot cellular automata (QCA) circuits to help automate the design process. QCA placement proceeds in three steps: zone partitioning, zone placement, and cell placement. The paper focuses on the last step. It proposes performing cell placement with the help of a k-layered bipartite graph, in which each edge (x,y) joins vertices x and y from partitions (layers) p and p+1, respectively.
Cell placement is done in three stages. The feed-through insertion stage adds feed-through gates to the original graph to satisfy both the relative ordering and the signal direction constraint. The second stage, row folding, is designed to decrease the number of the zone’s global column, by folding rows with a large number of gates into at least two rows. The last stage is designed to minimize wire length and wire crossing. This is a nondeterministic polynomial time (NP) hard problem. The authors solve it by using a barycenter heuristic, followed by simulated annealing.