Placement & Routing for Tile-based Field-coupled Nanocomputing Circuits is NP-complete
Sprache des Titels:
Englisch
Original Kurzfassung:
Field-coupled Nanocomputing (FCN) technologies provide an alternative to conventional CMOS-based computation technologies and are characterized by intriguingly low energy dissipation. Accordingly, their design
received significant attention in the recent past. FCN circuit implementations like Quantum-dot Cellular
Automata (QCA) or Nanomagnet Logic (NML) have already been built in labs and basic operations such
as inverters, Majority, AND, OR, etc. are already available. The design problem basically boils down to
the question how to place basic operations and route their connections so that the desired function results
while, at the same time, further constraints (related to timing, clocking, path lengths, etc.) are satisfied.
While several solutions for this problem have been proposed, interestingly no clear understanding about the
complexity of the underlying task exists thus far. In this research note, we consider this problem and eventually prove that placement and routing for tile-based FCN circuits is N P-complete. By this, we provide a
theoretical foundation for the further development of corresponding design methods.
Sprache der Kurzfassung:
Englisch
Journal:
ACM Journal on Emerging Technologies in Computing Systems
Forschungs-