Author: Uri Blass
Date: 01:56:08 10/04/01
Go up one level in this thread
On October 04, 2001 at 03:03:37, Jeremiah Penery wrote: >On October 04, 2001 at 02:01:59, Bruce Moreland wrote: > >>On October 03, 2001 at 18:53:31, Dave Gomboc wrote: >> >>>Observing that the parallel algorithm was super-linearly quicker immediately >>>gives rise to a superior sequential algorithm: alternate checking from the front >>>of the array and the back of the array for the zero. It would quickly be >>>observed that the parallel algorithm does not have super-linear speedup over >>>this superior sequential algorithm. In addition, the sequential algorithm may >>>be further optimized by ignoring the front of the array altogether, which would >>>reduce the parallel speedup further. >>> >>>To ignore the superior sequential algorithm and instead publish results >>>comparing only the original, poor sequential algorithm with the parallel >>>algorithm is not merely disingenuous but simply bad science. >>> >>>Dave >> >>My sequential algorithm is just fine if you have no idea what the data looks >>like. My parallel algorithm is also just fine if you have no idea what the data >>looks like. >> >>The fact that the data encountered in real life creates a worst case for the >>sequential algorithm and a best case for the parallel algorithm is a happy >>coincidence. > >The problem is that the data won't _always_ be that way. If you average the >parallel speedup over all possible sets of data for that algorithm, the speedup >will be provably not super-linear. You can't just pick one data point where you >do get a super-linear speedup and suggest that it always works that way. > >>It also refutes the idea that a dual-processor algorithm cannot be >>faster than 2x the speed of the single-processor algorithm that it is derived >>from, which was the point of the exercise. I was trying to demonstrate that the >>parallel algorithm is not equivalent to the single-processor algorithm running >>on two processors -- it is a different algorithm. >> >>Of course, if you know what the data looks like, you can make a sequential >>algorithm that solves the problem, but it is permissible to stipulate that you >>don't know what the data looks like. > >Which is exactly why you can't say that you will get a super-linear speedup on >average. > >>Bob was saying that you can't get a more than 2x speedup with two processors no >>way no how except in some pathological cases. > >I don't think that's what he was saying. I think he is simply saying that the >average must be less than N, for N processors. > >>I could have responded by suggesting that pathological cases could be common in >>some domains, but I thought this might be too big a pill to swallow, so I tried >>to come up with some examples that I thought everyone could understand and agree >>on. >> >>Silly me. >> >>The long argument about whether dragging something is necessarily *more* >>efficient than carrying something is especially crazy, as anyone who has tried >>to get a recalcitrant two year-old up a flight of stairs can tell you instantly. >> Of course now I've changed that example slightly and I look forward to another >>long argument about thermodynamics as applied to little kids. Or I should say, >>I look forward to ignoring such an argument. > >>I provided an overly simple but not completely crazy example of an algorithm >>where you'd get way more than 2x speedup if you parallelized it in an obvious >>way for two processors. Bob proceeded to discuss another algorithm entirely. > >Bob also showed that, on average, the speedup for that algorithm is less than >2.0. That is the entire point of this discussion. > >>I have better things to do than try to convince a mule that it is stubborn. The >>mule will be stubborn no matter what I say, since that is its nature. I have >>better things to do than spend time arguing with people who don't listen. > >I think that's a bit unfair. He may be guilty of it, but is the other side not >guilty of being overly-stubborn? No The difference is that the other side(I and Bruce) do not say that they know that there is a super linear improvement but that we cannot say that it is impossible with the known algorithm of today. I said that the only way is to investigate the problem by test positions in order to see if programs can get a super linear improvement from 2 processors. Here are some cases when Deep Fritz changed it's mind after long search. These positions are not good for tactical test suite and are only for Deep Fritz The last numbers are the depthes that Deep Fritz prefered the move when I considered only the depth of finding the suggested move in the last time as relevant depth 17-20 means that deep fritz considered the move as best at depth 17-20 and did not change it's mind at itearations 17-19 after finding the suggested move at depth 17 15,16-19 means that the sggested move was rejected at depth 15 only to be considered aqain as best at depth 16. cases like 14 16-19 were not mentioned if they happened It may be interesting to compare Deep Fritz parallel search times with deep Fritz not parallel search time(I am not sure if Deep Fritz is going to find always the suggested move because different hash tables and parallel search may cause some changes but I believe that it is going to find the suggested move in most of the cases at the relevant depthes). 1rb3k1/5pbp/6p1/1p2p3/8/1PPB2P1/4NP1P/5RK1 w - - 0 1 bm f4 17-20 1rb3k1/5pbp/6p1/1p2p3/2P5/1P1B2P1/4NP1P/5RK1 b - - 0 1 bm Ba6 17-21 2kr4/pppq1pp1/2nb1n2/3p4/5Pb1/2PPP2r/PP1BB1NP/R2QKN1R b KQ - 0 1 bm g5 19 2kr4/ppp2p2/8/6P1/3p1P1q/2PP2Nr/PP1Q1K1n/6RR b - - 0 1 bm c5 17 r2qkb1r/5pp1/p3p2p/8/1p1NP1n1/4B3/PPPQ3P/2KRR3 w kq - 0 1 bm Bf4 15,16-19 r2qkb1r/5pp1/p3p2p/4n3/1p1NP1P1/4B3/PPPQ3P/2KRR3 b kq - 0 1 bm Nc4 18-19 r2qkb1r/5pp1/p3p2p/8/1p1NPBn1/8/PPPQ3P/2KRR3 b kq - 0 1 bm g5 19 r2qkb1r/5pp1/p6p/4p3/1p1NPBn1/8/PPPQ3P/2KRR3 w kq - 0 1 bm Qg2 19 r4rk1/5pp1/1q2p2p/p1b1n3/1p1NP1P1/4B3/PPPRQ2P/1K1R4 b - - 0 1 bm Rfd8 18-19 6k1/5pp1/r3p2p/p1b1n3/1p2P1PP/1N6/PPPB4/1K1R4 b - - 0 1 bm Be7 18-19 r2r2k1/5pp1/1q2p2p/2b1n3/pp1NP1P1/4B2P/PPPRQ3/K2R4 b - - 0 1 bm Rd6 17 r2r2k1/5pp1/1q2p2p/p1b1n3/1p1NP1PP/4B3/PPPRQ3/1K1R4 b - h3 0 1 bm Rd7 18-20 r2r2k1/6p1/1q2pp1p/p1b1n3/1p1NP1P1/4B2P/PPPRQ3/1K1R4 w - - 0 1 bm b3 18 6k1/5pp1/1q2p2p/8/pp2P1P1/4b2P/PPP5/1KBQ4 w - - 0 1 bm Qe1 18-20 r2r2k1/5pp1/1q2p2p/2b1n1P1/p2NP3/1p2B2P/PPPRQ3/K2R4 b - - 0 1 bm hxg5 16-18 2rr2k1/5pp1/1q2p2p/2b1n1P1/p2NP3/Pp2B2P/1PPRQ3/K2R4 b - - 0 1 bm Bxd4 14-19 2rr2k1/5pp1/1q2p2p/4n3/p2NP1P1/PpP1B2P/3RQ3/K2R4 b - - 0 1 bm Qa5 17,18
This page took 0.01 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.