israel@profundo.rutgers.edu (Nelken) (12/10/88)
Recently there have been messages in this newsgrup about superlinear speedups in heuristic algorithms. The claim was that a uniprocessor might go down the wrong path in the tree because of some misleading heuristics. A parallel machine can explore several subtrees concurrently and might thus find the correct solution faster. In some cases the parallel program might be more than p times as fast as the sequential one. But wait! A uniprocessor can also be programmed to exlore the tree in the same order as the parallel machine. It may explore a node in one subtree and then explore a node in an entirely different subtree. If this search strategy is used, there is no superlinear speedup. The problem lies in the misuse of terms. Here are the accepted definitions: T(p) - the time required by a parallel machine (with p processors) to run the BEST parallel algorithm. T(1) - the time required by a uniprocessor with similar capabilities to run the BEST sequential algorithm. It is very difficult to claim that a particular heuristic algorithm is "best". In fact, the so called "superlinear" speedups that have been claimed are due to a non-optimal search strategy in the sequential case (we didn't use the best algorithm). True superlinear speedup would occur if, under the above definitions, T(1) >= p * T(p) In this discussion I avoided the questions of memory, cache and paging overheads which may affect a parallel machine differently than a uniprocessor. Izzy Nelken Department of Computer Science Hill Center, Rutgers University New Brunswick, NJ 08903
eugene@eos.arc.nasa.gov (Eugene Miya) (12/12/88)
In article <3808@hubcap.UUCP> israel@profundo.rutgers.edu (Nelken) writes: >Recently there have been messages in this newsgrup about superlinear >speedups in heuristic algorithms. The claim was that a uniprocessor >might go down the wrong path in the tree > . . . >The problem lies in the misuse of terms. This note reminded me of something: non-CS end-users think of parallelism in the spatial/geometric sense (typically grids and lattices). --------- | | | | | --------- | | | | | --------- | | | | | --------- Nice and regular. CS-types tend to think of graphs and trees [which have a greater degree of non-determinism]. . / \ /\ /\ I know there is an equivalence between the two, but it is amusing to here these two communities pass each other like ships in the night. Some one else brought up the term "apples and oranges." {Motherhood} Don't forget that both are made of the same basic genetic material (common stuff). I thought about going to the library to burst this analogy by getting chromosome counts. It's all going to depend on how close or far you look at these analyses. Another gross generalization from --eugene miya, NASA Ames Research Center, eugene@aurora.arc.nasa.gov resident cynic at the Rock of Ages Home for Retired Hackers: "Mailers?! HA!", "If my mail does not reach you, please accept my apology." {uunet,hplabs,ncar,decwrl,allegra,tektronix}!ames!aurora!eugene "Send mail, avoid follow-ups. If enough, I'll summarize."