June 22–26, 2014
Leipzig, Germany

Presentation Details

Name: Hourglass: A Bandwidth-Driven Performance Model for Sorting Algorithms
Time: Tuesday, June 24, 2014
02:45 pm - 03:15 pm
Room:   Hall 4
CCL - Congress Center Leipzig
Speaker:   Fabio Checconi, IBM T.J. Watson Research Center
Abstract:   We develop a bandwidth-driven performance model (referred to as Hourglass) for sorting algorithms. The model quantifies dominant data movements inherent to sorting algorithms (e.g., accesses to/from large buffers and network communication) and estimates a lower-bound execution time. We validate the model with parallel radix sort and merge sort as well as multinode sample sort on leadership high-performance IBM architectures.
The model helps better understand the inherent bottlenecks in a sorting algorithm – the users can leverage this model to optimize software and/or redesign the algorithm, and analyze architectural what-if scenarios to explore innovative designs.

Fabrizio Petrini, IBM T.J. Watson Research Center & Doe Hyun Yoon, Google