Quantitative synthesis for concurrent programs

P. Cerny, K. Chatterjee, T.A. Henzinger, A. Radhakrishna, R. Singh, in:, G. Gopalakrishnan, S. Qadeer (Eds.), Springer, 2011, pp. 243–259.

Download
OA 508.95 KB

Conference Paper | Published | English
Editor
;
Series Title
LNCS
Abstract
We present an algorithmic method for the quantitative, performance-aware synthesis of concurrent programs. The input consists of a nondeterministic partial program and of a parametric performance model. The nondeterminism allows the programmer to omit which (if any) synchronization construct is used at a particular program location. The performance model, specified as a weighted automaton, can capture system architectures by assigning different costs to actions such as locking, context switching, and memory and cache accesses. The quantitative synthesis problem is to automatically resolve the nondeterminism of the partial program so that both correctness is guaranteed and performance is optimal. As is standard for shared memory concurrency, correctness is formalized "specification free", in particular as race freedom or deadlock freedom. For worst-case (average-case) performance, we show that the problem can be reduced to 2-player graph games (with probabilistic transitions) with quantitative objectives. While we show, using game-theoretic methods, that the synthesis problem is Nexp-complete, we present an algorithmic method and an implementation that works efficiently for concurrent programs and performance models of practical interest. We have implemented a prototype tool and used it to synthesize finite-state concurrent programs that exhibit different programming patterns, for several performance models representing different architectures.
Publishing Year
Date Published
2011-04-21
Volume
6806
Page
243 - 259
Conference
CAV: Computer Aided Verification
Conference Location
Snowbird, USA
Conference Date
2011-07-14 – 2011-07-20
IST-REx-ID

Cite this

Cerny P, Chatterjee K, Henzinger TA, Radhakrishna A, Singh R. Quantitative synthesis for concurrent programs. In: Gopalakrishnan G, Qadeer S, eds. Vol 6806. Springer; 2011:243-259. doi:10.1007/978-3-642-22110-1_20
Cerny, P., Chatterjee, K., Henzinger, T. A., Radhakrishna, A., & Singh, R. (2011). Quantitative synthesis for concurrent programs. In G. Gopalakrishnan & S. Qadeer (Eds.) (Vol. 6806, pp. 243–259). Presented at the CAV: Computer Aided Verification, Snowbird, USA: Springer. https://doi.org/10.1007/978-3-642-22110-1_20
Cerny, Pavol, Krishnendu Chatterjee, Thomas A Henzinger, Arjun Radhakrishna, and Rohit Singh. “Quantitative Synthesis for Concurrent Programs.” edited by Ganesh Gopalakrishnan and Shaz Qadeer, 6806:243–59. Springer, 2011. https://doi.org/10.1007/978-3-642-22110-1_20 .
P. Cerny, K. Chatterjee, T. A. Henzinger, A. Radhakrishna, and R. Singh, “Quantitative synthesis for concurrent programs,” presented at the CAV: Computer Aided Verification, Snowbird, USA, 2011, vol. 6806, pp. 243–259.
Cerny P, Chatterjee K, Henzinger TA, Radhakrishna A, Singh R. 2011. Quantitative synthesis for concurrent programs. CAV: Computer Aided Verification, LNCS, vol. 6806. 243–259.
Cerny, Pavol, et al. Quantitative Synthesis for Concurrent Programs. Edited by Ganesh Gopalakrishnan and Shaz Qadeer, vol. 6806, Springer, 2011, pp. 243–59, doi:10.1007/978-3-642-22110-1_20 .
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:15:51Z


Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar