<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-192

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

T.H. Axford and M.S. Joy, List Processing in Parallel (August 1, 1991).

Abstract

A new model of list processing is proposed which is well suited to parallel implementation. Its main primitive functions are: "concatenate", which concatenates two lists; "split", which partitions a list into two parts; and "length", which gives the number of elements in a list. In the commonly used CREW P-RAM model of parallel computation, common high-level operations on lists such as "map" and "reduce" take O(log n) time in the new model as against O(n) time in the conventional head-tail-cons model of list processing. Parallel simulation of a number of simple programs in the functional language FLIC, using the new model of lists, gives parallel execution times consistent with this analysis. The programs tried use the high-level functions "map, filter" and "reduce", together with an implementation of Hoare's "quicksort".

<%@ include file="cited.html" %>

T.H. Axford and M.S. Joy, "List Processing Primitives for Parallel Computation", Computer Languages 19(1), pp. 1-17 (1993)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>