Parallel Data Structures Problem description:

Literature on parallel algorithms and data structures is vast. In fact, the literature has grown with the advent of GPGPU computing just a few years ago. However, most of the literature targets SIMD (single instruction, multiple data) hardware, which means that data structures are still sequential at their heart. In contrast to this, natural systems, and more recently new hardware, operates in a fashion which is asynchronous, solving MIMD or MISD (multiple instruction multiple data, multiple instruction single data) problems. As a consequence, we are interested in finding existing data structures that operate in an asynchronous fashion, and their benefits or drawbacks when compared to other data structures. The student shall research the state of the art of data structures for MIMD and MISD problems. Hence, the student will have to • Identify key “ingredients ” for parallel data structures. • Give an overview of the most relevant of these and reference the related literature. • Point out example problems for which these algorithms are highly suited. As a plus, the student may implement one or more of the data structures to show examples, or think about examples how to employ such data structures given special hardware, e.g. SpiNNaker. This task requires • a solid interest in parallel computing and • some knowledge of theoretical computer science (e.g. O-Notation)