CMOS Technology

CMOS Technology

September 18, 2013

[CMOS TECHNOLOGY] Abstract

Using Nano-electronic technologies are rapidly spread in terms of its

small size compared with CMOS. However, defect densities in such process

are higher than other technologies. A variety of electron devices that may be

scaled down to few nanometers have now been demonstrated, including field-

effect transistors, quantum interference devices, such as resonant tunneling

diodes, single-electron devices, and phase-change devices. Some of these

devices have been implemented using molecules, whose synthesis and self-

assembly is the preferred method of the bottom-up fabrication. In this paper, a

greedy mapping algorithm is presented for the purpose of defect the tolerance

in Nano-electronic systems. As expected results of such implementation, both

time complexity and the amount of free defect subsets should be enhanced

compared with old results.

2Page

September 18, 2013

[CMOS TECHNOLOGY]

Table of Contents

3Page

Content

Page

INTRODUCTION

4

PREVIOUS STUDIES

5

RESEARCH STATMENT

7

METHODOLOGY

8

RESULTS AND DISCUSSIONS

9

REFERENCES

10

September 18, 2013

[CMOS TECHNOLOGY] 1. INTRODUCTION

For the past forty years, electronic computers have grown more powerful as their basic sub-unit, the transistor, has shrunk. However, the laws of quantum mechanics, plus the limitations of materials and fabrication techniques soon are likely to inhibit further reduction in the minimum size of today's bulk-effect semiconductor transistors. Researchers have projected that as the overall size of the bulk-effect, semiconductor transistor is aggressively miniaturized to approximately 0.1 micron (i.e., 100 nanometers) and beyond, the devices may no longer function as well. The limitation of CMOS technology in electronic and computational circuits derives researchers is to focus on finding alternative technologies [1]. Nano-scale electronic devices promise to enhance the CMOS challenges and proposed many features in Nano-electronic systems. Un like CMOS devices, Nano-wires consume less power, occupy small area because of its size and density factors and implement computations in high speed[2][3] Unfortunately, defects are new challenges arise when integrate Nanowires

into

computing

and

electronic

systems.

Defects

are

either

nonprogrammable cross point defects or disconnected-wire defects [4]. While manufacturing process of Nano-crossbars, defects were found in both switches and wires. Many factors can be reasons of defects and broken switches and wires [5]. These broken wires defects are catastrophic and will prevent switches to be reconfigurable and unusable.

4Page

[CMOS TECHNOLOGY]

September 18, 2013

2. PREVIOUS STUDIES The need for defects tolerance techniques becomes crucially important specially when mapping any function to a defect crossbar. Researchers focus their efforts on finding different techniques and algorithms to handle defects problems. A defect-aware logic mapping frame work via Boolean satisfaction was proposed to solve logic mapping problems with higher defect rates [6]. It considers programmable logic arrays (PLA) defects. This method formulates. PLA logic mapping into Boolean CNF formulas, and the PLA defects covering and closing constraints. Most research papers analyze different factors which affect on logic mapping. A mathematical model in [7] tries to concentrate on yield improvement by analyze different factors in any logic mapping problems. It finds a relation between yields, rate of defects and run time. Another analysis for the relation between crossbar sizes, defect rare, function size and run time is mentioned in different researches [8]. They found that the run time is an important factor in Nano-scale logic mapping and defect tolerant techniques. It increases with the increase of function size and defect rates. While, on the other had it is decreasing with the increase of crossbar size. In addition, they also found that runtime can be improved by using large-sized crossbars which will reduce the correlations when mapping a function to a defect crossbar. Finding a valid function mapping in a defect crossbar was analyzed and studied in different papers. If there is a function and a defect map which shows defects location, an approach was described, which tries to find a correct function mapping using matrix representation [9]. In addition, a heuristic for logic mapping inspired by matrix canonization is proposed

5Page

[CMOS TECHNOLOGY]

September 18, 2013

