Topology aware mapping of logic functions onto nanowire-based crossbar architectures

ABSTRACT

Highly regular, nanodevice based architectures have been proposed to replace pure CMOS based architectures in the emerging post CMOS era. Since bottom-up self-assembly is used to build these architectures, regular nanowire crossbars are emerging as a promising candidate. While these regular structures resemble CMOS programmable logic arrays (PLAs), PLA logic synthesis methodologies fail to solve the associated problems since the length and connectivity constraints imposed by individual nanowires in these crossbars translate into challenges hitherto not considered. These strict topological constraints should be considered while mapping Boolean functions onto nanowire crossbars during logic synthesis. We develop a mathematical model for this problem, an algorithm to solve it and three heuristics to improve the algorithm runtime.

REFERENCES

• 1: European Commission, Technology Roadmap for Nanoelectronics, 2001.
• 2: ITRS, International Technology Roadmap for Semiconductors Emerging Research Devices, 2004.
• 3: M. S. Montemerlo, J. C. Love, G. J. Opitech, D. G. Gordon and J. C. Ellenbogen, Technologies and Designs for Electronic Nanocomputers, MITRE, July 1996.
• 4: Victor V. Zhirnov , Daniel J. C. Herr, New Frontiers: Self-Assembly and Nanoelectronics, Computer, v.34 n.1, p.34-43, January 2001
• 5: P. J. Kuekes, D. R. Stewart and R. S. Williams, "The Crossbar Latch: Logic Value Storage, Restoration, and Inversion in Crossbar Circuits", Journal of Applied Physics, vol. 97, n. 3, pp. 034301, July 2005.
• 6: A. DeHon, "Array-Based Architecture for FET-Based, Nanoscale Electronics", IEEE Transactions on Nanotechnology, vol. 2, n. 1, pp. 23--32, 2003.
• 7: Andre DeHon , Michael J. Wilson, Nanowire-based sublithographic programmable logic arrays, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968299]
• 8: G. Snider and W. Robinett, "Crossbar Demultiplexers for Nano-electronics Based on n-Hot Codes", IEEE Transactions on Nanotechnology, vol. 4, pp. 249--254, 2005.
• 9: C. P. Collier, E. W. Wong, M. Belohradsky, F. M. Raymo, J. F. Stoddart, P. J. Kuekes, R. S. Williams and J. R. Heath, "Electronically Configurable Molecular-Based Logic Gates", Science, vol. 285, pp. 391--394, July 1999.
• 10: Y. Luo, C. P. Collier, J. O. Jeppesen, K. A. Nielsen, E. DeIonno, G. Ho, J. Perkins, H. Tseng, T. Yamamoto, J. F. Stoddart and J. R. Heath, "Two-Dimensional Molecular Electronics Circuits", ChemPhysChem, vol. 3, pp. 519--525, 2002.
• 11: D. B. Strukov and K. K. Likharev, "CMOL FPGA: A Reconfigurable Architecture for Hybrid Digital Circuits with Two-terminal Nanodevices", Nanotechnology, vol. 16, pp. 888--900, Apr 2005.
• 12: Seth Copen Goldstein , Mihai Budiu, NanoFabrics: spatial computing using molecular electronics, Proceedings of the 28th annual international symposium on Computer architecture, p.178-191, June 30-July 04, 2001, Göteborg, Sweden
• 13: M. R. Stan, P. D. Franzon, S. C. Goldstein, J. C. Lach and M. M. Ziegler, "Molecular Electronics: From Devices and Interconnect to Circuits and Architecture", Proceedings of the IEEE, vol. 91, n. 11, pp. 1940--1957, November 2003.
• 14: G. Snider, P. J. Kuekes and R. S. Williams, "CMOS-like Logic in Defective, Nanoscale Crossbars", Nanotechnology, vol. 15, pp. 881--891, Aug 2004.
• 15: Collaborative Benchmarking Laboratory, 1993 LGSynth Bench-marks, North Carolina State University, Department of Computer Science, 1993.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.0 General

General Terms:
Algorithms, Design

Keywords:
PLA, crossbar, logic synthesis, nanoelectronic