Towards achieving reliable and high-performance nanocomputing via dynamic redundancy allocation

ABSTRACT

Nanoelectronic devices are considered to be the computational fabrics for the emerging nanocomputing systems due to their ultra-high speed and integration density. However, the imperfect bottom-up self-assembly fabrication leads to excessive defects that have become a barrier for achieving reliable computing. In addition, transient errors continue to be a problem. The massive parallelism rendered by nanoscale integration opens up new opportunities but also poses challenges on how to manage such massive resources for reliable and high-performance computing. In this paper, we propose a nanoarchitecture solution to address these emerging challenges. By using dynamic redundancy allocation, the massive parallelism is exploited to jointly achieve fault (defect/error) tolerance and high performance. Simulation results demonstrate the effectiveness of the proposed technique under a range of fault rates and operating conditions.

REFERENCES

• 1: Paul Beckett , Andrew Jennings, Towards nanocomputer architecture, Proceedings of the seventh Asia-Pacific conference on Computer systems architecture, p.141-150, January 01, 2002, Melbourne, Victoria, Australia
• 2: Bhaduri, D., Shukla, S., Graham, P., and Gokhale, M. 2007. Comparing reliability-redundancy tradeoffs for two von Neumann multiplexing architectures. IEEE Trans. Nanotech. 6, 3, 265--279.
• 3: Chen, Y., Jung, G.-Y., Ohlberg, D. A. A., Li, X., Stewart, D. R., Jeppesen, J. O., Nielsen, K. A., Stoddart, J. F., and Williams, R. S. 2003. Nanoscale molecular-switch crossbar circuits. Nanotech. 14, 4, 462--468.
• 4: André Dehon, Nanowire-based programmable architectures, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.1 n.2, p.109-162, July 2005 [doi>10.1145/1084748.1084750]
• 5: Keith I. Farkas , Paul Chow , Norman P. Jouppi , Zvonko Vranesic, The multicluster architecture: reducing cycle time through partitioning, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.149-159, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 6: Fountain, T. J., Duff, M. J. B. D., Crawley, D. G., Tomlinson, C., and Moffat, C. 1998. The use of nanoelectronic devices in highly-parallel computing systems. IEEE Trans. VLSI Syst. 6, 1, 31--38.
• 7: Manoj Franklin , Gurindar S. Sohi, The expandable split window paradigm for exploiting fine-grain parallelsim, Proceedings of the 19th annual international symposium on Computer architecture, p.58-67, May 19-21, 1992, Queensland, Australia
• 8: Seth Copen Goldstein , Mihai Budiu, NanoFabrics: spatial computing using molecular electronics, Proceedings of the 28th annual international symposium on Computer architecture, p.178-191, June 30-July 04, 2001, Göteborg, Sweden
• 9: Lance Hammond , Basem A. Nayfeh , Kunle Olukotun, A Single-Chip Multiprocessor, Computer, v.30 n.9, p.79-85, September 1997 [doi>10.1109/2.612253]
• 10: Han, J. and Jonker, P. 2002. A system architecture solution for unreliable nanoelectronic devices. IEEE Trans. Nanotech. 1, 4, 201--208.
• 11: Ligang He , Stephen A. Jarvis , Daniel P. Spooner , Xinuo Chen , Graham R. Nudd, Dynamic Scheduling of Parallel Jobs with QoS Demands in Multiclusters and Grids, Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, p.402-409, November 08-08, 2004 [doi>10.1109/GRID.2004.27]
• 12: Huang, Y., Duan, X., Cui, Y., Lauhon, L. J., Kim, K-Y., and Lieber, C. M. 2001. Logic gates and computation from assembled nanowire building blocks. Science, 294, 5545, 1313--1317.
• 13: Jeffery, C. M. and Figueiredo, R. 2006. Hierarchical fault tolerance for nanoscale memories. IEEE Trans. Nanotech. 5, 44, 407--414.
• 14: Koren, I., Koren, Z., and Stapper, C. H. 1994. A statistical study of defect maps of large area VLSI IC's. IEEE Trans. VLSI Syst., 2, 2, 249--256.
• 15: Kuekes, P. J., Robinett, W., Seroussi, G., and Williams, R. S. 2005. Defect-tolerant interconnect to nanoelectronic circuits: internally redundant demultiplexers based on error-correcting codes. Nanotech. 16, 6, 869--882.
• 16: Lent, C. S., Tougaw, P. D., Porod, W., and Bernstein, G. H. 1993. Quantum cellular automata. Nanotech. 4, 4, 49--57.
• 17: Jack L. Lo , Joel S. Emer , Henry M. Levy , Rebecca L. Stamm , Dean M. Tullsen , S. J. Eggers, Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.322-354, Aug. 1997 [doi>10.1145/263326.263382]
• 18: Xiaojun Ma , Jing Huang , Fabrizio Lombardi, A model for computing and energy dissipation of molecular QCA devices and circuits, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.3 n.4, p.1-30, January 2008 [doi>10.1145/1324177.1324180]
• 19: R. Martel , V. Derycke , J. Appenzeller , S. Wind , Ph. Avouris, Carbon nanotube field-effect transistors and logic circuits, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513944]
• 20: Mazumder, P., Kulkarni, S., Bhattacharya, M., Sun J. P., and Haddad, G. I. 1998. Digital circuit applications of resonant tunneling devices. In Proceeding of the IEEE, 86, 4, 664--686.
• 21: Mishra, M. and Goldstein, S. C. 2003. Defect tolerance at the end of the roadmap. In Proceedings of the International Test Conference. 1201--1211.
• 22: A. Nicolau , J. A. Fisher, Measuring the Parallelism Available for Very Long Instruction Word Architectures, IEEE Transactions on Computers, v.33 n.11, p.968-976, November 1984 [doi>10.1109/TC.1984.1676371]
• 23: Kunle Olukotun , Basem A. Nayfeh , Lance Hammond , Ken Wilson , Kunyung Chang, The case for a single-chip multiprocessor, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.2-11, October 01-04, 1996, Cambridge, Massachusetts, United States
• 24: Wenjing Rao , Alex Orailoglu , Ramesh Karri, Architectural-Level Fault Tolerant Computation in Nanoelectronic Processors, Proceedings of the 2005 International Conference on Computer Design, p.533-542, October 02-05, 2005 [doi>10.1109/ICCD.2005.27]
• 25: Wenjing Rao , Alex Orailoglu , Ramesh Karri, Towards Nanoelectronics Processor Architectures, Journal of Electronic Testing: Theory and Applications, v.23 n.2-3, p.235-254, June 2007 [doi>10.1007/s10836-006-0555-7]
• 26: Roy, S. and Beiu, V. 2005. Majority multiplexing-economical redundant fault-tolerant designs for nanoarchitectures. IEEE Trans. Nanotech. 4, 4, 441--451.
• 27: M. B. Tahoori, A mapping algorithm for defect-tolerance of reconfigurable nano-architectures, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.668-672, November 06-10, 2005, San Jose, CA
• 28: Xueyan Tang , Samuel T. Chanson, Optimizing Static Job Scheduling in a Network of Heterogeneous Computers, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.373, August 21-24, 2000
• 29: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 30: von Neumann, J. 1956. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In Automata Studies, C. Shannon and J. McCarthy, Eds., Princeton University Press.
• 31: Wall, D. W. 1993. Limits of instruction-level parallelism. Wester Research Laboratory Research Report 93/6, Digital Equipment Corporation.
• 32: Wang, S., Wang, L., and Jain, F. 2007. Dynamic redundancy allocation for reliable and high-performance aanocomputing. In Proceedings of the International Symposium on Nanoscale Architectures. 1--6.
• 33: Teng Wang , Zhenghua Qi , Csaba Andras Moritz, Opportunities and challenges in application-tuned circuits and architectures based on nanodevices, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy [doi>10.1145/977091.977161]
• 34: Weiping Zhu , Brett D. Fleisch, Performance Evaluation of Soft Real-Time Scheduling for Multicomputer Cluster, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.610, April 10-13, 2000

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.0 General

General Terms:
Design, Performance, Reliability

Keywords:
Nanoscale architecture, hardware reliability, performance, redundancy allocation, redundant design