Overview
Motivation
With core counts on the rise, the sequential components of applications are becoming the major bottleneck in performance scaling (as predicted by Amdahl's law). We are therefore faced with the simultaneous problems of occupying an increasing number of cores and speeding up sequential sections of code. With this research, we attempt to reconcile these two seemingly incompatible problems with a new programming model which seeks to exploit the diversity present in certain algorithms and provide a speedup or a quality-of-result improvement. The core idea is to launch a number of instances of a key computational step in parallel and in isolation and benefit from the diversity present by picking the best to complete.
Opportunity in diversity
In this research, we seek to exploit the fact that for certain computations, multiple algorithms exist to arrive to a valid answer for the problem. This is particularly true for NP-hard problems where approximation algorithms and/or heuristics are used to arrive to a solution. We seek to demonstrate the wide presence of diversity across a wide range of problems and show how we can efficiently exploit it with our framework.
Status
A framework has been built and we have demonstrated improvements on a wide variety of problems from SAT solvers where we manage a super-linear speedup, to improving the quality of the result of genetic algorithms. A paper outlining the entire technique is currently under review.
We are currently looking at how to automatically transform a program from C/C++ to a N-way program to take advantage of diversity. We are also looking at other forms of diversity such as the diversity intrinsicly present across different types of hardware.
A poster summarizing the current status of the work is available.
Papers
I explored the implications of N-way parallelism on power consumptions in work presented at PESPMA 2010. See the paper and the slides in Keynote format or PDF format.
A poster and a presentation on this work were presented at PACT 2009. See the poster and the presentation in PowerPoint format or PDF format.
The first paper on this work appeared in the electronic proceedings of the First USENIX Workshop of Hot Topics in Parallelism (HotPar 2009). See the paper and the slides in PowerPoint format or PDF format.
