Ceylan Muhammed

L Morgül

O Frontini

Lorena Tunali

V Anghel

Elena Ioana Ciriani

C A Vatajelu
email: ioana.vatajelu@univ-grenoble-alpes.fr

Mircea R Moritz
email: mircea@virginia.edu

Dan Stan

Mustafa Alexandrescu

Altun
email: altunmus@itu.edu.tr

M Ceylan Morgul

Luca Frontini
email: luca.frontini@unimi.it

Onur Tunali
email: onur.tunali@itu.edu.tr

Lorena Anghel
email: lorena.anghel@univ-grenoble-alpes.fr

Valentina Ciriani
email: valentina.ciriani@unimi.it

E Ioana Vatajelu

Andras Csaba
email: andras@ecs.umass.edu

M Ceylan Morgul
email: morgul@itu.edu.tr

Mustafa Altun

Csaba Andras Moritz

Mircea R Stan

Dan Alexandrescu
email: dan.alexandrescu@iroctech.com

Circuit Design Steps for Nano-Crossbar Arrays: Area-Delay-Power Optimization with Fault Tolerance

Keywords: Crossbar Arrays, Logic Synthesis, Defect Tolerance, Fault Tolerance, Performance Optimization, Memristor Arrays I

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

production. Because of the novel manufacturing techniques, end products have regular and dense forms with area and power efficient structures [START_REF] Chen | Nanoscale molecularswitch crossbar circuits[END_REF] [START_REF] Alexandrescu | Synthesis and performance optimization of a switching nano-crossbar computer[END_REF].

Main principle behind crossbar based computing is to utilize crosspoints to behave like switches, either as two-terminal or novel four-terminal [START_REF] Altun | Logic synthesis for switching lattices[END_REF]. This is illustrated in Figure 1. Depending on the used technology, a two-terminal switch behaves either as a diode [START_REF] Huang | Logic gates and computation from assembled nanowire building blocks[END_REF], a resistive/memristive switch [START_REF] Snider | Computing with hysteretic resistor crossbars[END_REF] [START_REF] Kim | A functional hybrid memristor crossbararray/CMOS system for data storage and neuromorphic applications[END_REF], or a field effect transistor (FET) [START_REF] Snider | Nanoelectronic architectures[END_REF]. Diode and resistive switches correspond to the crosspoint structure in Figure 1(a); here, the switch is controlled by the voltage difference between the terminals. Figure 1(b) shows a FET based switch; here, the red line represents the controlling input. This is a unique opportunity that allows us to integrate well developed conventional circuit design techniques into nano-crossbar arrays. Finally, a novel four-terminal switch is demonstrated in Figure 1(c). Four terminal architecture has either all of its terminals connected or disconnected. The desired state is actualized with a controlling input, which is not present in the Figure 1(c) and has a separate physical formation from the crossbar which is thoroughly explained for different technologies in [START_REF] Altun | Logic synthesis for switching lattices[END_REF] [START_REF] Safaltin | Realization of four-terminal switching lattices: Technology development and circuit modeling[END_REF]. Detailed TCAD simulations and technology development are presented in [START_REF] Safaltin | Realization of four-terminal switching lattices: Technology development and circuit modeling[END_REF]. In addition, a realization with standard CMOS process is demonstrated in [START_REF] Cevik | Cmos implementation of switching lattices[END_REF].

Contrary to the conventional technologies, circuit design steps of nano-crossbar arrays are not fully incorporated due to their emerging nature. Motivated by this, we expand and update our preliminary integrated synthesis methodology in [START_REF] Morgul | Integrated synthesis methodology for crossbar arrays[END_REF], and present it in length. Main steps of the methodology are logic synthesis, defect/fault tolerance and performance optimization. In Section II, overview of the methodology is stated with the background information. Details of the design steps are stated in the following sections III IV V. We present a case study to elaborate the methodology conclusively in section VI. For sake of clarity, the significant experimental results are shown in the related sections. Main contributions are as follows:

Text Text R1 A B f x 1 R3 f R2 R1 x 2 x 2 x 1 a) f x 1 x 2 x 2 c) x 1 b) x 1 x 2 x 2 x 1 f R d) x 1 x 2 x 1 x 2 f f Power Supply CMOS Controller x 1 x 2 x 1 x 2 f PFET part NFET part
• Expanded version of integrated synthesis methodology presented in [START_REF] Morgul | Integrated synthesis methodology for crossbar arrays[END_REF]. • Multi-output logic synthesis for four-terminal lattices and comparison with others. • A greedy optimization algorithm for two-level singleoutput memristor crossbar (logic synthesis). • Defect tolerance technique for four-terminal lattice.

• Performance (delay-power) analysis of diode, FET and four-terminal arrays.

II. OVERVIEW OF CIRCUIT DESIGN STEPS A. Background

Nano-crossbar arrays are first shown to be realizable conceptually in [START_REF] Snider | Computing with hysteretic resistor crossbars[END_REF], [START_REF] Strukov | CMOL FPGA: a reconfigurable architecture for hybrid digital circuits with two-terminal nanodevices[END_REF] and then physically in [START_REF] Yan | Programmable nanowire circuits for nanoprocessors[END_REF], [START_REF] Yao | Nanowire nanocomputer as a finite-state machine[END_REF] as an integrated circuit. After that, research mostly follows the order of technology demonstration such as logic synthesis with ideal (non-defective) arrays, logic synthesis with defective arrays, performance-aware design (performance analysis/optimization), and technology development. This study targets to integrate the current researches with completing missing parts.

1) Logic Synthesis: Main goal of logic synthesis process is to optimize the area size of the circuit through formalizing the circuit size specific to underlying technology. To illustrate different approaches, we show examples for the realization of f XOR2 = x 1 x 2 + x 1 x 2 in Figure 2. Logic synthesis models for diode and memristor based crossbars are quite similar to Programmable Logic Array (PLA) as can be seen in Figure 2(a) and 2(b). Memristor based crossbars have one major difference that establishing the output goes through several states/loops (for further information refer to [START_REF] Xie | Fast boolean logic mapped on memristor crossbar[END_REF]). We chose the approach in [START_REF] Xie | Fast boolean logic mapped on memristor crossbar[END_REF] for the memristive crossbars, because the proposed architecture design does not lose its functionality due to the sneak path issues [START_REF] Kim | A functional hybrid memristor crossbararray/CMOS system for data storage and neuromorphic applications[END_REF]. For FET based crossbars, each logic function product and dual function product is realized by a separate column, as seen in Figure 2(c). Each input is assigned to a row for controlling all the FETs on corresponding row. Finally, a four-terminal based crossbar; here every crosspoint performs switching on all four directions and connection between top and bottom yields 1 as output and 0 otherwise. Control lines of crosspoints are not shown in Figure 2(d), and detailed explanation of control lines can be found in [START_REF] Altun | Logic synthesis for switching lattices[END_REF] [START_REF] Safaltin | Realization of four-terminal switching lattices: Technology development and circuit modeling[END_REF].

2) Defect/Fault Tolerance: Anticipated fault rates are much higher for nano-crossbars, as expected, compared to those of conventional CMOS circuits [START_REF] Snider | CMOS-like logic in defective, nanoscale crossbars[END_REF]. Therefore, during logic mapping, consideration of faults is mandatory. This applies to the all technology types such as diode, FET based or novel four-terminal based arrays. In short, contrasting the conventional CMOS approach, certain switches cannot be used in mapping process, therefore mapping procedure becomes an assignment problem. Early attempts to overcome this issue consists of locating a fault-free region so no crossbar specific assignment is necessary as in [START_REF] Tahoori | A mapping algorithm for defect-tolerance of reconfigurable nano-architectures[END_REF]. However, it has quickly become apparent that fault free region is not satisfactory in terms of area size [START_REF] Tunali | A survey of fault-tolerance algorithms for reconfigurable nano-crossbar arrays[END_REF]. For this reason, researchers focus on challenges including defect and variance tolerances [START_REF] Tunali | Permanent and transient fault tolerance for reconfigurable nano-crossbar arrays[END_REF] [START_REF] Peker | A fast hill climbing algorithm for defect and variation tolerant logic mapping of nano-crossbar arrays[END_REF]. In this study, we apply a new fault tolerance technique for four-terminal crossbars (lattices).

