I defended my thesis in December 2010. You can download the thesis (in french) and the slides of the defense (in english).
As the gap between processor speed and memory speed is widening, efficiently using the cache is fundamental to improve performances of memory bounded applications. During my thesis, I designed and theoretically analyzed cache efficient techniques leading to significant speed up for scientific visualization applications. I first studied cache-oblivious algorithms that improve cache efficiency without knowledge of the cache parameters. Then I worked on parallel algorithms and work stealing schedulers to investigate the impact of parallelization strategies on cache behavior.
I developed a cache oblivious mesh layout, i.e. an algorithm to reorder points and cells of an unstructured mesh, that enhances locality of many visualization filters. I obtained theoretical performance guarantees and experimental validation showed speed up ranging from 1.3x to 4.9x both on CPU and GPU.
I proposed modifications of the min-max tree, an acceleration data structure for isosurface extraction. Memory consumption is reduced by a threefold factor and locality is further enhanced.
I designed a new parallelization strategy that efficiently uses the shared cache of multicore processors. I obtained a 20% gain compared to previous parallel algorithms.
I proposed a refined theoretical analysis of work stealing schedulers. This permits to evaluate the impact of modifications of the original technique for fine grain algorithms such as the parallelization strategy for shared caches.
I developed state of the art implementations of two common visualization filters: isosurface extraction and volume rendering by ray casting. These filters are developed in C for CPU and CUDA for GPU.
I enjoyed working with five undergraduate and one graduate students on projects related to my thesis such as parallel programming with work stealing and ray casting algorithms.
I participate weekly in working groups on scheduling and programming.