2006-03-23 : Automatic synchronization of multithreaded programs.
Create concurrent threads and let these run independently each doing some kind of task.
This could be the most concurrent code. The interleavings exhibited by such a code are
unrestricted. Hey, but we know that a particular interleaving would lead to race condition or data
hazard. Eliminate that that interleaving. How do we specify bad interleavings! By bad behaviours.
Model check for bad behaviours and remove inteleavings leading to bad behaviour. Prune off from
the computation tree!
2006-03-24 : It would help your cause if you spoke more clearly. Ok, let me see what you are
talking about here. There are two goals in concurrent code, safety and liveness. You propose
starting out with zero safety and complete liveness (no synchronization) - ok. It sounds like
you are suggesting we look at the set of all possible interleavings. From that set, we need to
remove the bad interleavings, which are distinguishable by their bad behaviors. It's an
interesting idea, but it doesn't get you much. What you are determining is all possible correct
ways at arriving at a correct solution, when all you really care about is arriving at a correct
solution. Why waste time looking at things you don't care about? The set of all possible
interleavings is factorially huge. It's fine to consider it in a theoretical sense, but you'll
want to keep it theoretical until you can apply rules to shrink it down. It's not something you
can work with in a practical sense.
Let's assume we are keeping it theoretical. You'd need to look at the generator for the set,
(the program) and have rules for modifying the generator until it could not produce bad
interleavings. I agree, this would be a great thing to have. But you'll have to give me some
concrete examples before I believe this will work. In this situation, you are talking about a
program that writes programs. Sure, very possible. But you're actually asking for a program to
understand and manipulate another program. That's a huge challenge.
Parallelizing compilers haven't worked
as well as people have hoped (to date, to my knowledge) and genetic / simulated
annealing algorithms take time to run. You'll find it very hard to compete with a human programmer.
Still, I'm willing to hear more. Tell me what you would do with a concrete example: summing
up all the elements of an array of integers, concurrently. How would what you propose work, when
given this problem?
-- Louis! :)