Title: Inherently parallel data structures

Proposer: Hans-Wolfgang Loidl

Suggested supervisors: Hans-Wolfgang Loidl

Goal: Develop and assess a library of inherently parallel data structures.


The classic design of efficient data structures has been strongly influenced by the sequential nature of processing them. Often linear data structures, such as lists or arrays, are used for high-performance computation, exploiting good data locality on algorithm level and good cache usage on system level.

With the advent of multi-core machines, data structures that do not force a sequential evaluation mechanism on the algorithms are highly desirable. They encourage the design of high-level data-oriented algorithms, specifying parallelism in a minimally intrusive way.

The aim of the project is to develop a library of inherently parallel list operations, to use them on classic algorithms and to assess the performance based on parallel Haskell implementations on multi-core architectures.

Resources required: Linux, Beowulf cluster, Parallel Haskell compiler (GHC-SMP)

Degree of difficulty: Moderate

Background needed: Functional programming background (Haskell, ML ...)


Last modified: Thu Jan 20 18:26:25 2011