3) Performance Optimization: With the process variability data (as an extended concept of defects) of crossbars, performance-aware design can be accomplished. Given that targeted technologies have different performance characteristics, to perform fair comparison, their dependencies on target function should be analyzed. Previously, we have analyzed and extracted delay and power characteristic with dependencies on given function for memristor crossbars [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF]. In this study, we present delay and power model for diode, FET, and fourterminal lattice. These models characterize the performance of crossbar technologies for given target function. Idea is to optimize a crossbar with given design specification. However, with the lack of experimental results, optimization and comparison studies are limited with modeled characteristics.

B. Overview of Integrated Methodology

As briefly stated, nano-fabrication produces switching nanocrossbar arrays with varying properties, structurally and/or component-wise. These random characteristics need to be considered carefully by the synthesis process. For example, a competent methodology must regard basic technology preference for switching elements, and defect or fault rate of the given nano-crossbar. Presented synthesis methodology in this study comprehensively covers the all specified factors and provides optimization algorithms for each step of the process. The diagram, given in Figure 3, summarizes the methodology with demonstrating every step including annotated research tasks. The first step (logic synthesis) covers the decision of switching technology and generate logic function description in crossbar form. The main goal is to determine which of the diode/memristor, FET, or four-terminal based components are to be used. This step is one of the most important procedures determining the area size of the nano-crossbar that is the chief optimization metric. Logic synthesis with diode/memristor, FET, and four-terminal switching technology is in Section III.

Text

The second step (fault tolerance) covers the permanent faults (defects forming in the course of fabrication) and the transient faults (which occur in-field). The main goal is to obtain a valid mapping of a given logic function in crossbar form, produced by logic synthesis step, and defect map. There are two distinct approaches titled as def ect -aware and def ect -unaware. The first approach employs faults existing in nano-crossbar during the mapping ofthe function, hence the name aware. The second approach avoids the defects by attempting to find a defect-free region on the nano-crossbar at the beginning, so that the mapping of the logic function is straightforward. Finally, transient fault analysis is performed with respect to fault rates/types and fed back to logic synthesis step. Detailed explanations are given in Section IV.

The third step (performance optimization ) covers final delay and power issues. The main goal is to analyze delay and power consumption of arrays by showing their dependencies on the properties of a given logic function as well as specifics of the used technology. Detailed explanations are given in Section V.

To demonstrate the whole process in work, a case study is provided to elucidate the proposed synthesis mechanism in Section VI.

III. LOGIC SYNTHESIS At the start, crossbar (or array used interchangeably) switching technology, i.e., diode, memristor, FET, or four-terminal, needs to be chosen based on the following criteria:

• Crossbar size (number of rows and columns)

• Number of outputs (single or multiple function realization) • Fabrication complexity • Power and delay specifications • Application requirements A decision can be made on the importance and priority of the listed items, depending on the preference. For example, if an application demands in-memory computing, then the memristor technology can be chosen for the realization of logic functions, since the memristor can also be used as a memory unit.

On the other hand, the realization of a logic function using a diode or a memristor based crossbar requires less number of crosspoints than those of the FET based crossbars. However, the FET based designs consume less power than the diode/memristor-based design. Moreover, the four-terminal based crossbar includes less number of crosspoints than other crossbar designs [START_REF] Morgul | Synthesis and optimization of switching nanoarrays[END_REF].

Initially, we examine the logic synthesis techniques developed for diode, memristor, and FET based crossbars in the literature and then we formulate their crossbar sizes required to implement given logic functions. We also present results for four-terminal switch based arrays to synthesize multi-output functions.

In the second part, we present a new two-level synthesis technique for memristor based crossbars and compare them with other techniques in the literature.

A. Area Comparisons for Different Crossbar Technologies

We present the Logic Synthesis step of the integrated methodology, considering only the number of crosspoints in the crossbar. The size of a crossbar array including diode, memristor, FET, and four-terminal is given as follows:

• Diode:

(# of products of all f i ) + n) × ((# of literals in f ) + n) • Memristor: ((# of products of all f i ) + n) × ((# of literals in f ) + 2n) [worst-case] • FET: (# of literals in f + n) × ((# of products of all f i ) + (# of products of all f D i )) • Four-terminal: (largest of # of products # in f D i s) × (()# of products of all f i ) + n -1) [worst-case]
where n is the number of logic functions (the number of outputs); f i denotes the i th logic function, and f D i stands for its dual with 1 ≤ i ≤ n. As mentioned in Section I, the logic synthesis on diode and memristive based crossbars is similar to the PLA like synthesis. Thus, the techniques, such as product sharing and phase changing used in the PLA design, are also applicable in these designs. Since, the array sizes can be further reduced using the product sharing, these array size formulations can be considered as an upper bound for the logic synthesis techniques.

Text

For the single and multiple output function realization, the synthesis methodology for FET crossbar does not allow us to produce multi-level logic synthesis, only two-level approach can be used [START_REF] Snider | CMOS-like logic in defective, nanoscale crossbars[END_REF]. However, multi-level logic synthesis approach is feasible for the diode and memristive crossbars [START_REF] Tunali | Logic synthesis and defect tolerance for memristive crossbar arrays[END_REF]. Therefore, the optimization of array size still demands further research for the diode and memristor based designs.

The logic synthesis using four-terminal crossbars, generally known as switching lattices, is a new method. As shown in [START_REF] Altun | Logic synthesis for switching lattices[END_REF], Altun presented a useful logic synthesis technique for the switching lattices. However, this method cannot find the optimal solution in terms of the lattice size. Therefore, new specific logic synthesis methodologies are needed to be presented. As shown in [START_REF] Gange | Synthesizing optimal switching lattices[END_REF] and [START_REF] Morgul | Synthesis and optimization of switching nanoarrays[END_REF], optimal synthesis methodologies are provided. Moreover, decomposition based approximate techniques are presented such as XOR based [START_REF] Morgül | Anahtarlamalı nano dizinler ile lojik devre tasarımı ve boyut optimizasyonu logic circuit design with switching nano arrays and area optimization[END_REF] [9], p-circuit [START_REF] Bernasconi | Logic synthesis for switching lattices by decomposition with p-circuits[END_REF], and dimension reducibility [START_REF] Bernasconi | Synthesis on switching lattices of dimension-reducible boolean functions[END_REF] decompositions. Furthermore, a very efficient (20x faster) technique for very large functions is recently developed to make logic synthesis of four-terminal nano-crossbar arrays more feasible [START_REF] Aksoy | A novel method for the realization of complex logic functions using switching lattices[END_REF].

However, all of these studies focus on the realization of a single logic function using switching lattices. On the other hand, in [START_REF] Aksoy | A satisfiability-based approximate algorithm for logic synthesis using switching lattices[END_REF] [1], three main steps are presented to realize the multiple functions using switching lattices. These steps are given as follows: 1) find the realization of each logic function using a switching lattice; 2) merge these lattices into a single lattice; 3) check if these lattices can be realized using a smaller number of rows and columns such that the final lattice includes a small number of four-terminal switches.

This article is the first to present the sizes of diode, memristor, FET, and four-terminal based crossbar on the multiple output functions. The results are given in Table I. Note that the results given in bold under the four-terminal column indicates that they are found using the approximate algorithm of [START_REF] Aksoy | A satisfiability-based approximate algorithm for logic synthesis using switching lattices[END_REF] [1] (JANUS), following the three steps described above. On the other hand, the other results are found using a divide and conquer method, based on the divide and synthesize (DS) method of [START_REF] Aksoy | A satisfiability-based approximate algorithm for logic synthesis using switching lattices[END_REF] [1], following the first two steps described above.

As can be observed from Table I, the four-terminal based crossbar arrays include significantly less number of crosspoints when compared to the diode, memristor, and FET based crossbar arrays.

