Personal tools
You are here: Home Events ICSA Colloquium Talk

ICSA Colloquium Talk

— filed under:

Title: Branch Prediction, Sorting and Complexity: Presentation by Dr David Gregg, Dept of Computer Science, Trinity College, Dublin.

  • Colloquium Series
When Feb 10, 2011
from 03:30 PM to 04:30 PM
Where 4.31/4.33
Add event to calendar vCal

One of the most important principles of modern computer architecture is to optimize for the common case. The result is that processors contain such features and caches, TLBs and branch predictors. Traditional algorithmic analysis has assumed a very simple machine model, but over the last decade there has been a great deal of interest in algorithms that take account of the cache. Branch prediction can also greatly affect performance, particularly for algorithms that perform large numbers of comparisons. In this talk we examine the branch prediction performance of several of the most important sorting algorithms. We find that different algorithms with the same overall time complexity can cause asymptotically different numbers of branch mispredictions, and that branch mispredictions can dominate the execution time of some algorithms. Through a combination of experimentation and analysis we show that insertion sort and quicksort have desirable branch prediction properties, which help to explain their good performance in practice. Finally, we argue that the interaction between architecture and algorithms can have a large impact on performance, and that understanding these interactions can be valuable for both architects and algorithm designers.


Bio: Dr David Gregg is a senior lecturer in Computer Science and Fellow of Trinity College Dublin, where he leads the software Tools group. His research deals with compilers, program optimization and processor microarchitecture, with a particular focus on software optimization for multi-core architectures. His work includes compiler optimization, implementation of the Java virtual machine, compiling scripting languages, algorithm design, and the interaction of software with architecture. Dr Gregg has supervised six PhD students to completion, and currently supervises four PhD students. He has published more than 40 papers in international journals, including PLDI, TOPLAS, TACO, CGO and VEE. He has served on the programme committee of leading conferences such as ASPLOS, PACT and PLDI and as general chair of the ACM 2008 Virtual Execution Environments (VEE) conference. 

Document Actions