From: Stefan Bruda Newsgroups: comp.parallel Subject: Re: superlinear question Date: 26 Oct 1998 20:14:59 GMT Organization: Queen's University Approved: bigrigg@cs.cmu.edu Message-Id: <712l83$h7m$1@encore.ece.cmu.edu> Originator: bigrigg@ece.cmu.edu Alain Coetmeur wrote: > >Superlinear speedup = (perpetual motion machine || perverse serial > >implementation). > > I agree with this point of view, but I'll add some point. > > if you can have a superlinear speed up, then > you could use the way the parallel version > schedule the operation, on a sequential machine... > [...] > to finish I'll reapeat my conviction, similar to randy's: > if you have superlinear speedup, it is only that you compare > unfairly the programs... > unfaily because of algorithm, because of memory size, > because of cache size, because of scheduling... Hi. While I agree with the point that the mentioned examples (Randy's) are perverse, I disagree with the opinion that superlinear speedup is impossible. First example that contradicts this is the parallel state space search (e.g., branch and bound), which has been mentioned in a previous message. See for example T.-H. Lai, S. Sahni, Anomalies in Parallel Branch-and-Bound Algorithms, Commun. ACM, 27, 1984, 594--602. However, this behaviour manifests itself only in some particular instances of the search space, hence the superunitary behaviour disappears when considering the worst-case analysis. On the other hand, if you consider some real-time component, then superunitary behaviour happens again, this time in the worst-case analysis too. For an example of such a paradigm, see F. Luccio, L. Pagli, Computing with Time--Varying Data: Sequential Complexity and Parallel Speed--up, Theory of Computing Systems, 31(1), 1998, 5--26. The results here have been improved in S. D. Bruda, S. G. Akl, On the Data-Accumulating Paradigm, Proceedings of the Fourth International Conference on Computer Science and Informatics, 1998. Available at http://www.qucis.queensu.ca/~bruda/data_accum/index.html and S. D. Bruda, S. G. Akl, The Characterization of Data-Accumulating Algorithms, submitted. Available at http://www.qucis.queensu.ca/~bruda/www/data_accum2/index.html Also, for a survey of paradigm that allow superunitary behaviour, see S. G. Akl, L. F. Lindon, Paradigms Admitting Superunitary Behaviour in Parallel Computation, Parallel Algorithms and Applications, 11, 1997, 129--153. and S. G. Akl, Parallel Computation: Models and Methods, Prentice-Hall, 1997 (Chapter 12). Regards, Stefan -- Articles to bigrigg+parallel@cs.cmu.edu (Admin: bigrigg@cs.cmu.edu) Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel