[r-t] Composition search?

[Alan Burlison]

On 24/11/2015 01:49, Don Morrison wrote:

> Yes and no. It isn't clear to me what the bottleneck will be that will
> tickle Amdahl's Law for this problem. While at one level it seems a highly
> parallelizable task, there's got to be some kind of coordination, both for
> decomposing the search and for bringing the results back together. And it's
> complicated by the fact that you can't predict ahead of time which subtasks
> are going to be most fruitful and thus take the most time. While it's not
> clear how big a bottleneck that is, it's there, and it will limit how many
> cores can be effectively deployed, at least for non-exotic architectures,
> though I've no intuition into how big that limit may be. I presume there
> must be a big body of research on parallel search algorithms out there
> somewhere; perhaps there are clever ways of attacking this.

The problem does seem eminently parallelisable and the search space 
seems pretty large, so it should be possible to make use of lots of 
cores. And yes, there has been lots of work in the area of parallel search.

-- 
Alan Burlison
--