AutoPar: automating the parallelization of functional programs

As the pervasiveness of parallel architectures in computing increases, so does the need for efficiently implemented parallel software. However, the development of parallel software is inherently more difficult than that of sequential software and is fraught with many pitfalls, such as race conditions and locking issues, amongst others. Developers are typically more comfortable developing sequentially, yet as the limitations of single-core processor speeds are reached, they have no choice but to reach for parallel implementations to obtain the required performance increases. An obvious solution to the parallelisation problem is to allow developers to continue to develop sequentially and generate efficient parallel programs automatically from these sequential ones. There are many existing techniques which automate the parallelisation process, however these techniques place many constraints upon the programs they are applicable to. This thesis defines a fully automatic parallelisation technique which places no restriction on its input programs and is applicable to programs defined using any data-type. The technique consists of two components: the first allows a given program to be redefined in terms of well-partitioned data. The second then explicitly parallelises the resulting program using Glasgow parallel Haskell. The technique is applied to several Haskell programs, the results of which have then been benchmarked with respect to the performance of handparallelised versions of the original programs. The benchmarking process has recorded the execution time and parallel performance of each benchmark program. The evaluation of the benchmark results has allowed for the merit of the automated parallelisation technique to be shown