For the logic synthesis of memristor based crossbars, there exists more area efficient techniques than in [START_REF] Xie | Fast boolean logic mapped on memristor crossbar[END_REF]; such as [START_REF] Ben-Hur | SIMPLER MAGIC: synthesis and mapping of inmemory logic executed in a single row to improve throughput[END_REF] (SIMPLER MAGIC ), [START_REF] Thangkhiew | An efficient memristor crossbar architecture for mapping boolean functions using binary decision diagrams (bdd)[END_REF], or [START_REF] Shirinzadeh | Logic synthesis for RRAM-based in-memory computing[END_REF] (which are essentially improved versions of the MAGIC [START_REF] Kvatinsky | MAGIC-memristor-aided logic[END_REF]). For example, misex1 can be realized in an array which has the size of 33, 88 and 52 with [START_REF] Ben-Hur | SIMPLER MAGIC: synthesis and mapping of inmemory logic executed in a single row to improve throughput[END_REF], [START_REF] Thangkhiew | An efficient memristor crossbar architecture for mapping boolean functions using binary decision diagrams (bdd)[END_REF] and [START_REF] Shirinzadeh | Logic synthesis for RRAM-based in-memory computing[END_REF], respectively. However they require much larger number of operation cycles: 83, 52 and 31 with [START_REF] Ben-Hur | SIMPLER MAGIC: synthesis and mapping of inmemory logic executed in a single row to improve throughput[END_REF], [START_REF] Thangkhiew | An efficient memristor crossbar architecture for mapping boolean functions using binary decision diagrams (bdd)[END_REF] and [START_REF] Shirinzadeh | Logic synthesis for RRAM-based in-memory computing[END_REF], respectively. Note that, required number of cycles is only 7 for [START_REF] Xie | Fast boolean logic mapped on memristor crossbar[END_REF]. This number can even be reduced to 5 with the proposed technique [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF]. On the other hand, as stated in [START_REF] Xie | A mapping methodology of boolean logic circuits on memristor crossbar[END_REF], the method in [START_REF] Xie | Fast boolean logic mapped on memristor crossbar[END_REF] can support the method MAGIC. Furthermore, since the method of MAGIC (and improved versions of it) uses all crosspoints in the array (density is 100%), its defect intolerance is much higher than [START_REF] Xie | Fast boolean logic mapped on memristor crossbar[END_REF]. Therefore, we used the approach in [START_REF] Xie | Fast boolean logic mapped on memristor crossbar[END_REF] and implemented the improved version to our integrated synthesis methodology.

B. Proposed Greedy Algorithm for two-level multi output synthesis for Memristive Arrays

In memristive crossbar arrays, function outputs and their negations are produced [START_REF] Xie | Fast boolean logic mapped on memristor crossbar[END_REF]. However production order changes the array size. We have called phase combination-0 and phase combination-1 realization, if realization is happened based on an output itself and its negation, respectively. For instance, for the realization of phase combination-1, first its negation is produced [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF] and at last original function outputs. Based on this property, array size of memristive crossbars can be optimized. The realization in [START_REF] Xie | Fast boolean logic mapped on memristor crossbar[END_REF] is phase combination-1 realization. initial Greedy Algorithm (GA-initial) [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF] and Proposed Greedy Algorithm (PGA)

In our previous study [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF], we have proposed a greedy algorithm, which only considers outputs individually, and doesn't consider outputs interrelation (i.e. no product sharing at the analysis). We can call this algorithm as "initial Greedy Algorithm (GA-initial)". In this algorithm, only product numbers of individual outputs are considered. On the other hand our new greedy algorithm considers product sharing with the change of phase, meaning it considers total number of products of whole (multi-output) function. We illustrate these two algorithms in Figure 4 side-by-side.

Proposed Greedy Algorithm (PGA): investigates outputs collectively by changing phase of outputs, one at a time, starting from phase combination-0 and phase combination-1. Compares them; if any of the changed phase combination has less # of total product; then keeps that phase and continues searching with changing other outputs' phase one at a time. Algorithm (PGA) is as follows:

1 For example, if we are given a function which has three outputs. First we check phases "000" and "111" (phase combination-0 and phase combination-1). Then calculate product numbers of phase in phase sets; set 0 : "001, 010, and 100" (changing zeros to one), and set 1 : "110, 101, and 011" (Changing ones to zero) (Note that, we change one at a time). Let's say we compared product numbers and found that phase "110" yields the minimum number of products. Then we continue from the phase "110", with changing ones to zero. Means, we check "100 and 010" and compare the results with result of phase "110". If there is one which yields less product number chose it, or chose the phase "110" for the final phase combination of the function. (Notice that, for a function, which has only three outputs, looking to sets of set 0 and set 1 is enough)

To evaluate the algorithms and compare the results, we use espresso and MATLAB TM on a 3.20 GHz Intel Core i7 CPU with 4GB memory. Results are shown in Table II. Algorithm performances differs from function to function. For six of the examples PGA results less area size than GA-initial. Overall, PGA surpasses GA-initial, yet for two (clip and sao2) of the functions GA-initial results less area size than PGA. For the rest they produce the same result. GA-initial's major advantages is that it has almost no time cost. It can be used for any case.

IV. DEFECT/FAULT TOLERANCE In this section, we investigate the effects of permanent and transient faults on the behavior of a logic function mapped on a given crossbar array. We categorize faults into 2 classes: permanent, generated by physical defects, and transient faults. As mentioned in Section I, actual nano-crossbar arrays being fabricated with emerging technologies, are affected mostly by defects, due to the poor technology yields. Indeed, immature process technologies used for nanowires, memristive, etc. elements generate high defect density crossbars. At the same time, these elements also show instabilities and variabilities (behaving like transient or intermittent faults) and they are also affected by transient phenomena occurring in the field. Permanent fault (defect) tolerance, also called defect avoidance, basically means finding defect-free regions or defect free crosspoints that can still be employed during logic mapping, and it is usually done by the logic function remapping (at the algorithm level) and/or by reconfiguration, at algorithm or hardware level. Permanent fault model can be seen in Figure 5 demonstrating only stuck-at-0 (open) and stuck-at-1 (close) faults as being the most representative permanent faults observed. This categorization is based on actual physical realization of nano-crossbar array as reported in [START_REF] Li | Efficient and self-adaptive in-situ learning in multilayer memristor neural networks[END_REF] and [START_REF] Borghetti | A hybrid nanomemristor/transistor logic circuit capable of self-programming[END_REF] which state that fault rates reach up to 10% and the most common faults are stuck-at-0 (open).

Transient and intermittent faults, on the other hand, manifest themselves due to particular combinations of topological, environmental factors or process mismatches and instabilities. They can be tolerated by proper architectural reconfiguration, but also by instability and variation-aware design. That is to say by using properly sized, or well estimated hardware redundancy in term of spare cells, critically sensitive cells can be circumvented or protected. Transient fault model can have multiple forms meaning they can be seen as parasitic, 0to-1 (1-to-0 ) transitions, parasitic positive (negative) pulses, neighbor cells pattern dependent transitions, etc. Transient fault domain is very closely related to a specific technology. Transient faults are more efficiently covered by fault tolerance strategies, as fault avoidance techniques will yield to a much higher area, but also due to the complexity of the technology dependence analysis.

For both type of faults, it is mandatory to perform crossbar sensitivity analysis as the mapping algorithm can be enhanced with fault avoidance properties, and also can be used to further drive the fault tolerance strategy.

A. Defect Tolerance for Diode, Memristor and FET

Defect tolerance is achieved by mapping a target logic function on a defective crossbar using a distinct input and output assignment. This problem is considered as NP-complete [START_REF] Shrestha | Orthogonal ray graphs and nano-PLA design[END_REF]. For the worst-case, N ! × M ! permutations are required to find a successful mapping for N × M crossbar. Algorithms in the literature use defect-unaware or defect-aware approach.

Defect-unaware algorithms aim to find the largest possible k × k defect-free sub-crossbar from a defective N × N crossbar where k ≤ N . The algorithms are inefficient for high fault rates -obtained k values are much smaller than N . In this regard, defect-aware algorithms perform much more satisfactorily [START_REF] Tunali | Permanent and transient fault tolerance for reconfigurable nano-crossbar arrays[END_REF]. Detailed analysis of both approaches can be found in [START_REF] Tunali | A survey of fault-tolerance algorithms for reconfigurable nano-crossbar arrays[END_REF].

