Cited By
View all- Woodruff JO’Boyle M(2021)New Regular Expressions on Old Accelerators2021 58th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18074.2021.9586095(343-348)Online publication date: 5-Dec-2021
Reliability Analysis for Unreliable FSM Computations
Authors: 
Amir Hossein Nodehi Sabet, 
Junqiao Qiu, 
Zhijia Zhao, 
Sriram KrishnamoorthyAuthors Info & Claims
Article No.: 12, Pages 1 - 23
Abstract
Finite State Machines (FSMs) are fundamental in both hardware design and software development. However, the reliability of FSM computations remains poorly understood. Existing reliability analyses are mainly designed for generic computations and are unaware of the special error tolerance characteristics in FSM computations. This work introduces RelyFSM -- a state-level reliability analysis framework for FSM computations. By modeling the behaviors of unreliable FSM executions and qualitatively reasoning about the transition structures, RelyFSM can precisely capture the inherent error tolerance in FSM computations. Our evaluation with real-world FSM benchmarks confirms both the accuracy and efficiency of RelyFSM.
References
[1]
Kevin Angstadt, Arun Subramaniyan, Elaheh Sadredini, Reza Rahimi, Kevin Skadron, Westley Weimer, and Reetuparna Das. 2018. ASPEN: A scalable In-SRAM architecture for pushdown automata. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture.
[2]
Robert C. Baumann. 2005. Radiation-induced soft errors in advanced semiconductor technologies. IEEE Transactions on Device and Materials Reliability 5, 3 (2005), 305--316.
[3]
Stephen D. Brown. 2007. Fundamentals of Digital Logic with Verilog Design. Tata McGraw-Hill Education.
[4]
Michael Carbin, Sasa Misailovic, and Martin C. Rinard. 2013. Verifying quantitative reliability for programs that execute on unreliable hardware. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA’13). ACM, New York, NY, 33--52.
[5]
Yangjun Chen, Duren Che, and Karl Aberer. 2002. On the efficient evaluation of relaxed queries in biological databases. In Proceedings of the 11th International Conference on Information and Knowledge Management. ACM, New York, NY, 227--236.
[6]
Cristiana Chitic and Daniela Rosu. 2004. On validation of XML streams using finite state machines. In Proceedings of the 7th International Workshop on the Web and Databases: Colocated with ACM SIGMOD/PODS 2004. ACM, New York, NY, 85--90.
[7]
Mihir R. Choudhury and Kartik Mohanram. 2007. Accurate and scalable reliability analysis of logic circuits. In Proceedings of the Conference on Design, Automation, and Test in Europe. 1454--1459.
[8]
Jeffrey J. Cook and Craig Zilles. 2008. A characterization of instruction-level error derating and its implications for error detection. In Proceedings of the 2008 IEEE International Conference on Dependable Systems and Networks with FTCS and DCC (DSN’08). IEEE, Los Alamitos, CA, 482--491.
[9]
Philip Simon Dauber. 1965. An analysis of errors in finite automata. Information and Control 8, 3 (1965), 295--303.
[10]
Marc de Kruijf, Shuou Nomura, and Karthikeyan Sankaralingam. 2010. Relax: An architectural framework for software recovery of hardware faults. In Proceedings of the 37th Annual International Symposium on Computer Architecture (ISCA’10). ACM, New York, NY, 497--508.
[11]
Paul Dlugosch, Dave Brown, Paul Glendenning, Michael Leventhal, and Harold Noyes. 2014. An efficient and scalable semiconductor architecture for parallel automata processing. IEEE Transactions on Parallel and Distributed Systems 25, 12 (2014), 3088--3098.
[12]
Hadi Esmaeilzadeh, Adrian Sampson, Luis Ceze, and Doug Burger. 2012. Architecture support for disciplined approximate programming. In Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVII). ACM, New York, NY, 301--312.
[13]
Hadi Esmaeilzadeh, Adrian Sampson, Luis Ceze, and Doug Burger. 2012. Neural acceleration for general-purpose approximate programs. In Proceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture. IEEE, Los Alamitos, CA, 449--460.
[14]
Laurent Falquet, Marco Pagni, Philipp Bucher, Nicolas Hulo, Christian J. A. Sigrist, Kay Hofmann, and Amos Bairoch. 2002. The PROSITE database, its status in 2002. Nucleic Acids Research 30, 1 (2002), 235--238.
[15]
Bo Fang, Qining Lu, Karthik Pattabiraman, Matei Ripeanu, and Sudhanva Gurumurthi. 2016. ePVF: An enhanced program vulnerability factor methodology for cross-layer resilience analysis. In Proceedings of the 2016 46th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’16). IEEE, Los Alamitos, CA, 168--179.
[16]
Shuguang Feng, Shantanu Gupta, Amin Ansari, and Scott Mahlke. 2010. Shoestring: Probabilistic soft error reliability on the cheap. ACM SIGARCH Computer Architecture News 38 (2010), 385--396.
[17]
Domenico Ficara, Stefano Giordano, Gregorio Procissi, Fabio Vitucci, Gianni Antichi, and Andrea Di Pietro. 2008. An improved DFA for fast regular expression matching. ACM SIGCOMM Computer Communication Review 38, 5 (2008), 29--40.
[18]
Todd J. Green, Gerome Miklau, Makoto Onizuka, and Dan Suciu. 2003. Processing XML streams with deterministic automata. In Proceedings of the International Conference on Database Theory. 173--189.
[19]
Weining Gu, Zbigniew Kalbarczyk, Ravishankar K. Iyer, and Zhenyu Yang. 2003. Characterization of Linux kernel behavior under errors. In Proceedings of the International Conference on Dependable Systems and Networks. IEEE, Los Alamitos, CA, 459.
[20]
Jie Han and Michael Orshansky. 2013. Approximate computing: An emerging paradigm for energy-efficient design. In Proceedings of the 2013 18th IEEE European Test Symposium (ETS’13). IEEE, Los Alamitos, CA, 1--6.
[21]
Siva Kumar Sastry Hari, Sarita V. Adve, Helia Naeimi, and Pradeep Ramachandran. 2012. Relyzer: Exploiting application-level fault equivalence to analyze application resiliency to transient faults. ACM SIGPLAN Notices 47 (2012), 123--134.
[22]
Bingsheng He. 2014. When data management systems meet approximate hardware: Challenges and opportunities. Proceedings of the VLDB Endowment 7, 10 (2014), 877--880.
[23]
Jan Holub and Stanislav Štekr. 2009. On parallel implementations of deterministic finite automata. In Implementation and Application of Automata. Springer, 54--64.
[24]
Peng Jiang and Gagan Agrawal. 2017. Combining SIMD and many/multi-core parallelism for finite state machines with enumerative speculation. ACM SIGPLAN Notices 52, 8 (2017), 179--191.
[25]
Jarkko Kari. 2003. Synchronizing finite automata on Eulerian digraphs. Theoretical Computer Science 295, 1 (2003), 223--232.
[26]
Randy H. Katz and Gaetano Borriello. 2005. Contemporary Logic Design (2nd ed.). Pearson.
[27]
Shmuel Tomi Klein and Yair Wiseman. 2003. Parallel Huffman decoding with applications to JPEG files. Computer Journal 46, 5 (2003), 487--497.
[28]
Smita Krishnaswamy, George F. Viamontes, Igor L. Markov, and John P. Hayes. 2005. Accurate reliability evaluation and enhancement via probabilistic transfer matrices. In Proceedings of the Conference on Design, Automation, and Test in Europe—Volume 1. IEEE, Los Alamitos, CA, 282--287.
[29]
Sailesh Kumar, Sarang Dharmapurikar, Fang Yu, Patrick Crowley, and Jonathan Turner. 2006. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. ACM SIGCOMM Computer Communication Review 36 (2006), 339--350.
[30]
Guanpeng Li and Karthik Pattabiraman. 2018. Modeling input-dependent error propagation in programs. In Proceedings of the IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’18). IEEE, Los Alamitos, CA.
[31]
Guanpeng Li, Karthik Pattabiraman, Siva Kumar Sastry Hari, Michael Sullivan, and Timothy Tsai. 2018. Modeling soft-error propagation in programs. In Proceedings of the IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’18). IEEE, Los Alamitos, CA.
[32]
Xuanhua Li and Donald Yeung. 2007. Application-level correctness and its impact on fault tolerance. In Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture (IIPCA’07). IEEE, Los Alamitos, CA, 181--192.
[33]
Hongyuan Liu, Mohamed Ibrahim, Onur Kayiran, Sreepathi Pai, and Adwait Jog. 2018. Architectural support for efficient large-scale automata processing. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture.
[34]
Tobias Marschall and Sven Rahmann. 2009. Efficient exact motif discovery. Bioinformatics 25, 12 (2009), i356--i364.
[35]
Jin Miao, Andreas Gerstlauer, and Michael Orshansky. 2013. Approximate logic synthesis under general error magnitude and frequency constraints. In Proceedings of the 2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD’13). IEEE, Los Alamitos, CA, 779--786.
[36]
Sasa Misailovic, Michael Carbin, Sara Achour, Zichao Qi, and Martin C. Rinard. 2014. Chisel: Reliability- and accuracy-aware optimization of approximate computational kernels. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA’14). ACM, New York, NY, 309--328.
[37]
Shubhendu S. Mukherjee, Christopher Weaver, Joel Emer, Steven K. Reinhardt, and Todd Austin. 2003. A systematic methodology to compute the architectural vulnerability factors for a high-performance microprocessor. In Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-36). IEEE, Los Alamitos, CA, 29--40.
[38]
Todd Mytkowicz, Madanlal Musuvathi, and Wolfram Schulte. 2014. Data-parallel finite-state machines. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’14). ACM, New York, NY, 529--542.
[39]
Frances Perry, Lester Mackey, George A. Reis, Jay Ligatti, David I. August, and David Walker. 2007. Fault-tolerant typed assembly language. ACM SIGPLAN Notices 42 (2007), 42--53.
[40]
Junqiao Qiu, Zhijia Zhao, and Bin Ren. 2016. MicroSpec: Speculation-centric fine-grained parallelization for FSM computations. In Proceedings of the 2016 International Conference on Parallel Architecture and Compilation Techniques (PACT’16). IEEE, Los Alamitos, CA, 221--233.
[41]
Junqiao Qiu, Zhijia Zhao, Bo Wu, Abhinav Vishnu, and Shuaiwen Leon Song. 2017. Enabling scalability-sensitive speculative parallelization for FSM computations. In Proceedings of the International Conference on Supercomputing. ACM, New York, NY, 2.
[42]
Ashish Ranjan, Swagath Venkataramani, Xuanyao Fong, Kaushik Roy, and Anand Raghunathan. 2015. Approximate storage for energy efficient spintronic memories. In Proceedings of the 52nd Annual Design Automation Conference (DAC’15). ACM, New York, NY, Article 195, 6 pages.
[43]
George A. Reis, Jonathan Chang, Neil Vachharajani, Ram Rangan, and David I. August. 2005. SWIFT: Software implemented fault tolerance. In Proceedings of the International Symposium on Code Generation and Optimization. IEEE, Los Alamitos, CA, 243--254.
[44]
Michael Ringenburg, Adrian Sampson, Isaac Ackerman, Luis Ceze, and Dan Grossman. 2015. Monitoring and debugging the quality of results in approximate programs. In Proceedings of the 20th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’15). ACM, New York, NY, 399--411.
[45]
Indranil Roy and Srinivas Aluru. 2014. Finding motifs in biological sequences using the Micron Automata Processor. In Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium. IEEE, Los Alamitos, CA, 415--424.
[46]
Adrian Sampson, Werner Dietl, Emily Fortuna, Danushen Gnanapragasam, Luis Ceze, and Dan Grossman. 2011. EnerJ: Approximate data types for safe and general low-power computation. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’11). ACM, New York, NY, 164--174.
[47]
Adrian Sampson, Jacob Nelson, Karin Strauss, and Luis Ceze. 2013. Approximate storage in solid-state memories. In Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-46). ACM, New York, NY, 25--36.
[48]
Premkishore Shivakumar, Michael Kistler, Stephen W. Keckler, Doug Burger, and Lorenzo Alvisi. 2002. Modeling the effect of technology trends on the soft error rate of combinational logic. In Proceedings of the 2002 International Conference on Dependable Systems and Networks (DSN’02). IEEE, Los Alamitos, CA, 389--398.
[49]
Wasuwee Sodsong, Jingun Hong, Seongwook Chung, Yeongkyu Lim, Shin-Dug Kim, and Bernd Burgstaller. 2016. Dynamic partitioning-based JPEG decompression on heterogeneous multicore architectures. Concurrency and Computation: Practice and Experience 28, 2 (2016), 517--536.
[50]
Vilas Sridharan and David R. Kaeli. 2009. Eliminating microarchitectural dependency from architectural vulnerability. In Proceedings of the 2009 IEEE 15th International Symposium on High Performance Computer Architecture (IIPCA’09). IEEE, Los Alamitos, CA, 117--128.
[51]
Arun Subramaniyan and Reetuparna Das. 2017. Parallel automata processor. In Proceedings of the 2017 ACM/IEEE 44th Annual International Symposium on Computer Architecture (ISCA’17). IEEE, Los Alamitos, CA, 600--612.
[52]
Arun Subramaniyan, Jingcheng Wang, Ezhil R. M. Balasubramanian, David Blaauw, Dennis Sylvester, and Reetuparna Das. 2017. Cache automaton. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture. ACM, New York, NY, 259--272.
[53]
Swagath Venkataramani, Amit Sabne, Vivek Kozhikkottu, Kaushik Roy, and Anand Raghunathan. 2012. SALSA: Systematic logic synthesis of approximate circuits. In Proceedings of the 49th Annual Design Automation Conference (DAC’12). ACM, New York, NY, 796--801.
[54]
Xin Victoria Wang, Natalie Blades, Jie Ding, Razvan Sultana, and Giovanni Parmigiani. 2012. Estimation of sequencing error rates in short reads. BMC Bioinformatics 13, 1 (2012), 185.
[55]
Li Yu, Dong Li, Sparsh Mittal, and Jeffrey S. Vetter. 2014. Quantitatively modeling application resilience with the data vulnerability factor. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. IEEE, Los Alamitos, CA, 695--706.
[56]
Zhijia Zhao and Xipeng Shen. 2015. On-the-fly principled speculation for FSM parallelization. In Proceedings of the 20th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’15). ACM, New York, NY, 619--630.
[57]
Zhijia Zhao, Bo Wu, and Xipeng Shen. 2014. Challenging the “Embarrassingly Sequential”: Parallelizing finite state machine-based computations through principled speculation. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’14). ACM, New York, NY, 543--558.
Index Terms
- Reliability Analysis for Unreliable FSM Computations
Recommendations
Enabling scalability-sensitive speculative parallelization for FSM computations
ICS '17: Proceedings of the International Conference on SupercomputingFinite state machines (FSMs) are the backbone of many applications, but are difficult to parallelize due to their inherent dependencies. Speculative FSM parallelization has shown promise on multicore machines with up to eight cores. However, as hardware ...
Low power FSM design using Huffman-style encoding
EDTC '97: Proceedings of the 1997 European conference on Design and TestThis paper presents a novel approach to synthesize low power FSMs using non-uniform code length. Switching activity is reduced by decreasing the expected number of state bits switched less than [log |S|] The state set S of the FSM is decomposed into two ...
Incremental methods for FSM traversal
ICCD '95: Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and ProcessorsComputing the set of reachable states of a finite state machine, is an important component of many problems in the synthesis and formal verification of digital systems. The process of design is usually iterative, and the designer may modify and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2020
169 pages
Copyright © 2020 ACM.
© 2020 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the United States Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 29 May 2020
Online AM: 07 May 2020
Accepted: 01 December 2019
Revised: 01 November 2019
Received: 01 June 2019
Published in TACO Volume 17, Issue 2
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- Department of Energy, Office of Science, Office of Advanced Scientific Computing Research
- National Science Foundation
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 780Total Downloads
- Downloads (Last 12 months)141
- Downloads (Last 6 weeks)25
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View all- Woodruff JO’Boyle M(2021)New Regular Expressions on Old Accelerators2021 58th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18074.2021.9586095(343-348)Online publication date: 5-Dec-2021
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in