Evolutionary Algorithms for Automatic Parallelization

Created by W.Langdon from gp-bibliography.bib Revision:1.4192

  author =       "Kenneth Peter Williams",
  title =        "Evolutionary Algorithms for Automatic
  school =       "Department of Computer Science, University of
  year =         "1998",
  address =      "Whiteknights Campus, Reading, UK",
  month =        dec # " 3",
  keywords =     "genetic algorithms, genetic programming, genetic
                 improvement, SBSE",
  URL =          "http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.265665",
  broken =       "ftp://ftp.pets.rdg.ac.uk/pub/cs/theses/PEDAL/williams98.txt",
  URL =          "ftp://ftp.pets.reading.ac.uk/pub/cs/theses/PEDAL/williams98.ps.gz",
  size =         "287 pages",
  abstract =     "The need for new techniques for use in automatically
                 parallelising compilers is emphasised by the limited
                 effectiveness of current automatic parallelization
                 tools. This presents a major barrier to the improved
                 use of parallel computers.

                 This thesis proposes that evolution provides an
                 effective way to parallelise sequential programs. The
                 contributions of this thesis are: description and
                 experimentation with direct and indirect
                 representations of an automatically parallelizing
                 compiler which are manipulated by 6 evolutionary
                 algorithms (EAs) across a set of 5 Fortran-77 benchmark
                 programs. One representation (called GT) naturally
                 gives rise to 5 genetic operators plus 1 heuristic
                 crossover operator, VLX-3. The other (GS) treats
                 compiler transformations as mutation operators.

                 In this research we present the Reading Evolutionary
                 Restructurer (Revolver) system which implements a range
                 of EAs to automatically parallelize sequential
                 Fortran-77 programs for a 12-node Meiko CS-1
                 message-passing architecture.

                 Issues involving the application of transformations to
                 code (called decoding) are investigated, three decoding
                 strategies developed, and comparative results

                 Detailed descriptions of a profiler and performance
                 estimation tool which have been implemented to analyse
                 the message-passing code generated by the EAs are
                 given. Static performance estimation of the code serves
                 as the fitness function of the EAs.

                 Detailed statistical comparisons are made between the
                 two representations, the three decoding strategies, and
                 the six genetic operators. Results show that EAs using
                 the GS representation consistently produce more
                 optimally parallelized code than that produced by EAs
                 using the GT representation. Most important result is
                 that the EAs were able to find a parallelization
                 strategy that would not have been obvious to a human
                 programmer using an interactive tool - therefore
                 showing that EAs have the ability to find novel
                 automatic parallelization strategies.",
  notes =        "Fig 2.19 overview of automatic Parallelization
                 research uk.bl.ethos.265665",

Genetic Programming entries for Kenneth Williams