1 1 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 0 1 1 0 1 0 0 1 0 1 1 1 1 2 0 2 2 0 1 1 0 0 0 2 2 2 0 b) c) 𝒙 𝟒 𝒙
Defect-aware algorithms consider the defect characteristics (stuck-at-0 or stuck-at-1), then decide which switch to employ during the mapping. In our previous work [START_REF] Tunali | Permanent and transient fault tolerance for reconfigurable nano-crossbar arrays[END_REF], we have proposed an efficient heuristic algorithms which aims to match defective crossbar and the given logic function. For this, it denotes crossbars as matrices. Therefore, it can perform sorting, matching and backtracking steps efficiently. It makes repetition for a limit of permutation. This controls heuristic feature of the algorithm.

Defect tolerance for nano-crossbars is a well established field with numerous research papers and for this reason we focus on four-terminal architectures which is, to our knowledge, exclusive to this study.

B. Defect Tolerance for Four Terminals Devices

Four-terminal defect tolerance demands a different approach than the architectures we have covered so far. For this reason, we present a novel method, which is firstly introduced in this paper. The proposed method utilizes a prior sensitivity analysis of crossbar (latttice) to specify critical switches, and strengthens them with proposed mitigation factors. The same naming conventions are applicable, regarding defects which are categorized as stuck-at-0 (SA0) and stuck-at-1 (SA1), called Stuck at Fault Model (SAF). Furthermore, we describe a new model that can be considered for crossbars (lattices), that consists in changing a switching literal in a cell c i,j of the lattice with a literal that is in a adjacent cell (i.e., c i-1,j , c i+1,j ,c i,j-1 , or c i,j+1 ). We denote this fault model as Adjacent Cellular Fault Model (ACF). In addition, we follow the same terminology adopted in [START_REF] Altun | Logic synthesis for switching lattices[END_REF] and [START_REF] Gange | Synthesizing optimal switching lattices[END_REF] by addressing crossbar as lattice and switch as cell to be consistent and emphasize the distinction of four-terminal approach. Finally, it should be noted that as opposed the previous sections, we provide a more detailed explanation due to original technical contribution presented in this section.

1) Defect Injection Methodology:

The two fault injections SAF and ACF are repeated for each cell of the lattice. Once a "defective" lattice is obtained, both algorithms generate all the possible 2 n inputs (where n is the number of variables). For each input, the simulation algorithms compare the given output with the correct one. The two fault injection algorithms (one for SAF and one for ACF) differ in the calculation of number of defective outputs in the two fault models, as explained in the following subsections.

Text

Fault Model 1: Stuck-at Faults (SAFs) The sensitivity of the decomposition algorithm on a given lattice is analyzed to face SA0 and SA1, as a model widely adopted today for memristive crossbars. As there is no consensus currently on the fault distribution, we have chosen a uniform distribution for each type of SA0 and SA1 [START_REF] Chen | RRAM defect modeling and failure analysis based on march test and a novel squeeze-search scheme[END_REF]. The fault rates considered may be up to 10% of the crossbar, all faults being independent, as reported in [START_REF] Chen | RRAM defect modeling and failure analysis based on march test and a novel squeeze-search scheme[END_REF]. The fault injection in the above lattices is performed substituting a single cell with an always stuck-at 1 (SA1) or stack-at 0 (SA0) cell.

Let E 0 ij (resp., E 1 ij ), with 1 ≤ i ≤ r, 1 ≤ j ≤ s, be the number of defective outputs with a SA0 (resp., SA1) in the cell (i, j) of the given lattice. Note that 0

≤ {E 0 ij , E 1 ij } ≤ 2 n . Moreover, when E 0 ij (resp., E 1 ij
) is equal to 0 we have that, for any possible input, the lattice output is never changed by the SAF in the cell c i,j . In this case, we call the cell c i,j robust w.r.t. SA0 (resp., SA1). Let R 0 (resp., R 1 ) be the total number of robust cells w.r.t. SA0 (resp., SA1) in the lattice. Finally, let

E 0 = i=r i=1 j=s j=1 E 0 ij (resp., E 1 = i=r i=1
j=s j=1 E 1 ij ) be the total number of defective outputs with SA0 (resp. SA1) in the simulation. For an example of function f = x 4 x 5 x 7 +x 4 x 6 x 7 +x 4 x 5 x 6 x 7 +x 4 x 6 x 7 +x 4 x 6 x 7 realized in Figure 6(a) (with the method in [START_REF] Altun | Logic synthesis for switching lattices[END_REF]), in the Figure 6(b) (resp., 6(c) shows the map containing E 0 ij (resp., E 1 ij ) in each cell. Consider SA0 case (matrix in Figure 6(b)). Each cell of the matrix contains the number of faulty outputs due to a SA0 in the corresponding cell of the lattice 6(a). When a cell of the matrices from Figures 6(b) (SA0) and 6(c) (SA1), contains the value 0, the cell of the corresponding lattice is robust. In this example, the overall number of robust cells for the SA0 (resp., SA1) is R 0 = 1 (resp., R 1 = 10).

Fault Model 2: Adjacent Cellular Faults (ACFs) In the classical CFM [START_REF] Friedman | Easily testable iterative systems[END_REF] used for CMOS circuits it is assumed that a fault modifies the behavior of exactly one node v in a given circuit C and that the modified behavior is still combinational. In the case of a switching lattice L, the fault model can be described as follows: a cellular fault in L is a tuple (c i,j , l c , l f ), where c i,j is the cell of the lattice L (i.e., fault location), l c is the correct controlling literal in c i,j , and l f ( = l c ) is the faulty controlling literal. We denote adjacent cellular fault a cellular fault where the faulty literal l f is the literal contained in an adjacent cell. More precisely:

Definition 1: Let l h,k be the literal in the cell c h,k of a lattice L, with 1 ≤ h ≤ r, 1 ≤ k ≤ s. We have that:

1) A Left Adjacent Cellular Fault (L-ACF) is the cellular fault i,j , l i,j l i,j-1 ) , 2) A Right Adjacent Cellular Fault (R-ACF) is the cellular fault (c i,j , l i,j , l i,j+1 ), 3) A Bottom Adjacent Cellular Fault (B-ACF) is the cellular fault (c i,j , l i,j , l i+1,j ), 4) A Top Adjacent Cellular Fault (T-ACF) is the cellular fault (c i,j , l i,j , l i-1,j ).

For example, consider the lattice depicted in Figure 6(a) and the cell c 2,1 containing the literal x 5 in the second row from top and first column from left. In this cell we can have three possible adjacent Cellular Faults: 1) R-ACF: (c 2,1 , x 5 , x 7 ) that makes x 7 the faulty literal of the cell c 2,1 ; 2) B-ACF: (c 2,1 , x 5 , x 7 ) that makes x 7 the faulty literal of the cell c 2,1 ; 3) T-ACF: (c 2,1 , x 5 , x 4 ) that makes x 4 the faulty literal of the cell c 2,1 . Notice that the cell c 2,1 cannot be affected by a Left Adjacent Cellular Fault.

Let

E L ij (resp., E R ij , E B ij
, and E T ij ), with 1 ≤ i ≤ r, 1 ≤ j ≤ s, be the number of defective outputs with a L-ACF (resp., R-ACF, B-ACF, and T-ACF) in the cell c i,j of the given lattice. Let R a (with a ∈ {L, R, B, T }) be the total number of robust cells w.r.t. a-ACF in the lattice. Finally, let E a = i=r i=1 j=s j=1 E a ij be the total number of defective outputs with a-ACF in the simulation.

2) Metrics used for Sensitivity Analysis: Let us consider a lattice with n input Boolean variables, the main aim of our sensitivity analysis is to understand how many inputs combinations (out of all the possible ones, which are 2 n in number) give an incorrect output value. For this purpose, we inject one error in a cell of the lattice (one error at time), for all cells. This way, we can compute the total number of defective outputs (E i , with i ∈ {0, 1, L, R, B, T }) and the total number of robust cells (R i , with i ∈ {0, 1, L, R, B, T }) as described in the previous section. In order to evaluate the sensitivity of a lattice to SAF and ACF, we propose two metrics. The first one measures the average number of defective outputs face to defect-sensitive cells. The second metric measures the average number of defective outputs in the entire lattice, considering robust and defective, non-robust cells. Note that the total number of cells is the area of the lattice (i.e., r•s ), the number of non-robust cells for SA0 (resp., SA1) is r • s -R 0 (resp., r•s-R 1 ), and 2 n is the total number of possible distinct inputs. Moreover, the number of non-robust cells for a-ACF (with a ∈ {L, R, B, T }) is r • s -R a .

