tag:blogger.com,1999:blog-740627553249438779.post1330131897060629942..comments2011-06-25T21:23:53.460-07:00Comments on Amdahl's Law: Take $1000 out of my pocket for Thinking ParallelPatrick H. Maddenhttp://www.blogger.com/profile/13864861107703981134noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-740627553249438779.post-39888351596249235602011-06-25T21:23:53.460-07:002011-06-25T21:23:53.460-07:00Shortest path can be parallelized. The speedup wil...Shortest path can be parallelized. The speedup will not be impressive but it will be high enough to win your $1000. How can I claim it?<br /><br />On a different note, nice blog. Great work. I agree with you that there are codes that cannot be paralllelized regardless of the language and framework. See my post on the same topic here: http://www.futurechips.org/software-for-hardware-guys/parallel-programming-frameworks-solve-part-problem.html .Aater Sulemanhttp://www.blogger.com/profile/07068003544808755975noreply@blogger.comtag:blogger.com,1999:blog-740627553249438779.post-50812092164033680172009-07-28T12:30:28.616-07:002009-07-28T12:30:28.616-07:00While it is likely, it has not yet been proven tha...While it is likely, it has not yet been proven that the class of polylogarithmic time algorithms parallelized on polynomial prcoessors is not equal to the class P. This parallelizable class is called "Nick's Class" (NC) and NC != P is an open problem much like proving NP != P.<br /><br />So Amdahl's law is indeed Amdahl's conjecture until you prove that there are such things as necessarily serial code. Unfortunately, offering up $1000 and not getting a winner does not qualify as a proof that NC != P.<br /><br />It seems like it should be simpler to prove that NC = P and NP = P cannot both be true...Amirhttp://www.blogger.com/profile/05436827810418004991noreply@blogger.comtag:blogger.com,1999:blog-740627553249438779.post-71716337166308274772008-11-27T22:30:00.000-08:002008-11-27T22:30:00.000-08:00your blog is really interesting one. But I am sure...your blog is really interesting one. But I am sure we can a discuss on something:<BR/><BR/>http://avinashbhojwani.wordpress.com/2008/11/27/programmers-vs-architects/Avinashhttp://avinashbhojwani.wordpress.com/noreply@blogger.com