another research [10]. Both function and crossbar are represented as matrices. The idea of this technique is reordering rows and columns of two same size matrices to make them look alike so they can be compared. Many researchers work on creating different greedy algorithms for defect-aware or defect-unaware mapping steps. The idea of greedy algorithm is perform a single procedure many times until it can't be done more. Then, the produced results will be checked whether it is the best one or not. So, greedy algorithm may not completely solve the problem or may not give a best solution. An approach is derived in [11] where defect-free subset of crossbars are extracted and then connected to achieve an array-based defect-free architecture which will be used in the design flow. Two mapping algorithms, recursive and greedy, are used to connect between defect-unaware steps and the final step of defect-aware mapping. They suppose that the defect-aware is not important in high level steps, it is important in the final step. A greedy algorithm tries to maximize the defect-free subsets and construct the compact defect map was discussed in [11]. The key idea is identifying the maximum defect-free subsets within the partially-defective chip. This will help to reduce the size of defect map.

Other different

techniques were discussed to supersede the most suitable algorithm to be used [12][13]. It follows the same idea but in different implementation, in which such new technique enhances cost and yield. Another technique presented a low time complexity algorithm by mixing the ideas of the previous two algorithms [14].

6Page

[CMOS TECHNOLOGY]

September 18, 2013

A new greedy algorithm based on the idea of the last three algorithms will be proposed throughout in this paper. The proposed algorithm should present a new t technique which tolerates defects in Nano-electronic switches. The heuristics mentioned in [15] will be used in order to find new mapping design. The idea of genetic algorithm and greedy algorithm will also be combined hoping to get better results.

3. RESEARCH STATEMENT The new algorithm tries to ignore the existence of defects and get the benefits of free defects switches. This requires following well-design steps in order to find maximum defect- free subsets. A graph will be considered as a defective crossbar. In any graph, finding the maximum biclique is same as finding a maximum independent set in the complement graph. This idea will be enforced but with different implementation in addition to use greedy and genetic algorithms. In order to find the maximum set in the complement graph, the proposed method suggests that whenever there is a picked node; choose an adjacent node with maximum degree. This scenario will be repeated and each time a node with zero degree will be added to the maximum independent set. The final nodes in the independent set will be considered as the final freedefect subset. Getting the benefits of greedy algorithm helps finding different solutions. At each stage, local optimal solution will be existed with the hope of finding a global optimal solution. In general, greedy algorithm does not give

7Page

[CMOS TECHNOLOGY]

September 18, 2013

an optimal solution, but it may give locally optimal solutions that approximate a global optimal solution in a reasonable time. The concepts of Genetic algorithm will be also used in order of giving better results. The genetic algorithm used to find approximate solutions through the principles of evolutionary biology to computer science. While using a genetic algorithm, a solution for the problem should be presented in beginning as a chromosome. Then, a population of solutions will be created. Genetic operators such as mutation and crossover will be applied on the population to evolve the solutions in order to find the best one.

4. RESEARCH METHODOLOGY In the beginning, the greedy algorithm which constructs the idea of finding the maximum independent set in a graph will be generated. It follows a new technique in implementing that idea. This part will be programmed using C++ language. Also, the old three algorithms which handled the same idea will be programmed in order of comparisons. Each of them is tested to get the value of free defect subset (k). Comparisons will be take place to see what kind of enhancements are foundafter deriving the new algorithm. The value of K and time complexity is the important factors to be analyzed. It supposes that high value of K and low time complexity is the desired results. After that, a genetic algorithm will be programmed using C++ language to enhance the results of the old and new algorithms in order to get an optimal solution. There is a desire to generate benchmarks for analyzing the

8Page

[CMOS TECHNOLOGY]

September 18, 2013

algorithms and results. It should test the yield, cost, run time of each algorithm.

5. RESULTS AND DISCUSSIONS Actually, different ideas were be implemented based on the concept of greedy algorithm. They also were tested and different values of K were resulted. Some of them were close to the old results, others were not. To continue enhance these results, the genetic algorithm are used and still need to be tested. The expected result is having low time complexity for the new one. This will be the main contribution in this work.

9Page

September 18, 2013

[CMOS TECHNOLOGY] REFERENCES

