Author: Dave Gomboc
Date: 15:36:29 10/04/01
Go up one level in this thread
On October 04, 2001 at 10:33:01, Miguel A. Ballicora wrote: >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. > >That is not Bruce's point (AFAIK). In a broad sense, for instance, alpha-beta >search applies to different games. It is possible that there is one type >of game where the "data" is "abnormal" when compared with other games. >In this particular game, the data has the particular feature that allows >this kind of speed ups. Bruce said that for instance "finding mate in ones type >of games" might be one example or the tree is full of that game is full of such >kind of anomalities. Of course, the data itself is no chosen, you choose the >game. You cannot have the speed up in checkers but you might have it in >Artic-Chess (I just made it up). Who knows, maybe some kind of smart pruning >is devised where you have the same kind of effect as "finding mate in ones" and >you can prune _immediately_ in certain kind of positions (maybe hitting some >tables, whatever). Then, you might have this super speedup. > >Then, a different question would be if you can rewrite the sequential algorithm. >Maybe you can, but it might be not convenient or just will have other >bottlenecks because of the rewriting (you add code so you might introduce an >overhead). > >Regards, >Miguel You can always rewrite the sequential algorithm, because you can simulate the parallel one. Any simulation overhead will be swamped by measurement error. Dave
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.