Date: 06 Oct 2011
From: jyrki@diku.dk
Subject: Thesis defence on parallel programming

M.Sc. thesis defence: Efficient chip-multi-processor programming

Defender: Sune Tougaard-Andersen
Censor: Kasper Graversen
Supervisor: Jyrki Katajainen
Time: Thursday, 13 October 2011 at 15.15-16.15
Place: Room 3-1-25

Abstract:

In this work a realistic machine model, the CMP-model, is investigated. 
This model captures the cache hierarchies on mainstream CMPs as well as 
the way these caches interact.

A parallel programming library for benchmarking is presented. The 
presented library introduces policy-based scheduling, allowing fair 
evaluation of scheduling algorithms. The parallel-depth-first scheduler 
theoretically performs better than the widely used work-stealing 
scheduler, in the CMP-cache model. Both schedulers are implemented in 
the benchmarking library.

Efficient parallelizations of the well-known sequential sorting 
algorithms quicksort and multi-way mergesort are analysed based on the 
CMP-cache model. The parallel quicksort algorithm is based on a 
parallelization of the in-place sequential partitioning algorithm. The 
parallel multi-way mergesort is based on a f-way partitioning algorithm 
that makes it possible to partition multiple sequences.

The presented library is used to evaluate the two analysed parallel 
sorting algorithms using both the implemented schedulers. We find that 
efficient parallel sorting algorithms are limited by memory access. We 
also find that the algorithmic techniques know from the external-memory 
model can be used to gain some performance on a CMP.

The thesis is available online at
http://www.diku.dk/~jyrki/PE-lab/Sune/

PE-lab's home page
http://www.diku.dk/~jyrki/PE-lab/