The traditional argument goes like this: an n-processor machine can never solve a problem more than n times faster than the same machine with only one processor
This is not quite true: it's not unknown to see superlinear speedup in some "embarrassingly parallel" calculations, because, for example, a larger proportion of the dataset will fit into cache, so that you spend less time waiting for memory fetches.
(That came across as more negative than I intended (even though if superlinearity is ever significant, it works in your favour anyway): I enjoyed the article!)
Yes, I thought there might be effects like this but I couldn't think how to squeeze them into the article. As it is I've just changed "The premise is correct" to "The premise is (approximately) correct" which hints at caveats without going into detail. Thanks for the feedback - and don't worry, I took it in the spirit it was intended!
Hum, looks interesting. I'll have a look at that this evening *mental note*.
I do hope you didn't do that while in Tuscany. Says the person who all heartedly tried but failed discussing cryptography while in Algarve. At least, I was "net"less...
(actually it's applicable to PK stuff as well, but even there you're all about the reductions to hard problems, rather than the wondering how hard the hard problems are)
I take being called a geek to be a nice compliment these days. One of my pupils at the school where I teach said to me on Monday that she thought of me being like Eugene from this year's Big Brother show (geek apparently), but a version of him who likes heavy metal & has a twisted sense of humour :)
Attack of the pedants
Date: 2005-09-21 01:43 pm (UTC)never solve a problem more than n times faster than the same machine
with only one processor
This is not quite true: it's not unknown to see superlinear speedup in some "embarrassingly parallel" calculations, because, for example, a larger proportion of the dataset will fit into cache, so that you spend less time waiting for memory fetches.
Understanding "Understanding "Understanding Brute Force""
Date: 2005-09-21 01:58 pm (UTC)Re: Attack of the pedants
Date: 2005-09-21 02:17 pm (UTC)no subject
Date: 2005-09-21 02:36 pm (UTC)Oh, and if you can find time to post this can you find time to text your poor lonely girlfriend in the wilds of Blackpool?
no subject
Date: 2005-09-21 03:02 pm (UTC)Hope you are back in time and can make it!
Luffs!
no subject
Date: 2005-09-22 09:32 am (UTC)no subject
Date: 2005-09-21 03:44 pm (UTC)no subject
Date: 2005-09-21 03:13 pm (UTC)I do hope you didn't do that while in Tuscany. Says the person who all heartedly tried but failed discussing cryptography while in Algarve. At least, I was "net"less...
no subject
Date: 2005-09-21 03:59 pm (UTC)no subject
Date: 2005-09-21 04:33 pm (UTC)(actually it's applicable to PK stuff as well, but even there you're all about the reductions to hard problems, rather than the wondering how hard the hard problems are)
no subject
Date: 2005-09-21 04:28 pm (UTC)I'm so pathetic
Date: 2005-09-21 04:56 pm (UTC)no subject
Date: 2005-09-21 06:19 pm (UTC)Take pity on a poor free user
no subject
Date: 2005-09-21 07:20 pm (UTC)no subject
Date: 2005-09-22 05:48 pm (UTC)no subject
Date: 2005-09-22 03:44 am (UTC)