From Boolean Relations to Control Software
Mari
Federico
author
Melatti
Igor
author
Salvo
Ivano
author
Tronci
Enrico
author
2011
ThinkMind
Many software as well digital hardware automatic synthesis methods define the set of implementations meeting the given system specifications with a boolean relation K. In such a context a fundamental step in the software (hardware) synthesis process is finding effective solutions to the functional equation defined by K. This entails finding a (set of) boolean function(s) F (typically represented using OBDDs, Ordered Binary Decision Diagrams) such that: 1) for all x for which K is satisfiable, K(x, F(x)) = 1 holds; 2) the implementation of F is efficient with respect to given implementation parameters such as code size or execution time. While this problem has been widely studied in digital hardware synthesis, little has been done in a software synthesis context. Unfortunately the approaches developed for hardware synthesis cannot be directly used in a software context. This motivates investigation of effective methods to solve the above problem when F has to be implemented with software. In this paper we present an algorithm that, from an OBDD representation for K, generates a C code implementation for F that has the same size as the OBDD for F and a WCET (Worst Case Execution Time) linear in nr, being n = |x| the number of input arguments for functions in F and r the number of functions in F.
Best Paper Award
exported from refbase (http://mclab.di.uniroma1.it/publications/show.php?record=14), last updated on Sat, 24 Nov 2012 12:30:39 +0100
text
http://www.thinkmind.org/index.php?view=article&articleid=icsea_2011_23_10_10186
http://mclab.di.uniroma1.it/publications/papers/mari/2011/14_Mari_etal2011.pdf
http://www.thinkmind.org/index.php?view=article&articleid=icsea_2011_23_10_10186
Mari_etal2011
Sapienza @ mari @ icsea11
Proceedings of ICSEA 2011, The Sixth International Conference on Software Engineering Advances
2011
ThinkMind
conference publication
528
533
978-1-61208-165-6