{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,28]],"date-time":"2023-12-28T05:32:30Z","timestamp":1703741550820},"reference-count":25,"publisher":"IGI Global","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,4,1]]},"abstract":"<p>This paper proposes a probabilistic framework for digital computation with lattices of nanoscale switches based on the mathematical phenomenon of percolation. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. This phenomenon is exploited to compute Boolean functions robustly in the presence of defects. It is shown that the margins, defined in terms of the steepness of the non-linearity, translate into the degree of defect tolerance. Achieving good margins entails a mapping problem. Given a target Boolean function, the problem is how to assign literals to regions of the lattice such that no diagonal paths of 1\u2019s exist in any assignment that evaluates to 0. Assignments with such paths result in poor error margins due to stray, random connections that can form across the diagonal. A necessary and sufficient condition is formulated for a mapping strategy that preserves good margins: the top-to-bottom and left-to-right connectivity functions across the lattice must be dual functions. Based on lattice duality, an efficient algorithm to perform the mapping is proposed. The algorithm optimizes the lattice area while meeting prescribed worst-case margins. Its effectiveness is demonstrated on benchmark circuits.<\/p>","DOI":"10.4018\/jnmc.2011040102","type":"journal-article","created":{"date-parts":[[2013,2,5]],"date-time":"2013-02-05T22:31:56Z","timestamp":1360103516000},"page":"12-30","source":"Crossref","is-referenced-by-count":1,"title":["Robust Computation through Percolation"],"prefix":"10.4018","volume":"3","author":[{"given":"Mustafa","family":"Altun","sequence":"first","affiliation":[{"name":"University of Minnesota, USA"}]},{"given":"Marc D.","family":"Riedel","sequence":"additional","affiliation":[{"name":"University of Minnesota, USA"}]}],"member":"2432","reference":[{"key":"jnmc.2011040102-0","doi-asserted-by":"crossref","unstructured":"Altun, M., & Riedel, M. D. (2010). Lattice-based computation of Boolean functions. In Proceedings of the 47th Design Automation Conference (pp. 609-612).","DOI":"10.1145\/1837274.1837423"},{"key":"jnmc.2011040102-1","article-title":"Logic synthesis for switching lattices.","author":"M.Altun","journal-title":"IEEE Transactions on Computers"},{"key":"jnmc.2011040102-2","doi-asserted-by":"crossref","unstructured":"Altun, M., Riedel, M. D., & Neuhauser, C. (2009). Nanoscale digital computation through percolation. In Proceedings of the 46th Design Automation Conference (pp. 615-616).","DOI":"10.1145\/1629911.1630070"},{"key":"jnmc.2011040102-3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-2821-6","author":"R. K.Brayton","year":"1984","journal-title":"Logic minimization algorithms for VLSI synthesis"},{"key":"jnmc.2011040102-4","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100032680"},{"key":"jnmc.2011040102-5","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270310"},{"key":"jnmc.2011040102-6","doi-asserted-by":"publisher","DOI":"10.1126\/science.291.5505.851"},{"key":"jnmc.2011040102-7","doi-asserted-by":"publisher","DOI":"10.1145\/1084748.1084750"},{"key":"jnmc.2011040102-8","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-27705-6_14"},{"key":"jnmc.2011040102-9","doi-asserted-by":"crossref","unstructured":"Eshaghian-Wilner, M. M., Khitun, A., Navab, S., & Wang, K. (2006). A nano-scale reconfigurable mesh with spin waves. In Proceedings of the International Conference on Computing Frontiers (pp. 5-9).","DOI":"10.1145\/1128022.1128033"},{"key":"jnmc.2011040102-10","doi-asserted-by":"publisher","DOI":"10.1007\/s10836-006-0547-7"},{"key":"jnmc.2011040102-11","doi-asserted-by":"crossref","unstructured":"Huang, J., Tahoori, M., & Lombardi, F. (2004). On the defect tolerance of nano-scale two-dimensional crossbars. In Proceedings of the International Symposium on Defect and Fault Tolerance of Very Large Scale Integration Systems (pp. 96-104).","DOI":"10.1109\/DFTVS.2004.1347829"},{"key":"jnmc.2011040102-12","doi-asserted-by":"publisher","DOI":"10.1126\/science.1066192"},{"key":"jnmc.2011040102-13","doi-asserted-by":"publisher","DOI":"10.1109\/TMAG.2008.2000812"},{"key":"jnmc.2011040102-14","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/16\/6\/043"},{"key":"jnmc.2011040102-15","doi-asserted-by":"publisher","DOI":"10.1002\/1439-7641(20020617)3:6<519::AID-CPHC519>3.0.CO;2-2"},{"key":"jnmc.2011040102-16","author":"E. J.McCluskey","year":"1986","journal-title":"Logic design principles with emphasis on testable semicustom circuits"},{"key":"jnmc.2011040102-17","unstructured":"McElvain, K. (1993). IWLS93 benchmark set: Version 4.0, distributed as part of the IWLS93 benchmark distribution. Retrieved from http:\/\/www.cbl.ncsu.edu:16080\/benchmarks\/lgsynth93\/"},{"key":"jnmc.2011040102-18","doi-asserted-by":"crossref","unstructured":"Pistol, C., Lebeck, A. R., & Dwyer, C. (2006). Design automation for DNA self-assembled nanostructures. In Proceedings of the 43rd Design Automation Conference (pp. 919-924).","DOI":"10.1145\/1146909.1147143"},{"key":"jnmc.2011040102-19","doi-asserted-by":"publisher","DOI":"10.1038\/nature04586"},{"key":"jnmc.2011040102-20","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/18\/3\/035204"},{"key":"jnmc.2011040102-21","doi-asserted-by":"crossref","unstructured":"Sun, F., & Zhang, T. (2006). Two fault tolerance design approaches for hybrid CMOS\/nanodevice digital memories. In Proceedings of the International Workshop on Defect and Fault Tolerant Nanoscale Architectures.","DOI":"10.1109\/TNANO.2007.893572"},{"key":"jnmc.2011040102-22","doi-asserted-by":"publisher","DOI":"10.1126\/science.1070821"},{"key":"jnmc.2011040102-23","doi-asserted-by":"publisher","DOI":"10.1126\/science.1089389"},{"key":"jnmc.2011040102-24","doi-asserted-by":"publisher","DOI":"10.1109\/TNANO.2003.820804"}],"container-title":["International Journal of Nanotechnology and Molecular Computation"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=66395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T21:00:15Z","timestamp":1654117215000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jnmc.2011040102"}},"subtitle":["Synthesizing Logic with Percolation in Nanoscale Lattices"],"short-title":[],"issued":{"date-parts":[[2011,4,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,4]]}},"URL":"https:\/\/doi.org\/10.4018\/jnmc.2011040102","relation":{},"ISSN":["1941-6318","1941-6326"],"issn-type":[{"value":"1941-6318","type":"print"},{"value":"1941-6326","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,1]]}}}