Computer-aided design algorithms and tools for nanotechnologies

The famous Moore's Law states that chip density doubles almost every 18 months. The Semiconductor Industries Association (SIA) roadmap predicts that complementary metal-oxide semiconductor (CMOS) chips will continue to fuel the need for high-performance systems for another 10--15 years. However, new devices and technologies must be introduced to continue the scaling of chips beyond that time-frame. With rapid advancements in electronic materials and devices, many new nanoscale devices have been created, such as resonant tunneling diode (RTD), quantum cellular automata (QCA), single electron transistor (SET), single electron box (SEB), and tunneling phase logic (TPL), which have novel structures and properties. Such devices offer the opportunity to further improve the compactness and speed of very large scale integrated (VLSI) systems. While it is easier to implement Boolean gates using CMOS, it is easier for many nanoscale devices to implement threshold and majority gates. As progress is made in the material and physical understanding of nanoscale devices, research must be done at the logic level to fully harness the potential offered by these devices. The main purpose of the work in this dissertation is to bridge the current wide gap between research on nanoscale devices and research on synthesis methodologies for generating optimized networks utilizing these devices. We present the first comprehensive threshold network synthesis methodology for multi-output multi-level threshold networks starting from Boolean descriptions. It does threshold logic synthesis through binate and unate splitting and by calling a linear program solver. We have implemented the methodology in a tool called TELS, on top of an existing logic synthesis tool, and validated it with a large number of benchmarks. We also present a methodology for efficient majority/minority network synthesis of arbitrary multi-output Boolean functions, which is based on the concept of admissible patterns of majority gates. We have implemented this methodology in a tool called MALS, on top of the same existing logic synthesis tool. We expanded our research from combinational circuits to sequential circuits by addressing the problem of state encoding of finite-state machines targeting threshold/majority logic based implementations. We propose a methodology for state encoding based on an evolutionary algorithm. Besides solving the logic synthesis and state encoding problems for threshold and majority circuits, we also evaluated several factorization methods, targeting threshold/majority logic circuits specifically. Nanotechnology-based circuits are usually more vulnerable to both permanent and transient faults. Therefore, we evaluated threshold/majority totally self-checking (TSC) circuits to impart concurrent error detection capability to such circuits. We establish the efficacy of all the above methods through experimental results on a large number of benchmarks.