Robust FPGA resynthesis based on fault-tolerant Boolean matching

ABSTRACT

We present FPGA logic synthesis algorithms for stochastic fault rate reduction in the presence of both permanent and transient defects. We develop an algorithm for fault tolerant Boolean matching (FTBM), which exploits the flexibility of the LUT configuration to maximize the stochastic yield rate for a logic function. Using FTBM, we propose a robust resynthesis algorithm (ROSE) which maximizes stochastic yield rate for an entire circuit. Finally, we show that existing PLB (programmable logic block) templates for area-aware Boolean matching and logic resynthesis are not effective for fault tolerance, and propose a new robust template with path re-convergence. Compared to the state-of-the-art academic technology mapper Berkeley ABC, ROSE using the proposed robust PLB template reduces the fault rate by 25% with 1% fewer LUTs, and increases MTBF (mean time between failures) by 31%, while preserving the optimal logic depth.

REFERENCES

• 1: A. Djupdal and P. C. Haddow, "Yield enhancing defect tolerance techniques for FPGAs," in MAPLD International Conference, 2006.
• 2: S. Durand and C. Piguet, "FPGA with self-repair capabilities," in FPGA, 1994.
• 3: N. J. Howard, A. M. Tyrrell, and N. M. Allinson, "The yield enhancement of field-programmable gate arrays," in TVLSI, 1994.
• 4: "Altera stratix II features," in http://www.altera.com/products/devices/stratix2/, 2006.
• 5: Abderrahim Doumar , Hideo Ito, Design of Switching Blocks Tolerating Defects/Faults in FPGA Interconnection Resources, Proceedings of the 15th IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems, p.134-142, October 25-27, 2000
• 6: A. J. Yu and G. G. Lemieux, "Defect-tolerant FPGA switch block and connection block with fine-grain redundancy for yield enhancement," in FPL, 2005.
• 7: H. Naeimi, "A greedy algorithm for tolerating defective crosspoints in NanoPLA design," in Master Thesis, California Institute of Technology, 2005.
• 8: M. Joshi and W. Al-Assadi, "Development and Analysis of Defect Tolerant Bipartite Mapping Techniques for Programmable cross-points in Nanofabric Architecture," Springer Netherlands, 2007.
• 9: Ravi Bonam , Yong-Bin Kim , Minsu Choi, Defect-Tolerant Gate Macro Mapping & Placement in Clock-Free Nanowire Crossbar Architecture, Proceedings of the 22nd IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems, p.161-169, September 26-28, 2007
• 10: R. Lyons and W. Vanderkulk, "The use of triple-modular redundancy to improve computer reliability," in IBM Journal of Research and Development, 1962.
• 11: Yan Lin , Lei He, Device and architecture concurrent optimization for FPGA transient soft error rate, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 12: Andrew Ling , Deshanand P. Singh , Stephen D. Brown, FPGA technology mapping: a study of optimality, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065693]
• 13: A. Ling, D. Singh, and S. Brown, "FPGA logic synthesis using quantified boolean satisfiability," in SAT, 2005.
• 14: Christos H Papadimitriou, Games against nature, Journal of Computer and System Sciences, v.31 n.2, p.288-301, Sept. 1985 [doi>10.1016/0022-0000(85)90045-5]
• 15: "Altera: QUIP for Quartus II V5.0," in http://www.altera.com/education/univ/.
• 16: "ABC: A system for sequential synthesis and verification," in http://www.eecs.berkeley.edu/alanmi/abc/.
• 17: J. Cong and Y.-Y. Hwang, "Boolean matching for LUT-based logic blocks with applications to architecture evaluation and technology mapping," in TODAES, 2001.
• 18: Luca Benini , Giovanni De Micheli, A survey of Boolean matching techniques for library binding, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.193-226, July 1997 [doi>10.1145/264995.264996]
• 19: Jason Cong , Kirill Minkovich, Improved SAT-based Boolean matching using implicants for LUT-based FPGAs, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216944]
• 20: Yu Hu , Victor Shih , Rupak Majumdar , Lei He, Exploiting symmetry in SAT-based Boolean matching for heterogeneous FPGA technology mapping, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 21: Sean Safarpour , Andreas Veneris , Gregg Baeckler , Richard Yuan, Efficient SAT-based Boolean matching for FPGA technology mapping, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147034]
• 22: G. D. Micheli, "Synchronous logic synthesis: algorithms for cycle-time minimization," in TCAD, 1991.
• 23: A. Mishchenko, S. Chatterjee, and R. Brayton, "DAG-aware AIG rewriting," in DAC, 2005.
• 24: S. Malik, E. Sentovich, R. Brayton, and A. Sangiovanni-Vincentelli, "Retiming and resynthesis: Optimizing sequential networks with combinational techniques," in TCAD, 1991.
• 25: R. Brayton and A. Mishchenko, "Sequential rewriting," in IWLS, 2007.
• 26: E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, "Logic decomposition during technology mapping," in TCAD, 1997.
• 27: Alan Mishchenko , Xinning Wang , Timothy Kam, A new enhanced constructive decomposition and mapping algorithm, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775871]
• 28: Yu Hu , Victor Shih , Rupak Majumdar , Lei He, FPGA area reduction by multi-output function based sequential resynthesis, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391478]
• 29: Alan Mishchenko , Robert K. Brayton, SAT-Based Complete Don't-Care Computation for Network Optimization, Proceedings of the conference on Design, Automation and Test in Europe, p.412-417, March 07-11, 2005 [doi>10.1109/DATE.2005.264]
• 30: Michael L. Littman, Initial experiments in stochastic satisfiability, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.667-672, July 18-22, 1999, Orlando, Florida, United States
• 31: N. Een and N. Sorensso, http://minisat.se/.
• 32: Zhong Xiu , David A. Papa , Philip Chong , Christoph Albrecht , Andreas Kuehlmann , Rob A. Rutenbar , Igor L. Markov, Early research experience with OpenAccess gear: an open source development environment for physical design, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055156]
• 33: Shubhendu S. Mukherjee , Joel Emer , Steven K. Reinhardt, The Soft Error Problem: An Architectural Perspective, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.243-247, February 12-16, 2005 [doi>10.1109/HPCA.2005.37]
• 34: "Altera stratix III features," in http://www.altera.com, 2007.
• 35: A. Cosoroaba and F. Rivoallon, "Achieving higher system performance with the Virtex-5 family of FPGAs," in http://www.xilinx.com/literature.
• 36: Alan Mishchenko , Robert Brayton , Satrajit Chatterjee, Boolean factoring and decomposition of logic networks, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
• 37: R. K. Brayton and F. Somenzi, "Boolean relations and the incomplete specification of logic networks," in VLSI, 1989.
• 38: Shigeru Yamashita , Hiroshi Sawada , Akira Nagoya, A new method to express functional permissibilities for LUT based FPGAs and its applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.254-261, November 10-14, 1996, San Jose, California, United States
• 39: Sudipta Kundu , Sorin Lerner , Rajesh Gupta, Validating High-Level Synthesis, Proceedings of the 20th international conference on Computer Aided Verification, July 07-14, 2008, Princeton, NJ, USA [doi>10.1007/978-3-540-70545-1_44]
• 40: J. von Neumann, "Probabilistic logics and the synthesis of reliable organisms from unreliable components," in Automata Studies (C. Shannon and J. McCarthy, eds.), Princeton Univ. Press, 1956.
• 41: Alessandra Nardi , Alberto L. Sangiovanni-Vincentelli, Synthesis for Manufacturability: A Sanity Check, Proceedings of the conference on Design, automation and test in Europe, p.20796, February 16-20, 2004
• 42: Smita Krishnaswamy , Stephen M. Plaza , Igor L. Markov , John P. Hayes, Enhancing design robustness with reliability-aware resynthesis and logic simulation, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 43: Michael L. Case , Victor N. Kravets , Alan Mishchenko , Robert K. Brayton, Merging nodes under sequential observability, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391605]
• 44: Yu Hu , Victor Shih , Rupak Majumdar , Lei He, FPGA area reduction by multi-output function based sequential resynthesis, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391478]