GIT-CERCS-03-31
Ramprasad Ravichandran, Nihal Ladiwala, Jean Nguyen, Sung Kyu Lim, Mike Niemier,
Automatic Placement for Quantum Cell Automata
Quantum-dot Cellular Automata (QCA) is a novel computing mechanism that can
represent binary information based on spatial distribution of electron charge
configuration in chemical molecules. It has the potential to allow for circuits
and systems with functional densities that are better than end of the roadmap
CMOS, but also imposes new constraints on system designers. Several recent
works concentrated on partitioning and global placement in the context of QCA
schematics based on constraints imposed by this architecture. In this paper we
develop the first cell-level placement of QCA circuits, where the given circuit
is assumed to be partitioned into 4-phase asynchronous QCA timing zones. We
formulate the QCA cell placement in each timing zone as a unidirectional
geometric embedding of k-layered bipartite graphs. We then present an
analytical and a stochastic solution for minimizing the wire crossings and wire
length in these placement solutions. Results provide designs of circuits and systems that will be used to develop computationally interesting
designs for chemists who are currently preparing to build the patterns and
substrates required for real QCA circuits.