Hofferek, Georg; Gupta, AshutoshIST Austria
Boolean controllers for systems with complex datapaths are often very difficult to implement correctly, in particular when concurrency is involved. Yet, in many instances it is easy to formally specify correctness. For example, the specification for the controller of a pipelined processor only has to state that the pipelined processor gives the same results as a non-pipelined reference design. This makes such controllers a good target for automated synthesis. However, an efficient abstraction for the complex datapath elements is needed, as a bit-precise description is often infeasible. We present Suraq, the first controller synthesis tool which uses uninterpreted functions for the abstraction. Quantified firstorder formulas (with specific quantifier structure) serve as the specification language from which Suraq synthesizes Boolean controllers. Suraq transforms the specification into an unsatisfiable SMT formula, and uses Craig interpolation to compute its results. Using Suraq, we were able to synthesize a controller (consisting of two Boolean signals) for a five-stage pipelined DLX processor in roughly one hour and 15 minutes.
The work presented in this paper was supported in part by the European Research Council (ERC) under grant agreement QUAINT (I774-N23)
68 - 74
HVC: Haifa Verification Conference
2014-11-18 – 2014-11-20
Hofferek G, Gupta A. Suraq - a controller synthesis tool using uninterpreted functions. In: Yahav E, ed. HVC 2014. Vol 8855. Springer; 2014:68-74. doi:10.1007/978-3-319-13338-6_6
Hofferek, G., & Gupta, A. (2014). Suraq - a controller synthesis tool using uninterpreted functions. In E. Yahav (Ed.), HVC 2014 (Vol. 8855, pp. 68–74). Haifa, Israel: Springer. https://doi.org/10.1007/978-3-319-13338-6_6
Hofferek, Georg, and Ashutosh Gupta. “Suraq - a Controller Synthesis Tool Using Uninterpreted Functions.” In HVC 2014, edited by Eran Yahav, 8855:68–74. Springer, 2014. https://doi.org/10.1007/978-3-319-13338-6_6.
G. Hofferek and A. Gupta, “Suraq - a controller synthesis tool using uninterpreted functions,” in HVC 2014, Haifa, Israel, 2014, vol. 8855, pp. 68–74.
Hofferek G, Gupta A. 2014. Suraq - a controller synthesis tool using uninterpreted functions. HVC 2014. HVC: Haifa Verification Conference, LNCS, vol. 8855. 68–74.
Hofferek, Georg, and Ashutosh Gupta. “Suraq - a Controller Synthesis Tool Using Uninterpreted Functions.” HVC 2014, edited by Eran Yahav, vol. 8855, Springer, 2014, pp. 68–74, doi:10.1007/978-3-319-13338-6_6.