EUVIMEDEUVIMED entdecken
Crossref

Placement and Routing for Tile-based Field-coupled Nanocomputing Circuits Is NP -complete (Research Note)

Marcel Walter, Robert Wille, Daniel Große, Frank Sill Torres, Rolf Drechsler

ACM Journal on Emerging Technologies in Computing Systems · 31.07.2019 · 15 (3) · 1-10

DOI: 10.1145/3312661 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Journal on Emerging Technologies in Computing Systems, online erschienen am 22.04.2019. Verfasst von Marcel Walter und 4 weiteren Autor:innen. Die Arbeit wurde bisher 32-mal zitiert (Crossref) und nennt 38 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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, and so on, are already available. The design problem basically boils down to the question of 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 NP -complete. By this, we provide a theoretical foundation for the further development of corresponding design methods.

Zitieren

APA

Walter, M., Wille, R., Große, D., Torres, F. S., & Drechsler, R. (2019). Placement and Routing for Tile-based Field-coupled Nanocomputing Circuits Is NP -complete (Research Note). ACM Journal on Emerging Technologies in Computing Systems, 15(3), 1-10. https://doi.org/10.1145/3312661

Vancouver

Walter M, Wille R, Große D, Torres FS, Drechsler R. Placement and Routing for Tile-based Field-coupled Nanocomputing Circuits Is NP -complete (Research Note). ACM Journal on Emerging Technologies in Computing Systems. 2019;15(3):1-10. doi:10.1145/3312661

BibTeX
@article{Walter2019,
  author = {Walter, Marcel and Wille, Robert and Große, Daniel and Torres, Frank Sill and Drechsler, Rolf},
  title = {Placement and Routing for Tile-based Field-coupled Nanocomputing Circuits Is NP -complete (Research Note)},
  journal = {ACM Journal on Emerging Technologies in Computing Systems},
  year = {2019},
  volume = {15},
  number = {3},
  pages = {1--10},
  doi = {10.1145/3312661}
}
Kostenlos starten →