Project Details

Přibližná ekvivalence pro aproximativní počítání

Project Period: 1. 1. 2016 - 31. 12. 2018

Project Type: grant

Code: GA16-17538S

Agency: Czech Science Foundation

Program: Standardní projekty

English title
Relaxed equivalence checking for approximate computing
Type
grant
Keywords

approximate computing; genetic programming; evolvable hardware; relaxed equivalence checking; automata; logic

Abstract

Approximate computing is a promising approach to obtain energy-efficient computer systems. It exploits the fact that many applications are error resilient, i.e., do not require a perfect output to be produced. An open problem is how to effectively obtain approximations that are good compromises between the error ratio, power consumption, and performance. Using evolutionary algorithms for the approximation has led to promising results, but it suffers from scalability problems in evaluating candidate solutions. For that, we propose a novel way: using advanced methods of formal verification redesigned to quickly calculate distances between candidate approximations and the reference implementation, which we call relaxed equivalence checking. The project seeks the following original contributions: (1) efficient algorithms for relaxed equivalence checking of combinational (stateless) and sequential (stateful) systems, (2) approximation algorithms based on genetic programming using the proposed relaxed equivalence checking, (3) experimental evaluation of the proposed approximation methods.

Team members
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT) , research leader
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
Lengál Ondřej, Ing., Ph.D. (UITS FIT VUT)
Rogalewicz Adam, doc. Mgr., Ph.D. (UITS FIT VUT)
Sekanina Lukáš, prof. Ing., Ph.D. (UPSY FIT VUT)
Vašíček Zdeněk, doc. Ing., Ph.D. (UPSY FIT VUT)
Publications

2019

  • SEKANINA Lukáš, VAŠÍČEK Zdeněk and MRÁZEK Vojtěch. Automated Search-Based Functional Approximation for Digital Circuits. Approximate Circuits - Methodologies and CAD. Heidelberg: Springer International Publishing, 2019, pp. 175-203. ISBN 978-3-319-99322-5. Detail

2018

  • HUSA Jakub and KALKREUTH Roman. A Comparative Study on Crossover in Cartesian Genetic Programming. In: Genetic Programming 21st European Conference, EuroGP 2018, Proceedings. Cham: Springer International Publishing, 2018, pp. 203-219. ISBN 978-3-319-77553-1. ISSN 0302-9743. Detail
  • ČEŠKA Milan, HAVLENA Vojtěch, HOLÍK Lukáš, LENGÁL Ondřej and VOJNAR Tomáš. Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection. In: Proceedings of TACAS'18. Thessaloniki: Springer Verlag, 2018, pp. 155-175. ISSN 0302-9743. Detail
  • WIGLASZ Michal and SEKANINA Lukáš. Cooperative Coevolutionary Approximation in HOG-based Human Detection Embedded System. In: 2018 IEEE Symposium Series on Computational Intelligence (SSCI 2018). Bengaluru: Institute of Electrical and Electronics Engineers, 2018, pp. 1313-1320. ISBN 978-1-5386-9276-9. Detail
  • CALINESCU Radu, ČEŠKA Milan, GERASIMOU Simos, KWIATKOWSKA Marta and PAOLETTI Nicola. Efficient Synthesis of Robust Models for Stochastic Systems. Journal of Systems and Software, vol. 2018, no. 143, pp. 140-158. ISSN 0164-1212. Detail
  • MRÁZEK Vojtěch and VAŠÍČEK Zdeněk. Evolutionary Design of Large Approximate Adders Optimized for Various Error Criteria. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '18). Kyoto: Association for Computing Machinery, 2018, pp. 294-295. ISBN 978-1-4503-5764-7. Detail
  • MRÁZEK Vojtěch, VAŠÍČEK Zdeněk and HRBÁČEK Radek. Role of circuit representation in evolutionary design of energy-efficient approximate circuits. IET Computers & Digital Techniques, vol. 2018, no. 4, pp. 139-149. ISSN 1751-8601. Detail
  • MRÁZEK Vojtěch, VAŠÍČEK Zdeněk, SEKANINA Lukáš, JIANG Honglan and HAN Jie. Scalable Construction of Approximate Multipliers With Formally Guaranteed Worst Case Error. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 26, no. 11, 2018, pp. 2572-2576. ISSN 1063-8210. Detail
  • HOLÍK Lukáš, LENGÁL Ondřej, SÍČ Juraj, VEANES Margus and VOJNAR Tomáš. Simulation Algorithms for Symbolic Automata. In: Proc. of 16th International Symposium on Automated Technology for Verification and Analysis. Heidelberg: Springer Verlag, 2018, pp. 109-125. ISBN 978-3-030-01089-8. ISSN 0302-9743. Detail
  • HOLÍK Lukáš, LENGÁL Ondřej, SÍČ Juraj, VEANES Margus and VOJNAR Tomáš. Simulation Algorithms for Symbolic Automata (Technical Report). Ithaca, 2018. Detail

