Calculational design of special purpose parallel algorithms

Abdallah, A. E. and Hawkins, J. (2000) Calculational design of special purpose parallel algorithms. In: Electronics, Circuits and Systems, 2000. ICECS 2000. The 7th IEEE International Conference. IEEE Conference Publications, pp. 261-267. ISBN 0-7803-6542-9

Full text not available from this repository. (Request a copy)

Abstract

This paper adopts a transformational programming approach for deriving massively parallel algorithms from functional specifications. It gives a brief description of a framework for relating key higher order functions such as map, reduce, and scan with communicating processes with different configurations. The parallelisation of many interesting functional algorithms can then be systematically synthesized by combining "off the shelf" parallel implementations of instances of these higher order functions. Efficiency in the final message-passing algorithms is achieved by exploiting data parallelism, for generating the intermediate results in parallel; and functional parallelism, for processing intermediate results in stages such that the output of one stage is simultaneously input to the next one. This approach is illustrated through a case study for testing whether all the elements of a given list are distinct. Bird-Meertens formalism is used to concisely carry out algebraic transformations.

Item Type: Book Section
Uncontrolled Keywords: algebraic transformations, special purpose parallel algorithms, transformational programming approach, massively parallel algorithms, functional specifications, higher order functions, communicating processes, final message-passing algorithms, Bird-Meertens formalism
Subjects: G400 Computer Science
Divisions: Faculty of Computing, Engineering and the Built Environment
Faculty of Computing, Engineering and the Built Environment > School of Computing and Digital Technology
Faculty of Computing, Engineering and the Built Environment > School of Computing and Digital Technology > Cyber Security
UoA Collections > UoA11: Computer Science and Informatics
Depositing User: Oana-Andreea Dumitrascu
Date Deposited: 07 Apr 2017 10:35
Last Modified: 07 Apr 2017 10:35
URI: http://www.open-access.bcu.ac.uk/id/eprint/4226

Actions (login required)

View Item View Item

Research

In this section...