Synthesis of massively pipelined algorithms for list manipulation

Abdallah, Ali E. (1996) Synthesis of massively pipelined algorithms for list manipulation. In: Euro-Par'96 Parallel Processing. Springer, Berlin, Heidelberg, pp. 911-920. ISBN 978-3-540-70636-6

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

Abstract

This paper presents new, efficient, massively pipelined algorithms for several list manipulation operations. Transformational programming is used in the development of these algorithms from clear functional specifications to networks of linearly connected communicating processes in CSP. The derivation of each algorithm is achieved by transforming the specification into an instance of a generic parallel functional form called pipe pattern and then refining this into CSP. The approach is demonstrated by transforming quadratic functional algorithms for sorting, removing duplicates, and calculating the difference between two lists, into pipelined versions running in linear time with a linear number of processors. The refinement from functions to CSP processes is based on a formal treatment given in earlier work by the author. Derivation and reasoning are conducted using Bird-Meertens Formalism.

Item Type: Book Section
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 11:39
Last Modified: 07 Apr 2017 11:39
URI: http://www.open-access.bcu.ac.uk/id/eprint/4240

Actions (login required)

View Item View Item

Research

In this section...