The sensitivity to defective cells is the total number of inputs that give an uncorrected output (E i , with i ∈ {0, 1, L, R, B, T }) divided by the total number of inputs (2 n ), for each non-robust cell. The metric can be expressed as:

S i C = E i /(2 n •(r•s-R i )) for each fault i ∈ {0, 1, L, R, B, T }.
The sensitivity of lattice is the total number of inputs that give an uncorrected output divided by the total number of inputs for each cell: In particular,

S i L = E i /(2 n • r • s), with i ∈ {0, 1, L, R, B, T }.
In summary, the first metric measures the impact of one cell on the probability of failure of a logic function. The second one allows us to evaluate the integrity of the entire lattice and understand if it is possible to map strong, critical functions (for a specific operation) in such lattice, which have high sensitivity to faults or overall high robustness. For instance, if we have a lattice where half of the cells are non robust we can understand that we may not want to use it for critical functions (e.g., control, decision making, etc).

For example, consider the lattice depicted in Figure 6(a) and the map in Figure 6(c) showing the values of E 1 ij in each cell in the SA1 model. Note that the number of rows and columns is r = s = 5 and the number of different variables in the lattice is n = 4 (i.e., x 4 , x 5 , x 6 , and x 7 ). Moreover, the total number of incorrect outputs is the sum of all the errors, i.e., E 1 = 21 and the number of robust cells (i.e., cells with no Text errors) is R 1 = 10. Therefore, the sensitivity of defective cells is S

1 C = E 1 /(2 n • (r • s -R 1 )) = 21/(2 4 • (5 • 5 - 10
)) = 21/240. This means that out of all possible errors, which are 240 in number, we have 21 errors. The second metrics does not take into account the robust cells, therefore we have that

S 1 L = E 1 /(2 n • (r • s)) = 21/(2 4 • (5 • 5)) = 21/400.
3) Benchmarks and Simulations: The defect simulations have been run on a machine with two Intel Xeon E5-2683 for a total of 64 CPUs and 756 GByte of main memory, running Linux CentOS 7. The benchmarks functions are expressed in PLA form and are taken from a subset of LGSynth93 [START_REF] Yang | Logic synthesis and optimization benchmarks user guide: version 3.0[END_REF]. Each output of a function is implemented as a separate Boolean function for total of about 1000 functions.

The software used for simulations is written in C++. We used ESPRESSO [START_REF] Mcgeer | ESPRESSO-SIGNATURE: A new exact minimizer for logic functions[END_REF] to implement the method described in [START_REF] Altun | Logic synthesis for switching lattices[END_REF], and a collection of Python scripts for computing minimum-area lattices by transformation to a series of SAT problems, to simulate the results reported in [START_REF] Gange | Synthesizing optimal switching lattices[END_REF].

In Table III, we report a sample of benchmark functions and their sensitivity values, according to the metrics presented before. In particular, Table III refers to lattice synthesized as described in [START_REF] Altun | Logic synthesis for switching lattices[END_REF] and [START_REF] Gange | Synthesizing optimal switching lattices[END_REF]. The benchmarks marked with a in Table III, were stopped after ten minutes of SAT execution and, for this reason, they are missing from the benchmarks synthesized using quantified Boolean logic.

More precisely, in both methods, the first column reports the name and the number of the considered outputs of each function. The following columns report dimension (r × s) required for the synthesis of a given function according to each decomposition method, and the number of input variables n. Columns from 4 to 11 refers to Stuck At fault model, columns from 12 to 27 to Adjacent Cellular Fault model showing the total number of errors E, the Sensitivity of defective cells S C , the Sensitivity of lattice S L and the percentage of robust cells %R/r ×s. Table III shows that the synthesis method proposed by [START_REF] Altun | Logic synthesis for switching lattices[END_REF] produces lattices with a lower number of errors and a higher number of robust cells. However, the area of these lattices is greater than the area of the corresponding lattices synthesized using [START_REF] Gange | Synthesizing optimal switching lattices[END_REF]. For example, consider the benchmark circuit alu3(2): the area of the lattice minimized with [START_REF] Altun | Logic synthesis for switching lattices[END_REF] (resp., [START_REF] Gange | Synthesizing optimal switching lattices[END_REF]) method is 10×11 (resp., 6×4), while the percentage of robust cells in the lattice synthesized using [START_REF] Altun | Logic synthesis for switching lattices[END_REF] (resp., [START_REF] Gange | Synthesizing optimal switching lattices[END_REF]) method is 98% (resp., 33%) in the SA0 case. For the other fault models the percentage's comparison is similar.

Table IV describes the overall results for the considered benchmarks. More precisely in the columns from one to three is reported the synthesis method, the average lattice area, and the average number of input. Columns from four to twentyone show the average values of S C , S L , and %R/r × s for each fault injection methodology. The columns from twentytwo to twenty-four contain the average value of S C , S L , and %R/r × s obtained considering all the fault models.

Table IV shows that the percentage of cells that are considered robust according to our metrics is higher in the first approach [START_REF] Altun | Logic synthesis for switching lattices[END_REF]. For example if we consider the benchmark prom2(0) with SA1 faults, using the approach [START_REF] Altun | Logic synthesis for switching lattices[END_REF] we have 100% of resilient cells, instead using the approach [START_REF] Gange | Synthesizing optimal switching lattices[END_REF] there are no resilient cells. This is due to the more constrained structure of the lattices produced by the first synthesis method. Indeed, the method proposed in [START_REF] Altun | Logic synthesis for switching lattices[END_REF] computes a lattice for f and its dual, which it is in general less compact than the lattice given by [START_REF] Gange | Synthesizing optimal switching lattices[END_REF]. However, we can note that the sensitivity of the lattices is quite low for both methods. In fact, the experiments show that, in general, non-robust cells compute a failed output for a very limited number of inputs. In particular, lattices present lower sensitivity to Adjacent Cellular faults, with respect to the Stuck-At faults. This is due to the fact that when two adjacent cells contain the same value, this situation will not show an impact on the output. In both synthesis approaches, we observe that the lattice is more sensitive to SA0 faults, while in the case of SA1 faults, it requires higher percentage of redundant cells.

It is worth noting that we test lattices with up to 12 variables, this makes interesting the use of this technology to implement multipliers, or other complex arithmetic functions.

4) Mitigation by Defect Avoidance:

From the above results, it can be seen that the two analyzed mapping algorithms show different sensitivities of the output of a given function. As a matter of fact, the more restrictive an algorithm in terms of area it is (closer to the optimal solution), the higher the defect sensitivity of the output to a cell defect. It is thus mandatory to include the mapping algorithm defect-avoidance heuristics, but hardware-level defect tolerant scheme may also be necessary, especially in the case of very high defect densities and transient faults rates. Hardware redundancy schemes can be used at the lattice column level, or at the block level [START_REF] Nicolaidis | Memory defect tolerance architectures for nanotechnologies[END_REF], as the basic computation unit of a memristor array is not the memristive cell, as in classical CMOS based memories, but the entire column. Therefore, several redundant columns or blocks can be added to the initial design to replace the memristive RAM affected columns but also to overcome the situation when potential SAFs affect the redundant parts as well.