[1] W. Roa, A. Orailoglu and R. Karri, "Topology Aware Mapping of Logic Functios onto Nanowire-based Crossbar Architectures," DAC 2006, 24-28, Published in: Design Automation Conference, 2006 43rd ACM/IEEE Conference location: San Francisco, California, USA. [2]M. M. Ziegler, "CMOS/Nano Co-Design for Crossbar-Based Molecular Electronic Systems," Nanotechnology, IEEE Transactions on (Volume:2 , Issue: 4), Date of Publication: Dec. 2003 ,, Page(s):217 – 230. [3] Y. Chen, G. Jung, D. Ohlberg, X. Li, D. R. Stewart, J. O.Jeppesen, K. A. Nielsen, J.

F.Stoddart,

R. S. Williams,

"Nanoscale molecular-switch crossbar

circuits," ,,, NanotechnologyVolume 14 Number 4, Yong Chen et al 2003 Nanotechnology14 462 doi:10.1088/0957-4484/14/4/311. [4] A. M. S. SHRESTHA, A. TAKAOKA, S. TAYU, S. UENO, "On Two Problems of Nano-PLA Design,"IEICE Transactions 94-D(1): 35-41, 2011. [5] B. Ghavami, A. Tajary, M. Raji, H. Pedram, "Defect and Variation Issues on Design Mapping of Reconfigurable Nanoscale Crossbars," Published in: VLSI (ISVLSI), 2010 IEEE Computer Society Annual Symposium on , Date of Conference: 5-7 July 2010 , Page(s):173 – 178, Conference Location :Lixouri, Kefalonia. [6] Y. Zheng, C. Huang, "Defect-aware Logic Mapping for Nanowire-based programmable Logic Arrays via Satisfiability," Conference: Design, Automation, and Test in Europe - DATE , pp. 1279-1283, 2009. [7] Y. Su, W.RAO, "Defect-tolerant logic Mapping on Nanoscale Crossbar Architectures and Yield Analysis, "Published in: VLSI (ISVLSI), 2010 IEEE 10Page

[CMOS TECHNOLOGY]

September 18, 2013

Computer Society Annual Symposium on Date of Conference: 5-7, 2010, Page(s):173 – 178, Conference Location: Lixouri, Kefalonia. [8] Y. Su, W. Roa, "Runtime analysis for Defect-tolerant Logic Mapping on Nanoscale Crossbar Architectures," Published in: Nanoscale Architectures, 2009. NANOARCH '09. IEEE/ACM International Symposium on Date of Conference: 3031 July 2009. Page(s):75 – 78. Conference Location: San Francisco, CA. [9] J. Yang, R. Datta, "Efficient Function Mapping in Nanoscale Crossbar Architecture," Published in: Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT), 2011 IEEE International Symposium on Date of Conference: 3-5 Oct. 2011, Conference Location: Vancouver, BC, pp. 190-196. [10]

S.Goren, H.Ugurdag, O.palaz, "Defect-Aware Nanocrossbar logic Mapping

through matrix Canonization Using Two-Dimensional Radix Sort," ACM Journal on Emerging Technologies in computing Systems, Vol.7,No.3,Article 12, Publication date: 2011. [11] M.B.Tahoori, "Application-Independent Defect Tolerance Of Reconfigurable Nanoarchitectures, "ACM journal on Emerging Technologies in Computing Systems,Vol.2, No.3, 2006, pages 197-218. [12] M.B.Tahoori, "A mapping algorithm for defect-tolerance of reconfigurable Nano architectures," In Proc.int.Conf.Computer-Aided Design, Pages. 668-672, 2005. [13] A.AL-Yamani, S. Ramsunder and D.K.Pradhan, "A Defect Tolerance Scheme for Nanotechnology Circuits," IEEE Transactions on Circuits and Systems 1: Regular papers, vol.54, No.11, Page, 2402-2409, 2007

11Page

[CMOS TECHNOLOGY]

September 18, 2013

[14] B.Yuan, B.Li," A Low Time Complexity Defect-Tolerance Algorithm for Nanoelectronic Crossbar," international Conference on information Science and Technology, 2011 [15] J. Magun, "Greedy Matching Algorithm, an experimental Study," Published in: Journal of Experimental Algorithmics (JEA), Volume 3, 1998, Article No. 6, ACM New York, NY, USA.

12Page