- author = "Kenneth Peter Williams",
- title = "Evolutionary Algorithms for Automatic Parallelization",
- school = "Department of Computer Science, University of Reading",
- 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 produced.
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
ISNI: 0000 0001 3569 2105",
