(Inspired by Amdahl)’s competition
My colleague Patrick Madden, a professor of computer science at Binghamton University in New York, is a great fan of Amdahl’s Law, and in fact writes a blog of that name. His main argument is that Amdahl’s Law, which limits the speedup possible on an application ported or written for a multicore processor to the (easily) parallelisable part of the application, means that the pendulum of the computing industry has swung far too much to the “multicore” phenomenon of recent years, and is now ignoring potential improvement in single processor performance that would have an impact on many applications not-so-easily parallelised.
In my discussions with Patrick I think we have agreed that the world divides into different parts, and as my colleague Steve Leibson and I have discussed, there are many application and product spaces that can make use of multiple heterogeneous ASIPs - applications that demonstrate “convenient concurrency“. This is especially true in areas such as multimedia image processing, multi-functional portable devices of all kinds, and networking, as well as certain domains in high performance computing. However, I do agree with Patrick that there are other kinds of applications that could be called “stubbornly sequential”, and may best be solved, with our current state of understanding and knowledge, by a faster uni-processor, assuming one could be built.
With that in mind, Patrick has issued a challenge which you can read about at his blog: “Take $1000 out of my pocket for Thinking Parallel”, for someone who can come up with a parallel multicore implementation of the shortest path problem, that beats Dijkstra’s serial algorithm, on a challenge called the 9th. DIMACS Implementation Challenge for Shortest Path. Read more about it at Patrick’s Blog! But please comment on it here if you would like.
4 Comments »
RSS feed for comments on this post. TrackBack URI
Leave a comment
Line and paragraph breaks automatic, e-mail address never displayed, HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>
August 5th, 2008 @ 2:47 am
I think the best argument about this is made in the July 2008 issue of IEEE Computer, where Mark Hill of UWisc argue that in most cases, for a varied workload, the best system combines a small number of fast and expensive cores with lots of slower cheaper cores. In this way, you have a strong single-thread processor to pull you through the stubbornly sequential part, and then lots of parallelism for the parallel parts.
Admittedly, Mark is from a general-purpose datacenter computer architecture background, which means that his idea of such a chip is probably more a Niagara + Rock combination rather than a set of ARMs of various abilities… but I think the overall argument is the most sensible for a chip that has to tackle a wide variety of workloads.
September 4th, 2008 @ 3:13 am
Didn’t this thread use to have many more comments? Did they go away when akismet was turned on?
September 4th, 2008 @ 12:48 pm
Jakob
Yes, there were many more comments. As I mentioned in my blog on DATE 2009, in the course of deleting some of the spam comments (before I activated Akismet), I accidentally wiped out some of the comments on this blog. My apologies to the commentors - if any of them can recreate the dialogue here it would be greatly appreciated. And my thanks again to Jakob for pointing me to Akismet; in the day since I activated it my spambot generated spam has increased from about 250 a day to 1000 a day!! and it is doing a great job of suppressing them.
Grant
September 4th, 2008 @ 2:08 pm
Ah. So that’s the legit comments you mentioned. I assumed it was about new comments on the more recent posts, but you are right — I recall spambots shooting into every thread available when I had the problem. Too bad, this discussion was really good.