[r-t] Composition search?

[Don Morrison]

On Mon, Nov 23, 2015 at 8:08 PM Alan Burlison <alan.burlison at gmail.com>
wrote:
> Yes, I know.  Not so much of a problem when you have hundreds of cores
though ;-)

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.


-- 
Don Morrison <dfm at ringing.org>
"He had outwitted every enemy but time."
              -- Will Durant, _The Renaissance_
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://bellringers.net/pipermail/ringing-theory/attachments/20151124/c4b27441/attachment-0003.html>