Besides Redundancy Repair Techniques, other defect tolerance techniques can be used. For example, Error Correcting Codes (ECC) especially when transient faults are the main issue, but also fault masking techniques to typically repair permanent faults, or combinations of both. Various advanced error correction techniques have been proposed for emerging technologies structures, which provide improvements over the conventional ECC or Redundancy Repair techniques [START_REF] Kang | A low-cost built-in error correction circuit design for STT-MRAM reliability improvement[END_REF]. But it is worth noting that all of them are generating quite significant area overhead due to the encoding/decoding circuitry, or to the extra spare rows and columns, or a more complex addressing and accessing schemes, but they also impact the write/read margins of the lattice, and increase the access latency, and power consumption. Therefore, a combination of efficient defect avoidance mapping algorithm combined with Redundancy based Repair techniques and/or ECC codes will lead to fully functional lattices even for high defect and transient fault rates. Mapping of logic functions on crossbar arrays are thus divided into two main phases: mapping phase to write the parameters of functions in the memristive array and a read operation to check the results from the crossbar. [START_REF] Altun | Logic synthesis for switching lattices[END_REF] AND [START_REF] Gange | Synthesizing optimal switching lattices[END_REF] The objective here is to identify at the writing time, if common literals and other multiple-choice literals of the function can be mapped on highly critical cells, or not, so that the output is not compromised.

Text

TABLE III A SAMPLE OF BENCHMARK FUNCTIONS SYNTHESIZED WITH

r × s n E 0 S 0 C S 0 L % R 0 r×s E 1 S 1 C S 1 L % R 1 r×s E R S R C S R L % R R r×s E L S L C S L L % R L r×s E T S T C S T L % R T r×s E B S B C S B L % R B
S 0 L % R 0 r×s S 1 C S 1 L % R 1 r×s S R C S R L % R R r×s S L C S L L % R L r×s S T C S T L % R T r×s S B C S B L % R B r×s Average values SC SL % R
Mitigation for Stuck at Faults: In order to mitigate the sensitivity of a lattice to SAF, we propose the following possible strategy applied to the synthesis method proposed in [START_REF] Altun | Logic synthesis for switching lattices[END_REF] which has been proven a less sensitive to SAF impact on the output functions: (1) For a given mapped function, if a potential SA0, SA1 faults affects a robust cell identified by the defect injection campaign, the lattice still computes the correct output, thus we do not need any more mitigation with defect tolerant design. (2) However, if an injected defect occurs in a multiple-choice cell, if a different literal can be chosen to increase the robustness, we change the literal with the new one.

(3) Otherwise, if the injected SA0 fault is proven as being critical for the output value, the column that contains that defective cell has to be replaced by a spare one. In case of an SA1, the row that contains the defective cell has to be replaced by a spare row. Note that in this case, the output still provides a correct function f from top to bottom, but the function from left to right could be changed and become a function which will not be dual of f anymore.

As an example, consider the lattice synthesized in Figure 7(a) with f = x 4 x 5 x 7 + x 4 x 6 x 7 + x 4 x 5 x 6 x 7 + x 4 x 6 x 7 + x 4 x 6 x 7 by using synthesis method presented in [START_REF] Altun | Logic synthesis for switching lattices[END_REF]. The example shows one case of mitigation of 3 independent SAD affecting the lattice implementing the function, yielding an approximate 10% defects. In Figure 7, critical SA1 cells are marked in blue and SA0 cells a remarked in red.

To avoid output errors due to these SAF we have used the following strategy: 1) Identify robust cells for a given function mapping. Example: the defect in the first row, fifth column is nonsignificant on the value of the output (robust cell). The sensitivity map obtained through defect injection campaign, shows that this cell (x 4 ) is not sensitive to SA1

for the mapped function. 2) Identify the swapping of literals during synthesis process on a column of a high sensitive cell. Example: the defect in fifth row, fourth column (i.e., blue cell) is sensitive to SA1. We can note that the yellow cell (the fourth row, fourth column cell) contains the literals x 7 . By Figure 7(a) we know that we can choose x 4 instead of x 7 .

With this new literal (x 4 ), we have an equivalent lattice where if the blue cell is affected by a SA1 at fabrication time, this will not affect the output of the function. 3) Identify the critical cell for the output value and add a spare column per critical cell. Example: the defect in the third row and second column will influence the value of the output and no swapping operands is possible. Thus the only solution remains to add a spare column (in green) identical to the column containing the SA0 defect, and perform the spare and replace strategy. By using spare columns, the mapping algorithm can eliminate columns of the lattice, with critical cells, susceptible to affect the output value of the function, in case SA defect appear at fabrication or in the field.

Mitigation for Adjacent Cellular Faults: In the case of adjacent cellular fault model, we can note that adjacent cells containing the same controlling literal are robust to faults. For example, consider the lattice depicted in Figure 6(a), and the two variables x 4 at the end of the first row. The lattice is obviously robust to a L-ACF in the last x 4 (and to a R-ACF in the forth cell, containing x 4 ). For this reason, in sensitivity analysis to ACF model, it is of huge importance to maximize the number of adjacent cells with the same controlling literal.

Recall that the properties of the lattice synthesized with [START_REF] Altun | Logic synthesis for switching lattices[END_REF] guarantee that row and column permutations for a given lattice do not change the Boolean function computed by the switching lattice. Because of the good level of flexibility, we consider the lattice obtained by this synthesis method as a starting point for increasing the number of robust cells without changing the function represented. Thus, given a lattice synthesized with [START_REF] Altun | Logic synthesis for switching lattices[END_REF], a possible strategy is to perform column and row permutations in order to maximize the number of adjacent cells containing the same literal. For example, consider the R-ACF, the number of cells with the same literal in the right-adjacent cell in the lattice in Figure 6(a) is 1. Suppose to simply swap the second and the third column, the number of cells with the same literal in the right-adjacent cell becomes 4 (i.e., the number of robust cells is incremented by 3). Note also that while the number of robust cells to R-ACF and L-ACF can be increased by column permutations, the number of robust cells to T-ACF and B-ACF can be increased by row permutations. Finally, observe that this method increases the number of robust cells without increasing the dimension of the lattice.

C. Transient Fault Tolerance

Before moving on to transient faults, one distinction should be emphasized such that contrary to defects, transient faults are not known in advance and occur in-field. For this reason, transient fault tolerance works in predictive manner. In addition, since nano-crossbars are in the early stage of development, there is data deficiency regarding the occurrence rates and characteristics of transient faults.

First, we follow the same naming conventions of defects (permanent faults) for transient faults in modeling. Accordingly, the effects of transient faults can be categorized with 4 different scenarios:

1) Stuck-at-zero on unused crosspoint produces no effect 2) Stuck-at-zero on used crosspoint removes corresponding input 3) Stuck-at-one on unused crosspoint adds corresponding input 4) Stuck-at-one on used crosspoint produces no effect. To mitigate faults, first approach is to introduce extra circuit elements to compensate erroneous results. Inserting redundant components can be constructed with adding extra rows and/or columns as shown in [START_REF] Rao | Logic level fault tolerance approaches targeting nanoelectronics PLAs[END_REF] [START_REF] Baranov | Designing fault tolerant FSM by nano-PLA[END_REF]. A detailed study of redundancy techniques can be found in [START_REF] Tunali | A survey of fault-tolerance algorithms for reconfigurable nano-crossbar arrays[END_REF].

f 2 = x 1 x 2 x 1 + x 2 x 3 + x 1 x 3 + x 1 x 2 x 3 f 1 = x 1 x 2 + x 2 x 3 + x 1 x 3 x 2 + x 1 x 2 x 3
The second approach requires the knowledge of prevalent fault types beforehand so that it is possible to modify the target logic function accordingly. If stuck-at-zero faults are more common, then using the logic function form with least number of inputs implies many unused crosspoints and high tolerance (scenario 1). If stuck-at-one faults are more common, then using the logic function form with the most number of inputs (e.g. using the minterm form) implies many used crosspoints and high tolerance (scenario 4). Nevertheless, trade-off between area size and transient fault tolerance is open to further research.

Finally, logic functions possess an inherent tolerance independent of methodology and benefits from the equivalence of different logic functions. This is an intrinsic feature of the given logic function having many forms. Figure 8 shows how different faults modify the crossbar and resulted logic function is equivalent to the original in Figure 8(b) and not in Figure 8(c). These tolerated faults are limited to certain switches of crossbar and can be found with using algebraic calculations as show in [START_REF] Tunali | Permanent and transient fault tolerance for reconfigurable nano-crossbar arrays[END_REF]. As for the example in Figure 8 f = x 1 x 2 + x 2 x 3 + x 1 x 3 + x 1 x 2 x 3 , every following function is equivalent to the original one:

• f 1 = x 1 x 2 + x 2 x 3 x 1 + x 1 x 3 + x 1 x 2 x 3 • f 2 = x 1 x 2 x 3 + x 2 x 3 + x 1 x 3 + x 1 x 2 x 3 • f 3 = x 1 x 2 + x 2 x 3 + x 1 x 3 x 2 + x 1 x 2 x 3
For more detailed explanations of determining tolerable switches, calculating the fault tolerance and effects of multioutput functions reader can refer to [START_REF] Tunali | Permanent and transient fault tolerance for reconfigurable nano-crossbar arrays[END_REF].

Eventually, a more resource hungry approach would be fault sensitivity analysis by performing extensive Monte Carlo simulation and determining every possible case of fault occurrence, yet it is rather costly. As a final word, transient fault tolerance, at the moment, is at its infancy and additional research is needed for best practices.

V. PERFORMANCE OPTIMIZATION

We focus on area-oriented optimization for our methodology. As stated in Section I, main motivation to use nanocrossbars is that they are dense. Thus, logic functions can be realized with smaller area. We first find the minimum sized array, and perform defect tolerance analysis. If it is needed, we increase the area size based on the defect tolerance results. Later, we perform delay and power performance analysis with minor tuning. However, as a downside we loose the benefit of further delay and power minimization [13] [5].

Section III investigates the area performance. Here, we will analyze the delay and power depending on number of products and/or literals. Main purpose is to construct a fair metric for performance comparison. In our previous study [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF], we have conducted this analysis for memristive crossbars. All supply voltages of technologies are assumed to be the same. Therefore, comparing their performance behaviors (for a given function) is considered to be sufficient method for integrated synthesis methodology.

1) Delay Analysis: We have used an approach of multiplying resistive and capacitive loads (RC-delay) for delay. This helps us to calculate maximum frequency with 1/delay. In the delay analysis for diode, we see that "number of columns" and "load resistor" dominate the capacitive load and resistive load respectively. For memristive crossbars, it is proportional to constant 7 × t cycle (independent from the target function; i.e. latency). Considering FET, we need to calculate resistive loads and capacitive loads from the longest path for the worst-case scenario. Lastly, four-terminal's delay is directly proportional to the longest path on the lattice, same as FET. The longest path on the lattice can be calculated as explained in [START_REF] Altun | Logic synthesis for switching lattices[END_REF]:

L long path = R R ≤ 2 C ≤ 1 3 R-2 2 C 2 + 2+(-1) R +(-1) C 2 R > 2 C > 1
where R: number of rows, C: number of columns, L long path : length of the longest path on the lattice.

Finally, Delay performances are proportional to:

• Diode: ∝ (load resistor) × (# of literals in f )

• Memristor: ∝ 7 × t cycle (latency) [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF] • FET: ∝ (degree of the largest product in f and f

D ) × ((# of products in f ) + (# of products in f D ) + # of literals in f ) • Four-terminal: ∝ L long path
2) Power Analysis: Power consumption is the total energy used in unit time. Therefore we estimate consumed total energy in a period, afterwards we divided it with delay (delay is proportional with a period at maximum frequency). Because we assumed that circuit will be used in maximum frequency. For delay estimation, we will going to use the formulation in above.

The power of diode based crossbar is dominated by static power. So, it is inversely proportional only with a load resistor. Load resistor can be considered as 10 times of diode's inner resistance. Total energy consumption of memristor is proportional to total count, because it is assumed that all memristors are changing their states one time only [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF]. Note that, in this memristor based crossbar, sneak path current is minimized [START_REF] Kim | A functional hybrid memristor crossbararray/CMOS system for data storage and neuromorphic applications[END_REF], so the power consumption caused by it can be neglected. Total energy consumption of FET crossbars is directly proportional to the capacitance of the output node and nodes related to the output node. For four-terminal, we assume all crosspoints consume energy at the worst-case scenario. Finally, we divide energy consumption by the delay to find the complexity of power consumption.

However, effect of the estimated switching activity of an input to the power consumption is not the same for all technologies. For memristor, even though change in inputs does not cause any change for the state of the output, there will be dynamic power consumption. Because every cycle (stage) will be recalculated. Also, since the power of diode is dominated by static power, we didn't include the effect of switching activity to the calculation of power consumption. For only FET and four-terminal, we include the estimation of switching activity by multiplying it with 0.5. (Notice that, supply voltages are assumed as the same.) Finally, Power performances are proportional to:

• Diode:∝ 1 / (load resistor) • Memristor: ∝ (total memristor count in crossbar)/7 [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF] [39] • FET: ∝ 0.5 / (degree of the largest product in f and f D ) (@ maximum frequency) • Four-terminal: ∝ (0.5 (# of products in rows) × (# of products in columns)) / L long path

VI. A CASE STUDY FOR BENCHMARK FUNCTION Squar5

In this section, we demonstrate the whole process with an example. We have chosen the benchmark function Squar5

Text which has 5 inputs, 25 products and 8 outputs in PLA format. Diagram of the process is given in Figure 9.

First, we need to evaluate different technologies such as diode, FET, memristor or four-terminal. Using logic synthesis, we can generate function descriptions in crossbar (lattice) form and obtain area sizes utilizing equations in Section III. Results are as follows:

Diode: (# of products of all f oi ) + n) × ((# of literals in f ) + n) = (25 + 8) × (10 + 8) = 594.

Memristor: ((# of products of all f oi ) + n) × ((# of literals in f ) + 2n) = (25 + 8) × (10 + 16) = 858. However, our proposed greedy algorithm PGA decreases the size to 832.

FET:

(# of literals in f + n) × ((# of
products of all f oi ) + (# of products of all f D oi )) = (10 + 8) × (25 + 25) = 900. Coincidentally, its dual also has the same number of products.

Four-terminal: (degree of the largest product in f D oi ) × (# of products of all f oi + n -1) = 5 x ( 25 + 8-1) = 160. First term is chosen according to the product which has the maximum number of literals.

Secondly, we use function descriptions and defect map of a crossbar. Applying the defect tolerant logic mapping methods in Section IV, it is possible to measure defect/fault performance. Key point is that diode, FET and memristor have a rich literature of methods for reaching 100% defect tolerance for defect rates up to 10% [START_REF] Tunali | A survey of fault-tolerance algorithms for reconfigurable nano-crossbar arrays[END_REF] [START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF]; nevertheless four-terminal is at its infancy in terms of defect tolerance. In this paper, defect performance of only single output functions are studied and we are planning to extend the work into multi output functions as well in the future.

Lastly, we conduct a performance optimization specific to technology dependent delay and power parameters of crossbars. Since related equations are presented in immediate section, only result are given:

Diode: Delay is R× 10 (Load resistor is shown with R). Power is 1/R. If assume R is 10 times than a diode's inner resistance, then Delay is 100 and Power is 1/10.

Memristor: Delay (latency) is constant (independent from the function) and 7t cycle . Power is 133/7 ≈ 19. The number 133 denotes the number of memristors used in the crossbar.

FET: Delay is 300 and power is 1/10. Including the next four-terminal, FET has the largest delay.

Four-terminal: The longest path is 73, so is the delay. Power is 80/73 ≈ 1.

Note that, values only lights the complexity of delay and power, they are not real elapsed time and power consumption. Here we assume, they all fabricated with same technology. For instance, in order to calculate the delay of diode crossbars, we need to know value of R and the source voltage.

To provide an overall evaluation, four-terminal is the most advantageous choice in terms of area size. However, defect tolerance is poor especially regarding the complexity and computation power needed to conduct experiments for fourterminal. Delay of memristive crossbars is predictable, it doesn't depend on function. Therefore, it could be considered as the most advantageous choice in terms of delay. For power consumption, diode seems to have the least value, yet it is static power also depends source voltage. On the other hand, FET crossbars has only dynamic power consumption with complementary architecture.

VII. CONCLUSION AND DISCUSSION

In conclusion, we have presented an integrated synthesis methodology regarding every design steps of a crossbar circuit including novel optimization and defect tolerance algorithms for each step. Since the main motivation of crossbar technologies is that they are able produce denser circuit structures comparing to the conventional technologies, the synthesis methodology takes area optimization as base. In addition to that, defect tolerance analysis gets the size of the crossbar as the input. However, devising area-oriented optimization causes only having course delay and power analysis/optimization. An extension of the selection of delay-or power-oriented optimizations will increase the performance optimization capability of the methodology.

In logic synthesis section, comparison of four crossbar types with multi-output logic functions is firstly presented. Also, a new technique of logic synthesis for memristor based crossbars is presented. Since developing new efficient algorithms for logic synthesis is in progress and also the area sizes are depending on different parameters of a logic, there has not been a verdict on this race.

In defect tolerance section, we focus on four-terminal architectures and design a novel sensitivity analysis and fault tolerance approach. First step of the method locates the problematic cells and guides the second step through introducing preventive measures such as reassignment of cell (if possible) or adding redundant columns/rows to the lattice. Currently, method is limited in term of input size, so an important improvement to sensitivity analysis would be to increase the number of variables the method can manage.

In performance optimization section, effects of the crossbar size and function parameters to the delay and power are presented. Even though room for optimizations of delay and power are limited due to the area-oriented optimization, the paper presents a clear projections to the designer. However the real values in the crossbar technologies (for different types) is in process of evolving. Certain studies are in proof of concept level. For instance, pitch sizes were given as micrometers in the early 2000s [START_REF] Huang | Logic gates and computation from assembled nanowire building blocks[END_REF] [34], yet they are reduced to tens of manometers [START_REF] Kim | A functional hybrid memristor crossbararray/CMOS system for data storage and neuromorphic applications[END_REF]. Also, a recent study [START_REF] Cevik | Cmos implementation of switching lattices[END_REF] realizes fourterminal switch based crossbar (lattice) with 65nm CMOSprocess for a proof of concept. As expected, the situation is also same for the comparison on the delay and power analysis. This is the inherent reason that this study is independent from technology nodes, thus it can be implemented to the every technology. 3D printing electronics could be a promising candidate for comparing the crossbar types with actual values.

As a future work, a fully automated software tool for the synthesis methodology is planned to be developed. It will take the target function, the used technology, and the performance specifications (area, delay and/or power consumption) as input and return the optimized crossbar-arrays structure as an output. This software tool, to be developed, will benefit from the Text optimization algorithms introduced in this study. It will also produce the mapping using technology specification data. The tool is expected to be updated based on established experimental results and novel algorithms. Another direction could be the study of transient faults on lattices, so that it can generate complete defect tolerance analysis. The future study should evaluate how the redundancies in lattices can limit the area overhead.

Fig. 1 .

 1 Fig. 1. Switching models of a nano-crossbar array: crosspoint as a) twoterminal switch with terminals in the crossed lines, b) two-terminal switch with terminals in the same line, and c) four-terminal switch.

Fig. 2 .

 2 Fig. 2. Realization of f XOR 2 with different nano-crossbar types: crosspoint as a) diode, b) memristor, c) FET, and d) four-terminal switch.

Fig. 3 .

 3 Fig. 3. Integrated synthesis methodology scheme for nano-crossbar arrays.

Fig. 4 .

 4 Fig.[START_REF] Alexandrescu | Synthesis and performance optimization of a switching nano-crossbar computer[END_REF]. Block diagrams of two-level multi output logic synthesis algorithms: initial Greedy Algorithm (GA-initial)[START_REF] Tunali | Defect-tolerant logic synthesis for memristor crossbars with performance evaluation[END_REF] and Proposed Greedy Algorithm (PGA)

Text

6 x 2 x 3 x 1 x 1 x 2 x 3 :Fig. 5 .

 635 Fig. 5. Nano-crossbar array with faulty/defective crosspoints and mapping process.

  a)Fig.6. a) Lattice design for the example function f and its sensitivity map for b) SAO and c) SA1.

Text

Fig. 7 .

 7 Fig. 7. a) defect-free lattice; b) lattice with defects: SA0 in red and SA1 in blue; and c) lattice with the defect fixed.

Fig. 8 .

 8 Fig. 8. Transient faults and how inherent tolerance works.

Fig. 9 .

 9 Fig. 9. Whole integrated synthesis pipeline of benchmark function squar5. R denotes the load resistor.

  Create set 0 and set 1 and SET={set 0 U set 1 }

				Text
	.iIn .oOut .pP . .	Heuristically Find phase combination which gives minimum # of products	.iIn .oOut .pP PhaseCombination .
	.e			.e
	GA_initial (Tunali, 2018)		PGA
			Calculate # of products of F with
	i<Out YES	NO	phase_combination-1 [P1] and phase_combination-0 [P0]
			Reference_Number = min(P1,P0)
	Calculate # of
	products of F i [P i ] and F i [Pinv i ]		Assign phase combination that yields lees number of products to Reference_Phase
	P i < Pinv i	NO	Find the phase combination [temp_phase] in SET yields less number of products.
	YES		Assign the number to temp_number.
	Phase[i]=1
				temp_number <
	Phase[i]=0		NO	Reference_Number
				YES
	Declare the phase combination as array of Phase		Reference_Number = temp_number Reference_Phase = temp_phase
				is the first
				temp_phase in
			YES	set 0 ?	NO
	Declare the phase combination as Reference_Phase		Create new SET based on Reference_Phase Change zeros to one
				Change ones to zero

  Assign minimum number of products to Ref erence N umber, and the phase combination to Ref erence P hase, If YES, Assign temp number to Ref erence N umber, and (temp phase) to Ref erence P hase; If NO, Jump to 8 (end of the algorithm), 5: Decide; If the found very first temp phase is in set 0 , 5a: If YES (in set 0 ), Create a new SET , with phase combinations, by changing "0"s of Ref erence P hase to "1"s, 5b: If NO (in set 1 ), Create a new SET , with phase combinations, by changing "1"s of Ref erence P hase to "0"s, (Note that, every phase combination in SET has only one alteration with Ref erence P hase) 6: Jump to 3, 7: Declare phase combinations as Ref erence P hase.

	: Calculate ucts of phase combination-1 (11..1), 4: Decide; and Compare number of prod-phase combination-0 (00..0) and Ref erence N umber. if temp number	is	less	than

2: Create two sets of candidate phase combinations; set 0 : includes phase combinations that only one output is in "phase-1" and set 1 : includes phase combinations that only one output is in "phase-0", and Assign SET = set 0 ∪ set 1 , 3: Find the phase combinations (temp phase) which yields minimum number of products (temp number) for the function in SET .

  𝟕 𝒙 𝟓 𝒙 𝟒 𝒙 𝟒 𝒙 𝟓 𝒙 𝟕 𝒙 𝟒 𝒙 𝟕 𝒙 𝟔 𝒙 𝟕 𝒙 𝟒 𝒙 𝟕 𝒙 𝟔 𝒙 𝟕 𝒙 𝟒 𝒙 𝟕 𝒙 𝟔 𝒙 𝟕 𝒙 𝟒 𝒙 𝟒 𝒙 𝟔 𝒙 𝟕 𝒙 𝟒 𝒙 𝟕

  APPROACHES AND THEIR SENSITIVITY VALUES

	name	Benchmark Size	Stuck at Fault Model	Adjacent Cellular Fault Model

P 1 P 2 P 4 P 3 x 2 x 3 x 1 x 1 x 2 x 3 f = x 1 x 2 + x 2 x 3 + x 1 x 3 + x 1 x 2 x 3 P 1 P 2 P 4 P 3 P 1 P 2 P 4 P 3 x 2 x 3 x 1 x 1 x 2 x 3 P 1 P 2 P 4 P 3 Transient Faults P 1 P 2 P 4 P 3 x 2 x 3 x 1 x 1 x 2 x 3 P 1 P 2 P 4 P 3

Acknowledgement: We thank Dr. Levent Aksoy for his contribution to synthesis process of multi-output functions with four-terminal based switching arrays.

The work is primarily done when he was with Istanbul Technical University; he is currently affiliated with University of Virginia This work is part of a project that has received funding from the European Union's H2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement #691178, as well as supported by the TUBITAK-Career project #113E760 and TUBITAK-2501 project #218E068.

Copyright (c) 2020 IEEE. Personal use of this material is permitted. However,