2017

  • SEKANINA Lukáš, VAŠÍČEK Zdeněk and MRÁZEK Vojtěch. Approximate Circuits in Low-Power Image and Video Processing: The Approximate Median Filter. Radioengineering, vol. 26, no. 3, 2017, pp. 623-632. ISSN 1210-2512. Detail
  • ČEŠKA Milan, MATYÁŠ Jiří, MRÁZEK Vojtěch, SEKANINA Lukáš, VAŠÍČEK Zdeněk and VOJNAR Tomáš. Approximating Complex Arithmetic Circuits with Formal Error Guarantees: 32-bit Multipliers Accomplished. In: Proceedings of 36th IEEE/ACM International Conference On Computer Aided Design (ICCAD). Irvine, CA: Institute of Electrical and Electronics Engineers, 2017, pp. 416-423. ISBN 978-1-5386-3093-8. Detail
  • ENEA Constantin, LENGÁL Ondřej, SIGHIREANU Mihaela and VOJNAR Tomáš. Compositional Entailment Checking for a Fragment of Separation Logic. Formal Methods in System Design, vol. 2017, no. 51, pp. 575-607. ISSN 0925-9856. Detail
  • CALINESCU Radu, ČEŠKA Milan, GERASIMOU Simos, KWIATKOWSKA Marta and PAOLETTI Nicola. Designing Robust Software Systems through Parametric Markov Chain Synthesis. In: Proceedings of 14th IEEE International Conference On Software Architecture. New Jersey: IEEE Computer Society, 2017, pp. 131-140. ISBN 978-1-5090-5729-0. Detail
  • MRÁZEK Vojtěch, HRBÁČEK Radek, VAŠÍČEK Zdeněk and SEKANINA Lukáš. EvoApprox8b: Library of Approximate Adders and Multipliers for Circuit Design and Benchmarking of Approximation Methods. In: Proc. of the 2017 Design, Automation & Test in Europe Conference & Exhibition (DATE). Lausanne: European Design and Automation Association, 2017, pp. 258-261. ISBN 978-3-9815370-9-3. Detail
  • FIEDOR Tomáš, HOLÍK Lukáš, JANKŮ Petr, LENGÁL Ondřej and VOJNAR Tomáš. Lazy Automata Techniques for WS1S. In: Proceedings of TACAS'17. Lecture Notes in Computer Science, vol. 10205. Heidelberg: Springer Verlag, 2017, pp. 407-425. ISBN 978-3-662-54576-8. ISSN 0302-9743. Detail
  • FIEDOR Tomáš, HOLÍK Lukáš, JANKŮ Petr, LENGÁL Ondřej and VOJNAR Tomáš. Lazy Automata Techniques for WS1S. arXiv:1701.06282, 2017. Detail
  • MINAŘÍK Miloš and SEKANINA Lukáš. On Evolutionary Approximation of Sigmoid Function for HW/SW Embedded Systems. In: 20th European Conference on Genetic Programming, EuroGP 2017. Lecture Notes in Computer Science, vol. 10196. Berlin: Springer International Publishing, 2017, pp. 343-358. ISBN 978-3-319-55696-3. Detail
  • CALINESCU Radu, ČEŠKA Milan, GERASIMOU Simos, KWIATKOWSKA Marta and PAOLETTI Nicola. Recent Advances in Designing Robust Probabilistic Systems. 2nd International Workshop on Design and Analysis of Robust Systems (Extended Abstract). Berlin, 2017. Detail
  • VAŠÍČEK Zdeněk. Relaxed equivalence checking: a new challenge in logic synthesis. In: Proceedings 2017 IEEE 20th International Symposium on Design and Diagnotics of Electronic Circuit & Systems. Dresden: IEEE Computer Society, 2017, pp. 1-6. ISBN 978-1-5386-0472-4. Detail
  • CALINESCU Radu, ČEŠKA Milan, GERASIMOU Simos, KWIATKOWSKA Marta and PAOLETTI Nicola. RODES: A Robust-Design Synthesis Tool for Probabilistic Systems. In: Proceedings of 14th International Conference on Quantitative Evaluation of SysTems. Heidelberg: Springer Verlag, 2017, pp. 304-308. ISBN 978-3-319-66335-7. Detail
  • CARDELLI Luca, ČEŠKA Milan, FRANZLE Martin, KWIATKOWSKA Marta, LAURENTI Luca, PAOLETTI Nicola and WHITBY Max. Syntax-Guided Optimal Synthesis for Chemical Reaction Networks. In: Proceedings of the 29th International Conference on Computer Aided Verification. Lecture Notes in Computer Science, vol. 10427. Heidelberg: Springer Verlag, 2017, pp. 375-395. ISBN 978-3-319-63390-9. Detail
  • VAŠÍČEK Zdeněk, MRÁZEK Vojtěch and SEKANINA Lukáš. Towards Low Power Approximate DCT Architecture for HEVC Standard. In: Proc. of the 2017 Design, Automation & Test in Europe Conference & Exhibition (DATE). Lausanne: European Design and Automation Association, 2017, pp. 1576-1581. ISBN 978-3-9815370-9-3. Detail

