Author: Robert Hyatt
Date: 15:23:05 10/04/01
Go up one level in this thread
On October 04, 2001 at 17:47:07, Bruce Moreland wrote: >On October 04, 2001 at 15:00:30, Robert Hyatt wrote: > >>On October 04, 2001 at 02:25:11, Bruce Moreland wrote: >> >>> >>>The solution is always returned in one comparison in the second thread. >> >>If that is the case, it will always be returned in one comparison in the serial >>algorithm too, Because I will always start _there_. >>> >>>In the sequential case, with an array length of D, the number of compares >>>necessary is D. In the parallel case, assuming that both threads run at the >>>same rate, the number of comparisons is 2. With a sufficiently large value of >>>D, the difference between D and 2 will dominate the parallel overhead. >>> >> >> >>So. You are picking 1 out of N possible cases and saying "super-linear". Do >>you _know_ that case comes up every time? If so, I start the serial test there >>first and I get the answer in _one_ comparison. >> >>If you don't know where the key lies, then you have to analyze the algorithm >>for the "average" case. And there you always get <= 2.0 speedup. >> >>I don't understand why that is hard to grasp. > >In the case of my simple algorithm, if you had been told to write a parallel >algorithm to process it, and a serial algorithm to process it, you may have >written both the algorithms the way I suggested. Perhaps you wouldn't have gone >backwards with the second thread, but in a group of 1000 students, I bet a few >would have. I disagree. This is a variation of the first assignment I give in the parallel programming course here, except the task is to find the min and max values in a big array. And without exception, because the code is so logical, everyone breaks the list up into chunks and process each chunk with the exact same piece of code. In lightweight threads, this is a must-do for the obvious solution, since you apply the same min/max function to different parts of the array in parallel. It would be illogical to do some from the front and one from the back because that would double that part of the code. > >If you had done this, and then I had dumped some "mystery data" on you, which >happened to be a series of null-terminated strings, you would have noticed that >the parallel algorithm would have experienced a super-linear speedup. For one test case. And I wouldn't have given it a moment's thought because I see this all the time. If it produced a super-linear speedup for several sets of data, that would get my attention, and I would then start looking to see what is wrong with the serial algorithm. Because it _must_ have a flaw since super-linear is an impossible thing to do on average cases. > >I think that there are some people who read this group who, if they hadn't >bothered to figure out why this had happened, would insist that the student had >a bug, because such a performance increase was impossible. Not from reading what I have wrote, I hope. I have _always_ said that I see super-linear speedups on special cases all the time. But not over a larger number of test cases that represent typical test sets. > >Both the serial and parallel algorithms are fine. The problem was with the >data. If the student had avoided getting stomped to death by the teacher for >being a computer science apostate, and had taken the trouble to understand the >super-linear speedup, rather than shutting his eyes denying its possibility, he >would have noted the obvious pattern in the data, understood it fully, and >changed the serial algorithm so it would work better on this data. First, _my_ students won't get stomped. I show them a super-linear speedup the _first_ day of class. And I then explain why. And then I explain why it can not be done on typical test cases. And then we move on to actual coding examples... > >Maybe. It would actually work worse on other data, since going backwards is >less efficient than going forwards. Why would that be true? On a Cray, for example, it makes absolutely no difference. The vector operators work in a +1 stride or a -1 stride with no headaches or performance loss. Ditto on the PC. You just load the entire cache line, but use the last 4 bytes first, rather than the first 4 bytes. I don't see how that would hurt. > >Perhaps this would have stimulated a discussion about how to write such an >algorithm, in order to avoid pathologies while retaining performance in more >entropic cases. Perhaps the serial algorithm should have been modified to check >the first and last elements first, a change that would be a waste of time if all >data was perfectly entropic. > >Perhaps as a result, someone would have learned something, and some progress >would have been made along some axis. > That is the goal of every class I teach. That some progress is made. And that has been the point of this discussion every time I have replied. That super- linear _can_ happen in odd cases. But overall, the speedup will always be <= N, where N is the number of processes. Because if you can produce a super-linear speedup in one case, you will also, by necessity, produce a < linear speedup in another case. And the very best you can hope for is to break even and get N. In reality, that is very uncommon and you end up at < N. >If the student is labelled an idiot, and Isaac Newton is invoked against him, no >progress is made and nobody learns anything. Students aren't labeled "idiots" here. However, if one shows up with a super-linear speedup and claims that he produces a super-linear speedup, period. Then he will be chastised and sent away to run more tests. He will then come back and say "oops... I see what you mean." > >The pathological data had a very heavy and obvious pattern in it. It is >possible that other patterns exist in real-world data, and there is an algorithm >other than the initial sequential algorithm (which has got to be provably >perfect if the data is entropic) would work better. The key is understanding >the data, but this is not always completely possible. > >A game tree is not completely entropic either, and I doubt it is well understood >by the people who manipulate them. It may have some patterns in it as well, >which might be eploited either intentionally or unintentionally, by changes in >an algorithm. > >Taking a serial alpha-beta algorithm (with pruning and extensions and hash >tables and all that) and adding parallelism to it is a change that could result >in an improvement in performance, because the new algorithm does not search the >same tree in the same order as the old one does. > But the point still is, if you can produce a consistent super-linear speedup on a lot of test positions, I will time-slice and search a node from this path, then a node from that path, just like the parallel algorithm would, with the only difference being that I never search two nodes at _exactly_ the same time, only that I search one node from each path in two adjacent time slots. And _that_ will run more efficiently than the normal serial algorithm. And I choose to use that from here on once you prove that the data is so pathological that this always happens. And now your super-linear speedup is gone, because the serial-parallel algorithm is better and you are no longer 2x faster than _it_. >This is why I think that someone who claims to have found a super-linear speedup >when doing a parallel search should not be labeled a computer science apostate. >A chess tree probably has enough entropy in it that the claim is due to a bug, >random chance, or bad performance measurement technique, but it is always >possible that some common orderliness inside the tree has been found and >exploited. > >bruce Sorry, but there are simply some things that are impossible. Perpetual motion. A pyramid scheme where _everybody_ wins. Super-linear speedups. All fit into the same category. Nice ideas but impossible in the real-world. Again, if someone shows me a parallel search that _consistently_ produces a super-linear speedup, I will instantly have a better serial algorithm to search trees, using the time-slicing approach. And then the super-linear speedup is once again consigned to the netherworld of mythology.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.