Constructing Parallel Programs Using Homomorphism
Date Issued
2015
Date
2015
Author(s)
Chi, Yun-Yan
Abstract
Parallel programming plays an very important role in nowadays world. To develop a parallel program, however, is not a simple task. Traditionally programmers are used to and have to rewrite a sequential program to its parallel version. This, however, takes lots of extra efforts and times. It natural that programmers want to have an automatic method for saving themselves from re-implementing the same algorithm twice. Therefore plenty of previous works have tried to develop methods for constructing and synthesising parallel programs from existing sequential programs. One of potential ways is using program derivation which allows us to construct a program definition from its specification, or, in this case, from existing definitions and properties. In this thesis, we use homomorphism as a model of parallel programs and focus on programs that handle the well-known linear data structure, list. We realise homomorphism as two specialisations: the list-homomorphism, which works as properties and is used for modelling parallel list-reducing programs; and the list- unhomomorphism, for parallel list-generating programs. By taking advantage of the third list-homomorphism theorem we introduce two methods to derive parallel list- reducing programs from its sequential definitions. The first method allows us to transform a proof of bi-foldability to a proof of existing of list-homomorphism where, obviously, contains the definition of list-homomorphism itself. The second one, provides us a syntactical approach to construct a list-homomorphism once an right weak inverse of the program we want to parallelise can be designed and picked. For list- unhomomorphism, on the other hand, we develop a dual theorem of the third list- homomorphism theorem so that list-generating programs can be constructed from its sequential definitions once the sufficient conditions of two essential properties of list- unhomomorphism can be satisfied.
Subjects
Parallel Program
Functional Program
List-Homomorphism
Third List- Homomorphism Theorem
Program Derivation
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-104-R00725051-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):2c855f3982450808f9bba01f1ce39144