LogP Modelling of List Algorithms

We present techniques for distributing lists for processing on distributed and shared memory architectures. The LogP cost model is extended for evaluating the schedules for the given problems and architectures. We consider both bounded and unbounded lists. The theoretical results are confirmed by measurements on a KSR-1. I. Introduction Most parallel algorithms operate on arrays because they are easy to distribute and redistribute, particularly, if their size is fixed, (c.f. [9]). However, arrays are not appropriate for a wide range of problems, e.g. for algorithms on graphs. But the lack of efficient distribution techniques of the elements forces programmers to use arrays instead of lists even if the latter is a better choice from a designer's point of view. The problem is even worse for the parallelization of sequential code, as the programmer usually does not consider parallel execution. The obvious solution, which would be the list converted into an array before distribution, is..