Abstract
Safety-critical systems are becoming more complex with use cases like autonomous driving or human-robot collaboration. Therefore, the performance impact of software-based fault-tolerance methods is challenging. Using software-based fault tolerance is an attractive approach because commercial off-the-shelf hardware can be used. One possibility to implement software-based fault tolerance are arithmetic codes, already used in safety-critical products. Recently, AN codes have received particular attention; however, they have a significant performance impact in complex safety applications that require 64-bit wide integer calculations. Therefore, we comprehensively analyze different arithmetic codes in this work to identify the best suitable 64-bit integer support. We identify the ones’ complement as the best matching encoding strategy through new code metrics, fault simulations, and performance analysis. We validate our results by applying ones’ complement coding to a sample algorithm. Performance measurements and fault injection simulation confirm our results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The source code of all analyses and measurements in this paper can be found at https://github.com/iswunistuttgart/arithmetic-coding-int.
- 2.
- 3.
- 4.
References
Avizienis, A.: Arithmetic error codes: cost and effectiveness studies for application in digital system design. IEEE Trans. Comput. C-20(11), 1322–1331 (1971)
Aviziens, A.: Fault-tolerant systems. IEEE Trans. Comput. C-25(12), 1304–1312 (1976)
Braun, J., Mottok, J.: The myths of coded processing. In: 17th International Conference on High Performance Computing and Communications, pp. 1637–1644. IEEE (2015)
Dubrova, E.: Fault-Tolerant Design. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-2113-9
Engel, H.: Data flow transformations to detect results which are corrupted by hardware faults. In: IEEE High-Assurance Systems Engineering Workshop, pp. 279–285. IEEE Computer Society Press (1997)
Fischer, M., Riedel, O., Lechler, A.: Arithmetic coding for floating-points and elementary mathematical functions. In: 5th International Conference on System Reliability and Safety (ICSRS), pp. 270–275. IEEE (2021)
Fischer, M., Riedel, O., Lechler, A., Verl, A.: Arithmetic coding for floating-point numbers. In: IEEE Conference on Dependable and Secure Computing (DSC), pp. 01–08. IEEE (2021)
Forin, P.: Vital coded microprocessor principles and application for various transit systems. IFAC Proc. Vol. 23(2), 79–84 (1990)
Früchtl, M.: Sicherheit eingebetteter Systeme auf Basis arithmetischer Codierungen. Ph.D. thesis, Universität Kassel, Kassel (2014)
Haddadin, S., de Luca, A., Albu-Schaffer, A.: Robot collisions: a survey on detection, isolation, and identification. IEEE Trans. Robot. 33(6), 1292–1312 (2017)
ISO/IEC: IEC 61508-2 functional safety of electrical/electronic/programmable electronic safety-related systems - part 2: requirements for electrical/electronic/programmable electronic safety-related systems
Koren, I., Krishna, C.M.: Fault-Tolerant Systems. Elsevier Morgan Kaufmann, Amsterdam (2007)
Kuvaiskii, D., Fetzer, C.: Delta-encoding: practical encoded processing. In: 2015 45th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2014), pp. 13–24. IEEE Computer Society (2015)
Kwan, D., Shtoyk, K., Serebryany, K., Lifantsev, M.L., Hochschild, P.: SiliFuzz: fuzzing CPUs by proxy. Technical report, Google (2021)
Mukherjee, S.: Architecture Design for Soft Errors. Elsevier, Burlington (2008)
Oh, N., Mitra, S., McCluskey, E.J.: ED4I: error detection by diverse data and duplicated instructions. IEEE Trans. Comput. 51(2), 180–199 (2002)
O’Halloran, M., Hall, J.G., Rapanotti, L.: Safety engineering with COTS components. Reliab. Eng. Syst. Saf. 160, 54–66 (2017)
Omidi, R., Towhidy, A., Mohammadi, K.: A survey on the best choice for modulus of residue code. Indones. J. Electr. Eng. Inform. (IJEEI) 7(4), 734–741 (2020)
Omondi, A.R.: Cryptography Arithmetic: Algorithms and Hardware Architectures. Advances in Information Security, vol. 77. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-34142-8
Osinski, L., Langer, T., Mottok, J.: A survey of fault tolerance approaches at different architecture levels. In: Trinitis, C., Pionteck, T. (eds.) ARCS 2017. VDE Verlag GmbH (2017)
Profeta, J.A., et al.: Safety-critical systems built with COTS. Computer 29(11), 54–60 (1996)
Reis, G.A., Chang, J., August, D.I.: Automatic instruction-level software-only recovery. In: International Conference on Dependable Systems and Networks, pp. 83–92. IEEE Computer Society (2006)
Reis, G.A., Chang, J., Vachharajani, N., Rangan, R., August, D.I.: SWIFT: software implemented fault tolerance. In: International Symposium on Code Generation and Optimization, pp. 243–254. IEEE Computer Society (2005)
Schiffel, U.: Hardware error detection using AN-codes. Ph.D. thesis, Technischen Universität Dresden, Dresden (2011)
Schuster, S., Ulbrich, P., Stilkerich, I., Dietrich, C., Schröder-Preikschat, W.: Demystifying soft-error mitigation by control-flow checking - a new perspective on its effectiveness. ACM Trans. Embed. Comput. Syst. 16(5s), 1–19 (2017)
Srikanth, S., Deng, B., Conte, T.M.: A brief survey of non-residue based computational error correction (2016)
Süßkraut, M., Schmitt, A., Kaienburg, J.: Safe program execution with diversified encoding. In: Proceedings of the 13th Embedded World Conference (2015)
Ulbrich, P.: Ganzheitliche Fehlertoleranz in eingebetteten Softwaresystemen. Ph.D. thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Fischer, M., Riedel, O., Lechler, A. (2022). Comprehensive Analysis of Software-Based Fault Tolerance with Arithmetic Coding for Performant Encoding of Integer Calculations. In: Trapp, M., Saglietti, F., Spisländer, M., Bitsch, F. (eds) Computer Safety, Reliability, and Security. SAFECOMP 2022. Lecture Notes in Computer Science, vol 13414. Springer, Cham. https://doi.org/10.1007/978-3-031-14835-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-14835-4_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-14834-7
Online ISBN: 978-3-031-14835-4
eBook Packages: Computer ScienceComputer Science (R0)