2016

  • ABATE Alessandro, ČEŠKA Milan and KWIATKOWSKA Marta. Approximate Policy Iteration for Markov Decision Processes via Quantitative Adaptive Aggregations. In: Proceedings of 14th International Symposium on Automated Technology for Verification and Analysis. Lecture Notes in Computer Science, vol. 9938. Heidelberg: Springer Verlag, 2016, pp. 13-31. ISBN 978-3-319-46519-7. Detail
  • HRBÁČEK Radek, MRÁZEK Vojtěch and VAŠÍČEK Zdeněk. Automatic Design of Approximate Circuits by Means of Multi-Objective Evolutionary Algorithms. In: Proceedings of the 11th International Conference on Design & Technology of Integrated Systems in Nanoscale Era. Istanbul: Istanbul Sehir University, 2016, pp. 239-244. ISBN 978-1-5090-0335-8. Detail
  • MRÁZEK Vojtěch and VAŠÍČEK Zdeněk. Automatic Design of Arbitrary-Size Approximate Sorting Networks with Error Guarantee. In: Power and Timing Modeling, Optimization and Simulation (PATMOS), 2016 26rd International Workshop on. Bremen: Institute of Electrical and Electronics Engineers, 2016, pp. 221-228. ISBN 978-1-5090-0733-2. Detail
  • DVOŘÁČEK Petr and SEKANINA Lukáš. Evolutionary Approximation of Edge Detection Circuits. In: 19th European Conference on Genetic programming. Lecture Notes in Computer Science, vol. 9594. Berlin: Springer International Publishing, 2016, pp. 19-34. ISBN 978-3-319-30667-4. Detail
  • VAŠÍČEK Zdeněk, MRÁZEK Vojtěch and SEKANINA Lukáš. Evolutionary Functional Approximation of Circuits Implemented into FPGAs. In: 2016 IEEE Symposium Series on Computational Intelligence. Athens: Institute of Electrical and Electronics Engineers, 2016, pp. 1-8. ISBN 978-1-5090-4240-1. Detail
  • VAVERKA Filip, HRBÁČEK Radek and SEKANINA Lukáš. Evolving Component Library for Approximate High Level Synthesis. In: 2016 IEEE Symposium Series on Computational Intelligence. Athens: IEEE Computational Intelligence Society, 2016, pp. 1-8. ISBN 978-1-5090-4240-1. Detail
  • CHEN Yu-Fang, HSIEH Chiao, LENGÁL Ondřej, LII Tsung-Ju, TSAI Ming-Hsien, WANG Bow-Yaw and WANG Farn. PAC Learning-Based Verification and Model Synthesis. In: Proceedings of the 38th International Conference on Software Engineering. Austin, TX: Association for Computing Machinery, 2016, pp. 714-724. ISBN 978-1-4503-3900-1. Detail
  • HOLÍK Lukáš, LENGÁL Ondřej, ROGALEWICZ Adam, SEKANINA Lukáš, VAŠÍČEK Zdeněk and VOJNAR Tomáš. Towards Formal Relaxed Equivalence Checking in Approximate Computing Methodology. In: 2nd Workshop on Approximate Computing (WAPCO 2016). Prague, 2016, pp. 1-6. Detail
  • SEKANINA Lukáš and KAPUSTA Vlastimil. Visualisation and Analysis of Genetic Records Produced by Cartesian Genetic Programming. In: GECCO'16 Companion. New York: Association for Computing Machinery, 2016, pp. 1411-1418. ISBN 978-1-4503-4323-7. Detail
Products

2017

  • Gaston - Symbolic WS1S Solver, software, 2017
    Authors: Fiedor Tomáš, Holík Lukáš, Janků Petr, Lengál Ondřej, Vojnar Tomáš Detail
Back to top