Quantitative Synthesis for Concurrent Programs

Computer Science – Programming Languages

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Quantitative Synthesis for Concurrent Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantitative Synthesis for Concurrent Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantitative Synthesis for Concurrent Programs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-178719

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.