A hill climbing algorithm with pre-processing and a column replication method for variation tolerant logic mapping problem

Nano-crossbar arrays are generally manufactured with faster and less costly methods than traditional tow-down lithography methods. However, due to very small device sizes, there is less control over these manufacturing processes. Therefore, crossbar arrays suffer from process variations and defects with considerably higher rates than lithography processes. This variations makes performance of any manufactured array unpredictable and worse than expected. As a result, variation and/or defect tolerant logic mapping algorithms needed to be developed for this problem. In this work, I focus on maximum delay increase due to process variations and focused on optimize this objective. Firstly, a matrix reducing method is proposed to achieve better runtimes for any variation tolerant logic mapping algorithm for the maximum delay optimization. In this method, we find columns which have very low (or no) probability to become the worst case on each performance test and reduce matrix bu deleting these columns. Deleted columns mapped randomly on final mapping. Note that this reducing method is algorithm independent, which means that it can be implemented on any variation tolerant logic mapping search algorithm with same performance criteria. As a variation tolerant logic mapping scheme, a Hill Climbing row search with column re-ordering (as restart points to search) algorithm is proposed. This method restarts Hill Climbing row search after reaching an unoptimizable point by re-ordering columns with data gathered on row search, until any of the stop criteria reached. Also, a greedy initial column ordering algorithm explained and matrix reducing method is applied to Hill Climbing algorithm as pre-processing phase. As an extension for our Hill Climbing algorithm on variance tolerance, we modeled variation tolerant logic mapping problem as defect tolerant logic mapping problem by adding defective crosspoints on array matrix and run our algorithm with these defects. Our algorithm successfully tolerate different defect rates for random matrices or benchmark circuits. Lastly, as a probabilistic approach by process parameters, a worst case route replication method is proposed. This method do not use any search algorithm or need any individual crosspoint characteristic testings, which are time and resource consuming processes. This approach uses area and power overhead as trade-off values, while power-delay product is generally having decreasing characteristics. We simulated all proposed algorithms and methods on Simulation Results Section. We explained some algorithms from the literature and compared our Hill Climbing with Column re-ordering algorithm with these. Our algorithm achieves performance outputs up to 15% and runtimes up to 150-400 times better than methods on the literature, depending on the array size. As a inspection of matrix reducing method, we applied this method on different benchmarks and algorithms to compare time optimization results. Up to 72% time improvement is achieved for certain benchmarks and different algorithms by this reducing approach. Our algorithm achieved 15-30% defect tolerance for random arrays with 40% crosspoint ratio and 5-20% defect tolerance for our benchmark set. We discuss to implement this methods for different nano-crossbar array types like diode or 4-terminal as future work. Also, we aim to improve presented algorithms since both matrix reducing and initial column mapping methods are in their preliminary states in this work.