Towards on-chip fault-tolerant communication

ABSTRACT

As CMOS technology scales down into the deep-submicron (DSM) domain, devices and interconnects are subject to new types of malfunctions and failures that are harder to predict and avoid with the current system-on-chip (SoC) design methodologies. Relaxing the requirement of 100% correctness in operation drastically reduces the costs of design but, at the same time, requires SoCs be designed with some degree of system-level fault-tolerance. In this paper, we introduce a high-level model of DSM failure patterns and propose a new communication paradigm for SoCs, namely stochastic communication. Specifically, for a generic tile-based architecture, we propose a randomized algorithm which not only separates computation from communication, but also provides the required fault-tolerance to on-chip failures. This new technique is easy and cheap to implement in SoCs that integrate a large number of communicating IP cores.

REFERENCES

• 1: Alberto Leon-Garcia , Indra Widjaja, Communication Networks, McGraw-Hill, Inc., New York, NY, 2003
• 2: N. Bailey. The Mathematical Theory of Infectious Diseases. Charles Griffin and Company, London, 2 edition, 1975.
• 3: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 4: William J. Dally , Brian Towles, Route packets, net wires: on-chip inteconnectoin networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 5: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 6: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 7: Vassos Hadzilacos , Sam Toueg, A Modular Approach to Fault-Tolerant Broadcasts and Related Problems, Cornell University, Ithaca, NY, 1994
• 8: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 9: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 10: F. T. Leighton et. al. On the fault tolerance of some popular bounded-degree networks. In IEEE Symp. on Foundations of Computer Science, 1992.
• 11: Wojciech Maly, IC design in high-cost nanometer-technologies era, Proceedings of the 38th conference on Design automation, p.9-14, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378249]
• 12: G. Martin, Design methodologies for system level IP, Proceedings of the conference on Design, automation and test in Europe, p.286-289, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 13: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
• 14: Semiconductor Association. "The International Technology Roadmap for Semiconductors (ITRS)", 2001.
• 15: Y. Taur and et. al. CMOS scaling into the nanometer regime. In Proc. of the IEEE, volume 85, April 1997.
• 16: T. N. Theis. The future of interconnection technology. IBM Journal on Research and Development, 44(3), 2000.
• 17: T. Valtonen et. al. Interconnection of autonomous error-tolerant cells. In Proc. ISCAS, 2002.