(Message inbox:989)
 -- using template mhl.format --
Date:    Sat, 05 Aug 95 19:16:37 EDT
To:      GA-List@AIC.NRL.NAVY.MIL, gaphd-list@dcs.warwick.ac.uk

From:    Ted.Belding@umich.edu (Theodore C. Belding)
Subject: superlinear speedup references

Return-Path: <martyn@dcs.warwick.ac.uk>
Newsgroups: comp.ai.genetic
Organization: University of Michigan CSE Division

(A copy of this message has also been posted to the following newsgroups:
comp.ai.genetic)

I'm currently writing a paper on the various types of superlinear 
speedup that are possible, specifically in parallel genetic algorithms.  
I thought in the meantime I'd post a bibliography of what I've come 
across so far, since it was suggested at the ICGA parallel GA workshop 
that some sort of summary would be useful.  Corrections and additions 
are, of course, gratefully accepted.  Pardon the kludgy LaTeX formatting; 
BibTeX and I don't seem to get along very well...

Many thanks to the organizers and participants of the ICGA parallel GA
workshop for a vigorous and useful discussion, and to Markus Schwehm 
and Quentin Stout for some references!
-Ted

\section{definitions of speedup}

Foster, I. (1995). {\it Designing and Building Parallel Programs.}
Reading, MA: Addison-Wesley. URL: {http://www.mcs.anl.gov/dbpp}

Golub, G., and J. M. Ortega.  (1993). {\it Scientific Computing: An
Introduction with Parallel Computing.} Boston: Academic Press.

Herzog, U. (1988). Performance evaluation principles for vector- and
multiprocessor systems. {\it Parallel Computing} {\bf 7}:425--438.

Leighton, F. T. (1992). {\it Introduction to parallel algorithms and
architectures: arrays, trees, hypercubes.} San Mateo, CA: Morgan
Kaufmann.


\section{The great debate --- is superlinear speedup possible?}

Faber, V., O. M. Lubeck, and A. B. White, Jr. (1986). Superlinear
speedup of an efficient sequential algorithm is not possible. {\it
Parallel Computing} {\bf 3}:259--260.

Faber, V., O. M. Lubeck, and A. B. White, Jr. (1987). Comments on the
paper ``Parallel efficiency can be greater than unity''. {\it Parallel
Computing} {\bf 4}:209--210.

Fischer, D. (1991). On superlinear speedups. {\it Parallel Computing}
{\bf 17}:695--697.

Forrest, S. (1990).  Emergent computation: self-organizing, collective,
and cooperative phenomena in natural and artificial computing networks.
{\it Physica D} {\bf 42}:1--11.  Reprinted in Forrest, S. (Ed.), {\it
Emergent Computation,} pp. 1--11. Cambridge, MA: MIT Press, 1991.

Jan{\ss}en, R. (1987). A note on superlinear speedup. {\it Parallel
Computing} {\bf 4}:211--213.

Parkinson, D. (1986). Parallel efficiency can be greater than unity.
{\it Parallel Computing} {\bf 3}:261--262.

Schneck, P. B. (1986). Superlinear speed-up and the halting problem.
{\it Software -- Practice and Experience} 16(9):781--782.


\section{Cache-effect and related I/O or memory-hierarchy superlinear
speedup}

Abu-Sufah, A., H. E. Husmann, and D. J. Kuck. (1986). On input/output
speedup in tightly coupled multiprocessors.  {\it IEEE Transactions on
Computers} {\bf C-35}(6):520--530.

Belding, T. C. (1995). The distributed genetic algorithm revisited. In
Eshelman, L. J. (Ed.), {\it Proceedings of the Sixth International
Conference on Genetic Algorithms,} pp. 114--121. San Francisco, CA:
Morgan Kaufmann. URL: {http://www.engin.umich.edu/~streak/dga.html}


\section{Superlinear speedup in parallel search}

Imai, M., Y. Yoshida, and T. Fukumura. (1979).  A parallel searching
scheme for multiprocessor systems and its application to combinatorial
problems. {\it IJCAI} 1979:416--418.

Janakiram, V. K., E. F. Gehringer, D. P. Agrawal, and R. Mehrotra.
(1988). A randomized parallel branch-and-bound algorithm. {\it
International Journal of Parallel Programming} {\bf 17}(3):277-301.

Kornfeld, W. A. (1981). The use of parallelism to implement a heuristic
search. {\it IJCAI} 1981:575--580.

Kumar, V., A. Grama, A. Gupta, and G. Karypis. (1994). {\it
Introduction to parallel computing: design and analysis of parallel
algorithms.} Redwood City, CA: Benjamin/Cummings.

Lai, T.-H., and S. Sahni. (1984). Anomalies in parallel
branch-and-bound algorithms.  {\it Communications of the ACM,} {\bf
27}(6):594--602.

Li, G.-J., and B. W. Wah. (1986). Coping with anomalies in parallel
branch-and-bound algorithms.  {\it IEEE Transactions on Computers} {\bf
C-35}(6):568--573.

Mehrotra, R., and E. Gehringer. (1985). Superlinear speedup through
randomized algorithms.  In {\it Proceedings of the 1985 International
Conference on Parallel Processing,} St. Charles, IL, pp. 291--300.

Quinn, M. J., and N. Deo. (1986). An upper bound for the speedup of
parallel best-bound branch-and-bound algorithms. {\it {BIT}} {\bf
26}:35--43.

Rao, V. N., and V. Kumar. (1988). Superlinear speedup in parallel
state-space search. In Nori, K. V., and S. Kumar (Eds.), {\it
Foundations of Software Technology and Theoretical Computer Science,
8th Conference,} Pune, India, December 21--23, 1988, Proceedings.
Lecture Notes in Computer Science Vol. 338, pp. 161--174. Berlin:
Springer-Verlag.

Speckenmeyer, E. (1987). Superlinear speedup for parallel backtracking.
In Houstis, E. N., T. S. Papatheodorou, and C. D. Polychronopoulos
(Eds.), {\it Supercomputing: 1st International Conference,} Athens,
Greece, June 8--12, 1987, Proceedings.  Lecture Notes in Computer
Science Vol. 297, pp. 985--993. Berlin: Springer-Verlag.

Speckenmeyer, E. (1988). Is average superlinear speedup possible? In
B\"orger, E., H. K. B\"uning, and M. M. Richter (Eds.), {\it CSL '88:
2nd Workshop on Computer Science Logic,} Duisburg, FRG, October 3--7,
1988, Proceedings.  Lecture Notes in Computer Science Vol. 385, pp.
301--312. Berlin: Springer-Verlag.

Tinker, P. A. (1988).  Performance of an {OR}-parallel logic
programming system. {\it International Journal of Parallel Programming}
{\bf 17}(1):59--92.


\section{Other superlinear speedup}

Boreddy, J., and A. Paulraj. (1990). On the performance of transputer
arrays for dense linear systems. {\it Parallel Computing} {\bf
15}:107--117. %superlinear speedup due to the reduction in array
indexing overheads in %multitransputer arrays


\section{Search-related superlinear speedup in genetic algorithms,
genetic programming, and classifier systems}

Baiardi, F., P. Gambini, A. Giani, and A. Starita. (1995). Improving
learning through rule cooperation in parallel classifier systems. URL:
{ftp://di.unipi.it/pub/Papers/giani/icgaws.ps.Z}

Collins. R. (1992). {\it Studies in Artificial Evolution.} Ph.D.
thesis, University of California -- Los Angeles, Los Angeles, CA. URL:
{ftp://ftp.cognet.ucla.edu/pub/alife/papers/collins-phd?.ps.gz} %see
chap. 7.

Giani, A., F. Baiardi, and A. Starita. (1995). PANIC: A parallel
evolutionary rule based system.  In {\it EP95}. URL:
{ftp://di.unipi.it/pub/Papers/giani/ep95.ps.Z}

Goldberg, D. E., H. Kargupta, J. Horn, and E. Cantu-Paz. (1995).
Critical deme size for serial and parallel genetic algorithms. IlliGAL
Report 95002. Urbana, IL: University of Illinois at Urbana-Champaign.

Koza, J., and D. Andre. (1995). Parallel genetic programming on a
network of transputers.  Stanford University Technical Report
STAN-CS-TR-95-1542. Stanford, CA: Stanford University. URL:
{ftp://elib.stanford.edu/pub/reports/cs/tr/95/1542/}

Maresky, J. (1994). {\it On Efficient Communication in Distributed
Genetic Algorithms.} M.S. Dissertation, Institute of Computer Science,
The Hebrew University of Jerusalem. URL:
{ftp://ftp.huji.ac.il/users/jonathan/msc-maresky.ps.gz} %superlinear
speedup

M{\"u}hlenbein, H., M. Schomisch, and J. Born. (1991). The parallel
genetic algorithm as function optimizer. {\it Parallel Computing} {\bf
17}:619--632.

Punch, W. F. (1995). Re: Superlinear speedup.  {\it Genetic Algorithm
Digest} {\bf 9}(15). URL:
{http://www.aic.nrl.navy.mil:80/galist/digests/}

Shonkwiler, R. (1993). Parallel genetic algorithms. In Forrest, S.
(Ed.), {\it Proceedings of the Fifth International Conference on
Genetic Algorithms,} pp. 199--205. San Mateo, CA: Morgan Kaufmann.

Shonkwiler, R., and E. Van Vleck. (1994). Parallel speed-up of Monte
Carlo methods for global optimization. {\it Journal of Complexity} {\bf
10}(1):64--95.

Shonkwiler, R., F. Mendivil, and A. Deliu. (1991). Genetic algorithms
for the 1-D fractal inverse problem. In Belew, R., and L. Booker
(Eds.), {\it Proceedings of the Fourth International Conference on
Genetic Algorithms,} pp. 495--501. San Mateo, CA: Morgan Kaufmann.

Tanese, R. (1987). Parallel genetic algorithms for a hypercube. In
Grefenstette, J. J. (Ed.), {\it Genetic Algorithms and Their
Applications: Proceedings of the Second International Conference on
Genetic Algorithms,} pp. 177-183.  Hillsdale, NJ: Lawrence Erlbaum.

--
Ted Belding           Ted.Belding@umich.edu or streak@engin.umich.edu
University of Michigan   Division of Computer Science and Engineering